mlsanityData to 7 Oct 2026

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

arXiv 1806.05451 ↗First posted 14 Jun 2018cs.LG cond-mat.dis-nn cond-mat.stat-mechcited by 58

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 58 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Jun 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 7; 2023: 8; 2024: 9; 2025: 12; 2026: 13.

58 papers.

Sort:

By area:

  1. 2021Continual Learning in the Teacher-Student Setup: Impact of Task Similaritycited by 86
  2. 2022Overview frequency principle/spectral bias in deep learningcited by 68
  3. 2021Learning Gaussian Mixtures with Generalised Linear Models: Precise Asymptotics in High-dimensionscited by 52
  4. 2022Phase diagram of Stochastic Gradient Descent in high-dimensional two-layer neural networkscited by 50
  5. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 50
  6. 2023Bayes-optimal Learning of Deep Random Networks of Extensive-widthcited by 41
  7. 2021Graph-based Approximate Message Passing Iterationscited by 35
  8. 2024A phase transition between positional and semantic learning in a solvable model of dot-product attentioncited by 30
  9. 2024Bayes-optimal learning of an extensive-width neural network from quadratically many samplescited by 23
  10. 2026There Will Be a Scientific Theory of Deep Learningcited by 21
  11. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  12. 2023High-dimensional Asymptotics of Denoising Autoencoderscited by 19
38 more
  1. 2022Theoretical characterization of uncertainty in high-dimensional linear classificationcited by 18
  2. 2022Learning curves for the multi-class teacher-student perceptroncited by 17
  3. 2024Fundamental computational limits of weak learnability in high-dimensional multi-index modelscited by 17
  4. 2021Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry IIcited by 16
  5. 2022On double-descent in uncertainty quantification in overparametrized modelscited by 15
  6. 2025Survey on Algorithms for multi-index modelscited by 15
  7. 2021On the interplay between data structure and loss function in classification problemscited by 12
  8. 2023Fundamental limits of overparametrized shallow neural networks for supervised learningcited by 12
  9. 2024High-dimensional learning of narrow neural networkscited by 12
  10. 2025The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networkscited by 11
  11. 2025Alternating Gradient Flows: A Theory of Feature Learning in Two-layer Neural Networkscited by 11
  12. 2022Annihilation of Spurious Minima in Two-Layer ReLU Networkscited by 9
  13. 2025Statistical mechanics of extensive-width Bayesian neural networks near interpolationcited by 9
  14. 2022Kernel Methods and Multi-layer Perceptrons Learn Linear Models in High Dimensionscited by 8
  15. 2026A solvable high-dimensional model where nonlinear autoencoders learn structure invisible to PCA while test loss misaligns with generalizationcited by 7
  16. 2025Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recoverycited by 6
  17. 2025Optimal Spectral Transitions in High-Dimensional Multi-Index Modelscited by 6
  18. 2025Information-theoretic reduction of deep neural networks to linear models in the overparametrized proportional regimecited by 6
  19. 2026Optimal scaling laws in learning hierarchical multi-index modelscited by 6
  20. 2023High-dimensional Asymptotics of VAEs: Threshold of Posterior Collapse and Dataset-Size Dependence of Rate-Distortion Curvecited by 5
  21. 2023How a student becomes a teacher: learning and forgetting through Spectral methodscited by 5
  22. 2023Enhancing Neural Training via a Correlated Dynamics Modelcited by 5
  23. 2021Semi-Supervised Federated Peer Learning for Skin Lesion Classificationcited by 4
  24. 2024Analysis of Bootstrap and Subsampling in High-dimensional Regularized Regressioncited by 4
  25. 2023Mixed Regression via Approximate Message Passingcited by 3
  26. 2024Solution space and storage capacity of fully connected two-layer neural networks with generic activation functionscited by 3
  27. 2025Bayes optimal learning of attention-indexed modelscited by 3
  28. 2023Hidden Minima in Two-Layer ReLU Networkscited by 2
  29. 2024Fermi-Bose Machine achieves both generalization and adversarial robustnesscited by 2
  30. 2025Analytic theory of dropout regularizationcited by 2
  31. 2025Generalization performance of narrow one-hidden layer networks in the teacher-student settingcited by 2
  32. 2026Deep Learning of Compositional Targets with Hierarchical Spectral Methodscited by 2
  33. 2021Understanding Robustness in Teacher-Student Setting: A New Perspectivecited by 1
  34. 2024Statistical Mechanics of Min-Max Problemscited by 1
  35. 2026Specialization of softmax attention heads: insights from the high-dimensional single-location modelcited by 1
  36. 2026A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Modelscited by 1
  37. 2021Towards Designing Optimal Sensing Matrices for Generalized Linear Inverse Problemscited by 0
  38. 2025Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolationcited by 0

50 most cited of 58 All 58 (JSON)