In this paper, we develop several related finite dimensional variational principles for discrete optimal transport (DOT), Minkowski type problems for convex polytopes and discrete Monge-Ampere equation (DMAE). A link between the discrete optimal transport, discrete Monge-Ampere equation and the power diagram in computa…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,742 papers · 148 categories
Trend · papers per month
48 results for “discrete optimal transport”
Proves hardness of semi-discrete optimal transport and proposes regularization methods.
problem Computing Wasserstein distance between discrete and non-discrete probability measures.
method Proves hardness, introduces distributionally robust dual optimal transport, regularizes primal objective, uses stochastic gradient descent.
result Regularization schemes and improved convergence guarantees for semi-discrete optimal transport problems.
New method reduces discrete flow transitions, improving perplexity estimation.
problem Stochasticity in discrete paths makes rectification strategies ineffective.
method Dynamic-optimal-transport-like minimization objective with minibatch strategies.
result 32 times reduction in transitions for same perplexity.
Estimates discontinuous optimal transport maps between a discrete and continuous distribution.
problem Estimating discontinuous optimal transport maps between a discrete and continuous distribution.
method Entropic optimal transport estimator, computationally efficient.
result The estimator converges at the minimax-optimal rate in the semi-discrete setting.
Particle-based variational inference offers a flexible way of approximating complex posterior distributions with a set of particles. In this paper we introduce a new particle-based variational inference method based on the theory of semi-discrete optimal transport. Instead of minimizing the KL divergence between the po…
A new discrete formula connects vertex and edge distributions on graphs.
problem Optimal transport on graphs with mixed vertex and edge distributions.
method Discrete transport equation and Benamou-Brenier formulation.
result Classification of all Wasserstein-1 geodesics on graphs.
New findings on optimal transport gradient for generative models, addressing numerical instabilities.
problem Numerical instabilities in training Wasserstein Generative Adversarial Networks (WGAN).
method Valid differentiation theorem for entropic regularized transport, semi-discrete gradient formulation, and optimization algorithm.
result Existence of optimal transport gradient for generative models under specified conditions.
This research proves that quadratic regularized optimal transport can approximate the Laplace-Beltrami operator on smooth manifolds.
problem Approximating the Laplace-Beltrami operator using optimal transport with quadratic regularization.
method Deriving first-order optimal potentials and analyzing the convergence of discrete Laplace operators.
result The discrete Laplace operators converge to the Laplace-Beltrami operator on smooth manifolds.
Rates of Estimation of Optimal Transport Maps using Plug-in Estimators via Barycentric Projectionsmath.ST
The paper analyzes rates of convergence for optimal transport map estimators using barycentric projections.
problem Estimating optimal transport maps from data sampled according to two distributions.
method Comprehensive analysis of rates of convergence for plug-in estimators defined via barycentric projections.
result New stability estimate for barycentric projections under minimal smoothness assumptions.
New method uses continuous OT for fairness, outperforming discrete OT.
problem Fairness issues in machine learning models.
method Stochastic-gradient fairness method based on continuous optimal transport.
result Continuous OT method outperforms discrete OT when data is limited.
Population Annealing as a Discrete-Time Schrödinger Bridgecond-mat.stat-mech
PA reinterpreted as SB problem, unifying thermodynamics and optimal transport.
problem Optimizing discrete-time paths between probability distributions.
method Schrödinger Bridge theory, solving variational problems.
result PA's reweighting step derived from Schrödinger system.
Stochastic Optimization in Semi-Discrete Optimal Transport: Convergence Analysis and Minimax Ratemath.ST
Stochastic optimization improves semi-discrete OT map estimation with a minimax rate.
problem Empirical success of SGD in semi-discrete OT, but lack of theoretical guarantees.
method Averaged projected SGD with a minimax convergence rate of O(1/√n).
result SGD methods can estimate the OT map with a minimax convergence rate of O(1/√n).
AlignFlow improves FGMs by optimizing noise and data alignment.
problem Optimal Transport methods for FGMs are limited by scalability issues.
method Introduces Semi-Discrete Optimal Transport (SDOT) to enhance FGM training.
result AlignFlow scales well to large datasets and model architectures.
We consider the entropic regularization of discretized optimal transport and propose to solve its optimality conditions via a logarithmic Newton iteration. We show a quadratic convergence rate and validate numerically that the method compares favorably with the more commonly used Sinkhorn--Knopp algorithm for small reg…
Optimal transport is #P-hard when components are independent, even with approximate solutions.
problem Computational complexity of optimal transport with independent marginals.
method Proved #P-hardness and developed a pseudo-polynomial time approximation algorithm.
result Optimal transport is #P-hard even with independent components and approximate solutions.
Study shows how optimal transport behaves in higher dimensions.
problem Characterizing optimal transport in higher dimensions with Euclidean distance.
method Investigates the small regularization limit of entropic optimal transport.
result The limiting transport plan is supported on transport rays and uniquely minimizes a relative entropy functional.
A new method uses normalizing flows to approximate optimal transport between empirical distributions.
problem Learning an optimal transport map between two empirical distributions.
method Relaxing the Monge formulation of optimal transport, using normalizing flows to approximate the solution.
result The method provides a good approximation of the true optimal transport.
Researchers analyze inverse optimal transport, deriving theoretical and empirical insights.
problem Understanding the inverse problem of inferring cost matrices from optimal couplings.
method Formalized and analyzed using entropy-regularized optimal transport, with theoretical and empirical contributions.
result Characterization of the manifold of cross-ratio equivalent costs and derivation of an MCMC sampler.
Graph Energy Matching improves generation quality for molecular graphs.
problem Discrete energy-based models struggle with efficient and high-quality sampling for graph generation.
method Inspired by transport-map optimization, Graph Energy Matching learns a permutation-invariant potential energy to guide sampling.
result GEM matches or surpasses discrete diffusion baselines on molecular graph benchmarks.
In this article we discuss the problem of calculating optimal model-independent (robust) bounds for the price of Asian options with discrete and continuous averaging. We will give geometric characterisations of the maximising and the minimising pricing model for certain types of Asian options in discrete and continuous…
Novel algorithm solves optimal transport using evolving probability distributions and convolution.
problem Sample-based optimal transport problem.
method Adversarial formulation with convolution of adaptive kernel and evolving measure.
result Algorithm robust to dimensionality and produces complex maps.
Sobolev Gradient Ascent for Optimal Transport: Barycenter Optimization and Convergence Analysismath.OC
Paper introduces SGA for barycenter optimization in optimal transport.
problem Optimizing Wasserstein barycenter for discrete distributions.
method Sobolev gradient ascent algorithm tailored to Wasserstein geometry.
result SGA achieves convergence rate similar to subgradient descent.
Survey of Sinkhorn algorithm for optimal transport, emphasizing its geometric origins.
problem Solving optimal transport problems efficiently and accurately.
method Discretization of a non-linear integral equation.
result Geometric interpretation and discretization of the Sinkhorn algorithm.
This work builds the connection between the regularity theory of optimal transportation map, Monge-Ampère equation and GANs, which gives a theoretic understanding of the major drawbacks of GANs: convergence difficulty and mode collapse. According to the regularity theory of Monge-Ampère equation, if the support of the …
Riemannian Neural OT maps improve scalability on manifolds.
problem Challenges in extending neural OT to high-dimensional Riemannian manifolds.
method Introduces Riemannian Neural OT (RNOT) maps that avoid discretization and incorporate geometric structure.
result RNOT maps approximate Riemannian OT maps with sub-exponential complexity in the dimension.
New geometry for optimal transport cost based on Bregman divergences.
problem Optimal transport cost calculation with Bregman divergences.
method Established properties, defined interpolations, constructed dualistic geometry.
result Derived generalized Pythagorean inequality and Bregman-Wasserstein barycenters.
UNOT solves optimal transport problems efficiently using neural networks.
problem Computational expense in solving optimal transport problems.
method UNOT (Universal Neural Optimal Transport) uses Fourier Neural Operators to predict OT distances and plans accurately and efficiently.
result UNOT achieves up to 7.4x speedup over the Sinkhorn algorithm while maintaining accuracy.
Framework uses optimal transport for neural architecture search.
problem Optimizing neural architectures in deep learning.
method Semi-discrete optimization using optimal transport.
result Gradient flow and minimizing movement scheme converge to reaction-diffusion equations.
Paper uses optimal transport for Bayesian filtering, deriving new EnKF and FPF formulations.
problem Bayesian filtering for nonlinear systems with non-Gaussian observations.
method Optimal transport theory applied to Bayes' law, constructing Brenier maps.
result New variational formulations of EnKF and FPF for non-Gaussian settings.
DRAG decreases regularization to accelerate semi-discrete OT convergence.
problem Mitigating bias in semi-discrete OT problems with entropic regularization.
method DRAG: Decreasing Regularization Averaged Gradient, a stochastic gradient descent algorithm.
result DRAG achieves unbiased sample and iteration complexity for OT cost and potential estimation, and rate for OT map.
Structured Optimal Transportstat.ML
Optimal Transport has recently gained interest in machine learning for applications ranging from domain adaptation, sentence similarities to deep learning. Yet, its ability to capture frequently occurring structure beyond the "ground metric" is limited. In this work, we develop a nonlinear generalization of (discrete) …
A mesh-free method solves continuum-marginal optimal transport problems.
problem Recovering minimum-energy velocity fields from time-continuous probability marginals.
method Embeds weak continuity equation in a reproducing kernel Hilbert space, optimizing with mini-batch stochastic methods.
result Accurately recovers drift and maintains marginal consistency in synthetic experiments.
Geometry-Aware Optimal Transport: Fast Intrinsic Dimension and Wasserstein Distance Estimationstat.ML
New estimators for intrinsic dimension and Wasserstein distance improve OT accuracy.
problem Intrinsic dimension estimation and Wasserstein distance estimation in large-scale OT.
method Introduces novel estimators for intrinsic dimension and Wasserstein distance.
result Simple, tuning-free estimator of OT and fast intrinsic dimension estimator.
A new method for manifold learning using sparse regularised optimal transport.
problem Detecting latent manifolds in high-dimensional data with noisy observations.
method Proposes a symmetric version of optimal transport with quadratic regularisation to construct a sparse and adaptive affinity matrix.
result The method outperforms competing methods in numerical experiments and demonstrates robustness to heteroskedastic noise.
Paper tackles robust optimal transport with improved computational complexity and barycenter approximation.
problem Computing robust optimal transport and its barycenter efficiently.
method Sinkhorn-based algorithms for robust optimal transport and iterative Bregman projections for barycenter approximation.
result Improved computational complexity for robust optimal transport and barycenter approximation.
Meta Optimal Transport learns from past problems to solve similar OT problems faster.
problem Solving similar optimal transport problems repeatedly from scratch is inefficient.
method Amortized optimization to predict optimal transport maps from past solutions.
result Meta OT models can solve new problems faster than standard methods.
Benchmark of Likelihood-Free Inference Methods based on Neural and Optimal Transport Approachesstat.ME
This study benchmarks likelihood-free inference methods for models with heavy-tailed or discrete data.
problem Comparing likelihood-free inference methods for models with structural features like heavy-tails or discreteness.
method Four approaches: MLE, NBE, EOT, and AW-NBE are evaluated using simulations.
result The choice of evaluation tools is crucial for models with extremes and discrete data.
This paper develops efficient bounds on the Wasserstein metric for discrete measures.
problem Computing the exact Wasserstein metric is computationally expensive.
method Formulates and solves a Kantorovich problem on a coarse grid using quantized measures and cost matrices, followed by upscaling and correction.
result Achieves a 10x-100x speedup while maintaining low approximation error.
This paper provides a simple procedure to fit generative networks to target distributions, with the goal of a small Wasserstein distance (or other optimal transport costs). The approach is based on two principles: (a) if the source randomness of the network is a continuous distribution (the "semi-discrete" setting), th…
New algorithm computes optimal transport barycenter efficiently.
problem Computing optimal transport barycenter for high-dimensional probability distributions.
method Wasserstein-Descent -Ascent (WDHA) algorithm.
result Exact barycenter computation in nearly linear time and linear space complexity.
The paper calibrates SPX and VIX options using optimal transport.
problem Joint calibration of SPX and VIX options or futures.
method Semimartingale optimal transport problem with PDE formulation and dual formulation.
result The model accurately calibrates SPX, VIX options, and futures simultaneously.
New algorithm improves OT map estimation for semi-discrete settings.
problem Improving estimation of OT maps in semi-discrete settings.
method Stochastic Gradient Descent with adaptive entropic regularization and averaging acceleration.
result Achieves nearly minimax rate of for OT map estimation.
A fast method for discrete OT with group-sparse regularization for class label preservation.
problem Efficiently measuring the distance between two discrete distributions with class labels.
method Fast discrete OT with group-sparse regularizers using gradient-based algorithms.
result Up to 8.6 times faster than original method without degrading accuracy.
Optimal transport reformulates multiple quantile hedging problem.
problem Multiple quantile hedging problem in incomplete markets.
method Reformulated as Monge optimal transport problem, introduced Kantorovitch version, proved no duality gap.
result Multiple quantile hedging problem can be seen as semi-discrete optimal transport problem.
CT-OT Flow estimates continuous-time dynamics from discrete snapshots.
problem Estimating continuous-time dynamics from temporally aggregated snapshots with noisy or uncertain timestamps.
method Two-stage framework: aligning neighboring intervals via partial optimal transport (POT) and reconstructing a continuous-time distribution through temporal kernel smoothing.
result Reduces distributional and trajectory errors compared with existing methods across synthetic and real datasets.
Framework for worst-case generation using Wasserstein space optimization.
problem Evaluating robustness and stress-testing systems under distribution shifts.
method Min-max optimization over continuous probability distributions in Wasserstein space.
result Global convergence guarantees for the proposed Gradient Descent Ascent scheme.
New forms of multi-marginal POT problem derived for computational efficiency.
problem Optimizing transport between multiple unbalanced measures with limited supports.
method Developed two equivalence forms of the POT problem and an optimization algorithm, ApproxMPOT.
result ApproxMPOT algorithm achieves optimal value with complexity .
Spectral clustering improves accuracy and efficiency for clustering discrete distributions.
problem Inaccurate clustering of discrete distributions using traditional methods.
method Spectral clustering combined with distribution affinity measures (MMD, Wasserstein distance) and linear optimal transport.
result Spectral clustering outperforms traditional methods in accuracy and efficiency.