{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T07:02:13Z","timestamp":1773385333648,"version":"3.50.1"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,1,6]],"date-time":"2024-01-06T00:00:00Z","timestamp":1704499200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,6]],"date-time":"2024-01-06T00:00:00Z","timestamp":1704499200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Hong Kong Research Grants Council (RGC) General Research Fund","award":["CUHK 14216122"],"award-info":[{"award-number":["CUHK 14216122"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,11]]},"DOI":"10.1007\/s10107-023-02031-6","type":"journal-article","created":{"date-parts":[[2024,1,6]],"date-time":"2024-01-06T11:02:33Z","timestamp":1704538953000},"page":"51-74","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["No dimension-free deterministic algorithm computes approximate stationarities of Lipschitzians"],"prefix":"10.1007","volume":"208","author":[{"given":"Lai","family":"Tian","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2588-7851","authenticated-orcid":false,"given":"Anthony Man-Cho","family":"So","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,1,6]]},"reference":[{"key":"2031_CR1","unstructured":"Arora, R., Basu, A., Mianjy, P., Mukherjee, A.: Understanding deep neural networks with rectified linear units. In: International Conference on Learning Representations (2018)"},{"issue":"1","key":"2031_CR2","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1137\/S0363012904439301","volume":"44","author":"M Bena\u00efm","year":"2005","unstructured":"Bena\u00efm, M., Hofbauer, J., Sorin, S.: Stochastic approximations and differential inclusions. SIAM J. Control Optim. 44(1), 328\u2013348 (2005)","journal-title":"SIAM J. Control Optim."},{"key":"2031_CR3","volume-title":"Set Theory and Abstract Algebra","author":"TS Blyth","year":"1975","unstructured":"Blyth, T.S.: Set Theory and Abstract Algebra. Longman Publishing Group, New York (1975)"},{"key":"2031_CR4","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2014.06.006","volume":"554","author":"HJ B\u00f6ckenhauer","year":"2014","unstructured":"B\u00f6ckenhauer, H.J., Hromkovi\u010d, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci. 554, 95\u2013108 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"2031_CR5","doi-asserted-by":"publisher","first-page":"4709","DOI":"10.1109\/TIT.2017.2701343","volume":"63","author":"G Braun","year":"2017","unstructured":"Braun, G., Guzm\u00e1n, C., Pokutta, S.: Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory. IEEE Trans. Inf. Theory 63(7), 4709\u20134724 (2017)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"2031_CR6","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-030-34910-3_6","volume-title":"Numerical Nonsmooth Optimization: State of the Art Algorithms","author":"JV Burke","year":"2020","unstructured":"Burke, J.V., Curtis, F.E., Lewis, A.S., Overton, M.L., Sim\u00f5es, L.E.: Gradient sampling methods for nonsmooth optimization. In: Numerical Nonsmooth Optimization: State of the Art Algorithms, pp. 201\u2013225. Springer, Cham (2020)"},{"issue":"3","key":"2031_CR7","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/030601296","volume":"15","author":"JV Burke","year":"2005","unstructured":"Burke, J.V., Lewis, A.S., Overton, M.L.: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Optim. 15(3), 751\u2013779 (2005)","journal-title":"SIAM J. Optim."},{"key":"2031_CR8","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: \u201cConvex until proven guilty\u201d: dimension-free acceleration of gradient descent on non-convex functions. In: Proceedings of the 34th International Conference on Machine Learning, pp. 654\u2013663 (2017)"},{"issue":"1\u20132","key":"2031_CR9","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-019-01406-y","volume":"184","author":"Y Carmon","year":"2020","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points I. Math. Program. 184(1\u20132), 71\u2013120 (2020)","journal-title":"Math. Program."},{"issue":"1","key":"2031_CR10","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10107-019-01431-x","volume":"185","author":"Y Carmon","year":"2021","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points II: first-order methods. Math. Program. 185(1), 315\u2013355 (2021)","journal-title":"Math. Program."},{"issue":"6","key":"2031_CR11","doi-asserted-by":"publisher","first-page":"2833","DOI":"10.1137\/090774100","volume":"20","author":"C Cartis","year":"2010","unstructured":"Cartis, C., Gould, N.I.M., Toint, P.L.: On the complexity of steepest descent, Newton\u2019s and regularized Newton\u2019s methods for nonconvex unconstrained optimization problems. SIAM J. Optim. 20(6), 2833\u20132852 (2010)","journal-title":"SIAM J. Optim."},{"key":"2031_CR12","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971309","volume-title":"Optimization and Nonsmooth Analysis","author":"FH Clarke","year":"1990","unstructured":"Clarke, F.H.: Optimization and Nonsmooth Analysis. SIAM, Philadelphia (1990)"},{"key":"2031_CR13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719857","volume-title":"Trust Region Methods","author":"AR Conn","year":"2000","unstructured":"Conn, A.R., Gould, N.I., Toint, P.L.: Trust Region Methods. SIAM, Philadelphia (2000)"},{"key":"2031_CR14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976748","volume-title":"Modern Nonconvex Nondifferentiable Optimization","author":"Y Cui","year":"2021","unstructured":"Cui, Y., Pang, J.S.: Modern Nonconvex Nondifferentiable Optimization. SIAM, Philadelphia (2021)"},{"issue":"2","key":"2031_CR15","doi-asserted-by":"publisher","first-page":"1327","DOI":"10.1137\/19M1298147","volume":"30","author":"A Daniilidis","year":"2020","unstructured":"Daniilidis, A., Drusvyatskiy, D.: Pathological subgradient dynamics. SIAM J. Optim. 30(2), 1327\u20131338 (2020)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2031_CR16","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. Optim. 29(1), 207\u2013239 (2019)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2031_CR17","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s10208-018-09409-5","volume":"20","author":"D Davis","year":"2020","unstructured":"Davis, D., Drusvyatskiy, D., Kakade, S., Lee, J.D.: Stochastic subgradient method converges on tame functions. Found. Comput. Math. 20(1), 119\u2013154 (2020)","journal-title":"Found. Comput. Math."},{"key":"2031_CR18","unstructured":"Davis, D., Drusvyatskiy, D., Lee, Y.T., Padmanabhan, S., Ye, G.: A gradient sampling method with complexity guarantees for Lipschitz functions in high and low dimensions. In: Advances in Neural Information Processing Systems, vol.\u00a035, pp. 6692\u20136703 (2022)"},{"issue":"3","key":"2031_CR19","doi-asserted-by":"publisher","first-page":"1908","DOI":"10.1137\/17M1151031","volume":"29","author":"D Davis","year":"2019","unstructured":"Davis, D., Grimmer, B.: Proximally guided stochastic subgradient method for nonsmooth, nonconvex problems. SIAM J. Optim. 29(3), 1908\u20131930 (2019)","journal-title":"SIAM J. Optim."},{"key":"2031_CR20","first-page":"123","volume":"44","author":"M Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A.: Computing the volume of convex bodies: a case where randomness provably helps. Probab. Comb. Appl. 44, 123\u2013170 (1991)","journal-title":"Probab. Comb. Appl."},{"issue":"1","key":"2031_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM 38(1), 1\u201317 (1991)","journal-title":"J. ACM"},{"issue":"4","key":"2031_CR22","doi-asserted-by":"publisher","first-page":"2341","DOI":"10.1137\/120880811","volume":"23","author":"S Ghadimi","year":"2013","unstructured":"Ghadimi, S., Lan, G.: Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM J. Optim. 23(4), 2341\u20132368 (2013)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2031_CR23","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/BF01584320","volume":"13","author":"A Goldstein","year":"1977","unstructured":"Goldstein, A.: Optimization of Lipschitz continuous functions. Math. Program. 13(1), 14\u201322 (1977)","journal-title":"Math. Program."},{"issue":"1","key":"2031_CR24","first-page":"35","volume":"2","author":"WW Hager","year":"2006","unstructured":"Hager, W.W., Zhang, H.: A survey of nonlinear conjugate gradient methods. Pac. J. Optim. 2(1), 35\u201358 (2006)","journal-title":"Pac. J. Optim."},{"key":"2031_CR25","volume-title":"Fundamentals of Convex Analysis","author":"JB Hiriart-Urruty","year":"2004","unstructured":"Hiriart-Urruty, J.B., Lemar\u00e9chal, C.: Fundamentals of Convex Analysis. Springer Science & Business Media, Berlin (2004)"},{"issue":"2","key":"2031_CR26","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/3418526","volume":"68","author":"C Jin","year":"2021","unstructured":"Jin, C., Netrapalli, P., Ge, R., Kakade, S.M., Jordan, M.I.: On nonconvex optimization for machine learning: gradients, stochasticity, and saddle points. J. ACM 68(2), 11 (2021)","journal-title":"J. ACM"},{"key":"2031_CR27","unstructured":"Jordan, M., Kornowski, G., Lin, T., Shamir, O., Zampetakis, M.: Deterministic nonsmooth nonconvex optimization. In: Proceedings of the 36th Conference on Learning Theory, pp. 4570\u20134597 (2023)"},{"key":"2031_CR28","unstructured":"Kakade, S.M., Lee, J.D.: Provably correct automatic subdifferentiation for qualified programs. In: Advances in Neural Information Processing Systems, vol. 31, pp. 7125\u20137135 (2018)"},{"issue":"2","key":"2031_CR29","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1137\/050639673","volume":"18","author":"KC Kiwiel","year":"2007","unstructured":"Kiwiel, K.C.: Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 18(2), 379\u2013388 (2007)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"2031_CR30","doi-asserted-by":"publisher","first-page":"1983","DOI":"10.1137\/090748408","volume":"20","author":"KC Kiwiel","year":"2010","unstructured":"Kiwiel, K.C.: A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 20(4), 1983\u20131994 (2010)","journal-title":"SIAM J. Optim."},{"key":"2031_CR31","doi-asserted-by":"crossref","unstructured":"Kong, S., Lewis, A.: The cost of nonconvexity in deterministic nonsmooth optimization. arXiv preprint arXiv:2210.00652 (2022)","DOI":"10.1287\/moor.2022.0289"},{"key":"2031_CR32","unstructured":"Kornowski, G., Shamir, O.: On the complexity of finding small subgradients in nonsmooth optimization. arXiv preprint arXiv:2209.10346 (2022)"},{"issue":"314","key":"2031_CR33","first-page":"1","volume":"23","author":"G Kornowski","year":"2022","unstructured":"Kornowski, G., Shamir, O.: Oracle complexity in nonsmooth nonconvex optimization. J. Mach. Learn. Res. 23(314), 1\u201344 (2022)","journal-title":"J. Mach. Learn. Res."},{"issue":"5","key":"2031_CR34","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/MSP.2020.3003845","volume":"37","author":"J Li","year":"2020","unstructured":"Li, J., So, A.M.C., Ma, W.K.: Understanding notions of stationarity in nonsmooth optimization: a guided tour of various constructions of subdifferential for nonsmooth functions. IEEE Signal Process. Mag. 37(5), 18\u201331 (2020)","journal-title":"IEEE Signal Process. Mag."},{"issue":"1","key":"2031_CR35","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/BF01589116","volume":"45","author":"DC Liu","year":"1989","unstructured":"Liu, D.C., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45(1), 503\u2013528 (1989)","journal-title":"Math. Program."},{"key":"2031_CR36","unstructured":"Majewski, S., Miasojedow, B., Moulines, E.: Analysis of nonsmooth stochastic approximation: the differential inclusion approach. arXiv preprint arXiv:1805.01916 (2018)"},{"key":"2031_CR37","doi-asserted-by":"crossref","unstructured":"Metel, M.R., Takeda, A.: Perturbed iterate SGD for Lipschitz continuous loss functions. J. Optim. Theory Appl. 195(2), 504\u2013547 (2022)","DOI":"10.1007\/s10957-022-02093-0"},{"key":"2031_CR38","volume-title":"Topology","author":"JR Munkres","year":"2000","unstructured":"Munkres, J.R.: Topology. Pearson Prentice Hall, Hoboken (2000)"},{"key":"2031_CR39","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"AS Nemirovskij","year":"1983","unstructured":"Nemirovskij, A.S., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience, Hoboken (1983)"},{"key":"2031_CR40","first-page":"543","volume":"269","author":"Yu Nesterov","year":"1983","unstructured":"Nesterov, Yu.: A method of solving a convex programming problem with convergence rate O$$(1\/k^2)$$. Dokl. Akad. Nauk 269, 543\u2013547 (1983)","journal-title":"Dokl. Akad. Nauk"},{"key":"2031_CR41","first-page":"10","volume":"88","author":"Yu Nesterov","year":"2012","unstructured":"Nesterov, Yu.: How to make the gradients small. Optima 88, 10\u201311 (2012)","journal-title":"Optima"},{"key":"2031_CR42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on Convex Optimization","author":"Yu Nesterov","year":"2018","unstructured":"Nesterov, Yu.: Lectures on Convex Optimization. Springer, Berlin (2018)"},{"issue":"1","key":"2031_CR43","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10107-006-0706-8","volume":"108","author":"Yu Nesterov","year":"2006","unstructured":"Nesterov, Yu., Polyak, B.T.: Cubic regularization of Newton method and its global performance. Math. Program. 108(1), 177\u2013205 (2006)","journal-title":"Math. Program."},{"key":"2031_CR44","volume-title":"Variational Analysis","author":"RT Rockafellar","year":"2009","unstructured":"Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer Science & Business Media, Berlin (2009)"},{"key":"2031_CR45","unstructured":"Tian, L., So, A.M.C.: On the hardness of computing near-approximate stationary points of Clarke regular nonsmooth nonconvex problems and certain DC programs. In: ICML Workshop on Beyond First-Order Methods in ML Systems (2021)"},{"key":"2031_CR46","unstructured":"Tian, L., Zhou, K., So, A.M.C.: On the finite-time complexity and practical computation of approximate stationarity concepts of Lipschitz functions. In: Proceedings of the 39th International Conference on Machine Learning, pp. 21360\u201321379 (2022)"},{"issue":"1","key":"2031_CR47","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/0803004","volume":"3","author":"SA Vavasis","year":"1993","unstructured":"Vavasis, S.A.: Black-box complexity of local minimization. SIAM J. Optim. 3(1), 60\u201380 (1993)","journal-title":"SIAM J. Optim."},{"key":"2031_CR48","unstructured":"Woodworth, B., Srebro, N.: Tight complexity bounds for optimizing composite objectives. In: Advances in Neural Information Processing Systems, vol.\u00a029, pp. 3646\u20133654 (2016)"},{"key":"2031_CR49","unstructured":"Zhang, J., Lin, H., Jegelka, S., Jadbabaie, A., Sra, S.: Complexity of finding stationary points of nonsmooth nonconvex functions. In: Proceedings of the 37th International Conference on Machine Learning, pp. 11173\u201311182 (2020)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02031-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02031-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02031-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T16:08:19Z","timestamp":1729008499000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02031-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,6]]},"references-count":49,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["2031"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02031-6","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,6]]},"assertion":[{"value":"18 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}