{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T15:16:54Z","timestamp":1777389414941,"version":"3.51.4"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319461274","type":"print"},{"value":"9783319461281","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-46128-1_50","type":"book-chapter","created":{"date-parts":[[2016,9,3]],"date-time":"2016-09-03T05:34:23Z","timestamp":1472880863000},"page":"795-811","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":431,"title":["Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-\u0141ojasiewicz Condition"],"prefix":"10.1007","author":[{"given":"Hamed","family":"Karimi","sequence":"first","affiliation":[]},{"given":"Julie","family":"Nutini","sequence":"additional","affiliation":[]},{"given":"Mark","family":"Schmidt","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,4]]},"reference":[{"key":"50_CR1","doi-asserted-by":"publisher","first-page":"2452","DOI":"10.1214\/12-AOS1032","volume":"40","author":"A Agarwal","year":"2012","unstructured":"Agarwal, A., Negahban, S.N., Wainwright, M.J.: Fast global convergence rates of gradient methods for high-dimensional statistical recovery. Ann. Statist. 40, 2452\u20132482 (2012)","journal-title":"Ann. Statist."},{"key":"50_CR2","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1137\/S1052623499359178","volume":"10","author":"M Anitescu","year":"2000","unstructured":"Anitescu, M.: Degenerate nonlinear programming with a quadratic growth condition. SIAM J. Optim. 10, 1116\u20131135 (2000)","journal-title":"SIAM J. Optim."},{"issue":"1-2","key":"50_CR3","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s10107-007-0133-5","volume":"116","author":"Hedy Attouch","year":"2007","unstructured":"Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. Ser. B 116, 5\u201316 (2009)","journal-title":"Mathematical Programming"},{"key":"50_CR4","unstructured":"Bach, F., Moulines, E.: Non-strongly-convex smooth stochastic approximation with convergence rate $$O(1\/n)$$. In: Advances in Neural Information Processing Systems (NIPS), pp. 773\u2013791 (2013)"},{"key":"50_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0334270000005142","volume":"28","author":"A Ben-Israel","year":"1986","unstructured":"Ben-Israel, A., Mond, B.: What is invexity? J. Austral. Math. Soc. 28, 1\u20139 (1986)","journal-title":"J. Austral. Math. Soc."},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.W.: From Error Bounds to the Complexity of First-Order Descent Methods for Convex Functions. arXiv:1510.08234 (2015)","DOI":"10.1007\/s10107-016-1091-6"},{"key":"50_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S1446788700022126","volume":"39","author":"BD Craven","year":"1985","unstructured":"Craven, B.D., Glover, B.M.: Invex functions and duality. J. Austral. Math. Soc. 39, 1\u201320 (1985)","journal-title":"J. Austral. Math. Soc."},{"key":"50_CR8","unstructured":"Dinuzzo, F., Ong, C.S., Gehler, P., Pillonetto, G.: Learning output kernels with block coordinate descent. In: Proceedings of the 28th ICML, pp. 49\u201356 (2011)"},{"key":"50_CR9","unstructured":"Garber, D., Hazan, E.: Faster rates for the Frank-Wolfe method over strongly-convex sets. In: Proceedings of the 32nd ICML, pp. 541\u2013549 (2015)"},{"key":"50_CR10","unstructured":"Garber, D., Hazan, E.: Faster and Simple PCA via Convex Optimization. arXiv:1509.05647v4 (2015)"},{"key":"50_CR11","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s11075-012-9668-5","volume":"64","author":"M Gu","year":"2013","unstructured":"Gu, M., Lim, L.-H., Wu, C.J.: ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals. Numer. Algor. 64, 321\u2013347 (2013)","journal-title":"Numer. Algor."},{"key":"50_CR12","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/0022-247X(81)90123-2","volume":"80","author":"MA Hanson","year":"1981","unstructured":"Hanson, M.A.: On sufficiency of the Kuhn-Tucker conditions. J. Math. Anal. Appl. 80, 545\u2013550 (1981)","journal-title":"J. Math. Anal. Appl."},{"key":"50_CR13","doi-asserted-by":"publisher","first-page":"263","DOI":"10.6028\/jres.049.027","volume":"49","author":"AJ Hoffman","year":"1952","unstructured":"Hoffman, A.J.: On approximate solutions of systems of linear inequalities. J. Res. Nat. Bur. Stand. 49, 263\u2013265 (1952)","journal-title":"J. Res. Nat. Bur. Stand."},{"key":"50_CR14","unstructured":"Hou, K., Zhou, Z., So, A.M.-C., Luo, Z.-Q.: On the linear convergence of the proximal gradient method for trace norm regularization. In: Advances in Neural Information Processing Systems (NIPS), pp. 710\u2013718 (2013)"},{"key":"50_CR15","first-page":"733","volume":"7","author":"D Hush","year":"2006","unstructured":"Hush, D., Kelly, P., Scovel, C., Steinwart, I.: QP algorithms with guaranteed accuracy and run time for support vector machines. J. Mach. Learn. Res. 7, 733\u2013769 (2006)","journal-title":"J. Mach. Learn. Res."},{"key":"50_CR16","unstructured":"Johnson, R., Zhang, T.: Accelerating stochastic gradient descent using predictive variance reduction. In: Advances in Neural Information Processing Systems (NIPS), pp. 315\u2013323 (2013)"},{"key":"50_CR17","doi-asserted-by":"crossref","unstructured":"Kadkhodaie, M. Sanjabi, M., Luo, Z.-Q.: On the Linear Convergence of the Approximate Proximal Splitting Method for Non-Smooth Convex Optimization. arXiv:1404.5350v1 (2014)","DOI":"10.1007\/s40305-014-0047-x"},{"key":"50_CR18","unstructured":"Li, G., Pong, T.K.: Calculus of the Exponent of Kurdyka-\u0141ojasiewicz Inequality and its Applications to Linear Convergence of First-Order Methods. arXiv:1602.02915v1 (2016)"},{"key":"50_CR19","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/140961134","volume":"25","author":"J Liu","year":"2015","unstructured":"Liu, J., Wright, S.J.: Asynchronous stochastic coordinate descent: parallelism and convergence properties. SIAM J. Optim. 25, 351\u2013376 (2015)","journal-title":"SIAM J. Optim."},{"key":"50_CR20","unstructured":"Liu, J., Wright, S.J., R\u00e9, C., Bittorf, V., Sridhar, S.: An Asynchronous Parallel Stochastic Coordinate Descent Algorithm. arXiv:1311.1873v3 (2014)"},{"key":"50_CR21","unstructured":"\u0141ojasiewicz, S.: A Topological Property of Real Analytic Subsets (in French). Coll. du CNRS, Les \u00e9quations aux d\u00e9riv\u00e9es partielles, vol. 117, pp. 87\u201389 (1963)"},{"key":"50_CR22","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02096261","volume":"46","author":"Z-Q Luo","year":"1993","unstructured":"Luo, Z.-Q., Tseng, P.: Error bounds and convergence analysis of feasible descent methods: a general approach. Ann. Oper. Res. 46, 157\u2013178 (1993)","journal-title":"Ann. Oper. Res."},{"key":"50_CR23","unstructured":"Ma, C., Tappenden, T., Tak\u00e1\u010d, M.: Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption. arXiv:1506.02530 (2015)"},{"key":"50_CR24","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/3-540-36434-X_4","volume-title":"Advanced Lectures on Machine Learning","author":"R Meir","year":"2003","unstructured":"Meir, R., R\u00e4tsch, G.: An introduction to boosting and leveraging. In: Mendelson, S., Smola, A.J. (eds.) Advanced Lectures on Machine Learning. LNCS (LNAI), vol. 2600, pp. 118\u2013183. Springer, Heidelberg (2003). doi:10.1007\/3-540-36434-X_4"},{"key":"50_CR25","unstructured":"Necoara, I., Nesterov, Y., Glineur, F.: Linear Convergence of First Order Methods for Non-Strongly Convex Optimization. arXiv:1504.06298v3 (2015)"},{"key":"50_CR26","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1137\/130950288","volume":"26","author":"I Necoara","year":"2016","unstructured":"Necoara, I., Clipici, D.: Parallel random coordinate descent method for composite minimization: convergence analysis and error bounds. SIAM J. Optim. 26, 197\u2013226 (2016)","journal-title":"SIAM J. Optim."},{"key":"50_CR27","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, 1574\u20131609 (2009)","journal-title":"SIAM J. Optim."},{"key":"50_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Dordrecht (2004)"},{"key":"50_CR29","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, 341\u2013362 (2012)","journal-title":"SIAM J. Optim."},{"key":"50_CR30","unstructured":"Nutini, J., Schmidt, M., Laradji, I.H., Friedlander, M., Koepke, H.: Coordinate descent converges faster with the Gauss-Southwell rule than random selection. In: Proceedings of the 32nd ICML, pp. 1632\u20131641 (2015)"},{"key":"50_CR31","first-page":"643","volume":"3","author":"BT Polyak","year":"1963","unstructured":"Polyak, B.T.: Gradient methods for minimizing functionals. Zh. Vychisl. Mat. Mat. Fiz. 3, 643\u2013653 (1963). (in Russian)","journal-title":"Zh. Vychisl. Mat. Mat. Fiz."},{"key":"50_CR32","unstructured":"Riedmiller, M., Braun, H.: RPROP - a fast adaptive learning algorithm. In: Proceedings of ISCIS VII (1992)"},{"key":"50_CR33","unstructured":"Roux, N.L., Schmidt, M., Bach, F.R.: A stochastic gradient method with an exponential convergence rate for finite training sets. In: Advances in Neural Information Processing Systems (NIPS), pp. 2672\u20132680 (2012)"},{"key":"50_CR34","unstructured":"Schmidt, M., Roux, N.L., Bach, F.R.: Convergence rates of inexact proximal-gradient methods for convex optimization. In: Advances in Neural Information Processing Systems (NIPS), pp. 1458\u20131466 (2011)"},{"key":"50_CR35","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 minimization. J. Mach. Learn. Res. 14, 567\u2013599 (2013)","journal-title":"J. Mach. Learn. Res."},{"key":"50_CR36","doi-asserted-by":"crossref","unstructured":"Reddi, S.J., Sra, S., Poczos, B., Smola, A.: Fast Incremental Method for Nonconvex Optimization. arXiv:1603.06159 (2016)","DOI":"10.1109\/CDC.2016.7798553"},{"key":"50_CR37","doi-asserted-by":"crossref","unstructured":"Reddi, S.J., Hefny, A., Sra, S., Poczos, B., Smola, A.: Stochastic Variance Reduction for Nonconvex Optimization. arXiv:1603.06160 (2016)","DOI":"10.1109\/ALLERTON.2016.7852377"},{"key":"50_CR38","doi-asserted-by":"crossref","unstructured":"Reddi, S.J., Sra, S., Poczos, B., Smola, A.,: Fast Stochastic Methods for Nonsmooth Nonconvex Optimization. arXiv:1605.06900 (2016)","DOI":"10.1109\/CDC.2016.7798553"},{"issue":"1-2","key":"50_CR39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-012-0614-z","volume":"144","author":"Peter Richt\u00e1rik","year":"2012","unstructured":"Richt\u00e1rik, P., Tak\u00e1\u010d, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. Ser. A 144, 1\u201338 (2014)","journal-title":"Mathematical Programming"},{"issue":"2","key":"50_CR40","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s10107-010-0394-2","volume":"125","author":"Paul Tseng","year":"2010","unstructured":"Tseng, P.: Approximation accuracy, gradient methods, and error bound for structured convex optimization. Math. Program. Ser. B 125, 263\u2013295 (2010)","journal-title":"Mathematical Programming"},{"key":"50_CR41","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1007\/s10957-008-9458-3","volume":"140","author":"P Tseng","year":"2009","unstructured":"Tseng, P., Yun, S.: Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization. J. Optim. Theory Appl. 140, 513\u2013535 (2009)","journal-title":"J. Optim. Theory Appl."},{"key":"50_CR42","first-page":"1523","volume":"15","author":"P-W Wang","year":"2014","unstructured":"Wang, P.-W., Lin, C.-J.: Iteration complexity of feasible descent methods for convex optimization. J. Mach. Learn. Res. 15, 1523\u20131548 (2014)","journal-title":"J. Mach. Learn. Res."},{"key":"50_CR43","doi-asserted-by":"publisher","first-page":"1062","DOI":"10.1137\/120869997","volume":"23","author":"L Xiao","year":"2013","unstructured":"Xiao, L., Zhang, T.: A proximal-gradient homotopy method for the sparse least-squares problem. SIAM J. Optim. 23, 1062\u20131091 (2013)","journal-title":"SIAM J. Optim."},{"key":"50_CR44","doi-asserted-by":"crossref","unstructured":"Zhang, H.: The Restricted Strong Convexity Revisited: Analysis of Equivalence to Error Bound and Quadratic Growth. arXiv:1511.01635 (2015)","DOI":"10.1007\/s11590-016-1058-9"},{"key":"50_CR45","unstructured":"Zhang, H., Yin, W.: Gradient Methods for Convex Minimization: Better Rates Under Weaker Conditions. arXiv:1303.4645v2 (2013)"}],"container-title":["Lecture Notes in Computer Science","Machine Learning and Knowledge Discovery in Databases"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-46128-1_50","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,7]],"date-time":"2022-07-07T18:23:29Z","timestamp":1657218209000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-46128-1_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319461274","9783319461281"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-46128-1_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"4 September 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ECML PKDD","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Joint European Conference on Machine Learning and Knowledge Discovery in Databases","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Riva del Garda","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ecml2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}