{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T07:21:47Z","timestamp":1789888907983,"version":"4.0.1"},"reference-count":42,"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":[[2018,1]]},"abstract":"<jats:p>We focus on the problem of minimizing the sum of smooth component functions (where the sum is strongly convex) and a nonsmooth convex function, which arises in regularized empirical risk minimization in machine learning and distributed constrained optimization in wireless sensor networks and smart grids. We consider solving this problem using the proximal incremental aggregated gradient (PIAG) method, which at each iteration moves along an aggregated gradient (formed by incrementally updating gradients of component functions according to a deterministic order) and takes a proximal step with respect to the nonsmooth function. While the convergence properties of this method with randomized orders (in updating gradients of component functions) have been investigated, this paper, to the best of our knowledge, is the first study that establishes the convergence rate properties of the PIAG method for any deterministic order. In particular, we show that the PIAG algorithm is globally convergent with a linear rate provided that the step size is sufficiently small. We explicitly identify the rate of convergence and the corresponding step size to achieve this convergence rate. Our results improve upon the best known condition number and gradient delay bound dependence of the convergence rate of the incremental aggregated gradient methods used for minimizing a sum of smooth functions.<\/jats:p>","DOI":"10.1137\/16m1094415","type":"journal-article","created":{"date-parts":[[2018,5,8]],"date-time":"2018-05-08T11:53:02Z","timestamp":1525780382000},"page":"1282-1300","source":"Crossref","is-referenced-by-count":34,"title":["Global Convergence Rate of Proximal Incremental Aggregated Gradient Methods"],"prefix":"10.1137","volume":"28","author":[{"given":"N. D.","family":"Vanli","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"G\u00fcrb\u00fczbalaban","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A.","family":"Ozdaglar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,5,8]]},"reference":[{"key":"atypb1","unstructured":"A. Aytekin, H. R. Feyzmahdavian, and M. Johansson,\n                      Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server\n                      , preprint,http:\/\/arxiv.org\/abs\/1610.05507, 2016."},{"key":"atypb2","first-page":"1","author":"Bertsekas D. P.","year":"2011","journal-title":"MA"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0472-0"},{"key":"atypb4","unstructured":"D. P. Bertsekas,\n                      Convex Optimization Algorithms\n                      , Athena Scientific, Nashua, NH, 2015."},{"key":"atypb5","unstructured":"D. P. Bertsekas,\n                      Incremental Aggregated Proximal and Augmented Lagrangian Algorithms\n                      , preprint, arXiv:1509.09257 [cs.SY], 2015."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/040615961"},{"key":"atypb7","unstructured":"S. Bubeck,\n                      Theory of Convex Optimization for Machine Learning\n                      , preprint,https:\/\/arxiv.org\/abs\/1405.4980, 2014."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827596304010"},{"key":"atypb9","first-page":"1646","author":"Defazio A.","year":"2014","journal-title":"MA"},{"key":"atypb10","first-page":"315","author":"Defazio A. J.","year":"2013","journal-title":"MA"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"atypb12","unstructured":"D. Drusvyatskiy and A. S. Lewis,\n                      Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods\n                      , preprint,http:\/\/arxiv.org\/abs\/1602.06661, 2016."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2011.2161027"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2007.910281"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/MSP.2013.2245726"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/TSG.2015.2434831"},{"key":"atypb17","unstructured":"M. Gurbuzbalaban, A. Ozdaglar, and P. Parrilo,\n                      On the Convergence Rate of Incremental Aggregated Gradient Algorithms\n                      , preprint, arXiv:1506.02081, 2015."},{"key":"atypb18","unstructured":"M. Gurbuzbalaban, A. Ozdaglar, and P. Parrilo,\n                      Why Random Reshuffling Beats Stochastic Gradient Descent\n                      , preprint, arXiv:1510.08560, 2015."},{"key":"atypb19","first-page":"1","author":"Hazan T.","year":"2008","journal-title":"NJ"},{"key":"atypb20","first-page":"315","author":"Johnson R.","year":"2014","journal-title":"MA"},{"key":"atypb21","first-page":"795","author":"Karimi H.","year":"2016","journal-title":"Berlin"},{"key":"atypb22","first-page":"3384","author":"Lin H.","year":"2016","journal-title":"MA"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/140957639"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2010.2055862"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/130950288"},{"key":"atypb26","unstructured":"I. Necoara, Y. Nesterov, and F. Glineur,\n                      Linear Convergence of First Order Methods for Non-Strongly Convex Optimization\n                      , preprint,http:\/\/arxiv.org\/abs\/1504.06298, 2016."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499362111"},{"key":"atypb28","first-page":"381","author":"Nedic A.","year":"2001","journal-title":"New York"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0149-x"},{"key":"atypb30","first-page":"693","author":"Niu F.","year":"2011","journal-title":"MA"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/07069729X"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1561\/2400000003"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"key":"atypb34","first-page":"2663","author":"Roux N. L.","year":"2012","journal-title":"MA"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2015.2461520"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018366000512"},{"key":"atypb37","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","volume":"58","author":"Tibshirani R.","year":"1994","journal-title":"J. R. Stat. Soc. Ser. B Stat. Methodol."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0170-0"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-013-0409-2"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1986.1104412"},{"key":"atypb41","first-page":"2543","volume":"11","author":"Xiao L.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5221-8"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1094415","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:03:12Z","timestamp":1787338992000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1094415"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1094415"],"URL":"https:\/\/doi.org\/10.1137\/16m1094415","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}