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

CardsList
  1. Optimal Confidence Band for Kernel Gradient Flow Estimator

    May 7, 2026Yuqian Cheng, Zhuo Chen, Qian LinKernel RegressionKernel Methods

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

    May 10, 2026Johannes Teutsch, Oleksii Molodchyk, Marion Leibold +2Kernel RegressionUncertainty Quantification