Landscape Complexity for the Empirical Risk of Generalized Linear Models

Antoine Maillard, Gérard Ben Arous, Giulio Biroli

Research output: Contribution to journalConference articlepeer-review


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 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 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.

Original languageEnglish (US)
Pages (from-to)287-327
Number of pages41
JournalProceedings of Machine Learning Research
StatePublished - 2020
Event1st Mathematical and Scientific Machine Learning Conference, MSML 2020 - Princeton, United States
Duration: Jul 20 2020Jul 24 2020


  • Empirical risk landscape
  • Generalized linear models
  • Kac-Rice
  • Landscape complexity

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Landscape Complexity for the Empirical Risk of Generalized Linear Models'. Together they form a unique fingerprint.

Cite this