The committee machine: computational to statistical gaps in learning a two-layers neural network

By Benjamin Aubin, A. Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris, Lenka Zdeborov'a. 2018

123 citations recorded by the source corpus.

Heuristic tools from statistical physics have been used in the past to locate the phase transitions and compute the optimal learning and generalization errors in the teacher-student scenario in multi-layer neural networks. In this paper, we provide a rigorous justification of these approaches for a two-layers neural network model called the committee machine, under a technical assumption. We also introduce a version of the approximate message passing (AMP) algorithm for the committee machine that allows optimal learning in polynomial time for a large set of parameters. We find that there are regimes in which a low generalization error is information-theoretically achievable while the AMP algorithm fails to deliver it; strongly suggesting that no efficient algorithm exists for those cases, unveiling a large computational gap.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics, Materials Chemistry

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

In Materials Chemistry

Citations in the corpus

Continual Learning in the Teacher-Student Setup: Impact of Task Similarity (2021, background): “…of activity in the machine learning community (Zimmer et al., 2014; Zhong et al., 2017; Tian, 2017; Du et al., 2018; Soltanolkotabi et al., 2018; Aubin et al., 2018; Saxe et al., 2018; Baity-Jesi et al., 2018; Goldt et al., 2019; Ghorbani et al., 2019; Yoshida & Okada, 2019; Ndirango & Lee,…”
Dynamics of stochastic gradient descent for two-layer neural networks in the teacher–student setup (2019, background): “[27] Benjamin Aubin, Antoine Maillard, Jean Barbier, Florent Krzakala, Nicolas Macris, and Lenka Zdeborová.”
Modelling the influence of data structure on learning in neural networks (2019, background): “…played a major role in theoretical studies of the generalisation ability of neural networks from an average-case perspective, particularly within the framework of statistical mechanics [3, 12, 4, 5, 13, 14, 15, 16, 17], and also in recent statistical learning theory works, e.g. [18, 19, 20, 21].”
Machine learning and the physical sciences (2019, background): “Recently the replica analysis of the op- timal generalization properties has been established rigorously (Aubin et al., 2018).”
The adaptive interpolation method: a simple scheme to prove replica formulas in Bayesian inference (2018, methodology): “1Since the rst version of this manuscript, the method has been successfully applied to many other problems including nonsymmetric matrix and tensor factorization [36], generalized linear models and learning [37], models of deep neural networks [38, 39], random linear estimation with structured matri”
Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm (2019, methodology): “The Teacher-Student paradigm has been broadly used to study supervised learning (Saad and Solla, 1995; Monasson and Zecchina, 1995; Opper and Saad, 2001; Engel and Van den Broeck, 2001; Zdeborová and Krzakala, 2016; Barbier et al., 2019; Gabrié et al., 2018; Aubin et al., 2018; Franz et al., 2018).”