Adaptive Online Learning

Abstract

We propose a general framework for studying adaptive regret bounds in the online learning framework, including model selection bounds and data-dependent bounds. Given a data- or model-dependent bound we ask, "Does there exist some algorithm achieving this bound?" We show that modifications to recently introduced sequential complexity measures can be used to answer this question by providing sufficient conditions under which adaptive rates can be achieved. In particular each adaptive rate induces a set of so-called offset complexity measures, and obtaining small upper bounds on these quantities is sufficient to demonstrate achievability. A cornerstone of our analysis technique is the use of one-sided tail inequalities to bound suprema of offset random processes. Our framework recovers and improves a wide variety of adaptive bounds including quantile bounds, second-order data-dependent bounds, and small loss bounds. In addition we derive a new type of adaptive bound for online linear optimization based on the spectral norm, as well as a new online PAC-Bayes theorem that holds for countably infinite sets.

References in corpus (3)

• Online Learning: Beyond Regret
• Learning with Square Loss: Localization through Offset Rademacher Complexity
• Achieving All with No Parameters: Adaptive NormalHedge

Cited by in corpus (7)

• Parameter-Free Online Convex Optimization with Sub-Exponential Noise
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• Prediction with Corrupted Expert Advice
• Combining Online Learning Guarantees
• Open Problem: Model Selection for Contextual Bandits
• Artificial Constraints and Lipschitz Hints for Unconstrained Online Learning
• Adaptive Online Learning with Varying Norms