The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
Open accessAbstract
We propose mS2GD: a method incorporating a mini-batching scheme for improving the theoretical complexity and practical performance of semi-stochastic gradient descent (S2GD). We consider the problem of minimizing a strongly convex function represented as the sum of an average of a large number of smooth convex functions, and a simple nonsmooth convex regularizer. Our method first performs a deterministic step (computation of the gradient of the objective function at the starting point), followed by a large number of stochastic steps. The process is repeated a few times with the last iterate becoming the new starting point. The novelty of our method is in introduction of mini-batching into the computation of stochastic steps. In each step, instead of choosing a single function, we sample$b$functions, compute their gradients, and compute the direction based on this. We analyze the complexity of the method and show that it benefits from two speedup effects. First, we prove that as long as$b$is below a certain threshold, we can reach any predefined accuracy with less overall work than without mini-batching. Second, our mini-batching scheme admits a simple parallel implementation, and hence is suitable for further acceleration by parallelization.
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
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
A Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643
Parikh, N., & Boyd, S. (2014) · Foundations and Trends® in Optimization · doi:10.1561/2400000003 · Cited by 4,102
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
Proximal Splitting Methods in Signal Processing
Combettes, P. L., & Pesquet, J.-C. (2011) · Springer Optimization and Its Applications · doi:10.1007/978-1-4419-9569-8_10 · Cited by 2,183
Robust Stochastic Approximation Approach to Stochastic Programming
Nemirovski, A., Juditsky, A., Lan, G., & Shapiro, A. (2009) · SIAM Journal on Optimization · doi:10.1137/070704277 · Cited by 1,945
Accelerating Stochastic Gradient Descent using Predictive Variance Reduction
Johnson, R., & Zhang, T. (2013) · Cited by 1,889
Pegasos: primal estimated sub-gradient solver for SVM
Shalev-Shwartz, S., Singer, Y., Srebro, N., & Cotter, A. (2011) · Mathematical Programming · doi:10.1007/s10107-010-0420-4 · Cited by 1,477
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
Solving large scale linear prediction problems using stochastic gradient descent algorithms
Zhang, T. (2004) · Twenty-first international conference on Machine learning - ICML '04 · doi:10.1145/1015330.1015332 · Cited by 1,106
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
Gradient methods for minimizing composite objective function
Nesterov, Y. E. (2007) · Cited by 867
Regularization Tools version 4.0 for Matlab 7.3
Hansen, P. C. (2007) · Numerical Algorithms · doi:10.1007/s11075-007-9136-9 · Cited by 787
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
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
Optimal Distributed Online Prediction using Mini-Batches
Dekel, O., Gilad-Bachrach, R., Shamir, O., & Xiao, L. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.1367 · Cited by 512
Fonctions convexes duales et points proximaux dans un espace hilbertien
Moreau, J. J. (1962) · HAL (Le Centre pour la Communication Scientifique Directe) · Cited by 501
A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
Roux, N. L., Schmidt, M., & Bach, F. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.6258 · Cited by 481
Spielman, D. A., & Teng, S. (2014) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090771430 · Cited by 462
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
Needell, D., Srebro, N., & Ward, R. (2016) · Mathematical Programming · doi:10.1007/s10107-015-0864-7 · Cited by 432
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
Accelerated, Parallel, and Proximal Coordinate Descent
Fercoq, O., & Richtárik, P. (2015) · SIAM Journal on Optimization · doi:10.1137/130949993 · Cited by 265
Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods
Ma, A., Needell, D., & Ramdas, A. (2015) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/15m1014425 · Cited by 217
Semi-Stochastic Gradient Descent Methods
Konečný, J., & Richtárik, P. (2017) · Frontiers in Applied Mathematics and Statistics · doi:10.3389/fams.2017.00009 · Cited by 213
Randomized Iterative Methods for Linear Systems
Gower, R. M., & Richtárik, P. (2015) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/15m1025487 · Cited by 209
Sparse Online Learning via Truncated Gradient
Langford, J. C., Li, L., & Zhang, T. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0806.4686 · Cited by 184
Stochastic Quasi-Fejér Block-Coordinate Fixed Point Iterations with Random Sweeping
Combettes, P. L., & Pesquet, J.-C. (2015) · SIAM Journal on Optimization · doi:10.1137/140971233 · Cited by 182
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
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
Better Mini-Batch Algorithms via Accelerated Gradient Methods
Cotter, A., Shamir, O., Srebro, N., & Sridharan, K. (2011) · arXiv · doi:10.48550/arxiv.1106.4574 · Cited by 173
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 148
Coordinate descent with arbitrary sampling I: algorithms and complexity †
Qu, Z., & Richtárik, P. (2016) · Optimization methods & software · doi:10.1080/10556788.2016.1190360 · Cited by 142
Convergence of Stochastic Proximal Gradient Algorithm
Rosasco, L., Villa, S., & Vũ, B. C. (2019) · Applied Mathematics & Optimization · doi:10.1007/s00245-019-09617-7 · Cited by 131
Adding vs. Averaging in Distributed Primal-Dual Optimization
Ma, C., Smith, V., Jaggi, M., Jordan, M. I., Richtárik, P., & Takáč, M. (2015) · Edinburgh Research Explorer (University of Edinburgh) · doi:10.48550/arxiv.1502.03508 · Cited by 131
Accelerated Mini-Batch Stochastic Dual Coordinate AscentPreprint
Shalev‐Shwartz, S., & Zhang, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.2581 · Cited by 108
Necoara, I., & Pătraşcu, A. (2013) · Computational Optimization and Applications · doi:10.1007/s10589-013-9598-8 · Cited by 99
Accelerating Minibatch Stochastic Gradient Descent using Stratified SamplingPreprint
Zhao, P., & Zhang, T. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1405.3080 · Cited by 82
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
Randomized Dual Coordinate Ascent with Arbitrary SamplingPreprint
Qu, Z., Richtárik, P., & Zhang, T. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.5873 · Cited by 49
Convergence analysis for Kaczmarz-type methods in a Hilbert space framework
Oswald, P., & Zhou, W. (2015) · Linear Algebra and its Applications · doi:10.1016/j.laa.2015.03.028 · Cited by 28
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×
“Two classes of methods address this issue – randomized coordinate descent methods [4], [5], [6] , [7], [8], [9], [10], [11], [12], [13] and stochastic gradien t methods [14], [15], [16], [17], [18].”
MethodNecoara, I., & Clipici, D. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.5302 · Cited by 18
Cited by
Federated Learning: A Survey on Enabling Technologies, Protocols, and Applications
Aledhari, M., Razzak, R., Parizi, R. M., & Saeed, F. (2020) · IEEE Access · doi:10.1109/access.2020.3013541 · Cited by 733
Recent Advances in Stochastic Gradient Descent in Deep Learning
Tian, Y., Zhang, Y., & Zhang, H. (2023) · Mathematics · doi:10.3390/math11030682 · Cited by 277
Mahboob, S., & Liu, L. (2024) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2023.3347145 · Cited by 255
Metadata
- Authors
- Konecny, J., Liu, J., Richtarik, P., & Takac, M.
- Venue
- IEEE Journal of Selected Topics in Signal Processing
- Published
- 2016-03
- Volume
- 10
- Issue
- 2
- Pages
- 242-255
- ISSN
- 1932-4553 (ISSN-L)
- 1941-0484
- OpenAlex
- W2103628399
- Cited by
- 254
- References
- 46
- FWCI
- 25.65
- 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.