New adaptive algorithms for online classification

Francesco Orabona, Koby Crammer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations


We propose a general framework to online learning for classification problems with time-varying potential functions in the adversarial setting. This framework allows to design and prove relative mistake bounds for any generic loss function. The mistake bounds can be specialized for the hinge loss, allowing to recover and improve the bounds of known online classification algorithms. By optimizing the general bound we derive a new online classification algorithm, called NAROW, that hybridly uses adaptive- and fixed- second order information. We analyze the properties of the algorithm and illustrate its performance using synthetic dataset.
Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, NIPS 2010
PublisherNeural Information Processing Systems
ISBN (Print)9781617823800
StatePublished - Jan 1 2010
Externally publishedYes


Dive into the research topics of 'New adaptive algorithms for online classification'. Together they form a unique fingerprint.

Cite this