Online Learning: Beyond Regret

Abstract

We study online learnability of a wide class of problems, extending the results of (Rakhlin, Sridharan, Tewari, 2010) to general notions of performance measure well beyond external regret. Our framework simultaneously captures such well-known notions as internal and general Phi-regret, learning with non-additive global cost functions, Blackwell's approachability, calibration of forecasters, adaptive regret, and more. We show that learnability in all these situations is due to control of the same three quantities: a martingale convergence term, a term describing the ability to perform well if future is known, and a generalization of sequential Rademacher complexity, studied in (Rakhlin, Sridharan, Tewari, 2010). Since we directly study complexity of the problem instead of focusing on efficient algorithms, we are able to improve and extend many known results which have been previously derived via an algorithmic construction.

Cited by in corpus (16)

• Model Theory and Machine Learning
• Optimizing Non-decomposable Performance Measures: A Tale of Two Classes
• Learning From An Optimization Viewpoint
• Online and Stochastic Gradient Methods for Non-decomposable Loss Functions
• Adaptive Online Learning
• Robust approachability and regret minimization in games with partial monitoring
• Relax and Localize: From Value to Algorithms
• (weak) Calibration is Computationally Hard
• Online Learning via Sequential Complexities
• Online Learning with an Almost Perfect Expert
• Online optimization and regret guarantees for non-additive long-term constraints
• Stronger Calibration Lower Bounds via Sidestepping
• Nonlinear Online Learning with Adaptive Nyström Approximation
• Refined approachability algorithms and application to regret minimization with global costs
• No-Regret Learnability for Piecewise Linear Losses
• Improved algorithms for online load balancing