On the Computational Efficiency of Adaptive and Dynamic Regret Minimization
This work addresses a computational bottleneck for researchers and practitioners in online learning, offering incremental improvements in efficiency for dynamic environments.
The paper tackles the computational inefficiency in adaptive and dynamic regret minimization for online convex optimization, showing how to reduce the computational penalty from logarithmic to doubly logarithmic in game iterations while maintaining near-optimal regret bounds.
In online convex optimization, the player aims to minimize regret, or the difference between her loss and that of the best fixed decision in hindsight over the entire repeated game. Algorithms that minimize (standard) regret may converge to a fixed decision, which is undesirable in changing or dynamic environments. This motivates the stronger metrics of performance, notably adaptive and dynamic regret. Adaptive regret is the maximum regret over any continuous sub-interval in time. Dynamic regret is the difference between the total cost and that of the best sequence of decisions in hindsight. State-of-the-art performance in both adaptive and dynamic regret minimization suffers a computational penalty - typically on the order of a multiplicative factor that grows logarithmically in the number of game iterations. In this paper we show how to reduce this computational penalty to be doubly logarithmic in the number of game iterations, and retain near optimal adaptive and dynamic regret bounds.