# Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jan 2020.

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

- [Deep Learning is Not So Mysterious or Different](https://mlsanity.com/paper/2503.02113/) (2025)
- [A Theoretical Analysis on Feature Learning in Neural Networks: Emergence from Inputs and Advantage over Fixed Features](https://mlsanity.com/paper/2206.01717/) (2022)
- [Physics of Language Models: Part 4.1, Architecture Design and the Magic of Canon Layers](https://mlsanity.com/paper/2512.17351/) (2025)
- [Beyond NTK with Vanilla Gradient Descent: A Mean-Field Analysis of Neural Networks with Polynomial Width, Samples, and Time](https://mlsanity.com/paper/2306.16361/) (2023)
- [Provable Guarantees for Neural Networks via Gradient Feature Learning](https://mlsanity.com/paper/2310.12408/) (2023)
- [Adversarial Training Can Provably Improve Robustness: Theoretical Analysis of Feature Learning Process Under Structured Data](https://mlsanity.com/paper/2410.08503/) (2024)
- [Theoretical Analysis of Robust Overfitting for Wide DNNs: An NTK Approach](https://mlsanity.com/paper/2310.06112/) (2023)
- [Deep Kernel Principal Component Analysis for Multi-level Feature Learning](https://mlsanity.com/paper/2302.11220/) (2023)
- [Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets](https://mlsanity.com/paper/2410.01779/) (2024)
- [Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining](https://mlsanity.com/paper/2601.19756/) (2026)
- [Deep Learning of Compositional Targets with Hierarchical Spectral Methods](https://mlsanity.com/paper/2602.10867/) (2026)
- [Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectories](https://mlsanity.com/paper/2511.07368/) (2025)
- [Muon Learns More Robust and Transferable Features than Adam](https://mlsanity.com/paper/2606.09658/) (2026)
- [Learning Hierarchical Polynomials of Multiple Nonlinear Features with Three-Layer Networks](https://mlsanity.com/paper/2411.17201/) (2024)
- [Feature learning is decoupled from generalization in high capacity neural networks](https://mlsanity.com/paper/2507.19680/) (2025)
- [MeGU: Machine-Guided Unlearning with Target Feature Disentanglement](https://mlsanity.com/paper/2602.17088/) (2026)
- [Why ReLU? A Bit-Model Dichotomy for Deep Network Training](https://mlsanity.com/paper/2602.19017/) (2026)
- [Algorithmic Separation between Constant-Depth and Logarithmic-Depth Neural Networks](https://mlsanity.com/paper/2607.25200/) (2026)
- [Greedy Local Learning for Language Model Pretraining: Gaps and Objective Design](https://mlsanity.com/paper/2610.04867/) (2026)

## Abstract (arXiv)

Deep learning is also known as hierarchical learning, where the learner learns_ to represent a complicated target function by decomposing it into a sequence of simpler functions to reduce sample and time complexity. This paper formally analyzes how multi-layer neural networks can perform such hierarchical learning efficiently_ and automatically_ by SGD on the training objective. On the conceptual side, we present a theoretical characterizations of how certain types of deep (i.e. super-constant layer) neural networks can still be sample and time efficiently trained on some hierarchical tasks, when no existing algorithm (including layerwise training, kernel method, etc) is known to be efficient. We establish a new principle called "backward feature correction", where the errors in the lower-level features can be automatically corrected when training together with the higher-level layers. We believe this is a key behind how deep learning is performing deep (hierarchical) learning, as opposed to layerwise learning or simulating some non-hierarchical method. On the technical side, we show for every input dimension d > 0, there is a concept class of degree ω(1) multi-variate polynomials so that, using ω(1)-layer neural networks as learners, SGD can learn any function from this class in mathsfpoly(d) time to any frac1mathsfpoly(d) error, through learning to represent it as a composition of ω(1) layers of quadratic functions using "backward feature correction." In contrast, we do not know any other simpler algorithm (including layerwise training, applying kernel method sequentially, training a two-layer network, etc) that can learn this concept class in mathsfpoly(d) time even to any d-0.01 error. As a side result, we prove dω(1) lower bounds for several non-hierarchical learners, including any kernel methods.