The DOI matches its Crossref record; 23 of the 23 references it cites were found in a registry or an index.
Accelerated, Parallel, and Proximal Coordinate Descent
Open accessAbstract
We propose a new randomized coordinate descent method for minimizing the sum of convex functions each of which depends on a small number of coordinates only. Our method (APPROX) is simultaneously Accelerated, Parallel, and PROXimal; this is the first time such a method is proposed. In the special case when the number of processors is equal to the number of coordinates, the method converges at the rate $2\bar{\omega}\bar{L} R^2/(k+1)^2 $, where $k$ is the iteration counter, $\bar{\omega}$ is a data-weighted average degree of separability of the loss function, $\bar{L}$ is the average of Lipschitz constants associated with the coordinates and individual functions in the sum, and $R$ is the distance of the initial point from the minimizer. We show that the method can be implemented without the need to perform full-dimensional vector operations, which is the major bottleneck of accelerated coordinate descent. The fact that the method depends on the average degree of separability, and not on the maximum degree, can be attributed to the use of new safe large stepsizes, leading to improved expected separable overapproximation (ESO). These are of independent interest and can be utilized in all existing parallel randomized coordinate descent algorithms based on the concept of ESO. In special cases, our method recovers several classical and recent algorithms such as simple and accelerated proximal gradient descent, as well serial, parallel, and distributed versions of randomized block coordinate descent. Our bounds match or improve on the best known bounds for these methods.
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
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
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
Smooth minimization of non-smooth functions
Nesterov, Y. (2005) · Mathematical Programming · doi:10.1007/s10107-004-0552-5 · Cited by 2,455
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
Nesterov, Y. (2012) · SIAM Journal on Optimization · doi:10.1137/100802001 · Cited by 1,187
Coordinate descent algorithms for lasso penalized regressionPreprint
Wu, T. T., & Lange, K. L. (2008) · Cited by 735
Richtárik, P., & Takáč, M. (2014) · Mathematical Programming · doi:10.1007/s10107-012-0614-z · Cited by 654
Self-citationParallel 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
Self-citationAccelerated proximal stochastic dual coordinate ascent for regularized loss minimization
Shalev-Shwartz, S., & Zhang, T. (2016) · Mathematical Programming · doi:10.1007/s10107-014-0839-0 · Cited by 360
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
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
On the complexity analysis of randomized block-coordinate descent methods
Lu, Z., & Xiao, L. (2015) · Mathematical Programming · doi:10.1007/s10107-014-0800-2 · Cited by 203
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-citationEfficient 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
Lin, Q., Lu, Z., & Xiao, L. (2015) · SIAM Journal on Optimization · doi:10.1137/141000270 · Cited by 135
Mini-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 128
Self-citationOn optimal probabilities in stochastic coordinate descent methods
Richtárik, P., & Takáč, M. (2015) · Optimization Letters · doi:10.1007/s11590-015-0916-1 · Cited by 100
Self-citationProximal Stochastic Dual Coordinate AscentPreprint
Shalev‐Shwartz, S., & Zhang, T. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1211.2717 · Cited by 99
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 99
Necoara, I., & Clipici, D. (2013) · Journal of Process Control · doi:10.1016/j.jprocont.2012.12.012 · Cited by 81
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-citationFast 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
Self-citation
Cited by
Wright, S. J. (2015) · Mathematical Programming · doi:10.1007/s10107-015-0892-3 · Cited by 1,438
An introduction to continuous optimization for imaging
Chambolle, A., & Pock, T. (2016) · Acta Numerica · doi:10.1017/s096249291600009x · Cited by 545
Hong, M., Razaviyayn, M., Luo, Z.-Q., & Pang, J.-S. (2016) · IEEE Signal Processing Magazine · doi:10.1109/msp.2015.2481563 · Cited by 447
Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
Lian, X., Huang, Y., Li, Y., & Liu, J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.08272 · Cited by 324
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
Konecny, J., Liu, J., Richtarik, P., & Takac, M. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2015.2505682 · Cited by 254
Metadata
- Authors
- Fercoq, O., & Richtárik, P.
- Venue
- SIAM Journal on Optimization
- Published
- 2015-01
- Volume
- 25
- Issue
- 4
- Pages
- 1997-2023
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W1947202642
- Cited by
- 265
- References
- 23
- FWCI
- 34.41
- 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.