Convergence Rates for Regularized Optimal Transport via Quantization

• URL: http://arxiv.org/abs/2208.14391v3
• Date: Wed, 21 Jun 2023 08:31:59 GMT
• Title: Convergence Rates for Regularized Optimal Transport via Quantization
• Authors: Stephan Eckstein, Marcel Nutz
• Abstract summary: We study the convergence of divergence-regularized optimal transport as the regularization parameter vanishes. A novel methodology using quantization and martingale couplings is suitable for non-compact marginals.
• Score: 3.04585143845864
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the convergence of divergence-regularized optimal transport as the regularization parameter vanishes. Sharp rates for general divergences including relative entropy or $L^{p}$ regularization, general transport costs and multi-marginal problems are obtained. A novel methodology using quantization and martingale couplings is suitable for non-compact marginals and achieves, in particular, the sharp leading-order term of entropically regularized 2-Wasserstein distance for all marginals with finite $(2+\delta)$-moment.

Related papers

• Flow matching achieves almost minimax optimal convergence [50.38891696297888]
  Flow matching (FM) has gained significant attention as a simulation-free generative model. This paper discusses the convergence properties of FM for large sample size under the $p$-Wasserstein distance. We establish that FM can achieve an almost minimax optimal convergence rate for $1 leq p leq 2$, presenting the first theoretical evidence that FM can reach convergence rates comparable to those of diffusion models.
  arXiv  Detail & Related papers  (2024-05-31T14:54:51Z)
• Convergence rate of Tsallis entropic regularized optimal transport [0.0]
  We establish fundamental results such as the $Gamma$-convergence of the Tsallis regularized optimal transport to the Monge--Kantorovich problem as the regularization parameter tends to zero. We show that the KL regularization achieves the fastest convergence rate in the Tsallis framework.
  arXiv  Detail & Related papers  (2023-04-13T15:37:14Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  Existing generalization bounds fail to explain crucial factors that drive the generalization of modern neural networks. We derive instance-dependent generalization bounds that depend on the local Lipschitz regularity of the learned prediction function in the data space. We empirically analyze our generalization bounds for neural networks, showing that the bound values are meaningful and capture the effect of popular regularization methods during training.
  arXiv  Detail & Related papers  (2022-11-02T16:39:42Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• An improved central limit theorem and fast convergence rates for entropic transportation costs [13.9170193921377]
  We prove a central limit theorem for the entropic transportation cost between subgaussian probability measures. We complement these results with new, faster, convergence rates for the expected entropic transportation cost between empirical measures.
  arXiv  Detail & Related papers  (2022-04-19T19:26:59Z)
• Nearly Tight Convergence Bounds for Semi-discrete Entropic Optimal Transport [0.483420384410068]
  We derive nearly tight and non-asymptotic convergence bounds for solutions of entropic semi-discrete optimal transport. Our results also entail a non-asymptotic and tight expansion of the difference between the entropic and the unregularized costs.
  arXiv  Detail & Related papers  (2021-10-25T06:52:45Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• On Multimarginal Partial Optimal Transport: Equivalent Forms and Computational Complexity [11.280177531118206]
  We study the multi-marginal partial optimal transport (POT) problem between $m$ discrete (unbalanced) measures with at most $n$ supports. We first prove that we can obtain two equivalence forms of the multimarginal POT problem in terms of the multimarginal optimal transport problem via novel extensions of cost tensor. We demonstrate that the ApproxMPOT algorithm can approximate the optimal value of multimarginal POT problem with a computational complexity upper bound of the order $tildemathcalO(m3(n+1)m/ var
  arXiv  Detail & Related papers  (2021-08-18T06:46:59Z)
• Optimal transport with $f$-divergence regularization and generalized Sinkhorn algorithm [0.0]
  Entropic regularization provides a generalization of the original optimal transport problem. replacing the Kullback-Leibler divergence with a general $f$-divergence leads to a natural generalization. We propose a practical algorithm for computing the regularized optimal transport cost and its gradient.
  arXiv  Detail & Related papers  (2021-05-29T16:37:31Z)

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.