针对延迟反馈的在线优化,提出新算法实现更优的误差控制。
Exploiting Curvature in Online Convex Optimization with Delayed Feedback
- 利用损失函数曲率设计改进的正则化跟踪算法
- 最大缺失观测数下误差界为σ_max ln T,总延迟下为√d_tot
- 适用于有曲率的损失场景,适合在线学习研究者
本文研究具有曲率损失和延迟反馈的在线凸优化问题。当损失函数强凸时,现有方法的误差界为 d_max ln T(d_max 为最大延迟,T 为时间范围),但常劣于延迟版在线梯度下降的 √d_tot(d_tot 为总延迟)。本文提出一种改进的跟随正则化领导者算法,实现误差界 min{σ_max ln T, √d_tot},其中 σ_max 为最大缺失观测数。进一步针对指数凹损失,扩展在线牛顿步算法并引入自适应学习率,获得误差界 min{d_max n ln T, √d_tot}(n 为维度),这是首个在指数凹损失下达到此界的方法。针对无约束线性回归,通过剪裁技巧改进 Vovk-Azoury-Warmuth 预测器,同样获得类似性能。实验验证了算法在多种延迟和损失设置下的优越表现。
原文摘要 · Abstract (English)
In this work, we study the online convex optimization problem with curved losses and delayed feedback. When losses are strongly convex, existing approaches obtain regret bounds of order $d_{\max} \ln T$, where $d_{\max}$ is the maximum delay and $T$ is the time horizon. However, in many cases, this guarantee can be much worse than $\sqrt{d_{\mathrm{tot}}}$ as obtained by a delayed version of online gradient descent, where $d_{\mathrm{tot}}$ is the total delay. We bridge this gap by proposing a variant of follow-the-regularized-leader that obtains regret of order $\min\{σ_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}$, where $σ_{\max}$ is the maximum number of missing observations. We then consider exp-concave losses and extend the Online Newton Step algorithm to handle delays with an adaptive learning rate tuning, achieving regret $\min\{d_{\max} n\ln T, \sqrt{d_{\mathrm{tot}}}\}$ where $n$ is the dimension. To our knowledge, this is the first algorithm to achieve such a regret bound for exp-concave losses. We further consider the problem of unconstrained online linear regression and achieve a similar guarantee by designing a variant of the Vovk-Azoury-Warmuth forecaster with a clipping trick. Finally, we implement our algorithms and conduct experiments under various types of delay and losses, showing an improved performance over existing methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。