Fastest rates for stochastic mirror descent methods

Filip Hanzely, Peter Richtarik

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Relative smoothness—a notion introduced in Birnbaum et al. (Proceedings of the 12th ACM conference on electronic commerce, ACM, pp 127–136, 2011) and recently rediscovered in Bauschke et al. (Math Oper Res 330–348, 2016) and Lu et al. (Relatively-smooth convex optimization by first-order methods, and applications, arXiv:1610.05708, 2016)—generalizes the standard notion of smoothness typically used in the analysis of gradient type methods. In this work we are taking ideas from well studied field of stochastic convex optimization and using them in order to obtain faster algorithms for minimizing relatively smooth functions. We propose and analyze two new algorithms: Relative Randomized Coordinate Descent (relRCD) and Relative Stochastic Gradient Descent (relSGD), both generalizing famous algorithms in the standard smooth setting. The methods we propose can be in fact seen as particular instances of stochastic mirror descent algorithms, which has been usually analyzed under stronger assumptions: Lipschitzness of the objective and strong convexity of the reference function. As a consequence, one of the proposed methods, relRCD corresponds to the first stochastic variant of mirror descent algorithm with linear convergence rate.
Original languageEnglish (US)
Pages (from-to)717-766
Number of pages50
JournalComputational Optimization and Applications
Issue number3
StatePublished - Jun 9 2021

Bibliographical note

KAUST Repository Item: Exported on 2021-06-21

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Fastest rates for stochastic mirror descent methods'. Together they form a unique fingerprint.

Cite this