Timezone: »
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.
Author Information
Damek Davis (Cornell University)
Brent Edmunds (University of California)
Madeleine Udell (Cornell)
More from the Same Authors
-
2021 Poster: Can we globally optimize cross-validation loss? Quasiconvexity in ridge regression »
Will Stephenson · Zachary Frangella · Madeleine Udell · Tamara Broderick -
2020 Poster: Matrix Completion with Quantified Uncertainty through Low Rank Gaussian Copula »
Yuxuan Zhao · Madeleine Udell -
2020 Poster: Approximate Cross-Validation with Low-Rank Data in High Dimensions »
Will Stephenson · Madeleine Udell · Tamara Broderick -
2019 Poster: Factor Group-Sparse Regularization for Efficient Low-Rank Matrix Recovery »
Jicong Fan · Lijun Ding · Yudong Chen · Madeleine Udell -
2018 : Panel: Explainability, Fairness and Human Aspects in Financial Services »
Madeleine Udell · Jiahao Chen · Nitzan Mekel-Bobrov · Manuela Veloso · Jon Kleinberg · Andrea Freeman · Samik Chandarana · Jacob Sisk · Michael McBurnett -
2018 : Invited Talk 1: Fairness and Causality with Missing Data »
Madeleine Udell -
2018 Poster: Limited Memory Kelley's Method Converges for Composite Convex and Submodular Objectives »
Song Zhou · Swati Gupta · Madeleine Udell -
2018 Spotlight: Limited Memory Kelley's Method Converges for Composite Convex and Submodular Objectives »
Song Zhou · Swati Gupta · Madeleine Udell -
2018 Poster: Causal Inference with Noisy and Missing Covariates via Matrix Factorization »
Nathan Kallus · Xiaojie Mao · Madeleine Udell -
2017 Poster: Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data »
Joel A Tropp · Alp Yurtsever · Madeleine Udell · Volkan Cevher