
HH
Haichen Hu, David Simchi-Levi
· 1 min read
ResearcharXiv cs.LG
Tight Sequential Confidence Intervals for Online Kernel Regression
arXiv:2611.19772v1 Announce Type: cross
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)+\epsilon_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)-\mu_n(x)|\le\rho_n(\delta)\sigma_n(x)$, where $\mu_n$ and $\sigma_n$ are the posterior mean and standard deviation of a surrogate Gaussian process model with regularization parameter $\lambda$. Writing $\rho_n^*(\delta)$ 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 $\delta\in(0,1/4]$, $\rho_n^*(\delta)\asymp B+(R/\lambda)\sqrt{\gamma_n+\log(1/\delta)}$, where $\gamma_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 $\Omega(B+(R/\lambda)\sqrt{\gamma_n})$ with constant probability. This rules out the conjectured polylogarithmic width in the worst case over kernels and online designs.
Original source
This story was published by arXiv cs.LG and written by Haichen Hu, David Simchi-Levi. SyncAI.news shows a preview; the complete article is on the publisher's site.
Read the full story on arxiv.org


