Convergence rate of Tsallis entropic regularized optimal transport
- URL: http://arxiv.org/abs/2304.06616v1
- Date: Thu, 13 Apr 2023 15:37:14 GMT
- Title: Convergence rate of Tsallis entropic regularized optimal transport
- Authors: Takeshi Suguro and Toshiaki Yachimura
- Abstract summary: We consider Tsallis entropic regularized optimal transport and discuss the convergence rate as the regularization parameter $varepsilon$ goes to $0$.
We compare this to the convergence rate of the entropic regularized optimal transport with Kullback--Leibler divergence and show that KL is the fastest convergence rate in terms of Tsallis relative entropy.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider Tsallis entropic regularized optimal transport and
discuss the convergence rate as the regularization parameter $\varepsilon$ goes
to $0$. In particular, we establish the convergence rate of the Tsallis
entropic regularized optimal transport using the quantization and shadow
arguments developed by Eckstein--Nutz. We compare this to the convergence rate
of the entropic regularized optimal transport with Kullback--Leibler (KL)
divergence and show that KL is the fastest convergence rate in terms of Tsallis
relative entropy.
Related papers
- Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
We prove new convergence rates for a generalized version of Nesterov acceleration underrho conditions.
Our analysis reduces the dependence on the strong growth constant from $$ to $sqrt$ as compared to prior work.
arXiv Detail & Related papers (2024-04-03T00:41:19Z) - On a Relation Between the Rate-Distortion Function and Optimal Transport [25.59334941818991]
We show that a function defined via an extremal entropic OT distance is equivalent to the rate-distortion function.
We numerically verify this result as well as previous results that connect the Monge and Kantorovich problems to optimal scalar quantization.
arXiv Detail & Related papers (2023-07-01T06:20:23Z) - Accelerating Convergence in Global Non-Convex Optimization with
Reversible Diffusion [0.0]
Langevin Dynamics has been extensively in global non- optimization experiments.
Our proposed method is used to investigate the trade-off between speed and discretization error.
arXiv Detail & Related papers (2023-05-19T07:49:40Z) - Convergence Rates for Regularized Optimal Transport via Quantization [3.04585143845864]
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.
arXiv Detail & Related papers (2022-08-30T16:58:40Z) - 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) - Conformal field theory from lattice fermions [77.34726150561087]
We provide a rigorous lattice approximation of conformal field theories given in terms of lattice fermions in 1+1-dimensions.
We show how these results lead to explicit error estimates pertaining to the quantum simulation of conformal field theories.
arXiv Detail & Related papers (2021-07-29T08:54:07Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence.
We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
arXiv Detail & Related papers (2021-06-30T17:51:36Z) - Variational Refinement for Importance Sampling Using the Forward
Kullback-Leibler Divergence [77.06203118175335]
Variational Inference (VI) is a popular alternative to exact sampling in Bayesian inference.
Importance sampling (IS) is often used to fine-tune and de-bias the estimates of approximate Bayesian inference procedures.
We propose a novel combination of optimization and sampling techniques for approximate Bayesian inference.
arXiv Detail & Related papers (2021-06-30T11:00:24Z) - The Convergence Indicator: Improved and completely characterized
parameter bounds for actual convergence of Particle Swarm Optimization [68.8204255655161]
We introduce a new convergence indicator that can be used to calculate whether the particles will finally converge to a single point or diverge.
Using this convergence indicator we provide the actual bounds completely characterizing parameter regions that lead to a converging swarm.
arXiv Detail & Related papers (2020-06-06T19:08:05Z) - Support recovery and sup-norm convergence rates for sparse pivotal
estimation [79.13844065776928]
In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level.
We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
arXiv Detail & Related papers (2020-01-15T16:11:04Z)
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.