mlsanityData to 14 Oct 2026

Optimistic Estimate Uncovers the Potential of Nonlinear Models

arXiv 2307.08921 ↗First posted 18 Jul 2023cs.LG stat.MLcited by 5

Not on the map. Why?

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.

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

17 of 24 references.

References · 17

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,674
  4. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  5. 2017Implicit Regularization in Matrix Factorizationcited by 322
  6. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  7. 2021Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariancescited by 127
  8. 2022SGD with Large Step Sizes Learns Sparse Featurescited by 68
  9. 2020Phase diagram for two-layer ReLU neural networks at infinite-width limitcited by 67
  10. 2018Gradient Descent Quantizes ReLU Network Featurescited by 61
  11. 2021Embedding Principle of Loss Landscape of Deep Neural Networkscited by 38
  12. 2021Towards Understanding the Condensation of Neural Networks at Initial Trainingcited by 32
5 more
  1. 2019Semi-flat minima and saddle points by embedding neural networks to overparameterizationcited by 30
  2. 2022Implicit regularization of dropoutcited by 25
  3. 2021Embedding Principle: a hierarchical structure of loss landscape of deep neural networkscited by 22
  4. 2022Empirical Phase Diagram for Three-layer Neural Networks with Infinite Widthcited by 17
  5. 2020An analytic theory of shallow networks dynamics for hinge loss classificationcited by 14

Built on by

Cited by year

Citing papers per year: 2024: 4; 2025: 1.

5 papers.

  1. 2025An overview of condensation phenomenon in deep learningcited by 17
  2. 2024Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completioncited by 3
  3. 2024Geometry of Critical Sets and Existence of Saddle Branches for Two-layer Neural Networkscited by 2
  4. 2024Disentangle Sample Size and Initialization Effect on Perfect Generalization for Single-Neuron Targetcited by 0
  5. 2024Local Linear Recovery Guarantee of Deep Neural Networks at Overparameterizationcited by 0