Dimension-free exponentiated gradient

Francesco Orabona

Dimension-free exponentiated gradient

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

Abstract

I present a new online learning algorithm that extends the exponentiated gradient framework to infinite dimensional spaces. My analysis shows that the algorithm is implicitly able to estimate the L2 norm of the unknown competitor, U, achieving a regret bound of the order of O(U log(U T + 1)) √ T), instead of the standard O((U2 + 1) √ T), achievable without knowing U. For this analysis, I introduce novel tools for algorithms with time-varying regularizers, through the use of local smoothness. Through a lower bound, I also show that the algorithm is optimal up to √ log(UT) term for linear and Lipschitz losses.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems
Publisher	Neural information processing systems foundation
State	Published - Jan 1 2013
Externally published	Yes

Bibliographical note

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

Cite this

@inproceedings{4445cadf6e2e4879901192a562aeac4c,

title = "Dimension-free exponentiated gradient",

abstract = "I present a new online learning algorithm that extends the exponentiated gradient framework to infinite dimensional spaces. My analysis shows that the algorithm is implicitly able to estimate the L2 norm of the unknown competitor, U, achieving a regret bound of the order of O(U log(U T + 1)) √ T), instead of the standard O((U2 + 1) √ T), achievable without knowing U. For this analysis, I introduce novel tools for algorithms with time-varying regularizers, through the use of local smoothness. Through a lower bound, I also show that the algorithm is optimal up to √ log(UT) term for linear and Lipschitz losses.",

author = "Francesco Orabona",

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

year = "2013",

month = jan,

day = "1",

language = "English (US)",

booktitle = "Advances in Neural Information Processing Systems",

publisher = "Neural information processing systems foundation",

}

TY - GEN

T1 - Dimension-free exponentiated gradient

AU - Orabona, Francesco

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

PY - 2013/1/1

Y1 - 2013/1/1

N2 - I present a new online learning algorithm that extends the exponentiated gradient framework to infinite dimensional spaces. My analysis shows that the algorithm is implicitly able to estimate the L2 norm of the unknown competitor, U, achieving a regret bound of the order of O(U log(U T + 1)) √ T), instead of the standard O((U2 + 1) √ T), achievable without knowing U. For this analysis, I introduce novel tools for algorithms with time-varying regularizers, through the use of local smoothness. Through a lower bound, I also show that the algorithm is optimal up to √ log(UT) term for linear and Lipschitz losses.

AB - I present a new online learning algorithm that extends the exponentiated gradient framework to infinite dimensional spaces. My analysis shows that the algorithm is implicitly able to estimate the L2 norm of the unknown competitor, U, achieving a regret bound of the order of O(U log(U T + 1)) √ T), instead of the standard O((U2 + 1) √ T), achievable without knowing U. For this analysis, I introduce novel tools for algorithms with time-varying regularizers, through the use of local smoothness. Through a lower bound, I also show that the algorithm is optimal up to √ log(UT) term for linear and Lipschitz losses.

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

M3 - Conference contribution

BT - Advances in Neural Information Processing Systems

PB - Neural information processing systems foundation

ER -

Dimension-free exponentiated gradient

Abstract

Bibliographical note

Other files and links

Fingerprint

Cite this