Landscape Complexity for the Empirical Risk of Generalized Linear Models: Discrimination between Structured Data
This provides theoretical insights into optimization challenges in machine learning with structured data, but it is incremental as it extends existing methods to more complex scenarios.
The paper tackles the problem of characterizing the loss landscape complexity for generalized linear models with structured data, using random matrix theory to compute the average number of critical points in high-dimensional settings, with results exact in the large-dimension limit.
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.