{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T13:43:23Z","timestamp":1790257403026,"version":"4.1.0"},"reference-count":48,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"DeepMind Graduate Scholarship"},{"DOI":"10.13039\/100006754","name":"Army Research Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006754","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100011102","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["617071"],"award-info":[{"award-number":["617071"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["PGSD3-460176-2014"],"award-info":[{"award-number":["PGSD3-460176-2014"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009941","name":"Ministry of Defence","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100009941","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/R013616\/1"],"award-info":[{"award-number":["EP\/R013616\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000635","name":"Institute for Advanced Studies in the Humanities, University of Edinburgh","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000635","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>The conditions of relative smoothness and relative strong convexity were recently introduced for the analysis of Bregman gradient methods for convex optimization. We introduce a generalized left-preconditioning method for gradient descent and show that its convergence on an essentially smooth convex objective function can be guaranteed via an application of relative smoothness in the dual space. Our relative smoothness assumption is between the designed preconditioner and the convex conjugate of the objective, and it generalizes the typical Lipschitz gradient assumption. Under dual relative strong convexity, we obtain linear convergence with a generalized condition number that is invariant under horizontal translations, distinguishing it from Bregman gradient methods. Thus, in principle our method is capable of improving the conditioning of gradient descent on problems with a non-Lipschitz gradient or nonstrongly convex structure. We demonstrate our method on $p$-norm regression and exponential penalty function minimization.<\/jats:p>","DOI":"10.1137\/19m130858x","type":"journal-article","created":{"date-parts":[[2021,3,30]],"date-time":"2021-03-30T14:09:42Z","timestamp":1617113382000},"page":"991-1016","source":"Crossref","is-referenced-by-count":13,"title":["Dual Space Preconditioning for Gradient Descent"],"prefix":"10.1137","volume":"31","author":[{"given":"Chris J.","family":"Maddison","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Paulin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yee Whye","family":"Teh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arnaud","family":"Doucet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,3,30]]},"reference":[{"key":"atypb1","first-page":"1405","author":"Adil D.","year":"2019","journal-title":"Philadelphia"},{"key":"atypb2","first-page":"14189","author":"Adil D.","year":"2019","journal-title":"Proceedings of Advances in Neural Information Processing Systems"},{"key":"atypb3","first-page":"892","author":"Adil D.","year":"2020","journal-title":"SIAM"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.1.43"},{"key":"atypb6","first-page":"1705","volume":"6","author":"Banerjee A.","year":"2005","journal-title":"J. Mach. Learn. Res."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0817"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00231-6"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2013.10.007"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.2002.7176"},{"key":"atypb11","unstructured":"B. Birnbaum, N. R. Devanur, and L. Xiao,\n                      New Convex Programs and Distributed Algorithms for Fisher Markets with Linear and Spending Constraint Utilities\n                      , Technical report MSR-TR-2010-112, 2010."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138558"},{"key":"atypb13","unstructured":"J. Borwein and A. S. Lewis,\n                      Convex Analysis and Nonlinear Optimization: Theory and Examples\n                      , Springer, New York, 2010."},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"S. Boucheron, G. Lugosi, and P. Massart,\n                      Concentration Inequalities: A Nonasymptotic Theory of Independence\n                      , Oxford University Press, Oxford, 2013.","DOI":"10.1093\/acprof:oso\/9780199535255.001.0001"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"S. Boyd and L. Vandenberghe,\n                      Convex Optimization\n                      , Cambridge University Press, Cambridge, 2004.","DOI":"10.1017\/CBO9780511804441"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(67)90040-7"},{"key":"atypb17","first-page":"1130","author":"Bubeck S.","year":"2018","journal-title":"ACM"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S106482750037620X"},{"key":"atypb19","unstructured":"R. Caron and T. Traynor,\n                      The Zero Set of a Polynomial\n                      , Technical report, 2005; available online athttp:\/\/www1.uwindsor.ca\/math\/sites\/uwindsor.ca.math\/files\/05-03.pdfandhttps:\/\/www.researchgate.net\/publication\/281285245_The_Zero_Set_of_a_Polynomial."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02190058"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582220"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/15M102887X"},{"key":"atypb23","unstructured":"R.A. Dragomir, J. Bolte, and A. d'Aspremont,\n                      Fast Gradient Methods for Symmetric Nonnegative Matrix Factorization\n                      , arXiv e-prints,https:\/\/arxiv.org\/abs\/1901.10791, 2019."},{"key":"atypb24","unstructured":"N. Flammarion and F. Bach,\n                      Stochastic composite least-squares regression with convergence rate $o (1\/n)$\n                      , in Proceedings of the Conference on Learning Theory, 2017."},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"A. Greenbaum,\n                      Iterative Methods for Solving Linear Systems\n                      , SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9781611970937"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1214\/11-AAP803"},{"key":"atypb28","unstructured":"S. Kakade, S. Shalev-Shwartz, and A. Tewari,\n                      On the Duality of Strong Convexity and Strong Smoothness: Learning Applications and Matrix Regularization\n                      , unpublished manuscript,http:\/\/ttic.uchicago.edu\/~shai\/papers\/KakadeShalevTewari09.pdf, 2009."},{"key":"atypb29","first-page":"1190","author":"Kyng R.","year":"2015","journal-title":"Proceedings of the Conference on Learning Theory"},{"key":"atypb30","first-page":"288","volume":"1","author":"Lu H.","year":"2019","journal-title":"Optim."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/16M1099546"},{"key":"atypb32","first-page":"118","author":"Meir R.","year":"2003","journal-title":"New York"},{"key":"atypb33","unstructured":"K. Mishchenko,\n                      Sinkhorn Algorithm as a Special Case of Stochastic Mirror Descent\n                      , arXiv e-prints, 2019,https:\/\/arxiv.org\/abs\/1909.06918."},{"key":"atypb34","first-page":"135","volume":"15","author":"Nemirovski A.","year":"1979","journal-title":"Metody"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Lectures on Convex Optimization\n                      , Springer Optim. Appl. 137, Springer, New York, 2018.","DOI":"10.1007\/978-3-319-91578-4_2"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01449-1"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614440"},{"key":"atypb38","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 1970."},{"key":"atypb39","doi-asserted-by":"crossref","unstructured":"Y. Saad,\n                      Iterative Methods for Sparse Linear Systems\n                      , SIAM, Philadelphia, 2003.","DOI":"10.1137\/1.9780898718003"},{"key":"atypb40","first-page":"18","author":"Sabanis S.","year":"2013","journal-title":"Electron. Commun. Probab."},{"key":"atypb41","unstructured":"S. Shalev-Shwartz and Y. Singer,\n                      Online Learning: Theory, Algorithms, and Applications\n                      , Ph.D. thesis, Hebrew University, 2007."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1284-2"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/0329006"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580598"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s10013-016-0238-3"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492915000021"},{"key":"atypb47","unstructured":"A. Wilson, L. Mackey, and A. Wibisono,\n                      Accelerating rescaled gradient descent\n                      , in Proceedings of Advances in Neural Information Processing Systems, 2019."},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"C. Z\u0103linescu,\n                      Convex Analysis in General Vector Spaces\n                      , World Scientific, River Edge, NJ, 2002.","DOI":"10.1142\/5021"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M130858X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:04:52Z","timestamp":1787339092000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M130858X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M130858X"],"URL":"https:\/\/doi.org\/10.1137\/19m130858x","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}