Adaptive online gradient descent

Peter L. Bartlett; Elad E. Hazan; Alexander Rakhlin

Adaptive online gradient descent

Peter L. Bartlett, Elad E. Hazan, Alexander Rakhlin

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

Abstract

We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between √ T and log T. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference
State	Published - Dec 1 2009
Externally published	Yes
Event	21st Annual Conference on Neural Information Processing Systems, NIPS 2007 - Vancouver, BC, Canada Duration: Dec 3 2007 → Dec 6 2007

Other

Other	21st Annual Conference on Neural Information Processing Systems, NIPS 2007
Country/Territory	Canada
City	Vancouver, BC
Period	12/3/07 → 12/6/07

All Science Journal Classification (ASJC) codes

Information Systems

Cite this

@inproceedings{001eeb08f75743d48131e72719e75aa7,

title = "Adaptive online gradient descent",

abstract = "We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between √ T and log T. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.",

author = "Bartlett, {Peter L.} and Hazan, {Elad E.} and Alexander Rakhlin",

year = "2009",

month = dec,

day = "1",

language = "English (US)",

isbn = "160560352X",

booktitle = "Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference",

note = "21st Annual Conference on Neural Information Processing Systems, NIPS 2007 ; Conference date: 03-12-2007 Through 06-12-2007",

}

TY - GEN

T1 - Adaptive online gradient descent

AU - Bartlett, Peter L.

AU - Hazan, Elad E.

AU - Rakhlin, Alexander

PY - 2009/12/1

Y1 - 2009/12/1

N2 - We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between √ T and log T. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.

AB - We study the rates of growth of the regret in online convex optimization. First, we show that a simple extension of the algorithm of Hazan et al eliminates the need for a priori knowledge of the lower bound on the second derivatives of the observed functions. We then provide an algorithm, Adaptive Online Gradient Descent, which interpolates between the results of Zinkevich for linear functions and of Hazan et al for strongly convex functions, achieving intermediate rates between √ T and log T. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.

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

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

M3 - Conference contribution

AN - SCOPUS:84858789001

SN - 160560352X

SN - 9781605603520

BT - Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference

T2 - 21st Annual Conference on Neural Information Processing Systems, NIPS 2007

Y2 - 3 December 2007 through 6 December 2007

ER -

Adaptive online gradient descent

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this