Nearest neighbor empirical processes

• URL: http://arxiv.org/abs/2110.15083v4
• Date: Wed, 10 Apr 2024 08:29:31 GMT
• Title: Nearest neighbor empirical processes
• Authors: François Portier,
• Abstract summary: An empirical measure based on the responses from the nearest neighbors to a given point $x$ is introduced and studied as a central statistical quantity. A uniform non-asymptotic bound is established under a well-known condition, often referred to as Vapnik-Chervonenkis, on the uniform entropy numbers. This suggests the possibility of using standard formulas to estimate the variance by using only the nearest neighbors instead of the full data.
• Score: 7.034466417392574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the regression framework, the empirical measure based on the responses resulting from the nearest neighbors, among the covariates, to a given point $x$ is introduced and studied as a central statistical quantity. First, the associated empirical process is shown to satisfy a uniform central limit theorem under a local bracketing entropy condition on the underlying class of functions reflecting the localizing nature of the nearest neighbor algorithm. Second a uniform non-asymptotic bound is established under a well-known condition, often referred to as Vapnik-Chervonenkis, on the uniform entropy numbers. The covariance of the Gaussian limit obtained in the uniform central limit theorem is simply equal to the conditional covariance operator given the covariate value. This suggests the possibility of using standard formulas to estimate the variance by using only the nearest neighbors instead of the full data. This is illustrated on two problems: the estimation of the conditional cumulative distribution function and local linear regression.

Related papers

• Conditional Independence of 1D Gibbs States with Applications to Efficient Learning [0.23301643766310368]
  We show that spin chains in thermal equilibrium have a correlation structure in which individual regions are strongly correlated at most with their near vicinity. We prove that these measures decay superexponentially at every positive temperature.
  arXiv  Detail & Related papers  (2024-02-28T17:28:01Z)
• 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)
• Coefficient-based Regularized Distribution Regression [4.21768682940933]
  We consider the coefficient-based regularized distribution regression which aims to regress from probability measures to real-valued responses over a kernel reproducing Hilbert space (RKHS) Asymptotic behaviors of the algorithm in different regularity ranges of the regression function are comprehensively studied. We get the optimal rates under some mild conditions, which matches the one-stage sampled minimax optimal rate.
  arXiv  Detail & Related papers  (2022-08-26T03:46:14Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• 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)
• 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)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Reweighting samples under covariate shift using a Wasserstein distance criterion [0.0]
  We study an optimal reweighting that minimizes the Wasserstein distance between the empirical measures of the two samples. The consistency and some convergence rates in terms of expected Wasserstein distance are derived. These results have some application in Uncertainty Quantification for decoupled estimation and in the bound of the generalization error for the Nearest Neighbor Regression.
  arXiv  Detail & Related papers  (2020-10-19T07:23:55Z)
• Consistent Online Gaussian Process Regression Without the Sample Complexity Bottleneck [14.309243378538012]
  We propose an online compression scheme that fixes an error neighborhood with respect to the Hellinger metric centered at the current posterior. For constant error radius, POG converges to a neighborhood of the population posterior (Theorem 1(ii))but with finite memory at-worst determined by the metric entropy of the feature space.
  arXiv  Detail & Related papers  (2020-04-23T11:52:06Z)
• A Measure-Theoretic Approach to Kernel Conditional Mean Embeddings [14.71280987722701]
  We present an operator-free, measure-theoretic approach to the conditional mean embedding. We derive a natural regression interpretation to obtain empirical estimates. As natural by-products, we obtain the conditional analogues of the mean discrepancy and Hilbert-Schmidt independence criterion.
  arXiv  Detail & Related papers  (2020-02-10T12:44:12Z)

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.