Scale-free algorithms for online linear optimization

Francesco Orabona, Dávid Pál

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

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.
Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlagservice@springer.de
Pages287-301
Number of pages15
ISBN (Print)9783319244853
DOIs
StatePublished - Jan 1 2015
Externally publishedYes

Fingerprint

Dive into the research topics of 'Scale-free algorithms for online linear optimization'. Together they form a unique fingerprint.

Cite this