Concentration inequalities for leave-one-out cross validation

• URL: http://arxiv.org/abs/2211.02478v3
• Date: Mon, 16 Oct 2023 14:21:31 GMT
• Title: Concentration inequalities for leave-one-out cross validation
• Authors: Benny Avelin and Lauri Viitasaari
• Abstract summary: We show that estimator stability is enough to show that leave-one-out cross validation is a sound procedure. We obtain our results by relying on random variables with distribution satisfying the logarithmic Sobolev inequality.
• Score: 1.90365714903665
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In this article we prove that estimator stability is enough to show that leave-one-out cross validation is a sound procedure, by providing concentration bounds in a general framework. In particular, we provide concentration bounds beyond Lipschitz continuity assumptions on the loss or on the estimator. We obtain our results by relying on random variables with distribution satisfying the logarithmic Sobolev inequality, providing us a relatively rich class of distributions. We illustrate our method by considering several interesting examples, including linear regression, kernel density estimation, and stabilized/truncated estimators such as stabilized kernel regression.

Related papers

• Convergence of Score-Based Discrete Diffusion Models: A Discrete-Time Analysis [56.442307356162864]
  We study the theoretical aspects of score-based discrete diffusion models under the Continuous Time Markov Chain (CTMC) framework. We introduce a discrete-time sampling algorithm in the general state space $[S]d$ that utilizes score estimators at predefined time points. Our convergence analysis employs a Girsanov-based method and establishes key properties of the discrete score function.
  arXiv  Detail & Related papers  (2024-10-03T09:07:13Z)
• Uncertainty Quantification via Stable Distribution Propagation [60.065272548502]
  We propose a new approach for propagating stable probability distributions through neural networks. Our method is based on local linearization, which we show to be an optimal approximation in terms of total variation distance for the ReLU non-linearity.
  arXiv  Detail & Related papers  (2024-02-13T09:40:19Z)
• A Tale of Sampling and Estimation in Discounted Reinforcement Learning [50.43256303670011]
  We present a minimax lower bound on the discounted mean estimation problem. We show that estimating the mean by directly sampling from the discounted kernel of the Markov process brings compelling statistical properties.
  arXiv  Detail & Related papers  (2023-04-11T09:13:17Z)
• Stochastic Saddle Point Problems with Decision-Dependent Distributions [0.6091702876917279]
  This paper focuses on saddle point problems with decision-dependent in both the static and time-varying settings. We introduce the notion of equilibrium points -- which are saddle points for the stationary minimax problem. We show that primal-dual algorithms converge to saddle points in a similar fashion.
  arXiv  Detail & Related papers  (2022-01-07T03:36:41Z)
• Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
  We consider the task of heavy-tailed statistical estimation given streaming $p$ samples. We design a clipped gradient descent and provide an improved analysis under a more nuanced condition on the noise of gradients.
  arXiv  Detail & Related papers  (2021-08-25T21:30:27Z)
• Distribution-Free Robust Linear Regression [5.532477732693]
  We study random design linear regression with no assumptions on the distribution of the covariates. We construct a non-linear estimator achieving excess risk of order $d/n$ with the optimal sub-exponential tail. We prove an optimal version of the classical bound for the truncated least squares estimator due to Gy"orfi, Kohler, Krzyzak, and Walk.
  arXiv  Detail & Related papers  (2021-02-25T15:10:41Z)
• Adversarial robust weighted Huber regression [2.0257616108612373]
  We consider a robust estimation of linear regression coefficients. We derive an estimation error bound, which depends on the stable rank and the condition number of the covariance matrix.
  arXiv  Detail & Related papers  (2021-02-22T15:50:34Z)
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method [18.541857410928387]
  The randomized diffusion method, proposed by [SL19], has emerged as an optimal discretization procedure for simulating the continuous time Langevin Langevin.
  arXiv  Detail & Related papers  (2020-11-06T03:39:23Z)
• Nonparametric Score Estimators [49.42469547970041]
  Estimating the score from a set of samples generated by an unknown distribution is a fundamental task in inference and learning of probabilistic models. We provide a unifying view of these estimators under the framework of regularized nonparametric regression. We propose score estimators based on iterative regularization that enjoy computational benefits from curl-free kernels and fast convergence.
  arXiv  Detail & Related papers  (2020-05-20T15:01:03Z)
• Batch Stationary Distribution Estimation [98.18201132095066]
  We consider the problem of approximating the stationary distribution of an ergodic Markov chain given a set of sampled transitions. We propose a consistent estimator that is based on recovering a correction ratio function over the given data.
  arXiv  Detail & Related papers  (2020-03-02T09:10:01Z)
• Pareto Smoothed Importance Sampling [8.705872384531318]
  Importance weighting is a general way to adjust Monte Carlo integration to account for draws from the wrong distribution. This routinely occurs when there are aspects of the target distribution that are not well captured by the approximating distribution. We present a new method for stabilizing importance weights using a generalized Pareto distribution fit to the upper tail of the distribution of the simulated importance ratios.
  arXiv  Detail & Related papers  (2015-07-09T18:43:28Z)

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.