SGD Through the Lens of Kolmogorov Complexity
Not on the map. Why?
Abstract (arXiv)
We prove that stochastic gradient descent (SGD) finds a solution that achieves (1-ε) classification accuracy on the entire dataset. We do so under two main assumptions: (1. Local progress) The model accuracy improves on average over batches. (2. Models compute simple functions) The function computed by the model is simple (has low Kolmogorov complexity). It is sufficient that these assumptions hold only for a tiny fraction of the epochs. Intuitively, the above means that intermittent local progress of SGD implies global progress. Assumption 2 trivially holds for underparameterized models, hence, our work gives the first convergence guarantee for general, underparameterized models. Furthermore, this is the first result which is completely model agnostic - we do not require the model to have any specific architecture or activation function, it may not even be a neural network. Our analysis makes use of the entropy compression method, which was first introduced by Moser and Tardos in the context of the Lov'asz local lemma.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 16 of its 42 references that are in the map. First posted on arXiv 10 Nov 2021.
Builds on
16 of 42 references.
References · 16
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
- 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 787
- 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 574
- 2018On the Optimization of Deep Networks: Implicit Acceleration by Overparameterizationcited by 284
- 2018A Convergence Analysis of Gradient Descent for Deep Linear Neural Networkscited by 184
- 2018Deep learning generalizes because the parameter-function map is biased towards simple functionscited by 183
- 2019Towards moderate overparameterization: global convergence guarantees for training shallow neural networkscited by 176
- 2018Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networkscited by 141
- 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 121
- 2017Spurious Local Minima are Common in Two-Layer ReLU Neural Networkscited by 104
- 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
- 2020Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topologycited by 66
4 more
- 2020An Overview of Neural Network Compressioncited by 59
- 2020Is SGD a Bayesian sampler? Well, almostcited by 50
- 2021On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widthscited by 44
- 2021A Convergence Theory Towards Practical Over-parameterized Deep Neural Networkscited by 4
Built on by
Citing papers per year: 2022: 1.
1 paper.