提出轻量版在线牛顿法，速度更快且保持最优误差
A Simple, Optimal and Efficient Algorithm for Online Exp-Concave Optimization
- 用域变换技术延迟昂贵的投影计算，降低每轮开销
- 总时间复杂度从O(d^ωT)降至O(d²T + d^ω√(T log T))
- 适合需要高效在线优化的场景，如自适应梯度和带宽学习
在线指数凹优化（OXO）是在线学习中的基础问题，目标是在损失函数为指数凹时最小化累计遗憾。标准算法在线牛顿步（ONS）可达到最优的O(d log T)遗憾，其中d为维度，T为时间范围。然而，由于每轮需进行马哈拉诺比斯投影，其计算瓶颈显著：在有界域上每轮耗时 ilde{O}(d^ω)，总时间可达 ilde{O}(d^ωT)，尤其当迭代频繁接近边界时。本文提出一种简单变体LightONS，将总运行时间降至O(d²T + d^ω√(T log T))，同时保持最优遗憾。结合在线转批量转换，可得随机指数凹优化方法，运行时间 ilde{O}(d³/ε)，解决了Koren [2013]提出的开放问题。该设计借鉴参数无关在线学习中的域变换技巧，仅在必要时执行投影，保留了ONS的简洁结构，使其可作为更广泛场景下的高效替换方案，包括梯度范数自适应、参数化随机老虎机和内存高效的OXO。
原文摘要 · Abstract (English)
Online eXp-concave Optimization (OXO) is a fundamental problem in online learning, where the goal is to minimize regret when loss functions are exponentially concave. The standard algorithm, Online Newton Step (ONS), guarantees an optimal $O(d \log T)$ regret, where $d$ is the dimension and $T$ is the time horizon. Despite its simplicity, ONS may face a computational bottleneck due to the Mahalanobis projection at each round. This step costs $\tilde{O}(d^ω)$ arithmetic operations for bounded domains, even for simple domains such as the unit ball, where $ω\in (2,3]$ is the matrix-multiplication exponent. As a result, the total runtime can reach $\tilde{O}(d^ωT)$, particularly when iterates frequently oscillate near the domain boundary. This paper proposes a simple variant of ONS, called LightONS, which reduces the total runtime to $O(d^2 T + d^ω\sqrt{T \log T})$ while preserving the optimal regret. Deploying LightONS with the online-to-batch conversion implies a method for stochastic exp-concave optimization with runtime $\tilde{O}(d^3/\varepsilon)$, thereby answering an open problem posed by Koren [2013]. The design leverages domain-conversion techniques from parameter-free online learning and defers expensive Mahalanobis projections until necessary, thereby preserving the elegant structure of ONS and enabling LightONS to act as an efficient plug-in replacement in broader scenarios, including gradient-norm adaptivity, parametric stochastic bandits, and memory-efficient OXO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。