Reducing communication in proximal Newton methods for sparse least squares problems

Saeed Soori, James Demmel, Aditya Devarakonda, Mert Gurbuzbalaban, Zachary Blanco, Maryam Mehri Dehnavi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Proximal Newton methods are iterative algorithms that solve l1-regularized least squares problems. Distributed-memory implementation of these methods have become popular since they enable the analysis of large-scale machine learning problems. However, the scalability of these methods is limited by the communication overhead on modern distributed architecture. We propose a stochastic variance-reduced proximal method along with iteration-overlapping and Hessian-reuse to find an efficient trade-off between computation complexity and data communication. The proposed RC-SFSITA algorithm reduces latency costs by a factor of k without altering bandwidth costs. RC-SFISTA is implemented on both MPI and Spark and compared to the state-of-the-art framework, ProxCoCoA. The performance of RC-SFISTA is evaluated on 1 to 512 nodes for multiple benchmarks and demonstrates speedups of up to 12× compared to ProxCoCoA with scaling properties that outperform the original algorithm.

Original languageEnglish (US)
Title of host publicationProceedings of the 47th International Conference on Parallel Processing, ICPP 2018
PublisherAssociation for Computing Machinery
ISBN (Print)9781450365109
DOIs
StatePublished - Aug 13 2018
Event47th International Conference on Parallel Processing, ICPP 2018 - Eugene, United States
Duration: Aug 14 2018Aug 16 2018

Publication series

NameACM International Conference Proceeding Series

Other

Other47th International Conference on Parallel Processing, ICPP 2018
CountryUnited States
CityEugene
Period8/14/188/16/18

Fingerprint

Newton-Raphson method
Communication
Electric sparks
Learning systems
Scalability
Costs
Bandwidth
Data storage equipment

All Science Journal Classification (ASJC) codes

  • Human-Computer Interaction
  • Computer Networks and Communications
  • Computer Vision and Pattern Recognition
  • Software

Cite this

Soori, S., Demmel, J., Devarakonda, A., Gurbuzbalaban, M., Blanco, Z., & Mehri Dehnavi, M. (2018). Reducing communication in proximal Newton methods for sparse least squares problems. In Proceedings of the 47th International Conference on Parallel Processing, ICPP 2018 [a22] (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3225058.3225131
Soori, Saeed ; Demmel, James ; Devarakonda, Aditya ; Gurbuzbalaban, Mert ; Blanco, Zachary ; Mehri Dehnavi, Maryam. / Reducing communication in proximal Newton methods for sparse least squares problems. Proceedings of the 47th International Conference on Parallel Processing, ICPP 2018. Association for Computing Machinery, 2018. (ACM International Conference Proceeding Series).
@inproceedings{3b3eec451908498db207b673834da6b5,
title = "Reducing communication in proximal Newton methods for sparse least squares problems",
abstract = "Proximal Newton methods are iterative algorithms that solve l1-regularized least squares problems. Distributed-memory implementation of these methods have become popular since they enable the analysis of large-scale machine learning problems. However, the scalability of these methods is limited by the communication overhead on modern distributed architecture. We propose a stochastic variance-reduced proximal method along with iteration-overlapping and Hessian-reuse to find an efficient trade-off between computation complexity and data communication. The proposed RC-SFSITA algorithm reduces latency costs by a factor of k without altering bandwidth costs. RC-SFISTA is implemented on both MPI and Spark and compared to the state-of-the-art framework, ProxCoCoA. The performance of RC-SFISTA is evaluated on 1 to 512 nodes for multiple benchmarks and demonstrates speedups of up to 12× compared to ProxCoCoA with scaling properties that outperform the original algorithm.",
author = "Saeed Soori and James Demmel and Aditya Devarakonda and Mert Gurbuzbalaban and Zachary Blanco and {Mehri Dehnavi}, Maryam",
year = "2018",
month = "8",
day = "13",
doi = "10.1145/3225058.3225131",
language = "English (US)",
isbn = "9781450365109",
series = "ACM International Conference Proceeding Series",
publisher = "Association for Computing Machinery",
booktitle = "Proceedings of the 47th International Conference on Parallel Processing, ICPP 2018",

}

Soori, S, Demmel, J, Devarakonda, A, Gurbuzbalaban, M, Blanco, Z & Mehri Dehnavi, M 2018, Reducing communication in proximal Newton methods for sparse least squares problems. in Proceedings of the 47th International Conference on Parallel Processing, ICPP 2018., a22, ACM International Conference Proceeding Series, Association for Computing Machinery, 47th International Conference on Parallel Processing, ICPP 2018, Eugene, United States, 8/14/18. https://doi.org/10.1145/3225058.3225131

Reducing communication in proximal Newton methods for sparse least squares problems. / Soori, Saeed; Demmel, James; Devarakonda, Aditya; Gurbuzbalaban, Mert; Blanco, Zachary; Mehri Dehnavi, Maryam.

Proceedings of the 47th International Conference on Parallel Processing, ICPP 2018. Association for Computing Machinery, 2018. a22 (ACM International Conference Proceeding Series).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Reducing communication in proximal Newton methods for sparse least squares problems

AU - Soori, Saeed

AU - Demmel, James

AU - Devarakonda, Aditya

AU - Gurbuzbalaban, Mert

AU - Blanco, Zachary

AU - Mehri Dehnavi, Maryam

PY - 2018/8/13

Y1 - 2018/8/13

N2 - Proximal Newton methods are iterative algorithms that solve l1-regularized least squares problems. Distributed-memory implementation of these methods have become popular since they enable the analysis of large-scale machine learning problems. However, the scalability of these methods is limited by the communication overhead on modern distributed architecture. We propose a stochastic variance-reduced proximal method along with iteration-overlapping and Hessian-reuse to find an efficient trade-off between computation complexity and data communication. The proposed RC-SFSITA algorithm reduces latency costs by a factor of k without altering bandwidth costs. RC-SFISTA is implemented on both MPI and Spark and compared to the state-of-the-art framework, ProxCoCoA. The performance of RC-SFISTA is evaluated on 1 to 512 nodes for multiple benchmarks and demonstrates speedups of up to 12× compared to ProxCoCoA with scaling properties that outperform the original algorithm.

AB - Proximal Newton methods are iterative algorithms that solve l1-regularized least squares problems. Distributed-memory implementation of these methods have become popular since they enable the analysis of large-scale machine learning problems. However, the scalability of these methods is limited by the communication overhead on modern distributed architecture. We propose a stochastic variance-reduced proximal method along with iteration-overlapping and Hessian-reuse to find an efficient trade-off between computation complexity and data communication. The proposed RC-SFSITA algorithm reduces latency costs by a factor of k without altering bandwidth costs. RC-SFISTA is implemented on both MPI and Spark and compared to the state-of-the-art framework, ProxCoCoA. The performance of RC-SFISTA is evaluated on 1 to 512 nodes for multiple benchmarks and demonstrates speedups of up to 12× compared to ProxCoCoA with scaling properties that outperform the original algorithm.

UR - http://www.scopus.com/inward/record.url?scp=85054856512&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054856512&partnerID=8YFLogxK

U2 - 10.1145/3225058.3225131

DO - 10.1145/3225058.3225131

M3 - Conference contribution

SN - 9781450365109

T3 - ACM International Conference Proceeding Series

BT - Proceedings of the 47th International Conference on Parallel Processing, ICPP 2018

PB - Association for Computing Machinery

ER -

Soori S, Demmel J, Devarakonda A, Gurbuzbalaban M, Blanco Z, Mehri Dehnavi M. Reducing communication in proximal Newton methods for sparse least squares problems. In Proceedings of the 47th International Conference on Parallel Processing, ICPP 2018. Association for Computing Machinery. 2018. a22. (ACM International Conference Proceeding Series). https://doi.org/10.1145/3225058.3225131