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:
- Polynomial Improvements: Lénaïc Chizat et al. proved in Sharper exponential convergence rates for Sinkhorn's algorithm in continuous settings that if the underlying distributions satisfy geometric properties like log-concavity, Sinkhorn's algorithm can achieve exponential convergence rates that depend only polynomially on the regularization parameter.
- Unbounded Costs: Similarly, Promit Ghosal et al. established in On the Convergence Rate of Sinkhorn’s Algorithm non-asymptotic convergence bounds under general, unbounded cost functions where the dependence on $\epsilon$ scales polynomially (e.g., $\epsilon^{-2p}$) rather than exponentially.
- Probabilistic Coupling: Using a stochastic control perspective, Giacomo Greco et al. in Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach derived explicit bounds confirming that while convergence speed decreases as the parameter is reduced, the degradation can be precisely quantified and bounded using probabilistic coupling methods.
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.