Avoiding Communication in Primal and Dual Block Coordinate Descent Methods
Authors:
- Aditya DevarakondaADAditya Devarakonda
- Kimon FountoulakisKFKimon Fountoulakis
- James DemmelJDJames Demmel
- Michael W. MahoneyMMMichael W. Mahoney
- 2 January 2019
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 41 (1) , C1-C27
Abstract
Primal and dual block coordinate descent methods are iterative methods for solving regularized and unregularized optimization problems. Distributed-memory parallel implementations of these methods have become popular in analyzing large machine learning datasets. However, existing implementations communicate at every iteration, which, on modern data center and supercomputing architectures, often dominates the cost of floating-point computation. Recent results on communication-avoiding Krylov subspace methods suggest that large speedups are possible by re-organizing iterative algorithms to avoid communication. We show how applying similar algorithmic transformations can lead to primal and dual block coordinate descent methods that only communicate every $s$ iterations---where $s$ is a tuning parameter---instead of every iteration for the regularized least-squares problem. We show that the communication-avoiding variants reduce the number of synchronizations by a factor of $s$ on distributed-memory parallel ...
Keywords
All Related Versions
Funding Information
- Samsung
- U.S. Department of Energy (DE-SC0010200, DE-SC0008700, DE-AC02-05CH11231)
- Intel Corporation
- Defense Advanced Research Projects Agency
- Oracle
- HP Development Company
- Huawei Technologies
- National Science Foundation (DGE 1106400)
- Cray Incorporated (47277)
- Nvidia
- ASPIRE Lab
- LGE
This publication has 21 references indexed in Scilit:
- Avoiding Communication in Nonsymmetric Lanczos-Based Krylov Subspace MethodsSIAM Journal on Scientific Computing, 2013
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite functionMathematical Programming, 2012
- Efficiency of Coordinate Descent Methods on Huge-Scale Optimization ProblemsSIAM Journal on Optimization, 2012
- Communication-optimal Parallel and Sequential QR and LU FactorizationsSIAM Journal on Scientific Computing, 2012
- LIBSVMACM Transactions on Intelligent Systems and Technology, 2011
- An efficient nonsymmetric Lanczos method on parallel vector computersJournal of Computational and Applied Mathematics, 1992
- On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchyParallel Computing, 1989
- s-step iterative methods for symmetric linear systemsJournal of Computational and Applied Mathematics, 1989
- Implementation of the GMRES Method Using Householder TransformationsSIAM Journal on Scientific and Statistical Computing, 1988
- Expected Length of the Longest Probe Sequence in Hash Code SearchingJournal of the ACM, 1981