L-SVRG and L-Katyusha with Arbitrary Sampling

Xun Qian; Zheng Qu; Peter Richtarik

L-SVRG and L-Katyusha with Arbitrary Sampling

Research output: Contribution to journal › Article › peer-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 language	English (US)
Journal	Journal of Machine Learning Research
Volume	22
State	Published - 2021

Bibliographical note

KAUST Repository Item: Exported on 2021-07-15
Acknowledgements: We thank the action editor and two anonymous referees for their valuable comments. All authors are thankful for support through the KAUST Baseline Research Funding Scheme. Xun Qian and Peter Richtárik acknowledge further funding by the Extreme Computing
Research Center at KAUST, and administrative support from the Visual Computing Center at KAUST. Zheng Qu acknowledges further funding by Hong Kong Research Grants Council Early Career Scheme 27303016.

ASJC Scopus subject areas

Artificial Intelligence
Software
Statistics and Probability
Control and Systems Engineering

Access to Document

https://repository.kaust.edu.sa/bitstream/10754/660285/3/20-156.pdf

Cite this

@article{74414974dc4d4bfc80f5da4c1270d293,

title = "L-SVRG and L-Katyusha with Arbitrary Sampling",

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",

author = "Xun Qian and Zheng Qu and Peter Richtarik",

note = "KAUST Repository Item: Exported on 2021-07-15 Acknowledgements: We thank the action editor and two anonymous referees for their valuable comments. All authors are thankful for support through the KAUST Baseline Research Funding Scheme. Xun Qian and Peter Richt{\'a}rik acknowledge further funding by the Extreme Computing Research Center at KAUST, and administrative support from the Visual Computing Center at KAUST. Zheng Qu acknowledges further funding by Hong Kong Research Grants Council Early Career Scheme 27303016.",

year = "2021",

language = "English (US)",

volume = "22",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

}

TY - JOUR

T1 - L-SVRG and L-Katyusha with Arbitrary Sampling

AU - Qian, Xun

AU - Qu, Zheng

AU - Richtarik, Peter

N1 - KAUST Repository Item: Exported on 2021-07-15 Acknowledgements: We thank the action editor and two anonymous referees for their valuable comments. All authors are thankful for support through the KAUST Baseline Research Funding Scheme. Xun Qian and Peter Richtárik acknowledge further funding by the Extreme Computing Research Center at KAUST, and administrative support from the Visual Computing Center at KAUST. Zheng Qu acknowledges further funding by Hong Kong Research Grants Council Early Career Scheme 27303016.

PY - 2021

Y1 - 2021

N2 - 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

AB - 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

UR - http://hdl.handle.net/10754/660285

UR - https://jmlr.csail.mit.edu/papers/volume22/20-156/20-156.pdf

M3 - Article

SN - 1532-4435

VL - 22

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

ER -

L-SVRG and L-Katyusha with Arbitrary Sampling

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this