SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm

Abstract

We introduce the Stochastic Monotone Aggregated Root-Finding (SMART) algorithm, a new randomized operator-splitting scheme for finding roots of finite sums of operators. These algorithms are similar to the growing class of incremental aggregated gradient algorithms, which minimize finite sums of functions; the difference is that we replace gradients of functions with black-boxes called operators, which represent subproblems to be solved during the algorithm. By replacing gradients with operators, we increase our modeling power, and we simplify the application and analysis of the resulting algorithms. The operator point of view also makes it easy to extend our algorithms to allow arbitrary sampling and updating of blocks of coordinates throughout the algorithm. Implementing and running an algorithm like this on a computing cluster can be slow if we force all computing nodes to be synched up at all times. To take better advantage of parallelism, we allow computing nodes to delay updates and break synchronization. This paper has several technical and practical contributions. We prove the weak, almost sure convergence of a new class of randomized operator-splitting schemes in separable Hilbert spaces; we prove that this class of algorithms convergences linearly in expectation when a weak regularity property holds; we highlight connections to other algorithms; and we introduce a few new algorithms for large-scale optimization.

70 pages

References in corpus (10)

• ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• An Asynchronous Parallel Randomized Kaczmarz Algorithm
• Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions
• Incremental Aggregated Proximal and Augmented Lagrangian Algorithms
• Variance Reduced Stochastic Gradient Descent with Neighbors
• Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping
• The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growth
• Asynchronous Block-Iterative Primal-Dual Decomposition Methods for Monotone Inclusions

Cited by in corpus (7)

• Reducing Noise in GAN Training with Variance Reduced Extragradient
• The proximal point method revisited
• The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
• The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning
• Hybrid Acceleration Scheme for Variance Reduced Stochastic Optimization Algorithms