Peter Bartlett and Elad Hazan and Alexander Rakhlin

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-82

June 14, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-82.pdf

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 $\sqrt{T}$ and $\log T$. Furthermore, we show strong optimality of the algorithm. Finally, we provide an extension of our results to general norms.

---

BibTeX citation:

@techreport{Bartlett:EECS-2007-82,
    Author= {Bartlett, Peter and Hazan, Elad and Rakhlin, Alexander},
    Title= {Adaptive Online Gradient Descent},
    Year= {2007},
    Month= {Jun},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-82.html},
    Number= {UCB/EECS-2007-82},
    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 $\sqrt{T}$
and $\log T$. Furthermore, we show strong optimality of
the algorithm. Finally, we provide an extension of our results to general norms.},
}

EndNote citation:

%0 Report
%A Bartlett, Peter 
%A Hazan, Elad 
%A Rakhlin, Alexander 
%T Adaptive Online Gradient Descent
%I EECS Department, University of California, Berkeley
%D 2007
%8 June 14
%@ UCB/EECS-2007-82
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-82.html
%F Bartlett:EECS-2007-82