Research map / Optimization / Implicit bias and generalization
Optimal Rates for Generalization of Gradient Descent for Deep ReLU Classification
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows gradient descent on deep ReLU networks for NTK-separable binary classification attains the optimal-type excess risk Õ(L^6/(nγ^2)) with only polynomial depth dependence, via a near-initialization activation-pattern analysis and covering-number Lipschitz bound.
Problem
Generalization of gradient descent for deep ReLU classifiers: existing bounds are O(1/sqrt(n)) or exponential in depth L, or only cover smooth activations or shallow nets. The question is whether GD can reach the optimal 1/(nγ^2) rate for deep ReLU networks with polynomial depth dependence.
Approach
Bound the optimization error by a reference model near initialization (F_S(W̄)/(ηT)), show all GD iterates stay in a ball around it, and control Rademacher complexity via sparse-matrix products and a covering-number argument that gives polynomial (Õ(L^2)) Lipschitzness near initialization rather than exponential in L.
Key results
- Main theorem: excess risk Õ(L^6 (log T)^2/(nγ^2)) under width m ≳ n^3 L^16 ... /γ^8, improving the width requirement of prior NTK-separable analysis (L^22/γ^8) by a factor L^6.
- Lipschitz constant of deep ReLU network near initialization is Õ(L^2), replacing prior e^{O(L)} bounds.
- On noisy 2-XOR data with two-layer ReLU nets (m=128, T=500, η=0.1), test error scales as approximately 0.15 d^2/n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed deep ReLU GD analysis instead of the prior deep ReLU bound | Deep ReLU networks on NTK-separable data · NTK-separable data | generalization error: \widetilde{O}\left(\frac{L^6}{\gamma^2n}\right) versus \widetilde{O}\big(\min\{\frac{4^LL^2\sqrt{m}}{\gamma\sqrt{n}},\fr | Helped |
| Use the proposed deep ReLU GD analysis rather than the prior smooth-activation approach | Deep networks on NTK-separable data · NTK-separable data | generalization error: \widetilde{O}\left(\frac{L^6}{\gamma^2n}\right) versus \widetilde{O}\left(\frac{e^{O(L)}}{\gamma^2n}\right) | Mixed |
| Use the proposed deep ReLU GD analysis instead of the prior shallow ReLU result | ReLU networks on NTK-separable data · NTK-separable data | generalization error: \widetilde{O}\left(\frac{L^6}{\gamma^2n}\right) versus \widetilde{O}\left(\frac{1}{\gamma^2n}\right) | Mixed |
| Refine control of ReLU activation patterns and iterate distance | Deep ReLU GD · NTK-separable data | required width: L^6 | Helped |
| Apply GD to noisy 2-XOR data with a two-layer ReLU network | Noisy 2-XOR · Noisy 2-XOR | test error: approximately 0.15d^2/n | Mixed |
Limitations
- Width requirement is still large (n^3 and 1/γ^8 with L^16), far from polylogarithmic width.
- Analysis is for full-batch GD on fully connected networks only; SGD and other architectures are not covered.
- Experiments are small-scale two-layer networks on synthetic 2-XOR data, which do not test the deep-network bound.
Experimental setup
Datasets: noisy 2-XOR synthetic distribution
Benchmarks: noisy 2-XOR synthetic data
Metrics: test error
Baselines: Cao and Gu (2019) deep ReLU bound Richards and Kuzborskij (2021) shallow ReLU bound Lei and Ying-style smooth-activation stability bound (e^{O(L)}/(nγ^2)) Ji and Telgarsky NTK-separable bounds
Builds on: neural tangent kernel neural tangent random features algorithmic stability generalization
Closest papers by meaning
- Generalization Error Bounds of Gradient Descent for Learning Over-Parameterized Deep ReLU Networks (AAAI 2020 · similarity 0.91)
- Understanding Generalization and Optimization Performance of Deep CNNs (ICML 2018 · similarity 0.90)
- On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths (ICML 2021 · similarity 0.90)
- Generalization of Scaled Deep ResNets in the Mean-Field Regime (ICLR 2024 · similarity 0.88)
- Simplicity Bias and Optimization Threshold in Two-Layer ReLU Networks (ICML 2025 · similarity 0.88)
- Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.