Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGD
This provides incremental insights into the theoretical understanding of SGD dynamics in neural networks, relevant for researchers in machine learning theory.
The paper tackles the sample complexity for two-layer neural networks learning generalized linear target functions with SGD in high-dimensional settings with many flat directions, finding that overparameterization improves convergence only by a constant factor and that stochasticity has minimal impact on escape times.
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.