Adaptive Online Learning in Dynamic Environments

Abstract

In this paper, we study online convex optimization in dynamic environments, and aim to bound the dynamic regret with respect to any sequence of comparators. Existing work have shown that online gradient descent enjoys an $O(\sqrt{T}(1+P_T))$ dynamic regret, where $T$ is the number of iterations and $P_T$ is the path-length of the comparator sequence. However, this result is unsatisfactory, as there exists a large gap from the $\Omega (\sqrt{T(1+P_T)})$ lower bound established in our paper. To address this limitation, we develop a novel online method, namely adaptive learning for dynamic environment (Ader), which achieves an optimal $O(\sqrt{T(1+P_T)})$ dynamic regret. The basic idea is to maintain a set of experts, each attaining an optimal dynamic regret for a specific path-length, and combines them with an expert-tracking algorithm. Furthermore, we propose an improved Ader based on the surrogate loss, and in this way the number of gradient evaluations per round is reduced from $O(\log T)$ to $1$. Finally, we extend Ader to the setting that a sequence of dynamical models is available to characterize the comparators.

References in corpus (3)

• Online Optimization : Competing with Dynamic Comparators
• Improved Dynamic Regret for Non-degenerate Functions
• MetaGrad: Multiple Learning Rates in Online Learning

Cited by in corpus (16)

• Long-Term Energy Management for Microgrid with Hybrid Hydrogen-Battery Energy Storage: A Prediction-Free Coordinated Optimization Framework
• Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization
• Non-stationary Online Learning with Memory and Non-stochastic Control
• Online Forecasting of Total-Variation-bounded Sequences
• Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
• Dynamic Regret of Convex and Smooth Functions
• Bandit Convex Optimization in Non-stationary Environments
• Proximal Online Gradient is Optimum for Dynamic Regret
• Optimal Dynamic Regret in Exp-Concave Online Learning
• Improved Path-length Regret Bounds for Bandits
• Trading-Off Static and Dynamic Regret in Online Least-Squares and Beyond
• Revisiting Smoothed Online Learning
• A closer look at temporal variability in dynamic online learning
• Universal Online Convex Optimization Meets Second-order Bounds
• Online Graph Learning in Dynamic Environments
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR