{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T09:10:30Z","timestamp":1785402630301,"version":"3.56.0"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-23-1-0531"],"award-info":[{"award-number":["FA9550-23-1-0531"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>This work considers the nonconvex, nonsmooth problem of minimizing a composite objective of the form [Formula: see text] where the inner mapping [Formula: see text] is a smooth finite summation or expectation amenable to variance reduction. In such settings, prox-linear methods enjoy variance-reduced speed-ups despite the existence of nonsmoothness. We provide a unified convergence theory applicable to a wide range of common variance-reduced vector and Jacobian constructions. All the technical conditions we require for variance-reduced methods can be summarized in a single unified assumption. Our theory (i) requires only operator norm bounds on Jacobians (whereas prior works used potentially much larger Frobenius norms), (ii) provides state-of-the-art high probability guarantees, and (iii) allows inexactness in proximal computations.<\/jats:p>","DOI":"10.1137\/25m1727606","type":"journal-article","created":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T08:00:32Z","timestamp":1785398432000},"page":"1619-1646","source":"Crossref","is-referenced-by-count":0,"title":["Some Unified Theory for Variance Reduced Prox-Linear Methods"],"prefix":"10.1137","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-4121-0788","authenticated-orcid":true,"given":"Yue","family":"Wu","sequence":"first","affiliation":[{"name":"Johns Hopkins University, Baltimore, MD 21211 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7003-8448","authenticated-orcid":true,"given":"Benjamin","family":"Grimmer","sequence":"additional","affiliation":[{"name":"Johns Hopkins University, Baltimore, MD 21211 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,7,30]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585997"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/11082381X"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01758-4"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/18M1178244"},{"key":"ref5","first-page":"1","volume":"22","author":"Davis D.","year":"2021","journal-title":"J. Mach. Learn. Res."},{"key":"ref6","unstructured":"A. Defazio, F. Bach, and S. Lacoste-Julien, SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives, in Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1, Adv. Neural Inform. Process. Syst. 27, MIT Press, 2014, pp. 1646\u20131654, https:\/\/dl.acm.org\/doi\/10.5555\/2968826.2969010."},{"key":"ref7","unstructured":"D. Drusvyatskiy, The Proximal Point Method Revisited, preprint, 2017, https:\/\/arxiv.org\/abs\/1712.06038."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0889"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1311-3"},{"key":"ref10","volume-title":"Advances in Neural Information Processing Systems 31","author":"Fang C.","year":"2018"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/120880811"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0846-1"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"R. M. Gower, M. Schmidt, F. Bach, and P. Richt\u00e1rik, Variance-reduced methods for machine learning, in Proc. IEEE, 108 (2020), pp. 1968\u20131983, https:\/\/doi.org\/10.1109\/JPROC.2020.3028013.","DOI":"10.1109\/JPROC.2020.3028013"},{"key":"ref14","unstructured":"B. Grimmer and D. Li, Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization, preprint, 2024, https:\/\/arxiv.org\/abs\/2305.17323."},{"key":"ref15","unstructured":"N. J. A. Harvey, C. Liaw, Y. Plan, and S. Randhawa, Tight analyses for non-smooth stochastic gradient descent, in Proceedings of the Thirty-Second Conference on Learning Theory, PMLR, 2019, pp. 1579\u20131613."},{"key":"ref16","first-page":"2489","volume":"15","author":"Hazan E.","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"ref17","unstructured":"S. J. Reddi, S. Sra, B. Poczos, and A. J. Smola, Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization, in Proceedings of the 30th International Conference on Neural Information Processing Systems, Adv. Neural Inform. Process. Syst. 29, Curran Associates, 2016, pp. 1153\u20131161, https:\/\/dl.acm.org\/doi\/abs\/10.5555\/3157096.3157225."},{"key":"ref18","unstructured":"R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction, in Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 1, Adv. Neural Inform. Process. Syst. 26, Curran Associates, 2013, pp. 315\u2013323, https:\/\/dl.acm.org\/doi\/10.5555\/2999611.2999647."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.3389\/fams.2017.00009"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0943-9"},{"key":"ref21","first-page":"5813","volume":"44","author":"Liu L.","year":"2022","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-023-02180-w"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1080\/08927020600643812"},{"key":"ref24","unstructured":"L. M. Nguyen, J. Liu, K. Scheinberg, and M. Tak\u00e1\u010d, Sarah: A novel method for machine learning problems using stochastic recursive gradient, in Proceedings of the 34th International Conference on Machine Learning, ICML\u201917, 2017, pp. 2613\u20132621."},{"key":"ref25","unstructured":"A. Rakhlin, O. Shamir, and K. Sridharan, Making gradient descent optimal for strongly convex stochastic optimization, in Proceedings of the 29th International Conference on Machine Learning, ICML\u201912, 2012, pp. 1571\u20131578."},{"key":"ref26","unstructured":"Q. Tran-Dinh, N. Pham, and L. Nguyen, Stochastic Gauss-Newton algorithms for nonconvex compositional optimization, in Proceedings of the 37th International Conference on Machine Learning, PMLR, 2020, pp. 9572\u20139582."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9099-z"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1561\/2200000048"},{"key":"ref29","first-page":"1","volume":"18","author":"Wang M.","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref30","unstructured":"Y. Wu and B. Grimmer, Some Unified Theory for Variance Reduced Prox-Linear Methods, preprint, 2024, https:\/\/arxiv.org\/abs\/2412.15008."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01709-z"},{"key":"ref32","unstructured":"D. Zhou, P. Xu, and Q. Gu, Stochastic variance-reduced cubic regularized Newton methods, in Proceedings of the 35th International Conference on Machine Learning, PMLR, 2018, pp. 5990\u20135999."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T08:00:38Z","timestamp":1785398438000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1727606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,30]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,9,30]]}},"alternative-id":["10.1137\/25M1727606"],"URL":"https:\/\/doi.org\/10.1137\/25m1727606","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,30]]}}}