Peter Richtarik

Random Reshuffling with Variance Reduction: New Analysis and Better Rates

Virtually all state-of-the-art methods for training supervised machine l...
04/19/2021 ∙ by Grigory Malinovsky, et al. ∙ 0 ∙ share

read it
ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computation

We propose ZeroSARAH – a novel variant of the variance-reduced method SA...
03/02/2021 ∙ by Zhize Li, et al. ∙ 6 ∙ share

read it
Hyperparameter Transfer Learning with Adaptive Complexity

Bayesian optimization (BO) is a sample efficient approach to automatical...
02/25/2021 ∙ by Samuel Horvath, et al. ∙ 18 ∙ share

read it
AI-SARAH: Adaptive and Implicit Stochastic Recursive Gradient Methods

We present an adaptive stochastic variance reduced method with an implic...
02/19/2021 ∙ by Zheng Shi, et al. ∙ 12 ∙ share

read it
ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks

We propose ADOM - an accelerated method for smooth and strongly convex d...
02/18/2021 ∙ by Dmitry Kovalev, et al. ∙ 10 ∙ share

read it
IntSGD: Floatless Compression of Stochastic Gradients

We propose a family of lossy integer compressions for Stochastic Gradien...
02/16/2021 ∙ by Konstantin Mishchenko, et al. ∙ 17 ∙ share

read it
MARINA: Faster Non-Convex Distributed Learning with Compression

We develop and analyze MARINA: a new communication efficient method for ...
02/15/2021 ∙ by Eduard Gorbunov, et al. ∙ 6 ∙ share

read it
Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization

Large scale distributed optimization has become the default tool for the...
02/14/2021 ∙ by Mher Safaryan, et al. ∙ 16 ∙ share

read it
Distributed Second Order Methods with Fast Rates and Compressed Communication

We develop several new communication-efficient second-order methods for ...
02/14/2021 ∙ by Rustem Islamov, et al. ∙ 8 ∙ share

read it
Proximal and Federated Random Reshuffling

Random Reshuffling (RR), also known as Stochastic Gradient Descent (SGD)...
02/12/2021 ∙ by Konstantin Mishchenko, et al. ∙ 7 ∙ share

read it
A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!

Decentralized optimization methods enable on-device training of machine ...
11/03/2020 ∙ by Dmitry Kovalev, et al. ∙ 22 ∙ share

read it
Local SGD: Unified Theory and New Efficient Methods

We present a unified framework for analyzing local SGD methods in the co...
11/03/2020 ∙ by Eduard Gorbunov, et al. ∙ 62 ∙ share

read it
Optimal Client Sampling for Federated Learning

It is well understood that client-master communication can be a primary ...
10/26/2020 ∙ by Wenlin Chen, et al. ∙ 6 ∙ share

read it
Linearly Converging Error Compensated SGD

In this paper, we propose a unified analysis of variants of distributed ...
10/23/2020 ∙ by Eduard Gorbunov, et al. ∙ 1 ∙ share

read it
Optimal Gradient Compression for Distributed and Federated Learning

Communicating information, like gradient vectors, between computing node...
10/07/2020 ∙ by Alyazeed Albasyoni, et al. ∙ 0 ∙ share

read it
Lower Bounds and Optimal Algorithms for Personalized Federated Learning

In this work, we consider the optimization formulation of personalized f...
10/05/2020 ∙ by Filip Hanzely, et al. ∙ 0 ∙ share

read it
Distributed Proximal Splitting Algorithms with Rates and Acceleration

We analyze several generic proximal splitting algorithms well suited for...
10/02/2020 ∙ by Laurent Condat, et al. ∙ 0 ∙ share

read it
Variance-Reduced Methods for Machine Learning

Stochastic optimization lies at the heart of machine learning, and its c...
10/02/2020 ∙ by Robert M. Gower, et al. ∙ 20 ∙ share

read it
PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization

In this paper, we propose a novel stochastic gradient estimator—ProbAbil...
08/25/2020 ∙ by Zhize Li, et al. ∙ 8 ∙ share

read it
Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization

We consider the task of decentralized minimization of the sum of smooth ...
06/21/2020 ∙ by Dmitry Kovalev, et al. ∙ 19 ∙ share

read it
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization

We present a unified theorem for the convergence analysis of stochastic ...
06/20/2020 ∙ by Ahmed Khaled, et al. ∙ 30 ∙ share

read it
A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning

Modern large-scale machine learning applications require stochastic opti...
06/19/2020 ∙ by Samuel Horvath, et al. ∙ 6 ∙ share

read it
Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm

We consider the task of sampling with respect to a log concave probabili...
06/16/2020 ∙ by Adil Salim, et al. ∙ 16 ∙ share

read it
A Unified Analysis of Stochastic Gradient Methods for Nonconvex Federated Optimization

In this paper, we study the performance of a large family of SGD variant...
06/12/2020 ∙ by Zhize Li, et al. ∙ 18 ∙ share

read it
Random Reshuffling: Simple Analysis with Vast Improvements

Random Reshuffling (RR) is an algorithm for minimizing finite-sum functi...
06/10/2020 ∙ by Konstantin Mishchenko, et al. ∙ 17 ∙ share

read it
Adaptive Learning of the Optimal Mini-Batch Size of SGD

Recent advances in the theoretical understandingof SGD (Qian et al., 201...
05/03/2020 ∙ by Motasem Alfarra, et al. ∙ 22 ∙ share

read it
On the Convergence Analysis of Asynchronous SGD for Solving Consistent Linear Systems

In the realm of big data and machine learning, data-parallel, distribute...
04/05/2020 ∙ by Atal Narayan Sahu, et al. ∙ 0 ∙ share

read it
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms

We introduce a new primal-dual algorithm for minimizing the sum of three...
04/03/2020 ∙ by Adil Salim, et al. ∙ 8 ∙ share

read it
From Local SGD to Local Fixed Point Methods for Federated Learning

Most algorithms for solving optimization problems or finding saddle poin...
04/03/2020 ∙ by Grigory Malinovsky, et al. ∙ 0 ∙ share

read it
On Biased Compression for Distributed Learning

In the last few years, various communication compression techniques have...
02/27/2020 ∙ by Aleksandr Beznosikov, et al. ∙ 15 ∙ share

read it
Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization

Due to the high communication cost in distributed and federated learning...
02/26/2020 ∙ by Zhize Li, et al. ∙ 0 ∙ share

read it
Fast Linear Convergence of Randomized BFGS

Since the late 1950's when quasi-Newton methods first appeared, they hav...
02/26/2020 ∙ by Dmitry Kovalev, et al. ∙ 0 ∙ share

read it
Stochastic Subspace Cubic Newton Method

In this paper, we propose a new randomized second-order optimization alg...
02/21/2020 ∙ by Filip Hanzely, et al. ∙ 0 ∙ share

read it
Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor

In order to mitigate the high communication cost in distributed and fede...
02/20/2020 ∙ by Mher Safaryan, et al. ∙ 13 ∙ share

read it
Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization

Adaptivity is an important yet under-studied property in modern optimiza...
02/13/2020 ∙ by Samuel Horvath, et al. ∙ 4 ∙ share

read it
Variance Reduced Coordinate Descent with Acceleration: New Method With a Surprising Application to Finite-Sum Problems

We propose an accelerated version of stochastic variance reduced coordin...
02/11/2020 ∙ by Filip Hanzely, et al. ∙ 0 ∙ share

read it
Federated Learning of a Mixture of Global and Local Models

We propose a new optimization formulation for training federated learnin...
02/10/2020 ∙ by Filip Hanzely, et al. ∙ 7 ∙ share

read it
Better Theory for SGD in the Nonconvex World

Large-scale nonconvex optimization problems are ubiquitous in modern mac...
02/09/2020 ∙ by Ahmed Khaled, et al. ∙ 26 ∙ share

read it
Distributed Fixed Point Methods with Compressed Iterates

We propose basic and natural assumptions under which iterative optimizat...
12/20/2019 ∙ by Sélim Chraibi, et al. ∙ 0 ∙ share

read it
Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates

We present two new remarkably simple stochastic second-order methods for...
12/03/2019 ∙ by Dmitry Kovalev, et al. ∙ 13 ∙ share

read it
Better Communication Complexity for Local SGD

We revisit the local Stochastic Gradient Descent (local SGD) method and ...
09/10/2019 ∙ by Ahmed Khaled, et al. ∙ 0 ∙ share

read it
Gradient Descent with Compressed Iterates

We propose and analyze a new type of stochastic first order method: grad...
09/10/2019 ∙ by Ahmed Khaled, et al. ∙ 28 ∙ share

read it
First Analysis of Local GD on Heterogeneous Data

We provide the first convergence analysis of local gradient descent for ...
09/10/2019 ∙ by Ahmed Khaled, et al. ∙ 32 ∙ share

read it
Stochastic Convolutional Sparse Coding

State-of-the-art methods for Convolutional Sparse Coding usually employ ...
08/31/2019 ∙ by Jinhui Xiong, et al. ∙ 20 ∙ share

read it
Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates

We propose a new algorithm---Stochastic Proximal Langevin Algorithm (SPL...
05/28/2019 ∙ by Adil Salim, et al. ∙ 0 ∙ share

read it
Direct Nonlinear Acceleration

Optimization acceleration techniques such as momentum play a key role in...
05/28/2019 ∙ by Aritra Dutta, et al. ∙ 0 ∙ share

read it
Revisiting Stochastic Extragradient

We consider a new extension of the extragradient method that is motivate...
05/27/2019 ∙ by Konstantin Mishchenko, et al. ∙ 0 ∙ share

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

We propose a remarkably general variance-reduced method suitable for sol...
05/27/2019 ∙ by Filip Hanzely, et al. ∙ 0 ∙ share

read it
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent

In this paper we introduce a unified analysis of a large family of varia...
05/27/2019 ∙ by Eduard Gorbunov, et al. ∙ 0 ∙ share

read it
Natural Compression for Distributed Deep Learning

Due to their hunger for big data, modern deep learning models are traine...
05/27/2019 ∙ by Samuel Horvath, et al. ∙ 0 ∙ share

read it

Peter Richtarik

Featured Co-authors