{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T16:24:36Z","timestamp":1771863876939,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,7]]},"DOI":"10.1007\/s10589-021-00284-5","type":"journal-article","created":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T06:20:54Z","timestamp":1623219654000},"page":"717-766","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Fastest rates for stochastic mirror descent methods"],"prefix":"10.1007","volume":"79","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0203-4004","authenticated-orcid":false,"given":"Filip","family":"Hanzely","sequence":"first","affiliation":[]},{"given":"Peter","family":"Richt\u00e1rik","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,9]]},"reference":[{"key":"284_CR1","unstructured":"Afkanpour A, Gy\u00f6rgy A, Szepesv\u00e1ri C, Bowling M: A randomized mirror descent algorithm for large scale multiple kernel learning. In: International Conference on Machine Learning, pp. 374\u2013382 (2013)"},{"key":"284_CR2","unstructured":"Allen-Zhu, Z., Orecchia, L.: Linear coupling: an ultimate unification of gradient and mirror descent. arXiv:1407.1537 (2014)"},{"key":"284_CR3","doi-asserted-by":"crossref","unstructured":"Bauschke, H.H., Bolte, J., Teboulle, M.: A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res. 330\u2013348 (2016)","DOI":"10.1287\/moor.2016.0817"},{"issue":"3","key":"284_CR4","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","volume":"31","author":"A Beck","year":"2003","unstructured":"Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167\u2013175 (2003)","journal-title":"Oper. Res. Lett."},{"key":"284_CR5","unstructured":"Benning, M., Betcke, M., Ehrhardt, M., Sch\u00f6nlieb, C.-B.: Gradient descent in a generalised Bregman distance framework. arXiv:1612.02506 (2016)"},{"issue":"12","key":"284_CR6","doi-asserted-by":"publisher","first-page":"123006","DOI":"10.1088\/0266-5611\/25\/12\/123006","volume":"25","author":"M Bertero","year":"2009","unstructured":"Bertero, M., Boccacci, P., Desider\u00e0, G., Vicidomini, G.: Image deblurring with poisson data: from cells to galaxies. Inverse Probl. 25(12),\u00a0123006 (2009)","journal-title":"Inverse Probl."},{"key":"284_CR7","doi-asserted-by":"crossref","unstructured":"Birnbaum, B., Devanur, N.R., Xiao, L.: Distributed algorithms via gradient descent for Fisher markets. In: Proceedings of the 12th ACM conference on Electronic commerce, pp. 127\u2013136. ACM (2011)","DOI":"10.1145\/1993574.1993594"},{"issue":"3","key":"284_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1961189.1961199","volume":"2","author":"C-C Chang","year":"2011","unstructured":"Chang, C.-C., Lin, L.: A library for support vector machines. ACM transactions on intelligent systems and technology (TIST) 2(3), 1\u201327 (2011)","journal-title":"ACM transactions on intelligent systems and technology (TIST)"},{"issue":"4","key":"284_CR9","doi-asserted-by":"publisher","first-page":"2032","DOI":"10.1214\/aos\/1176348385","volume":"19","author":"I Csiszar","year":"1991","unstructured":"Csiszar, I., et al.: Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems. Ann. Stat. 19(4), 2032\u20132066 (1991)","journal-title":"Ann. Stat."},{"issue":"2","key":"284_CR10","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1137\/130936361","volume":"25","author":"CD Dang","year":"2015","unstructured":"Dang, C.D.: Stochastic block mirror descent methods for nonsmooth and stochastic optimization. SIAM J. Optim. 25(2), 856\u2013881 (2015)","journal-title":"SIAM J. Optim."},{"key":"284_CR11","unstructured":"Defazio, A., Bach, F., Lacoste-Julien, S.: Saga: a fast incremental gradient method with support for non-strongly convex composite objectives. arXiv:1407.0202 (2014)"},{"key":"284_CR12","unstructured":"Flammarion, N., Bach, F.: Stochastic composite least-squares regression with convergence rate $$\\cal{O}(1\/n)$$. arXiv:1702.06429 (2017)"},{"issue":"4","key":"284_CR13","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(4), 1469\u20131492 (2012)","journal-title":"SIAM J. Optim."},{"key":"284_CR14","unstructured":"Hien, L.T.K., Lu, C., Xu, H., Feng, J.: Accelerated stochastic mirror descent algorithms for composite non-strongly convex optimization. arXiv preprint arXiv:1605.06892 (2016)"},{"key":"284_CR15","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. 26, 315\u2013323 (2013)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"284_CR16","unstructured":"Kenneth, L.: MM Optimization Algorithms. SIAM (2016)"},{"key":"284_CR17","unstructured":"Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. In: Proceedings of the 3rd International Conference on Learning Representations (ICLR) (2014)"},{"key":"284_CR18","first-page":"2845","volume":"28","author":"W Krichene","year":"2015","unstructured":"Krichene, W., Bayen, A., Bartlett, P.L.: Accelerated mirror descent in continuous and discrete time. Adv. Neural Inf. Process. Syst. 28, 2845\u20132853 (2015)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"284_CR19","doi-asserted-by":"crossref","unstructured":"Lan, G., Lu, Z., Monteiro, R.D.: Primal-dual first-order methods with $${\\cal{O}}(1\/ \\epsilon )$$ iteration-complexity for cone programming. Math. Program. 126(1), 1\u201329 (2011)","DOI":"10.1007\/s10107-008-0261-6"},{"key":"284_CR20","unstructured":"Lu, H.: Relative-continuity for non-Lipschitz non-smooth convex optimization using stochastic (or deterministic) mirror descent. arXiv preprint arXiv:1710.04718 (2017)"},{"key":"284_CR21","unstructured":"Lu, H., Freud, R.M., Nesterov, Y.: Relatively-smooth convex optimization by first-order methods, and applications. arXiv preprint arXiv:1610.05708 (2016)"},{"issue":"1","key":"284_CR22","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1137\/120894464","volume":"24","author":"A Nedic","year":"2014","unstructured":"Nedic, A., Lee, S.: On stochastic subgradient mirror-descent algorithm with weighted averaging. SIAM J. Optim. 24(1), 84\u2013107 (2014)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"284_CR23","doi-asserted-by":"publisher","first-page":"1574","DOI":"10.1137\/070704277","volume":"19","author":"A Nemirovski","year":"2009","unstructured":"Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4), 1574\u20131609 (2009)","journal-title":"SIAM J. Optim."},{"key":"284_CR24","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"A Nemirovsky","year":"1983","unstructured":"Nemirovsky, A., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)"},{"issue":"2","key":"284_CR25","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1137\/100802001","volume":"22","author":"Y Nesterov","year":"2012","unstructured":"Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341\u2013362 (2012)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"284_CR26","first-page":"372","volume":"27","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate $${O}(1\/k^2)$$. Soviet Math. Doklady 27(2), 372\u2013376 (1983)","journal-title":"Soviet Math. Doklady"},{"key":"284_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Yurii Nesterov","year":"2004","unstructured":"Nesterov, Yurii: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, London (2004)"},{"key":"284_CR28","unstructured":"Nguyen, L., Liu, J., Scheinberg, K., Tak\u00e1\u010d, M.: Sarah: a novel method for machine learning problems using stochastic recursive gradient. arXiv preprint arXiv:1703.00102 (2017)"},{"key":"284_CR29","unstructured":"Polyak, B.T.: Introduction to Optimization. Optimization Software (1987)"},{"issue":"5","key":"284_CR30","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1080\/10556788.2016.1190360","volume":"31","author":"Zheng Qu","year":"2016","unstructured":"Qu, Zheng, Richt\u00e1rik, P.: Coordinate descent with arbitrary sampling I: algorithms and complexity. Optim. Methods Softw. 31(5), 829\u2013857 (2016)","journal-title":"Optim. Methods Softw."},{"issue":"5","key":"284_CR31","doi-asserted-by":"publisher","first-page":"858","DOI":"10.1080\/10556788.2016.1190361","volume":"31","author":"Zheng Qu","year":"2016","unstructured":"Qu, Zheng, Richt\u00e1rik, Peter: Coordinate descent with arbitrary sampling II: expected separable overapproximation. Optim. Methods Softw. 31(5), 858\u2013884 (2016)","journal-title":"Optim. Methods Softw."},{"key":"284_CR32","unstructured":"Rakhlin, A., Shamir, O., Sridharan, K.: Making gradient descent optimal for strongly convex stochastic optimization. In: Proceedings of the 29th International Conference on Machine Learning, pp. 449\u2013456 (2012)"},{"issue":"6","key":"284_CR33","doi-asserted-by":"publisher","first-page":"1233","DOI":"10.1007\/s11590-015-0916-1","volume":"10","author":"Peter Richt\u00e1rik","year":"2016","unstructured":"Richt\u00e1rik, Peter, Tak\u00e1\u010d, Martin: On optimal probabilities in stochastic coordinate descent methods. Optim. Lett. 10(6), 1233\u20131243 (2016)","journal-title":"Optim. Lett."},{"issue":"1\u20132","key":"284_CR34","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s10107-015-0901-6","volume":"156","author":"P Richt\u00e1rik","year":"2016","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Parallel coordinate descent methods for big data optimization. Math. Program. 156(1\u20132), 433\u2013484 (2016)","journal-title":"Math. Program."},{"key":"284_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-012-0614-z","volume":"144","author":"P Richt\u00e1rik","year":"2014","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144, 1\u201338 (2014)","journal-title":"Math. Program."},{"issue":"1","key":"284_CR36","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s10107-015-0901-6","volume":"156","author":"P Richt\u00e1rik","year":"2016","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Parallel coordinate descent methods for big data optimization. Math. Program. 156(1), 433\u2013484 (2016)","journal-title":"Math. Program."},{"key":"284_CR37","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1214\/aoms\/1177729586","volume":"22","author":"H Robbins","year":"1951","unstructured":"Robbins, H., Monro, S.: A stochastic approximation method. Ann. Math. Stat. 22, 400\u2013407 (1951)","journal-title":"Ann. Math. Stat."},{"key":"284_CR38","unstructured":"Roux, N.L., Schmidt, M., Bach, F.: A stochastic gradient method with an exponential convergence rate for finite training sets. Adv. Neural Inf. Process. Syst. 2663\u20132671 (2012)"},{"key":"284_CR39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019","volume-title":"Understanding Machine Learning: from Theory to Algorithms","author":"S. Shalev-Shwartz","year":"2014","unstructured":"Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning: from Theory to Algorithms. Cambridge University Press, Cambridge (2014)"},{"issue":"1","key":"284_CR40","first-page":"567","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), 567\u2013599 (2013)","journal-title":"J. Mach. Learn. Res."},{"key":"284_CR41","unstructured":"Tappenden, R., Tak\u00e1\u010d, M., Richt\u00e1rik, P.: On the complexity of parallel coordinate descent. arXiv preprint arXiv:1503.03033 (2015)"},{"key":"284_CR42","unstructured":"Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. Technical report, Department of Mathematics, University of Washington\u00a0(2008)"},{"key":"284_CR43","doi-asserted-by":"crossref","unstructured":"Zhang, L.: Proportional response dynamics in the Fisher market. Theor. Comput. Sci. 412(24): 2691 \u2013 2698 (2011). Selected Papers from 36th International Colloquium on Automata, Languages and Programming (ICALP 2009)","DOI":"10.1016\/j.tcs.2010.06.021"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00284-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-021-00284-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00284-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,17]],"date-time":"2021-06-17T19:23:51Z","timestamp":1623957831000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-021-00284-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["284"],"URL":"https:\/\/doi.org\/10.1007\/s10589-021-00284-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"29 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}