{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T05:26:23Z","timestamp":1787289983640,"version":"build-2736575974"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T00:00:00Z","timestamp":1785196800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"},{"start":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T00:00:00Z","timestamp":1785196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0"}],"funder":[{"DOI":"10.13039\/501100004052","name":"King Abdullah University of Science and Technology","doi-asserted-by":"publisher","award":["Center of Excellence for Generative AI, award 5940"],"award-info":[{"award-number":["Center of Excellence for Generative AI, award 5940"]}],"id":[{"id":"10.13039\/501100004052","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004052","name":"King Abdullah University of Science and Technology","doi-asserted-by":"publisher","award":["Competitive Research Grant, award 6460"],"award-info":[{"award-number":["Competitive Research Grant, award 6460"]}],"id":[{"id":"10.13039\/501100004052","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004052","name":"King Abdullah University of Science and Technology","doi-asserted-by":"publisher","award":["SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence"],"award-info":[{"award-number":["SDAIA-KAUST Center of Excellence in Data Science and Artificial Intelligence"]}],"id":[{"id":"10.13039\/501100004052","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1007\/s10957-026-03065-4","type":"journal-article","created":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T06:32:29Z","timestamp":1785220349000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization"],"prefix":"10.1007","volume":"210","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7087-1002","authenticated-orcid":false,"given":"Laurent","family":"Condat","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Richt\u00e1rik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,28]]},"reference":[{"key":"3065_CR1","doi-asserted-by":"crossref","unstructured":"Allen-Zhu, Z.: Katyusha: The first direct acceleration of stochastic gradient methods. In: Proc. of 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1200\u20131205. (2017)","DOI":"10.1145\/3055399.3055448"},{"key":"3065_CR2","unstructured":"Bai, Y., Liu, Y., Luo, L.: On the complexity of finite-sum smooth optimization under the Polyak-\u0141ojasiewicz condition. In: Proc. of 41st International Conference on Machine Learning (ICML), pp. 2392\u20132417. (2024). (PMLR 235)"},{"key":"3065_CR3","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, 2nd edn. Springer, New York (2017)","edition":"2"},{"key":"3065_CR4","volume-title":"Convex Optimization Algorithms.","author":"DP Bertsekas","year":"2015","unstructured":"Bertsekas, D.P.: Convex Optimization Algorithms. Athena Scientific, Belmont, MA, USA (2015)"},{"key":"3065_CR5","unstructured":"Bhojanapalli, S., Neyshabur, B., Srebro, N.: Global optimality of local search for low rank matrix recovery. In: Advances in Neural Information Processing Systems (NeurIPS), vol. 29, Curran Associates, Inc (2016)"},{"issue":"3\u20134","key":"3065_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1561\/2200000050","volume":"8","author":"S Bubeck","year":"2015","unstructured":"Bubeck, S.: Convex optimization: Algorithms and complexity. Found. Trends Mach. Learn. 8(3\u20134), 231\u2013357 (2015)","journal-title":"Found. Trends Mach. Learn."},{"issue":"1","key":"3065_CR7","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/18M1178244","volume":"29","author":"D Davis","year":"2019","unstructured":"Davis, D., Drusvyatskiy, D.: Stochastic model-based minimization of weakly convex functions. SIAM J. Optimization 29(1), 207\u2013239 (2019)","journal-title":"SIAM J. Optimization"},{"key":"3065_CR8","first-page":"1","volume":"25","author":"Y Han","year":"2024","unstructured":"Han, Y., Xie, G., Zhang, Z.: Lower complexity bounds of finite-sum optimization problems: the results and construction. J. Mach. Learn. Res. 25, 1\u201386 (2024)","journal-title":"J. Mach. Learn. Res."},{"key":"3065_CR9","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-\u0141ojasiewicz 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":"3065_CR10","unstructured":"Kawaguchi, K.: Deep learning without poor local minima. In: Advances in Neural Information Processing Systems (NeurIPS), vol. 29, Curran Associates, Inc (2016)"},{"key":"3065_CR11","unstructured":"Kovalev, D., Horv\u00e1th, S., Richt\u00e1rik, P.: Don\u2019t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In: Proc. of 31st Int. Conf. Algorithmic Learning Theory (ALT), pp. 451\u2013467. (2020). (PMLR 117)"},{"key":"3065_CR12","unstructured":"Li, B., Ma, M., Giannakis, G.B.: On the convergence of SARAH and beyond. In: Proc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), pp. 223\u2013233. (2020). (PMLR 108)"},{"key":"3065_CR13","unstructured":"Li, Z., Bao, H., Zhang, X., Richt\u00e1rik, P.: PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In: Proc. of 38th Int. Conf. Machine Learning (ICML), pp. 6286\u20136295. (2021). (PMLR 139)"},{"key":"3065_CR14","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: International Conference on Machine Learning (ICML), pp. 2613\u20132621. (2017)"},{"issue":"1","key":"3065_CR15","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF01068677","volume":"9","author":"E Nurminskii","year":"1973","unstructured":"Nurminskii, E.: The quasigradient method for the solving of the nonlinear programming problems. Cybernetics 9(1), 145\u2013150 (1973)","journal-title":"Cybernetics"},{"key":"3065_CR16","unstructured":"Richt\u00e1rik, P., Sokolov, I., Fatkhullin, I.: EF21: A new, simpler, theoretically better, and practically faster error feedback. In: Advances in Neural Information Processing Systems (NeurIPS), vol. 34, pp. 4384\u20134396. Curran Associates, Inc (2021)"},{"key":"3065_CR17","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding machine learning: From theory to algorithms, Cambridge University Press (2014)","DOI":"10.1017\/CBO9781107298019"},{"key":"3065_CR18","doi-asserted-by":"crossref","unstructured":"Sra, S., Nowozin, S., Wright, S.J.: Optimization for Machine Learning, The MIT Press (2011)","DOI":"10.7551\/mitpress\/8996.001.0001"},{"key":"3065_CR19","unstructured":"Sun, J., Qu, Q., Wright, J.: A geometric analysis of phase retrieval. In: Foundations of Computational Mathematics (FoCM), pp. 55\u2013124. Springer (2018)"},{"key":"3065_CR20","unstructured":"Sun, S., Yu, Y.: Least squares estimation of weakly convex functions. In: Proc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), (2019). (PMLR 89)"},{"key":"3065_CR21","unstructured":"Tyurin, A., Sun, L., Burlachenko, K., Richt\u00e1rik, P.: Sharper rates and flexible framework for nonconvex SGD with client and data sampling. Transactions on Machine Learning Research, (2023)"},{"key":"3065_CR22","unstructured":"Yue, P., Fang, C., Lin, Z.: On the lower bound of minimizing Polyak-\u0141ojasiewicz functions. In: Proc. of Thirty Sixth Conference on Learning Theory, pp. 2948\u20132968. (2023). (PMLR 195)"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-026-03065-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-026-03065-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-026-03065-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T05:08:47Z","timestamp":1787288927000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-026-03065-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,28]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["3065"],"URL":"https:\/\/doi.org\/10.1007\/s10957-026-03065-4","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,28]]},"assertion":[{"value":"14 December 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","label":"Competing Interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"33"}}