On the Generalization Ability of Online Strongly Convex Programming Algorithms

Published 8 December 2008

Sham M. Kakade, Ambuj Tewari

Citations121

TL;DR

A sharp bound is held on the excess risk of the output of an online algorithm in terms of the average regret, that allows one to use recent algorithms with logarithmic cumulative regret guarantees to achieve fast convergence rates for the excessrisk with high probability.

Abstract

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. As a corollary, we characterize the convergence rate of PEGASOS (with high probability), a recently proposed method for solving the SVM optimization problem. 1

Keywords

Computer ScienceDecision Sciences

Discriminative training methods for hidden Markov models

1,889 Citations2002Michael Collins

Experimental results on part-of-speech tagging and base noun phrase chunking are given, in both cases showing improvements over results for a maximum-entropy tagger.

View PDF

Online Passive-Aggressive Algorithms

1,449 Citations2006Koby Crammer, Ofer Dekel +3 more

Pegasos

982 Citations2007Shai Shalev‐Shwartz, Yoram Singer +1 more

A simple and effective stochastic sub-gradient descent algorithm for solving the optimization problem cast by Support Vector Machines, which is particularly well suited for large text classification problems, and demonstrates an order-of-magnitude speedup over previous SVM learning methods.

The Annals of ProbabilityOn Tail Probabilities for Martingales

628 Citations1975David A. Freedman

View PDF

IEEE Transactions on Information TheoryOn the Generalization Ability of On-Line Learning Algorithms

442 Citations2004Nicolò Cesa‐Bianchi, Alex Conconi +1 more

This paper proves tight data-dependent bounds for the risk of this hypothesis in terms of an easily computable statistic M/sub n/ associated with the on-line performance of the ensemble, and obtains risk tail bounds for kernel perceptron algorithms interms of the spectrum of the empirical kernel matrix.

Lecture notes in computer scienceLogarithmic Regret Algorithms for Online Convex Optimization

207 Citations2006Elad Hazan, Adam Tauman Kalai +2 more

Mistake bounds and logarithmic linear-threshold learning algorithms

184 Citations1990N. Littlestone

An analysis that shows that a straightforward transformation applied to mistake bounded algorithms, consisting of adding a hypothesis testing phase, produces algorithms that have asymptotically optimal PAC-learning bounds for certain target classes.

Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)(Online) Subgradient Methods for Structured Prediction

140 Citations2018Nathan Ratliff, J. Andrew Bagnell +1 more

This work proposes using simple subgradient-based techniques for optimizing a regularized risk formulation of structured learning problems in both online and batch settings, and analyzes the theoretical convergence, generalization, and robustness properties of the resulting techniques.

Neural Information Processing SystemsMind the Duality Gap: Logarithmic regret algorithms for online optimization

92 Citations2008Shai Shalev‐Shwartz, Sham M. Kakade

A primal-dual framework for the design and analysis of online strongly convex optimization algorithms is described and a new algorithm is derived that shares the computational simplicity of gradient descent but achieves lower regret in many practical situations.

IEEE Transactions on Information TheoryImproved Risk Tail Bounds for On-Line Algorithms

50 Citations2008Nicolò Cesa‐Bianchi, Claudio Gentile

Tight bounds are derived on the risk of models in the ensemble generated by incremental training of an arbitrary learning algorithm based on uniform convergence arguments, and improves on previous bounds published by the same authors.