Landscape Complexity for the Empirical Risk of Generalized Linear Models

Antoine Maillard, Gérard Ben Arous, Giulio Biroli
Proceedings of The First Mathematical and Scientific Machine Learning Conference, PMLR 107:287-327, 2020.

Abstract

We present a method to obtain the average and the typical value of the number of critical points of the empirical risk landscape for generalized linear estimation problems and variants. This represents a substantial extension of previous applications of the Kac-Rice method since it allows to analyze the critical points of high dimensional non-Gaussian random functions. We obtain a rigorous explicit variational formula for the \emph{annealed complexity}, which is the logarithm of the average number of critical points at fixed value of the empirical risk. This result is simplified, and extended, using the non-rigorous Kac-Rice replicated method from theoretical physics. In this way we find an explicit variational formula for the \emph{quenched complexity}, which is generally different from its annealed counterpart, and allows to obtain the number of critical points for typical instances up to exponential accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v107-maillard20a, title = {Landscape Complexity for the Empirical Risk of Generalized Linear Models}, author = {Maillard, Antoine and Ben Arous, G\'erard and Biroli, Giulio}, booktitle = {Proceedings of The First Mathematical and Scientific Machine Learning Conference}, pages = {287--327}, year = {2020}, editor = {Lu, Jianfeng and Ward, Rachel}, volume = {107}, series = {Proceedings of Machine Learning Research}, month = {20--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v107/maillard20a/maillard20a.pdf}, url = {https://proceedings.mlr.press/v107/maillard20a.html}, abstract = { We present a method to obtain the average and the typical value of the number of critical points of the empirical risk landscape for generalized linear estimation problems and variants. This represents a substantial extension of previous applications of the Kac-Rice method since it allows to analyze the critical points of high dimensional non-Gaussian random functions. We obtain a rigorous explicit variational formula for the \emph{annealed complexity}, which is the logarithm of the average number of critical points at fixed value of the empirical risk. This result is simplified, and extended, using the non-rigorous Kac-Rice replicated method from theoretical physics. In this way we find an explicit variational formula for the \emph{quenched complexity}, which is generally different from its annealed counterpart, and allows to obtain the number of critical points for typical instances up to exponential accuracy. } }
Endnote
%0 Conference Paper %T Landscape Complexity for the Empirical Risk of Generalized Linear Models %A Antoine Maillard %A Gérard Ben Arous %A Giulio Biroli %B Proceedings of The First Mathematical and Scientific Machine Learning Conference %C Proceedings of Machine Learning Research %D 2020 %E Jianfeng Lu %E Rachel Ward %F pmlr-v107-maillard20a %I PMLR %P 287--327 %U https://proceedings.mlr.press/v107/maillard20a.html %V 107 %X We present a method to obtain the average and the typical value of the number of critical points of the empirical risk landscape for generalized linear estimation problems and variants. This represents a substantial extension of previous applications of the Kac-Rice method since it allows to analyze the critical points of high dimensional non-Gaussian random functions. We obtain a rigorous explicit variational formula for the \emph{annealed complexity}, which is the logarithm of the average number of critical points at fixed value of the empirical risk. This result is simplified, and extended, using the non-rigorous Kac-Rice replicated method from theoretical physics. In this way we find an explicit variational formula for the \emph{quenched complexity}, which is generally different from its annealed counterpart, and allows to obtain the number of critical points for typical instances up to exponential accuracy.
APA
Maillard, A., Ben Arous, G. & Biroli, G.. (2020). Landscape Complexity for the Empirical Risk of Generalized Linear Models. Proceedings of The First Mathematical and Scientific Machine Learning Conference, in Proceedings of Machine Learning Research 107:287-327 Available from https://proceedings.mlr.press/v107/maillard20a.html.

Related Material