Negatively Dependent Subsampling for Stochastic Mirror-Descent Optimal Transport

Optimal transport finds the cheapest way to move one distribution of points onto another. It underlies domain adaptation, color transfer and the pairing step of flow-based generative models, but exact solvers need memory quadratic in the number of points. Practitioners therefore estimate the expensive sums inside the solver from random subsamples, and those subsamples are almost always drawn independently. Independent samples clump: they over-represent some regions and miss others. The resulting estimates are noisy, and points get forced to match targets that are absent from the batch.

This note proposes a different subsampler. Draw subsamples whose members repel each other in a cheap, provable way, using stratified sampling without replacement over a fixed clustering of the data. Then analyze the solver as primal mirror descent, meaning gradient steps taken in a curved geometry suited to probability distributions. Under that view, Sinkhorn's matrix-scaling algorithm becomes a sequence of multiplicative updates. The core claim is simple. In this solver, every noisy quantity is a plain weighted sum over sampled source points, so classical negative-dependence tail bounds apply to it directly. A negatively dependent sampler then shrinks the error of each mirror step by a factor set by within-cluster spread rather than total spread. Most of this structure has been proved and never tested. The project builds the stochastic solver, proves the inexact-step bound, and then does what the underlying theory papers did not: measures whether the predicted constants and rates hold on real benchmarks.

Where the pieces stand

Three lines of work meet here, each missing something the others supply.

The first line supplies the optimization method. Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM shows that Sinkhorn on entropic optimal transport is primal mirror descent with a fixed step. Its rates are $O(1/n)$ in general and linear when costs are bounded. The paper is deterministic and contains no experiments, and it names discretization to empirical measures as unresolved. Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective derives the Φ-match family from the semi-dual formulation, including momentum variants. It too lists empirical evaluation against strong solvers as future work. These two papers provide the update rule we make stochastic, and they are the clearest instances of the validation gap we address.

The second line supplies the concentration tool. Balls and Bins: A Study in Negative Dependence and Simple Proofs of Occupancy Tail Bounds show that negatively associated variables have moment-generating functions dominated by the independent product. Chernoff–Hoeffding bounds therefore carry over unchanged, and sampling without replacement is a standard negatively associated example. Small coresets via negative dependence: DPPs, linear statistics, and concentration shows that repulsive sampling with determinantal point processes beats the $\epsilon^{-2}$ independent barrier for linear statistics. It also constrains us in two ways. The advantage decays like $1/d$ in dimension $d$, and exact sampling costs $O(nm^2)$. Our design must take both seriously rather than assume a free lunch in high dimensions.

The third line motivates the problem. Minibatch optimal transport distances; analysis and applications analyzes independent minibatch OT as U- and V-statistics and introduces a debiased loss, but it never uses explicit negative dependence. Improving Mini-batch Optimal Transport via Partial Transportation attributes minibatch OT's failures to "misspecified mappings" from independent batches. Its authors write that exploring the dependence structure between batches is an open direction. Active Mini-Batch Sampling Using Repulsive Point Processes is the closest methodological neighbor. It shows that repulsion adds a negative covariance term that lowers SGD gradient variance, with Poisson disk sampling at roughly 0.16 s per batch against roughly 189 s for a determinantal process. Its setting is Euclidean SGD for classification, its argument is heuristic and pairwise, and it does not touch transport plans or mirror geometry.

Core Claim

Take source points $x_i$ with weights $a_i$ and target points $y_j$ with weights $b_j$, cost $c_{ij}$, entropic temperature $\varepsilon$, and target-side dual potential $g$. The semi-dual mirror step needs the target marginal of the current plan. That marginal is a sum over all source points:

$$q_j(g) = \sum_{i=1}^{n} a_i\, s_{ij}(g), \qquad s_{ij}(g) = \frac{\exp((g_j - c_{ij})/\varepsilon)}{\sum_{k} \exp((g_k - c_{ik})/\varepsilon)}.$$

Here $s_{ij}$ is the fraction of point $i$'s mass that the current plan sends to target $j$. We replace $q_j$ with an inverse-probability-weighted estimate built from a source subsample $S$, drawn with inclusion probabilities $p_i$:

$$\hat q_j = \sum_{i \in S} \frac{a_i}{p_i}\, s_{ij}(g).$$

We then apply the multiplicative mirror update $g_j \leftarrow g_j + \eta\,\varepsilon\,(\log b_j - \log \hat q_j)$, where $\eta$ is the step size. Each step costs $O(|S|\,n_{\text{target}})$ memory instead of $O(n\,n_{\text{target}})$. The target side can be subsampled symmetrically for the source potential.

The point of the construction is that $\hat q_j$ is a linear statistic of the inclusion indicators. When $S$ is drawn by stratified sampling without replacement over $K$ clusters, the indicators are negatively associated. The MGF domination then gives a Chernoff tail for every coordinate. The variance is governed by the spread of $s_{ij}$ within each cluster, not across the whole dataset. Since $s_{ij}$ is Lipschitz in $x_i$ with constant of order $1/\varepsilon$ times the cost's Lipschitz constant, within-cluster spread shrinks with cluster radius. For data of intrinsic dimension $d_{\text{int}}$, that radius scales like $K^{-1/d_{\text{int}}}$.

This prediction is falsifiable and agrees with the $1/d$ decay found by Bardenet et al. The advantage should be large on low-intrinsic-dimension data such as images, color point clouds and PCA features. It should vanish on isotropic high-dimensional Gaussians. We combine the tail bound with an inexact-step version of the relative-smoothness analysis, treating estimation error as an additive perturbation of the Bregman descent inequality. The result is a bound on accumulated marginal KL error, which separates the deterministic $O(1/T)$ term from a sampling term proportional to within-stratum variance.

Research Program

The work has three parts, run in order.

The first part is the algorithm. We implement stochastic semi-dual mirror descent with four subsamplers that differ only in how $S$ is drawn: uniform independent, uniform without replacement, stratified-NA, and Poisson disk sampling. A fifth variant samples from a determinantal point process and is used only at small $n$ as an upper reference. Clusters come from a single mini-batch k-means pass over each side, an $O(nK)$ preprocessing cost that is reported in all wall-clock figures.

The second part is the theory: the coordinatewise NA tail bound for $\hat q$ and the inexact relative-smoothness bound. We state explicitly where bounded costs are needed, so that the linear-rate claim covers only bounded-cost settings.

The third part is the validation study, which is half the contribution. For each theorem we compute the quantity it predicts and compare it with the observed value. The theorem constants include the relative smoothness constant after discretization, the per-step deviation of $\hat q$ against its NA tail bound, and the predicted contraction rate against the measured one. Squared Euclidean cost on Gaussians gives an unbounded-cost regime, where the theory predicts only sublinear rates.

Baselines

The naive reference point is uniform independent subsampling at the same subsample size, step size and number of steps. This is what minibatch practice does by default. Beating it means lower marginal KL error and lower primal suboptimality at matched wall-clock time, including clustering cost, on a majority of DOTmark problem classes.

The strongest full-batch competitor is MDOT with preconditioned nonlinear conjugate gradients from Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients. That paper reports empirical complexity between $O(n^2)$ and $O(n^{5/2})$ and up to a 10x speedup from Taylor warm-starts on DOTmark and color transfer up to $n = 16{,}384$. No absolute per-instance runtime is reported on Lacuna for DOTmark, so we rerun their method on the same GPU. We do not expect to beat it at moderate $n$ when high precision is required. We count a win if our method reaches moderate precision (marginal error 1e-3) faster above some crossover $n$, and if it runs where MDOT-PNCG runs out of memory. The crossover point is reported honestly.

For downstream learning, the strongest baselines are debiased minibatch Sinkhorn and partial minibatch OT. Minibatch optimal transport distances; analysis and applications reports an Inception Score of 4.76 on CIFAR-10 for the debiased loss, against 3.61 for biased minibatch OT. Improving Mini-batch Optimal Transport via Partial Transportation reports accuracy gains of 5.28% on Digits, 5.75% on Office-Home and 11.17% on VisDA-2017 over standard minibatch OT. We rerun both with identical architectures, training budgets and a shared grid over the mass fraction $s$. Beating them means a gain from swapping only the batch sampler, both alone and combined with the partial transport, at equal training compute.

The key ablation isolates negative dependence from coverage. Stratified-NA is compared against stratified sampling with replacement, which keeps the same strata and allocation but removes the without-replacement repulsion. A second comparison against Poisson disk sampling, which is repulsive but has no NA guarantee, tests whether the formal structure matters beyond heuristic spreading.

Why not just…?

Why not just use larger uniform batches? At fixed memory this is impossible: batch size is exactly the budget being saved. At fixed wall-clock time, the comparison is built into every plot, because each method gets the same compute. If uniform sampling with more steps matches stratified-NA at equal time, the claim fails on that problem class, and we will report it.

Why not just add a control variate, as in variance-reduced SGD? This is a real threat. Control variates also cut the variance of linear statistics such as $\hat q_j$, and they need no clustering. We will implement an SVRG-style anchor that recomputes the full marginal periodically and corrects stochastic estimates against it. We compare it with stratified-NA and with the combination of both. Our expectation is that the two methods are complementary rather than competing. The control variate removes slowly drifting error, while stratification removes per-step clumping, so we predict the combination wins. If the control variate alone dominates, the negative-dependence contribution reduces to the theory and validation study, and we will say so.

Why not just use a determinantal point process for maximal repulsion? Per Active Mini-Batch Sampling Using Repulsive Point Processes, exact determinantal sampling took about 189 s for a batch of 150. That cost is incompatible with drawing a fresh sample at every mirror step. Small coresets via negative dependence: DPPs, linear statistics, and concentration also shows its advantage fades as $1/d$. We keep it only at small $n$, to measure how much variance reduction stratification leaves unclaimed.

Why not just truncate mass with partial OT instead of fixing the sampler? Partial transport discards the symptom of misspecified matches but does not address the cause. Its authors identify independent batching itself as the limitation. Because the two methods act at different stages, we test them as additive and report whether sampler gains survive once partial transport is applied.

Proposed Experiments

The solver experiments run on DOTmark under $L_1$ and squared $L_2$ costs. Upsampled MNIST and DALL-E 2 color point clouds follow the protocol of Efficient and Accurate Optimal Transport with Mirror Descent and Conjugate Gradients. We then extend to megapixel color transfer as in Minibatch optimal transport distances; analysis and applications, beyond the full-batch memory limit. Exact linear-programming solutions on small instances serve as ground truth. Metrics are marginal KL error and primal suboptimality against wall-clock time. We also record the per-step empirical deviation of $\hat q$ against the NA tail bound.

The downstream experiments swap the batch sampler in two settings. The first is domain adaptation on Digits, Office-Home and VisDA-2017. The second is minibatch-OT pairing for flow matching using TorchCFM, the code accompanying Improving and generalizing flow-based generative models with minibatch optimal transport, on CIFAR-10. Metrics are target accuracy and FID.

Three checks are decisive. First, on synthetic Gaussians with ambient dimension 2 to 256 and controlled intrinsic dimension, the stratified advantage should track $K^{-1/d_{\text{int}}}$ and vanish at high intrinsic dimension. If it persists there, or fails at low dimension, the mechanism is wrong. Second, the observed deviations must stay within the NA tail bound, and the measured relative smoothness constants after discretization must be reported, closing the empirical gap left by the two theory papers. Third, under unbounded squared Euclidean cost, the observed rate should drop from linear to sublinear as the theory predicts. If it stays linear, the bounded-cost assumption is looser than claimed, which is itself a useful finding.