新算法同时实现自适应与普适性,自动根据梯度变化调节性能。
Adaptivity and Universality: Problem-dependent Universal Regret for Online Convex Optimization
- 提出UniGrad系列算法,通过元学习框架融合多类函数的最优更新机制。
- 在强凸和指数凹函数下,后悔值随梯度变化量$V_T$对数增长,优于传统方法。
- 可选变体仅需每轮1次梯度查询,兼顾理论性能与实际效率,适合在线优化场景。
通用在线学习旨在不依赖目标函数曲率先验的情况下实现最优后悔界。现有方法已达到极小极大最优后悔界:对凸函数为$\mathcal{O}(\sqrt{T})$,指数凹函数为$\mathcal{O}(d \log T)$,强凸函数为$\mathcal{O}(\log T)$,其中$T$为轮次数,$d$为可行域维度。但这些方法仍缺乏问题依赖的自适应能力,尤其无法依据梯度变化量$V_T$动态调整性能,而$V_T$在随机优化和博弈快速收敛中至关重要。本文提出UniGrad,包含UniGrad.Correct与UniGrad.Bregman两种实现,均实现通用性与自适应性,分别在强凸函数下达到$\mathcal{O}(\log V_T)$,在指数凹函数下达到$\mathcal{O}(d \log V_T)$的后悔界。对于凸函数,UniGrad.Correct实现$\mathcal{O}(\sqrt{V_T \log V_T})$边界并保持关键的RVU性质,利于在线博弈快速收敛;UniGrad.Bregman则通过创新设计获得最优的$\mathcal{O}(\sqrt{V_T})$边界。两者均采用$\mathcal{O}(\log T)$个基础学习器的元算法,每轮需$\mathcal{O}(\log T)$次梯度查询。为提升效率,引入UniGrad++,通过代理优化将梯度查询降至每轮1次,同时保持原有后悔界。本文还探讨了多种应用意义。
原文摘要 · Abstract (English)
Universal online learning aims to achieve optimal regret guarantees without requiring prior knowledge of the curvature of online functions. Existing methods have established minimax-optimal regret bounds for universal online learning, where a single algorithm can simultaneously attain $\mathcal{O}(\sqrt{T})$ regret for convex functions, $\mathcal{O}(d \log T)$ for exp-concave functions, and $\mathcal{O}(\log T)$ for strongly convex functions, where $T$ is the number of rounds and $d$ is the dimension of the feasible domain. However, these methods still lack problem-dependent adaptivity. In particular, no universal method provides regret bounds that scale with the gradient variation $V_T$, a key quantity that plays a crucial role in applications such as stochastic optimization and fast-rate convergence in games. In this work, we introduce UniGrad, a novel approach that achieves both universality and adaptivity, with two distinct realizations: UniGrad.Correct and UniGrad.Bregman. Both methods achieve universal regret guarantees that adapt to gradient variation, simultaneously attaining $\mathcal{O}(\log V_T)$ regret for strongly convex functions and $\mathcal{O}(d \log V_T)$ regret for exp-concave functions. For convex functions, the regret bounds differ: UniGrad.Correct achieves an $\mathcal{O}(\sqrt{V_T \log V_T})$ bound while preserving the RVU property that is crucial for fast convergence in online games, whereas UniGrad.Bregman achieves the optimal $\mathcal{O}(\sqrt{V_T})$ regret bound through a novel design. Both methods employ a meta algorithm with $\mathcal{O}(\log T)$ base learners, which naturally requires $\mathcal{O}(\log T)$ gradient queries per round. To enhance computational efficiency, we introduce UniGrad++, which retains the regret while reducing the gradient query to just $1$ per round via surrogate optimization. We further provide various implications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。