Adaptive Regret of Convex and Smooth Functions

Abstract

We investigate online convex optimization in changing environments, and choose the adaptive regret as the performance measure. The goal is to achieve a small regret over every interval so that the comparator is allowed to change over time. Different from previous works that only utilize the convexity condition, this paper further exploits smoothness to improve the adaptive regret. To this end, we develop novel adaptive algorithms for convex and smooth functions, and establish problem-dependent regret bounds over any interval. Our regret bounds are comparable to existing results in the worst case, and become much tighter when the comparator has a small loss.

Cited by in corpus (5)

• Minimizing Dynamic Regret and Adaptive Regret Simultaneously
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints
• Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems
• Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles
• Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Losses