Improved Dynamic Regret for Non-degenerate Functions

Abstract

Recently, there has been a growing research interest in the analysis of dynamic regret, which measures the performance of an online learner against a sequence of local minimizers. By exploiting the strong convexity, previous studies have shown that the dynamic regret can be upper bounded by the path-length of the comparator sequence. In this paper, we illustrate that the dynamic regret can be further improved by allowing the learner to query the gradient of the function multiple times, and meanwhile the strong convexity can be weakened to other non-degenerate conditions. Specifically, we introduce the squared path-length, which could be much smaller than the path-length, as a new regularity of the comparator sequence. When multiple gradients are accessible to the learner, we first demonstrate that the dynamic regret of strongly convex functions can be upper bounded by the minimum of the path-length and the squared path-length. We then extend our theoretical guarantee to functions that are semi-strongly convex or self-concordant. To the best of our knowledge, this is the first time that semi-strong convexity and self-concordance are utilized to tighten the dynamic regret.

References in corpus (3)

• Online Optimization : Competing with Dynamic Comparators
• Dynamical Models and Tracking Regret in Online Convex Programming
• Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient

Cited by in corpus (18)

• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• Online Learning with Inexact Proximal Online Gradient Descent Algorithms
• Adaptive Online Learning in Dynamic Environments
• Second-order Online Nonconvex Optimization
• Adaptive Gradient-Based Meta-Learning Methods
• Non-stationary Online Learning with Memory and Non-stochastic Control
• 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
• Online Convex Optimization Using Coordinate Descent Algorithms
• Proximal Online Gradient is Optimum for Dynamic Regret
• Online Learning with Continuous Variations: Dynamic Regret and Reductions
• Distributed Online Convex Optimization with Improved Dynamic Regret
• Revisiting Smoothed Online Learning
• Continuous Online Learning and New Insights to Online Imitation Learning
• Dynamic Regret Convergence Analysis and an Adaptive Regularization Algorithm for On-Policy Robot Imitation Learning
• Tracking Moving Agents via Inexact Online Gradient Descent Algorithm
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory