{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T05:51:34Z","timestamp":1788587494459,"version":"build-2803163510"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A popular approach to minimizing a finite sum of smooth convex functions is stochastic gradient descent (SGD) and its variants. Fundamental research questions associated with SGD include (i) how to find a lower bound on the number of times that the gradient oracle of each individual function must be assessed in order to find an [Formula: see text]-minimizer of the overall objective; (ii) how to design algorithms which guarantee finding an [Formula: see text]-minimizer of the overall objective in expectation no more than a certain number of times (in terms of [Formula: see text]) that the gradient oracle of each function needs to be assessed (i.e., upper bound). If these two bounds are at the same order of magnitude, then the algorithms may be called optimal. Most existing results along this line of research typically assume that the functions in the objective share the same condition number. In this paper, the first model we study is the problem of minimizing the sum of finitely many strongly convex functions whose condition numbers are all different. We propose an SGD-based method for this model and show that it is optimal in gradient computations, up to a logarithmic factor. We then consider a constrained separate block optimization model and present lower and upper bounds for its gradient computation complexity. Next, we propose solving the Fenchel dual of the constrained block optimization model via generalized SSNM, which we introduce earlier, and show that it yields a lower iteration complexity than solving the original model by the ADMM-type approach. Finally, we extend the analysis to the general composite convex optimization model and obtain gradient-computation complexity results under certain conditions.<\/jats:p>","DOI":"10.1137\/22m1503646","type":"journal-article","created":{"date-parts":[[2024,4,11]],"date-time":"2024-04-11T04:01:55Z","timestamp":1712808115000},"page":"1374-1401","source":"Crossref","is-referenced-by-count":1,"title":["A Gradient Complexity Analysis for Minimizing the Sum of Strongly Convex Functions with Varying Condition Numbers"],"prefix":"10.1137","volume":"34","author":[{"given":"Nuozhou","family":"Wang","sequence":"first","affiliation":[{"name":"Department of Industrial and System Engineering, University of Minnesota, Minneapolis, MN 55455 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5838-1676","authenticated-orcid":true,"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Industrial and System Engineering, University of Minnesota, Minneapolis, MN 55455 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,4,11]]},"reference":[{"key":"ref1","first-page":"8194","volume":"18","author":"Allen-Zhu Z.","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/100818327"},{"key":"ref3","first-page":"1646","volume-title":"Advances in Neural Information Processing Systems","author":"Defazio A.","year":"2014"},{"key":"ref4","unstructured":"X. Gao, Low-Order Optimization Algorithms: Iteration Complexity and Applications, Ph.D. thesis, University of Minnesota, 2018."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-023-02060-2"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1034-2"},{"key":"ref7","unstructured":"Y. Jin, A. Sidford, and K. Tian, Sharper rates for separable minimax and finite sum optimization via primal-dual extragradient methods, in Conference on Learning Theory, PMLR, 2022, pp. 4362\u20134415."},{"key":"ref8","first-page":"315","volume":"26","author":"Johnson R.","year":"2013","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.pan.a004868"},{"key":"ref10","first-page":"451","volume-title":"Algorithmic Learning Theory","author":"Kovalev D.","year":"2020"},{"key":"ref11","first-page":"10462","volume":"32","author":"Lan G.","year":"2019","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1173-0"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/140971178"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-016-0182-0"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0800-2"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(92)90013-2"},{"key":"ref17","series-title":"Appl. Optim. 87","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Nesterov Y.","year":"2003"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0790-0"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1030-6"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01660-z"},{"key":"ref24","unstructured":"K. Zhou, Q. Ding, F. Shang, J. Cheng, D. Li, and Z.Q. Luo, Direct acceleration of SAGA using sampled negative momentum, in the 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 1602\u20131610."},{"key":"ref25","unstructured":"X. Zhou, On the Fenchel Duality Between Strong Convexity and Lipschitz Continuous Gradient, preprint, arXiv:1803.06573, 2018."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1503646","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:05:41Z","timestamp":1787339141000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1503646"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,11]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1137\/22M1503646"],"URL":"https:\/\/doi.org\/10.1137\/22m1503646","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,11]]}}}