Escaping mediocrity: how two-layer networks learn hard generalized linear models with SGD

2023/05/29 by Luca Arnaboldi, Arnaboldi, Luca, Florent Krząkała +5 · 3 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Neural Networks and Applications #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2305.18502

openalex publication_date 2023/05/29 · openalex created_date 2023/06/01 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Fast Escape, Slow Convergence: Learning Dynamics of Phase Retrieval under Power-Law Data
• Spectral Gradient Descent Mitigates Anisotropy-Driven Misalignment: A Case Study in Phase Retrieval
• Scaling Laws and Spectra of Shallow Neural Networks in the Feature Learning Regime

Related

• SGD on Neural Networks Learns Functions of Increasing Complexity
• Neural Networks Efficiently Learn Low-Dimensional Representations with SGD
• From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks
• Emergence and scaling laws in SGD learning of shallow neural networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers