Online Optimization : Competing with Dynamic Comparators

Abstract

Recent literature on online learning has focused on developing adaptive algorithms that take advantage of a regularity of the sequence of observations, yet retain worst-case performance guarantees. A complementary direction is to develop prediction methods that perform well against complex benchmarks. In this paper, we address these two directions together. We present a fully adaptive method that competes with dynamic benchmarks in which regret guarantee scales with regularity of the sequence of cost functions and comparators. Notably, the regret bound adapts to the smaller complexity measure in the problem environment. Finally, we apply our results to drifting zero-sum, two-player games where both players achieve no regret guarantees against best sequences of actions in hindsight.

23 pages, To appear in International Conference on Artificial Intelligence and Statistics (AISTATS) 2015

References in corpus (2)

• Online Learning with Predictable Sequences
• Online Optimization in Dynamic Environments

Cited by in corpus (20)

• An Online Convex Optimization Approach to Dynamic Network Resource Allocation
• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Online Primal-Dual Methods with Measurement Feedback for Time-Varying Convex Optimization
• Online Learning with Inexact Proximal Online Gradient Descent Algorithms
• Adaptive Online Learning in Dynamic Environments
• Improved Dynamic Regret for Non-degenerate Functions
• Second-order Online Nonconvex Optimization
• Predictive Online Convex Optimization
• Tracking Slowly Moving Clairvoyant: Optimal Dynamic Regret of Online Learning with True and Noisy Gradient
• Local Strong Convexity of Source Localization and Error Bound for Target Tracking under Time-of-Arrival Measurements
• Delay-Tolerant Constrained OCO with Application to Network Resource Allocation
• Random Feature-based Online Multi-kernel Learning in Environments with Unknown Dynamics
• Personalized incentives as feedback design in generalized Nash equilibrium problems
• Strongly Adaptive Online Learning
• A Stochastic Operator Framework for Optimization and Learning with Sub-Weibull Errors
• Non-stationary Stochastic Optimization under $L_{p,q}$-Variation Measures
• Competitive ratio versus regret minimization: achieving the best of both worlds
• An Online Optimization Approach for Multi-Agent Tracking of Dynamic Parameters in the Presence of Adversarial Noise
• Online Learning with Automata-based Expert Sequences
• Dynamic Regret Convergence Analysis and an Adaptive Regularization Algorithm for On-Policy Robot Imitation Learning