In classical machine learning theory, optimization and generalization are treated as two sides of the same coin. We design a loss function to act as a proxy for true risk, minimize it on a training set, and rely on uniform convergence bounds to guarantee that low training error translates to low test error.
However, in modern deep learning, this tight coupling breaks down completely. We routinely prove that standard optimization algorithms can successfully drive training loss to a global minimum across a wide variety of architectures—including wide convolutional networks (Quynh Nguyen et al. in [The loss surface and expressivity of deep convolutional neural networks]), deep equilibrium models (Xingyu Xie et al. in [Global Convergence of Over-parameterized Deep Equilibrium Models]), and massive Transformers (Cheng Gao et al. in [Global Convergence in Training Large-Scale Transformers]).
Yet, as Jason D. Lee et al. observe in [Gradient Descent Finds Global Minima of Deep Neural Networks], proving that an optimizer can find a global minimum tells us virtually nothing about why the resulting model generalizes to unseen data. This fundamental disconnect forms the optimization-generalization gap: the mathematical mechanisms that guarantee easy training are distinct from, and often independent of, the mechanisms that ensure predictive accuracy.
The Sufficiency Gap: Why Zero Training Loss is Not Enough
To understand why optimization proofs fail to explain generalization, we must look at the geometry of over-parameterized loss landscapes. When a network has far more parameters than training samples, the system of equations is highly under-determined. The global optimum is no longer a single isolated point, but an entire high-dimensional manifold of solutions that all achieve zero training error.
C. Daniel Freeman et al. demonstrated in [Topology and Geometry of Half-Rectified Network Optimization] that as networks grow wider, their loss landscapes become "asymptotically connected." This means an optimizer can easily navigate the landscape to find a valid global minimum. However, this manifold of zero training loss is heterogeneous: it contains some parameter configurations that capture the true underlying data distribution, and others that simply memorize noise or exhibit extreme sensitivity to out-of-distribution inputs.
Consequently, architectural modifications that smooth the loss landscape do not automatically improve generalization. For instance, Shiyu Liang et al. showed in [Adding One Neuron Can Eliminate All Bad Local Minima] that adding a single specialized neuron can mathematically eliminate all bad local minima from a network's loss surface. While this guarantee ensures that gradient descent will never get stuck during training, it provides no theoretical protection against overfitting. The optimization objective is perfectly satisfied, but it remains fundamentally blind to the model's downstream generalization quality.
Over-parameterized Parameter Space
┌────────────────────────────────────────┐
│ Manifold of Zero Training Loss │
│ ┌──────────────────┐ │
│ │ Overfitted │ │
│ │ Solutions │ │
│ └──────────────────┘ │
│ ▲ │
│ │ Optimization finds │
│ │ a path here... │
│ ┌────────────┴─────┐ │
│ │ Well-Generalizing│ │
│ │ Solutions │ │
│ └──────────────────┘ │
└────────────────────────────────────────┘
The Necessity Gap: Why Perfect Fitting is Not Required
The decoupling of optimization and generalization cuts both ways. Just as achieving a global minimum is insufficient for generalization, perfectly minimizing the training objective is also surprisingly unnecessary.
In a direct challenge to conventional learning theory, Roi Livni et al. identified a phenomenon termed "benign underfitting" in [Benign Underfitting of Stochastic Gradient Descent]. They proved that Stochastic Gradient Descent (SGD) can find solutions that achieve optimal population risk (test performance) even when the algorithm fails to minimize the empirical training error, leaving a large training-generalization gap.
Furthermore, when training objectives are modified for computational efficiency—such as using data compression techniques—the absolute mathematical optimum of the training objective can be statistically inferior to suboptimal alternatives. Alex Gittens et al. demonstrated this tension in [Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging], showing that a sketched regression solution can achieve a near-optimal training objective value while simultaneously exhibiting a statistical risk that is significantly worse than the true solution.
Because the global training optimum does not always align with the best test performance, exploring a set of near-optimal solutions can yield better models. As Satoshi Hara et al. showed in [Enumerate Lasso Solutions for Feature Selection], enumerating alternative solutions that sit slightly below the absolute mathematical optimum allows practitioners to discover models with significantly better predictive power and scientific interpretability on unseen data.
Bridging the Gap via Trajectories and Implicit Bias
If the final value of the training loss function does not dictate generalization, what does? The resolution to this paradox lies in the optimization trajectory—the specific path an optimizer takes through the parameter space. The choice of optimizer, initialization, and step size exerts an implicit bias that selects well-generalizing solutions out of the infinite pool of valid training minimizers.
Several theoretical frameworks attempt to model this interaction:
- Path Geometry: Yi Zhou et al. argue in [SGD Converges to Global Minimum in Deep Learning via Star-convex Path] that the geometric properties of the path traversed by SGD inherently bias the model toward solutions with strong predictive capabilities, rather than just any arbitrary global minimum.
- Feature Distribution Dynamics: Instead of tracking individual weights, Cong Fang et al. developed a mean-field framework in [Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks] that tracks the distribution of hidden unit outputs. This allows them to show how optimization dynamics escape "lazy training" regimes to learn robust, generalizable feature representations.
- Ergodic Invariant Measures: In large-scale training, model weights rarely settle into a single stationary point. Haochuan Li et al. proved in [Neural Network Weights Do Not Converge to Stationary Points: An Invariant Measure Perspective] that while individual weights continue to fluctuate dynamically, their distribution stabilizes. This stable invariant measure explains why training loss flattens out even as the model keeps moving, providing a potential link to generalization bounds.
- Continuous Transportation Maps: Bypassing infinite-width assumptions, Taiji Suzuki established global convergence and fast generalization rates in [Generalization bound of globally optimal non-convex neural network training: Transportation map estimation by infinite dimensional Langevin dynamics] by modeling the training trajectory as a transportation map estimation problem solved via infinite-dimensional Langevin dynamics.
As Zixuan Zhang et al. emphasize in [Nonparametric Classification on Low Dimensional Manifolds using Overparameterized Convolutional Residual Networks], isolating architectural capacity from optimization dynamics creates an incomplete picture. A complete end-to-end theory of deep learning cannot simply prove that an optimizer reaches a destination; it must explain how the optimization journey itself guides the network toward low-complexity, high-generalization regions of the parameter space.
Key Foundational Work
Topology and Geometry of Half-Rectified Network Optimization (2017) — contributed 1 concept elements to this direction.
Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging (2017) — contributed 1 concept elements to this direction.
Learning a hyperplane classifier by minimizing an exact bound on the VC dimension (2015) — contributed 1 concept elements to this direction.