{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:42Z","timestamp":1787340222202,"version":"build-2736575974"},"reference-count":69,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-24-1-0076"],"award-info":[{"award-number":["FA9550-24-1-0076"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-22-1-2348"],"award-info":[{"award-number":["N00014-22-1-2348"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012950","name":"Institut national de recherche en informatique et en automatique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012950","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1210362"],"award-info":[{"award-number":["1210362"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Agencia Nacional de Investigacion y Desarrollo","award":["ACT210005"],"award-info":[{"award-number":["ACT210005"]}]},{"name":"Centro Nacional de Inteligencia Artificial","award":["FB210017"],"award-info":[{"award-number":["FB210017"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We initiate the study of nonsmooth optimization problems under bounded local subgradient variation, which postulates bounded difference between (sub)gradients in small local regions around points, in either the average or the maximum sense. The resulting class of objective functions encapsulates the classes of objective functions traditionally studied in the optimization literature, which are defined based on either Lipschitz continuity of the objective or H\u00f6lder\/Lipschitz continuity of the function\u2019s gradient. Further, the defined class is richer in the sense that it contains functions that neither are Lipschitz continuous nor have a H\u00f6lder-continuous gradient. Finally, when restricted to the aforementioned traditional classes of optimization problems, the constants defining the studied classes lead to more fine-grained oracle complexity bounds. Some highlights of our results are that (i) it is possible to obtain complexity results for both convex and nonconvex optimization problems with (local or global) Lipschitz constant being replaced by a constant of local subgradient variation, corresponding to small local regions, and (ii) complexity of the subgradient set around the set of optima\u2014measured by its mean width in a local region around optima\u2014plays a role in the complexity of nonsmooth optimization, particularly in parallel optimization settings. A consequence of (ii) is that for any error parameter [Formula: see text], parallel oracle complexity of nonsmooth Lipschitz convex optimization is lower than its sequential oracle complexity by a factor [Formula: see text] whenever the objective function is piecewise-affine with the number of pieces polynomial in the dimension and [Formula: see text]. This is particularly surprising considering that existing parallel complexity lower bounds are based on such classes of functions. The seeming contradiction is resolved by considering the region in which the algorithm is allowed to query the objective.<\/jats:p>","DOI":"10.1137\/24m1659510","type":"journal-article","created":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T09:00:36Z","timestamp":1771318836000},"page":"152-184","source":"Crossref","is-referenced-by-count":0,"title":["Optimization on a Finer Scale: Bounded Local Subgradient Variation Perspective"],"prefix":"10.1137","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3439-0310","authenticated-orcid":true,"given":"Jelena","family":"Diakonikolas","sequence":"first","affiliation":[{"name":"Department of Computer Sciences, University of Wisconsin-Madison, Madison, WI 53706 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Crist\u00f3bal","family":"Guzm\u00e1n","sequence":"additional","affiliation":[{"name":"Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,2,17]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08114-4"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"E. Balkanski, A. Rubinstein, and Y. Singer, An exponential speedup in parallel running time for submodular maximization without loss in approximation, in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.","DOI":"10.1137\/1.9781611975482.19"},{"key":"ref3","first-page":"1","volume":"31","author":"Ball K.","year":"1997","journal-title":"Flavors Geom."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/100818327"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1017\/9781108755528"},{"key":"ref6","volume":"32","author":"Bubeck S.","year":"2019","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01431-x"},{"key":"ref8","first-page":"19052","volume":"33","author":"Carmon Y.","year":"2020","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref9","unstructured":"Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford, Thinking inside the ball: Near-optimal minimization of the maximal loss, in Proceedings of the Conference on Learning Theory, 2021."},{"key":"ref10","volume":"36","author":"Chakrabarty D.","year":"2023","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"ref12","unstructured":"M. B. Cohen, J. Diakonikolas, and L. Orecchia, On acceleration with noise-corrupted gradients, in Proceedings of the International Conference on Machine Learning (ICML), 2018."},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976748"},{"key":"ref14","unstructured":"A. Cutkosky, H. Mehta, and F. Orabona, Optimal stochastic non-smooth non-convex optimization through online-to-non-convex conversion, in Proceedings of the International Conference on Machine Learning, 2023."},{"key":"ref15","doi-asserted-by":"crossref","first-page":"6692","DOI":"10.52202\/068431-0485","volume":"35","author":"Davis D.","year":"2022","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-024-09653-y"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0677-5"},{"key":"ref18","first-page":"153","volume":"21","author":"Diakonikolas J.","year":"2020","journal-title":"J. Mach. Learn. Res."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/18M1172314"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/110831659"},{"key":"ref21","unstructured":"A. D. Flaxman, A. T. Kalai, and H. B. McMahan, Online convex optimization in the bandit setting: Gradient descent without a gradient, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 385\u2013394."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1134\/S0965542518010050"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/110848864"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/17M1122980"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/18M117306X"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-023-02060-2"},{"key":"ref27","unstructured":"V. Guigues, J. Liang, and R. D. C. Monteiro, Universal Subgradient and Proximal Bundle Methods for Convex and Strongly Convex Hybrid Composite Optimization, https:\/\/arxiv.org\/abs\/2407.10073, 2024."},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"O. G\u00fcler, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29 (1991), pp. 403\u2013419, https:\/\/doi.org\/10.1137\/0329022.","DOI":"10.1137\/0329022"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2014.08.003"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/0802032"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/21M1468450"},{"key":"ref32","volume":"28","author":"Hazan E.","year":"2015","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-11370-4"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160140317"},{"key":"ref35","unstructured":"M. Jordan, G. Kornowski, T. Lin, O. Shamir, and M. Zampetakis, Deterministic nonsmooth nonconvex optimization, in Proceedings of the Conference on Learning Theory, 2023, pp. 4570\u20134597."},{"key":"ref36","series-title":"Math. Oper. Res.","volume-title":"The cost of nonconvexity in deterministic nonsmooth optimization","volume":"49","author":"Kong S.","year":"2023"},{"key":"ref37","first-page":"14161","volume":"23","author":"Kornowski G.","year":"2022","journal-title":"J. Mach. Learn. Res."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/060662228"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0737-x"},{"key":"ref40","unstructured":"C. Lemarechal, Nonsmooth Optimization and Descent Methods, IIASA Research Report RR-78-004,\u00a0IIASA, Laxenburg, Austria, 1978."},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-025-02250-z"},{"key":"ref42","unstructured":"J. Liang, R. D. C. Monteiro, and H. Zhang, Proximal Bundle Methods for Hybrid Weakly Convex Composite Optimization Problems, https:\/\/arxiv.org\/abs\/2303.14896, 2024."},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1287\/ijoo.2018.0008"},{"key":"ref44","unstructured":"Y. Malitsky and K. Mishchenko, Adaptive gradient descent without descent, in\u00a0Proceedings of the 37th International Conference on Machine Learning (ICML), Proc. Mach. Learn. Res. 119, 2020."},{"key":"ref45","first-page":"154","volume":"4","author":"Martinet B.","year":"1970","journal-title":"R.I.R.O."},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1625"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1025"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"ref49","first-page":"356","volume":"25","author":"Nemirovskii A.","year":"1985","journal-title":"Zh. Vychisl. Mat. Mat. Fiz."},{"key":"ref50","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovskii A.","year":"1983"},{"key":"ref51","doi-asserted-by":"crossref","unstructured":"Y. Nesterov, Minimizing Functions with Bounded Variation of Subgradients, Technical report, CORE Discussion Papers, 2005.","DOI":"10.2139\/ssrn.885880"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0790-0"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-015-9296-2"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-81241-5_10"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.34229\/2707-451X.20.1.1"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614322"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/BF01498415"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1137\/15M1027371"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1137\/0314056"},{"key":"ref61","series-title":"Springer Ser. Comput. Math.","volume-title":"Minimization Methods for Non-differentiable Functions","volume":"3","author":"Shor N. Z.","year":"2012"},{"key":"ref62","volume-title":"Harmonic analysis: Real-Variable Methods, Orthogonality, and Oscillatory Integrals","volume":"3","author":"Stein E. M.","year":"1993"},{"key":"ref63","first-page":"97","volume":"10","author":"Steklov V.","year":"1907","journal-title":"Comm. Charkov Math. Soc."},{"key":"ref64","unstructured":"A. B. Taylor, Convex Interpolation and Performance Estimation of First-Order Methods for Convex Optimization, Ph.D. thesis, Catholic University of Louvain, Louvain-la-Neuve, Belgium, 2017."},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"ref66","first-page":"133","author":"Wiegerinck J.","year":"1997","journal-title":"Encyclopaedia of Mathematics Supplement Volume I"},{"key":"ref67","volume":"31","author":"Woodworth B. E.","year":"2018","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref68","doi-asserted-by":"crossref","unstructured":"F. Yousefian, A. Nedi\u0107, and U. V. Shanbhag, Convex nondifferentiable stochastic optimization: A local randomized smoothing technique, in Proceedings of the American Control Conference, 2010.","DOI":"10.1109\/ACC.2010.5530908"},{"key":"ref69","unstructured":"J. Zhang, H. Lin, S. Jegelka, S. Sra, and A. Jadbabaie, Complexity of finding stationary points of nonconvex nonsmooth functions, in Proceedings of the International Conference on Machine Learning, 2020, pp. 11173\u201311182."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1659510","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:35Z","timestamp":1787336735000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1659510"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,17]]},"references-count":69,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1137\/24M1659510"],"URL":"https:\/\/doi.org\/10.1137\/24m1659510","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,17]]}}}