Phase Transitions, Optimal Errors and Optimality of Message-Passing in Generalized Linear Models

Jean Barbier 1 Florent Krzakala 1 Nicolas Macris 2 Léo Miolane 3 Lenka Zdeborová 4
3 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : We consider generalized linear models where an unknown $n$-dimensional signal vector is observed through the successive application of a random matrix and a non-linear (possibly probabilistic) componentwise function. We consider the models in the high-dimensional limit, where the observation consists of $m$ points, and $m/n {\to} {\alpha}$ where ${\alpha}$ stays finite in the limit $m, n {\to} {\infty}$. This situation is ubiquitous in applications ranging from supervised machine learning to signal processing. A substantial amount of work suggests that both the inference and learning tasks in these problems have sharp intrinsic limitations when the available data become too scarce or too noisy. Here, we provide rigorous asymptotic predictions for these thresholds through the proof of a simple expression for the mutual information between the observations and the signal. Thanks to this expression we also obtain as a consequence the optimal value of the generalization error in many statistical learning models of interest, such as the teacher-student binary perceptron, and introduce several new models with remarquable properties. We compute these thresholds (or "phase transitions") using ideas from statistical physics that are turned into rigorous methods thanks to a new powerful smart-path interpolation technique called the stochastic interpolation method, which has recently been introduced by two of the authors. Moreover we show that a polynomial-time algorithm refered to as generalized approximate message-passing reaches the optimal generalization performance for a large set of parameters in these problems. Our results clarify the difficulties and challenges one has to face when solving complex high-dimensional statistical problems.
Liste complète des métadonnées
Contributeur : Emmanuelle De Laborderie <>
Soumis le : mardi 10 octobre 2017 - 16:02:57
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03


  • HAL Id : cea-01614258, version 1
  • ARXIV : 1708.03395


Jean Barbier, Florent Krzakala, Nicolas Macris, Léo Miolane, Lenka Zdeborová. Phase Transitions, Optimal Errors and Optimality of Message-Passing in Generalized Linear Models. 35 pages, 3 figures. 2017. 〈cea-01614258〉



Consultations de la notice