An Asynchronous Parallel Stochastic Coordinate Descent Algorithm

2013/11/08 by Liu, Ji, Wright, Stephen J., Ré, Christopher +2 · 1 citation
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1311.1873

Abstract

We describe an asynchronous parallel stochastic coordinate descent algorithm for minimizing smooth unconstrained or separably constrained functions. The method achieves a linear convergence rate on functions that satisfy an essential strong convexity property and a sublinear rate (1/K) on general convex functions. Near-linear speedup on a multicore system can be expected if the number of processors is O(n^1/2) in unconstrained optimization and O(n^1/4) in the separable-constrained case, where n is the number of variables. We describe results from implementation on 40-core processors.

Cited by

• Randomized coordinate gradient descent almost surely escapes strict saddle points

Related

• Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
• Fully Asynchronous Stochastic Coordinate Descent: A Tight Lower Bound on the Parallelism Achieving Linear Speedup
• Parallel Stochastic Asynchronous Coordinate Descent: Tight Bounds on the Possible Parallelism
• An Analysis of Asynchronous Stochastic Accelerated Coordinate Descent
• Accelerated, Parallel and Proximal Coordinate Descent