Semi-Stochastic Gradient Descent Methods
Open accessThe DOI matches its Crossref record.
Abstract
In this paper we study the problem of minimizing the average of a large number of smooth convex loss functions. We propose a new method, S2GD (Semi-Stochastic Gradient Descent), which runs for one or several epochs in each of which a single full gradient and a random number of stochastic gradients is computed, following a geometric law. For strongly convex objectives, the method converges linearly. The total work needed for the method to output an epsilon-accurate solution in expectation, measured in the number of passes over data, is proportional to the condition number of the problem and inversely proportional to the number of functions forming the average. This is achieved by running the method with number of stochastic gradient evaluations per epoch proportional to conditioning of the problem. The SVRG method of Johnson and Zhang arises as a special case. To illustrate our theoretical results, S2GD only needs the workload equivalent to about 2.1 full gradient evaluations to find a 10e-6 accurate solution for a problem with 10e9 functions and a condition number of 10e3.
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
Cited by
Federated 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-citationSAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
Defazio, A., Bach, F., & Lacoste-Julien, S. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.0202 · Cited by 834
A Survey on Federated Learning for Resource-Constrained IoT Devices
Imteaj, A., Thakker, U., Wang, S., Li, J., & Amini, M. H. (2022) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3095077 · Cited by 774
“There have been various methods to deal with distributed online optimization and distributed learning, including stochastic variance reduced gradient (SVRG) [87], [88], DANE [84] that is particularly for distributed optimization, naive Federated SVRG, and Federated SVRG ( FSVRG ) .”
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
A Proximal Stochastic Gradient Method with Progressive Variance Reduction
Xiao, L., & Zhang, T. (2014) · SIAM Journal on Optimization · doi:10.1137/140961791 · Cited by 592
Federated Optimization:Distributed Optimization Beyond the Datacenter
Konečný, J., McMahan, B., & Ramage, D. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.03575 · Cited by 544
Self-citationPrivacy preservation in federated learning: An insightful survey from the GDPR perspective
Truong, N., Sun, K., Wang, S., Guitton, F., & Guo, Y. (2021) · Computers & Security · doi:10.1016/j.cose.2021.102402 · Cited by 399
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
Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
Zhang, H., Reddi, S. J., & Sra, S. (2016) · arXiv · doi:10.48550/arxiv.1605.07147 · Cited by 140
“The linear space version of (1) where M = R d has been the subject of intense algorithmic development in machine learning and optimization, starting with the classical work of Robbins and Monro [22] to the recent spate of work on variance reduction methods [7; 14; 16; 21; 24].”
BackgroundMethodZhou, Z., Yang, S., Pu, L., & Yu, S. (2020) · IEEE Internet of Things Journal · doi:10.1109/jiot.2020.2984332 · Cited by 77
“For the local iterations in each global iteration, to achieve a local model accuracy of θ(t), the number of local iterations is upper bounded by O(log(1/θ(t))) for a wide range of iterative algorithms to solve problem (2), such as gradient descent, coordinate descent, or stochastic dual coordinate descent [24].”
Background
Metadata
- Authors
- Konečný, J., & Richtárik, P.
- Venue
- Frontiers in Applied Mathematics and Statistics
- Publisher
- Frontiers Media SA
- Published
- 2017-05-23
- Volume
- 3
- ISSN
- 2297-4687 (ISSN-L)
- OpenAlex
- W1523661875
- Cited by
- 132
- References
- 0
- FWCI
- 7.87
- Type
- journal article
- Language
- en
- Open access
- gold
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.