To understand why deep neural networks optimize so reliably and generalize so well, learning theorists often reach for a familiar tool: the linear model. By studying linear regression, linear logistic regression, or heavily linearized approximations like the Neural Tangent Kernel (NTK) regime, researchers can derive exact mathematical guarantees. We can calculate precise risk bounds, map out optimization trajectories, and quantify adversarial vulnerabilities.
However, a profound tension underpins this approach. Deep neural networks are fundamentally non-linear, non-convex systems. While linear models provide an elegant mathematical sandbox, they often fail to capture the chaotic dynamics, intricate geometries, and emergent behaviors—such as grokking or phase transitions—that define modern deep learning. This discrepancy forms the linear approximation gap: the theoretical blind spot where insights derived from linear systems fail to translate to non-linear architectures.
The Appeal of the Linear Sandbox
Before exploring where linear approximations fail, it is essential to understand why they are so widely used. In overparameterized regimes (where a model has more parameters than data points), linear systems exhibit rich, unexpected behaviors that mirror deep learning phenomena.
For instance, linear models have helped unpack the mystery of implicit regularization—the tendency of gradient descent to find simple, well-generalizing solutions without an explicit penalty like weight decay. Difan Zou et al. demonstrated in The Benefits of Implicit Regularization from SGD in Least Squares Problems that the instance-wise advantages of Stochastic Gradient Descent (SGD) can be rigorously bounded within linear least squares problems.
Similarly, linear frameworks allow us to analyze specific optimization choices, such as stepsize schedules and weight averaging:
- Stepsize Schedules: In Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regression, Jingfeng Wu et al. established sharp, problem-dependent risk bounds for the final iterate of SGD under geometric stepsize decay, proving that the final model generalizes nearly as well as more complex averaging techniques.
- Weight Averaging: When explicit averaging is used, such as Exponential Moving Average (EMA), Quanquan Gu et al. used high-dimensional linear regression in Understanding SGD with Exponential Moving Average: A Case Study in Linear Regression to show how EMA uniquely combines rapid bias convergence with robust variance reduction.
- Data Augmentation: Linearization also clarifies data scheduling. Boris Hanin et al. analyzed linear regression in How Data Augmentation affects Optimization for Linear Regression to show how jointly scheduling learning rates and data augmentation strength guarantees convergence to minimum-norm solutions.
Even in generative modeling and classification, linear simplifications yield elegant insights. Dana Weitzner et al. stripped away the complexity of deep diffusion networks in On the Relation Between Linear Diffusion and Power Iteration, revealing that the linear generative process shares a deep mathematical lineage with classical power iteration. On nonseparable data, Matus Telgarsky proved in The implicit bias of gradient descent on nonseparable data that linear logistic regression follows a mathematically precise "optimal ray" biased toward the most separable components of the dataset.
Furthermore, high-dimensional linear regression allows theorists to map out complex generalization curves. Denny Wu et al. identified optimal ridge regularization matrices to minimize prediction risk in On the Optimal Weighted $\ell_2$ Regularization in Overparameterized Linear Regression, while Gabriel Mel developed a framework in A theory of high dimensional regression with arbitrary correlations between input features and target functions: sample complexity, multiple descent curves and a hierarchy of phase transitions that captures multiple descent curves and phase transitions under arbitrary feature correlations.
This tractability extends directly to adversarial robustness. Mahdi Soltanolkotabi et al. provided an exact characterization of the tradeoff between standard accuracy and robustness in Precise Tradeoffs in Adversarial Training for Linear Regression, showing that adversarial training acts as a regularizer that shifts the famous double descent peak. Similarly, Antonio H. Ribeiro et al. proved in Regularization properties of adversarially-trained linear regression that adversarially trained linear regression bridges the gap between classical shrinkage methods (like Lasso) and minimum-norm interpolation, offering noise-independent error bounds.
Where the Linear Proxy Fails
Despite these successes, the core limitation remains: deep networks do not behave like linear models during practical training. The linear proxy breaks down across several critical dimensions.
Chaotic and Non-Convex Optimization Dynamics
Linear models possess convex loss landscapes with predictable trajectories. In contrast, deep networks operate in highly non-convex landscapes. As noted by the authors of How Data Augmentation affects Optimization for Linear Regression, proofs of linear convergence fail to account for the chaotic dynamics encountered in deep architectures.
Similarly, Konstantinos Pitas et al. point out in The Fine Print on Tempered Posteriors that theoretical analyses relying on linearized approximations and Gaussian gradient assumptions fail to reflect the intricate high-dimensional geometry and non-linearities of actual deep learning loss landscapes.
The Fragility of Robustness Guarantees
The geometric intuition of robustness in linear models can be actively misleading. For example, Antonio H. Ribeiro et al. demonstrated a striking dichotomy in overparameterized linear models in Overparameterized Linear Regression under Adversarial Attacks: adding features improves robustness against $\ell_2$-norm attacks but makes the model infinitely brittle against $\ell_\infty$-norm attacks. However, the authors emphasize that such linear frameworks fail to describe deep non-linear architectures, particularly during the middle stages of training.
Furthermore, while more data typically helps linear models, Yifei Min et al. proved in The curious case of adversarially robust models: More data can help, double descend, or hurt generalization that in adversarial regimes, more training data can actually hurt generalization on clean test sets—a paradox whose behavior in multi-layer, non-linear networks remains an open question.
Emergent Behaviors and Concept Shifts
Linear models scale smoothly, but deep networks exhibit discontinuous behaviors like grokking (sudden generalization long after overfitting). Licong Lin et al. noted in Improved Scaling Laws in Linear Regression via Data Reuse that scaling laws derived from linear regression completely miss these non-linear dynamics.
Similarly, when studying how models adapt to changing environments, Alex Nguyen et al. showed in Generalization vs Specialization under Concept Shift that under "concept shift," more data can degrade performance. While their linear ridge regression framework provides a baseline, it cannot fully capture the complex risk dynamics of deep, highly non-linear architectures.
Accelerated Optimization
Even basic optimization choices diverge. While momentum is standard in deep learning, Xuheng Li et al. note in Risk Bounds of Accelerated SGD for Overparameterized Linear Regression that linear regression frameworks cannot determine whether Accelerated SGD actually improves generalization or merely speeds up optimization in non-convex settings with non-linear activations.
Escaping Linearization
To overcome the limitations of the linear model assumption, recent theoretical work has begun to analyze finite-width, non-linear networks directly, avoiding the oversimplifications of the NTK or linear regimes.
A key example of this shift is the work of Jing An in Convergence of Stochastic Gradient Descent under a Local Łojasiewicz Condition for Deep Neural Networks. Instead of approximating the network as a linear system, the author leverages a local Łojasiewicz condition to analyze the true non-convex landscape of finite-width deep neural networks. This approach proves that if SGD initializes near a region of good solutions, there is a measurable, positive probability that the entire training trajectory will remain bounded within that region and successfully converge to a global minimum.
By moving away from global linearization and instead analyzing the local geometric properties of non-convex landscapes, such frameworks allow theorists to capture the genuine non-linear dynamics of neural networks. Bridging this gap completely remains one of the most vital frontiers in machine learning theory, ensuring that our mathematical explanations match the empirical reality of deep learning.
Key Foundational Work
The implicit bias of gradient descent on nonseparable data (2019) — contributed 1 concept elements to this direction.
Gradient descent with identity initialization efficiently learns positive definite linear transformations by deep residual networks (2018) — contributed 1 concept elements to this direction.