Scale-free online learning

Francesco Orabona, Dávid Pál

Research output: Contribution to journalArticlepeer-review

58 Scopus citations

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.
Original languageEnglish (US)
Pages (from-to)50-69
Number of pages20
JournalTheoretical Computer Science
Volume716
DOIs
StatePublished - Mar 15 2018
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Scale-free online learning'. Together they form a unique fingerprint.

Cite this