# Landscape Complexity for the Empirical Risk of Generalized Linear Models

arXiv: https://arxiv.org/abs/1912.02143 · HTML: https://mlsanity.com/paper/1912.02143/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Dec 2019.

## Built on by (most cited first, 15 of 15)

- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem](https://mlsanity.com/paper/2103.04902/) (2021)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Learning a Single Neuron for Non-monotonic Activation Functions](https://mlsanity.com/paper/2202.08064/) (2022)
- [Exploring Neural Network Landscapes: Star-Shaped and Geodesic Connectivity](https://mlsanity.com/paper/2404.06391/) (2024)
- [Appearance of Random Matrix Theory in Deep Learning](https://mlsanity.com/paper/2102.06740/) (2021)
- [The Role of the Time-Dependent Hessian in High-Dimensional Optimization](https://mlsanity.com/paper/2403.02418/) (2024)
- [Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Models](https://mlsanity.com/paper/2502.16849/) (2025)
- [A spin-glass model for the loss surfaces of generative adversarial networks](https://mlsanity.com/paper/2101.02524/) (2021)
- [Universal characteristics of deep neural network loss surfaces from random matrix theory](https://mlsanity.com/paper/2205.08601/) (2022)
- [On the number of modes of Gaussian kernel density estimators](https://mlsanity.com/paper/2412.09080/) (2024)
- [Asymptotic Dynamics of Alternating Minimization for Bilinear Regression](https://mlsanity.com/paper/2402.04751/) (2024)
- [Sharp description of local minima in the loss landscape of high-dimensional two-layer ReLU neural networks](https://mlsanity.com/paper/2604.09412/) (2026)
- [Topological Exploration of High-Dimensional Empirical Risk Landscapes: general approach, and applications to phase retrieval](https://mlsanity.com/paper/2602.17779/) (2026)
- [Topological complexity of spiked random polynomials and finite-rank spherical integrals](https://mlsanity.com/paper/2312.12323/) (2023)

## Abstract (arXiv)

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. Under a technical hypothesis, 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.