# Local Linear Recovery Guarantee of Deep Neural Networks at Overparameterization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 25 references that are in the map.
- First posted on arXiv 26 Jun 2024.

## Builds on (most cited first, 18 of 18)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances](https://mlsanity.com/paper/2105.12221/) (2021)
- [Recovery Guarantees for One-hidden-layer Neural Networks](https://mlsanity.com/paper/1706.03175/) (2017)
- [Phase diagram for two-layer ReLU neural networks at infinite-width limit](https://mlsanity.com/paper/2007.07497/) (2020)
- [Gradient Descent Quantizes ReLU Network Features](https://mlsanity.com/paper/1803.08367/) (2018)
- [The Global Landscape of Neural Networks: An Overview](https://mlsanity.com/paper/2007.01429/) (2020)
- [Embedding Principle of Loss Landscape of Deep Neural Networks](https://mlsanity.com/paper/2105.14573/) (2021)
- [Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functions](https://mlsanity.com/paper/2209.15055/) (2022)
- [Towards Understanding the Condensation of Neural Networks at Initial Training](https://mlsanity.com/paper/2105.11686/) (2021)
- [Semi-flat minima and saddle points by embedding neural networks to overparameterization](https://mlsanity.com/paper/1906.04868/) (2019)
- [Implicit regularization of dropout](https://mlsanity.com/paper/2207.05952/) (2022)
- [Embedding Principle: a hierarchical structure of loss landscape of deep neural networks](https://mlsanity.com/paper/2111.15527/) (2021)
- [Empirical Phase Diagram for Three-layer Neural Networks with Infinite Width](https://mlsanity.com/paper/2205.12101/) (2022)
- [Embedding Principle in Depth for the Loss Landscape Analysis of Deep Neural Networks](https://mlsanity.com/paper/2205.13283/) (2022)
- [Optimistic Estimate Uncovers the Potential of Nonlinear Models](https://mlsanity.com/paper/2307.08921/) (2023)

## Abstract (arXiv)

Determining whether deep neural network (DNN) models can reliably recover target functions at overparameterization is a critical yet complex issue in the theory of deep learning. To advance understanding in this area, we introduce a concept we term "local linear recovery" (LLR), a weaker form of target function recovery that renders the problem more amenable to theoretical analysis. In the sense of LLR, we prove that functions expressible by narrower DNNs are guaranteed to be recoverable from fewer samples than model parameters. Specifically, we establish upper limits on the optimistic sample sizes, defined as the smallest sample size necessary to guarantee LLR, for functions in the space of a given DNN. Furthermore, we prove that these upper bounds are achieved in the case of two-layer tanh neural networks. Our research lays a solid groundwork for future investigations into the recovery capabilities of DNNs in overparameterized scenarios.