Proximal Online Gradient is Optimum for Dynamic Regret
arXiv:1810.03594
Abstract
In online learning, the dynamic regret metric chooses the reference (optimal) solution that may change over time, while the typical (static) regret metric assumes the reference solution to be constant over the whole time horizon. The dynamic regret metric is particularly interesting for applications such as online recommendation (since the customers' preference always evolves over time). While the online gradient method has been shown to be optimal for the static regret metric, the optimal algorithm for the dynamic regret remains unknown. In this paper, we show that proximal online gradient (a general version of online gradient) is optimum to the dynamic regret by showing that the proved lower bound matches the upper bound that slightly improves existing upper bound.
References in corpus (13)
- An Online Convex Optimization Approach to Dynamic Network Resource Allocation
- Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
- Adaptive Online Learning in Dynamic Environments
- Improved Dynamic Regret for Non-degenerate Functions
- Mirror Descent Meets Fixed Share (and feels no regret)
- Tracking the Best Expert in Non-stationary Stochastic Environments
- Dynamic Regret of Strongly Adaptive Methods
- Online learning with noisy side observations
- Strongly Adaptive Online Learning
- Efficient tracking of a growing number of experts
- Online Learning to Rank with Feedback at the Top
- Online Gradient Descent in Function Space
- Online optimization and regret guarantees for non-additive long-term constraints
Cited by in corpus (6)
- Second-order Online Nonconvex Optimization
- Decentralized Online Learning: Take Benefits from Others' Data without Sharing Your Own to Track Global Trend
- Dynamic Regret of Policy Optimization in Non-stationary Environments
- Distributed Online Optimization for Multi-Agent Networks with Coupled Inequality Constraints
- Distributed Online Convex Optimization with an Aggregative Variable
- Understand Dynamic Regret with Switching Cost for Online Decision Making