The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm
Open accessAbstract
We obtain an improved finite-sample guarantee on the linear convergence of stochastic gradient descent for smooth and strongly convex objectives, improving from a quadratic dependence on the conditioning (L/μ)2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(L/\mu )^2$$\end{document} (where L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L$$\end{document} is a bound on the smoothness and μ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu $$\end{document} on the strong convexity) to a linear dependence on L/μ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L/\mu $$\end{document}. Furthermore, we show how reweighting the sampling distribution (i.e. importance sampling) is necessary in order to further improve convergence, and obtain a linear dependence in the average smoothness, dominating previous results. We also discuss importance sampling for SGD more broadly and show how it can improve convergence also in other scenarios. Our results are based on a connection we make between SGD and the randomized Kaczmarz algorithm, which allows us to transfer ideas between the separate bodies of literature studying each of the two methods. In particular, we recast the randomized Kaczmarz algorithm as an instance of SGD, and apply our results to prove its exponential convergence, but to the solution of a weighted least squares problem rather than the original least squares problem. We then present a modified Kaczmarz algorithm with partially biased sampling which does converge to the original least squares solution with the same exponential convergence rate.
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
Large-Scale Machine Learning with Stochastic Gradient Descent
Bottou, L. (2010) · Proceedings of COMPSTAT'2010 · doi:10.1007/978-3-7908-2604-3_16 · Cited by 5,795
Computerized transverse axial scanning (tomography): Part 1. Description of system
Hounsfield, G. N. (1973) · The British Journal of Radiology · doi:10.1259/0007-1285-46-552-1016 · Cited by 3,924
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
Advances in Neural Information Processing Systems 27 (NIPS 2014)
Zhong, M., Goddard, N., & Sutton, C. A. (2014) · Cited by 2,636
The Mathematics of Computerized Tomography
Natterer, F., & Wang, G. (2002) · Medical Physics · doi:10.1118/1.1429631 · Cited by 2,524
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
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
The Tradeoffs of Large-Scale Learning
Bottou, L., & Bousquet, O. (2011) · Optimization for Machine Learning · doi:10.7551/mitpress/8996.003.0015 · Cited by 1,128
The Mathematics of Computerized Tomography
Natterer, F. (2001) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719284 · Cited by 1,047
International Conference on Machine Learning (ICML-99).
Scheffer, T. (1999) · Künstliche Intell. · Cited by 1,003
Minimizing finite sums with the stochastic average gradient
Schmidt, M., Le Roux, N., & Bach, F. (2017) · Mathematical Programming · doi:10.1007/s10107-016-1030-6 · Cited by 922
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
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
Graph Sparsification by Effective Resistances
Spielman, D. A., & Srivastava, N. (2011) · SIAM Journal on Computing · doi:10.1137/080734029 · Cited by 489
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
Bach, F., & Moulines, É. (2011) · Cited by 488
Herman, G. T., & Meyer, L. B. (1993) · IEEE Transactions on Medical Imaging · doi:10.1109/42.241889 · Cited by 486
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
Randomized Algorithms for Matrices and Data
MAHONEY, M. (2012) · Chapman & Hall/CRC Data Mining and Knowledge Discovery Series · doi:10.1201/b11822-37 · Cited by 409
Paved with good intentions: Analysis of a randomized block Kaczmarz method
Needell, D., & Tropp, J. A. (2013) · Linear Algebra and its Applications · doi:10.1016/j.laa.2012.12.022 · Cited by 323
Self-citationAn improved approximation algorithm for the column subset selection problem
Boutsidis, C., Mahoney, M. W., & Petros Drineas, B. (2009) · doi:10.5555/1496770.1496875 · Cited by 286
A Statistical Perspective on Algorithmic LeveragingPreprint
MaPing, MahoneyMichael, W., & Yubin, Y. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.5362 · Cited by 254
SVM optimization: inverse dependence on training set size
Shalev-Shwartz, S., & Srebro, N. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390273 · Cited by 240
Self-citationStable and Robust Sampling Strategies for Compressive Imaging
Krahmer, F., & Ward, R. (2014) · IEEE Transactions on Image Processing · doi:10.1109/tip.2013.2288004 · Cited by 176
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
Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive SamplingPreprint
WangShusen, & ZhangZhihua (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.4207 · Cited by 152
Byrne, C. L. (2007) · A K Peters/CRC Press eBooks · doi:10.1201/9780429295492 · Cited by 131
Acceleration of randomized Kaczmarz method via the Johnson–Lindenstrauss Lemma
Eldar, Y. C., & Needell, D. M. (2011) · Numerical Algorithms · doi:10.1007/s11075-011-9451-z · Cited by 123
Self-citationEFFICIENT METHODS IN CONVEX PROGRAMMING
Nemirovski, A. S. (2007) · Cited by 114
Augmented $\ell_1$ and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
Lai, M., & Yin, W. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/120863290 · Cited by 102
A Statistical Study of On-line Learning
Murata, N. (1999) · Cambridge University Press eBooks · doi:10.1017/cbo9780511569920.005 · Cited by 93
Gradient methods for convex minimization: better rates under weaker conditionsPreprint
Zhang, H., & Yin, W. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1303.4645 · Cited by 91
Stochastic Optimization with Importance SamplingPreprint
Zhao, P., & Zhang, T. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1401.2753 · Cited by 77
Smoothness, Low Noise and Fast RatesPreprint
Srebro, N., Sridharan, K., & Tewari, A. (2010) · arXiv (Cornell University) · Cited by 52
Self-citation
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
Minimizing finite sums with the stochastic average gradient
Schmidt, M., Le Roux, N., & Bach, F. (2017) · Mathematical Programming · doi:10.1007/s10107-016-1030-6 · Cited by 922
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
Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
Shalev-Shwartz, S., Shammah, S., & Shashua, A. (2016) · arXiv · doi:10.48550/arxiv.1610.03295 · Cited by 509
“High variance of the gradient has a detrimental effect on the convergence rate of SGD [22, 29, 16, 28, 24] and given the nature of our problem domain, with extremely low-probability corner cases, the effect of an extremely high variance could bring about bad policy solutions.”
Background
Metadata
- Authors
- Needell, D., Srebro, N., & Ward, R.
- Venue
- Mathematical Programming
- Published
- 2015-02-03
- Volume
- 155
- Issue
- 1-2
- Pages
- 549-573
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2162287622
- Cited by
- 432
- References
- 36
- FWCI
- 38.48
- Type
- journal article
- Language
- en
- Open access
- green
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.