The Sound of APALM Clapping: Faster Nonsmooth Nonconvex Optimization with Stochastic Asynchronous PALM
arXiv:1606.02338
Abstract
We introduce the Stochastic Asynchronous Proximal Alternating Linearized Minimization (SAPALM) method, a block coordinate stochastic proximal-gradient method for solving nonconvex, nonsmooth optimization problems. SAPALM is the first asynchronous parallel optimization method that provably converges on a large class of nonconvex, nonsmooth problems. We prove that SAPALM matches the best known rates of convergence --- among synchronous or asynchronous methods --- on this problem class. We provide upper bounds on the number of workers for which we can expect to see a linear speedup, which match the best bounds known for less complex problems, and show that in practice SAPALM achieves this linear speedup. We demonstrate state-of-the-art performance on several matrix factorization problems.
References in corpus (6)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
- ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
- An Asynchronous Parallel Randomized Kaczmarz Algorithm
- A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
- SMART: The Stochastic Monotone Aggregated Root-Finding Algorithm
Cited by in corpus (9)
- Breaking the Nonsmooth Barrier: A Scalable Parallel Method for Composite Optimization
- Inertial Stochastic PALM (iSPALM) and Applications in Machine Learning
- 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
- Asynchronous Stochastic Proximal Methods for Nonconvex Nonsmooth Optimization
- Stochastic Optimization for Non-convex Inf-Projection Problems
- 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