No-Regret Algorithms for Unconstrained Online Convex Optimization
arXiv:1211.2260
Abstract
Some of the most compelling applications of online convex optimization, including online prediction and classification, are unconstrained: the natural feasible set is R^n. Existing algorithms fail to achieve sub-linear regret in this setting unless constraints on the comparator point x^* are known in advance. We present algorithms that, without such prior knowledge, offer near-optimal regret bounds with respect to any choice of x^*. In particular, regret with respect to x^* = 0 is constant. We then prove lower bounds showing that our guarantees are near-optimal in this setting.
To appear
Cited by in corpus (17)
- Online Learning: A Modern Introduction Using Convex Optimization
- Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations
- Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning
- A Survey of Algorithms and Analysis for Adaptive Online Learning
- Online Learning Without Prior Information
- Achieving All with No Parameters: Adaptive NormalHedge
- A Generalized Online Mirror Descent with Applications to Classification and Regression
- Training Deep Networks without Learning Rates Through Coin Betting
- MetaGrad: Adaptation using Multiple Learning Rates in Online Learning
- Low Complexity Approximate Bayesian Logistic Regression for Sparse Online Learning
- Combining Online Learning Guarantees
- Parameter-free Stochastic Optimization of Variationally Coherent Functions
- Matrix-Free Preconditioning in Online Learning
- Minimax Optimal Algorithms for Unconstrained Linear Optimization
- Proximal Algorithms for Smoothed Online Convex Optimization with Predictions
- Online Parameter-Free Learning of Multiple Low Variance Tasks
- Adaptive Online Learning with Varying Norms