The Convergence Cost of Weak Regularization

17 concepts16 papers1 proposal

Many fundamental problems in machine learning and optimization are notoriously difficult to solve because they lack smoothness. For instance, computing exact Optimal Transport (OT) distances involves solving linear programs with sharp combinatorial constraints, while Mathematical Programs with Equilibrium Constraints (MPECs) contain non-differentiable "min" functions.

To make these problems tractable, a common strategy is to inject a regularization term—often an entropic penalty or a smoothing function. This transforms a jagged, hard-to-optimize landscape into a smooth, strictly convex one, enabling fast iterative algorithms.

However, this introduces a fundamental trade-off. If the regularization is too strong, the optimization landscape is smooth but the optimal solution is heavily distorted. For example, in dynamic mass transport, strong regularization introduces unwanted mass diffusion, as noted by Ferran Arqué et al. in Approximate Wasserstein Attraction Flows for Dynamic Mass Transport over Networks. To recover the true, unregularized solution, we must decrease the regularization parameter toward zero. But as we do, the computational efficiency collapses. This phenomenon—where the convergence rate degrades as regularization weakens—is a ubiquitous bottleneck across modern optimization.

Why Regularization Accelerates Optimization

To understand why weak regularization slows down convergence, we must first understand why strong regularization speeds it up.

Imagine trying to find the lowest point of a sharp, V-shaped valley. Without regularization, optimization algorithms must rely on subgradient methods, which are forced to take slow, cautious steps to avoid bouncing back and forth across the valley walls.

When we add a smoothing regularizer, we effectively fill the bottom of the valley with water, creating a smooth, curved lake. The sharp corner disappears, replaced by a differentiable surface where the gradient points reliably toward the center.

This geometric transformation manifests across several domains:

  • Kernel Methods: In Support Vector Machines (SVMs) with indefinite kernels, Yiming Ying et al. demonstrated in Analysis of SVM with Indefinite Kernels that regularizing the objective makes it differentiable with a Lipschitz continuous gradient. This smoothness allows the deployment of Nesterov’s accelerated optimization techniques, drastically reducing the iteration count.
  • Equilibrium Constraints: In MPECs, S. Ilker Birbil et al. used an entropic regularization approach in An entropic regularization approach for mathematical programs with equilibrium constraints to smooth out non-differentiable constraints, turning a combinatorial nightmare into a continuous problem solvable by standard calculus.
  • Optimal Transport: Adding an entropic penalty to a transport plan makes the objective strongly convex. As shown by Jean-David Benamou et al. in Iterative Bregman Projections for Regularized Transportation Problems, this allows the problem to be framed as a sequence of alternating Kullback-Leibler (KL) projections (the Sinkhorn-Knopp algorithm), which enjoy rapid, closed-form updates.

The Conditioning Collapse

What happens when we try to achieve high precision by dialing the regularization parameter ($\epsilon$) down toward zero? The water drains out of the valley, and the geometry collapses back into its non-smooth state.

Mathematically, the regularizer acts as a cushion that bounds the curvature of the optimization landscape. As $\epsilon \to 0$, this cushion vanishes, triggering two destructive mathematical phenomena:

1. Exploding Lipschitz Constants

The step size of gradient descent is bounded by the inverse of the objective's Lipschitz constant ($1/L$). As the regularizer weakens, the landscape becomes steeper and sharper. The authors of Analysis of SVM with Indefinite Kernels proved that the Lipschitz constant of the smoothed objective is often inversely proportional to the regularization parameter ($L \propto 1/\epsilon$). When $\epsilon$ is tiny, $L$ explodes, forcing algorithms to take infinitesimally small steps to avoid divergence.

2. Vanishing Contraction Coefficients

Algorithms like Sinkhorn operate as contraction mappings in Hilbert's projective metric. Each iteration squeezes the distance to the optimal solution by a specific contraction factor. As highlighted by Zebang Shen et al. in Sinkhorn Barycenter via Functional Gradient Descent, this contraction factor approaches $1$ exponentially fast as $\epsilon \to 0$. When the factor is close to $1$, the algorithm barely makes progress from one iteration to the next, causing the convergence rate to degrade exponentially.

The Pervasiveness of the Trade-off

This tension between exactness and iteration count is not unique to a single algorithm; it is a shared characteristic across diverse machine learning paradigms.

Distribution Matching and Generative Models

In applications like Sinkhorn AutoEncoders, introduced by Giorgio Patrini et al. in Sinkhorn AutoEncoders, or streaming optimal transport, analyzed by Arthur Mensch et al. in Online Sinkhorn: Optimal Transport distances from sample streams, practitioners face a strict accuracy-iteration trade-off. Lowering the regularization parameter yields sharper, more realistic distribution matching, but demands a massive increase in optimization iterations.

This slowdown affects not only the objective values but also their derivatives. Edouard Pauwels et al. demonstrated in The derivatives of Sinkhorn-Knopp converge that computing accurate gradients for backpropagation requires a proportional increase in Sinkhorn iterations as regularization decreases. A similar bottleneck appears when computing gradients for structural comparisons across different spaces, as explored by Wei Zhang et al. in Fast Gradient Computation for Gromov-Wasserstein Distance.

Mean-Field Optimization and Min-Max Games

When optimizing infinite-width neural networks or solving continuous min-max games via best-response flows, entropy regularization is used to guarantee global convergence. However, the same trade-off applies. Atsushi Nitanda et al. in Particle dual averaging: optimization of mean field neural network with global convergence rate analysis* and Razvan-Andrei Lascu et al. in Entropic Mean-Field Min–Max Problems via Best Response Flow showed that these convergence rates slow down significantly or exhibit exponential dependence on the entropy parameter when weak regularization is applied.

Monotonic Constraints and Seriation

Even in combinatorial heuristics, such as recovering the underlying order of noisy data, the phenomenon persists. Jingyan Wang et al. observed in A heuristic for statistical seriation that swapping out hard constraints for soft continuous regularizers creates a quantifiable trade-off: stronger enforcement of the target structure increases the number of iterations required to reach a stable solution.

Breaking the Exponential Barrier

For a long time, the exponential dependence on $1/\epsilon$ was seen as an unavoidable tax on precision. However, recent theoretical work has begun to map out conditions under which this dependency can be mitigated by leveraging the underlying geometric structure of the data.

Worst-Case Arbitrary Data       ======>   Exponential Slowdown O(e^(1/ε))
Log-Concave / Structured Data   ======>   Polynomial Slowdown O(ε^-p)

By moving away from worst-case bounds, researchers have shown that the convergence cost is highly dependent on the smoothness of the underlying distributions themselves:

These insights shift the narrative: the convergence cost of weak regularization is not an unyielding law of nature, but a reflection of the problem's geometry. By understanding the interplay between the regularization parameter and the data's intrinsic structure, we can design algorithms that achieve high precision without sacrificing computational feasibility.

Key Foundational Work

An entropic regularization approach for mathematical programs with equilibrium constraints (2004) — contributed 3 concept elements to this direction.
Analysis of SVM with Indefinite Kernels (2009) — 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_regularization_dependent_convergence_49f7b394,
  title = {regularization-dependent convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/regularization-dependent-convergence/rdr_49f7b394db9048f4bdcfeaba0e2dc015},
  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_regularization_dependent_convergence_49f7b394_v1,
  title = {regularization-dependent convergence},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/regularization-dependent-convergence/rdr_49f7b394db9048f4bdcfeaba0e2dc015/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake