@inproceedings{
arnaboldi2023escaping,
title={Escaping mediocrity: how two-layer networks learn hard generalized linear models},
author={Luca Arnaboldi and Florent Krzakala and Bruno Loureiro and Ludovic Stephan},
booktitle={OPT 2023: Optimization for Machine Learning},
year={2023},
url={https://openreview.net/forum?id=kyQq0vIUBw}
}
This study explores the sample complexity for two-layer neural networks to learn a generalized linear target function under Stochastic Gradient Descent (SGD), focusing on the challenging regime where many flat directions are present at initialization. It is well-established that in this scenario $n=O(d\log d)$  samples are typically needed. However, we provide precise results concerning the pre-factors in high-dimensional contexts and for varying widths. Notably, our findings suggest that overparameterization can only enhance convergence by a constant factor within this problem class. These insights are grounded in the reduction of SGD dynamics to a stochastic process in lower dimensions, where escaping mediocrity equates to calculating an exit time. Yet, we demonstrate that a deterministic approximation of this process adequately represents the escape time, implying that the role of stochasticity may be minimal in this scenario.
Escaping mediocrity: how two-layer networks learn hard generalized linear models
Luca Arnaboldi Florent Krzakala Bruno Loureiro Ludovic Stephan