Landscape Complexity for the Empirical Risk of Generalized Linear Models: Discrimination between Structured Data

Abstract

We use the Kac-Rice formula and results from random matrix theory to obtain the average number of critical points of a family of high-dimensional empirical loss functions, where the data are correlated $d$-dimensional Gaussian vectors, whose number has a fixed ratio with their dimension. The correlations are introduced to model the existence of structure in the data, as is common in current Machine-Learning systems. Under a technical hypothesis, our results are exact in the large-$d$ limit, and characterize the annealed landscape complexity, namely the logarithm of the expected number of critical points at a given value of the loss. We first address in detail the landscape of the loss function of a single perceptron and then generalize it to the case where two competing data sets with different covariance matrices are present, with the perceptron seeking to discriminate between them. The latter model can be applied to understand the interplay between adversity and non-trivial data structure. For completeness, we also treat the case of a loss function used in training Generalized Linear Models in the presence of correlated input data.

References in corpus (13)

• Statistical physics of inference: Thresholds and algorithms
• A Deterministic Equivalent for the Analysis of Correlated MIMO Multiple Access Channels
• The simplest model of jamming
• Freezing Transitions and Extreme Values: Random Matrix Theory, $\zeta (1/2+it)$, and Disordered Landscapes
• Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions
• Free energy and complexity of spherical bipartite models
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels
• Replica Symmetry Breaking in Bipartite Spin Glasses and Neural Networks
• Disordered Systems Insights on Computational Hardness
• On weak ergodicity breaking in mean-field spin glasses
• How to count in hierarchical landscapes: a 'full' solution to mean-field complexity
• A spin-glass model for the loss surfaces of generative adversarial networks
• When is the average number of saddle points typical?