Kernel Ridge Regression Inference

• URL: http://arxiv.org/abs/2302.06578v2
• Date: Thu, 19 Oct 2023 18:50:45 GMT
• Title: Kernel Ridge Regression Inference
• Authors: Rahul Singh and Suhas Vijaykumar
• Abstract summary: We provide uniform inference and confidence bands for kernel ridge regression. We construct sharp, uniform confidence sets for KRR, which shrink at nearly the minimax rate, for general regressors. We use our procedure to construct a novel test for match effects in school assignment.
• Score: 7.066496204344619
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We provide uniform inference and confidence bands for kernel ridge regression (KRR), a widely-used non-parametric regression estimator for general data types including rankings, images, and graphs. Despite the prevalence of these data -- e.g., ranked preference lists in school assignment -- the inferential theory of KRR is not fully known, limiting its role in economics and other scientific domains. We construct sharp, uniform confidence sets for KRR, which shrink at nearly the minimax rate, for general regressors. To conduct inference, we develop an efficient bootstrap procedure that uses symmetrization to cancel bias and limit computational overhead. To justify the procedure, we derive finite-sample, uniform Gaussian and bootstrap couplings for partial sums in a reproducing kernel Hilbert space (RKHS). These imply strong approximation for empirical processes indexed by the RKHS unit ball with logarithmic dependence on the covering number. Simulations verify coverage. We use our procedure to construct a novel test for match effects in school assignment, an important question in education economics with consequences for school choice reforms.

Related papers

• Highly Adaptive Ridge [84.38107748875144]
  We propose a regression method that achieves a $n-2/3$ dimension-free L2 convergence rate in the class of right-continuous functions with square-integrable sectional derivatives. Har is exactly kernel ridge regression with a specific data-adaptive kernel based on a saturated zero-order tensor-product spline basis expansion. We demonstrate empirical performance better than state-of-the-art algorithms for small datasets in particular.
  arXiv  Detail & Related papers  (2024-10-03T17:06:06Z)
• 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)
• Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay [9.427635404752936]
  We study the tensor-on-tensor regression, where the goal is to connect tensor responses to tensor covariates with a low Tucker rank parameter/matrix. We propose two methods to cope with the challenge of unknown rank. We provide the first convergence guarantee for the general tensor-on-tensor regression.
  arXiv  Detail & Related papers  (2022-06-17T13:15:27Z)
• Experimental Design for Linear Functionals in Reproducing Kernel Hilbert Spaces [102.08678737900541]
  We provide algorithms for constructing bias-aware designs for linear functionals. We derive non-asymptotic confidence sets for fixed and adaptive designs under sub-Gaussian noise.
  arXiv  Detail & Related papers  (2022-05-26T20:56:25Z)
• Optimally tackling covariate shift in RKHS-based nonparametric regression [43.457497490211985]
  We show that a kernel ridge regression estimator with a carefully chosen regularization parameter is minimax rate-optimal. We also show that a naive estimator, which minimizes the empirical risk over the function class, is strictly sub-optimal. We propose a reweighted KRR estimator that weights samples based on a careful truncation of the likelihood ratios.
  arXiv  Detail & Related papers  (2022-05-06T02:33:24Z)
• Meta-Learning Hypothesis Spaces for Sequential Decision-making [79.73213540203389]
  We propose to meta-learn a kernel from offline data (Meta-KeL) Under mild conditions, we guarantee that our estimated RKHS yields valid confidence sets. We also empirically evaluate the effectiveness of our approach on a Bayesian optimization task.
  arXiv  Detail & Related papers  (2022-02-01T17:46:51Z)
• 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)
• Oversampling Divide-and-conquer for Response-skewed Kernel Ridge Regression [20.00435452480056]
  We develop a novel response-adaptive partition strategy to overcome the limitation of the divide-and-conquer method. We show the proposed estimate has a smaller mean squared error (AMSE) than that of the classical dacKRR estimate under mild conditions.
  arXiv  Detail & Related papers  (2021-07-13T04:01:04Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)
• Early stopping and polynomial smoothing in regression with reproducing kernels [2.0411082897313984]
  We study the problem of early stopping for iterative learning algorithms in a reproducing kernel Hilbert space (RKHS) We present a data-driven rule to perform early stopping without a validation set that is based on the so-called minimum discrepancy principle. The proposed rule is proved to be minimax-optimal over different types of kernel spaces.
  arXiv  Detail & Related papers  (2020-07-14T05:27:18Z)
• Optimal Rates of Distributed Regression with Imperfect Kernels [0.0]
  We study the distributed kernel regression via the divide conquer and conquer approach. We show that the kernel ridge regression can achieve rates faster than $N-1$ in the noise free setting.
  arXiv  Detail & Related papers  (2020-06-30T13:00:16Z)

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.