Published on Sun Jun 06 2021

MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization

Laurent Condat, Peter Richtárik

We propose a generic variance-reduced algorithm, which we call MUltiple RANdomized Algorithm (MURANA) MURANA minimizes a sum of several smooth functions plus a regularizer, in a sequential or distributed manner.

5
0
0
Abstract

We propose a generic variance-reduced algorithm, which we call MUltiple RANdomized Algorithm (MURANA), for minimizing a sum of several smooth functions plus a regularizer, in a sequential or distributed manner. Our method is formulated with general stochastic operators, which allow us to model various strategies for reducing the computational complexity. For example, MURANA supports sparse activation of the gradients, and also reduction of the communication load via compression of the update vectors. This versatility allows MURANA to cover many existing randomization mechanisms within a unified framework. However, MURANA also encodes new methods as special cases. We highlight one of them, which we call ELVIRA, and show that it improves upon Loopless SVRG.

Wed May 02 2018
Machine Learning
k-SVRG: Variance Reduction for Large Scale Optimization
Variance reduced stochastic gradient (SGD) methods converge significantly faster than the vanilla SGD counterpart. However, these methods are not very practical on large scale problems. We propose -SVRG that addresses these issues by making best use of available memory.
0
0
0
Mon Dec 30 2013
Machine Learning
Communication Efficient Distributed Optimization using an Approximate Newton-type Method
We present a novel Newton-type method for distributed optimization. The method is particularly well suited for stochastic optimization and learning problems. For quadratic objectives, the method enjoys a linear rate of convergence.
0
0
0
Tue Jun 20 2017
Machine Learning
A Unified Approach to Adaptive Regularization in Online and Stochastic Optimization
We describe a framework for deriving and analyzing online optimization algorithms that incorporate adaptive, data-dependent regularization. Such algorithms have been proven useful in stochastic optimization by reshaping gradients according to the geometry of the data.
0
0
0
Tue Jun 23 2015
Machine Learning
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
We study optimization algorithms based on variance reduction for stochastic gradient descent (SGD) We propose an asynchronous algorithm grounded in our framework, and prove its fast convergence. Our method achieves near linear speedup in sparse settings common to machine learning.
0
0
0
Tue May 20 2014
Machine Learning
Convex Optimization: Algorithms and Complexity
This monograph presents the main complexity theorems in convex optimization and their corresponding algorithms. We also pay special attention to non-Euclidean settings and discuss their relevance in machine learning.
0
0
0
Thu Sep 26 2019
Machine Learning
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
In the era of big data, one of the key challenges is the development of novel optimization algorithms that can accommodate vast amounts of data. In this thesis we are focusing on the design, complexity analysis and efficient implementations of such algorithms.
0
0
0
Sat Jan 26 2019
Machine Learning
Distributed Learning with Compressed Gradient Differences
Training large machine learning models requires a distributed computing approach. Several methods based on the compression of updates were recently proposed. None of these methods are able to learn the gradients, which renders them incapable of converging.
2
7
21
Wed Feb 17 2016
Machine Learning
Communication-Efficient Learning of Deep Networks from Decentralized Data
Modern mobile devices have access to a wealth of data suitable for learning models. This rich data is often privacy sensitive, large in quantity, or both. We present a practical method for the federated learning of deep networks.
3
0
4
Tue Dec 10 2019
Machine Learning
Advances and Open Problems in Federated Learning
Federated learning (FL) is a machine learning setting where many clients collaboratively train a model. FL can mitigate many of the systemic privacy risks and costs resulting from traditional, centralized machine learning approaches.
2
0
2
Sat Jun 20 2020
Machine Learning
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization
We present a unified theorem for the convergence analysis of stochastic gradient algorithms. We do this by extending the unified analysis of Gorbunov, Hanzely\& Richt\'arik (2020) and dropping the requirement that the loss function be strongly convex.
0
0
0
Fri Oct 23 2020
Machine Learning
Linearly Converging Error Compensated SGD
In this paper, we propose a unified analysis of variants of distributed SGD with arbitrary compressions and delayed updates. Our framework is general enough to cover different variants of quantized SGD, Error-Compensated SGD (EC-SGD) and SGD with delayed updates (D- SGD) Via a single theorem,
0
0
0
Tue Jul 01 2014
Machine Learning
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
SAGA improves on the theorybehind SAG and SVRG, with better theoretical convergence rates. SAGA supports non-strongly convex problems directly, and is adaptive to any inherent strong convexity of the problem.
0
0
0