改进了核方法在模型不匹配时的理论保证,显著降低误差放大。
Sharper Guarantees for Misspecified Kernelized Bandit Optimization
- 通过谱局部化和域分割,控制不匹配误差传播
- 离线与在线场景下,不匹配项增长从平方根降至对数级
- 适用于高维核函数优化,理论更紧致实用
现有核化带宽优化的误差界中,不匹配程度ε会随核有效维数√d_eff或最大信息增益√γ_n放大。本文针对一大类核函数证明,可通过谱局部化与域分割机制将误差放大降至对数或多项式对数级。离线情况下,基于谱Lebesgue常数建立了高概率单次后悔界,一维单调谱下为对数增长,多维傅里叶对角乘积核为多项式对数增长。在线情况下,修改域分割算法,在弱局部特征衰减假设下,实现累积后悔界~O(√γ_n n + nε),消除了原界中额外的√γ_n因子。核心思想是局部化:谱局部化控制离线近似算子的Lebesgue常数,域分割则在在线场景中实现空间上的局部化,防止局部误差全局放大。
原文摘要 · Abstract (English)
Existing guarantees for misspecified kernelized bandit optimization pay for misspecification through kernel complexity: in generic offline bounds, the misspecification level $\varepsilon$ is multiplied by $\sqrt{d_\mathrm{eff}}$, where $d_\mathrm{eff}$ is the kernel effective dimension, while in online regret bounds, the corresponding penalty is $\sqrt{γ_n}\,n\varepsilon$, where $γ_n$ is the maximum information gain after $n$ rounds of interaction. In this work, we show that, for a large class of kernels, the misspecification amplification can be reduced to logarithmic or polylogarithmic growth. In the offline setting, we first prove high-probability simple-regret bounds whose misspecification term is governed by a spectral Lebesgue constant. This yields logarithmic amplification for one-dimensional monotone spectra and polylogarithmic amplification for multivariate Fourier-diagonal product kernels. In the online setting, we modify a domain-splitting algorithm and prove a cumulative regret bound of $\widetilde{\mathcal O}(\sqrt{γ_n n}+n\varepsilon)$ under mild localized eigendecay assumptions, removing the extra $\sqrt{γ_n}$ factor from the misspecification term. The common principle is localization: spectral localization controls the Lebesgue constant of the offline approximation operator, while domain splitting implements the spatial analogue of this mechanism in the online setting, preventing local misspecification errors from being amplified globally.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。