Federated Random Reshuffling with Compression and Variance Reduction

2022-05-08 · Grigory Malinovsky, Peter Richtárik

Random Reshuffling (RR), which is a variant of Stochastic Gradient Descent (SGD) employing sampling without replacement, is an immensely popular method for training supervised machine learning models via empirical risk minimization. Due to its superior practical performance, it is embedded and often set as default in standard machine learning software. Under the name FedRR, this method was recently shown to be applicable to federated learning (Mishchenko et al.,2021), with superior performance when compared to common baselines such as Local SGD. Inspired by this development, we design three new algorithms to improve FedRR further: compressed FedRR and two variance reduced extensions: one for taming the variance coming from shuffling and the other for taming the variance due to compression. The variance reduction mechanism for compression allows us to eliminate dependence on the compression parameter, and applying additional controlled linear perturbations for Random Reshuffling, introduced by Malinovsky et al.(2021) helps to eliminate variance at the optimum. We provide the first analysis of compressed local methods under standard assumptions without bounded gradient assumptions and for heterogeneous data, overcoming the limitations of the compression operator. We corroborate our theoretical results with experiments on synthetic and real data sets.

📄 PDF Abstract BibTeX arXiv:2205.03914

Code (0)

등록된 구현이 없습니다.

Tasks

BIG-bench Machine Learning Federated Learning

Methods 이 논문이 사용한 방법론

SGD Stochastic Gradient Descent is an iterative optimization technique that uses minibatches of data to form an expectation of the gradient, rather than the full gradient using…

Local SGD Local SGD is a distributed training technique that runs SGD independently in parallel on different workers and averages the sequences…

Federated Optimization Algorithms with Random Reshuffling and Gradient Compression

2022-06-14 · Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov, Igor Sokolov 외

Gradient compression is a popular technique for improving communication complexity of stochastic first-order methods in distributed training of machine learning models. However, the existing works consider only with-repl…

Federated Learning Quantization

FedShuffle: Recipes for Better Use of Local Work in Federated Learning

2022-04-27 · Samuel Horváth, Maziar Sanjabi, Lin Xiao, Peter Richtárik 외

The practice of applying several local updates before aggregation across clients has been empirically shown to be a successful approach to overcoming the communication bottleneck in Federated Learning (FL). Such methods …

Federated Learning

Variance-Reduced Stochastic Learning under Random Reshuffling

2017-08-04 · Bicheng Ying, Kun Yuan, Ali H. Sayed

Several useful variance-reduced stochastic gradient algorithms, such as SVRG, SAGA, Finito, and SAG, have been proposed to minimize empirical risks with linear convergence properties to the exact minimizer. The existing …

Random Reshuffling with Variance Reduction: New Analysis and Better Rates

2021-04-19 · Grigory Malinovsky, Alibek Sailanbayev, Peter Richtárik

Virtually all state-of-the-art methods for training supervised machine learning models are variants of SGD enhanced with a number of additional tricks, such as minibatching, momentum, and adaptive stepsizes. One of the t…

BIG-bench Machine Learning

Server-Side Stepsizes and Sampling Without Replacement Provably Help in Federated Optimization

2022-01-26 · Grigory Malinovsky, Konstantin Mishchenko, Peter Richtárik

We present a theoretical study of server-side optimization in federated learning. Our results are the first to show that the widely popular heuristic of scaling the client updates with an extra parameter is very useful i…