Statistical Mechanics of Unsupervised Representation Learning
Learning of representations of data stands behind the recent progress in machine learning and paves our way towards artificial intelligence. Certain models for representation learning can be seen as a particular kind of a meanfield spin glasses. Methods stemming from physics of disordered systems turn out as very instrumental in understanding the behaviour of those model both from informationtheoretic and computational point of view. This line of study brought up remarkable connections between physical phase transitions and appearance of computational hardness.

F. Antenucci (CEA), P. Urbani (CEA), F. Krzakala (ENS), S. Franz (LPTMS), L. Zdeborová (CEA)
Learning of representations of data stands behind the recent progress in machine learning and paves our way towards artificial intelligence. Certain models for representation learning can be seen as a particular kind of a meanfield spin glasses. Methods stemming from physics of disordered systems turn out as very instrumental in understanding the behaviour of those model both from informationtheoretic and computational point of view. This line of study brought up remarkable connections between physical phase transitions and appearance of computational hardness. A socaller hard phase was identified where learning is possible, but no efficient algorithm are known to obtain it. This hard phase is located via a study of message passing algorithms.
In the existing literature, the hard phase is located using the simplest (replica symmetric) version of the message passing algorithms that ignores the fact that from the physics point of view this hard phase is glassy. Our contribution is the development of the approximate survey propagation (ASP) algorithm that takes glassines into account, in particular by breaking of the replica symmetry. We show that the large size limit of ASP algorithm leads to the onestepreplica symmetry breaking fixedpoint equations well known from the context of spin glasses. Using this setting, we characterize the glassy property of the hard region, measuring the entropy of the metastable glassy states, called complexity. We show that this glassiness extends even outside of the hard phase thus strongly suggesting that sampling based algorithms such as Monte Carlo or Langevin sampling will not be able to match the performance of the simple message passing algorithms. This is contrary to what was widely believe in the field and is being confirmed using numerical simulations and analytical studies of the dynamics in simpler models.
Analyzing the ASP algorithm we reached another striking conclusion: ASP is unable to outperform the simpler message passing algorithm and so in particular ASP also does not work in the hard phase, this is despite taking correctly into account the glassiness while the simpler algorithm ignores it. This is a considerable evidence towards the fact that the hard phase is impenetrable for efficient algorithms for perhaps fundamental reasons, that are however out of reach of current computational complexity theory. Further investigation of this point is an exciting direction both for physics and theoretical computer science.
Mean Square Error of the ASP algorithm as a function of the Parisi parameter s on which the algorithm depends. We see that the minimal error is always reached for s=1 for which the ASP algorithm reduces to the simpler form that ignores glassy aspects of the hard phase.
F. Antenucci (CEA), P. Urbani (CEA), F. Krzakala (ENS), L. Zdeborová (CEA), Approximate Survey Propagation for Statistical Inference, arXiv:1807.01296 (2018).
F. Antenucci (CEA), S. Franz (LPTMS), P. Urbani (CEA), L. Zdeborová (CEA), On the glassy nature of the hard phase in inference problems, arXiv:1805.05857 (2018).
Résultats obtenus dans le cadre du projet SaMURai financé par le thème émergence du LabEx PALM et porté par Lenka Zdeborová (CEA) et Silvio Franz (LPTMS).
Conf IR & visible 
Dernières (r)évolutions dans le domaine des détecteurs, du visible à l'infrarouge
17 et 18 décembre 2018
Auditorium de l'Institut d'Optique 
ICoQC 
International Conference on Quantum Computing
Du 26 au 30 novembre 2018
ENS Paris 
GDR EMIE 
Réunion Plénière du GDR EMIE
Du 12 au 15 novembre 2018
Domaine de Chalès 
PXRNMS2018 
Workshop Physics of Xray and Neutron Multilayer Structures
Du 7 au 9 novembre 2018
Campus EDF (Palaiseau) 
WFS&Control 
International workshop on WaveFront Sensing and Control
Du 22 au 24 octobre 2018

Journée MSC 3 
Journée de la matière et des systèmes complexes 3eme édition
Le 19 octobre 2018
Ecole CentraleSupélec (Théâtre Joël Rousseau)

PNP16 
16th International Conference on the physics of NonIdeal Plasma
Du 24 au 28 septembre 2018
SaintMalo

Cosful2018 
Workshop sur les fullerènes cosmiques 2018
Du 19 au 21 septembre 2018
Amphi Blandin du LPS (Orsay)

ECOCLIM 2018 
Circuit et matériaux quantiques
Du 11 au 14 juin 2018
Université ParisSud (Orsay)

Colloque LIA 
Circuit et matériaux quantiques
Les 5 et 6 juin 2018
Domaine St Paul (St Remy Les Chevreuses)
