Optimization Online


The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems

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

Abstract: We introduce the Asynchronous PALM algorithm, a new extension of the Proximal Alternating Linearized Minimization (PALM) algorithm for solving nonconvex nonsmooth optimization problems. Like the PALM algorithm, each step of the Asynchronous PALM algorithm updates a single block of coordinates; but unlike the PALM algorithm, the Asynchronous PALM algorithm eliminates the need for sequential updates that occur one after the other. Instead, our new algorithm allows each of the coordinate blocks to be updated asynchronously and in any order, which means that any number of computing cores can compute updates in parallel without synchronizing their computations. In practice, this asynchronization strategy often leads to speedups that increase linearly with the number of computing cores. We introduce two variants of the Asynchronous PALM algorithm, one stochastic and one deterministic. In the stochastic and deterministic cases, we show that cluster points of the algorithm are stationary points. In the deterministic case, we show that the algorithm converges globally whenever the Kurdyka-Lojasiewicz property holds for a function closely related to the objective function, and we derive its convergence rate in a common special case. Finally, we provide a concrete case in which our assumptions hold.

Keywords: stochastic algorithm, nonconvex, nonsmooth, first-order optimization, coordinate descent, asynchronous

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: UCLA CAM Report TBA

Download: [Postscript][PDF]

Entry Submitted: 03/08/2016
Entry Accepted: 03/08/2016
Entry Last Modified: 04/02/2016

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