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 (10)

• Adaptive Regret for Control of Time-Varying Dynamics
• Minimizing Dynamic Regret and Adaptive Regret Simultaneously
• Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints
• Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions
• Convergence Analyses of Online ADAM Algorithm in Convex Setting and Two-Layer ReLU Neural Network
• Unconstrained Online Optimization: Dynamic Regret Analysis of Strongly Convex and Smooth Problems
• Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles
• Universal Online Convex Optimization Meets Second-order Bounds
• Near-Linear Time Algorithm with Near-Logarithmic Regret Per Switch for Mixable/Exp-Concave Losses
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory