  


SMART: The Stochastic Monotone Aggregated RootFinding Algorithm
Damek Davis (damekmath.ucla.edu) Abstract: We introduce the Stochastic Monotone Aggregated RootFinding (SMART) algorithm, a new randomized operatorsplitting 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 blackboxes 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 operatorsplitting 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 largescale optimization Keywords: stochastic algorithm, operatorsplitting, aggregated gradient, variance reduction, coordinate updates, asynchronous updates Category 1: Convex and Nonsmooth Optimization Citation: UCLA CAM Report 1568 Download: [PDF] Entry Submitted: 12/10/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  