Coordinate descent algorithms
The DOI matches its Crossref record; 59 of the 63 references it cites were found in a registry or an index.
Abstract
Coordinate descent algorithms solve optimization problems by successively performing approximate minimization along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This paper describes the fundamentals of the coordinate descent approach, together with variants and extensions and their convergence properties, mostly with reference to convex objectives. We pay particular attention to a certain problem structure that arises frequently in machine learning applications, showing that efficient implementations of accelerated coordinate descent algorithms are possible for problems of this type. We also present some parallel variants and discuss their convergence properties under several models of parallel execution.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“The model parameter partitioned edge learning approach [72] proposed to train only a block of model parameters based on the coordinate decent method for the decomposable ML models [154] or the alternating minimization approach for the general DL models [155].”
From Edge artificial intelligence for 6g: vision, enabling technologies, and applications (2022) · cites this paper as [154]
Citations
Cites
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
Regularization Paths for Generalized Linear Models via Coordinate Descent
Friedman, J., Hastie, T., & Tibshirani, R. (2010) · Journal of Statistical Software · doi:10.18637/jss.v033.i01 · Cited by 19,927
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
Beck, A., & Teboulle, M. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080716542 · Cited by 11,952
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Iterative Solution of Nonlinear Equations in Several Variables
Ortega, J. M., & Rheinboldt, W. C. (2000) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719468 · Cited by 6,860
Sparse inverse covariance estimation with the graphical lasso
Friedman, J., Hastie, T., & Tibshirani, R. (2008) · Biostatistics · doi:10.1093/biostatistics/kxm045 · Cited by 6,355
Advances in kernel methods: support vector learning
Schölkopf, B., Burges, C. J. C., & Smola, A. J. (1999) · doi:10.5555/299094 · Cited by 5,789
Fast Training of Support Vector Machines Using Sequential Minimal Optimization
Platt, J. C. (1998) · Advances in Kernel Methods · doi:10.7551/mitpress/1130.003.0016 · Cited by 5,437
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Iterative Solution of Nonlinear Equations in Several Variables
I., E., Ortega, J. M., & Rheinboldt, W. C. (1971) · Mathematics of Computation · doi:10.2307/2004942 · Cited by 4,408
Introductory Lectures on Convex Optimization: A Basic Course
Nesterov, Y. E. (2014) · Medical Entomology and Zoology · Cited by 3,557
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, B., Fazel, M., & Parrilo, P. A. (2010) · SIAM Review · doi:10.1137/070697835 · Cited by 3,471
Eckstein, J., & Bertsekas, D. P. (1992) · Mathematical Programming · doi:10.1007/bf01581204 · Cited by 2,791
Introductory Lectures on Convex Optimization
Nesterov, Y. (2004) · Applied Optimization · doi:10.1007/978-1-4419-8853-9 · Cited by 2,698
Weik, M. H. (2000) · Computer Science and Communications Dictionary · doi:10.1007/1-4020-0613-6_12436 · Cited by 2,570
Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization
Tseng, P. (2001) · Journal of Optimization Theory and Applications · doi:10.1023/a:1017501703105 · Cited by 1,989
(1989) · Choice Reviews Online · doi:10.5860/choice.26-5109 · Cited by 1,755
Proximal alternating linearized minimization for nonconvex and nonsmooth problems
Bolte, J., Sabach, S., & Teboulle, M. (2014) · Mathematical Programming · doi:10.1007/s10107-013-0701-9 · Cited by 1,688
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization
Razaviyayn, M., Hong, M., & Luo, Z.-Q. (2013) · SIAM Journal on Optimization · doi:10.1137/120891009 · Cited by 1,304
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 1×
“(A similar assumption was used to analyze convergence of as asynchronous stochastic gradient algorithm in [39].”
MethodSelf-citationEfficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
Nesterov, Y. (2012) · SIAM Journal on Optimization · doi:10.1137/100802001 · Cited by 1,187
Attouch, H., Bolte, J., Redont, P., & Soubeyran, A. (2010) · Mathematics of Operations Research · doi:10.1287/moor.1100.0449 · Cited by 1,172
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
A coordinate gradient descent method for nonsmooth separable minimization
Tseng, P., & Yun, S. (2009) · Mathematical Programming · doi:10.1007/s10107-007-0170-0 · Cited by 728
Breheny, P., & Huang, J. (2011) · The Annals of Applied Statistics · doi:10.1214/10-aoas388 · Cited by 671
Richtárik, P., & Takáč, M. (2014) · Mathematical Programming · doi:10.1007/s10107-012-0614-z · Cited by 654
Stochastic dual coordinate ascent methods for regularized lossPreprint
Shalev‐Shwartz, S., & Zhang, T. (2013) · Cited by 637
On the Convergence of Block Coordinate Descent Type Methods
Beck, A., & Tetruashvili, L. (2013) · SIAM Journal on Optimization · doi:10.1137/120887679 · Cited by 572
Cyclic coordinate descent: A robotics algorithm for protein loop closure
Canutescu, A. A., & Dunbrack, R. L. (2003) · Protein Science · doi:10.1110/ps.0242703 · Cited by 521
On the convergence of the coordinate descent method for convex differentiable minimization
Luo, Z. Q., & Tseng, P. (1992) · Journal of Optimization Theory and Applications · doi:10.1007/bf00939948 · Cited by 502
SparseNet: Coordinate Descent With Nonconvex Penalties
Mazumder, R., Friedman, J. H., & Hastie, T. (2011) · Journal of the American Statistical Association · doi:10.1198/jasa.2011.tm09738 · Cited by 449
A unified approach to statistical tomography using coordinate descent optimization
Bouman, C. A., & Sauer, K. (1996) · IEEE Transactions on Image Processing · doi:10.1109/83.491321 · Cited by 442
Error bounds and convergence analysis of feasible descent methods: a general approach
Luo, Z.-Q., & Tseng, P. (1993) · Annals of Operations Research · doi:10.1007/bf02096261 · Cited by 420
Parallel coordinate descent methods for big data optimization
Richtárik, P., & Takáč, M. (2016) · Mathematical Programming · doi:10.1007/s10107-015-0901-6 · Cited by 396
Randomized 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
On search directions for minimization algorithms
Powell, M. J. D. (1973) · Mathematical Programming · doi:10.1007/bf01584660 · Cited by 338
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
Coordinate Descent Method for Large-scale L2-loss Linear Support Vector Machines
Chang, K., Hsieh, C., & Lin, C. (2008) · Journal of Machine Learning Research · doi:10.5555/1390681.1442778 · Cited by 296
Accelerated, Parallel, and Proximal Coordinate Descent
Fercoq, O., & Richtárik, P. (2015) · SIAM Journal on Optimization · doi:10.1137/130949993 · Cited by 265
Stochastic Methods for l 1 -regularized Loss Minimization
Shalev-ShwartzShai, & TewariAmbuj (2011) · Journal of Machine Learning Research · doi:10.5555/1953048.2021059 · Cited by 240
Liu, H., Palatucci, M., & Zhang, J. (2009) · Proceedings of the 26th Annual International Conference on Machine Learning · doi:10.1145/1553374.1553458 · Cited by 216
Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties
Liu, J., & Wright, S. J. (2015) · SIAM Journal on Optimization · doi:10.1137/140961134 · Cited by 212
Self-citationParallel 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
Communication-Efficient Distributed Dual Coordinate Ascent
Jaggi, M., Smith, V., Takáč, M., Terhorst, J., Krishnan, S., Hofmann, T., & Jordan, M. I. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1409.1458 · Cited by 177
Block Coordinate Relaxation Methods for Nonparametric Wavelet Denoising
Sardy, S., Bruce, A. G., & Tseng, P. (2000) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.2000.10474885 · Cited by 171
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems
Lee, Y. T., & Sidford, A. (2013) · 2013 IEEE 54th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.24 · Cited by 167
Stochastic Methods for l 1 -regularized Loss Minimization
Shalev‐Shwartz, S., & Tewari, A. (2011) · Journal of Machine Learning Research · Cited by 129
An accelerated randomized Kaczmarz algorithm
Liu, J., & Wright, S. J. (2015) · Mathematics of Computation · doi:10.1090/mcom/2971 · Cited by 127
Self-citationOptical diffusion tomography by iterative-coordinate-descent optimization in a Bayesian framework
Ye, J. C., Webb, K. J., Bouman, C. A., & Millane, R. P. (1999) · Journal of the Optical Society of America A · doi:10.1364/josaa.16.002400 · Cited by 123
Omidvar, R., & Bidgoli, B. M. (2020) · BENTHAM SCIENCE PUBLISHERS eBooks · doi:10.2174/9789811459597120010004 · Cited by 120
A Coordinate Descent Method for the Bi‐level O–D Matrix Adjustment Problem
Florian, M., & Chen, Y. (1995) · International Transactions in Operational Research · doi:10.1016/0969-6016(95)00001-n · Cited by 105
Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
Pătraşcu, A., & Necoara, I. (2014) · Journal of Global Optimization · doi:10.1007/s10898-014-0151-9 · Cited by 90
Subgradient methods for huge-scale optimization problems
Nesterov, Y. E. (2013) · Mathematical Programming · doi:10.1007/s10107-013-0686-4 · Cited by 88
Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
Mareček, J., Richtárik, P., & Takáč, M. (2015) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-319-17689-5_11 · Cited by 56
Low-rank Matrix Completion using Alternating MinimizationPreprint
Jain, P., Netrapalli, P., & Sanghavi, S. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1212.0467 · Cited by 35
Fast distributed coordinate descent for non-strongly convex losses
Fercoq, O., Qu, Z., Richtarik, P., & Takac, M. (2014) · 2014 IEEE International Workshop on Machine Learning for Signal Processing (MLSP) · doi:10.1109/mlsp.2014.6958862 · Cited by 27 · cited 1×
“This scheme is enhanced with an acceleration step in [15]; the extra computations associated with the acceleration step too are parallelized, using ideas from [23].”
Method
Research works printed but not linked: 5
- Bradley, J.K., Kyrola, A., Bickson, D., Guestrin, C.: Parallel coordunate descent for $$\ell _1$$ ℓ 1 -regularized loss minimization. In: Proceedings of the 28 International Conference on Machine Learning (ICML 2011) (2011)
- Kaczmarz, S.: Angenäherte auflösung von systemen linearer gleichungen. Bulletin International de l’Academie Polonaise des Sciences et des Lettres 35, 355–357 (1937)
- Lin, Q., Lu, Z., Xiao, L.: An accelerated proximal coordinate gradient method and its application to empirical risk minimization. Technical Report, Microsoft Research (2014). arXiv:1407.1296 · arXiv
- Liu, J., Wright, S.J., Ré, C., Bittorf, V., Sridhar, S.: An asynchronous parallel stochastic coordinate descent algorithm. Technical Report, Computer Sciences Department, University of Wisconsin-Madison (2013). (To appear in Journal of Machine Learning Research). arXiv:1311.1873 · arXiv
- Nesterov, Y.: A method for unconstrained convex problem with the rate of convergence $$O(1/k^2)$$ O ( 1 / k 2 ) . Doklady AN SSSR 269, 543–547 (1983)
Cited by
X3D: Expanding Architectures for Efficient Video Recognition
Feichtenhofer, C. (2020) · 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr42600.2020.00028 · Cited by 1,233
A Survey on Distributed Machine Learning
Verbraeken, J., Wolting, M., Katzy, J., Kloppenburg, J., Verbelen, T., & Rellermeyer, J. S. (2021) · ACM Computing Surveys · doi:10.1145/3377454 · Cited by 872
Edge artificial intelligence for 6g: vision, enabling technologies, and applications
Letaief, K. B., Shi, Y., Lu, J., & Lu, J. (2022) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2021.3126076 · Cited by 829
“The model parameter partitioned edge learning approach [72] proposed to train only a block of model parameters based on the coordinate decent method for the decomposable ML models [154] or the alternating minimization approach for the general DL models [155].”
MethodProblem 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
Learning Temporal Information for Brain-Computer Interface Using Convolutional Neural Networks
Sakhavi, S., Guan, C., & Yan, S. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2018.2789927 · Cited by 656
Metadata
- Authors
- Wright, S. J.
- Affiliations
- University of Wisconsin–Madison (US)
- Corresponding author
- Wright, Stephen J.
- ORCID
- Wright, Stephen J.
- Venue
- Mathematical Programming
- Published
- 2015-03-25
- Volume
- 151
- Issue
- 1
- Pages
- 3-34
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2000769684
- Cited by
- 1,438
- References
- 63
- Citations by year
- 2026: 116 · 2025: 130 · 2024: 136 · 2023: 125 · 2022: 141 · 2021: 178 · 2020: 174 · 2019: 156 · 2018: 125 · 2017: 94 · 2016: 50 · 2015: 10
- FWCI
- 91.18
- Type
- journal article
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Mathematical Programming (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Keywords
- coordinate descent, convex optimization, convergence analysis, parallel coordinate descent, machine learning optimization
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.