Tight Sequential Confidence Intervals for Online Kernel Regression
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 at adaptively chosen points, with and i.i.d. -sub-Gaussian noise, and reports the interval , where and are the posterior mean and standard deviation of a surrogate Gaussian process model with regularization parameter . Writing 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 , and all , , where is the maximal information gain and grows polynomially in . 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 with constant probability. This rules out the conjectured polylogarithmic width in the worst case over kernels and online designs.
Kernel Regression
Kernel regression uses similarity functions to predict outputs from data, with theory linking kernel choice, regularization, and generalization.
See all 36 papers