Monotonicity in Quadratically Regularized Linear Programs

This study is motivated by optimal transport and related minimization problems over probability measures. In its simplest form, the transport problem between probability measures $\mu$ and $\nu$ is

where $\hat{c}(x,y)$ is a given “cost” function and $\Gamma(\mu,\nu)$ denotes the set of couplings; i.e., joint probability measures $\gamma$ with marginals $(\mu,\nu)$. See [34] for a detailed discussion. In many applications such as machine learning or statistics (see [24, 31] for surveys), the marginals encode observed data points ${X_{1},\dots,X_{N}}$ and ${Y_{1},\dots,Y_{N}}$ which are represented by their empirical measures $\mu=\frac{1}{N}\sum_{i}\delta_{X_{i}}$ and $\nu=\frac{1}{N}\sum_{i}\delta_{Y_{i}}$. Denoting by $c_{ij}=\hat{c}(X_{i},Y_{j})$ the resulting $N\times N$ cost matrix, (OT) then becomes a linear program

where the polytope $\mathcal{P}$ is (up to a constant factor) the Birkhoff polytope of doubly stochastic matrices of size $N\times N$. For different choices of polytope, (LP) includes other problems of recent interest, such as multi-marginal optimal transport and Wasserstein barycenters [2] or adapted Wasserstein distances [3]. The optimal transport problem is computationally costly when $N$ is large. The impactful paper [13] proposed to regularize (OT) by penalizing with Kullback–Leibler divergence (entropy). Then, solutions can be computed using the Sinkhorn–Knopp algorithm, which has lead to an explosion of high-dimensional applications (see [32]). More generally, [14] introduced regularized optimal transport with regularization by a divergence. Different divergences give rise to different properties of the solution. Entropic regularization always leads to couplings whose support contains all data pairs $(X_{i},Y_{j})$, even though (OT) typically has a sparse solution. In some applications that is undesirable; for instance, it may correspond to blurrier images in an image processing task [6]. The second-most prominent regularization is $\chi^{2}$-divergence or equivalently the squared norm, as proposed in [6],¹¹1See also [17] for a similar formulation of minimum-cost flow problems, and the predecessors referenced therein. Our model with a general polytope includes such problems, and many others. which gives rise to sparse solutions. In the Eulerian formulation of [14], this is exactly our problem (1) with $\mathcal{P}$ being the (scaled) Birkhoff polytope. Alternately, the problem can be stated in Lagrangian form as in [6], making the squared-norm penalty explicit:

where $d\gamma/d(\mu\otimes\nu)$ denotes the density of $\gamma$ wrt. the product measure $\mu\otimes\nu$ and the regularization strength is now parameterized by $\eta\in[0,\infty]$. In the general setting, this corresponds to

which has a unique solution $x_{\eta}$ for any $\eta\in[0,\infty]$. The curves $(x^{\eta})$ and $(x_{\eta})$ of solutions to (1) and (2), respectively, coincide up to a simple reparametrization.

In optimal transport, the regularized problem is often solved to approximate the linear problem (OT). The latter has a generically unique (see [12]) solution $x$, which is recovered as $\delta\to\delta_{\max}$ (or $\eta\to\infty$): $x=x^{\delta_{\max}}=x_{\infty}$.²²2For problems with non-unique solution, $x^{\delta_{\max}}$ recovers the minimum-norm solution. In particular, the support of $x^{\delta}$ converges to the support of $x$, which is generically sparse ($N$ out of $N^{2}$ possible points, again by [12]). In numerous experiments, it has been observed not only that $\operatorname*{spt}x^{\delta}$ is sparse when $\delta$ is large, but also that $\operatorname*{spt}x^{\delta}$ monotonically decreases to $\operatorname*{spt}x$ (e.g., [6]). If this monotonicity holds, then in particular $\operatorname*{spt}x\subset\operatorname*{spt}x^{\delta}$, meaning that $\operatorname*{spt}x^{\delta}$ can be used as a multivariate confidence band for the (unknown) solution $x$.

When $\mathcal{P}$ is a set of measures, the support of $x\in\mathcal{P}$ can be defined as usual. When $\mathcal{P}$ is a general polytope, the set of vertices of the minimal face containing $x$ yields a similar notion. With that in mind, we can ask whether the support of $x^{\delta}$ is monotone wrt. the strength $\delta$ of regularization. (The two notions of support yield the same result when $\mathcal{P}$ is the simplex or the Birkhoff polytope; cf. Lemma 4.2.) Geometrically, this corresponds to the aforementioned invariance property: if $x^{\delta}\in F$ for some face $F$, does it follow that $x^{\delta^{\prime}}\in F$ for all $\delta^{\prime}\geq\delta$? The answer may of course depend on the cost $c$; we call $\mathcal{P}$ monotone if the invariance holds for any $c\in\mathbb{R}^{d}$.

We show that monotonicity can be characterized by the geometry of $\mathcal{P}$. Namely, monotonicity of $\mathcal{P}$ is equivalent to two properties: for any proper face $F$, the minimum-norm point of the affine hull of $F$ must lie in $F$, and moreover, the minimum-norm point of $\mathcal{P}$ must lie in the relative interior $\operatorname*{ri}\mathcal{P}$. See Theorem 3.2. Once the right point of view is taken, the proof is quite elementary. An example satisfying both properties, and hence monotonicity, is the unit simplex $\Delta\subset\mathbb{R}^{d}$, for any $d\geq 1$. For that choice of polytope, $x^{\delta}$ is a sparse soft-min of $c=(c_{1},\dots,c_{d})$, converging to $1_{\{\operatorname*{argmin}c\}}$ in the unregularized limit. On the other hand, we show that the Birkhoff polytope violates the first condition whenever the marginals have $N\geq 5$ data points (meaning that $d\geq 25$). As a result, the optimal support in quadratically regularized optimal transport problems is not always monotone, even if it appears so in numerous experiments. In fact, we exhibit a particularly egregious failure of monotonicity where the support of the limiting (unregularized) optimal transport $x$ is not contained in $\operatorname*{spt}x^{\delta}$ for some reasonably large $\delta$. Our counterexample is constructed by hand, based on theoretical considerations. Our numerical experiments using random cost matrices have failed to locate counterexamples, suggesting that there are, in some sense, “few” faces violating our condition on the minimum-norm point. (See also the proof of Lemma 4.10.) This is an interesting problem for further study in combinatorics, where the Birkhoff polytope has remained an active topic even after decades of research (e.g., [30] and the references therein).

The remainder of this note is organized as follows. Section 2 introduces the regularized linear program and its solution curve in detail. Section 3 contains the main abstract result, whereas Section 4 reports the applications to optimal transport and soft-min.

We first prove the “if” implication, using the Lagrangian formulation (Lemma 2.3). This parametrization is convenient because $\eta\mapsto x_{\eta}$ is piecewise affine. While the latter is well-known (even for some more general norms, see [18] and the references therein); we detail the statement for completeness.

Recall that $\operatorname*{rbd}K:=K\setminus\operatorname*{ri}K$ denotes the relative boundary of $K\subset\mathbb{R}^{d}$. Consider the first time the curve $\eta\mapsto x_{\eta}$ touches a given face $F$ of $\mathcal{P}$. That point may lie in $\operatorname*{ri}F$ or in $\operatorname*{rbd}F$. As seen in Lemma 3.5 below, the boundary situation indicates that $\eta\mapsto x_{\eta}$ left another face $F_{*}$ when it entered $F\not\subset F_{*}$, meaning that $\mathcal{P}$ is not monotone. Hence, we analyze that situation in detail in the next lemma.

To begin with a straightforward example, let $\mathcal{P}=\Delta$ be the unit simplex in Euclidean space $\mathbb{R}^{d}$ and $c=(c_{1},\dots,c_{d})\in\mathbb{R}^{d}$. Then

corresponds to finding the minimum value of $c$. More specifically, $x=(x_{1},\dots,x_{d})$ is a minimizer if and only if $x$ is supported in $\operatorname*{argmin}c$; i.e., $\operatorname*{spt}x=\{i:\,x_{i}\neq 0\}\subset\operatorname*{argmin}c$. When this linear program is regularized with the entropy of $x$, we obtain the usual soft-min (counterpart of log-sum-exp) which gives large weights to the small values of $c$ but non-zero weights to all values. The quadratic regularization,

yields a sparse soft-min: as $\delta\to\delta_{\max}$ (or as $\eta\to\infty$), the support of the solution tends to $\operatorname*{argmin}c$. In this example, $\delta_{\min}=1$ and $\delta_{\max}=(\#\operatorname*{argmin}c)^{-1}$.

We recall the quadratically regularized optimal transport problem

where $\Gamma(\mu,\nu)$ denotes the set of couplings of the probability measures $(\mu,\nu)$. We will be concerned with the discrete case as introduced in [6, 14, 17]. See also [26, 27, 29] for more general theory, [4, 16, 19] for asymptotic aspects, [15, 20, 22, 25, 33] for computational approaches and [25, 35] for some recent applications.

Fix $N\in\mathbb{N}$ and two sets of distinct points, $\{X_{1},\dots,X_{N}\}\subset\mathbb{R}^{D}$ and $\{Y_{1},\dots,Y_{N}\}\subset\mathbb{R}^{D}$. Let $\mu=\frac{1}{N}\sum_{i=1}^{N}\delta_{X_{i}}$ and $\nu=\frac{1}{N}\sum_{i=1}^{N}\delta_{Y_{i}}$ denote the associated empirical measures, and let $\hat{c}:\mathbb{R}^{D}\times\mathbb{R}^{D}\to\mathbb{R}$ be a (cost) function. We note that $\mu\otimes\nu=\frac{1}{N^{2}}\sum_{i,j=1}^{N}\delta_{(X_{i},Y_{j})}$ while $d\gamma/d(\mu\otimes\nu)$ is simply the ratio of the probability mass functions. Any coupling $\gamma\in\Gamma(\mu,\nu)$ can be identified with its matrix of probability weights

via $\gamma=\sum_{i,j=1}^{N}\gamma_{i,j}\delta_{(X_{i},Y_{j})}$. Writing similarly $c_{ij}=\hat{c}(X_{i},X_{j})$, (QOT) can be identified with the problem

Clearly $\Gamma_{N}=\frac{1}{N}\Pi_{N}$ where

denotes the Birkhoff polytope of doubly stochastic matrices; see, e.g., [9]. The monotonicity (in the sense of Definition 3.1) of $\Pi_{N}$ is equivalent to that of $\Gamma_{N}$.

The following result connects the measure-theoretic support $\operatorname*{spt}\pi=\{(i,j):\,\pi_{ij}>0\}$ with the geometric notion discussed below Definition 3.1.

As a consequence of Lemma 4.2, we have the following equivalence.