Quantitative Uniform Stability of the Iterative Proportional Fitting Procedure

• URL: http://arxiv.org/abs/2108.08129v1
• Date: Wed, 18 Aug 2021 13:02:31 GMT
• Title: Quantitative Uniform Stability of the Iterative Proportional Fitting Procedure
• Authors: George Deligiannidis, Valentin De Bortoli, Arnaud Doucet
• Abstract summary: 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.
• Score: 24.45063570951773
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We establish the uniform in time stability, w.r.t. the marginals, of the Iterative Proportional Fitting Procedure, also known as Sinkhorn algorithm, used to solve entropy-regularised Optimal Transport problems. Our result is quantitative and stated in terms of the 1-Wasserstein metric. As a corollary we establish a quantitative stability result for Schr\"odinger bridges.

Related papers

• Hessian stability and convergence rates for entropic and Sinkhorn potentials via semiconcavity [4.604003661048267]
  This is the first work addressing this second-order quantitative stability estimate in general unbounded settings. We deduce exponential convergence rates for gradient and Hessian of Sinkhorns along Sinkhorn's algorithm.
  arXiv  Detail & Related papers  (2025-04-15T12:34:09Z)
• Synthesis and Analysis of Data as Probability Measures with Entropy-Regularized Optimal Transport [12.573382512049053]
  We consider synthesis and analysis of probability measures using the entropy-regularized Wasserstein-2 cost and its unbiased version, the Sinkhorn divergence. We show that these coefficients, as well as the value of the barycenter functional, can be estimated from samples with dimension-independent rates of convergence. We employ the barycentric coefficients as features for classification of corrupted point cloud data, and show that compared to neural network baselines, our approach is more efficient in small training data regimes.
  arXiv  Detail & Related papers  (2025-01-13T16:16:53Z)
• Powering a quantum clock with a non-equilibrium steady state [50.24983453990065]
  We propose powering a quantum clock with the non-thermal resources offered by the stationary state of an integrable quantum spin chain. Using experimentally relevant examples of quantum spin chains, we suggest crossing a phase transition point is crucial for optimal performance.
  arXiv  Detail & Related papers  (2024-12-17T17:25:11Z)
• On the Selection Stability of Stability Selection and Its Applications [2.263635133348731]
  This paper seeks to broaden the use of an established stability estimator to evaluate the overall stability of the stability selection framework. We suggest that the stability estimator offers two advantages: it can serve as a reference to reflect the robustness of the outcomes obtained and help identify an optimal regularization value to improve stability.
  arXiv  Detail & Related papers  (2024-11-14T00:02:54Z)
• Quantum walk in stochastic environment [4.51060985591184]
  We consider a quantized version of the Sinai-Derrida model for "random walk in random environment" We analyze in detail this enhancement and its dependence on the model parameters.
  arXiv  Detail & Related papers  (2023-08-16T15:06:39Z)
• Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees [57.67528738886731]
  We study the numerical stability of scalable sparse approximations based on inducing points. For low-dimensional tasks such as geospatial modeling, we propose an automated method for computing inducing points satisfying these conditions.
  arXiv  Detail & Related papers  (2022-10-14T15:20:17Z)
• Stability and Generalization for Markov Chain Stochastic Gradient Methods [49.981789906200035]
  We provide a comprehensive generalization analysis of MC-SGMs for both minimization and minimax problems. We establish the optimal excess population risk bounds for both smooth and non-smooth cases. We develop the first nearly optimal convergence rates for convex-concave problems both in expectation and with high probability.
  arXiv  Detail & Related papers  (2022-09-16T15:42:51Z)
• 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)
• 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)
• Stabilizer R\'enyi entropy [0.0]
  We introduce a novel measure for the quantum property of nonstabilizerness - commonly known as "magic" We show that this is a good measure of nonstabilizerness from the point of view of resource theory and show bounds with other known measures. We show that the nonstabilizerness is intimately connected to out-of-time-order correlation functions and that maximal levels of nonstabilizerness are necessary for quantum chaos.
  arXiv  Detail & Related papers  (2021-06-23T18:00:02Z)
• 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)
• Continuous Regularized Wasserstein Barycenters [51.620781112674024]
  We introduce a new dual formulation for the regularized Wasserstein barycenter problem. We establish strong duality and use the corresponding primal-dual relationship to parametrize the barycenter implicitly using the dual potentials of regularized transport problems.
  arXiv  Detail & Related papers  (2020-08-28T08:28:06Z)
• 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)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)

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.