732 citations · 3.2k across the 65 of their papers we have counts for
15 papers · 1 filter
Monotone and nonmonotone linearized block coordinate descent methods for nonsmooth composite optimization problems
Yassine Nabou, Lahcen El Bourkhissi, Sebastian U. Stich +1
In this paper, we introduce both monotone and nonmonotone variants of LiBCoD, a \textbf{Li}nearized \textbf{B}lock \textbf{Co}ordinate \textbf{D}escent method for solving composite…
Revisiting LocalSGD and SCAFFOLD: Improved Rates and Missing Analysis
Ruichen Luo, Sebastian U Stich, Samuel Horváth +1
LocalSGD and SCAFFOLD are widely used methods in distributed stochastic optimization, with numerous applications in machine learning, large-scale data processing, and federated lea…
Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions
Nikita Doikov, Sebastian U. Stich, Martin Jaggi
The performance of optimization methods is often tied to the spectrum of the objective Hessian. Yet, conventional assumptions, such as smoothness, do often not enable us to make fi…
Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates
Siqi Zhang, Sayantan Choudhury, Sebastian U Stich +1
Distributed and federated learning algorithms and techniques associated primarily with minimization problems. However, with the increase of minimax optimization and variational ine…
Decentralized Gradient Tracking with Local Steps
Yue Liu, Tao Lin, Anastasia Koloskova +1
Gradient tracking (GT) is an algorithm designed for solving decentralized optimization problems over a network (such as training a machine learning model). A key feature of GT is a…
Decentralized Local Stochastic Extra-Gradient for Variational Inequalities
Aleksandr Beznosikov, Pavel Dvurechensky, Anastasia Koloskova +3
We consider distributed stochastic variational inequalities (VIs) on unbounded domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We…
A Linearly Convergent Algorithm for Decentralized Optimization: Sending Less Bits for Free!
Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi +2
Decentralized optimization methods enable on-device training of machine learning models without a central coordinator. In many scenarios communication between devices is energy dem…
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko +2
We consider distributed optimization where the objective function is spread among different devices, each sending incremental model updates to a central server. To alleviate the co…
Efficient Greedy Coordinate Descent for Composite Problems
Sai Praneeth Karimireddy, Anastasia Koloskova, Sebastian U. Stich +1
Coordinate descent with random coordinate selection is the current state of the art for many large scale optimization problems. However, greedy selection of the steepest coordinate…
Local SGD Converges Fast and Communicates Little
Sebastian U. Stich
Mini-batch stochastic gradient descent (SGD) is state of the art in large scale distributed training. The scheme can reach a linear speedup with respect to the number of workers, b…
k-SVRG: Variance Reduction for Large Scale Optimization
Anant Raj, Sebastian U. Stich
Variance reduced stochastic gradient (SGD) methods converge significantly faster than the vanilla SGD counterpart. However, these methods are not very practical on large scale prob…
Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
Robert M. Gower, Filip Hanzely, Peter Richtárik +1
We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particu…
On low complexity Acceleration Techniques for Randomized Optimization: Supplementary Online Material
Sebastian U. Stich
Recently it was shown by Nesterov (2011) that techniques form convex optimization can be used to successfully accelerate simple derivative-free randomized optimization methods. The…
Variable Metric Random Pursuit
Sebastian U. Stich, Christian L. Müller, Bernd Gärtner
We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and…
Optimization of Convex Functions with Random Pursuit
Sebastian U. Stich, Christian L. Müller, Bernd Gärtner
We consider unconstrained randomized optimization of convex objective functions. We analyze the Random Pursuit algorithm, which iteratively computes an approximate solution to the…