Decoupling Optimization Convergence from Generalization Performance

28 concepts29 papers1 proposal

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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimization_generalization_gap_f9a7a480,
  title = {optimization-generalization gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimization-generalization-gap/rdr_f9a7a4807a644e309f15bb6ad8823d3a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimization_generalization_gap_f9a7a480_v1,
  title = {optimization-generalization gap},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimization-generalization-gap/rdr_f9a7a4807a644e309f15bb6ad8823d3a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake