{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:15:58Z","timestamp":1761293758834,"version":"3.37.3"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,6,5]],"date-time":"2018-06-05T00:00:00Z","timestamp":1528156800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Center for Mathematical Modeling, Universidad de Chile"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s10107-018-1297-x","type":"journal-article","created":{"date-parts":[[2018,6,5]],"date-time":"2018-06-05T02:34:51Z","timestamp":1528166091000},"page":"253-292","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["On variance reduction for stochastic smooth convex optimization with multiplicative noise"],"prefix":"10.1007","volume":"174","author":[{"given":"Alejandro","family":"Jofr\u00e9","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1166-3320","authenticated-orcid":false,"given":"Philip","family":"Thompson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,5]]},"reference":[{"key":"1297_CR1","unstructured":"Allen-Zhu, Z.: Katyusha: the first direct acceleration of stochastic gradient methods (2016). Preprint at arXiv:1603.05953"},{"issue":"5","key":"1297_CR2","doi-asserted-by":"publisher","first-page":"3235","DOI":"10.1109\/TIT.2011.2182178","volume":"58","author":"A Agarwal","year":"2012","unstructured":"Agarwal, A., Barlett, P., Ravikumar, P., Wainwright, M.J.: Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Trans. Inf. Theory 58(5), 3235\u20133249 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1297_CR3","first-page":"1","volume":"18","author":"YF Atchad\u00e9","year":"2017","unstructured":"Atchad\u00e9, Y.F., Fort, G., Moulines, E.: On perturbed proximal gradient algorithms. J. Mach. Learn. Res. 18, 1\u201333 (2017)","journal-title":"J. Mach. Learn. Res."},{"key":"1297_CR4","first-page":"595","volume":"15","author":"F Bach","year":"2014","unstructured":"Bach, F.: Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression. J. Mach. Learn. Res. 15, 595\u2013627 (2014)","journal-title":"J. Mach. Learn. Res."},{"key":"1297_CR5","unstructured":"Bach, F., Moulines, E.: Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In: Conference Paper, Advances in Neural Information Processing Systems (NIPS) (2011)"},{"key":"1297_CR6","unstructured":"Balamurugan, P., Bach, F.: Stochastic variance reduction methods for saddle-point problems. In: Conference Paper, Advances in Neural Information Processing Systems (NIPS) (2016)"},{"issue":"1","key":"1297_CR7","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":"1297_CR8","unstructured":"Bottou, L., Curtis, F.E., Nocedal, J.: Optimization methods for large-scale machine learning (2016). Preprint at arXiv:1606.04838"},{"issue":"1","key":"1297_CR9","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-012-0572-5","volume":"134","author":"RH Byrd","year":"2012","unstructured":"Byrd, R.H., Chin, G.M., Nocedal, J., Wu, Y.: Sample size selection in optimization methods for machine learning. Math. Program. Ser. B 134(1), 127\u2013155 (2012)","journal-title":"Math. Program. Ser. B"},{"key":"1297_CR10","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1214\/aoms\/1177728716","volume":"25","author":"KL Chung","year":"1954","unstructured":"Chung, K.L.: On a stochastic approximation method. Ann. Math. Stat. 25, 463\u2013483 (1954)","journal-title":"Ann. Math. Stat."},{"key":"1297_CR11","first-page":"1646","volume-title":"Advances in Neural Information Processing Systems","author":"A Defazio","year":"2014","unstructured":"Defazio, A., Bach, F., Lacoste-Julien, S.: SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives. In: Ghahramani, Z., Welling, M., Cortes, C., Lawrence, N.D., Weinberger, K.Q. (eds.) Advances in Neural Information Processing Systems, vol. 27, pp. 1646\u20131654. Curran Associates, Inc., Red Hook (2014)"},{"key":"1297_CR12","unstructured":"Dieuleveut, A., Flammarion, N., Bach, F.: Harder, better, faster stronger convergence rates for least-squares regression (2016). Preprint at arXiv:1602.05419"},{"key":"1297_CR13","first-page":"2899","volume":"10","author":"J Duchi","year":"2009","unstructured":"Duchi, J., Singer, Y.: Efficient online and batch learning using forward backward splitting. J. Mach. Learn. Res. 10, 2899\u20132934 (2009)","journal-title":"J. Mach. Learn. Res."},{"key":"1297_CR14","doi-asserted-by":"crossref","unstructured":"Dvoretzky, A.: On stochastic approximation. In: Proceedings of the Third Berkeley Symposium on Mathematical Statistics and Probability, Vol. 1, pp. 39\u201355. University of California Press (1956)","DOI":"10.1525\/9780520313880-007"},{"key":"1297_CR15","unstructured":"Flammarion, N., Bach, F.: Stochastic composite least-squares regression with convergence rate $$O(1\/n)$$ O ( 1 \/ n ) (2017). Preprint at arXiv:1702.06429"},{"issue":"3","key":"1297_CR16","doi-asserted-by":"publisher","first-page":"1380","DOI":"10.1137\/110830629","volume":"34","author":"M Friedlander","year":"2012","unstructured":"Friedlander, M., Schmidt, M.: Hybrid deterministic-stochastic methods for data fitting. SIAM J. Sci. Comput. 34(3), 1380\u20131405 (2012)","journal-title":"SIAM J. Sci. Comput."},{"key":"1297_CR17","unstructured":"Frostig, R., Ge, R., Kakade, S.M., Sidford, A.: Competing with the empirical risk minimizer in a single pass. In: COLT 2015 Proceedings (2015)"},{"volume-title":"Handbook of Simulation Optimization","year":"2015","key":"1297_CR18","unstructured":"Fu, M.C. (ed.): Handbook of Simulation Optimization. Springer, New York (2015)"},{"key":"1297_CR19","unstructured":"Gadat, S., Panloup, F.: Optimal non-asymptotic bound of the Ruppert\u2013Polyak averaging without strong convexity (2017). Preprint at arXiv:1709.03342"},{"issue":"4","key":"1297_CR20","doi-asserted-by":"publisher","first-page":"1469","DOI":"10.1137\/110848864","volume":"22","author":"S Ghadimi","year":"2012","unstructured":"Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, I: a generic algorithmic framework. SIAM J. Optim. 22(4), 1469\u20131492 (2012)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1297_CR21","doi-asserted-by":"publisher","first-page":"2061","DOI":"10.1137\/110848876","volume":"23","author":"S Ghadimi","year":"2013","unstructured":"Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, II: shrinking procedures and optimal algorithms. SIAM J. Optim. 23(4), 2061\u20132089 (2013)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1297_CR22","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(1), 59\u201399 (2016)","journal-title":"Math. Program. Ser. A"},{"key":"1297_CR23","unstructured":"G\u00fcrb\u00fczbalaban, M., Ozdaglar, A., Parrilo, P.: Convergence rate of incremental aggregated gradient algorithms. SIAM J. Optim. Preprint at arXiv:1506.02081"},{"key":"1297_CR24","first-page":"2489","volume":"15","author":"E Hazan","year":"2014","unstructured":"Hazan, E., Kale, S.: Beyond the regret minimization barrier optimal algorithms for stochastic strongly-convex optimization. J. Mach. Learn. Res. 15, 2489\u20132512 (2014)","journal-title":"J. Mach. Learn. Res."},{"key":"1297_CR25","unstructured":"Hu, C., Kwok, J.T., Pan, W.: Accelerated gradient methods for stochastic optimization and online learning. In: Advances in Neural Information Processing Systems (NIPS) (2009)"},{"key":"1297_CR26","unstructured":"Iusem, A., Jofr\u00e9, A., Thompson, P.: Incremental constraint projection methods for monotone stochastic variational inequalities. Math. Oper. Res. Preprint at arXiv:1703.00272"},{"issue":"2","key":"1297_CR27","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1137\/15M1031953","volume":"27","author":"A Iusem","year":"2017","unstructured":"Iusem, A., Jofr\u00e9, A., Oliveira, R.I., Thompson, P.: Extragradient methods with variance reduction for stochastic variational inequalities. SIAM J. Optim. 27(2), 686\u2013724 (2017)","journal-title":"SIAM J. Optim."},{"key":"1297_CR28","unstructured":"Iusem, A., Jofr\u00e9, A., Oliveira, R.I., Thompson, P.: Variance-based stochastic extragradient methods with line search for stochastic variational inequalities (2016). Preprint at arXiv:1703.00262"},{"key":"1297_CR29","unstructured":"Jain, P., Kakade, S.M., Kidambi, R., Netrapalli, P., Sidford, A.: Parallelizing stochastic approximation through mini-batching and tail-averaging (2016). Preprint at arXiv:1610.03774"},{"key":"1297_CR30","unstructured":"Jain, P., Kakade, S.M., Kidambi, R., Netrapalli, P., Sidford, A.: Accelerating stochastic gradient descent (2017). Preprint at arXiv:1704.08227"},{"issue":"6","key":"1297_CR31","doi-asserted-by":"publisher","first-page":"1462","DOI":"10.1109\/TAC.2008.925853","volume":"53","author":"H Jiang","year":"2008","unstructured":"Jiang, H., Xu, H.: Stochastic approximation approaches to the stochastic variational inequality problem. IEEE Trans. Autom. Control 53(6), 1462\u20131475 (2008)","journal-title":"IEEE Trans. Autom. Control"},{"key":"1297_CR32","unstructured":"Johnson, R., Zhang, T.: Accelerating stochastic gradient descent using predictive variance reduction. In: Advances in Neural Information Processing Systems (NIPS) (2013)"},{"issue":"4","key":"1297_CR33","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/s11122-006-0005-2","volume":"41","author":"AB Juditsky","year":"2005","unstructured":"Juditsky, A.B., Nazin, A.V., Tsybakov, A.B., Vayatis, N.: Recursive aggregation of estimators via the mirror descent algorithm with averaging. Probl. Inf. Transm. 41(4), 368\u2013384 (2005)","journal-title":"Probl. Inf. Transm."},{"issue":"1","key":"1297_CR34","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/10-SSY011","volume":"1","author":"A Juditsky","year":"2011","unstructured":"Juditsky, A., Nemirovski, A., Tauvel, C.: Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1(1), 17\u201358 (2011)","journal-title":"Stoch. Syst."},{"issue":"5","key":"1297_CR35","doi-asserted-by":"publisher","first-page":"2183","DOI":"10.1214\/07-AOS546","volume":"36","author":"A Juditsky","year":"2008","unstructured":"Juditsky, A., Rigollet, P., Tsybakov, A.B.: Learning by mirror averaging. Ann. Stat. 36(5), 2183\u20132206 (2008)","journal-title":"Ann. Stat."},{"issue":"1","key":"1297_CR36","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10107-010-0434-y","volume":"133","author":"G Lan","year":"2012","unstructured":"Lan, G.: An optimal method for stochastic composite optimization. Math. Program. Ser. A 133(1), 365\u2013397 (2012)","journal-title":"Math. Program. Ser. A"},{"key":"1297_CR37","unstructured":"Le Roux, N., Schmidt, M., Bach, F.R.: A stochastic gradient method with an exponential convergence rate for finite training sets. In: Advances in Neural Information Processing Systems 25 (NIPS) (2012)"},{"key":"1297_CR38","first-page":"1705","volume":"13","author":"S Lee","year":"2012","unstructured":"Lee, S., Wright, S.: Manifold identification in dual averaging for regularized stochastic online learning. J. Mach. Learn. Res. 13, 1705\u20131744 (2012)","journal-title":"J. Mach. Learn. Res."},{"key":"1297_CR39","unstructured":"Lin, H., Mairal, J., Harchaoui, Z.: A universal catalyst for first-order optimization. In: Advances in Neural Information Processing Systems (NIPS) (2015)"},{"issue":"2","key":"1297_CR40","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1007\/s10589-013-9633-9","volume":"58","author":"Q Lin","year":"2014","unstructured":"Lin, Q., Chen, X., Pe\u00f1a, J.: A sparsity preserving stochastic gradient methods for sparse regression. Comput. Optim. Appl. 58(2), 455\u2013482 (2014)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"1297_CR41","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/s10107-015-0864-7","volume":"155","author":"D Needell","year":"2016","unstructured":"Needell, D., Srebro, N., Ward, R.: Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Math. Program. Ser. A 155(1), 549\u2013573 (2016)","journal-title":"Math. Program. Ser. A"},{"issue":"4","key":"1297_CR42","doi-asserted-by":"publisher","first-page":"1574","DOI":"10.1137\/070704277","volume":"19","author":"A Nemirovski","year":"2009","unstructured":"Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4), 1574\u20131609 (2009)","journal-title":"SIAM J. Optim."},{"key":"1297_CR43","unstructured":"Nemirovskii, A., Yudin, D.: On Cezari\u2019s convergence of the steepest descent method for approximating saddle point of convex-concave functions. (in Russian)\u2014Doklady Akademii Nauk SSSR, 239, 5 (1978) (English translation: Soviet Math. Dokl. 19, 2 (1978))"},{"key":"1297_CR44","volume-title":"Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics","author":"AS Nemirovski","year":"1983","unstructured":"Nemirovski, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics. Wiley, New York (1983)"},{"key":"1297_CR45","first-page":"372","volume":"27","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence $$O(1\/k^2)$$ O ( 1 \/ k 2 ) . Soviet Math. Doklady 27, 372\u2013376 (1983)","journal-title":"Soviet Math. Doklady"},{"key":"1297_CR46","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Cambridge (2004)"},{"issue":"1","key":"1297_CR47","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10107-012-0629-5","volume":"140","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Gradient methods for minimizing composite objective function. Math. Program. Ser. B 140(1), 125\u2013161 (2013)","journal-title":"Math. Program. Ser. B"},{"issue":"1","key":"1297_CR48","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s10107-007-0149-x","volume":"120","author":"Y Nesterov","year":"2009","unstructured":"Nesterov, Y.: Primal-dual subgradient methods for convex problems. Math. Program. Ser. B 120(1), 221\u2013259 (2009)","journal-title":"Math. Program. Ser. B"},{"issue":"6","key":"1297_CR49","doi-asserted-by":"publisher","first-page":"1559","DOI":"10.1016\/j.automatica.2008.01.017","volume":"44","author":"YV Nesterov","year":"2008","unstructured":"Nesterov, Y.V.: Confidence level solutions for stochastic programming. Automatica 44(6), 1559\u20131568 (2008)","journal-title":"Automatica"},{"key":"1297_CR50","first-page":"937","volume":"51","author":"BT Polyak","year":"1991","unstructured":"Polyak, B.T.: New method of stochastic approximation type. Autom. Remote Control 51, 937\u2013946 (1991)","journal-title":"Autom. Remote Control"},{"key":"1297_CR51","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0330046","volume":"30","author":"BT Polyak","year":"1992","unstructured":"Polyak, B.T., Juditsky, A.B.: Acceleration of stochastic approximation by averaging. SIAM J. Control Optim. 30, 838\u2013855 (1992)","journal-title":"SIAM J. Control Optim."},{"key":"1297_CR52","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, 400\u2013407 (1951)","journal-title":"Ann. Math. Stat."},{"key":"1297_CR53","unstructured":"Rosasco, L., Villa, S., V\u0169, B.C.: Convergence of a stochastic proximal gradient algorithm (2014). Preprint at arXiv:1403.5074"},{"key":"1297_CR54","unstructured":"Ruppert, D.: Efficient estimations from a slowly convergent Robbins\u2013Monro process. Technical report, Cornell University Operations Research and Industrial Engineering (1988). Preprint at https:\/\/ecommons.cornell.edu\/handle\/1813\/8664"},{"issue":"1","key":"1297_CR55","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s10107-016-1030-6","volume":"162","author":"M Schmidt","year":"2017","unstructured":"Schmidt, M., Le Roux, N., Bach, F.: Minimizing finite sums with the stochastic average gradient. Math. Program. Ser. A 162(1), 83\u2013112 (2017)","journal-title":"Math. Program. Ser. A"},{"key":"1297_CR56","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718751","volume-title":"Lectures on Stochastic Programming: Modeling and Theory. MOS-SIAM Series on Optimization","author":"A Shapiro","year":"2009","unstructured":"Shapiro, A., Dentcheva, D., Ruszczy\u0144ski, A.: Lectures on Stochastic Programming: Modeling and Theory. MOS-SIAM Series on Optimization. SIAM, Philadelphia (2009)"},{"volume-title":"Optimization for Machine Learning","year":"2012","key":"1297_CR57","unstructured":"Sra, S., Nowozin, S., Wright, S.J. (eds.): Optimization for Machine Learning. The MIT Press, Cambridge, MA (2012)"},{"key":"1297_CR58","volume-title":"On Accelerated Proximal Gradient Methods for Convex\u2013Concave Optimization","author":"P Tseng","year":"2008","unstructured":"Tseng, P.: On Accelerated Proximal Gradient Methods for Convex\u2013Concave Optimization. University of Washington, Seattle (2008)"},{"key":"1297_CR59","first-page":"2543","volume":"9","author":"L Xiao","year":"2010","unstructured":"Xiao, L.: Dual averaging methods for regularized stochastic learning and online optimization. J. Mach. Learn. Res. 9, 2543\u20132596 (2010)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"1297_CR60","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":"1297_CR61","unstructured":"Woodworth, B.E., Srebro, N.: Tight complexity bounds for optimizing composite objectives. In: Advances in Neural Information Processing Systems 29 (NIPS) (2016)"},{"key":"1297_CR62","unstructured":"Zhang, L., Yang, T., Jin, R., He, X.: $$O(log T)$$ O ( l o g T ) projections for stochastic optimization of smooth and strongly convex functions. In: Proceedings of the International Conference on International Conference on Machine Learning (ICML), Vol. 28 (2013)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1297-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-018-1297-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1297-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T00:57:26Z","timestamp":1661389046000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-018-1297-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,5]]},"references-count":62,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["1297"],"URL":"https:\/\/doi.org\/10.1007\/s10107-018-1297-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2018,6,5]]},"assertion":[{"value":"24 May 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}