Optimization and Generalization of Gradient Descent for Shallow ReLU Networks with Minimal Width

2026/01/01

paper

Abstract

Understanding the generalization and optimization of neural networks is a longstanding problem in modern learning theory. The prior analysis often leads to risk bounds of order 1/√(n) for ReLU networks, where n is the sample size. In this paper, we present a general optimization and generalization analysis for gradient descent applied to shallow ReLU networks. We develop convergence rates of the order 1/T for gradient descent with T iterations, and show that the gradient descent iterates fall inside local balls around either an initialization point or a reference point. Then we develop improved Rademacher complexity estimates by using the activation pattern of the ReLU function in these local balls. We apply our general result to NTK-separable data with a margin γ, and develop an almost optimal risk bound of the order 1/(nγ²) for the ReLU network with a polylogarithmic width.

Related

• Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths
• Optimization dependent generalization bound for ReLU networks based on sensitivity in the tangent bundle
• How Much Over-parameterization Is Sufficient to Learn Deep ReLU\n Networks?
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks