# Optimistic Estimate Uncovers the Potential of Nonlinear Models

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 24 references that are in the map.
- First posted on arXiv 18 Jul 2023.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [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)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances](https://mlsanity.com/paper/2105.12221/) (2021)
- [SGD with Large Step Sizes Learns Sparse Features](https://mlsanity.com/paper/2210.05337/) (2022)
- [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)
- [Embedding Principle of Loss Landscape of Deep Neural Networks](https://mlsanity.com/paper/2105.14573/) (2021)
- [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)
- [An analytic theory of shallow networks dynamics for hinge loss classification](https://mlsanity.com/paper/2006.11209/) (2020)

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

- [An overview of condensation phenomenon in deep learning](https://mlsanity.com/paper/2504.09484/) (2025)
- [Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completion](https://mlsanity.com/paper/2405.13721/) (2024)
- [Geometry of Critical Sets and Existence of Saddle Branches for Two-layer Neural Networks](https://mlsanity.com/paper/2405.17501/) (2024)
- [Disentangle Sample Size and Initialization Effect on Perfect Generalization for Single-Neuron Target](https://mlsanity.com/paper/2405.13787/) (2024)
- [Local Linear Recovery Guarantee of Deep Neural Networks at Overparameterization](https://mlsanity.com/paper/2406.18035/) (2024)

## Abstract (arXiv)

We propose an optimistic estimate to evaluate the best possible fitting performance of nonlinear models. It yields an optimistic sample size that quantifies the smallest possible sample size to fit/recover a target function using a nonlinear model. We estimate the optimistic sample sizes for matrix factorization models, deep models, and deep neural networks (DNNs) with fully-connected or convolutional architecture. For each nonlinear model, our estimates predict a specific subset of targets that can be fitted at overparameterization, which are confirmed by our experiments. Our optimistic estimate reveals two special properties of the DNN models -- free expressiveness in width and costly expressiveness in connection. These properties suggest the following architecture design principles of DNNs: (i) feel free to add neurons/kernels; (ii) restrain from connecting neurons. Overall, our optimistic estimate theoretically unveils the vast potential of nonlinear models in fitting at overparameterization. Based on this framework, we anticipate gaining a deeper understanding of how and why numerous nonlinear models such as DNNs can effectively realize their potential in practice in the near future.