Monotonicity in Quadratically Regularized Linear Programs

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

TL;DR

This paper provides a rigorous geometric characterization of when the support of a quadratically regularized linear program solution changes monotonically as the regularization is relaxed. While often assumed to be true in Optimal Transport (OT) applications, the authors prove that this "monotonicity" property actually fails for the Birkhoff polytope once the dimension exceeds $4 \times 4$, though they solve a long-standing conjecture by Erdős along the way.

What Problem Does This Paper Address?

In fields like machine learning and statistics, Optimal Transport (OT) is a powerful tool for comparing probability distributions. However, the standard linear programming formulation of OT is computationally expensive and yields sparse solutions that are hard to differentiate. To solve this, researchers often use regularization.

While entropic regularization (the Sinkhorn algorithm) is the most popular, it results in "dense" solutions where every point has some mass. Quadratic regularization (using the squared norm) is a popular alternative because it maintains sparsity. Practitioners have long observed that as you decrease the regularization strength, the "support" (the set of non-zero entries) of the solution seems to shrink monotonically toward the unregularized solution.

The authors set out to answer a fundamental question: Is this monotonicity guaranteed? If it were, regularized solutions could serve as reliable "confidence bands" for the true, unregularized transport plan.

Methods

The authors abstract the problem away from OT and look at it through the lens of geometry and convex polytopes. They define a property called $c$-monotonicity: once the solution curve (parameterized by the regularization strength $\delta$) enters a specific "face" of the polytope, does it stay there until the end?

To analyze this, they compare two formulations:

  1. Eulerian: Minimizing the cost subject to a norm constraint ($\|x\| \le \delta$).
  2. Lagrangian: Minimizing a weighted sum of the cost and the squared norm.

The core of their method is a geometric characterization (Theorem 3.2). They prove that a polytope is monotone if and only if:

  • The minimum-norm point of the polytope lies in its relative interior.
  • For every face of the polytope, the minimum-norm point of that face's affine hull actually lies within the face itself (a property they call being "centered").

Datasets

As a theoretical mathematics paper, it does not use standard machine learning datasets (like ImageNet). Instead, the authors use:

  • Synthetic Cost Matrices: Specifically, they construct a $5 \times 5$ counterexample matrix to prove that monotonicity can fail in higher dimensions.
  • Combinatorial Objects: They analyze the properties of the Birkhoff polytope (the set of all doubly stochastic matrices) across different dimensions $N$.

Key Insights and Ideas

  • The Geometry of Sparsity: The "support" of a solution in OT corresponds to a specific face of the Birkhoff polytope. Monotonicity is essentially a question of whether the path of the optimal solution "backtracks" out of a face it has already entered.
  • The $N=5$ Threshold: One of the most surprising findings is that the Birkhoff polytope is perfectly "monotone" for $N \le 4$. However, at $N=5$, the geometry becomes complex enough that "non-centered" faces appear, allowing the support to behave non-monotonically.
  • Why Experiments Deceive: The authors note that while monotonicity fails theoretically for $N \ge 5$, it is rarely seen in random numerical experiments. This suggests that the "bad" faces that cause non-monotonicity are mathematically present but statistically rare in typical cost landscapes.
  • Solving Erdős: By applying their geometric "centered face" framework, the authors characterize "Erdős matrices" (doubly stochastic matrices where the squared norm equals the maximal trace) and prove a conjecture that these matrices must always have rational entries.

Key Results

  • Theorem 3.2 (The Main Characterization): Provides the necessary and sufficient geometric conditions for a polytope to be monotone for any cost vector.
  • OT Monotonicity: Proves that for quadratically regularized OT, monotonicity holds for $N \in \{1, 2, 3, 4\}$ but fails for $N \ge 5$.
  • Counterexample: The authors provide an explicit $5 \times 5$ cost matrix where a specific location $(X_1, Y_1)$ is in the support for very high and very low regularization, but disappears for intermediate values—proving the conjecture of universal monotonicity false.

Limitations and Future Work

The primary limitation is that the paper focuses on the existence of non-monotonicity rather than its prevalence. While they prove it can happen, their numerical experiments suggest it rarely happens with random costs.

Future research directions suggested by the work include:

  • Probabilistic Analysis: Quantifying the probability that a random cost matrix will trigger a non-monotone path.
  • Combinatorics: Further exploring the "centeredness" of faces in other famous polytopes used in optimization.
  • Algorithmic Implications: Determining if the rare cases of non-monotonicity significantly impact the stability or convergence of active-set methods used to solve regularized OT.

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},
}

Loading related content...

Figure