提出新方法解决噪声随接近最优而线性减小的凸带权问题
A Regularized Online Newton Method for Stochastic Convex Bandits with Linear Vanishing Noise
- 基于在线牛顿法改进，引入正则化提升稳定性
- 在二次增长损失下实现时间跨度的多对数后悔界
- 适合研究带噪声优化与自适应学习的学者
我们研究一种随机凸带权问题，假设子高斯噪声参数随学习者逐步接近损失函数最小值而线性下降。为此，我们提出一种正则化在线牛顿法（RONM），基于arXiv:2406.06506中的在线牛顿法（ONM）。当损失函数在约束集上呈二次增长时，RONM在时间跨度n上达到多对数后悔界，复现了arXiv:2402.12042在线性带权中的结果。分析依赖于ONM中精度矩阵Σ_t^{-1}的增长率，发现线性增长恰好解决了该问题。该分析还使我们在损失函数增长更快时获得更优收敛速率。此外，我们还研究并分析了两个新带权模型：噪声按子高斯参数函数缩放的随机凸带权，以及具有随机乘性噪声的凸带权。
原文摘要 · Abstract (English)
We study a stochastic convex bandit problem where the subgaussian noise parameter is assumed to decrease linearly as the learner selects actions closer and closer to the minimizer of the convex loss function. Accordingly, we propose a Regularized Online Newton Method (RONM) for solving the problem, based on the Online Newton Method (ONM) of arXiv:2406.06506. Our RONM reaches a polylogarithmic regret in the time horizon $n$ when the loss function grows quadratically in the constraint set, which recovers the results of arXiv:2402.12042 in linear bandits. Our analyses rely on the growth rate of the precision matrix $Σ_t^{-1}$ in ONM and we find that linear growth solves the question exactly. These analyses also help us obtain better convergence rates when the loss function grows faster. We also study and analyze two new bandit models: stochastic convex bandits with noise scaled to a subgaussian parameter function and convex bandits with stochastic multiplicative noise.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。