# SGD Through the Lens of Kolmogorov Complexity

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

## Key facts

- Cited by 1 papers 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 (most cited first, 16 of 16)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018)
- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [An Improved Analysis of Training Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/1906.04688/) (2019)
- [Spurious Local Minima are Common in Two-Layer ReLU Neural Networks](https://mlsanity.com/paper/1712.08968/) (2017)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topology](https://mlsanity.com/paper/2002.07867/) (2020)
- [An Overview of Neural Network Compression](https://mlsanity.com/paper/2006.03669/) (2020)
- [Is SGD a Bayesian sampler? Well, almost](https://mlsanity.com/paper/2006.15191/) (2020)
- [On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths](https://mlsanity.com/paper/2101.09612/) (2021)
- [A Convergence Theory Towards Practical Over-parameterized Deep Neural Networks](https://mlsanity.com/paper/2101.04243/) (2021)

## Built on by (most cited first, 1 of 1)

- [Multiclass classification utilising an estimated algorithmic probability prior](https://mlsanity.com/paper/2212.07426/) (2022)

## 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.