{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:46:58Z","timestamp":1775594818171,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"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":["Found Comput Math"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s10208-021-09502-2","type":"journal-article","created":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T21:02:36Z","timestamp":1616792556000},"page":"211-256","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A Simple Nearly Optimal Restart Scheme For Speeding Up First-Order Methods"],"prefix":"10.1007","volume":"22","author":[{"given":"James","family":"Renegar","sequence":"first","affiliation":[]},{"given":"Benjamin","family":"Grimmer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,26]]},"reference":[{"issue":"2","key":"9502_CR1","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/moor.2016.0817","volume":"42","author":"H Bauschke","year":"2017","unstructured":"Bauschke, H., Bolte, J., Teboulle, M.: A descent lemma beyond lipschitz gradient continuity: First-order methods revisited and applications. Mathematics of Operations Research 42(2), 330\u2013348 (2017). https:\/\/doi.org\/10.1287\/moor.2016.0817.","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"9502_CR2","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/S0363012902407120","volume":"42","author":"H Bauschke","year":"2003","unstructured":"Bauschke, H., Borwein, J., Combettes, P.: Bregman monotone optimization algorithms. SIAM Journal on control and optimization 42(2), 596\u2013636 (2003)","journal-title":"SIAM Journal on control and optimization"},{"issue":"1","key":"9502_CR3","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 journal on imaging sciences 2(1), 183\u2013202 (2009)","journal-title":"SIAM journal on imaging sciences"},{"issue":"2","key":"9502_CR4","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1137\/100818327","volume":"22","author":"A Beck","year":"2012","unstructured":"Beck, A., Teboulle, M.: Smoothing and first order methods: A unified framework. SIAM Journal on Optimization 22(2), 557\u2013580 (2012)","journal-title":"SIAM Journal on Optimization"},{"issue":"4","key":"9502_CR5","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1137\/050644641","volume":"17","author":"J Bolte","year":"2007","unstructured":"Bolte, J., Daniilidis, A., Lewis, A.: The \u0141ojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization 17(4), 1205\u20131223 (2007)","journal-title":"SIAM Journal on Optimization"},{"issue":"2","key":"9502_CR6","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s10107-016-1091-6","volume":"165","author":"J Bolte","year":"2017","unstructured":"Bolte, J., Nguyen, T., Peypouquet, J., Suter, B.: From error bounds to the complexity of first-order descent methods for convex functions. Mathematical Programming 165(2), 471\u2013507 (2017)","journal-title":"Mathematical Programming"},{"key":"9502_CR7","unstructured":"Fercoq, O., Qu, Z.: Restarting accelerated gradient methods with a rough strong convexity estimate. arXiv preprint arxiv:1609.07358 (2016)"},{"issue":"4","key":"9502_CR8","doi-asserted-by":"publisher","first-page":"2069","DOI":"10.1093\/imanum\/drz007","volume":"39","author":"O Fercoq","year":"2019","unstructured":"Fercoq, O., Qu, Z.: Adaptive restart of accelerated gradient methods under local quadratic growth condition. IMA Journal of Numerical Analysis 39(4), 2069\u20132095 (2019)","journal-title":"IMA Journal of Numerical Analysis"},{"key":"9502_CR9","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s10107-010-0430-2","volume":"133","author":"A Gilpin","year":"2010","unstructured":"Gilpin, A., Pena, J., Sandholm, T.: First-order algorithm with $${\\cal{O}({\\rm ln}(1{\/}\\epsilon ))}$$ convergence for $${\\epsilon }$$-equilibrium in two-person zero-sum games. Mathematical Programming 133, 279\u2013298 (2010)","journal-title":"Mathematical Programming"},{"key":"9502_CR10","doi-asserted-by":"crossref","unstructured":"Giselsson, P., Boyd, S.: Monotonicity and restart in fast gradient methods. In: Decision and Control (CDC), 2014 IEEE 53rd Annual Conference on, pp. 5058\u20135063. IEEE (2014)","DOI":"10.1109\/CDC.2014.7040179"},{"issue":"1","key":"9502_CR11","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF01584346","volume":"13","author":"J Goffin","year":"1977","unstructured":"Goffin, J.: On convergence rates of subgradient optimization methods. Mathematical Programming 13(1), 329\u2013347 (1977)","journal-title":"Mathematical Programming"},{"key":"9502_CR12","unstructured":"Iouditski, A., Nesterov, Y.: Primal-dual subgradient methods for minimizing uniformly convex functions. arXiv:1401.1792 (2014)"},{"issue":"1","key":"9502_CR13","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10107-018-01361-0","volume":"180","author":"P Johnstone","year":"2020","unstructured":"Johnstone, P., Moulin, P.: Faster subgradient methods for functions with h\u00f6lderian growth. Mathematical Programming 180(1), 417\u2013450 (2020)","journal-title":"Mathematical Programming"},{"key":"9502_CR14","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"},{"key":"9502_CR15","unstructured":"Lin, Q., Xiao, L.: An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization. In: International Conference on Machine Learning, pp. 73\u201381 (2014)"},{"key":"9502_CR16","first-page":"87","volume":"117","author":"S Lojasiewicz","year":"1963","unstructured":"Lojasiewicz, S.: Une propri\u00e9t\u00e9 topologique des sous-ensembles analytiques r\u00e9els. Les \u00e9quations aux d\u00e9riv\u00e9es partielles 117, 87\u201389 (1963)","journal-title":"Les \u00e9quations aux d\u00e9riv\u00e9es partielles"},{"key":"9502_CR17","doi-asserted-by":"publisher","first-page":"1575","DOI":"10.5802\/aif.1384","volume":"43","author":"S \u0141ojasiewicz","year":"1993","unstructured":"\u0141ojasiewicz, S.: Sur la g\u00e9om\u00e9trie semi-et sous-analytique. In: Annales de l\u2019institut Fourier, vol.\u00a043, pp. 1575\u20131595 (1993)","journal-title":"Annales de l\u2019institut Fourier"},{"issue":"1","key":"9502_CR18","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/16M1099546","volume":"28","author":"H Lu","year":"2018","unstructured":"Lu, H., Freund, R., Nesterov, Y.: Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization 28(1), 333\u2013354 (2018). https:\/\/doi.org\/10.1137\/16M1099546.","journal-title":"SIAM Journal on Optimization"},{"key":"9502_CR19","unstructured":"Necoara, I., Nesterov, Y., Glineur, F.: Linear convergence of first order methods for non-strongly convex optimization. Mathematical Programming pp. 1\u201339 (2016)"},{"issue":"2","key":"9502_CR20","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0041-5553(85)90100-4","volume":"25","author":"A Nemirovski","year":"1985","unstructured":"Nemirovski, A., Nesterov, Y.: Optimal methods of smooth convex minimization. U.S.S.R. Comput. Math. Math. Phys. 25(2), 21\u201330 (1985)","journal-title":"U.S.S.R. Comput. Math. Math. Phys."},{"key":"9502_CR21","unstructured":"Nemirovski, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley (1983)"},{"issue":"2","key":"9502_CR22","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 Mathematics Doklady 27(2), 372\u2013376 (1983)","journal-title":"Soviet Mathematics Doklady"},{"issue":"1","key":"9502_CR23","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Mathematical programming 103(1), 127\u2013152 (2005)","journal-title":"Mathematical programming"},{"issue":"2","key":"9502_CR24","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10107-006-0001-8","volume":"110","author":"Y Nesterov","year":"2007","unstructured":"Nesterov, Y.: Smoothing technique and its applications in semidefinite optimization. Mathematical Programming 110(2), 245\u2013259 (2007)","journal-title":"Mathematical Programming"},{"issue":"1","key":"9502_CR25","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. Mathematical Programming 140(1), 125\u2013161 (2013)","journal-title":"Mathematical Programming"},{"issue":"1\u20132","key":"9502_CR26","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s10107-014-0790-0","volume":"152","author":"Y Nesterov","year":"2015","unstructured":"Nesterov, Y.: Universal gradient methods for convex optimization problems. Mathematical Programming 152(1-2), 381\u2013404 (2015)","journal-title":"Mathematical Programming"},{"issue":"3","key":"9502_CR27","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/s10208-013-9150-3","volume":"15","author":"B. ODonoghue","year":"2015","unstructured":"ODonoghue, B., Candes, E.: Adaptive restart for accelerated gradient schemes. Foundations of Computational Mathematics 15(3), 715\u2013732 (2015)","journal-title":"Foundations of Computational Mathematics"},{"issue":"4","key":"9502_CR28","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1016\/0041-5553(63)90382-3","volume":"3","author":"B Polyak","year":"1963","unstructured":"Polyak, B.: 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":"9502_CR29","unstructured":"Polyak, B.: Subgradient methods: a survey of Soviet research. In: Nonsmooth optimization: Proceedings of the IIASA workshop, pp. 5\u201330 (1977)"},{"key":"9502_CR30","unstructured":"Polyak, B.: Introduction to optimization. translations series in mathematics and engineering. Optimization Software (1987)"},{"key":"9502_CR31","doi-asserted-by":"publisher","first-page":"2649","DOI":"10.1137\/15M1027371","volume":"26","author":"J Renegar","year":"2016","unstructured":"Renegar, J.: \u201cEfficient\u201d subgradient methods for general convex optimization. SIAM Journal on Optimization 26, 2649\u20132676 (2016)","journal-title":"SIAM Journal on Optimization"},{"key":"9502_CR32","doi-asserted-by":"crossref","unstructured":"Renegar, J.: Accelerated first-order methods for hyperbolic programming. Mathematical Programming pp. 1\u201335 (2017)","DOI":"10.1007\/s10107-017-1203-y"},{"issue":"1","key":"9502_CR33","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1137\/18M1224568","volume":"30","author":"V Roulet","year":"2020","unstructured":"Roulet, V., d\u2019Aspremont, A.: Sharpness, restart, and acceleration. SIAM Journal on Optimization 30(1), 262\u2013289 (2020)","journal-title":"SIAM Journal on Optimization"},{"key":"9502_CR34","doi-asserted-by":"crossref","unstructured":"Shor, N.: Minimization Methods for Non-Differentiable Functions. Springer (1985)","DOI":"10.1007\/978-3-642-82118-9"},{"issue":"1","key":"9502_CR35","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s10107-018-1284-2","volume":"170","author":"M Teboulle","year":"2018","unstructured":"Teboulle, M.: A simplified view of first order methods for optimization. Math. Program. 170(1), 67\u201396 (2018)","journal-title":"Math. Program."},{"key":"9502_CR36","unstructured":"Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. submitted to SIAM Journal on Optimization 2, 3 (2008)"},{"key":"9502_CR37","unstructured":"Yang, T.: Adaptive accelerated gradient converging methods under H\u00f6lderian error bound condition. In: 31st Conference on Neural Information Processing System (2017)"},{"issue":"1","key":"9502_CR38","first-page":"236","volume":"19","author":"T Yang","year":"2018","unstructured":"Yang, T., Lin, Q.: RSG: Beating subgradient method without smoothness and strong convexity. The Journal of Machine Learning Research 19(1), 236\u2013268 (2018)","journal-title":"The Journal of Machine Learning Research"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09502-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-021-09502-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-021-09502-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,4]],"date-time":"2022-02-04T23:19:49Z","timestamp":1644016789000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-021-09502-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,26]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["9502"],"URL":"https:\/\/doi.org\/10.1007\/s10208-021-09502-2","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,26]]},"assertion":[{"value":"30 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 October 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}