Timezone: »

 
Poster
On the Generalization Ability of Online Strongly Convex Programming Algorithms
Sham M Kakade · Ambuj Tewari

Tue Dec 09 07:30 PM -- 12:00 AM (PST) @ None #None

This paper examines the generalization properties of online convex programming algorithms when the loss function is Lipschitz and strongly convex. Our main result is a sharp bound, that holds with high probability, on the excess risk of the output of an online algorithm in terms of the average regret. This allows one to use recent algorithms with logarithmic cumulative regret guarantees to achieve fast convergence rates for the excess risk with high probability. The bound also solves an open problem regarding the convergence rate of {\pegasos}, a recently proposed method for solving the SVM optimization problem.

Author Information

Sham M Kakade (Microsoft Research)
Ambuj Tewari (University of Michigan)

More from the Same Authors