{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:44:37Z","timestamp":1787341477339,"version":"3.56.0"},"reference-count":60,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE-1650441"],"award-info":[{"award-number":["DGE-1650441"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We study convergence rates of the classic proximal bundle method for a variety of nonsmooth convex optimization problems. We show that, without any modification, this algorithm adapts to converge faster in the presence of smoothness or a H\u00f6lder growth condition. Our analysis reveals that with a constant stepsize, the bundle method is adaptive, yet it exhibits suboptimal convergence rates. We overcome this shortcoming by proposing nonconstant stepsize schemes with optimal rates. These schemes use function information such as growth constants, which might be prohibitive in practice. We provide a parallelizable variant of the bundle method that can be applied without prior knowledge of function parameters while maintaining near-optimal rates. The practical impact of this scheme is limited since we incur a (parallelizable) log factor in the complexity. These results improve on the scarce existing convergence rates and provide a unified analysis approach across problem settings and algorithmic details. Numerical experiments support our findings.<\/jats:p>","DOI":"10.1137\/21m1428601","type":"journal-article","created":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T09:39:41Z","timestamp":1684402781000},"page":"424-454","source":"Crossref","is-referenced-by-count":17,"title":["Optimal Convergence Rates for the Proximal Bundle Method"],"prefix":"10.1137","volume":"33","author":[{"given":"Mateo","family":"D\u00edaz","sequence":"first","affiliation":[{"name":"Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA 91125 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7003-8448","authenticated-orcid":true,"given":"Benjamin","family":"Grimmer","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD 21218 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,5,17]]},"reference":[{"key":"ref1","unstructured":"LIBSVM data: Classification (Binary class), https:\/\/www.csie.ntu.edu.tw\/\u223ccjlin\/libsvmtools\/datasets\/binary.html (2021)."},{"key":"ref2","first-page":"641","volume":"16","author":"Apkarian P.","year":"2009","journal-title":"J. Convex Anal."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585756"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/0331063"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582063"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-020-09490-9"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585170"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/18M1178244"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2017.10.010"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-019-00755-4"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0809-6"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0873-6"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34910-3_12"},{"key":"ref14","unstructured":"M. D\u00edaz  and \nB. Grimmer , Optimal Convergence Rates for the Proximal Bundle Method, preprint, arXiv:2105.07874, 2021."},{"key":"ref15","unstructured":"L. Ding  and \nB. Grimmer , Revisit of Spectral Bundle Methods: Primal-dual (Sub)linear Convergence Rates, preprint, arXiv:2008.07067, 2020."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01432-w"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-017-1108-1"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/120865987"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"A. Frangioni , Standard bundle methods: Untrusted models and duality, in Numerical Nonsmooth Optimization\u2014State of the Art Algorithms, Springer, Cham, 2020, pp. 61\u2013116, https:\/\/doi.org\/10.1007\/978-3-030-34910-3_3.","DOI":"10.1007\/978-3-030-34910-3_3"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/090754595"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-015-9762-4"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497328987"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-06409-2"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01414-y"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/17M1148189"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591907"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.185"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0074500"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585731"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585554"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004689609425"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/040603929"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0737-x"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"C. Lemarechal , An extension of Davidon methods to nondifferentiable problems, Springer, Berlin, Heidelberg, 1975, pp. 95\u2013109, https:\/\/doi.org\/10.1007\/BFb0120700.","DOI":"10.1007\/BFb0120700"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45586-8_4"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585555"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614390"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"J. Liang  and \nR. D. C. Monteiro , A Proximal Bundle Variant with Optimal Iteration-complexity for a Large Range of Prox Stepsizes, arXiv:2003.11457, 2021.","DOI":"10.1137\/20M1327513"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-017-0565-2"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-018-0490-6"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2.2.191"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120960"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0630-3"},{"key":"ref44","first-page":"291","author":"Mifflin R.","year":"2012","journal-title":"Doc. Math."},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.21105\/joss.00615"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-019-00115-8"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-020-00939-3"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2020.1858831"},{"key":"ref50","volume-title":"Springer Ser. Oper. Res. Financ. Eng.","author":"Nocedal J.","year":"2006","edition":"2"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-018-01452-0"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011388"},{"key":"ref53","volume-title":"Introduction to Optimization, Optimization Software","author":"Polyak B. T.","year":"1987"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-021-09502-2"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1515\/9781400841059"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0570-7"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1137\/040603875"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0420-4"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOTA.0000005046.70410.02"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120703"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1428601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:22:36Z","timestamp":1787340156000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1428601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,17]]},"references-count":60,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1137\/21M1428601"],"URL":"https:\/\/doi.org\/10.1137\/21m1428601","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,17]]}}}