The committee machine: Computational to statistical gaps in learning a two-layers neural network
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2018
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909122900787200 |
|---|---|
| author | Aubin, Benjamin Maillard, Antoine Barbier, Jean Krzakala, Florent Macris, Nicolas Zdeborová, Lenka |
| author_facet | Aubin, Benjamin Maillard, Antoine Barbier, Jean Krzakala, Florent Macris, Nicolas Zdeborová, Lenka |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1806_05451 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | The committee machine: Computational to statistical gaps in learning a two-layers neural network Aubin, Benjamin Maillard, Antoine Barbier, Jean Krzakala, Florent Macris, Nicolas Zdeborová, Lenka Machine Learning Disordered Systems and Neural Networks Statistical Mechanics Computational Physics 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. |
| title | The committee machine: Computational to statistical gaps in learning a two-layers neural network |
| topic | Machine Learning Disordered Systems and Neural Networks Statistical Mechanics Computational Physics |
| url | https://arxiv.org/abs/1806.05451 |