解决在线学习中自适应难题,首次实现梯度变化与光滑性同步最优。
Improved Impossible Tuning and Lipschitz-Adaptive Universal Online Learning with Gradient Variations
- 设计新算法,通过辅助初始轮次和大学习率消除误差项
- 首次实现梯度变化与光滑性自适应的最优上界,无额外对数因子
- 适合研究在线学习理论或需高鲁棒性算法的科研人员
在线学习的核心目标是自适应未知问题特性,如梯度变化(GV)、函数曲率(通用在线学习,UOL)和梯度尺度(Lipschitz自适应,LA)。同时达到这些自适应且保持最优性能是重大挑战,部分源于预测专家建议算法的局限性。现有解决“不可能调参”问题的算法在后悔界中比下界多出一个√log T因子。本文提出一种新型乐观在线镜面下降算法,引入大学习率的辅助初始轮次,通过生成负项抵消间隙相关因子,将“不可能调参”问题解决至log log T因子范围内。以此改进算法为元算法,我们构建了首个同时实现最优GV边界和LA的UOL算法,在标准假设下取得突破。该结果克服了先前工作的关键限制,尤其解决了LA机制与GV后悔分析之间的矛盾——这是Xie等人指出的开放问题。
原文摘要 · Abstract (English)
A central goal in online learning is to achieve adaptivity to unknown problem characteristics, such as environmental changes captured by gradient variation (GV), function curvature (universal online learning, UOL), and gradient scales (Lipschitz adaptivity, LA). Simultaneously achieving these with optimal performance is a major challenge, partly due to limitations in algorithms for prediction with expert advice. These algorithms often serve as meta-algorithms in online ensemble frameworks, and their sub-optimality hinders overall UOL performance. Specifically, existing algorithms addressing the ``impossible tuning'' issue incur an excess $\sqrt{\log T}$ factor in their regret bound compared to the lower bound. To solve this problem, we propose a novel optimistic online mirror descent algorithm with an auxiliary initial round using large learning rates. This design enables a refined analysis where a generated negative term cancels the gap-related factor, resolving the impossible tuning issue up to $\log\log T$ factors. Leveraging our improved algorithm as a meta-algorithm, we develop the first UOL algorithm that simultaneously achieves state-of-the-art GV bounds and LA under standard assumptions. Our UOL result overcomes key limitations of prior works, notably resolving the conflict between LA mechanisms and regret analysis for GV bounds -- an open problem highlighted by Xie et al.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。