Monotonicity in Quadratically Regularized Linear Programs

Alberto González-Sanz, Marcel Nutz, Andrés Riveros Valdevenito

Abstract

In optimal transport, quadratic regularization is a sparse alternative to entropic regularization: the solution measure tends to have small support. Computational experience suggests that the support decreases monotonically to the unregularized counterpart as the regularization parameter is relaxed. We find it useful to investigate this monotonicity more abstractly for linear programs over polytopes, regularized with the squared norm. Here, monotonicity can be stated as an invariance property of the curve mapping the regularization parameter to the solution: once the curve enters a face of the polytope, does it remain in that face forever? We show that this invariance is equivalent to a geometric property of the polytope, namely that each face contains the minimum norm point of its affine hull. Returning to the optimal transport problem and its associated Birkhoff polytope, we verify this property for low dimensions, but show that it fails for marginals with five or more point masses. As a consequence, the conjectured monotonicity of the support fails in general, even if experiments suggest that monotonicity holds for many cost matrices. Separately, we apply our geometric point of view to a problem of Erdős, namely to characterize the doubly stochastic matrices whose maximal trace equals their squared norm.

Introduction

Optimal Transport (OT) is a fundamental tool in machine learning for comparing probability distributions. However, the standard linear programming formulation is often computationally prohibitive and produces sparse solutions that lack the differentiability required for many modern optimization pipelines. To address this, researchers frequently turn to regularization.

While entropic regularization (Sinkhorn algorithm) is widely used, it produces dense solutions. Quadratic regularization (using the squared norm) has gained popularity because it preserves sparsity. A common observation in practice is that as the regularization parameter is relaxed, the support of the solution (the set of non-zero entries) appears to shrink monotonically toward the unregularized solution. This paper investigates whether this "monotonicity" is a universal property or a statistical artifact.

Geometric Characterization of Monotonicity

The authors abstract the problem to linear programs over convex polytopes regularized by the squared norm. They define $c$-monotonicity as an invariance property: if the solution path $x^\delta$ (where $\delta$ is the regularization strength) enters a face of the polytope, it must remain within that face for all subsequent values of $\delta$ as the regularization is further relaxed.

Geometric interpretation of the solution path $x^\delta$ for varying regularization $\delta$. The path tracks the optimal solution across the faces of the polytope.

The core theoretical contribution is Theorem 3.2, which provides a necessary and sufficient geometric condition for monotonicity. A polytope is monotone if and only if every face is "centered"—meaning the minimum-norm point of the face's affine hull lies within the face itself. This property ensures that the optimal path does not "backtrack" out of a face once it has been entered.

The Birkhoff Polytope and the $N=5$ Threshold

The research specifically examines the Birkhoff polytope (the set of all $N \times N$ doubly stochastic matrices), which is central to OT. The authors prove that for dimensions $N \le 4$, the Birkhoff polytope is indeed monotone. However, they discover that at $N=5$, the geometry becomes sufficiently complex to allow for "non-centered" faces.

By constructing an explicit $5 \times 5$ cost matrix, the authors demonstrate a counterexample where a specific entry in the transport plan is present for high and low regularization but disappears for intermediate values. This proves that universal monotonicity in quadratically regularized OT is false for $N \ge 5$.

Why Monotonicity Appears to Hold in Practice

Despite the theoretical failure for $N \ge 5$, numerical experiments often suggest monotonicity holds. The authors posit that the "bad" faces causing non-monotonicity are mathematically present but statistically rare. In typical cost landscapes, the solution path is unlikely to encounter these non-centered regions, explaining the discrepancy between practitioner experience and theoretical limits.

Solving an Erdős Conjecture

The geometric framework developed for monotonicity also provides tools to solve a long-standing problem posed by Paul Erdős. The authors characterize "Erdős matrices"—doubly stochastic matrices where the squared norm equals the maximal trace. Using their "centered face" analysis, they prove the conjecture that such matrices must always have rational entries.

Conclusion

This work provides a rigorous geometric foundation for understanding the behavior of regularized optimization. While monotonicity of support is not a universal guarantee in quadratic OT for larger dimensions, the characterization of "centered" faces offers a new lens for analyzing the stability and convergence of active-set methods. Future work may involve probabilistic analyses to determine exactly how rare non-monotone cases are in real-world applications.

Summary updated

Abstract

In optimal transport, quadratic regularization is a sparse alternative to entropic regularization: the solution measure tends to have small support. Computational experience suggests that the support decreases monotonically to the unregularized counterpart as the regularization parameter is relaxed. We find it useful to investigate this monotonicity more abstractly for linear programs over polytopes, regularized with the squared norm. Here, monotonicity can be stated as an invariance property of the curve mapping the regularization parameter to the solution: once the curve enters a face of the polytope, does it remain in that face forever? We show that this invariance is equivalent to a geometric property of the polytope, namely that each face contains the minimum norm point of its affine hull. Returning to the optimal transport problem and its associated Birkhoff polytope, we verify this property for low dimensions, but show that it fails for marginals with five or more point masses. As a consequence, the conjectured monotonicity of the support fails in general, even if experiments suggest that monotonicity holds for many cost matrices. Separately, we apply our geometric point of view to a problem of Erdős, namely to characterize the doubly stochastic matrices whose maximal trace equals their squared norm.
BibTeX
@article{gonzalezsanz2025monotonicity,
  author = {Alberto González-Sanz and Marcel Nutz and Andrés Riveros Valdevenito},
  title = {{Monotonicity in Quadratically Regularized Linear Programs}},
  journal = {SIAM J. Optim.},
  year = {2025},
  doi = {10.1137/24m1685171},
}
Figure