Semi-stochastic coordinate descent
Open accessThe DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Abstract
We propose a novel stochastic gradient method—semi-stochastic coordinate descent—for the problem of minimizing a strongly convex function represented as the average of a large number of smooth convex functions: . Our method first performs a deterministic step (computation of the gradient of f at the starting point), followed by a large number of stochastic steps. The process is repeated a few times, with the last stochastic iterate becoming the new starting point where the deterministic step is taken. The novelty of our method is in how the stochastic steps are performed. In each such step, we pick a random function and a random coordinate j—both using non-uniform distributions—and update a single coordinate of the decision vector only, based on the computation of the jth partial derivative of at two different points. Each random step of the method constitutes an unbiased estimate of the gradient of f and moreover, the squared norm of the steps goes to zero in expectation, meaning that the stochastic estimate of the gradient progressively improves. The computational complexity of the method is the sum of two terms: evaluations of gradients and evaluations of partial derivatives , where is a novel condition number.
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 Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
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
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 3×
“Also, efficient accelerated variants with O(1/ √ ) rate were developed [2,4], capable of solving problems with 50 billion variables.”
Self-citation
Cited by
Federated Learning: Strategies for Improving Communication Efficiency
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., & Bacon, D. (2016) · arXiv · doi:10.48550/arxiv.1610.05492 · Cited by 3,766
Self-citationFederated Optimization: Distributed Machine Learning for On-Device Intelligence
Konečný, J., McMahan, H. B., Ramage, D., & Richtárik, P. (2016) · arXiv · doi:10.48550/arxiv.1610.02527 · Cited by 1,563
Self-citationFederated Learning over Wireless Networks: Optimization Model Design and Analysis
Tran, N. H., Bao, W., Zomaya, A., Nguyen, M. N. H., & Hong, C. S. (2019) · IEEE INFOCOM 2019 - IEEE Conference on Computer Communications · doi:10.1109/infocom.2019.8737464 · Cited by 1,013
Federated Learning for Internet of Things: Recent Advances, Taxonomy, and Open Challenges
Khan, L. U., Saad, W., Han, Z., Hossain, E., & Hong, C. S. (2021) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2021.3090430 · Cited by 892
Luo, S., Chen, X., Wu, Q., Zhou, Z., & Yu, S. (2020) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2020.3003744 · Cited by 455
Metadata
- Authors
- Konečný, J., Qu, Z., & Richtárik, P.
- Venue
- Optimization Methods and Software
- Publisher
- Informa UK Limited
- Published
- 2017-03-13
- Volume
- 32
- Issue
- 5
- Pages
- 993-1005
- ISSN
- 1026-7670 (ISSN-L)
- 1055-6788
- 1029-4937
- OpenAlex
- W159656292
- Cited by
- 89
- References
- 3
- FWCI
- 3.28
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Semi-stochastic coordinate descent. https://app.cochat.ai/papers/10.1080/10556788.2017.1298596
- The paper
- Konečný, J., Qu, Z., & Richtárik, P. (2017). Semi-stochastic coordinate descent. Optimization Methods and Software. https://doi.org/10.1080/10556788.2017.1298596
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.