Dynamic Regret of Strongly Adaptive Methods
arXiv:1701.07570
Abstract
To cope with changing environments, recent developments in online learning have introduced the concepts of adaptive regret and dynamic regret independently. In this paper, we illustrate an intrinsic connection between these two concepts by showing that the dynamic regret can be expressed in terms of the adaptive regret and the functional variation. This observation implies that strongly adaptive algorithms can be directly leveraged to minimize the dynamic regret. As a result, we present a series of strongly adaptive algorithms that have small dynamic regrets for convex functions, exponentially concave functions, and strongly convex functions, respectively. To the best of our knowledge, this is the first time that exponential concavity is utilized to upper bound the dynamic regret. Moreover, all of those adaptive algorithms do not need any prior knowledge of the functional variation, which is a significant advantage over previous specialized methods for minimizing dynamic regret.
Cited by in corpus (25)
- A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
- Decentralized Online Learning: Take Benefits from Others' Data without Sharing Your Own to Track Global Trend
- Non-stationary Online Learning with Memory and Non-stochastic Control
- Dynamic Regret of Convex and Smooth Functions
- Online Forecasting of Total-Variation-bounded Sequences
- Minimizing Dynamic Regret and Adaptive Regret Simultaneously
- Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
- Dynamic Regret of Policy Optimization in Non-stationary Environments
- Proximal Online Gradient is Optimum for Dynamic Regret
- Optimal Dynamic Regret in Exp-Concave Online Learning
- Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints
- Temporal Variability in Implicit Online Learning
- Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions
- Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environments
- A closer look at temporal variability in dynamic online learning
- Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems
- Online Second Price Auction with Semi-bandit Feedback Under the Non-Stationary Setting
- Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles
- Non-stationary Online Regression
- An Optimal Reduction of TV-Denoising to Adaptive Online Learning
- Adaptive Online Estimation of Piecewise Polynomial Trends
- Understand Dynamic Regret with Switching Cost for Online Decision Making
- Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Losses
- Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR
- Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory