Timezone: »

Mind the Duality Gap: Logarithmic regret algorithms for online optimization
Shai Shalev-Shwartz · Sham M Kakade

Tue Dec 09 11:58 AM -- 11:59 AM (PST) @

We describe a primal-dual framework for the design and analysis of online strongly convex optimization algorithms. Our framework yields the tightest known logarithmic regret bounds for Follow-The-Leader and for the gradient descent algorithm proposed in HazanKaKaAg06. We then show that one can interpolate between these two extreme cases. In particular, we derive a new algorithm that shares the computational simplicity of gradient descent but achieves lower regret in many practical situations. Finally, we further extend our framework for generalized strongly convex functions.

Author Information

Shai Shalev-Shwartz (Mobileye & HUJI)
Sham M Kakade (Harvard University & Amazon)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors