{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:59:03Z","timestamp":1762102743622,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T00:00:00Z","timestamp":1655164800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T00:00:00Z","timestamp":1655164800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"european research council","doi-asserted-by":"publisher","award":["Advanced Grant 788368"],"award-info":[{"award-number":["Advanced Grant 788368"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex minimization problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of the standard Subgradient and Ellipsoid methods. However, in contrast to the latter one, the proposed method has a reasonable convergence rate even when the dimensionality of the problem is sufficiently large. For generating accuracy certificates in our algorithm, we propose an efficient technique, which ameliorates the previously known recipes (Nemirovski in Math Oper Res 35(1):52\u201378, 2010).<\/jats:p>","DOI":"10.1007\/s10107-022-01833-4","type":"journal-article","created":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T14:10:50Z","timestamp":1655215850000},"page":"305-341","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Subgradient ellipsoid method for nonsmooth convex problems"],"prefix":"10.1007","volume":"199","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9656-8554","authenticated-orcid":false,"given":"Anton","family":"Rodomanov","sequence":"first","affiliation":[]},{"given":"Yurii","family":"Nesterov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,14]]},"reference":[{"issue":"2","key":"1833_CR1","first-page":"67","volume":"7","author":"A Auslender","year":"1973","unstructured":"Auslender, A.: R\u00e9solution num\u00e9rique d\u2019in\u00e9galit\u00e9s variationnelles. RAIRO 7(2), 67\u201372 (1973)","journal-title":"RAIRO"},{"unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization. Lecture notes (2021)","key":"1833_CR2"},{"issue":"6","key":"1833_CR3","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1287\/opre.29.6.1039","volume":"29","author":"R Bland","year":"1981","unstructured":"Bland, R., Goldfarb, D., Todd, M.: The ellipsoid method: a survey. Oper. Res. 29(6), 1039\u20131091 (1981)","journal-title":"Oper. Res."},{"unstructured":"Bubeck, S., Lee, Y.T.: Black-box optimization with a politician. In: International Conference on Machine Learning, pp. 1624\u20131631. PMLR (2016)","key":"1833_CR4"},{"unstructured":"Bubeck, S., Lee, Y.T., Singh, M.: A geometric alternative to Nesterov\u2019s accelerated gradient descent. arXiv preprint arXiv:1506.08187 (2015)","key":"1833_CR5"},{"unstructured":"Bulatov, V., Shepot\u2019ko, L.: Method of centers of orthogonal simplexes for solving convex programming problems. Methods Optim. Appl. (1982)","key":"1833_CR6"},{"unstructured":"Duchi, J., Hazan, E., Singer, Y.: Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res. 12(7) (2011)","key":"1833_CR7"},{"issue":"1","key":"1833_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s10957-016-0999-6","volume":"171","author":"P Dvurechensky","year":"2016","unstructured":"Dvurechensky, P., Gasnikov, A.: Stochastic intermediate gradient method for convex problems with stochastic inexact oracle. J. Optim. Theory Appl. 171(1), 121\u2013145 (2016)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"1833_CR9","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"issue":"5","key":"1833_CR10","first-page":"1093","volume":"244","author":"L Khachiyan","year":"1979","unstructured":"Khachiyan, L.: A polynomial algorithm in linear programming. Soviet Math. Dokl. 244(5), 1093\u20131096 (1979)","journal-title":"Soviet Math. Dokl."},{"issue":"1","key":"1833_CR11","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10107-010-0434-y","volume":"133","author":"G Lan","year":"2012","unstructured":"Lan, G.: An optimal method for stochastic composite optimization. Math. Program. 133(1), 365\u2013397 (2012)","journal-title":"Math. Program."},{"key":"1833_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39568-1","volume-title":"First-Order and Stochastic Optimization Methods for Machine Learning","author":"G Lan","year":"2020","unstructured":"Lan, G.: First-Order and Stochastic Optimization Methods for Machine Learning. Springer, Switzerland (2020)"},{"issue":"6","key":"1833_CR13","first-page":"1244","volume":"160","author":"A Levin","year":"1965","unstructured":"Levin, A.: An algorithm for minimizing convex functions. Soviet Math. Dokl. 160(6), 1244\u20131247 (1965)","journal-title":"Soviet Math. Dokl."},{"unstructured":"Nemirovski, A.: Information-based complexity of convex programming. Lecture notes (1995)","key":"1833_CR14"},{"issue":"4","key":"1833_CR15","doi-asserted-by":"publisher","first-page":"1574","DOI":"10.1137\/070704277","volume":"19","author":"A Nemirovski","year":"2009","unstructured":"Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4), 1574\u20131609 (2009)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1833_CR16","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1287\/moor.1090.0427","volume":"35","author":"A Nemirovski","year":"2010","unstructured":"Nemirovski, A., Onn, S., Rothblum, U.G.: Accuracy certificates for computational problems with convex structure. Math. Oper. Res. 35(1), 52\u201378 (2010)","journal-title":"Math. Oper. Res."},{"key":"1833_CR17","first-page":"543","volume":"269","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method for solving the convex programming problem with convergence rate $$O(1\/k^2)$$. Soviet Math. Dokl. 269, 543\u2013547 (1983)","journal-title":"Soviet Math. Dokl."},{"issue":"1","key":"1833_CR18","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s10107-007-0149-x","volume":"120","author":"Y Nesterov","year":"2009","unstructured":"Nesterov, Y.: Primal-dual subgradient methods for convex problems. Math. Program. 120(1), 221\u2013259 (2009)","journal-title":"Math. Program."},{"key":"1833_CR19","doi-asserted-by":"publisher","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. Springer, Berlin (2018)"},{"issue":"3","key":"1833_CR20","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/321281.321291","volume":"12","author":"D Newman","year":"1965","unstructured":"Newman, D.: Location of the maximum on unimodal surfaces. J. ACM (JACM) 12(3), 395\u2013398 (1965)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"1833_CR21","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/BF01071394","volume":"13","author":"N Shor","year":"1977","unstructured":"Shor, N.: Cut-off method with space extension in convex programming problems. Cybernetics 13(1), 94\u201396 (1977)","journal-title":"Cybernetics"},{"issue":"1","key":"1833_CR22","first-page":"226","volume":"37","author":"S Tarasov","year":"1988","unstructured":"Tarasov, S., Khachiyan, L., Erlikh, I.: The method of inscribed ellipsoids. Soviet Math. Dokl. 37(1), 226\u2013230 (1988)","journal-title":"Soviet Math. Dokl."},{"issue":"2","key":"1833_CR23","first-page":"22","volume":"13","author":"D Yudin","year":"1976","unstructured":"Yudin, D., Nemirovskii, A.: Informational complexity and efficient methods for the solution of convex extremal problems. Matekon 13(2), 22\u201345 (1976)","journal-title":"Matekon"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01833-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01833-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01833-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T17:30:34Z","timestamp":1682098234000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01833-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,14]]},"references-count":23,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1833"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01833-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2022,6,14]]},"assertion":[{"value":"25 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}