The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Parallel coordinate descent methods for big data optimization
Open accessAbstract
In this work we show that randomized (block) coordinate descent methods can be accelerated by parallelization when applied to the problem of minimizing the sum of a partially separable smooth convex function and a simple separable convex function. The theoretical speedup, as compared to the serial method, and referring to the number of iterations needed to approximately solve the problem with high probability, is a simple expression depending on the number of parallel processors and a natural and easily computable measure of separability of the smooth component of the objective function. In the worst case, when no degree of separability is present, there may be no speedup; in the best case, when the problem is separable, the speedup is equal to the number of processors. Our analysis also works in the mode when the number of blocks being updated at each iteration is random, which allows for modeling situations with busy or unreliable processors. We show that our algorithm is able to solve a LASSO problem involving a matrix with 20 billion nonzeros in 2 h on a large memory node with 24 cores.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Introductory Lectures on Convex Optimization: A Basic Course
Nesterov, Y. E. (2014) · Medical Entomology and Zoology · Cited by 3,557
Introductory Lectures on Convex Optimization
Nesterov, Y. (2004) · Applied Optimization · doi:10.1007/978-1-4419-8853-9 · Cited by 2,698
Gradient methods for minimizing composite functions
Nesterov, Y. (2013) · Mathematical Programming · doi:10.1007/s10107-012-0629-5 · Cited by 1,298
Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Niu, F., Recht, B., Re, C., & Wright, S. J. (2011) · arXiv · doi:10.48550/arxiv.1106.5730 · Cited by 1,211 · cited 2×
“Partially separable problems were independently studied in [9], where an asynchronous parallel stochastic gradient algorithm was developed to solve them.”
BackgroundMethodEfficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
Nesterov, Y. (2012) · SIAM Journal on Optimization · doi:10.1137/100802001 · Cited by 1,187
Iterative Methods by Space Decomposition and Subspace Correction
Xu, J. (1992) · SIAM Review · doi:10.1137/1034116 · Cited by 1,163
A Randomized Kaczmarz Algorithm with Exponential Convergence
Strohmer, T., & Vershynin, R. (2009) · Journal of Fourier Analysis and Applications · doi:10.1007/s00041-008-9030-4 · Cited by 903
Richtárik, P., & Takáč, M. (2014) · Mathematical Programming · doi:10.1007/s10107-012-0614-z · Cited by 654
Self-citationRandomized Methods for Linear Constraints: Convergence Rates and Conditioning
Leventhal, D., & Lewis, A. S. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0456 · Cited by 349
Stochastic methods for l 1 regularized loss minimization
Shalev-Shwartz, S., & Tewari, A. (2009) · Proceedings of the 26th Annual International Conference on Machine Learning · doi:10.1145/1553374.1553493 · Cited by 298
Scalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems
Yu, H.-F., Hsieh, C.-J., Si, S., & Dhillon, I. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.168 · Cited by 253
Parallel Coordinate Descent for L1-Regularized Loss Minimization
Bradley, J. K., Kyrola, A., Bickson, D., & Guestrin, C. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1105.5379 · Cited by 189
Distributed Coordinate Descent Method for Learning with Big Data
Richtárik, P., & Takáč, M. (2013) · Edinburgh Research Explorer (University of Edinburgh) · doi:10.48550/arxiv.1310.2059 · Cited by 182
Self-citationMini-Batch Primal and Dual Methods for SVMsPreprint
Takáč, M., Bijral, A. S., Richtárik, P., & Srebro, N. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.2314 · Cited by 148
Self-citationLi, Y., & Osher, S. (2009) · Inverse Problems and Imaging · doi:10.3934/ipi.2009.3.487 · Cited by 146
Parallel Coordinate Descent for L1-Regularized Loss Minimization
Kyrola, A., Bickson, D., Guestrin, C., & Bradley, J. K. (2011) · International Conference on Machine Learning · Cited by 146
On Convergence of an Augmented Lagrangian Decomposition Method for Sparse Convex Optimization
Ruszczyński, A. (1995) · Mathematics of Operations Research · doi:10.1287/moor.20.3.634 · Cited by 143
On the Nonasymptotic Convergence of Cyclic Coordinate Descent Methods
Saha, A., & Tewari, A. (2013) · SIAM Journal on Optimization · doi:10.1137/110840054 · Cited by 134
Stochastic Methods for l 1 -regularized Loss Minimization
Shalev‐Shwartz, S., & Tewari, A. (2011) · Journal of Machine Learning Research · Cited by 129
Necoara, I., & Pătraşcu, A. (2013) · Computational Optimization and Applications · doi:10.1007/s10589-013-9598-8 · Cited by 99
Subgradient methods for huge-scale optimization problems
Nesterov, Y. E. (2013) · Mathematical Programming · doi:10.1007/s10107-013-0686-4 · Cited by 88
Parallel and distributed sparse optimization
Peng, Z., Yan, M., & Yin, W. (2013) · Asilomar Conference on Signals, Systems and Computers (ACSSC) · doi:10.1109/acssc.2013.6810364 · Cited by 87
Necoara, I., & Clipici, D. (2013) · Journal of Process Control · doi:10.1016/j.jprocont.2012.12.012 · Cited by 81
Inexact Coordinate Descent: Complexity and Preconditioning
Tappenden, R., Richtárik, P., & Gondzio, J. (2016) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-016-0867-4 · Cited by 67
Self-citationNearest Neighbor based Greedy Coordinate Descent
Dhillon, I. S., Ravikumar, P., & Tewari, A. (2011) · Cited by 52
Smooth Minimization of Nonsmooth Functions with Parallel Coordinate Descent Methods
Fercoq, O., & Richtárik, P. (2019) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-030-12119-8_4 · Cited by 49
Self-citationAccelerated dual descent for network optimization
Zargham, M., Ribeiro, A., Ozdaglar, A., & Jadbabaie, A. (2011) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2011.5991367 · Cited by 40
Cited by
Wright, S. J. (2015) · Mathematical Programming · doi:10.1007/s10107-015-0892-3 · Cited by 1,438
Problem formulations and solvers in linear SVM: a review
Chauhan, V. K., Dahiya, K., & Sharma, A. (2019) · Artificial Intelligence Review · doi:10.1007/s10462-018-9614-6 · Cited by 660
Zhong, R. Y., Newman, S. T., Huang, G. Q., & Lan, S. (2016) · Computers & Industrial Engineering · doi:10.1016/j.cie.2016.07.013 · Cited by 586
Hong, M., Razaviyayn, M., Luo, Z.-Q., & Pang, J.-S. (2016) · IEEE Signal Processing Magazine · doi:10.1109/msp.2015.2481563 · Cited by 447
Petuum: A New Platform for Distributed Machine Learning on Big Data
Xing, E. P., Ho, Q., Dai, W., Kim, J. K., Wei, J., Lee, S., Zheng, X., Xie, P., Kumar, A., & Yu, Y. (2015) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2015.2472014 · Cited by 388
Metadata
- Authors
- Richtárik, P., & Takáč, M.
- Venue
- Mathematical Programming
- Published
- 2015-04-12
- Volume
- 156
- Issue
- 1-2
- Pages
- 433-484
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2032395696
- Cited by
- 396
- References
- 27
- FWCI
- 58.50
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.