Online Adaptive Methods, Universality and Acceleration
This work addresses the need for a universal optimization method that works across different scenarios (smooth, non-smooth, stochastic) without modifications, which is incremental in combining existing adaptive and coupling techniques.
The paper tackles the problem of convex unconstrained optimization by introducing a novel method that simultaneously achieves accelerated convergence for smooth objectives, standard convergence for non-smooth settings, and standard convergence in stochastic optimization, which is the first method to apply to all these settings. The results are supported by theoretical findings and empirical validation.
We present a novel method for convex unconstrained optimization that, without any modifications, ensures: (i) accelerated convergence rate for smooth objectives, (ii) standard convergence rate in the general (non-smooth) setting, and (iii) standard convergence rate in the stochastic optimization setting. To the best of our knowledge, this is the first method that simultaneously applies to all of the above settings. At the heart of our method is an adaptive learning rate rule that employs importance weights, in the spirit of adaptive online learning algorithms (Duchi et al., 2011; Levy, 2017), combined with an update that linearly couples two sequences, in the spirit of (Allen-Zhu and Orecchia, 2017). An empirical examination of our method demonstrates its applicability to the above mentioned scenarios and corroborates our theoretical findings.