2023/06/28 by Arvind V. Mahankali, Mahankali, Arvind, Jeff Z. HaoChen +7 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and ELM #Model Reduction and Neural Networks #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2306.16361
openalex publication_date 2023/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Despite recent theoretical progress on the non-convex optimization of two-layer neural networks, it is still an open question whether gradient descent on neural networks without unnatural modifications can achieve better sample complexity than kernel methods. This paper provides a clean mean-field analysis of projected gradient flow on polynomial-width two-layer neural networks. Different from prior works, our analysis does not require unnatural modifications of the optimization algorithm. We prove that with sample size n = O(d3.1) where d is the dimension of the inputs, the network trained with projected gradient flow converges in poly(d) time to a non-trivial error that is not achievable by kernel methods using n ≪ d4 samples, hence demonstrating a clear separation between unmodified gradient descent and NTK. As a corollary, we show that projected gradient descent with a positive learning rate and a polynomial number of iterations converges to low error with the same sample complexity.