Stochastic Variance Reduction for Nonconvex Optimization
Open accessThe DOI matches its OpenAlex record; 27 of the 27 references it cites were found in a registry or an index.
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
(2010) · Cited by 14,134
A Stochastic Approximation Method
Robbins, H., & Monro, S. (1951) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729586 · Cited by 9,643 · cited 3×
“Two fundamental models in machine learning that profit from IFO algorithms are (i) empirical risk minimization, which typically uses convex finite-sum models; and (ii) deep learning, which uses nonconvex ones.”
BackgroundMethodParikh, 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
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
Analysis of recursive stochastic algorithms
Ljung, L. (1977) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1977.1101561 · Cited by 1,467
Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
Ghadimi, S., & Lan, G. (2013) · SIAM Journal on Optimization · doi:10.1137/120880811 · Cited by 1,034 · cited 4×
“While the quantities (cid:107)∇ f ( x ) 2 and f ( x ) − f ( x ∗ ) or (cid:107) x − x ∗ (cid:107) 2 are not comparable in general (see (Ghadimi & Lan, 2013)), they are typically assumed to be of similar magnitude.”
BackgroundMethodInfluentialMinimizing 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 · cited 6×
“Among these, of particular importance are variance reduced (VR) stochastic meth-ods (Schmidt et al., 2013; Johnson & Zhang, 2013; Defazio et al., 2014a), which have delivered exciting progress such as linear convergence rates (for strongly convex functions) as opposed to sub-linear rates of…”
BackgroundMethodInfluentialSAGA: 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 · cited 4×
“Two fundamental models in machine learning that profit from IFO algorithms are (i) empirical risk minimization, which typically uses convex finite-sum models; and (ii) deep learning, which uses nonconvex ones.”
BackgroundMethodInfluentialStochastic Gradient Learning in Neural Networks
Bottou, L. (1991) · Cited by 817
Cubic regularization of Newton method and its global performance
Nesterov, Y., & Polyak, B. T. (2006) · Mathematical Programming · doi:10.1007/s10107-006-0706-8 · Cited by 781 · cited 1×
“We use Svrg (Johnson & Zhang, 2013), an algorithm recently shown to be very effective for reducing variance in convex problems.”
MethodEfficient mini-batch training for stochastic optimization
Li, M., Zhang, T., Chen, Y., & Smola, A. J. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623612 · Cited by 742 · cited 1×
“In contrast, Sgd does not yield an efficient mini-batch strategy as it requires O ( b 1 / 2 / 2 ) IFO calls for achieving an (cid:15) -accurate solution (Li et al., 2014).”
BackgroundSelf-citationStochastic 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 · cited 4×
“Algorithm 2 attains linear convergence for strongly convex f (Johnson & Zhang, 2013); for non-strongly convex functions, rates faster than Sgd can be shown by using an indirect perturbation argument—see e.g., (Koneˇcn´y & Richt´arik, 2013; Xiao & Zhang, 2014).”
BackgroundMethodInfluentialOptimal 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 · cited 2×
“√ For a batch size of b , Sgd obtains a rate of O (1 / bT ) (Dekel et al., 2012) (obtainable by a simple modification of Theorem 1).”
MethodIncremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey
Bertsekas, D. P. (2011) · Optimization for Machine Learning · doi:10.7551/mitpress/8996.003.0006 · Cited by 381
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 · cited 2×
“A similar rate for parallel and distributed SGD was shown recently in (Lian et al., 2015).”
BackgroundMini-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
An optimal randomized incremental gradient method
Lan, G., & Zhou, Y. (2017) · Mathematical Programming · doi:10.1007/s10107-017-1173-0 · Cited by 214 · cited 1×
“Agarwal & Bottou (2014); Lan & Zhou (2015) study lower-bounds for convex finite-sum problems.”
BackgroundPerturbed Iterate Analysis for Asynchronous Stochastic Optimization
Mania, H., Pan, X., Papailiopoulos, D., Recht, B., Ramchandran, K., & Jordan, M. I. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1057000 · Cited by 154 · cited 1×
“Asynchronous VR frameworks are developed in (Reddi et al., 2015; Mania et al., 2015).”
Finito: A Faster, Permutable Incremental Gradient Method for Big Data ProblemsPreprint
Defazio, A., Caetano, T. S., & Domke, J. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.2710 · Cited by 126 · cited 3×
“The Svrg algorithm of (Johnson & Zhang, 2013) is particularly attractive here because of its low storage requirement in comparison to the algorithms in (Schmidt et al., 2013; Defazio et al., 2014a).”
BackgroundMethodBeyond Convexity: Stochastic Quasi-Convex OptimizationPreprint
Hazan, E., Levy, K. Y., & Shalev‐Shwartz, S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1507.02030 · Cited by 114 · cited 2×
“Finally, we note another interesting example, stochastic optimization of locally quasi-convex functions (Hazan et al., 2015), wherein actually a O (1 / 2 ) convergence in function value is shown.”
BackgroundOn Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants
Reddi, S. J., Hefny, A., Sra, S., Póczos, B., & Smola, A. J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.06840 · Cited by 99
Self-citationSDCA without DualityPreprint
Shalev‐Shwartz, S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.06177 · Cited by 36 · cited 3×
“dca in the setting of Corollary 6 when the condition number is reasonably large { a case that typically arises in machine 7 learning. More precisely, for l 2-regularized empirical loss minimization, Shalev-Shwartz (2015) show that Sdca requires O((n+ 2)log(1=) iterations when the f i’s are possibly nonconvex but their…”
BackgroundInfluentialHong, M. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.6058 · Cited by 28 · cited 1×
“Hong (2014) studies a distributed nonconvex incremental ADMM algorithm.”
BackgroundUniVR: A Universal Variance Reduction Framework for Proximal Stochastic Gradient Method.Preprint
Allen-Zhu, Z., & Yang, Y. (2015) · arXiv (Cornell University) · Cited by 5
Cited by
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., & Suresh, A. T. (2019) · arXiv · doi:10.48550/arxiv.1910.06378 · Cited by 1,734
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
Adaptive Federated Optimization
Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečný, J., Kumar, S., & McMahan, H. B. (2020) · arXiv · doi:10.48550/arxiv.2003.00295 · Cited by 840
“Assumptions 1 and 3 are fairly standard in nonconvex optimization literature (Reddi et al., 2016; Ward et al., 2018; Zaheer et al., 2018).”
BackgroundSelf-citationLinear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
Karimi, H., Nutini, J., & Schmidt, M. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-46128-1_50 · Cited by 824
A Survey of Optimization Methods From a Machine Learning Perspective
Sun, S., Cao, Z., Zhu, H., & Zhao, J. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2950779 · Cited by 789
Metadata
- Authors
- Reddi, S. J., Hefny, A., Sra, S., Póczos, B., & Smola, A. J.
- Venue
- arXiv (Cornell University)
- Publisher
- Cornell University
- Published
- 2016-03-19
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1603.06160
- OpenAlex
- W2304667012
- Cited by
- 215
- References
- 27
- Type
- posted content
- 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.