Optimization Online


SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm

Damek Davis (damek***at***math.ucla.edu)

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

Keywords: stochastic algorithm, operator-splitting, aggregated gradient, variance reduction, coordinate updates, asynchronous updates

Category 1: Convex and Nonsmooth Optimization

Citation: UCLA CAM Report 15-68

Download: [PDF]

Entry Submitted: 12/10/2015
Entry Accepted: 12/10/2015
Entry Last Modified: 12/29/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society