{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T05:10:47Z","timestamp":1790745047468,"version":"4.1.0"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1637473"],"award-info":[{"award-number":["CMMI-1637473"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1637474"],"award-info":[{"award-number":["CMMI-1637474"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In this paper, we consider a class of finite-sum convex optimization problems defined over a distributed multiagent network with $m$ agents connected to a central server. In particular, the objective function consists of the average of $m$ ($\\ge 1$) smooth components associated with each network agent together with a strongly convex term. Our major contribution is to develop a new randomized incremental gradient algorithm, namely, the random gradient extrapolation method (RGEM), which does not require any exact gradient evaluation even for the initial point, but can achieve the optimal ${\\cal O}(\\log(1\/\\epsilon))$ complexity bound in terms of the total number of gradient evaluations of component functions to solve the finite-sum problems. Furthermore, we demonstrate that for stochastic finite-sum optimization problems, RGEM maintains the optimal ${\\cal O}(1\/\\epsilon)$ complexity (up to a certain logarithmic factor) in terms of the number of stochastic gradient computations, but attains an ${\\cal O}(\\log(1\/\\epsilon))$ complexity in terms of communication rounds. (Each round involves only one agent.) It is worth noting that the former bound is independent of the number of agents $m$, while the latter one only linearly depends on $m$ or even $\\sqrt m$ for ill-conditioned problems. To the best of our knowledge, this is the first time that these complexity bounds have been obtained for distributed and stochastic optimization problems. Moreover, our algorithms were developed based on a novel dual perspective of Nesterov's accelerated gradient method.<\/jats:p>","DOI":"10.1137\/17m1157891","type":"journal-article","created":{"date-parts":[[2018,10,2]],"date-time":"2018-10-02T13:36:37Z","timestamp":1538487397000},"page":"2753-2782","source":"Crossref","is-referenced-by-count":28,"title":["Random Gradient Extrapolation for Distributed and Stochastic Optimization"],"prefix":"10.1137","volume":"28","author":[{"given":"Guanghui","family":"Lan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yi","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,10,2]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"Z. Allen-Zhu,\n                      Katyusha: The first direct acceleration of stochastic gradient methods\n                      , in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, pp. 1200-1205.","DOI":"10.1145\/3055399.3055448"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403427823"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012902407120"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/040615961"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(67)90040-7"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF00934676"},{"key":"atypb7","unstructured":"C. Dang and G. Lan,\n                      Randomized First-Order Methods for Saddle Point Optimization\n                      , preprint, arXiv:1409.8625, 2014."},{"key":"atypb8","unstructured":"A. Defazio, F. Bach, and S. Lacoste-Julien,\n                      SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives\n                      , in Proceedings of Advances of Neural Information Processing Systems (NIPS), 2014."},{"key":"atypb9","first-page":"165","volume":"13","author":"Dekel O.","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2016.2525015"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/110848864"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/110848876"},{"key":"atypb13","unstructured":"S. Ghadimi and G. Lan,\n                      Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Optimization\n                      , Technical report, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 2013."},{"key":"atypb14","unstructured":"E. Hazan and H. Luo,\n                      Variance-Reduced and Projection-Free Stochastic Optimization\n                      , CoRR, abs\/1602.02101, 2016."},{"key":"atypb15","unstructured":"J. Hiriart-Urruty and C. Lemar\u00e9chal,\n                      Fundamentals of Convex Analysis\n                      , Springer, New York, 2012."},{"key":"atypb16","first-page":"2305","author":"Hofmann T.","year":"2015","journal-title":"Proceedings of Advances in Neural Information Processing Systems"},{"key":"atypb17","unstructured":"R. Johnson and T. Zhang,\n                      Accelerating stochastic gradient descent using predictive variance reduction\n                      , in Proceedings of Advances of Neural Information Processing Systems (NIPS), 2013, pp. 315-323."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012995281742"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0434-y"},{"key":"atypb20","unstructured":"G. Lan, S. Lee, and Y. Zhou,\n                      Communication-Efficient Algorithms for Decentralized and Stochastic Optimization\n                      , preprint, arXiv:1701.03961, 2017."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0261-6"},{"key":"atypb22","first-page":"1","volume":"13","author":"Lan G.","year":"2017","journal-title":"Math. Program."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2650563"},{"key":"atypb24","unstructured":"H. Lin, J. Mairal, and Z. Harchaoui,\n                      A Universal Catalyst for First-Order Optimization\n                      , Technical report, HAL-01160728, 2015."},{"key":"atypb25","unstructured":"H. B. McMahan, E. Moore, D. Ramage, S. Hampson, et al.\n                      Communication-Efficient Learning of Deep Networks from Decentralized Data\n                      , preprint, arXiv:1602.05629, 2016."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"atypb27","unstructured":"A. S. Nemirovski and D. Yudin,\n                      Problem Complexity and Method Efficiency in Optimization\n                      , Wiley-Interscience Ser. Discrete Math., John Wiley, New York, 1983."},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"Y. E. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Kluwer Academic Publishers, Norwell, MA, 2004.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb29","first-page":"55","author":"Pedregosa F.","year":"2017","journal-title":"Proceedings of Advances in Neural Information Processing Systems"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1030-6"},{"key":"atypb31","first-page":"567","volume":"14","author":"Shalev-Shwartz S.","year":"2013","journal-title":"J. Mach. Learn. Res."},{"key":"atypb32","first-page":"64","author":"Shalev-Shwartz S.","year":"2014","journal-title":"Proceedings of the International Conference on Machine Learning"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/14096668X"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s00041-008-9030-4"},{"key":"atypb35","unstructured":"P. Tseng,\n                      On Accelerated Proximal Gradient Methods for Convex-Concave Optimization\n                      , Manuscipt, University of Washington, Seattle, 2008."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1137\/140961791"},{"key":"atypb37","unstructured":"Y. Zhang and L. Xiao,\n                      Stochastic primal-dual coordinate method for regularized empirical risk minimization\n                      , in Proceedings of the 32nd International Conference on Machine Learning, 2015, pp. 353-361."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1157891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:51:45Z","timestamp":1787338305000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1157891"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1157891"],"URL":"https:\/\/doi.org\/10.1137\/17m1157891","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}