TheCommitteeMachine swMATH ID: 38983 Software Authors: Aubin, Benjamin; Maillard, Antoine; Barbier, Jean; Krzakala, Florent; Macris, Nicolas; Zdeborová, Lenka Description: The committee machine: computational to statistical gaps in learning a two-layers neural network. 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. Homepage: https://arxiv.org/abs/1806.05451 Source Code: https://github.com/benjaminaubin/TheCommitteeMachine Related Software: lsd; dnner; PRMLT; AlexNet; ImageNet; gss; SigClust; AdaBoost.MH; GitHub; Entropy-SGD Cited in: 7 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year The committee machine: computational to statistical gaps in learning a two-layers neural network. Zbl 1459.82248Aubin, Benjamin; Maillard, Antoine; Barbier, Jean; Krzakala, Florent; Macris, Nicolas; Zdeborová, Lenka 2019 all top 5 Cited by 17 Authors 3 Barbier, Jean 3 Macris, Nicolas 1 Aubin, Benjamin 1 Biehl, Michael 1 Chan, Chun Lam 1 Feng, Oliver Y. 1 Huang, Hanwen 1 Krzakąła, Florent 1 Maillard, Antoine 1 Nishimori, Hidetoshi 1 Oostwal, Elisa 1 Rush, Cynthia 1 Samworth, Richard J. 1 Straat, Michiel 1 Venkataramanan, Ramji 1 Yang, Qinglong 1 Zdeborová, Lenka all top 5 Cited in 6 Serials 2 Journal of Statistical Mechanics: Theory and Experiment 1 Journal of Statistical Physics 1 Physica A 1 Probability Theory and Related Fields 1 Journal of Physics A: Mathematical and Theoretical 1 Foundations and Trends in Machine Learning all top 5 Cited in 6 Fields 5 Statistical mechanics, structure of matter (82-XX) 3 Statistics (62-XX) 2 Computer science (68-XX) 1 Combinatorics (05-XX) 1 Probability theory and stochastic processes (60-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year