File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Analysis of online composite mirror descent algorithm

TitleAnalysis of online composite mirror descent algorithm
Authors
Issue Date2017
Citation
Neural Computation, 2017, v. 29, n. 3, p. 825-860 How to Cite?
AbstractWe 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.
Persistent Identifierhttp://hdl.handle.net/10722/330002
ISSN
2023 Impact Factor: 2.7
2023 SCImago Journal Rankings: 0.948
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorLei, Yunwen-
dc.contributor.authorZhou, Ding Xuan-
dc.date.accessioned2023-08-09T03:37:06Z-
dc.date.available2023-08-09T03:37:06Z-
dc.date.issued2017-
dc.identifier.citationNeural Computation, 2017, v. 29, n. 3, p. 825-860-
dc.identifier.issn0899-7667-
dc.identifier.urihttp://hdl.handle.net/10722/330002-
dc.description.abstractWe 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.-
dc.languageeng-
dc.relation.ispartofNeural Computation-
dc.titleAnalysis of online composite mirror descent algorithm-
dc.typeArticle-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1162/NECO_a_00930-
dc.identifier.pmid28095196-
dc.identifier.scopuseid_2-s2.0-85013675736-
dc.identifier.volume29-
dc.identifier.issue3-
dc.identifier.spage825-
dc.identifier.epage860-
dc.identifier.eissn1530-888X-
dc.identifier.isiWOS:000395564100010-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats