Loss bounds for online category ranking

Koby Crammer, Yoram Singer

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

5 Scopus citations


Category ranking is the task of ordering labels with respect to their relevance to an input instance. In this paper we describe and analyze several algorithms for online category ranking where the instances are revealed in a sequential manner. We describe additive and multiplicative updates which constitute the core of the learning algorithms. The updates are derived by casting a constrained optimization problem for each new instance. We derive loss bounds for the algorithms by using the properties of the dual solution while imposing additional constraints on the dual form. Finally, we outline and analyze the convergence of a general update that can be employed with any Bregman divergence.

Original languageEnglish (US)
Title of host publicationLearning Theory - 18th Annual Conference on Learning Theory, COLT 2005, Proceedings
PublisherSpringer Verlag
Number of pages15
ISBN (Print)3540265562, 9783540265566
StatePublished - 2005
Event18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory - Bertinoro, Italy
Duration: Jun 27 2005Jun 30 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3559 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other18th Annual Conference on Learning Theory, COLT 2005 - Learning Theory

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Loss bounds for online category ranking'. Together they form a unique fingerprint.

Cite this