← 研踪 PaperTrailarXiv:2611.19772 · v1
Tight Sequential Confidence Intervals for Online Kernel Regression
首次提交 2026-11-15 11:58
版本更新 2026-11-15 11:58
雷达观测 2026-11-17 12:06
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-15 11:58 · 最新观测版本
Tight Sequential Confidence Intervals for Online Kernel Regression
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.
查看此版本解读 →查看此版本原文 ↗