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

arXiv: https://arxiv.org/abs/2505.10423 · HTML: https://mlsanity.com/paper/2505.10423/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 29 references that are in the map.
- First posted on arXiv 15 May 2025.

## Builds on (most cited first, 13 of 13)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [SGD Learns the Conjugate Kernel Class of the Network](https://mlsanity.com/paper/1702.08503/) (2017)
- [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021)
- [Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity](https://mlsanity.com/paper/2003.04180/) (2020)
- [Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and Luck](https://mlsanity.com/paper/2309.03800/) (2023)
- [Distributional PAC-Learning from Nisan's Natural Proofs](https://mlsanity.com/paper/2310.03641/) (2023)
- [Learning Boolean Circuits with Neural Networks](https://mlsanity.com/paper/1910.11923/) (2019)

## Abstract (arXiv)

We study the relationship between gradient-based optimization of parametric models (e.g., neural networks) and optimization of linear combinations of random features. Our main result shows that if a parametric model can be learned using mini-batch stochastic gradient descent (bSGD) without making assumptions about the data distribution, then with high probability, the target function can also be approximated using a polynomial-sized combination of random features. The size of this combination depends on the number of gradient steps and numerical precision used in the bSGD process. This finding reveals fundamental limitations of distribution-free learning in neural networks trained by gradient descent, highlighting why making assumptions about data distributions is often crucial in practice. Along the way, we also introduce a new theoretical framework called average probabilistic dimension complexity (adc), which extends the probabilistic dimension complexity developed by Kamath et al. (2020). We prove that adc has a polynomial relationship with statistical query dimension, and use this relationship to demonstrate an infinite separation between adc and standard dimension complexity.