 |
Center for Nonlinear Studies |
Generalized linear models (GLMs) arise in high-dimensional machine learning, statistics, communications and signal processing. In this paper we analyze GLMs when the data matrix is random, as relevant in problems such as compressed sensing, error-correcting codes or benchmarks models in neural networks. We evaluate the mutual information (or “free entropy”) from which we deduce the Bayes-optimal inference and generalization errors. Our analysis applies to the high-dimensional limit where both the number of samples and di-mensions are large and their ratio is fixed. Non-rigorous predictions for the optimal inference and generalization errors existed for special cases of GLMs, e.g. for the perceptron in the field of statistical physics based on the so-called replica method. Our present paper rigorously establishes those decades old conjectures and brings for-ward their algorithmic interpretation in terms of performance of the generalized approximate message-passing algorithm. Furthermore, we tightly characterize, for many learning problems, regions of pa- rameters for which this algorithm achieves the optimal performance, and locate the associated sharp phase transitions separating learn- able and non-learnable regions. We believe that this random version of GLMs can serve as a challenging benchmark for multi-purpose algorithms such as those arising in deep learning. (This is a collaboration with J. Barbier, L. Miolane, F. Krzakala and L. Zdeborova.)
Host: Marc Vuffray