跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 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.

查看此版本解读 →查看此版本原文 ↗