Research map / Optimization / Implicit bias and generalization

The Power of Random Features and the Limits of Distribution-Free Gradient Descent

ICML 2025 · Optimization › Implicit bias and generalization · approach: Low-rank and single-index recovery · 0 citations (OpenAlex)

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 that distribution-free mini-batch SGD learnability of a parametric model implies that most target functions (under any prior) are approximable by polynomially many random features, and introduces average probabilistic dimension complexity (adc) with an infinite separation from standard dimension complexity.

Problem

Understanding why gradient descent on neural networks works in practice despite worst-case hardness, specifically what distribution-free learnability by mini-batch SGD implies about representational power; also whether probabilistic dimension complexity can be infinitely separated from standard dime

Approach

Chains a bSGD-to-statistical-query simulation, SQ dimension characterization via sign-matrix discrepancy and 2-party communication, and AdaBoost-style boosting to show that a prior-averaged target is approximable by a polynomial-size linear combination of random features; introduces the average-case variant adc that relaxes the universal quantifier over hypotheses.

Key results

• Main theorem: if bSGD(T,c,b,p) distribution-free learns a model, then for any prior mu over targets, with probability 1-delta over f~mu a random-feature linear combination of size poly(Tp/c^2) achieves small 0/1 loss.
• Shows adc(mu) is at most poly(SQ dimension), giving adc in O(1/epsilon) while standard dimension complexity is 2^{Omega(n^{1/4})}, an infinite separation.

Surprising findings

• Distribution-free gradient descent with limited precision collapses, on average, to learning linear combinations of random features, which implies parity learning is hard for distribution-free bSGD.

Limitations

• Requires gradient precision c bounded away from fine precision; the result does not hold for arbitrarily fine gradients.
• Bounds are polynomial but loose (e.g., exponent 24.01 on SQ dimension), and the result is purely theoretical with no experiments.

Experimental setup

Metrics: 0/1 loss dimension complexity

Baselines: probabilistic dimension complexity standard dimension complexity

Builds on: Statistical query dimension (Blum et al.) Probabilistic dimension complexity (Kamath, Montasser, Srebro et al.) AdaBoost Sherstov sign-matrix discrepancy theorem

Closest papers by meaning

• On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.88)
• Learning with SGD and Random Features (NeurIPS 2018 · similarity 0.87)
• Random Function Descent (NeurIPS 2024 · similarity 0.87)
• The Sample Complexity of Gradient Descent in Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
• Learning Complexity of Gradient Descent and Conjugate Gradient Algorithms (AAAI 2025 · similarity 0.87)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.86)