# A Provably Correct Algorithm for Deep Learning that Actually Works

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2018.

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

- [A Phase Transition in Diffusion Models Reveals the Hierarchical Nature of Data](https://mlsanity.com/paper/2402.16991/) (2024)
- [Revisiting Locally Supervised Learning: an Alternative to End-to-end Training](https://mlsanity.com/paper/2101.10832/) (2021)
- [How Deep Neural Networks Learn Compositional Data: The Random Hierarchy Model](https://mlsanity.com/paper/2307.02129/) (2023)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Towards a theory of how the structure of language is acquired by deep neural networks](https://mlsanity.com/paper/2406.00048/) (2024)
- [Probing the Latent Hierarchical Structure of Data via Diffusion Models](https://mlsanity.com/paper/2410.13770/) (2024)
- [How Compositional Generalization and Creativity Improve as Diffusion Models are Trained](https://mlsanity.com/paper/2502.12089/) (2025)
- [Learning curves theory for hierarchically compositional data with power-law distributed features](https://mlsanity.com/paper/2505.07067/) (2025)
- [How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model](https://mlsanity.com/paper/2404.10727/) (2024)
- [Training Deep Architectures Without End-to-End Backpropagation: A Survey on the Provably Optimal Methods](https://mlsanity.com/paper/2101.03419/) (2021)
- [Scaling Laws and Representation Learning in Simple Hierarchical Languages: Transformers vs. Convolutional Architectures](https://mlsanity.com/paper/2505.07070/) (2025)
- [Deep networks learn to parse uniform-depth context-free languages from local statistics](https://mlsanity.com/paper/2602.06065/) (2026)
- [What Makes Data Suitable for a Locally Connected Neural Network? A Necessary and Sufficient Condition Based on Quantum Entanglement](https://mlsanity.com/paper/2303.11249/) (2023)
- [Neural Networks Generalize on Low Complexity Data](https://mlsanity.com/paper/2409.12446/) (2024)
- [Towards Worst-Case Guarantees with Scale-Aware Interpretability](https://mlsanity.com/paper/2602.05184/) (2026)
- [Sampling Data with Chains of Forward-Backward Diffusion Steps](https://mlsanity.com/paper/2605.27006/) (2026)
- [Learn from your own latents and not from tokens: A sample-complexity theory](https://mlsanity.com/paper/2605.27734/) (2026)
- [Statistical Properties of Training & Generalization](https://mlsanity.com/paper/2606.20299/) (2026)
- [An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammars](https://mlsanity.com/paper/2606.17522/) (2026)
- [A theory of platonic representations in language models](https://mlsanity.com/paper/2610.07168/) (2026)

## Abstract (arXiv)

We describe a layer-by-layer algorithm for training deep convolutional networks, where each step involves gradient updates for a two layer network followed by a simple clustering algorithm. Our algorithm stems from a deep generative model that generates mages level by level, where lower resolution images correspond to latent semantic classes. We analyze the convergence rate of our algorithm assuming that the data is indeed generated according to this model (as well as additional assumptions). While we do not pretend to claim that the assumptions are realistic for natural images, we do believe that they capture some true properties of real data. Furthermore, we show that our algorithm actually works in practice (on the CIFAR dataset), achieving results in the same ballpark as that of vanilla convolutional neural networks that are being trained by stochastic gradient descent. Finally, our proof techniques may be of independent interest.