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

Abstract

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 contribution, we provide a rigorous justification of these approaches for a two-layers neural network model called the committee machine. We also introduce a version of the approximate message passing (AMP) algorithm for the committee machine that allows to perform 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, and unveiling a large computational gap.

18 pages + supplementary material, 3 figures. (v2: update to match the published version ; v3: clarification of the caption of Fig. 3)

References in corpus (4)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• Efficient supervised learning in networks with binary synapses
• Inference from correlated patterns: a unified theory for perceptron learning and linear vector channels

Cited by in corpus (9)

• Hidden Unit Specialization in Layered Neural Networks: ReLU vs. Sigmoidal Activation
• Activation function dependence of the storage capacity of treelike neural networks
• Learning curves for the multi-class teacher-student perceptron
• Teacher-student learning for a binary perceptron with quantum fluctuations
• Large scale analysis of generalization error in learning using margin based classification methods
• Theoretical characterization of uncertainty in high-dimensional linear classification
• Analyticity of the energy in an Ising spin glass with correlated disorder
• High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curve
• Fermi-Bose Machine achieves both generalization and adversarial robustness