# Linear Stability Hypothesis and Rank Stratification for Nonlinear Models

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 31 references that are in the map.
- First posted on arXiv 21 Nov 2022.

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

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks](https://mlsanity.com/paper/1901.06523/) (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)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Training behavior of deep neural network in frequency domain](https://mlsanity.com/paper/1807.01251/) (2018)
- [Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances](https://mlsanity.com/paper/2105.12221/) (2021)
- [An analytic theory of generalization dynamics and transfer learning in deep linear networks](https://mlsanity.com/paper/1809.10374/) (2018)
- [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)
- [Linear Frequency Principle Model to Understand the Absence of Overfitting in Neural Networks](https://mlsanity.com/paper/2102.00200/) (2021)
- [Embedding Principle in Depth for the Loss Landscape Analysis of Deep Neural Networks](https://mlsanity.com/paper/2205.13283/) (2022)

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

- [Complexity Control Facilitates Reasoning-Based Compositional Generalization in Transformers](https://mlsanity.com/paper/2501.08537/) (2025)
- [Initialization is Critical to Whether Transformers Fit Composite Functions by Reasoning or Memorizing](https://mlsanity.com/paper/2405.05409/) (2024)
- [An Analysis for Reasoning Bias of Language Models with Small Initialization](https://mlsanity.com/paper/2502.04375/) (2025)
- [Understanding the Initial Condensation of Convolutional Neural Networks](https://mlsanity.com/paper/2305.09947/) (2023)
- [Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completion](https://mlsanity.com/paper/2405.13721/) (2024)
- [Scalable Complexity Control Facilitates Reasoning Ability of LLMs](https://mlsanity.com/paper/2505.23013/) (2025)
- [Disentangle Sample Size and Initialization Effect on Perfect Generalization for Single-Neuron Target](https://mlsanity.com/paper/2405.13787/) (2024)

## Abstract (arXiv)

Models with nonlinear architectures/parameterizations such as deep neural networks (DNNs) are well known for their mysteriously good generalization performance at overparameterization. In this work, we tackle this mystery from a novel perspective focusing on the transition of the target recovery/fitting accuracy as a function of the training data size. We propose a rank stratification for general nonlinear models to uncover a model rank as an "effective size of parameters" for each function in the function space of the corresponding model. Moreover, we establish a linear stability theory proving that a target function almost surely becomes linearly stable when the training data size equals its model rank. Supported by our experiments, we propose a linear stability hypothesis that linearly stable functions are preferred by nonlinear training. By these results, model rank of a target function predicts a minimal training data size for its successful recovery. Specifically for the matrix factorization model and DNNs of fully-connected or convolutional architectures, our rank stratification shows that the model rank for specific target functions can be much lower than the size of model parameters. This result predicts the target recovery capability even at heavy overparameterization for these nonlinear models as demonstrated quantitatively by our experiments. Overall, our work provides a unified framework with quantitative prediction power to understand the mysterious target recovery behavior at overparameterization for general nonlinear models.