A generalized online mirror descent with applications to classification and regression

Francesco Orabona, Koby Crammer, Nicolò Cesa-Bianchi

Research output: Contribution to journalArticlepeer-review

51 Scopus citations

Abstract

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
Volume99
Issue number3
DOIs
StatePublished - Jun 22 2015
Externally publishedYes

Bibliographical note

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

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software

Fingerprint

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