Improved Impossible Tuning and Lipschitz-Adaptive Universal Online Learning with Gradient Variations
This work addresses a foundational problem in online learning theory by providing a solution to an open problem in achieving optimal adaptivity, which is incremental but resolves key limitations in prior algorithms.
The paper tackles the challenge of achieving simultaneous adaptivity to gradient variation, function curvature, and gradient scales in online learning, which is hindered by sub-optimal algorithms for prediction with expert advice. It proposes a novel optimistic online mirror descent algorithm that resolves the 'impossible tuning' issue, reducing the regret bound gap from √log T to log log T factors, and uses this to develop the first universal online learning algorithm achieving state-of-the-art gradient variation bounds and Lipschitz adaptivity.
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.