L-SVRG and L-Katyusha with Arbitrary Sampling

By Xun Qian, Zheng Qu, Peter Richtárik. 2019

34 citations recorded by the source corpus.

We develop and analyze a new family of {\em nonaccelerated and accelerated loopless variance-reduced 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 {\em arbitrary sampling schemes} as well as the nonconvex case. We perform an in-depth estimation of these expected smoothness parameters and propose new importance samplings which allow {\em 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 results recover as special cases the recently proposed loopless SVRG and loopless Katyusha.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Peter Richtárik
2. Nicolas Loizou
3. Simon Lacoste-Julien
4. Filip Hanzely
5. Ioannis Mitliagkas
6. Hugo Berard
7. Pascal Vincent
8. Sebastian U. Stich

In Computational Mechanics

1. Peter Richtárik
2. Nicolas Loizou
3. Simon Lacoste-Julien
4. Ioannis Mitliagkas
5. Filip Hanzely
6. Hugo Berard
7. Pascal Vincent
8. Alexia Jolicoeur-Martineau

In Statistics and Probability

1. Nicolas Loizou
2. Filip Hanzely
3. Peter Richtárik
4. Simon Lacoste-Julien
5. Hugo Berard
6. Ioannis Mitliagkas
7. Pascal Vincent
8. Alexia Jolicoeur-Martineau

In Optimization & Training

1. Nicolas Loizou
2. Peter Richtárik
3. Filip Hanzely
4. Simon Lacoste-Julien
5. Ioannis Mitliagkas
6. Hugo Berard
7. Pascal Vincent
8. Alexia Jolicoeur-Martineau

Citations in the corpus

• Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “CONVERGENCE OF L-SVRG (WITH RESTART) In Qian et al. (2019) an analysis of L-SVRG (Algorithm 5) was provided for non-convex and smooth functions.”
• Federated Learning of a Mixture of Global and Local Models (2020, methodology): “Note that Algorithm 3 is a particular special case of SAGA with importance sampling (Qian et al., 2019b); thus, we obtain convergence rate of the method for free.”