改进带梯度变化的在线凸优化维度依赖，提升算法性能
Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations
- 提出非连续梯度变化的精细化分析方法
- 在凸与强凸函数上实现更优的维度依赖性
- 适用于动态、通用最优及博弈场景
梯度变化在线学习因与博弈论、优化等领域的深刻联系而受到越来越多关注。尽管在全信息设置下研究充分，但在带偏反馈下的研究仍不充分。本文聚焦于两点反馈下的带梯度变化的带偏凸优化（BCO）。通过提出对非连续梯度变化这一关键量的精细化分析，我们在凸函数和强凸函数上均改进了现有最佳结果（Chiang et al., 2013）的维度依赖性。该改进分析还带来了其他有利的问题相关保证，如梯度方差与小损失后悔。超越两点设定，我们展示了该技术的通用性，首次实现了在超矩形域上的一点反馈线性优化的梯度变化界。最后，在更具挑战性的任务如动态/通用后悔最小化和带偏博弈中验证了结果的有效性，建立了两点BCO的首个梯度变化动态与通用后悔界，并在带偏博弈中实现快速收敛速率。
原文摘要 · Abstract (English)
Gradient-variation online learning has drawn increasing attention due to its deep connections to game theory, optimization, etc. It has been studied extensively in the full-information setting, but is underexplored with bandit feedback. In this work, we focus on gradient variation in Bandit Convex Optimization (BCO) with two-point feedback. By proposing a refined analysis on the non-consecutive gradient variation, a fundamental quantity in gradient variation with bandits, we improve the dimension dependence for both convex and strongly convex functions compared with the best known results (Chiang et al., 2013). Our improved analysis for the non-consecutive gradient variation also implies other favorable problem-dependent guarantees, such as gradient-variance and small-loss regrets. Beyond the two-point setup, we demonstrate the versatility of our technique by achieving the first gradient-variation bound for one-point bandit linear optimization over hyper-rectangular domains. Finally, we validate the effectiveness of our results in more challenging tasks such as dynamic/universal regret minimization and bandit games, establishing the first gradient-variation dynamic and universal regret bounds for two-point BCO and fast convergence rates in bandit games.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。