L-SVRG and L-Katyusha with Arbitrary Sampling

Xun Qian, Zheng Qu, Peter Richtarik

Research output: Contribution to journalArticlepeer-review

Abstract

We develop and analyze a new family of nonaccelerated and accelerated loopless variancereduced methods for finite-sum optimization problems. Our convergence analysis relies on a novel expected smoothness condition which upper bounds the variance of the stochastic gradient estimation by a constant times a distance-like function. This allows us to handle with ease arbitrary sampling schemes as well as the nonconvex case. We perform an indepth estimation of these expected smoothness parameters and propose new importance samplings which allow linear speedup when the expected minibatch size is in a certain range. Furthermore, a connection between these expected smoothness parameters and expected separable overapproximation (ESO) is established, which allows us to exploit data sparsity as well. Our general methods and results recover as special cases the loopless SVRG (Hofmann et al., 2015) and loopless Katyusha (Kovalev et al., 2019) methods. Keywords: L-SVRG, L-Katyusha, Arbitrary sampling, Expected smoothness, ESO
Original languageEnglish (US)
JournalJournal of Machine Learning Research
Volume22
StatePublished - 2021

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Statistics and Probability
  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'L-SVRG and L-Katyusha with Arbitrary Sampling'. Together they form a unique fingerprint.

Cite this