One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods

By Filip Hanzely, Peter Richtárik. 2019

27 citations recorded by the source corpus.

We propose a remarkably general variance-reduced method suitable for solving regularized empirical risk minimization problems with either a large number of training examples, or a large model dimension, or both. In special cases, our method reduces to several known and previously thought to be unrelated methods, such as {\tt SAGA}, {\tt LSVRG}, {\tt JacSketch}, {\tt SEGA} and {\tt ISEGA}, and their arbitrary sampling and proximal generalizations. However, we also highlight a large number of new specific algorithms with interesting properties. We provide a single theorem establishing linear convergence of the method under smoothness and quasi strong convexity assumptions. With this theorem we recover best-known and sometimes improved rates for known methods arising in special cases. As a by-product, we provide the first unified method and theory for stochastic gradient and stochastic coordinate descent type methods.

Subfields: Artificial Intelligence, Statistics and Probability

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

In Statistics and Probability

Citations in the corpus

SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, methodology): “Numerous variations and extensions of the technique are studied in (Hanzely and Richtárik, 2019).”
Federated Learning of a Mixture of Global and Local Models (2020, methodology): “However, it is still a special case of a more general algorithm from (Hanzely & Richtárik, 2019).”
Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization (2020, methodology): “…descent (CGD) (Alistarh et al., 2017; Khirirat et al., 2018; Horv´ath et al., 2019a) and distributed CGD methods which employ variance reduction to tame the variance introduced by compression (Hanzely et al., 2018; Mishchenko et al., 2019a; Horv´ath et al., 2019b; Hanzely & Richt´arik, 2019b).”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, methodology): “This is standard in variance reduction methods (Johnson & Zhang, 2013; Defazio et al., 2014; Hanzely & Richt´arik, 2019).”