{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T07:02:41Z","timestamp":1781766161720,"version":"3.54.5"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T00:00:00Z","timestamp":1600128000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T00:00:00Z","timestamp":1600128000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005370","name":"Gates Cambridge Trust","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005370","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S026045\/1"],"award-info":[{"award-number":["EP\/S026045\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/N014588\/1"],"award-info":[{"award-number":["EP\/N014588\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/S026045\/1"],"award-info":[{"award-number":["EP\/S026045\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Variance reduction is a crucial tool for improving the slow convergence of stochastic gradient descent. Only a few variance-reduced methods, however, have yet been shown to directly benefit from Nesterov\u2019s acceleration techniques to match the convergence rates of accelerated gradient methods. Such approaches rely on \u201cnegative momentum\u201d, a technique for further variance reduction that is generally specific to the SVRG gradient estimator. In this work, we show for the first time that negative momentum is unnecessary for acceleration and develop a universal acceleration framework that allows all popular variance-reduced methods to achieve accelerated convergence rates. The constants appearing in these rates, including their dependence on the number of functions<jats:italic>n<\/jats:italic>, scale with the mean-squared-error and bias of the gradient estimator. In a series of numerical experiments, we demonstrate that versions of SAGA, SVRG, SARAH, and SARGE using our framework significantly outperform non-accelerated versions and compare favourably with algorithms using negative momentum.<\/jats:p>","DOI":"10.1007\/s10107-020-01566-2","type":"journal-article","created":{"date-parts":[[2020,9,15]],"date-time":"2020-09-15T12:02:39Z","timestamp":1600171359000},"page":"671-715","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Accelerating variance-reduced stochastic gradient methods"],"prefix":"10.1007","volume":"191","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1582-5884","authenticated-orcid":false,"given":"Derek","family":"Driggs","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthias J.","family":"Ehrhardt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carola-Bibiane","family":"Sch\u00f6nlieb","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,9,15]]},"reference":[{"key":"1566_CR1","unstructured":"Allen-Zhu, Z.: Natasha: Faster non-convex stochastic optimization via strongly non-convex parameter. In: ICML (2017)"},{"key":"1566_CR2","first-page":"1","volume":"18","author":"Z Allen-Zhu","year":"2018","unstructured":"Allen-Zhu, Z.: Katyusha: the first direct acceleration of stochastic gradient methods. J. Mach. Learn. Res. 18, 1\u201351 (2018)","journal-title":"J. Mach. Learn. Res."},{"key":"1566_CR3","unstructured":"Allen-Zhu, Z.: Katyusha X: practical momentum method for stochastic sum-of-nonconvex optimization. In: ICML (2018)"},{"key":"1566_CR4","unstructured":"Allen-Zhu, Z.: Natasha 2: Faster non-convex optimization than SGD. In: Advances in Neural Information Processing Systems (2018)"},{"key":"1566_CR5","unstructured":"Allen-Zhu, Z., Hazan, E.: Variance reduction for faster non-convex optimization. In: Proceedings of the 33rd International Conference on Machine Learning, vol.\u00a048 (2016)"},{"key":"1566_CR6","unstructured":"Allen-Zhu, Z., Orecchia, L.: Linear coupling: an ultimate unification of gradient and mirror descent. In: Proceedings of the 8th Innovations in Theoretical Computer Science (ITCS) (2017)"},{"key":"1566_CR7","unstructured":"Allen-Zhu, Z., Yuan, Y.: Improved SVRG for non-strongly-convex or sum-of-non-convex objectives. In: ICML (2018)"},{"issue":"3","key":"1566_CR8","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S1052623403427823","volume":"16","author":"A Auslender","year":"2006","unstructured":"Auslender, A., Teboulle, M.: Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16(3), 697\u2013725 (2006)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1566_CR9","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"1566_CR10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/16M1080173","volume":"60","author":"L Bottou","year":"2018","unstructured":"Bottou, L., Curtis, F.E., Nocedal, J.: Optimization methods for large-scale machine learning. SIAM Rev. 60, 223\u2013311 (2018)","journal-title":"SIAM Rev."},{"issue":"3","key":"1566_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1970392.1970395","volume":"58","author":"EJ Cand\u00e8s","year":"2009","unstructured":"Cand\u00e8s, E.J., Li, X., Ma, Y., Wright, J.: Robust principal component analysis? J. ACM 58(3), 1\u201337 (2009)","journal-title":"J. ACM"},{"key":"1566_CR12","doi-asserted-by":"crossref","unstructured":"Cand\u00e9s, E.J., Recht, B.: Exact matrix completion via convex optimization. In: Foundations of Computational Mathematics, pp. 717\u2013772 (2009)","DOI":"10.1007\/s10208-009-9045-5"},{"issue":"4","key":"1566_CR13","doi-asserted-by":"publisher","first-page":"1168","DOI":"10.1137\/050626090","volume":"4","author":"PL Combettes","year":"2005","unstructured":"Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward\u2013backward splitting. Multiscale Model. Simul. 4(4), 1168\u20131200 (2005)","journal-title":"Multiscale Model. Simul."},{"key":"1566_CR14","unstructured":"Defazio, A.: A simple practical accelerated method for finite sums. In: Advances In Neural Information Processing Systems, pp. 676\u2013684 (2016)"},{"key":"1566_CR15","unstructured":"Defazio, A., Bach, F., Lacoste-Julien, S.: SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives. In: Advances in Neural Information Processing Systems, pp. 1646\u20131654 (2014)"},{"key":"1566_CR16","unstructured":"Driggs, D., Liang, J., Sch\u00f6nlieb, C.B.: A unified analysis of biased stochastic gradient methods and one new one. Technical Report, University of Cambridge (2019)"},{"key":"1566_CR17","unstructured":"Fang, C., Li, C.J., Lin, Z., Zhang, T.: Spider: near-optimal non-convex optimization via stochastic path integrated differential estimator. In: 32nd Conference on Neural Information Processing Systems (2018)"},{"key":"1566_CR18","first-page":"1","volume":"37","author":"R Frostig","year":"2015","unstructured":"Frostig, R., Ge, R., Kakade, S.M., Sidford, A.: Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization. ICML 37, 1\u201328 (2015)","journal-title":"ICML"},{"key":"1566_CR19","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s10107-015-0871-8","volume":"156","author":"S Ghadimi","year":"2016","unstructured":"Ghadimi, S., Lan, G.: Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Math. Program. Ser. A 156, 59\u201399 (2016)","journal-title":"Math. Program. Ser. A"},{"key":"1566_CR20","unstructured":"Hofmann, T., Lucchi, A., Lacoste-Julien, S., McWilliams, B.: Variance reduced stochastic gradient descent with neighbors. In: Advances in Neural Information Processing Systems (2015)"},{"key":"1566_CR21","unstructured":"Johnson, R., Zhang, T.: Accelerating stochastic gradient descent using predictive variance reduction. In: Advances in Neural Information Processing Systems, pp. 315\u2013323 (2013)"},{"key":"1566_CR22","unstructured":"Lan, G., Li, Z., Zhou, Y.: A unified variance-reduced accelerated gradient method for convex optimization. arXiv:1905.12412 (2019)"},{"issue":"1\u20132","key":"1566_CR23","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10107-017-1173-0","volume":"171","author":"G Lan","year":"2018","unstructured":"Lan, G., Zhou, Y.: An optimal randomized incremental gradient method. Math. Program. 171(1\u20132), 167\u2013215 (2018)","journal-title":"Math. Program."},{"key":"1566_CR24","unstructured":"Lin, H., Mairal, J., Harchaoui, Z.: A universal catalyst for first-order optimization. In: Advances in Neural Information Processing Systems (2015)"},{"key":"1566_CR25","doi-asserted-by":"publisher","first-page":"1182","DOI":"10.1002\/mrm.21391","volume":"6","author":"M Lustig","year":"2007","unstructured":"Lustig, M., Donoho, D., Pauly, J.M.: SparseMRI: the application of compressed sensing for rapid MR imaging. Magn. Reson. Med. 6, 1182\u20131195 (2007)","journal-title":"Magn. Reson. Med."},{"key":"1566_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Programming","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Programming. Springer, Berlin (2004)"},{"key":"1566_CR27","unstructured":"Nguyen, L.M., Liu, J., Scheinberg, K., Tak\u00e1\u0109, M.: SARAH: s novel method for machine learning problems using stochastic recursive gradient. In: Proceedings of the 34th International Conference on Machine Learning, vol.\u00a070, pp. 2613\u20132621 (2017)"},{"key":"1566_CR28","unstructured":"Nitanda, A.: Stochastic proximal gradient descent with acceleration techniques. In: Advances in Neural Information Processing Systems, pp. 1574\u20131582 (2014)"},{"issue":"2","key":"1566_CR29","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0022-247X(79)90234-8","volume":"72","author":"GB Passty","year":"1979","unstructured":"Passty, G.B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72(2), 383\u2013390 (1979)","journal-title":"J. Math. Anal. Appl."},{"key":"1566_CR30","unstructured":"Pham, N.H., Nguyen, L.M., Phan, D.T., Tran-Dinh, Q.: ProxSARAH: an efficient algorithmic framework for stochastic composite nonconvex optimization. arXiv:1902.05679 (2019)"},{"key":"1566_CR31","doi-asserted-by":"crossref","unstructured":"Reddi, S.J., Sra, S., P\u00f3cz\u00f3s, B., Smola, A.: Fast stochastic methods for nonsmooth nonconvex optimization. In: ICML (2016)","DOI":"10.1109\/ALLERTON.2016.7852377"},{"issue":"3","key":"1566_CR32","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1214\/aoms\/1177729586","volume":"22","author":"H Robbins","year":"1951","unstructured":"Robbins, H., Monro, S.: A stochastic approximation method. Ann. Math. Stat. 22(3), 400\u2013407 (1951)","journal-title":"Ann. Math. Stat."},{"key":"1566_CR33","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s10107-016-1030-6","volume":"162","author":"M Schmidt","year":"2017","unstructured":"Schmidt, M., Roux, N.L., Bach, F.: Minimizing finite sums with the stochastic average gradient. Math. Program. 162, 83\u2013112 (2017)","journal-title":"Math. Program."},{"key":"1566_CR34","unstructured":"Shang, F., Liu, Y., Cheng, J., Zhuo, J.: Fast stochastic variance reduced gradient method with momentum acceleration for machine learning. In: Proceedings of the 34th International Conference on Machine Learning (ICML) (2017)"},{"key":"1566_CR35","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"R Tibshirani","year":"1996","unstructured":"Tibshirani, R.: Regression shrinkage and variable selection via the lasso. J. R. Stat. Soc. Ser. B 58, 267\u2013288 (1996)","journal-title":"J. R. Stat. Soc. Ser. B"},{"key":"1566_CR36","unstructured":"Wang, Z., Ji, K., Zhou, Y., Liang, Y., Tarokh, V.: SpiderBoost: a class of faster variance-reduced algorithms for nonconvex optimization. arXiv:1810.10690 (2018)"},{"key":"1566_CR37","unstructured":"Woodworth, B., Srebro, N.: Tight complexity bounds for optimizing composite objectives. In: Advances in Neural Information Processing Systems (2016)"},{"issue":"4","key":"1566_CR38","doi-asserted-by":"publisher","first-page":"2057","DOI":"10.1137\/140961791","volume":"24","author":"L Xiao","year":"2014","unstructured":"Xiao, L., Zhang, T.: A proximal stochastic gradient method with progressive variance reduction. SIAM J. Optim. 24(4), 2057\u20132075 (2014)","journal-title":"SIAM J. Optim."},{"key":"1566_CR39","unstructured":"Zhang, Y., Xiao, L.: Stochastic primal-dual coordinate method for regularized empirical risk minimization. In: ICML (2015)"},{"key":"1566_CR40","unstructured":"Zhou, K.: Direct acceleration of saga using sampled negative momentum. arXiv:1806.11048 (2018)"},{"key":"1566_CR41","unstructured":"Zhou, K., Shang, F., Cheng, J.: A simple stochastic variance reduced algorithm with fast convergence rates. In: ICML (2018)"},{"key":"1566_CR42","unstructured":"Zhou, Y., Wang, Z., Ji, K., Liang, Y., Tarokh, V.: Momentum schemes with stochastic variance reduction for nonconvex composite optimization. arXiv:1902.02715 (2019)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01566-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01566-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01566-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,13]],"date-time":"2024-08-13T21:29:31Z","timestamp":1723584571000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01566-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,15]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["1566"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01566-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,15]]},"assertion":[{"value":"8 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}