Landscape Complexity for the Empirical Risk of Generalized Linear Models

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

arXiv comment18 pages and 18 pages appendix. Update to match the published version (v2). Corrections of remaining small typos (v3). Simplification of a technical argument in Appendix A (v4) and clarification of a technical hypothesis (v5)

References in corpus (13)

• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• The statistics of critical points of Gaussian fields on large-dimensional spaces
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• The simplest model of jamming
• Critical Behaviour of the Number of Minima of a Random Landscape at the Glass Transition Point and the Tracy-Widom distribution
• Depth Creates No Bad Local Minima
• Algorithmic thresholds for tensor PCA
• Quenched complexity of the p-spin spherical spin-glass with external magnetic field
• How to iron out rough landscapes and get optimal performances: Averaged Gradient Descent and its application to tensor PCA
• Topology and Geometry of Half-Rectified Network Optimization
• Counting stationary points of the loss function in the simplest constrained least-square optimization

Cited by in corpus (4)

• A spin-glass model for the loss surfaces of generative adversarial networks
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model
• Large deviations for the largest eigenvalue of matrices with variance profiles
• Superposition of Random Plane Waves in High Spatial Dimensions: Random Matrix Approach to Landscape Complexity