Analysis of Online Composite Mirror Descent Algorithm

Yunwen Lei, Ding Xuan Zhou

Research output: Contribution to journalLetterpeer-review

9 Citations (Scopus)

Abstract

We study the convergence of the online composite mirror descent algorithm, which involves a mirror map to reflect the geometry of the data and a convex objective function consisting of a loss and a regularizer possibly inducing sparsity. Our error analysis provides convergence rates in terms of properties of the strongly convex differentiable mirror map and the objective function. For a class of objective functions with Hölder continuous gradients, the convergence rates of the excess (regularized) risk under polynomially decaying step sizes have the order O(T-1/2 log T) after T iterates. Our results improve the existing error analysis for the online composite mirror descent algorithm by avoiding averaging and removing boundedness assumptions, and they sharpen the existing convergence rates of the last iterate for online gradient descent without any boundedness assumptions. Our methodology mainly depends on a novel error decomposition in terms of an excess Bregman distance, refined analysis of self-bounding properties of the objective function, and the resulting one-step progress bounds.

Original languageEnglish
Pages (from-to)825-860
Number of pages36
JournalNeural Computation
Volume29
Issue number3
DOIs
Publication statusPublished - 1 Mar 2017

Scopus Subject Areas

  • Arts and Humanities (miscellaneous)
  • Cognitive Neuroscience

Fingerprint

Dive into the research topics of 'Analysis of Online Composite Mirror Descent Algorithm'. Together they form a unique fingerprint.

Cite this