Scale-free algorithms for online linear optimization

Francesco Orabona; Dávid Pál

doi:10.1007/978-3-319-24486-0_19

Scale-free algorithms for online linear optimization

Francesco Orabona, Dávid Pál

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

25 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 language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer [email protected]
Pages	287-301
Number of pages	15
ISBN (Print)	9783319244853
DOIs	https://doi.org/10.1007/978-3-319-24486-0_19
State	Published - Jan 1 2015
Externally published	Yes

Access to Document

10.1007/978-3-319-24486-0_19

Cite this

@inproceedings{989caa603e194aa882227b0868a613b8,

title = "Scale-free algorithms for online linear optimization",

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.",

author = "Francesco Orabona and D{\'a}vid P{\'a}l",

note = "Generated from Scopus record by KAUST IRTS on 2023-09-25",

year = "2015",

month = jan,

day = "1",

doi = "10.1007/978-3-319-24486-0_19",

language = "English (US)",

isbn = "9783319244853",

pages = "287--301",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer [email protected]",

}

TY - GEN

T1 - Scale-free algorithms for online linear optimization

AU - Orabona, Francesco

AU - Pál, Dávid

N1 - Generated from Scopus record by KAUST IRTS on 2023-09-25

PY - 2015/1/1

Y1 - 2015/1/1

N2 - 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.

AB - 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.

UR - http://link.springer.com/10.1007/978-3-319-24486-0_19

UR - http://www.scopus.com/inward/record.url?scp=84945956950&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-24486-0_19

DO - 10.1007/978-3-319-24486-0_19

M3 - Conference contribution

SN - 9783319244853

SP - 287

EP - 301

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

PB - Springer [email protected]

ER -

Scale-free algorithms for online linear optimization

Abstract

Access to Document

Other files and links

Fingerprint

Cite this