Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification

arXiv:2510.02779v3 Announce Type: replace Abstract: Recent advances have significantly improved our understanding of the generalization performance of gradient descent (GD) methods in deep neural networks. A natural and fundamental question is whether GD can achieve generalization rates comparable to the minimax optimal rates established in the kernel setting. Existing results either yield suboptimal rates of O(1/sqrt{n}), or focus on networks with smooth activation functions, incurring exponential dependence on network depth L. In this work, we establish optimal generalization rates for GD with deep ReLU networks by carefully trading off optimization and generalization errors, achieving only polynomial dependence on depth. Specifically, under the assumption that the data are NTK separable from the margin gamma, we prove an excess risk rate of widetilde{O}(L^6 / (n gamma^2)), which aligns with the optimal SVM-type rate widetilde{O}(1 / (n gamma^2)) up to depth-dependent factors. A key technical contribution is our novel control of activation patterns near a reference model, enabling a sharper Rademacher complexity bound for deep ReLU networks trained with gradient descent.

Related

• Gradient flow dynamics of shallow ReLU networks for square loss and orthogonal inputs
• An overview of condensation phenomenon in deep learning
• Product-Stability: Provable Convergence for Gradient Descent on the Edge of Stability
• PAC-Bayesian Bounds on Constrained f-Entropic Risk Measures
• Fisher-Geometric Diffusion in Stochastic Gradient Descent: Optimal Rates, Oracle Complexity, and Information-Theoretic Limits

Source: arXiv cs.LG | 2026-04-14