{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:52Z","timestamp":1787341432576,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001961","name":"AXA Research Fund","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001961","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100010663","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":["11160939"],"award-info":[{"award-number":["11160939"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We formulate an affine-invariant implementation of the accelerated first-order algorithm in [Y. Nesterov, Dokl. Math., 27 (1983), pp. 372--376]. Its complexity bound is proportional to an affine-invariant regularity constant defined with respect to the Minkowski gauge of the feasible set. We extend these results to more general problems, optimizing H\u00f6lder smooth functions using $p$-uniformly convex prox terms, and derive an algorithm whose complexity better fits the geometry of the feasible set and adapts to both the best H\u00f6lder smoothness parameter and the best gradient Lipschitz constant. Finally, we detail matching complexity lower bounds when the feasible set is an $\\ell_p$ ball. In this setting, our upper bounds on iteration complexity for the algorithm in [Y. Nesterov, Dokl. Math., 27 (1983), pp. 372--376] are thus optimal in terms of target precision, smoothness, and problem dimension.<\/jats:p>","DOI":"10.1137\/17m1116842","type":"journal-article","created":{"date-parts":[[2018,8,23]],"date-time":"2018-08-23T12:31:16Z","timestamp":1535027476000},"page":"2384-2405","source":"Crossref","is-referenced-by-count":6,"title":["Optimal Affine-Invariant Smooth Minimization Algorithms"],"prefix":"10.1137","volume":"28","author":[{"given":"Alexandre","family":"d'Aspremont","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Crist\u00f3bal","family":"Guzm\u00e1n","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Jaggi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,23]]},"reference":[{"key":"atypb1","unstructured":"Z. Allen-Zhu and L. Orecchia,\n                      Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent\n                      , preprint,https:\/\/arxiv.org\/abs\/1407.1537, 2014."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01231769"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/0803026"},{"key":"atypb5","unstructured":"O. Devolder, F. Glineur, and Y. Nesterov,\n                      First-Order Methods of Smooth Convex Optimization with Inexact Oracle\n                      , CORE discussion paper 2011\/2, ECORE, Brussels, 2011."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"atypb7","unstructured":"M. Grant, S. Boyd, and Y. Ye,\n                      CVX: Matlab Software for Disciplined Convex Programming\n                      ,http:\/\/cvxr.com\/cvx, 2001."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2014.08.003"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"J.B. Hiriart-Urruty and C. Lemare\u0301chal,\n                      Convex Analysis and Minimization Algorithms u\u0306shape I\n                      , Grundlehren Math. Wiss. 305, Springer, Berlin, 1993.","DOI":"10.1007\/978-3-662-02796-7"},{"key":"atypb10","unstructured":"A. Juditsky and A. Nemirovski,\n                      Large Deviations of Vector-Valued Martingales in $2$-Smooth Normed Spaces\n                      , preprint,https:\/\/arxiv.org\/abs\/0809.0813, 2008."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(85)90100-4"},{"key":"atypb12","unstructured":"A. S. Nemirovski\\v\\i and D. B. Yudin,\n                      Problem Complexity and Method Efficiency in Optimization\n                      , Nauka, Moscow, 1979 (in Russian)."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"atypb14","first-page":"372","volume":"27","author":"Nesterov Y.","year":"1983","journal-title":"Dokl. Math."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Introductory Lectures on Convex Optimization: A Basic Course\n                      , Appl. Optim. 87, Springer, Boston, MA, 2003.","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0552-5"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0790-0"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Y. Nesterov and A. Nemirovskii,\n                      Interior-Point Polynomial Algorithms in Convex Programming\n                      , Stud. Appl. Numer. Math. 13, SIAM, Philadelphia, PA, 1994.","DOI":"10.1137\/1.9781611970791"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760337"},{"key":"atypb20","first-page":"2645","author":"Srebro N.","year":"2011","journal-title":"NY"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1116842","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:20Z","timestamp":1787339960000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1116842"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1116842"],"URL":"https:\/\/doi.org\/10.1137\/17m1116842","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}