Research map / Optimization / Implicit bias and generalization
Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods
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.
Gives algorithm-dependent (stability-based) excess-risk and generalization bounds for gradient descent on smooth-activation deep nets, showing e^{O(L)}/(γ² n) test error under NTK separability and a constant-width XOR result with a large step size.
Problem
Generalization and convergence guarantees for gradient-trained deep networks with smooth activations; existing Rademacher bounds depend on width and NTK-regime bounds are suboptimal, and kernel-regime analyses need large width or small steps.
Approach
Uses an algorithmic stability analysis that exploits the Hessian structure of the objective along GD iterates to obtain bounds depending on the training loss and initialization distance, not on width; also uses a large step size (eta = m) with quadratic activation to learn XOR in log(d) SGD steps with constant width.
Key results
- Under NTK separability with width poly(log n), the test error bound is e^{O(L)}/(γ² n) + 1/(γ² T), improving on the earlier 4^L sqrt(m/n) Rademacher-based bound.
- For XOR with a one-hidden-layer quadratic network of constant width and step size eta=m, SGD reaches near-perfect test accuracy after T=log(d) iterations with n=Õ(d) samples; experiments use m=20.
- Experiments on FashionMNIST and MNIST show the theoretical algorithmic generalization bound tracks the empirical generalization gap and test loss (non-vacuous, though only approximate).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the stability-based bound instead of the prior ReLU bound | Deep networks under NTK separability · NTK-separable noiseless classification | test loss bound: $\widetilde O(\frac{e^{O(L)}}{\gamma^2} \sqrt{\frac{m}{n}} + \frac{1}{\gamma^2 T})$ -> $\widetilde O(\frac{e^{O(L)}}{\ga | Helped |
| Use quadratic activation and a large step-size $\eta=m$ instead of the NTK-regime method | Neural networks learning XOR · d-dimensional XOR | SGD iterations: $d^2$ -> $\log(d)$ | Helped |
| Use a constant-width quadratic-activation network instead of the prior NTK method | Neural networks learning XOR · d-dimensional XOR | network width: $\Omega(\mathrm{poly}(d))$ -> $\Omega(1)$ | Helped |
| Use a constant-width quadratic-activation network instead of the prior ReLU feature-learning method | Neural networks learning XOR · d-dimensional XOR | network width: $\Omega(\mathrm{poly}(\log(d)))$ -> $\Omega(1)$ | Helped |
| Use the proposed quadratic-activation SGD method instead of the prior ReLU feature-learning method | Neural networks learning XOR · d-dimensional XOR | SGD iterations: $\mathrm{poly}(\log(d))$ -> $\log(d)$ | Helped |
Surprising findings
- The distance ||w_t - w_0|| is of constant order and can even decrease with width, contrary to the growth of ||w_t||, which makes initialization-dependent bounds width-independent.
Limitations
- Width condition m = Omega(poly(log n / γ)) scales with the separability margin and depth exponent (6L+4), and the noisy-data result needs polynomial width in n.
- Bounds rely on Hessian-norm assumptions with constants beta_L = e^{O(L)} and high-probability statements; empirical bound validation is approximate, using one realization and a non-verified width condition.
Experimental setup
Datasets: FashionMNIST MNIST synthetic d-dimensional XOR distribution
Benchmarks: FashionMNIST MNIST d-dimensional XOR
Metrics: training loss test loss generalization gap test error distance from initialization
Baselines: Rademacher complexity bounds for deep nets NTK-regime GD guarantees (d^2 steps) ReLU network XOR learning with large SGD steps
Builds on: neural tangent kernel regime algorithmic stability analysis generalized local quasi-convexity
Closest papers by meaning
- On the Complexity of Learning Neural Networks (NeurIPS 2017 · similarity 0.91)
- Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks (NeurIPS 2019 · similarity 0.90)
- Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernel (NeurIPS 2021 · similarity 0.89)
- Stability and Generalization of Learning Algorithms that Converge to Global Optima (ICML 2018 · similarity 0.89)
- Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel (NeurIPS 2025 · similarity 0.88)
- Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · 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.