TL;DR
The Sliced Wasserstein Distance (SWD) enables fast optimal transport by projecting high-dimensional data onto random 1D lines, but Monte Carlo sampling of these directions introduces severe gradient variance. Inspired by the ReSTIR algorithm from real-time graphics rendering, Reservoir SWD (ReSWD) uses Weighted Reservoir Sampling to retain and reweight the most informative projection directions across optimization steps. This drastically stabilizes gradient updates while preserving unbiasedness, yielding faster convergence and cleaner results in distribution matching, color grading, and diffusion model guidance.
What Problem Does This Paper Address?
Aligning two probability distributions is a core objective across computer vision and graphics—underpinning tasks from color grading and texture synthesis to guided diffusion generation. While the classic Wasserstein distance captures distribution shifts cleanly, computing it directly in high dimensions suffers from combinatorial complexity ($O(n \log n)$ in 1D, but cubic in general high-dimensional settings).
The popular workaround, Sliced Wasserstein Distance (SWD), projects distributions onto random 1D directions where sorting solves the transport problem efficiently. However, SWD relies on Monte Carlo (MC) sampling of these random directions. In optimization settings, this introduces heavy stochastic variance: noisy gradients, wandering trajectories, and slow convergence. Previous solutions either select only the single maximal direction (like Max-SW, sacrificing unbiasedness and global distributional shape) or use quasi-Monte Carlo sampling without reusing information between consecutive optimization steps.
Methods
ReSWD borrows the core philosophy of ReSTIR (Reservoir-based Spatio-Temporal Importance Resampling from real-time path tracing): reuse samples over time, but weight them properly so the estimate stays unbiased.
Step t-1 Reservoir (K directions) ──> Time Decay ──┐
├──> Combine & Resample (K largest keys) ──> Weighted SWD Loss
Fresh Candidates (M directions) ───────────────────┘
The algorithm operates in four main steps at each optimization iteration:
-
Time-Decay Reweighting: Because the target distributions shift as optimization proceeds, stored directions in the reservoir age exponentially: $$\tilde{w}_i \leftarrow w_i \exp(-(t - t_i)/\tau)$$ This gradually phases out stale projections.
-
Candidate Generation & Weighted Reservoir Sampling (WRS): A pool $P_t$ is formed by merging $K$ directions from the previous reservoir with $M$ newly drawn random directions ($N_t$). Each direction is evaluated for its 1D Wasserstein distance $D(\theta)$. Using Efraimidis-Spirakis reservoir sampling, random keys $k_j = u_j^{1/D(\theta_j)}$ are generated, retaining the $K$ directions with the largest keys. This biases selection toward projections with higher loss contributions.
-
Self-Normalized Importance Weighting: Survivors are assigned weights: $$w_i = \frac{1/q(\theta_i)}{\sum_j 1/q(\theta_j)}$$ The weights are detached from backpropagation, providing an unbiased Monte Carlo estimate while focusing gradient computation where distribution discrepancies are largest.
-
Effective Sample Size (ESS) Reset: If weight variance collapses ($ESS < \alpha K$), the reservoir is flushed to prevent degenerate sampling.
The authors apply ReSWD to:
- Differentiable Color Correction: Optimizing an ASC Color Decision List (CDL) parameterization (slope, offset, power, saturation) in the CIELAB color space.
- Diffusion Guidance: Applying SWD color guidance on Stable Diffusion (SDXL and SD3.5). Crucially, they stop gradients after the backbone transformer and backpropagate only through the VAE decoder using an Adam optimizer, dramatically reducing memory and latency.
Datasets
- Synthetic Distribution Matching: 1,000 synthetic 3D distribution pairs (combinations of Gaussian, uniform, and bimodal Gaussian distributions) with 1,024 samples per distribution.
- Real-World Color Matching Dataset: A custom dataset created by the authors consisting of 10 real-world scenes captured under two distinct illumination conditions, each accompanied by Macbeth color calibration checker charts for quantitative evaluation.
- Color Diffusion Guidance Benchmark: Following prior work, evaluations were conducted using 1,000 prompts from the ContraStyles dataset paired with 1,000 reference images drawn from Unsplash Lite.
Key Insights and Ideas
- Cross-pollination between rendering and optimal transport: Both ray tracing and sliced optimal transport depend on Monte Carlo integration. Applying streaming importance resampling (WRS) provides temporal sample reuse without the memory explosion of storing large batches of historical directions.
- Unbiased focus vs. Greedy selection: While Max-SW only optimizes the single worst projection (often getting stuck or distorting other dimensions), ReSWD maintains an ensemble of high-error projections while mathematically correcting for sampling bias via importance weights.
- The "Warmup" Dynamic: During the initial steps, ReSWD shows slightly slower convergence as the reservoir populates. However, once established (around step 140 in synthetic tests), its gradient Signal-to-Noise Ratio (SNR) surpasses vanilla SWD, converging to lower final error.
- Decoder-only diffusion guidance: Bypassing full backpropagation through heavy diffusion transformer backbones and restricting gradient flow to the VAE decoder preserves color guidance fidelity while cutting runtime by over 70%.
Key Results
- Synthetic 3D Matching: ReSWD achieved a Mean-$W_1$ error of $0.622 \times 10^{-3}$ (and $0.610 \times 10^{-3}$ when combined with Quasi-Monte Carlo), outperforming standard SWD ($0.733 \times 10^{-3}$) and prior variance-reduction methods (e.g., QMC alone at $0.670 \times 10^{-3}$). Gradient SNR improved from 0.215 to 0.278.
- Ablation on Candidates: With a total budget of 64 directions, retaining 56 in the reservoir and introducing $M=8$ fresh candidates per step yielded the lowest error ($0.622 \times 10^{-3}$).
- Color Correction: ReSWD achieved the best Color PSNR (24.64 dB) and lowest transform RMSE (0.31) in 5 seconds per match, beating classical methods (Reinhard et al.: 21.94 dB) and neural alternatives (Yoo et al.: 20.97 dB in 20s; Larchenko et al.: 14.80 dB in 24s).
- Diffusion Guidance:
- On SDXL, ReSWD reduced Wasserstein generation error (Mean-$W_2$) from 1.941 (Lobashev et al.) to 1.213, while slashing generation time from 124 seconds to 34 seconds.
- On SD3.5-Turbo, generation ran in just 4 seconds per image, achieving a Mean-$W_2$ of 0.675 and high visual quality (CLIP-IQA: 0.800).
Limitations and Future Work
- The Curse of Dimensionality in Direction Space: While ReSWD excels in lower-dimensional feature spaces ($d \le 6$), its performance degrades significantly as dimensionality scales ($d \ge 12$, reaching an error of 21.446 at $d=64$). In high-dimensional spaces, uniformly drawing informative candidate directions becomes an "infinitesimal needle in a haystack," leading to reservoir stagnation and stale directions.
- Restriction to Matrix Projections: The method currently applies to simple linear projections. Extending reservoir sampling to complex, learned convolutional projection filters (as used in patch-matching GANs) failed because the random filter search space is far too large for naive candidate generation.
- Future Directions: Incorporating adaptive or learned proposals for new candidate directions (rather than purely uniform spherical sampling) could alleviate stale reservoirs in higher dimensions.
Summary updated