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
• 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

• Nonparametric Goodness-of-fit Testing under Covariate Shift [4.3686879183724665]
  The distribution mismatch is quantified by either a bounded moment condition or a sub-exponential tail condition on the target-to-source density ratio.<n>Our method combines truncated importance-weighting kernel ridge regression with a multiplier bootstrap to construct confidence sets for the regression function.<n>We prove nonasymptotic validity and sharpness of the resulting confidence sets under suitable operator compatibility conditions.
  arXiv  Detail & Related papers  (2026-08-05T13:51:43Z)
• Distributionally Faithful Imputation via Positive Semi-Definite Kernel Density Estimation [55.47411235954028]
  We recast imputation under missing completely at random as density estimation from masked observations.<n>We obtain a convex empirical risk problem with closed form marginals, solvable by a Newton interior point method.<n>The resulting PSD Impute model yields both single and multiple imputations from the same fitted density.
  arXiv  Detail & Related papers  (2026-07-08T15:51:05Z)
• Generalized nonparametric regression in reproducing kernel Hilbert spaces: Consistency and rates of convergence [0.0]
  We develop a comprehensive theory for M-lev in reproducing spaces.<n>For Sobo spaces we obtain new rates that connect to spaces of smoothness with mixed smoothness functions.
  arXiv  Detail & Related papers  (2026-06-22T08:12:31Z)
• 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.