Flow Matching with Semidiscrete Couplings

• URL: http://arxiv.org/abs/2509.25519v1
• Date: Mon, 29 Sep 2025 21:22:35 GMT
• Title: Flow Matching with Semidiscrete Couplings
• Abstract summary: Flow models parameterized as time-dependent velocity fields can generate data from noise by integrating an ODE.<n>These models are often trained using flow matching, i.e. by sampling random pairs of noise and target points.<n>Although promising in theory, the OT flow matching (OT-FM) approach is not widely used in practice.
• Score: 29.980130720112726
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Flow models parameterized as time-dependent velocity fields can generate data from noise by integrating an ODE. These models are often trained using flow matching, i.e. by sampling random pairs of noise and target points $(\mathbf{x}_0,\mathbf{x}_1)$ and ensuring that the velocity field is aligned, on average, with $\mathbf{x}_1-\mathbf{x}_0$ when evaluated along a segment linking $\mathbf{x}_0$ to $\mathbf{x}_1$. While these pairs are sampled independently by default, they can also be selected more carefully by matching batches of $n$ noise to $n$ target points using an optimal transport (OT) solver. Although promising in theory, the OT flow matching (OT-FM) approach is not widely used in practice. Zhang et al. (2025) pointed out recently that OT-FM truly starts paying off when the batch size $n$ grows significantly, which only a multi-GPU implementation of the Sinkhorn algorithm can handle. Unfortunately, the costs of running Sinkhorn can quickly balloon, requiring $O(n^2/\varepsilon^2)$ operations for every $n$ pairs used to fit the velocity field, where $\varepsilon$ is a regularization parameter that should be typically small to yield better results. To fulfill the theoretical promises of OT-FM, we propose to move away from batch-OT and rely instead on a semidiscrete formulation that leverages the fact that the target dataset distribution is usually of finite size $N$. The SD-OT problem is solved by estimating a dual potential vector using SGD; using that vector, freshly sampled noise vectors at train time can then be matched with data points at the cost of a maximum inner product search (MIPS). Semidiscrete FM (SD-FM) removes the quadratic dependency on $n/\varepsilon$ that bottlenecks OT-FM. SD-FM beats both FM and OT-FM on all training metrics and inference budget constraints, across multiple datasets, on unconditional/conditional generation, or when using mean-flow models.

Related papers

• Same Flow, Different Paths: Variance Reduction in Flow Matching [67.12978375116599]
  We study the choice of this path from an optimization perspective.<n>Our main finding is that the choice of path $g_t$ can fundamentally change the convergence rate of SGD.
  arXiv  Detail & Related papers  (2026-09-15T15:01:04Z)
• Velocity Scheduled Flow Matching [0.0]
  Flow matching trains a neural network to regress the conditional velocity along a linear interpolant between noise and data.<n>We introduce Velocity Scheduled Flow Matching, which replaces the conditional target.<n>VSFM can be sampled under any admissible profile by integrating its ODE on a non-uniform profile.
  arXiv  Detail & Related papers  (2026-07-13T11:50:06Z)
• Regularized Random Fourier Features and Finite Element Reconstruction for Operator Learning in Sobolev Space [0.7734726150561088]
  Kernel-based operator learning can offer accurate, theoretically justified approximations that require less training than standard methods.<n>We propose a regularized random Fourier feature (RRFF) approach, coupled with a finite element reconstruction map (RRFF-FEM)<n>We show that RRFF and RRFF-FEM are robust to noise and achieve improved performance with reduced training time compared to the unregularized random feature model.
  arXiv  Detail & Related papers  (2025-12-19T18:36:24Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
  arXiv  Detail & Related papers  (2025-06-30T13:27:39Z)
• On Fitting Flow Models with Large Sinkhorn Couplings [21.33171004803672]
  Flow models transform data gradually from one modality (e.g. noise) onto another (e.g. images)<n>Recent works have proposed to sample mini-batches of $n$ source and $n$ target points and reorder them using an OT solver to form better pairs.<n>We show that flow models greatly benefit when fitted with large Sinkhorn couplings, with a low entropic regularization.
  arXiv  Detail & Related papers  (2025-06-05T19:19:01Z)
• Distilling Two-Timed Flow Models by Separately Matching Initial and Terminal Velocities [8.766883138603765]
  We present a new loss function for TTFM distillation called the emphinitial/terminal velocity matching (ITVM) loss.<n>Preliminary experiments show that our loss leads to better few-step generation performance on multiple types of datasets.
  arXiv  Detail & Related papers  (2025-05-02T10:17:49Z)
• Outsourced diffusion sampling: Efficient posterior inference in latent spaces of generative models [65.71506381302815]
  We propose amortize the cost of sampling from a posterior distribution of the form $p(mathbfxmidmathbfy) propto p_theta(mathbfx)$.<n>For many models and constraints, the posterior in noise space is smoother than in data space, making it more suitable for amortized inference.
  arXiv  Detail & Related papers  (2025-02-10T19:49:54Z)
• Inverse Entropic Optimal Transport Solves Semi-supervised Learning via Data Likelihood Maximization [72.69498649272347]
  conditional distributions is a central problem in machine learning.<n>We propose a new paradigm that integrates both paired and unpaired data.<n>We show that our approach can theoretically recover true conditional distributions with arbitrarily small error.
  arXiv  Detail & Related papers  (2024-10-03T16:12:59Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  This paper investigates group distributionally robust optimization (GDRO) with the goal of learning a model that performs well over $m$ different distributions. To reduce the number of samples in each round from $m$ to 1, we cast GDRO as a two-player game, where one player conducts and the other executes an online algorithm for non-oblivious multi-armed bandits. In the second scenario, we propose to optimize the average top-$k$ risk instead of the maximum risk, thereby mitigating the impact of distributions.
  arXiv  Detail & Related papers  (2023-02-18T09:24:15Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  We show a training algorithm for distributed computation workers with varying communication frequency. In this work, we obtain a tighter convergence rate of $mathcalO!!!(sigma2-2_avg!! . We also show that the heterogeneity term in rate is affected by the average delay within each worker.
  arXiv  Detail & Related papers  (2022-06-16T17:10:57Z)
• Multimeasurement Generative Models [7.502947376736449]
  We map the problem of sampling from an unknown distribution with density $p_X$ in $mathbbRd$ to the problem of learning and sampling $p_mathbfY$ in $mathbbRMd$ obtained by convolving $p_X$ with a fixed factorial kernel.
  arXiv  Detail & Related papers  (2021-12-18T02:11:36Z)
• Robust Model Selection and Nearly-Proper Learning for GMMs [26.388358539260473]
  In learning theory, a standard assumption is that the data is generated from a finite mixture model. But what happens when the number of components is not known in advance? We are able to approximately determine the minimum number of components needed to fit the distribution within a logarithmic factor.
  arXiv  Detail & Related papers  (2021-06-05T01:58:40Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y = langle X,w* rangle + epsilon$ We propose estimators for this problem under two settings: (i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance and (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  arXiv  Detail & Related papers  (2020-07-16T06:44:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.