Scale-free online learning
From MaRDI portal
Abstract: We design and analyze algorithms for online linear optimization that have optimal regret and at the same time do not need to know any upper or lower bounds on the norm of the loss vectors. Our algorithms are instances of the Follow the Regularized Leader (FTRL) and Mirror Descent (MD) meta-algorithms. We achieve adaptiveness to the norms of the loss vectors by scale invariance, i.e., our algorithms make exactly the same decisions if the sequence of loss vectors is multiplied by any positive constant. The algorithm based on FTRL works for any decision set, bounded or unbounded. For unbounded decisions sets, this is the first adaptive algorithm for online linear optimization with a non-vacuous regret bound. In contrast, we show lower bounds on scale-free algorithms based on MD on unbounded domains.
Recommendations
Cites work
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- A decision-theoretic generalization of on-line learning and an application to boosting
- A game of prediction with expert advice
- A generalized online mirror descent with applications to classification and regression
- Adaptive and self-confident on-line learning algorithms
- Adaptive subgradient methods for online learning and stochastic optimization
- Convex optimization: algorithms and complexity
- Dual averaging methods for regularized stochastic learning and online optimization
- Efficient algorithms for online decision problems
- Exponentiated gradient versus gradient descent for linear predictors
- Follow the leader if you can, hedge if you must
- How to use expert advice
- Large margin classification using the perceptron algorithm
- Learning permutations with exponential weights
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Near-optimal regret bounds for reinforcement learning
- Online learning and online convex optimization
- Prediction, Learning, and Games
- Primal-dual subgradient methods for convex problems
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Scale-free algorithms for online linear optimization
- The weighted majority algorithm
Cited in
(20)- Provably efficient reinforcement learning in decentralized general-sum Markov games
- SOLO FTRL algorithm for production management with transfer prices
- Following the leader and fast rates in online linear prediction: curved constraint sets and other regularities
- Nonstationary online convex optimization with multiple predictions
- A generalized online mirror descent with applications to classification and regression
- Adaptive and optimal online linear regression on \(\ell ^{1}\)-balls
- Scale-free algorithms for online linear optimization
- Adaptive and optimal online linear regression on \(\ell^1\)-balls
- Online learning via congregational gradient descent
- A modular analysis of adaptive (non-)convex optimization: optimism, composite objectives, and variational bounds
- Online Learning Meets Optimization in the Dual
- A survey of algorithms and analysis for adaptive online learning
- Multi-scale online learning: theory and applications to online auctions and pricing
- A modular analysis of adaptive (non-)convex optimization: optimism, composite objectives, variance reduction, and variational bounds
- Scale-invariant unconstrained online learning
- Scale-invariant unconstrained online learning
- scientific article; zbMATH DE number 7415104 (Why is no real title available?)
- Optimistic optimisation of composite objective with exponentiated update
- Adaptive and self-confident on-line learning algorithms
- Principal component analysis and optimal portfolio
This page was built for publication: Scale-free online learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1704560)
