{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T15:07:17Z","timestamp":1760800037765,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2017,6,28]],"date-time":"2017-06-28T00:00:00Z","timestamp":1498608000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,6,28]],"date-time":"2017-06-28T00:00:00Z","timestamp":1498608000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1537414","1254446"],"award-info":[{"award-number":["1537414","1254446"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1319050","N00014-13-1-0036"],"award-info":[{"award-number":["1319050","N00014-13-1-0036"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s10107-017-1173-0","type":"journal-article","created":{"date-parts":[[2017,6,28]],"date-time":"2017-06-28T09:07:56Z","timestamp":1498640876000},"page":"167-215","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":49,"title":["An optimal randomized incremental gradient method"],"prefix":"10.1007","volume":"171","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2103-087X","authenticated-orcid":false,"given":"Guanghui","family":"Lan","sequence":"first","affiliation":[]},{"given":"Yi","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,28]]},"reference":[{"key":"1173_CR1","unstructured":"Agarwal, A., Bottou, L.: A Lower Bound for the Optimization of Finite Sums. ArXiv e-prints, Oct 2014"},{"key":"1173_CR2","unstructured":"Allen-Zhu, Z., Hazan, E.: Optimal black-box reductions between optimization objectives. arXiv preprint \n                    arXiv:1603.05642\n                    \n                   (2016)"},{"key":"1173_CR3","unstructured":"Arjevani, Y., Shamir, O.: Dimension-free iteration complexity of finite sum optimization problems. arXiv preprint \n                    arXiv:1606.09333\n                    \n                   (2016)"},{"key":"1173_CR4","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S1052623403427823","volume":"16","author":"A Auslender","year":"2006","unstructured":"Auslender, A., Teboulle, M.: Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16, 697\u2013725 (2006)","journal-title":"SIAM J. Optim."},{"key":"1173_CR5","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/S0363012902407120","volume":"42","author":"HH Bauschke","year":"2003","unstructured":"Bauschke, H.H., Borwein, J.M., Combettes, P.L.: Bregman monotone optimization algorithms. SIAM J. Control Optim. 42, 596\u2013636 (2003)","journal-title":"SIAM J. Control Optim."},{"key":"1173_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"1173_CR7","first-page":"85","volume-title":"Optimization for Machine Learning","author":"DP Bertsekas","year":"2012","unstructured":"Bertsekas, D.P.: Incremental gradient, subgradient, and proximal methods for convex optimization: a survey. In: Nowozin, S., Sra, S., Wright, S.J. (eds.) Optimization for Machine Learning, pp. 85\u2013119. MIT Press, Cambridge (2012). (Extended version: LIDS report LIDS-P2848, MIT, 2010)"},{"key":"1173_CR8","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/0041-5553(67)90040-7","volume":"7","author":"LM Bregman","year":"1967","unstructured":"Bregman, L.M.: The relaxation method of finding the common point convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Phys. 7, 200\u2013217 (1967)","journal-title":"USSR Comput. Math. Phys."},{"key":"1173_CR9","unstructured":"Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal\u2013dual algorithm, Oct. 30, 2014"},{"key":"1173_CR10","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","volume":"40","author":"A Chambolle","year":"2011","unstructured":"Chambolle, A., Pock, T.: A first-order primal\u2013dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120\u2013145 (2011)","journal-title":"J. Math. Imaging Vis."},{"key":"1173_CR11","doi-asserted-by":"crossref","unstructured":"Chen, C., He, B., Ye, Y., Yuan, X.: The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program. 155, 57\u201379 (2016)","DOI":"10.1007\/s10107-014-0826-5"},{"issue":"4","key":"1173_CR12","doi-asserted-by":"publisher","first-page":"1779","DOI":"10.1137\/130919362","volume":"24","author":"Y Chen","year":"2014","unstructured":"Chen, Y., Lan, G., Ouyang, Y.: Optimal primal\u2013dual methods for a class of saddle point problems. SIAM J. Optim. 24(4), 1779\u20131814 (2014)","journal-title":"SIAM J. Optim."},{"key":"1173_CR13","unstructured":"Dang, C., Lan, G.: Randomized First-Order Methods for Saddle Point Optimization. Manuscript, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA, Sept 2014"},{"key":"1173_CR14","first-page":"1646","volume":"27","author":"A Defazio","year":"2014","unstructured":"Defazio, A., Bach, F., Lacoste-Julien, S.: SAGA: a fast incremental gradient method with support for non-strongly convex composite objectives. Adv. Neural Inf. Process. Syst. (NIPS) 27, 1646\u20131654 (2014)","journal-title":"Adv. Neural Inf. Process. Syst. (NIPS)"},{"key":"1173_CR15","unstructured":"Fercoq, O., Richt\u00e1rik, P.: Smooth minimization of nonsmooth functions with parallel coordinate descent methods. ArXiv e-prints, Sept 2013"},{"key":"1173_CR16","doi-asserted-by":"publisher","first-page":"1469","DOI":"10.1137\/110848864","volume":"22","author":"S Ghadimi","year":"2012","unstructured":"Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, I: a generic algorithmic framework. SIAM J. Optim. 22, 1469\u20131492 (2012)","journal-title":"SIAM J. Optim."},{"key":"1173_CR17","doi-asserted-by":"publisher","first-page":"2061","DOI":"10.1137\/110848876","volume":"23","author":"S Ghadimi","year":"2013","unstructured":"Ghadimi, S., Lan, G.: Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, II: shrinking procedures and optimal algorithms. SIAM J. Optim. 23, 2061\u20132089 (2013)","journal-title":"SIAM J. Optim."},{"key":"1173_CR18","unstructured":"Ghadimi, S., Lan, G.: Accelerated gradient methods for nonconvex nonlinear and stochastic optimization. Technical report, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA, June 2013"},{"key":"1173_CR19","volume-title":"Fundamentals of Convex Analysis","author":"J-B Hiriart-Urruty","year":"2012","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Fundamentals of Convex Analysis. Springer, New York (2012)"},{"key":"1173_CR20","first-page":"315","volume":"26","author":"R Johnson","year":"2013","unstructured":"Johnson, R., Zhang, T.: Accelerating stochastic gradient descent using predictive variance reduction. Adv. Neural Inf. Process. Syst. (NIPS) 26, 315\u2013323 (2013)","journal-title":"Adv. Neural Inf. Process. Syst. (NIPS)"},{"key":"1173_CR21","volume-title":"Optimization for Machine Learning","author":"A Juditsky","year":"2011","unstructured":"Juditsky, A., Nemirovski, A.S.: First-order methods for nonsmooth convex large-scale optimization, I: general purpose methods. In: Sra, S., Nowozin, S., Wright, S.J. (eds.) Optimization for Machine Learning. MIT Press, Cambridge (2011)"},{"key":"1173_CR22","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/S0363012995281742","volume":"35","author":"KC Kiwiel","year":"1997","unstructured":"Kiwiel, K.C.: Proximal minimization methods with generalized Bregman functions. SIAM J. Control Optim. 35, 1142\u20131168 (1997)","journal-title":"SIAM J. Control Optim."},{"issue":"1","key":"1173_CR23","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10107-010-0434-y","volume":"133","author":"G Lan","year":"2012","unstructured":"Lan, G.: An optimal method for stochastic composite optimization. Math. Program. 133(1), 365\u2013397 (2012)","journal-title":"Math. Program."},{"key":"1173_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-008-0261-6","volume":"126","author":"G Lan","year":"2011","unstructured":"Lan, G., Lu, Z., Monteiro, R.D.C.: Primal\u2013dual first-order methods with $${{\\cal{O}}}(1\/\\epsilon )$$ iteration-complexity for cone programming. Math. Program. 126, 1\u201329 (2011)","journal-title":"Math. Program."},{"key":"1173_CR25","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/s10107-011-0442-6","volume":"134","author":"G Lan","year":"2012","unstructured":"Lan, G., Nemirovski, A.S., Shapiro, A.: Validation analysis of mirror descent stochastic approximation method. Math. Program. 134, 425\u2013458 (2012)","journal-title":"Math. Program."},{"key":"1173_CR26","unstructured":"Lin, H., Mairal, J., Harchaoui, Z.: A universal catalyst for first-order optimization. Technical report, 2015. hal-01160728"},{"key":"1173_CR27","unstructured":"Lin, Q., Lu, Z., Xiao, L.: An accelerated proximal coordinate gradient method and its application to regularized empirical risk minimization. Technical report, 2014. no. MSR-TR-2014-94"},{"key":"1173_CR28","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/S1052623403425629","volume":"15","author":"AS Nemirovski","year":"2005","unstructured":"Nemirovski, A.S.: Prox-method with rate of convergence $$o(1\/t)$$ for variational inequalities with lipschitz continuous monotone operators and smooth convex\u2013concave saddle point problems. SIAM J. Optim. 15, 229\u2013251 (2005)","journal-title":"SIAM J. Optim."},{"key":"1173_CR29","doi-asserted-by":"publisher","first-page":"1574","DOI":"10.1137\/070704277","volume":"19","author":"AS Nemirovski","year":"2009","unstructured":"Nemirovski, A.S., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19, 1574\u20131609 (2009)","journal-title":"SIAM J. Optim."},{"key":"1173_CR30","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"AS Nemirovski","year":"1983","unstructured":"Nemirovski, A.S., Yudin, D.: Problem Complexity and Method Efficiency in Optimization, vol. XV. Wiley-Interscience Series in Discrete Mathematics. Wiley, New York (1983)"},{"key":"1173_CR31","first-page":"543","volume":"269","author":"YE Nesterov","year":"1983","unstructured":"Nesterov, Y.E.: A method for unconstrained convex minimization problem with the rate of convergence $$O(1\/k^2)$$. Dokl. AN SSSR 269, 543\u2013547 (1983)","journal-title":"Dokl. AN SSSR"},{"key":"1173_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"YE Nesterov","year":"2004","unstructured":"Nesterov, Y.E.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer, Boston (2004)"},{"key":"1173_CR33","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"YE Nesterov","year":"2005","unstructured":"Nesterov, Y.E.: Smooth minimization of nonsmooth functions. Math. Program. 103, 127\u2013152 (2005)","journal-title":"Math. Program."},{"key":"1173_CR34","unstructured":"Nesterov, Y.E.: Efficiency of coordinate descent methods on huge-scale optimization problems. Technical report, Center for Operations Research and Econometrics (CORE), Catholic University of Louvain, Feb 2010"},{"key":"1173_CR35","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10107-012-0629-5","volume":"140","author":"YE Nesterov","year":"2013","unstructured":"Nesterov, Y.E.: Gradient methods for minimizing composite objective functions. Math. Program. Ser. B 140, 125\u2013161 (2013)","journal-title":"Math. Program. Ser. B"},{"issue":"1","key":"1173_CR36","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/moor.1080.0348","volume":"34","author":"Y Nesterov","year":"2009","unstructured":"Nesterov, Y.: Unconstrained convex minimization in relative scale. Math. Oper. Res. 34(1), 180\u2013193 (2009)","journal-title":"Math. Oper. Res."},{"key":"1173_CR37","unstructured":"Schmidt, M., Roux, N.L., Bach, F.: Minimizing finite sums with the stochastic average gradient. Technical report, Sept 2013"},{"issue":"1","key":"1173_CR38","first-page":"567599","volume":"14","author":"S Shalev-Shwartz","year":"2013","unstructured":"Shalev-Shwartz, S., Zhang, T.: Stochastic dual coordinate ascent methods for regularized loss. J. Mach. Learn. Res. 14(1), 567599 (2013)","journal-title":"J. Mach. Learn. Res."},{"key":"1173_CR39","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S., Zhang, T.: Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. Math. Program. 155, 105\u2013145 (2016)","DOI":"10.1007\/s10107-014-0839-0"},{"key":"1173_CR40","unstructured":"Tseng, P.: On accelerated proximal gradient methods for convex\u2013concave optimization. Manuscript, University of Washington, Seattle, May 2008"},{"key":"1173_CR41","volume-title":"Operations Research: Applications and Algorithms","author":"WL Winston","year":"2004","unstructured":"Winston, W.L., Goldberg, J.B.: Operations Research: Applications and Algorithms, vol. 3. Duxbury Press, Belmont (2004)"},{"key":"1173_CR42","unstructured":"Woodworth, B., Srebro, N.: Tight complexity bounds for optimizing composite objectives. arXiv preprint \n                    arXiv:1605.08003\n                    \n                   (2016)"},{"key":"1173_CR43","unstructured":"Zhang, Y., Xiao, L.: Stochastic primal\u2013dual coordinate method for regularized empirical risk minimization. In: Proceedings of the 32nd International Conference on Machine Learning, pp. 353\u2013361 (2015)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-017-1173-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1173-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-017-1173-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T16:22:24Z","timestamp":1589646144000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-017-1173-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,28]]},"references-count":43,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["1173"],"URL":"https:\/\/doi.org\/10.1007\/s10107-017-1173-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2017,6,28]]},"assertion":[{"value":"18 October 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}