CS Paper Radar

Correcting CondOT: Exact Finite-Step Sampling in Gaussian Flow Matching

Ron Levy, Michael Elad

cs.LG ·submitted 2026-09-30 10:50 UTC · v1
hot direction

Abstract

Flow matching generates samples by gradually transforming noise into data. In practice, using a finite number of sampling steps introduces a numerical error that depends on the chosen schedule. We study this dependence for Gaussian targets and the explicit midpoint sampling method, using the exact flow field. We measure sampling error by the squared Wasserstein distance between the target distribution and the final distribution produced by the midpoint sampler. We show that the standard conditional optimal transport (CondOT) schedule cancels the leading midpoint error and improves the general convergence bound, even when the sampling steps are unequally spaced. On a uniform grid of $S$ sampling steps, we fix the signal schedule at $α_t=t$ and prove the existence of scalar noise schedules $β_t$ that approach the CondOT noise schedule $1-t$ at rate $1/S$ and yield exact Gaussian sampling for every sufficiently large $S$. Controlled Gaussian experiments illustrate the convergence rates and exact calibration.

Comment
38 pages, 5 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Flow Matching under Noisy Latent Structure: Beyond Exact Low-Dimensional Support

cs.LG stat.ML ·2026-09-30 ·Lifeng Hao, Shaolin Ji
hot direction similarity 0.67
Abstract · 66 pages, 0 figures

Flow Matching (FM) learns a velocity field whose ODE transports a simple source distribution to a target law. Existing finite-sample theory largely treats ambient-space regularity or data supported exactly on low-dimensional sets. We study linear FM under a noisy latent-generator model, where a low-dimensional Hölder map is perturbed by nondegenerate ambient Gaussian noise, so the target law is full-dimensional despite its latent structure. We construct a spatially regular ReLU velocity class and establish non-asymptotic high-probability approximation and estimation bounds whose leading sample-size exponent is governed by the latent dimension rather than the ambient dimension, with ambient and noise dependence kept explicit. Fixed positive target noise keeps the interpolation nondegenerate over the full time interval. The same spatial regularity propagates the learned velocity error through the transport ODE, yielding a corresponding Wasserstein convergence guarantee. These results show that exact low-dimensional support is not necessary for Flow Matching to retain latent-dimensional statistical behavior.

0.40

Gaussian Flow-Matching Schedules: Implications for Sampling and Training

cs.LG ·2026-09-22 ·Arsène Claustre, Hugo Negrel, Claire Boyer, Kimia Nadjahi, Eric Vanden-Eijnden
similarity 0.66
Abstract

Flow-matching schedules affect both sampling dynamics and the variance of the regression target. For centered commuting Gaussians, we show that a direction-dependent schedule decomposes into two independent design choices: a variance path, which fully determines the intermediate laws and probability flow, and a factorization, which leaves this flow unchanged while controlling irreducible regression variance. On the sampling side, we analyze finite-step Euler accuracy and derive a necessary drift bound for exact N -step sampling, connecting the geodesic and the logarithmic path. On the training side, for any fixed path, we derive closed-form factorizations that either minimize time-averaged regression variance or make it constant along the path.

0.46

Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

cs.LG stat.ML ·2026-10-14 ·Haowei Wang, Yilin Zheng
theoryhot direction similarity 0.62
Abstract

Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Matérn kernels with smoothness parameter $ν$ in dimension $d$, we establish a worst-case expected simple-regret upper bound of $O(N^{-ν/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $Ω(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Matérn-$5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $Θ(N^{-ν/d})$ for both discrete and continuous implementations.

0.28

Computing All Optimal Partial $p$-Wasserstein Matchings on the Line

cs.CG cs.DS ·2026-08-19 ·Sebastian Angrick, Jacobus Conradi, Mónika Csikós, Niko Hastrich, Danny Mittal +3 more
theorycode/data similarity 0.62
Abstract

For $p \ge 1$, the $p$-Wasserstein distance measures the minimum cost of transporting probability mass between distributions, where moving unit mass between two points costs the $p$th power of their distance. For discrete distributions in one dimension, full transport is especially simple: after sorting, mass is matched in order along the line. By contrast, partial and unbalanced transport on the line remains much less understood. Recently, Chapel and Tavenard [ICLR'25] showed that, for $p=1$, all optimal partial transport plans between distributions supported on $n$ points, with uniform mass at each point, can be computed in $O(n\log n)$ time by exploiting the metric structure of the cost. For $p>1$, this structure no longer applies, and existing approaches require $Ω(n^2)$ time. Our main contribution is an FFT-based data structure for balanced-interval transport queries, which bypasses this quadratic bottleneck and yields an $O(p\,n\log^2 n)$-time algorithm for computing all optimal partial transports on the line for every finite $p\ge 1$. We also provide an open-source C++ implementation that outperforms the state-of-the-art baseline on a range of synthetic instances. Finally, we establish a conditional lower bound for $p=\infty$: any subquadratic-time algorithm for computing all optimal partial transport plan costs on the line would violate the $(\min,+)$-Convolution Hypothesis. This separates the problem from full optimal transport, which is solvable in $O(n\log n)$.

0.25

Direct Intermediate Initialization for Tilted Diffusion Samplers

cs.LG stat.ML ·2026-10-05 ·Gregory D. Bellchambers
publishedbenchmark similarity 0.62
Abstract · Accepted at the NeurIPS 2026 Workshop on AI for Stochastic Dynamics (STODY)

Some diffusion posterior samplers construct Gaussian-tilted intermediate distributions along the reverse process. We observe that these targets can be pulled back to clean-space posteriors with weaker conditioning, with samples transported analytically to the corresponding noisy-space target through a Gaussian bridge. For the sequential Monte Carlo (SMC) sampler MCGDiff, the effective observation variance of this pulled-back problem is up to twice the diffusion-noise variance. We exploit this structure to initialize MCGDiff directly at an intermediate time: an approximate solver samples the softened clean-space posterior, the Gaussian bridge maps these samples to the tilted target, and only the remaining SMC suffix is run. This trades asymptotic consistency for finite-particle performance. With moment-matching posterior sampling (MMPS) as the solver, the hybrid improves sliced Wasserstein distance by roughly $2\times$ at matched particle count on a structured Gaussian-mixture inverse problem, and by more than an order of magnitude when the posterior-relevant mode is rare under the prior. A prior-initialization control, which retains the bridge but drops the clean-space conditioning, shows that on MCGDiff's standard Gaussian-mixture benchmark most of the improvement is insensitive to the conditioning. Conditioning the initialization gives a further consistent gain on the structured problem, and becomes decisive on a rare-mode problem, where resampling cannot repopulate a mode absent from the initial population.

0.35

Elliptic Sampling: Optimal Interpolant Schedules for Gaussians and Beyond

cs.AI stat.MLcs.LG ·2026-11-13 ·Cole Becker, Taylan Kargin, Kimia Hassibi, Asuman Ozdaglar, Pablo A. Parrilo
similarity 0.61
Abstract

Generative modeling based on stochastic interpolants requires specifying two key choices: an interpolant schedule bridging the initial and target distributions, and an efficient discretization of the resulting probability-flow ODE. In this work, we introduce a new framework for joint schedule/discretization design based on the analyticity properties of the (complexified) ODE trajectories, which in turn ensure good numerical behavior. Our formulation can be solved exactly via conformal mapping, yielding a natural family of variance-preserving elliptic schedules, parametrized by Jacobi elliptic functions. Pairing an elliptic schedule with a tailored discretization, we obtain Zoloflow, a new sampling algorithm closely connected to Zolotarev's optimal rational function approximants. Crucially, both the elliptic schedule and Zoloflow explicitly incorporate the condition number $κ$ of the target distribution and reduce to the classical trig schedule in the limit $κ\rightarrow 1$. For Gaussian targets, Zoloflow achieves minimax optimality among all oblivious score-span algorithms, attaining total-variation error $\varepsilon$ using $Θ(\logκ\,\log(\sqrt d/\varepsilon))$ (exact) score queries. For the log-concave case, the elliptic schedule allows sampling with at most $\varepsilon$ 2-Wasserstein-error by requiring merely $\widetilde{O}(\sqrt{d} \, \mathrm{polylog}(κ, 1/\varepsilon))$ score evaluations. Complementing these theoretical results, we empirically evaluate the elliptic schedule on general (non-log-concave) target distributions, including detailed comparisons with alternative schedule proposals on both synthetic benchmarks and existing image generation datasets.

0.31

Fast and Scalable Multi-Agent Distribution Matching via Partitioned Optimal Transport

cs.MA cs.ROeess.SYmath.OC ·2026-09-30 ·Kooktae Lee, Ruchika Singh
theory similarity 0.61
Abstract

This paper presents a scalable optimal-transport-based framework for terminal distribution matching in multi-agent systems. While optimal transport provides a natural way to measure distributional mismatch and assign agents to a desired spatial distribution, global discrete transport can become computationally expensive for large-scale systems. We address this bottleneck by partitioning agents and target samples into spatially corresponding blocks and solving smaller local transport problems. Under a mass-balance condition, the resulting restricted coupling remains feasible for the global problem and provides an upper bound on the Wasserstein cost. The local assignments generate target locations for finite-horizon agent control, applicable to both linear and nonlinear dynamics. By alternating local assignment and control, we establish a cycle-to-cycle descent guarantee for the resulting transport surrogate. The proposed framework therefore enables scalable terminal distribution matching while retaining a rigorous connection to the Wasserstein objective. The technical soundness of the proposed results is validated through simulations.

0.27

What Does a Stream Model Buy You in Flow Matching?

cs.LG ·2026-09-28 ·Jian Xu
benchmark similarity 0.60
Abstract

Stream-level flow matching replaces the linear interpolant of conditional flow matching (CFM) by a Gaussian-process (GP) stream connecting each source--target pair, and reports lower sample error than \icfm{} on 2-Gaussian, MNIST and CIFAR-10 benchmarks. We ask what such a stream model actually contributes. Three results answer the question. (i)~\emph{Reduction.} The stream-level CFM objective depends on the stream law only through the per-time joint law of $(s_t,\sdot_t)$, so the conditional paths a Gaussian stream can reach are exactly the Gaussian conditional paths CFM already parametrises; in the coordinate-wise, shared-scalar-kernel construction gpcfm actually uses, the entire design space collapses to two scalar curves $(m_t,v_t)$, and cross-time covariance affects only estimator variance. (ii)~\emph{The GP is a constrained chart of that space.} One kernel sets both $m_t$ and $v_t$, so the paper's own recipe for widening coverage-shrinking the SE length-scale---destroys the interpolant (the midpoint mean weight falls from $1.03$ to $0.00$). On the 2-Gaussian benchmark this makes the GP chart diverge on $15/200$ runs at high coverage against $0/200$ for a decoupled $(m_t,v_t)$ chart ($p=6.6\times10^{-5}$), and crossing the two curves shows the divergence tracks the mean, not the variance. On MNIST the same sweep does not diverge and the ordering reverses, so whether the coupling is harmful is benchmark-dependent; what holds on both is that the recipe buys nothing---no coverage level beats the paper's own, and past $\max_t\sqrt{v_t}\approx0.6$ both charts degrade. (iii)~\emph{Audit.} The released code does not implement the mechanism it describes: state and velocity are drawn independently ($\mathrm{corr}=0.00\pm0.01$ against an intended $\pm0.83$--$0.99$).

0.24