Adaptivity and Optimality: A Universal Algorithm for Online Convex Optimization
This work addresses the limitation of existing universal methods in online convex optimization, which are only optimal for subclasses of loss functions, by providing a more broadly applicable solution for researchers and practitioners in machine learning.
The paper tackles the problem of designing a universal algorithm for online convex optimization that achieves optimal regret bounds across multiple types of loss functions, and the proposed method, Maler, achieves optimal O(√T), O(d log T), and O(log T) regret bounds for general convex, exponentially concave, and strongly convex functions, respectively.
In this paper, we study adaptive online convex optimization, and aim to design a universal algorithm that achieves optimal regret bounds for multiple common types of loss functions. Existing universal methods are limited in the sense that they are optimal for only a subclass of loss functions. To address this limitation, we propose a novel online method, namely Maler, which enjoys the optimal $O(\sqrt{T})$, $O(d\log T)$ and $O(\log T)$ regret bounds for general convex, exponentially concave, and strongly convex functions respectively. The essential idea is to run multiple types of learning algorithms with different learning rates in parallel, and utilize a meta algorithm to track the best one on the fly. Empirical results demonstrate the effectiveness of our method.