Hessian stability and convergence rates for entropic and Sinkhorn potentials via semiconcavity

• URL: http://arxiv.org/abs/2504.11133v1
• Date: Tue, 15 Apr 2025 12:34:09 GMT
• Title: Hessian stability and convergence rates for entropic and Sinkhorn potentials via semiconcavity
• Authors: Giacomo Greco, Luca Tamanini,
• Abstract summary: This is the first work addressing this second-order quantitative stability estimate in general unbounded settings.<n>We deduce exponential convergence rates for gradient and Hessian of Sinkhorns along Sinkhorn's algorithm.
• Score: 4.604003661048267
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we determine quantitative stability bounds for the Hessian of entropic potentials, i.e., the dual solution to the entropic optimal transport problem. Up to authors' knowledge this is the first work addressing this second-order quantitative stability estimate in general unbounded settings. Our proof strategy relies on semiconcavity properties of entropic potentials and on the representation of entropic transport plans as laws of forward and backward diffusion processes, known as Schr\"odinger bridges. Moreover, our approach allows to deduce a stochastic proof of quantitative stability entropic estimates and integrated gradient estimates as well. Finally, as a direct consequence of these stability bounds, we deduce exponential convergence rates for gradient and Hessian of Sinkhorn iterates along Sinkhorn's algorithm, a problem that was still open in unbounded settings. Our rates have a polynomial dependence on the regularization parameter.

Related papers

• A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm [3.7498611358320733]
  We study stability of unboundeds and convergence of Sinkhorn's algorithm in the framework of entropic optimal transport.<n>New applications include subspace elastic costs, weakly log-concave marginals, marginals with light tails.
  arXiv  Detail & Related papers  (2024-12-12T12:45:31Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• Convergence and concentration properties of constant step-size SGD through Markov chains [0.0]
  We consider the optimization of a smooth and strongly convex objective using constant step-size gradient descent (SGD) We show that, for unbiased gradient estimates with mildly controlled variance, the iteration converges to an invariant distribution in total variation distance. All our results are non-asymptotic and their consequences are discussed through a few applications.
  arXiv  Detail & Related papers  (2023-06-20T12:36:28Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)
• 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)
• Quantitative Uniform Stability of the Iterative Proportional Fitting Procedure [24.45063570951773]
  We establish the uniform in time stability, w.r.t. the marginals, of the Iterative Proportional Fitting Procedure. As a corollary we establish a quantitative stability result for Schr"odinger bridges.
  arXiv  Detail & Related papers  (2021-08-18T13:02:31Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• 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)
• Bernstein-Greene-Kruskal approach for the quantum Vlasov equation [91.3755431537592]
  The one-dimensional stationary quantum Vlasov equation is analyzed using the energy as one of the dynamical variables. In the semiclassical case where quantum tunneling effects are small, an infinite series solution is developed.
  arXiv  Detail & Related papers  (2021-02-18T20:55:04Z)
• The Instability of Accelerated Gradient Descent [26.613126943532357]
  We study the algorithmic stability of Nesterov's accelerated gradient method. For convex quadratic objectives, citetchen 2018stability proved that the uniform stability of the method grows quadratically with the number of optimization steps. We disprove this conjecture and show, for two notions of stability, that the stability of Nesterov's accelerated method in fact deteriorates emphexponentially fast with the number of gradient steps.
  arXiv  Detail & Related papers  (2021-02-03T17:50:42Z)
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent [55.85456985750134]
  We introduce a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting. To our best knowledge, this gives the firstever-known stability and generalization for SGD with even non-differentiable loss functions.
  arXiv  Detail & Related papers  (2020-06-15T06:30:19Z)

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.