SGD Through the Lens of Kolmogorov Complexity

Abstract

We prove that stochastic gradient descent (SGD) finds a solution that achieves $(1-\epsilon )$ 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ász local lemma.

References in corpus (9)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• Deep learning generalizes because the parameter-function map is biased towards simple functions
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• On the Proof of Global Convergence of Gradient Descent for Deep ReLU Networks with Linear Widths