The Generalization Cost of Efficient Optimization

This direction is split into other directions: generalization-optimization tradeoff. Its last version stays readable and citable here.

Version 1 of 166 papers84 conceptsfrozen 2026-10-04

In the traditional view of numerical optimization, the goal is simple: find the global minimum of a loss function as quickly and precisely as possible. However, in machine learning, we do not care about the training loss for its own sake; we care about the "population risk"—how the model performs on data it has never seen.

A recurring theme across decades of research, from early neural network studies to modern second-order methods, is that optimization efficiency and generalization are often at odds. When we make an optimizer "better" at its job—faster, more precise, or more globally aware—we often make the resulting model worse at generalizing.

The Precision Trap

Standard first-order methods like Stochastic Gradient Descent (SGD) are notoriously "lazy." They are noisy, they get stuck in plateaus, and they take a long time to converge. Yet, this slowness is a form of implicit regularization. Rich Caruana, Steve Lawrence, and C. Lee Giles noted in Overfitting in Neural Nets: Backpropagation, Conjugate Gradient, and Early Stopping that highly efficient algorithms like Conjugate Gradient (CG) can be detrimental because they rapidly minimize training error by fitting noise.

When an optimizer is too precise, it finds "sharp" minima—narrow holes in the loss landscape that represent a perfect fit for the training data but fail to capture the broader structure of the problem. Dachao Lin and colleagues demonstrate this in Towards Better Generalization: BP-SVRG in Training Deep Neural Networks, where they show that theoretically "faster" variance-reduced methods (SVRG) often generalize poorly. Their solution is counter-intuitive: intentionally increasing gradient variance to force the model toward flatter, more robust regions of the parameter space.

The Cost of Curvature

Second-order optimizers use the Hessian (the matrix of second derivatives) to navigate the loss landscape more intelligently. Algorithms like K-FAC, developed by James Martens and Jimmy Ba, or the Hessian-based ADLER by Dario Balboni and Davide Bacciu, can converge in a fraction of the steps required by SGD.

However, these "giant leaps" come with a risk. As Martens and Ba observe, second-order methods lack the inherent stochastic noise that helps first-order methods skip over small, noisy minima. By following the curvature of the training loss too faithfully, these optimizers reach regimes of zero training error before the model has learned generalizable features. This creates a "generalization gap" where test performance plateaus or even degrades while training loss continues to plummet.

The Optimality Paradox in Decision Trees

This tension isn't limited to neural networks. In the world of decision trees, the classic CART algorithm is "greedy"—it makes the best local split at each step without looking ahead. While this seems suboptimal, researchers have found that seeking mathematical optimality often leads to worse results.

Hector Kohler and Pierre‐Marie Preux explore this in Breiman meets Bellman: Non-Greedy Decision Trees with MDPs. They note that while optimal solvers can find the absolute best tree for a training set, these trees are often hyper-specialized to that specific data. The "suboptimal" greedy approach acts as a natural constraint, preventing the tree from becoming too complex and ensuring it remains useful for new data.

The Multi-Pass Phase Transition

Perhaps the most striking evidence of this trade-off is the "catastrophic overfitting" observed when moving from a single pass of data to multiple passes. In Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization, Tomer Koren, Roi Livni, and Shira Vansover-Hager prove that the very step size that makes SGD "optimal" for a single epoch can cause population loss to explode in the second epoch.

This suggests that generalization is not a stable state that we "arrive at" and stay in; it is a transient property of the learning trajectory. If the optimizer is too efficient, it passes through the "generalization zone" too quickly and begins the process of memorization.

Reconciling Speed and Generalization

If efficiency is dangerous, how do we build better optimizers? The research suggests several paths:

  1. Implicit Regularization through Noise: Methods like Label Noise GD (Wei Huang et al., How Does Label Noise Gradient Descent Improve Generalization in the Low SNR Regime?) show that adding noise can suppress the memorization of training errors, allowing the signal to grow while the noise is ignored.
  2. Landscape Smoothing: Techniques that focus on finding "flat" minima, such as Sharpness-Aware Minimization (SAM) or the adaptive scaling mechanisms proposed by Jumin Han and Jun-Hee Kim in Towards Generalizable 3D Human Pose Estimation via Ensembles on Flat Loss Landscapes, attempt to decouple optimization speed from the risk of hitting sharp, non-generalizable holes.
  3. Satisficing Objectives: Instead of pure minimization, methods like Satisficing Domain Generalization (Ozan Şener and Vladlen Koltun, Domain Generalization without Excess Empirical Risk) treat training performance as a constraint rather than a target to be maximized indefinitely.

The takeaway for researchers is that an optimizer's success should not be measured by how low it can drive the training loss, but by how well it preserves the model's ability to handle the unknown. In machine learning, the fastest path to the bottom is rarely the best path to the truth.

Papers in this version

Showing 60 of 66 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_generalization_cost_of_efficient_opt_10f9c51e,
  title = {The Generalization Cost of Efficient Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-generalization-cost-of-efficient-optimization/rdr_10f9c51ef39a4f84a766e5953635feda},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_generalization_cost_of_efficient_opt_10f9c51e_v1,
  title = {The Generalization Cost of Efficient Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-generalization-cost-of-efficient-optimization/rdr_10f9c51ef39a4f84a766e5953635feda/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}