Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithm

• URL: http://arxiv.org/abs/2311.04041v2
• Date: Wed, 17 Jan 2024 13:25:50 GMT
• Title: Hilbert's projective metric for functions of bounded growth and exponential convergence of Sinkhorn's algorithm
• Authors: Stephan Eckstein
• Abstract summary: We study versions of Hilbert's projective metric for spaces of integrable functions of bounded growth. We show that kernel integral operators are contractions with respect to suitable specifications of such metrics. As an application to entropic optimal transport, we show exponential convergence of Sinkhorn's algorithm in settings where the marginal distributions have sufficiently light tails.
• Score: 1.6317061277457001
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the entropic optimal transport problem in unbounded settings, we study versions of Hilbert's projective metric for spaces of integrable functions of bounded growth. These versions of Hilbert's metric originate from cones which are relaxations of the cone of all non-negative functions, in the sense that they include all functions having non-negative integral values when multiplied with certain test functions. We show that kernel integral operators are contractions with respect to suitable specifications of such metrics even for kernels which are not bounded away from zero, provided that the decay to zero of the kernel is controlled. As an application to entropic optimal transport, we show exponential convergence of Sinkhorn's algorithm in settings where the marginal distributions have sufficiently light tails compared to the growth of the cost function.

Related papers

• One-Step Estimation of Differentiable Hilbert-Valued Parameters [2.0305676256390934]
  We present estimators for smooth Hilbert-valued parameters, where smoothness is characterized by a pathwise differentiability condition. These estimators correspond to generalizations of cross-fitted one-step estimators based on Hilbert-valued efficient influence functions.
  arXiv  Detail & Related papers  (2023-03-29T14:06:00Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  We show that pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. We also show that focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints.
  arXiv  Detail & Related papers  (2023-01-16T10:30:04Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Optimal Learning Rates for Regularized Least-Squares with a Fourier Capacity Condition [14.910167993978487]
  We derive minimax adaptive rates for a new, broad class of Tikhonov-regularized learning problems in Hilbert scales. We demonstrate that the spectrum of the Mercer operator can be inferred in the presence of tight'' embeddings of suitable Hilbert scales.
  arXiv  Detail & Related papers  (2022-04-16T18:32:33Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Estimation of Riemannian distances between covariance operators and Gaussian processes [0.7360807642941712]
  We study two distances between infinite-dimensional positive definite Hilbert-Schmidt operators. Results show that both distances converge in the Hilbert-Schmidt norm.
  arXiv  Detail & Related papers  (2021-08-26T09:57:47Z)
• Uniform Function Estimators in Reproducing Kernel Hilbert Spaces [0.0]
  This paper addresses the problem of regression to reconstruct functions, which are observed with superimposed errors at random locations. It is demonstrated that the estimator, which is often derived by employing Gaussian random fields, converges in the mean norm of the kernel reproducing Hilbert space to the conditional expectation.
  arXiv  Detail & Related papers  (2021-08-16T08:13:28Z)
• Exact thermal properties of free-fermionic spin chains [68.8204255655161]
  We focus on spin chain models that admit a description in terms of free fermions. Errors stemming from the ubiquitous approximation are identified in the neighborhood of the critical point at low temperatures.
  arXiv  Detail & Related papers  (2021-03-30T13:15:44Z)
• Non-asymptotic Optimal Prediction Error for Growing-dimensional Partially Functional Linear Models [0.951828574518325]
  We show the rate-optimal upper and lower bounds of the prediction error. An exact upper bound for the excess prediction risk is shown in a non-asymptotic form. We derive the non-asymptotic minimax lower bound under the regularity assumption of the Kullback-Leibler divergence of the models.
  arXiv  Detail & Related papers  (2020-09-10T08:49:32Z)
• Metrizing Weak Convergence with Maximum Mean Discrepancies [88.54422104669078]
  This paper characterizes the maximum mean discrepancies (MMD) that metrize the weak convergence of probability measures for a wide class of kernels. We prove that, on a locally compact, non-compact, Hausdorff space, the MMD of a bounded continuous Borel measurable kernel k, metrizes the weak convergence of probability measures if and only if k is continuous.
  arXiv  Detail & Related papers  (2020-06-16T15:49:33Z)
• 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)

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.