Asynchronous Parallel Algorithms for Nonconvex Big-Data Optimization. Part II: Complexity and Numerical Results

Abstract

We present complexity and numerical results for a new asynchronous parallel algorithmic method for the minimization of the sum of a smooth nonconvex function and a convex nonsmooth regularizer, subject to both convex and nonconvex constraints. The proposed method hinges on successive convex approximation techniques and a novel probabilistic model that captures key elements of modern computational architectures and asynchronous implementations in a more faithful way than state-of-the-art models. In the companion paper we provided a detailed description on the probabilistic model and gave convergence results for a diminishing stepsize version of our method. Here, we provide theoretical complexity results for a fixed stepsize version of the method and report extensive numerical comparisons on both convex and nonconvex problems demonstrating the efficiency of our approach.

This is the second part of a two-paper work. The first part can be found at: arXiv:1607.04818

References in corpus (7)

• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Parallel and Distributed Methods for Nonconvex Optimization--Part II: Applications
• Parallel Selective Algorithms for Big Data Optimization
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
• The Asynchronous PALM Algorithm for Nonsmooth Nonconvex Problems
• Minimization of Transformed $L_1$ Penalty: Theory, Difference of Convex Function Algorithm, and Robust Application in Compressed Sensing

Cited by in corpus (2)

• Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization
• Asynchronous Decentralized Successive Convex Approximation