On the Pinsker bound of inner product kernel regression in large dimensions

• URL: http://arxiv.org/abs/2409.00915v1
• Date: Mon, 2 Sep 2024 03:01:56 GMT
• Title: On the Pinsker bound of inner product kernel regression in large dimensions
• Authors: Weihao Lu, Jialin Ding, Haobo Zhang, Qian Lin,
• Abstract summary: We investigate the Pinsker bound for inner product kernel regression on the sphere $mathbbSd$. We have determined the exact minimax risk for kernel regression in this setting, not only identifying the minimax rate but also the exact constant, known as the Pinsker constant, associated with the excess risk.
• Score: 8.591920836556772
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Building on recent studies of large-dimensional kernel regression, particularly those involving inner product kernels on the sphere $\mathbb{S}^{d}$, we investigate the Pinsker bound for inner product kernel regression in such settings. Specifically, we address the scenario where the sample size $n$ is given by $\alpha d^{\gamma}(1+o_{d}(1))$ for some $\alpha, \gamma>0$. We have determined the exact minimax risk for kernel regression in this setting, not only identifying the minimax rate but also the exact constant, known as the Pinsker constant, associated with the excess risk.

Related papers

• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• The phase diagram of kernel interpolation in large dimensions [8.707305374058794]
  generalization ability of kernel in large dimensions might be one of the most interesting problems in the recent renaissance of kernel regression. We fully characterized the exact order of both the variance and bias of large-dimensional kernel under various source conditions $sgeq 0$. We determined the regions in $(s,gamma)$-plane where the kernel is minimax optimal, sub-optimal and inconsistent.
  arXiv  Detail & Related papers  (2024-04-19T03:04:06Z)
• Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensions [15.988264513040903]
  We study the large-dimensional behavior of kernel ridge regression (KRR) where the sample size $n asymp dgamma$ for some $gamma > 0$. Our results illustrate that the curves of rate varying along $gamma$ exhibit the periodic plateau behavior and the multiple descent behavior.
  arXiv  Detail & Related papers  (2024-01-02T16:14:35Z)
• Optimal Rate of Kernel Regression in Large Dimensions [13.641780902673792]
  We first build a general tool to characterize the upper bound and the minimax lower bound of kernel regression for large dimensional data. We utilize the new tool to show that the minimax rate of the excess risk of kernel regression is $n-1/2$ when $nasymp dgamma$ for $gamma =2, 4, 6, 8, cdots$.
  arXiv  Detail & Related papers  (2023-09-08T11:29:05Z)
• A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [50.90125395570797]
  This nearly establishes a conjecture ofciteSaundersonCPW12, within logarithmic factors. The latter conjecture has attracted significant attention over the past decade, due to its connections to machine learning and sum-of-squares lower bounds for certain statistical problems.
  arXiv  Detail & Related papers  (2022-12-21T17:48:01Z)
• 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)
• How rotational invariance of common kernels prevents generalization in high dimensions [8.508198765617196]
  Kernel ridge regression is well-known to achieve minimax optimal rates in low-dimensional settings. Recent work establishes consistency for kernel regression under certain assumptions on the ground truth function and the distribution of the input data.
  arXiv  Detail & Related papers  (2021-04-09T08:27:37Z)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  We derive the regret upper bounds on the classes of Sobolev spaces $W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases $beta> fracd2$ or $p=infty$ these rates are (essentially) optimal.
  arXiv  Detail & Related papers  (2021-02-06T15:05:14Z)
• Sinkhorn Barycenter via Functional Gradient Descent [125.89871274202439]
  We consider the problem of computing the barycenter of a set of probability distributions under the Sinkhorn divergence. This problem has recently found applications across various domains, including graphics, learning, and vision. We develop a novel functional gradient descent method named Sinkhorn Descent.
  arXiv  Detail & Related papers  (2020-07-20T20:16:47Z)
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data [10.739602293023058]
  We study the risk (i.e. generalization error) of Kernel Ridge Regression (KRR) for a kernel $K$ with ridge $lambda>0$ and i.i.i.d. observations. We introduce two objects: the Signal Capture Threshold (SCT) and the Kernel Alignment Risk Estimator (KARE)
  arXiv  Detail & Related papers  (2020-06-17T12:00:05Z)
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
  We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards. We empirically validate our approach in continuous MDPs with sparse rewards.
  arXiv  Detail & Related papers  (2020-04-12T12:23:46Z)

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.