Optimal Scheduling of Dynamic Transport

• URL: http://arxiv.org/abs/2504.14425v1
• Date: Sat, 19 Apr 2025 23:40:54 GMT
• Title: Optimal Scheduling of Dynamic Transport
• Authors: Panos Tsimpos, Zhi Ren, Jakob Zech, Youssef Marzouk,
• Abstract summary: We show that a specific class of trajectories can significantly improve approximation and learning.<n>For a broad class of source/target measures and transport maps $T$, the emphoptimal schedule can be computed in closed form.<n>Our proof technique relies on the calculus of variations and $Gamma$-convergence.
• Score: 1.4436965372953483
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Flow-based methods for sampling and generative modeling use continuous-time dynamical systems to represent a {transport map} that pushes forward a source measure to a target measure. The introduction of a time axis provides considerable design freedom, and a central question is how to exploit this freedom. Though many popular methods seek straight line (i.e., zero acceleration) trajectories, we show here that a specific class of ``curved'' trajectories can significantly improve approximation and learning. In particular, we consider the unit-time interpolation of any given transport map $T$ and seek the schedule $\tau: [0,1] \to [0,1]$ that minimizes the spatial Lipschitz constant of the corresponding velocity field over all times $t \in [0,1]$. This quantity is crucial as it allows for control of the approximation error when the velocity field is learned from data. We show that, for a broad class of source/target measures and transport maps $T$, the \emph{optimal schedule} can be computed in closed form, and that the resulting optimal Lipschitz constant is \emph{exponentially smaller} than that induced by an identity schedule (corresponding to, for instance, the Wasserstein geodesic). Our proof technique relies on the calculus of variations and $\Gamma$-convergence, allowing us to approximate the aforementioned degenerate objective by a family of smooth, tractable problems.

Related papers

• Distribution learning via neural differential equations: minimal energy regularization and approximation theory [1.5771347525430774]
  differential ordinary equations (ODEs) provide expressive representations of invertible transport maps that can be used to approximate complex probability distributions.<n>We show that for a large class of transport maps $T$, there exists a time-dependent ODE velocity field realizing a straight-line $(1-t)x + t(tTx)$, of the displacement induced by the map.<n>We show that such velocity fields are minimizers of a training objective containing a specific minimum-energy regularization.
  arXiv  Detail & Related papers  (2025-02-06T05:50:21Z)
• Displacement-Sparse Neural Optimal Transport [6.968698312185846]
  Optimal Transport (OT) theory seeks to determine the map $T:X to Y$ that transports a source measure $P to a target measure $Q$. We introduce a sparsity penalty into the minimax Wasserstein formulation, promote sparsity in displacement vectors $Delta(mathbfx) := T(mathbfx) := T(mathbfx) := T(mathbfx) := T(mathbfx) := T(mathbf
  arXiv  Detail & Related papers  (2025-02-03T23:44:17Z)
• Using Linearized Optimal Transport to Predict the Evolution of Stochastic Particle Systems [42.49693678817552]
  We use linearized optimal transport theory to prove that the measure-valued algorithm is first-order accurate when the measure evolves smoothly''<n>We specifically demonstrate the efficacy of our approach by showing that our algorithm vastly reduces the number of micro-scale steps needed to correctly approximate long-term behavior.
  arXiv  Detail & Related papers  (2024-08-03T20:00:36Z)
• Normalizing flows as approximations of optimal transport maps via linear-control neural ODEs [49.1574468325115]
  We consider the problem of recovering the $Wimat$-optimal transport map T between absolutely continuous measures $mu,nuinmathcalP(mathbbRn)$ as the flow of a linear-control neural ODE.
  arXiv  Detail & Related papers  (2023-11-02T17:17:03Z)
• Projected Langevin dynamics and a gradient flow for entropic optimal transport [0.8057006406834466]
  We introduce analogous diffusion dynamics that sample from an entropy-regularized optimal transport. By studying the induced Wasserstein geometry of the submanifold $Pi(mu,nu)$, we argue that the SDE can be viewed as a Wasserstein gradient flow on this space of couplings.
  arXiv  Detail & Related papers  (2023-09-15T17:55:56Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Manifold Interpolating Optimal-Transport Flows for Trajectory Inference [64.94020639760026]
  We present a method called Manifold Interpolating Optimal-Transport Flow (MIOFlow) MIOFlow learns, continuous population dynamics from static snapshot samples taken at sporadic timepoints. We evaluate our method on simulated data with bifurcations and merges, as well as scRNA-seq data from embryoid body differentiation, and acute myeloid leukemia treatment.
  arXiv  Detail & Related papers  (2022-06-29T22:19:03Z)
• Trajectory Inference via Mean-field Langevin in Path Space [0.17205106391379024]
  Trajectory inference aims at recovering the dynamics of a population from snapshots of its temporal marginals. A min-entropy estimator relative to the Wiener measure in path space was introduced by Lavenant et al.
  arXiv  Detail & Related papers  (2022-05-14T23:13:00Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  We consider optimization with delayed gradients where, at each time stept$, the algorithm makes an update using a stale computation - d_t$ for arbitrary delay $d_t gradient. Our experiments demonstrate the efficacy and robustness of our algorithm in cases where the delay distribution is skewed or heavy-tailed.
  arXiv  Detail & Related papers  (2021-06-22T15:50:45Z)
• The Wasserstein Proximal Gradient Algorithm [23.143814848127295]
  Wasserstein gradient flows are continuous time dynamics that define curves of steepest descent to minimize an objective function over the space of probability measures. We propose a Forward Backward (FB) discretization scheme that can tackle the case where the objective function is the sum of a smooth and a nonsmooth geodesically convex terms.
  arXiv  Detail & Related papers  (2020-02-07T22:19:32Z)
• A Near-Optimal Gradient Flow for Learning Neural Energy-Based Models [93.24030378630175]
  We propose a novel numerical scheme to optimize the gradient flows for learning energy-based models (EBMs) We derive a second-order Wasserstein gradient flow of the global relative entropy from Fokker-Planck equation. Compared with existing schemes, Wasserstein gradient flow is a smoother and near-optimal numerical scheme to approximate real data densities.
  arXiv  Detail & Related papers  (2019-10-31T02:26:20Z)

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.