{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T16:38:30Z","timestamp":1768322310254,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,2,25]],"date-time":"2023-02-25T00:00:00Z","timestamp":1677283200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,25]],"date-time":"2023-02-25T00:00:00Z","timestamp":1677283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we derive a new linear convergence rate for the gradient method with fixed step lengths for non-convex smooth optimization problems satisfying the Polyak-\u0141ojasiewicz (P\u0141) inequality. We establish that the P\u0141 inequality is a necessary and sufficient condition for linear convergence to the optimal value for this class of problems. We list some related classes of functions for which the gradient method may enjoy linear convergence rate. Moreover, we investigate their relationship with the P\u0141 inequality.<\/jats:p>","DOI":"10.1007\/s11590-023-01981-2","type":"journal-article","created":{"date-parts":[[2023,2,25]],"date-time":"2023-02-25T02:02:37Z","timestamp":1677290557000},"page":"1105-1125","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Conditions for linear convergence of the gradient method for non-convex optimization"],"prefix":"10.1007","volume":"17","author":[{"given":"Hadi","family":"Abbaszadehpeivasti","sequence":"first","affiliation":[]},{"given":"Etienne","family":"de Klerk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4086-0999","authenticated-orcid":false,"given":"Moslem","family":"Zamani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,25]]},"reference":[{"key":"1981_CR1","doi-asserted-by":"crossref","unstructured":"Abbaszadehpeivasti, H., de Klerk, E., Zamani, M.: The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions. Opt. Lett., pp. 1\u201313 (2021)","DOI":"10.1007\/s11590-021-01821-1"},{"key":"1981_CR2","unstructured":"Abbaszadehpeivasti, H., de Klerk, E., Zamani, M.: On the rate of convergence of the difference-of-convex algorithm (DCA). arXiv preprint arXiv:2109.13566 (2021)"},{"issue":"1","key":"1981_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10107-007-0133-5","volume":"116","author":"H Attouch","year":"2009","unstructured":"Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116(1), 5\u201316 (2009)","journal-title":"Math. Program."},{"issue":"2","key":"1981_CR4","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1287\/moor.1100.0449","volume":"35","author":"H Attouch","year":"2010","unstructured":"Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-\u0141ojasiewicz inequality. Math. Oper. Res. 35(2), 438\u2013457 (2010)","journal-title":"Math. Oper. Res."},{"key":"1981_CR5","unstructured":"Bu, J., Mesbahi, M.: A note on Nesterov\u2019s accelerated method in nonconvex optimization: a weak estimate sequence approach. arXiv preprint arXiv:2006.08548 (2020)"},{"key":"1981_CR6","first-page":"1","volume":"184","author":"Y Carmon","year":"2019","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points I. Math. Program. 184, 1\u201350 (2019)","journal-title":"Math. Program."},{"key":"1981_CR7","unstructured":"Danilova, M., Dvurechensky, P., Gasnikov, A., Gorbunov, E., Guminov, S., Kamzolov, D., Shibaev, I.: Recent theoretical advances in non-convex optimization. arXiv preprint arXiv:2012.06188 (2020)"},{"issue":"1","key":"1981_CR8","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/18M1178244","volume":"29","author":"D Davis","year":"2019","unstructured":"Davis, D., Drusvyatskiy, D.: Stochastic model-based minimization of weakly convex functions. SIAM J. Opt. 29(1), 207\u2013239 (2019)","journal-title":"SIAM J. Opt."},{"issue":"7","key":"1981_CR9","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1007\/s11590-016-1087-4","volume":"11","author":"E De Klerk","year":"2017","unstructured":"De Klerk, E., Glineur, F., Taylor, A.B.: On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Opt. Lett. 11(7), 1185\u20131199 (2017)","journal-title":"Opt. Lett."},{"issue":"3","key":"1981_CR10","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1137\/19M1281368","volume":"30","author":"E De Klerk","year":"2020","unstructured":"De Klerk, E., Glineur, F., Taylor, A.B.: Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation. SIAM J. Opt. 30(3), 2053\u20132082 (2020)","journal-title":"SIAM J. Opt."},{"key":"1981_CR11","unstructured":"Drori, Y.: Contributions to the complexity analysis of optimization algorithms. Ph.D. thesis, Tel-Aviv University (2014)"},{"issue":"1","key":"1981_CR12","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-013-0653-0","volume":"145","author":"Y Drori","year":"2014","unstructured":"Drori, Y., Teboulle, M.: Performance of first-order methods for smooth convex minimization: a novel approach. Math. Program. 145(1), 451\u2013482 (2014)","journal-title":"Math. Program."},{"key":"1981_CR13","unstructured":"Gupta, S.D., Van Parys, B.P., Ryu, E.K.: Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods. arXiv preprint arXiv:2203.07305 (2022)"},{"key":"1981_CR14","unstructured":"Hinder, O., Sidford, A., Sohoni, N.: Near-optimal methods for minimizing star-convex functions and beyond. In: Conference on Learning Theory, pp. 1894\u20131938. PMLR (2020)"},{"issue":"1","key":"1981_CR15","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10107-020-01486-1","volume":"187","author":"B Hu","year":"2021","unstructured":"Hu, B., Seiler, P., Lessard, L.: Analysis of biased stochastic gradient descent using sequential semidefinite programs. Math. Program. 187(1), 383\u2013408 (2021)","journal-title":"Math. Program."},{"key":"1981_CR16","doi-asserted-by":"crossref","unstructured":"Karimi, H., Nutini, J., Schmidt, M.: Linear convergence of gradient and proximal-gradient methods under the Polyak-\u0141ojasiewicz condition. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 795\u2013811. Springer (2016)","DOI":"10.1007\/978-3-319-46128-1_50"},{"issue":"1","key":"1981_CR17","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s10107-018-1232-1","volume":"175","author":"I Necoara","year":"2019","unstructured":"Necoara, I., Nesterov, Y., Glineur, F.: Linear convergence of first order methods for non-strongly convex optimization. Math. Program. 175(1), 69\u2013107 (2019)","journal-title":"Math. Program."},{"issue":"1","key":"1981_CR18","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10107-012-0629-5","volume":"140","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Gradient methods for minimizing composite functions. Math. Program. 140(1), 125\u2013161 (2013)","journal-title":"Math. Program."},{"key":"1981_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on Convex Optimization","author":"Y Nesterov","year":"2018","unstructured":"Nesterov, Y.: Lectures on Convex Optimization, vol. 137. Springer (2018)"},{"issue":"4","key":"1981_CR20","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1016\/0041-5553(63)90382-3","volume":"3","author":"BT Polyak","year":"1963","unstructured":"Polyak, B.T.: Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics 3(4), 864\u2013878 (1963)","journal-title":"USSR Computational Mathematics and Mathematical Physics"},{"key":"1981_CR21","unstructured":"Rotaru, T., Glineur, F., Panagiotis, P.: Tight convergence rates of the gradient method on hypoconvex functions. arXiv preprint arXiv:2203.00775 (2022)"},{"key":"1981_CR22","unstructured":"Taylor, A.B.: Convex interpolation and performance estimation of first-order methods for convex optimization. Ph.D. thesis, Catholic University of Louvain, Louvain-la-Neuve, Belgium (2017)"},{"issue":"1","key":"1981_CR23","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-016-1009-3","volume":"161","author":"AB Taylor","year":"2017","unstructured":"Taylor, A.B., Hendrickx, J.M., Glineur, F.: Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Math. Program. 161(1), 307\u2013345 (2017)","journal-title":"Math. Program."},{"key":"1981_CR24","unstructured":"Zamani, M., Abbaszadehpeivasti, H., de Klerk, E.: Convergence rate analysis of the gradient descent-ascent method for convex-concave saddle-point problems. arXiv preprint arXiv:2209.01272 (2022)"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-01981-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-023-01981-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-01981-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T10:34:26Z","timestamp":1683542066000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-023-01981-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,25]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1981"],"URL":"https:\/\/doi.org\/10.1007\/s11590-023-01981-2","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,25]]},"assertion":[{"value":"31 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}