Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality
Yu-Hu Yan, Peng Zhao, Zhi-Hua Zhou
In this work, we study offline convex optimization with smooth objectives, where the classical Nesterov's Accelerated Gradient (NAG) method achieves the optimal accelerated convergence. Extensive research has aimed to understand NAG from various perspectives. A recent line of work approaches this from the viewpoint of online learning and online-to-batch conversion, emphasizing the role of *optimistic algorithms* for acceleration. In this work, we contribute to this perspective by proposing novel *optimistic online-to-batch conversions* that incorporate optimism theoretically into the analysis, thereby significantly simplifying the algorithm design while preserving the optimal convergence rates. Specifically, we demonstrate the effectiveness of our conversions through the following results: *(i)* when combined with simple online gradient descent, our optimistic conversion achieves the optimal accelerated convergence; *(ii)* our conversion also applies to strongly convex objectives, achieving the optimal accelerated convergence rate; *(iii)* our optimistic conversion can achieve universality to smoothness --- applicable to both smooth and non-smooth objectives without requiring knowledge of the smoothness parameter --- and remains efficient as non-universal methods by using only one gradient query in each iteration. Finally, we explain the effectiveness of our optimistic online-to-batch conversions by a precise correspondence with NAG.