CS Paper Radar

Tight Sequential Confidence Intervals for Online Kernel Regression

Haichen Hu, David Simchi-Levi

cs.LG stat.MLmath.PR ·submitted 2026-11-15 03:58 UTC · v1

Abstract

We characterize, in the worst case over kernels, the sharp minimax width of online confidence intervals for elements of a reproducing kernel Hilbert space (RKHS). This resolves the open problem posed by Vakili et al. (2021) in its original discrete-time form. A learner observes $y_i=f(x_i)+ε_i$ at adaptively chosen points, with $\|f\|_{\mathcal H_k}\le B$ and i.i.d. $R$-sub-Gaussian noise, and reports the interval $|f(x)-μ_n(x)|\leρ_n(δ)σ_n(x)$, where $μ_n$ and $σ_n$ are the posterior mean and standard deviation of a surrogate Gaussian process model with regularization parameter $λ$. Writing $ρ_n^*(δ)$ for the minimax confidence width for a fixed kernel, we show that, for the sum of a linear kernel and a periodic Sobolev kernel, all sufficiently large $n$, and all $δ\in(0,1/4]$, $ρ_n^*(δ)\asymp B+(R/λ)\sqrt{γ_n+\log(1/δ)}$, where $γ_n$ is the maximal information gain and grows polynomially in $n$. Building on Lattimore (2023), we construct an adaptive design on a fixed two-dimensional domain for which, under Gaussian noise, the normalized error at a prespecified point is $Ω(B+(R/λ)\sqrt{γ_n})$ with constant probability. This rules out the conjectured polylogarithmic width in the worst case over kernels and online designs.

Closest papers

Nearest neighbours by meaning across the whole index.

MiNCE: Nonparametric, Strongly Consistent Confidence Envelopes for Band-Limited Functions and their Smoothed Spectra

cs.LG math.STeess.SPstat.ME+1 ·2026-09-08 ·Balázs Csanád Csáji, Bálint Horváth
similarity 0.67
Abstract

Minimum-norm confidence envelope strategies offer a nonparametric approach to constructing nonasymptotic, simultaneous confidence regions for band-limited functions, exploiting the theory of Reproducing Kernel Hilbert Spaces (RKHS). While the finite-sample coverage guarantees of these envelopes have been established, their consistency has not been analyzed so far. In this paper, we study this construction, here termed the Minimum-Norm Confidence Envelope (MiNCE) framework, and establish the strong uniform consistency of the resulting bands, both for noise-free and noisy observation models, under mild assumptions on the measurement noises. We further extend this formulation to the frequency domain, deriving nonasymptotic, simultaneous, strongly uniformly consistent confidence bands for the smoothed spectra. Numerical experiments in nonparametric regression and spectral estimation empirically confirm our theoretical results, illustrating the contraction of the confidence envelopes toward the target function as the sample size increases.

0.29

Unbounded Characteristic and Universal Kernels

cs.LG math.STstat.ML ·2026-10-07 ·Jose Cribeiro-Ramallo, Florian Kalinke, Zoltán Szabó
similarity 0.64
Abstract

Kernel methods are among the most powerful tools in machine learning and statistics, with a large number of successful applications. Their immense success stems from the flexible function class associated to each kernel---its reproducing kernel Hilbert space (RKHS)---which facilitates statistical analysis, as well as from their computational tractability and applicability to many domains. Multiple notions (such as characteristic, $L_p$-universal, and integrally strictly positive definite) capture the expressivity of kernels and their RKHSs and play a key role in understanding the statistical properties of kernel methods; these concepts and their relations are well-understood for bounded kernels. Even though unbounded kernels have received significant attention over the past decade (for instance, in the construction of kernel-based discrepancy and dependence measures such as the maximum mean discrepancy, the Hilbert-Schmidt independence criterion, and the kernel Stein discrepancy), surprisingly little is known about the relations of these notions in the unbounded case. In the present paper we tackle this severe bottleneck, establishing their relations under mild assumptions.

0.18

A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits

cs.IT stat.MLcs.LG ·2026-10-08 ·Chenkai Ma, Jonathan Scarlett
theory similarity 0.63
Abstract

The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Space (RKHS). A central quantity in the regret analysis of kernel bandits is the maximum information gain $γ_T$. In particular, the best existing upper bounds scale as $\sqrt{Tγ_T}$ up to log factors, and nearly-matching lower bounds have been derived for specific kernels such as squared exponential and Matérn. However, lower bounds for general kernels are lacking, thus making it unclear in what generality the upper bounds are near-optimal. In this paper, we establish a general $Ω(\sqrt{Tγ_T/\log T})$ minimax regret lower bound for non-constant continuous kernels on compact domains, establishing near-optimality (within log factors) in a very general sense. We show that the log factor appearing in this bound is unavoidable in general, but that it can be removed under certain conditions. Among other things, our findings imply that the minimax-optimal scaling is exactly $Θ(\sqrt{Tγ_T})$ (i.e., within constant factors) for the Matérn-$ν$ kernel with $ν\in (0,2)$, $γ$-exponential kernel with $γ\in (0,2)$, and certain piecewise-polynomial kernels.

0.21

On the Optimality of Random Features under General Conditions: Misspecified Cases and Robust Learning

cs.LG stat.ML ·2026-10-13 ·Caixing Wang
similarity 0.62
Abstract · 61 pages, 10 figures, 2 tables

Random features provide a standard approach to scaling kernel methods to large datasets by approximating the kernel with a finite-dimensional feature map. Existing works of random feature methods primarily focus on well-specified models and light-tailed noise conditions, leaving a gap in understanding their performance under more general conditions, such as misspecified models and heavy-tailed noise. In this paper, we provide a comprehensive and improved analysis of kernel ridge regression with random features (KRR-RF) under general conditions. In the light-tailed noise setting, we improve upon the worst-case uniform bounds of the feature map used in the previous works and lead to the minimax optimal learning rates with $2r+γ>α_0$, where $(r,γ,α_0)$ denote the regularity of the target function, the effective dimension of the kernel, and the embedding index of the RKHS, respectively. In the heavy-tailed noise setting, we leverage a recently developed Hilbert-valued Fuk-Nagaev inequality and extend the same optimal results under finite weak moment conditions. The additional cost to achieve robustness is a mildly stronger explicit sample-size requirement than in the light-tailed case. For both settings, our results recover the conditions random features budgets (up to log factors) required in the previous works. In the most benign case when $α_0=γ$, KRR-RF are minimax optimal for all $r \in (0,1]$. To the best of our knowledge, this is the first work to establish optimal learning rates for KRR-RF under weak moment conditions in the misspecified setting. Numerical experiments and a real data analysis validate the derived learning rates and demonstrate their practical relevance in the presence of mis-specification and heavy-tailed noise.

0.24

Random Projections for Spectral Algorithms: Optimal Rates in Sobolev Norms

cs.LG stat.ML ·2026-10-22 ·Caixing Wang, Yue Wang
similarity 0.62
Abstract

Random projections (RP) offer an effective method for reducing computational and storage overhead while preserving the geometric structure of data. However, existing studies have primarily focused on the optimal generalization performance of specific kernel-regularized algorithms with RP in the well-specified setting and under restrictive conditions. In this paper, we provide a comprehensive and improved analysis of the generalization performance of RP-based spectral algorithms under general conditions \change{without sacrificing statistical efficiency}. By leveraging the embedding property of the reproducing kernel Hilbert space (RKHS) and a refined analysis of the operator similarity, we establish optimal learning rates in Sobolev norms that match the minimax lower bounds up to logarithmic factors. For two common implementations of RP, randomized sketches and Nyström sub-sampling (uniform or leverage-based), we show that the projection dimension required for optimality is proportional to the average or maximal effective dimension, yielding a significant reduction in computational cost while maintaining the statistical efficiency. Our results do not rely on the uniform boundedness assumption on the regression function and are valid across a wide range of source conditions, i.e., $s> α_0-1/β$, where $s,β$, and $α_0$ denote the smoothness index, capacity index, and the embedding index, respectively. In the benign case when $α_0=1/β$, the optimality holds for all $s\in (0,2τ]$ with $τ$ and $γ$ denoting the qualification index and norm index. Experimental results demonstrate both the theoretical validity and the practical effectiveness of the proposed method.

0.29

Convergence Rates of Gaussian Process Thompson Sampling for Efficient Global Optimization

cs.LG stat.ML ·2026-10-14 ·Haowei Wang, Yilin Zheng
theoryhot direction similarity 0.61
Abstract

Efficient global optimization aims to identify a global optimum of an expensive black-box function within a limited evaluation budget $N$. We investigate the convergence rates of Gaussian process Thompson sampling (GP-TS) under noiseless observations, assuming a fixed objective function in a reproducing kernel Hilbert space (RKHS). For Matérn kernels with smoothness parameter $ν$ in dimension $d$, we establish a worst-case expected simple-regret upper bound of $O(N^{-ν/d}\sqrt{\log N})$ for both discrete GP-TS on sufficiently fine grids and its continuous counterpart. For the continuous implementation, we develop a nested-grid argument to control posterior sample paths over the entire domain. We further establish matching lower bounds of $Ω(N^{-5/2}\sqrt{\log N})$ for both implementations under a fixed one-dimensional Matérn-$5/2$ kernel, demonstrating that the logarithmic penalty is intrinsic to standard GP-TS in this setting. Motivated by this limitation, we propose Gaussian Process Capped Thompson Sampling (GP-CTS), which caps posterior sample paths using a valid RKHS norm upper bound while preserving optimism. This modification successfully eliminates the logarithmic penalty and achieves the minimax-optimal rate $Θ(N^{-ν/d})$ for both discrete and continuous implementations.

0.28

Near-Linear Accuracy Bounds for Moreau--Yosida Unadjusted Langevin Sampling

cs.LG ·2026-09-30 ·Yuchen Xin, Zhihua Zhang
similarity 0.59
Abstract

We establish near-linear accuracy bounds for the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA). The target is $π\propto e^{-f-g}$, where $f\in C^2(\mathbb{R}^d)$ is $m$-strongly convex with Lipschitz gradient and $g$ is convex and globally Lipschitz. Under an explicit parameter-dependent step-size condition, we bound the invariant-measure bias relative to the Moreau-smoothed target by $\widetilde O(h)$, with only logarithmic dependence on the inverse smoothing parameter in the error coefficient. Combining this estimate with the Moreau approximation bias and Wasserstein contraction gives $\widetilde O(\varepsilon^{-1})$ iterations to make the $N$th-iterate law $μ_N$ satisfy $\sqrt m\,W_2(μ_N,π)\le\varepsilon$, for fixed model parameters and initialization. We bound the stationary error directly, without assuming third derivatives or a Lipschitz Hessian. Each iteration uses one gradient evaluation and one exact proximal evaluation. The key idea in our analysis is to convert a second-order stationary residual into a Wasserstein bound using a Poisson-based estimate.

0.07

Reliable Risk Estimation with Kernel Mean Matching under Dependent Sampling

cs.LG ·2026-10-13 ·Alexey Zaytsev, Diana Koldasbayeva, Egor Serov
similarity 0.59
Abstract · 35 pages, 6 figures

Kernel Mean Matching (KMM) estimates risk under covariate shift by reweighting labelled source samples so that their kernel mean embedding matches that of unlabeled target samples. Existing finite-sample guarantees are usually stated for independent samples, although many applications involve temporal, spatial, or clustered dependence. We give a finite-sample KMM analysis under dependent sampling by replacing nominal sample sizes with effective sample sizes in the concentration steps used by the classical proof. The approach uses Bernstein inequalities for geometrically strongly mixing processes and derives a model-based effective sample size. The resulting bound separates overlap, dependence, and smoothness effects with specific constants derived under a Gaussian process assumption. This analysis yields an additional tradeoff: smoother losses preserve more input dependence and therefore reduce effective sample size, while also reducing function complexity and empirical-to-population risk gaps. Applying the result to prediction yields confidence intervals that achieve near-nominal coverage in synthetic experiments and substantially reduce undercoverage on real monitoring data.

0.25