Institut de Physique Théorique
Direction de la Recherche Fondamentale  -  Saclay
UMR 3681 - INP
encart droite
Encart de droite, peut être utilisé à des fins diverses. Actuellement caché via les CSS.
Mercredi 18 octobre 2017

Publication : t17/156


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

barbier J. ()
Krzakala F. ()
Macris N. ()
Miolane L. ()
Zdeborova L. (CEA, IPhT (Institut de Physique Théorique), F-91191 Gif-sur-Yvette, France)
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→α where α stays finite in the limit m,n→∞ . 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
Année de publication : 2017
Preprint : arXiv:1708.03395
Langue : Anglais

Fichier(s) à télécharger :
  • publi.pdf

  • Retour en haut