stat.MLNov 15, 2026

Tight Sequential Confidence Intervals for Online Kernel Regression

Authors: Haichen Hu, David Simchi-Levi

Organizations: Center for Computational Science and Engineering, MIT · Department of Civil and Environmental Engineering, MIT · Institute for Data, Systems, and Society, MIT

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 yi=f(xi)+εiy_i=f(x_i)+ε_i at adaptively chosen points, with ∥f∥Hk≤B\|f\|_{\mathcal H_k}\le B and i.i.d. RR-sub-Gaussian noise, and reports the interval ∣f(x)−μn(x)∣≤ρn(δ)σn(x)|f(x)-μ_n(x)|\leρ_n(δ)σ_n(x), where μnμ_n and σnσ_n are the posterior mean and standard deviation of a surrogate Gaussian process model with regularization parameter λλ. Writing ρn∗(δ)ρ_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 nn, and all δ∈(0,1/4]δ\in(0,1/4], ρn∗(δ)≍B+(R/λ)γn+log⁡(1/δ)ρ_n^*(δ)\asymp B+(R/λ)\sqrt{γ_n+\log(1/δ)}, where γnγ_n is the maximal information gain and grows polynomially in nn. 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/λ)γn)Ω(B+(R/λ)\sqrt{γ_n}) with constant probability. This rules out the conjectured polylogarithmic width in the worst case over kernels and online designs.

Explore similar work

May 7, 2026

Optimal Confidence Band for Kernel Gradient Flow Estimator

In this paper, we investigate the supremum-norm generalization error and the uniform inference for a specific class of kernel regression methods, namely the kernel gradient flows. Under the widely adopted capacity-source condition framework in the kernel regression literature, we first establish convergence rates for the supremum norm generalization error of both continuous and discrete kernel gradient flows under the source condition s>α0s>α_0, where α0∈(0,1)α_0\in(0,1) denotes the embedding index of the kernel function. Moreover, we show that these rates match the minimax optimal rates. Building on this result, we then construct simultaneous confidence bands for both continuous and discrete kernel gradient flows. Notably, the widths of the proposed confidence bands are also optimal, in the sense that their shrinkage rates are greater than, while can be arbitrarily close to, the minimax optimal rates.
Oct 8, 2026

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

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γ_T. In particular, the best existing upper bounds scale as TγT\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 Ω(TγT/log⁡T)Ω(\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 Θ(TγT)Θ(\sqrt{Tγ_T}) (i.e., within constant factors) for the Matérn-νν kernel with ν∈(0,2)ν\in (0,2), γγ-exponential kernel with γ∈(0,2)γ\in (0,2), and certain piecewise-polynomial kernels.
May 10, 2026

On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise

Providing non-conservative uncertainty quantification for function estimates derived from noisy observations remains a fundamental challenge in statistical machine learning, particularly for applications in safety-critical domains. In this work, we propose novel non-asymptotic probabilistic uniform error bounds for kernel-based regression. Compared to related bounds in the literature that are restricted to (conditionally) independent sub-Gaussian noise, our bounds allow to consider a broad class of non-Gaussian distributions, such as sub-Gaussian, bounded, sub-exponential, and variance/moment-bounded noise. Moreover, our results apply to correlated and uncorrelated noise. We compare our proposed error bounds with existing results in terms of the induced uncertainty region and their performance in safe control, demonstrating the tightness of the proposed bounds.