Beyond logarithmic bounds in online learning

Francesco Orabona, Nicolò Cesa-Bianchi, Claudio Gentile

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

29 Scopus citations


We prove logarithmic regret bounds that depend on the loss L∗T of the competitor rather than on the number T of time steps. In the general online convex optimization setting, our bounds hold for any smooth and exp-concave loss (such as the square loss or the logistic loss). This bridges the gap between the O (ln T) regret exhibited by expconcave losses and the O (√L∗T) regret exhibited by smooth losses. We also show that these bounds are tight for specific losses, thus they cannot be improved in general. For online regression with square loss, our analysis can be used to derive a sparse randomized variant of the online Newton step, whose expected number of updates scales with the algorithm's loss. For online classification, we prove the first logarithmic mistake bounds that do not rely on prior knowledge of a bound on the competitor's norm.
Original languageEnglish (US)
Title of host publicationJournal of Machine Learning Research
Number of pages9
StatePublished - Jan 1 2012
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2023-09-25

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Statistics and Probability
  • Control and Systems Engineering


Dive into the research topics of 'Beyond logarithmic bounds in online learning'. Together they form a unique fingerprint.

Cite this