Tight Sequential Confidence Intervals for Online Kernel Regression

Haichen Hu, David Simchi-LeviarXiv 2026 · arXiv

TL;DR

This paper settles a long-standing open problem in online kernel regression by proving that the "inflation" seen in sequential confidence intervals is a fundamental statistical limit, not just a loose analysis. The authors show that for adaptive designs, the confidence width must scale with the square root of the maximal information gain ($\sqrt{\gamma_n}$), ruling out the possibility of tighter polylogarithmic bounds in the worst case.

What Problem Does This Paper Address?

In kernel regression, we try to estimate an unknown function $f$ that lives in a Reproducing Kernel Hilbert Space (RKHS). A common way to quantify our uncertainty is through confidence intervals.

In the offline setting (where data points are chosen in advance), these intervals are quite tight, typically depending only logarithmically on the number of samples $n$. However, in the online setting (common in bandits and reinforcement learning), the learner chooses the next point $x_{i+1}$ based on previous observations. Existing theory for this adaptive setting included an extra $\sqrt{\gamma_n}$ term (where $\gamma_n$ is the maximal information gain).

Researchers wondered: Is this $\sqrt{\gamma_n}$ term a necessary evil of adaptive sampling, or just a sign that our math wasn't sharp enough? This paper proves it is necessary.

Methods

The authors resolve the problem by constructing a "hard instance"—a specific scenario where the learner is guaranteed to have a large error unless the confidence interval is wide.

  1. The Hard Kernel: They construct a composite kernel for a 2D domain. It combines a linear kernel (representing a simple global trend) and a periodic Sobolev kernel (representing high-frequency local fluctuations).
  2. Adaptive Design: Building on recent work by Lattimore (2023), they design a specific sequential sampling strategy. This strategy uses past noise to "steer" the estimate of the linear component, effectively tricking the learner.
  3. Minimax Analysis: They define the minimax confidence width $\rho_n^*(\delta)$—the smallest width that guarantees a specific success probability across all possible functions and noise laws—and prove a lower bound that matches the existing upper bounds.

Datasets

As a theoretical paper focused on proving fundamental limits, no real-world datasets were used. The results are derived through mathematical proofs based on a constructed synthetic environment:

  • Domain: A fixed two-dimensional space $\mathcal{X} = [-1, 1] \times [0, 2\pi]$.
  • Function Class: An RKHS defined by the sum of a linear and a periodic Sobolev kernel.

Key Insights and Ideas

  • Adaptivity is a Double-Edged Sword: While choosing points adaptively helps us learn faster in some cases, it also allows the "noise" to influence where we sample. This dependency creates a statistical bias that forces confidence intervals to be wider by a factor of $\sqrt{\gamma_n}$.
  • Information Gain Matters: The term $\gamma_n$ measures how much information we can extract about a function from $n$ points. For complex kernels (like Sobolev or Matérn), $\gamma_n$ grows polynomially with $n$, meaning the "online inflation" is significant.
  • Justification for Batching: This result explains why many state-of-the-art kernel bandit algorithms (like SupKernelUCB) use "batching" or "elimination" strategies. By collecting data in fixed batches, they temporarily act like an offline learner, allowing them to use tighter confidence intervals and achieve better regret bounds.

Key Results

The paper proves that for their constructed kernel, the sharp minimax width $\rho_n^*(\delta)$ satisfies: $$\rho_n^*(\delta) \asymp B + \frac{R}{\lambda}\sqrt{\gamma_n + \log \frac{1}{\delta}}$$ Where:

  • $B$ is the bound on the function's RKHS norm.
  • $R$ is the noise level.
  • $\lambda$ is the regularization parameter.
  • $\gamma_n$ is the maximal information gain.

For their specific Sobolev-based kernel, $\gamma_n$ grows as $n^{1/(2s)}$, leading to a confidence width that grows as $n^{1/(4s)}$. This confirms that the $\sqrt{\gamma_n}$ dependence is unavoidable in the discrete-time, worst-case over kernels setting.

Limitations and Future Work

  • Kernel Specificity: The lower bound is proven for a specific constructed kernel (linear + Sobolev). It remains an open question whether standard, widely-used kernels like the Matérn or Squared Exponential (RBF) kernels alone exhibit this same inflation at a single point.
  • Design-Specific Analysis: The result is a minimax lower bound (worst-case over all possible online designs). It doesn't rule out the possibility that specific clever online designs could achieve tighter intervals for certain problems.
  • Data-Driven Widths: The authors suggest that future work could look into constructing "data-dependent" widths that adapt to the actual design realized during the experiment, potentially offering tighter bounds in practice.

Summary updated

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.
BibTeX
@misc{hu2026tight,
  author = {Haichen Hu and David Simchi-Levi},
  title = {{Tight Sequential Confidence Intervals for Online Kernel Regression}},
  year = {2026},
  eprint = {2611.19772},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19772},
}
Figure