Scale-free algorithms for online linear optimization

DOI10.1007/978-3-319-24486-0_19MaRDI QIDQ2835636zbMATH OpenOpenAlexFDO

Authors Francesco Orabona, Dávid Pál

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.05744

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Convex programming (90C25) Online algorithms; streaming algorithms (68W27)

Abstract: We design 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. We achieve adaptiveness to norms of 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. Our algorithms work for any decision set, bounded or unbounded. For unbounded decisions sets, these are the first truly adaptive algorithms for online linear optimization.

Recommendations

• Scale-free online learning
• Scale-invariant unconstrained online learning
• Scale-invariant unconstrained online learning
• Adaptive and self-confident on-line learning algorithms
• Logarithmic Regret Algorithms for Online Convex Optimization

Cites work

• A continuous-time approach to online optimization
• 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
• Dual averaging methods for regularized stochastic learning and online optimization
• Follow the leader if you can, hedge if you must
• How to use expert advice
• Large margin classification using the perceptron algorithm
• Near-optimal regret bounds for reinforcement learning
• Online learning and online convex optimization
• Prediction by Categorical Features: Generalization Properties and Application to Feature Ranking
• Prediction, Learning, and Games
• The weighted majority algorithm

Cited in

(11)

• Adaptive and optimal online linear regression on ^1-balls
• Scale-free online learning
• Adaptive and self-confident on-line learning algorithms
• Linear programming with online learning
• Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
• Scale-invariant unconstrained online learning
• Scale-invariant unconstrained online learning
• scientific article; zbMATH DE number 7625168 (Why is no real title available?)
• Online Linear Extractors for Independent Sources
• The robustness of the \(p\)-norm algorithms
• Adaptive and optimal online linear regression on \(\ell ^{1}\)-balls

Describes a project that uses

Uses Software

• AdaGrad

This page was built for publication: Scale-free algorithms for online linear optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835636)