Research map / Optimization / Implicit bias and generalization
Do Neural Networks Need Gradient Descent to Generalize? A Theoretical Study
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.
Theoretically studies whether Guess & Check (random sampling until training fit) matches gradient descent generalization in matrix factorization, showing G&C generalization degrades with width (no better than chance for anti-symmetric activations) but improves with depth.
Problem
Whether overparameterized neural networks need gradient descent to generalize, i.e., whether the volume hypothesis (generalization via Guess & Check sampling from a prior conditioned on training fit) holds for wide and deep networks, which literature gives conflicting evidence on.
Approach
Uses matrix factorization as a canonical testbed and shows via infinite-width Gaussian process convergence that G&C posterior generalization equals prior generalization as width grows (provably inferior to gradient descent), while with normalized prior and depth growth G&C generalization becomes near-perfect, with probability 1-O(1/d).
Key results
- For anti-symmetric admissible activations, the posterior probability of low generalization loss converges to its prior probability as width grows, with O(1/sqrt(k)) rate for Gaussian priors.
- With normalized Gaussian prior, linear activation, depth d, rank-one ground truth, 1 - P(L_gen < c*eps | L_trn < eps) = O(1/d).
- Empirically, G&C generalization deteriorates with width and improves with depth, whereas gradient descent generalizes well throughout (matrix factorization, depth 2, m=m'=5, n=15, eight seeds).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase network width | Guess & Check on matrix factorization · Matrix factorization, varying width | generalization loss | Hurt |
| increase network width | Gradient descent on matrix factorization · Matrix factorization, varying width | generalization loss | No clear effect |
| increase network depth | Guess & Check on matrix factorization · Matrix factorization, varying depth | generalization loss | Helped |
| increase network depth | Gradient descent on matrix factorization · Matrix factorization, varying depth | generalization loss | No clear effect |
| use Leaky ReLU instead of linear or tanh activation | Gradient descent on matrix factorization · Matrix factorization, varying width | generalization loss | Hurt |
| normalize the Guess & Check prior | Guess & Check on matrix factorization · Matrix factorization, varying depth | generalization loss | Mixed |
Surprising findings
- Leaky ReLU gradient descent generalizes worse than with linear and tanh activations, outside the theory's scope.
- Deeper networks led to vanishing gradients for gradient descent, limiting experiments to depths up to ten.
Limitations
- Guarantees for G&C include unspecified constants and are non-vacuous only for large width or depth.
- Theory covers anti-symmetric admissible activations and for depth results only linear activation with rank-one ground truth and RIP.
- Gradient descent guarantee relies on a single result (Theorem 3.3 of prior work) limited to linear activation, depth two and RIP measurements.
Experimental setup
Metrics: generalization loss
Baselines: gradient descent G&C with Kaiming Gaussian prior single draw from prior
Builds on: volume hypothesis Guess & Check Lyapunov exponents of random matrix products infinite-width Gaussian process limits of neural networks
Closest papers by meaning
- Revisiting the Volume Hypothesis (ICML 2026 · similarity 0.91)
- How much does Initialization Affect Generalization? (ICML 2023 · similarity 0.90)
- Uniform convergence may be unable to explain generalization in deep learning (NeurIPS 2019 · similarity 0.90)
- Bias of Stochastic Gradient Descent or the Architecture: Disentangling the Effects of Overparameterization of Neural Networks (ICML 2024 · similarity 0.89)
- Simplicity Bias in Overparameterized Machine Learning (AAAI 2024 · similarity 0.88)
- Exact, Tractable Gauss-Newton Optimization in Deep Reversible Architectures Reveal Poor Generalization (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.