{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T12:46:27Z","timestamp":1760013987172,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T00:00:00Z","timestamp":1722556800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T00:00:00Z","timestamp":1722556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010665","name":"H2020 Marie Sklodowska-Curie Actions","doi-asserted-by":"publisher","award":["861137"],"award-info":[{"award-number":["861137"]}],"id":[{"id":"10.13039\/100010665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004702","name":"Universit\u00e0 degli Studi di Genova","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004702","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the context of finite sums minimization, variance reduction techniques are widely used to improve the performance of state-of-the-art stochastic gradient methods. Their practical impact is clear, as well as their theoretical properties. Stochastic proximal point algorithms have been studied as an alternative to stochastic gradient algorithms since they are more stable with respect to the choice of the step size. However, their variance-reduced versions are not as well studied as the gradient ones. In this work, we propose the first unified study of variance reduction techniques for stochastic proximal point algorithms. We introduce a generic stochastic proximal-based algorithm that can be specified to give the proximal version of SVRG, SAGA, and some of their variants. For this algorithm, in the smooth setting, we provide several convergence rates for the iterates and the objective function values, which are faster than those of the vanilla stochastic proximal point algorithm. More specifically, for convex functions, we prove a sublinear convergence rate of <jats:italic>O<\/jats:italic>(1\/<jats:italic>k<\/jats:italic>). In addition, under the Polyak-\u0142ojasiewicz condition, we obtain linear convergence rates. Finally, our numerical experiments demonstrate the advantages of the proximal variance reduction methods over their gradient counterparts in terms of the stability with respect to the choice of the step size in most cases, especially for difficult problems.<\/jats:p>","DOI":"10.1007\/s10957-024-02502-6","type":"journal-article","created":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T13:12:43Z","timestamp":1722604363000},"page":"1910-1939","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Variance Reduction Techniques for Stochastic Proximal Point Algorithms"],"prefix":"10.1007","volume":"203","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3114-4835","authenticated-orcid":false,"given":"Cheik","family":"Traor\u00e9","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vassilis","family":"Apidopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saverio","family":"Salzo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Silvia","family":"Villa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,2]]},"reference":[{"key":"2502_CR1","unstructured":"Allen-Zhu, Z., Yuan, Y.: Improved SVRG for non-strongly-convex or sum-of-non-convex objectives. In: Balcan, M. F., Weinberger K. Q. (eds) Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, New York, USA, 20\u201322 Jun 2016, pp. 1080\u20131089. PMLR"},{"issue":"3","key":"2502_CR2","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s10898-022-01164-w","volume":"84","author":"V Apidopoulos","year":"2022","unstructured":"Apidopoulos, V., Ginatta, N., Villa, S.: Convergence rates for the heavy-ball continuous dynamics for non-convex optimization, under Polyak-\u0141ojasiewicz condition. J. Glob. Optim. 84(3), 563\u2013589 (2022)","journal-title":"J. Glob. Optim."},{"issue":"3","key":"2502_CR3","doi-asserted-by":"publisher","first-page":"2257","DOI":"10.1137\/18M1230323","volume":"29","author":"H Asi","year":"2019","unstructured":"Asi, H., Duchi, J.C.: Stochastic (approximate) proximal point methods: convergence, optimality, and adaptivity. SIAM J. Optim. 29(3), 2257\u20132290 (2019)","journal-title":"SIAM J. Optim."},{"key":"2502_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48311-5","volume-title":"Convex Analysis and Monotone Operator Theory in Hilbert Spaces","author":"HH Bauschke","year":"2017","unstructured":"Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2017)"},{"issue":"7","key":"2502_CR5","doi-asserted-by":"publisher","first-page":"3115","DOI":"10.1016\/j.jde.2015.04.016","volume":"259","author":"P B\u00e9gout","year":"2015","unstructured":"B\u00e9gout, P., Bolte, J., Jendoubi, M.A.: On damped second-order gradient systems. J. Differ. Equ. 259(7), 3115\u20133143 (2015)","journal-title":"J. Differ. Equ."},{"issue":"2","key":"2502_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s10107-011-0472-0","volume":"129","author":"DP Bertsekas","year":"2011","unstructured":"Bertsekas, D.P.: Incremental proximal methods for large scale convex optimization. Math. Program. 129(2), 163\u2013195 (2011)","journal-title":"Math. Program."},{"issue":"4","key":"2502_CR7","doi-asserted-by":"publisher","first-page":"2235","DOI":"10.1137\/15M1017909","volume":"26","author":"P Bianchi","year":"2016","unstructured":"Bianchi, P.: Ergodic convergence of a stochastic proximal point algorithm. SIAM J. Optim. 26(4), 2235\u20132260 (2016)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"2502_CR8","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1137\/050644641","volume":"17","author":"J Bolte","year":"2007","unstructured":"Bolte, J., Daniilidis, A., Lewis, A.: The \u0141ojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205\u20131223 (2007)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2502_CR9","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s10107-016-1091-6","volume":"165","author":"J Bolte","year":"2017","unstructured":"Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.W.: From error bounds to the complexity of first-order descent methods for convex functions. Math. Program. 165(2), 471\u2013507 (2017)","journal-title":"Math. Program."},{"key":"2502_CR10","doi-asserted-by":"crossref","unstructured":"Bottou, L.: On-line Learning and Stochastic Approximations, pp. 9\u201342. Publications of the Newton Institute, Cambridge University Press, Cambridge (1999)","DOI":"10.1017\/CBO9780511569920.003"},{"key":"2502_CR11","doi-asserted-by":"crossref","unstructured":"Bottou, L.: Large-scale machine learning with stochastic gradient descent. In: Lechevallier, Y., Saporta, G. (eds) Proceedings of COMPSTAT\u20192010, pp. 177\u2013186, Heidelberg, 2010. Physica-Verlag HD","DOI":"10.1007\/978-3-7908-2604-3_16"},{"key":"2502_CR12","unstructured":"Chierchia, G., Chouzenoux, E., Combettes, P.L., Pesquet, J.-C.: The proximity operator repository. User\u2019s guide (2020). http:\/\/proximity-operator.net\/download\/guide.pdf"},{"key":"2502_CR13","volume-title":"Advances in Neural Information Processing Systems","author":"A Defazio","year":"2016","unstructured":"Defazio, A.: A simple practical accelerated method for finite sums. In: Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 29. Curran Associates Inc, Red Hook (2016)"},{"key":"2502_CR14","first-page":"1646","volume":"27","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. Adv. Neural. Inf. Process. Syst. 27, 1646\u20131654 (2014)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"issue":"3","key":"2502_CR15","doi-asserted-by":"publisher","first-page":"919","DOI":"10.1287\/moor.2017.0889","volume":"43","author":"D Drusvyatskiy","year":"2018","unstructured":"Drusvyatskiy, D., Lewis, A.S.: Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. 43(3), 919\u2013948 (2018)","journal-title":"Math. Oper. Res."},{"issue":"61","key":"2502_CR16","first-page":"2121","volume":"12","author":"J Duchi","year":"2011","unstructured":"Duchi, J., Hazan, E., Singer, Y.: Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res. 12(61), 2121\u20132159 (2011)","journal-title":"J. Mach. Learn. Res."},{"key":"2502_CR17","first-page":"689","volume-title":"Advances in Neural Information Processing Systems","author":"C Fang","year":"2018","unstructured":"Fang, C., Li, C.J., Lin, Z., Zhang, T.: SPIDER: near-optimal non-convex optimization via stochastic path-integrated differential estimator. In: Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 31, pp. 689\u2013699. Curran Associates Inc, Red Hook (2018)"},{"key":"2502_CR18","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1007\/s10107-022-01809-4","volume":"198","author":"G Garrigos","year":"2023","unstructured":"Garrigos, G., Rosasco, L., Villa, S.: Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry. Math. Program. 198, 937\u2013996 (2023)","journal-title":"Math. Program."},{"key":"2502_CR19","unstructured":"Gong, P., Ye, J.: Linear convergence of variance-reduced stochastic gradient without strong convexity. arXiv preprint arXiv:1406.1102 (2014)"},{"key":"2502_CR20","unstructured":"Gorbunov, E., Hanzely, F., Richtarik, P.: A unified theory of SGD: variance reduction, sampling, quantization and coordinate descent. In: Chiappa, S., Calandra, R. (eds) Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Volume 108 of Proceedings of Machine Learning Research, pp. 680\u2013690. PMLR (2020)"},{"key":"2502_CR21","first-page":"2305","volume-title":"Advances in Neural Information Processing Systems","author":"T Hofmann","year":"2015","unstructured":"Hofmann, T., Lucchi, A., Lacoste-Julien, S., McWilliams, B.: Variance reduced stochastic gradient descent with neighbors. In: Cortes, C., Lawrence, N., Lee, D., Sugiyama, M., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 28, pp. 2305\u20132313. Curran Associates Inc, Red Hook (2015)"},{"key":"2502_CR22","first-page":"315","volume-title":"Advances in Neural Information Processing Systems","author":"R Johnson","year":"2013","unstructured":"Johnson, R., Zhang, T.: Accelerating stochastic gradient descent using predictive variance reduction. In: Burges, C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K. (eds.) Advances in Neural Information Processing Systems, vol. 26, pp. 315\u2013323. Curran Associates Inc, Red Hook (2013)"},{"key":"2502_CR23","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1007\/978-3-319-46128-1_50","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"H Karimi","year":"2016","unstructured":"Karimi, H., Nutini, J., Schmidt, M.: Linear convergence of gradient and proximal-gradient methods under the Polyak-\u0142ojasiewicz condition. In: Frasconi, P., Landwehr, N., Manco, G., Vreeken, J. (eds.) Machine Learning and Knowledge Discovery in Databases, pp. 795\u2013811. Springer International Publishing, Cham (2016)"},{"key":"2502_CR24","unstructured":"Khaled, A., Jin, C.: Faster federated optimization under second-order similarity. In: The Eleventh International Conference on Learning Representations (2023)"},{"key":"2502_CR25","unstructured":"Khaled, A., Richt\u00e1rik, P. Better theory for SGD in the nonconvex world. Transactions on Machine Learning Research. Survey Certification (2023)"},{"key":"2502_CR26","unstructured":"Kim, J.L., Toulis, P., Kyrillidis, A.: Convergence and stability of the stochastic proximal point algorithm with momentum. In: Firoozi, R., Mehr, N., Yel, E., Antonova, R., Bohg, J., Schwager, M., Kochenderfer, M. (eds) Proceedings of The 4th Annual Learning for Dynamics and Control Conference, Volume 168 of Proceedings of Machine Learning Research, pp. 1034\u20131047. PMLR (2022)"},{"key":"2502_CR27","unstructured":"Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)"},{"key":"2502_CR28","unstructured":"Kovalev, D., Horv\u00e1th, S., Richt\u00e1rik, and P.: Don\u2019t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In: Kontorovich, A., Neu, G. (eds) Proceedings of the 31st International Conference on Algorithmic Learning Theory, Volume 117 of Proceedings of Machine Learning Research, pp. 451\u2013467. PMLR (2020)"},{"key":"2502_CR29","first-page":"87","volume":"117","author":"S \u0141ojasiewicz","year":"1963","unstructured":"\u0141ojasiewicz, S.: Une propri\u00e9t\u00e9 topologique des sous-ensembles analytiques r\u00e9els. Les \u00e9quations aux D\u00e9riv\u00e9es Partielles 117, 87\u201389 (1963)","journal-title":"Les \u00e9quations aux D\u00e9riv\u00e9es Partielles"},{"issue":"1","key":"2502_CR30","doi-asserted-by":"publisher","first-page":"1157","DOI":"10.1137\/22M1488181","volume":"34","author":"A Milzarek","year":"2024","unstructured":"Milzarek, A., Schaipp, F., Ulbrich, M.: A semismooth newton stochastic proximal point algorithm with variance reduction. SIAM J. Optim. 34(1), 1157\u20131185 (2024)","journal-title":"SIAM J. Optim."},{"key":"2502_CR31","first-page":"451","volume-title":"Advances in Neural Information Processing Systems","author":"E Moulines","year":"2011","unstructured":"Moulines, E., Bach, F.: Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In: Shawe-Taylor, J., Zemel, R., Bartlett, P., Pereira, F., Weinberger, K. (eds.) Advances in Neural Information Processing Systems, vol. 24, pp. 451\u2013459. Curran Associates Inc, Red Hook (2011)"},{"key":"2502_CR32","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2003","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. Springer Science & Business Media, Berlin (2003)"},{"key":"2502_CR33","unstructured":"Nguyen, L.M., Liu, J., Scheinberg, K., Tak\u00e1\u010d, M.: SARAH: a novel method for machine learning problems using stochastic recursive gradient. In: Precup, D., Teh, Y. W. (eds) Proceedings of the 34th International Conference on Machine Learning, Volume 70 of Proceedings of Machine Learning Research, pp. 2613\u20132621. PMLR (2017)"},{"issue":"1","key":"2502_CR34","first-page":"7204","volume":"18","author":"A Patrascu","year":"2017","unstructured":"Patrascu, A., Necoara, I.: Nonasymptotic convergence of stochastic proximal point methods for constrained convex optimization. J. Mach. Learn. Res. 18(1), 7204\u20137245 (2017)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"2502_CR35","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1016\/0041-5553(63)90382-3","volume":"3","author":"BT Polyak","year":"1963","unstructured":"Polyak, B.T.: Gradient methods for the minimisation of functionals. USSR Comput. Math. Math. Phys. 3(4), 864\u2013878 (1963)","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"5","key":"2502_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0041-5553(64)90137-5","volume":"4","author":"BT Polyak","year":"1964","unstructured":"Polyak, B.T.: Some methods of speeding up the convergence of iteration methods. USSR Comput. Math. Math. Phys. 4(5), 1\u201317 (1964)","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"3","key":"2502_CR37","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":"2502_CR38","unstructured":"Ryu, E.K., Boyd, S. Stochastic proximal iteration: a non-asymptotic improvement upon stochastic gradient descent. Author website, early draft (2014)"},{"issue":"1","key":"2502_CR39","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. 162(1), 83\u2013112 (2017)","journal-title":"Math. Program."},{"key":"2502_CR40","unstructured":"Sebbouh, O., Gower, R.M., Defazio, A.: Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. In: Belkin, M., Kpotufe, S. (eds) Proceedings of Thirty Fourth Conference on Learning Theory, Volume 134 of Proceedings of Machine Learning Research, pp. 3935\u20133971. PMLR (2021)"},{"key":"2502_CR41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding Machine Learning: From Theory to Algorithms","author":"S Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge (2014)"},{"issue":"4","key":"2502_CR42","doi-asserted-by":"publisher","first-page":"1694","DOI":"10.1214\/16-AOS1506","volume":"45","author":"P Toulis","year":"2017","unstructured":"Toulis, P., Airoldi, E.M.: Asymptotic and finite-sample properties of estimators based on stochastic gradients. Ann. Stat. 45(4), 1694\u20131727 (2017)","journal-title":"Ann. Stat."},{"issue":"1","key":"2502_CR43","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1111\/rssb.12405","volume":"83","author":"P Toulis","year":"2021","unstructured":"Toulis, P., Horel, T., Airoldi, E.M.: The proximal Robbins-Monro method. J. R. Stat. Soc. Ser. B Stat. Methodol. 83(1), 188\u2013212 (2021)","journal-title":"J. R. Stat. Soc. Ser. B Stat. Methodol."},{"key":"2502_CR44","unstructured":"Toulis, P., Tran, D., Airoldi, E.: Towards stability and optimality in stochastic gradient descent. In: Gretton, A., Robert, C.C. (eds) Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, Volume 51 of Proceedings of Machine Learning Research, Cadiz, Spain, 09\u201311 May 2016, pp. 1290\u20131298. PMLR"},{"key":"2502_CR45","first-page":"2406","volume-title":"Advances in Neural Information Processing Systems","author":"Z Wang","year":"2019","unstructured":"Wang, Z., Ji, K., Zhou, Y., Liang, Y., Tarokh, V.: Spiderboost and momentum: faster variance reduction algorithms. In: Wallach, H., Larochelle, H., Beygelzimer, A., d\u2019Alch\u00e9-Buc, F., Fox, E., Garnett, R. (eds.) Advances in Neural Information Processing Systems, vol. 32, pp. 2406\u20132416. Curran Associates Inc, Red Hook (2019)"},{"issue":"2","key":"2502_CR46","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/s10957-021-01978-w","volume":"192","author":"J Zhang","year":"2022","unstructured":"Zhang, J., Zhu, X.: Linear convergence of Prox-SVRG method for separable non-smooth convex optimization problems under bounded metric subregularity. J. Optim. Theory Appl. 192(2), 564\u2013597 (2022)","journal-title":"J. Optim. Theory Appl."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-024-02502-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-024-02502-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-024-02502-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T10:09:05Z","timestamp":1731319745000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-024-02502-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,2]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["2502"],"URL":"https:\/\/doi.org\/10.1007\/s10957-024-02502-6","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2024,8,2]]},"assertion":[{"value":"18 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}