  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.
