The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems

Abstract

We introduce the Asynchronous PALM algorithm, a new extension of the Proximal Alternating Linearized Minimization (PALM) algorithm for solving nonsmooth, nonconvex 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 \textit{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-Łojasiewicz 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.

References in corpus (5)

• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Coordinate Friendly Structures, Algorithms and Applications
• SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm

Cited by in corpus (10)

• A Stochastic Alternating Direction Method of Multipliers for Non-smooth and Non-convex Optimization
• Asynchronous Parallel Algorithms for Nonconvex Big-Data Optimization. Part II: Complexity and Numerical Results
• A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning
• SPRING: A fast stochastic proximal alternating method for non-smooth non-convex optimization
• TMAC: A Toolbox of Modern Async-Parallel, Coordinate, Splitting, and Stochastic Methods
• Asynchronous Stochastic Proximal Methods for Nonconvex Nonsmooth Optimization
• Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization
• Block Distributed Majorize-Minimize Memory Gradient Algorithm and its application to 3D image restoration
• A Model Parallel Proximal Stochastic Gradient Algorithm for Partially Asynchronous Systems
• Asynchronous Variance-reduced Block Schemes for Composite Nonconvex Stochastic Optimization: Block-specific Steplengths and Adapted Batch-sizes