A generalized online mirror descent with applications to classification and regression

Francesco Orabona, Koby Crammer, Nicolò Cesa-Bianchi

Research output: Contribution to journalArticlepeer-review

43 Scopus citations


Online learning algorithms are fast, memory-efficient, easy to implement, and applicable to many prediction problems, including classification, regression, and ranking. Several online algorithms were proposed in the past few decades, some based on additive updates, like the Perceptron, and some on multiplicative updates, like Winnow. A unifying perspective on the design and the analysis of online algorithms is provided by online mirror descent, a general prediction strategy from which most first-order algorithms can be obtained as special cases. We generalize online mirror descent to time-varying regularizers with generic updates. Unlike standard mirror descent, our more general formulation also captures second order algorithms, algorithms for composite losses and algorithms for adaptive filtering. Moreover, we recover, and sometimes improve, known regret bounds as special cases of our analysis using specific regularizers. Finally, we show the power of our approach by deriving a new second order algorithm with a regret bound invariant with respect to arbitrary rescalings of individual features.
Original languageEnglish (US)
Pages (from-to)411-435
Number of pages25
JournalMachine Learning
Issue number3
StatePublished - Jun 22 2015
Externally publishedYes

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software


Dive into the research topics of 'A generalized online mirror descent with applications to classification and regression'. Together they form a unique fingerprint.

Cite this