Optimization Online


ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates

Zhimin Peng (zhimin.peng***at***math.ucla.edu)
Yangyang Xu (yangyang.xu***at***uwaterloo.ca)
Ming Yan (yanm***at***math.ucla.edu)
Wotao Yin (wotaoyin***at***math.ucla.edu)

Abstract: We propose ARock, an asynchronous parallel algorithmic framework for finding a fixed point to a nonexpansive operator. In the framework, a set of agents (machines, processors, or cores) update a sequence of randomly selected coordinates of the unknown variable in an asynchronous parallel fashion. As special cases of ARock, novel algorithms for linear systems, convex optimization, machine learning, distributed and decentralized optimization are introduced. We show that if the operator has a fixed point and is nonexpansive, then with probability one, the sequence of points generated by ARock converges to a fixed point. Stronger convergence properties such as linear convergence are obtained under stronger conditions. Very promising numerical performance of ARock has been observed. Considering the paper length, we present the numerical results of solving linear equations and sparse logistic regression problems.

Keywords: asynchronous, parallel, coordinate, fixed-point iteration, nonexpansive operator, Alternating Direction Method of Multipliers

Category 1: Optimization Software and Modeling Systems (Parallel Algorithms )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 06/09/2015
Entry Accepted: 07/02/2015
Entry Last Modified: 07/08/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