{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T19:58:32Z","timestamp":1791316712669,"version":"4.3.1"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100020785","name":"Shenzhen Research Institute of Big Data","doi-asserted-by":"crossref","award":["T00120230001"],"award-info":[{"award-number":["T00120230001"]}],"id":[{"id":"10.13039\/501100020785","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003452","name":"Innovation and Technology Commission","doi-asserted-by":"publisher","award":["CIMDA"],"award-info":[{"award-number":["CIMDA"]}],"id":[{"id":"10.13039\/501100003452","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010877","name":"Shenzhen Science and Technology Innovation Commission","doi-asserted-by":"publisher","award":["GXWD20201231105722002-20200901175001001"],"award-info":[{"award-number":["GXWD20201231105722002-20200901175001001"]}],"id":[{"id":"10.13039\/501100010877","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Anderson acceleration ([Formula: see text]) is a popular acceleration technique to enhance the convergence of fixed-point schemes. The analysis of [Formula: see text] approaches often focuses on the convergence behavior of a corresponding fixed-point residual, while the behavior of the underlying objective function values along the accelerated iterates is currently not well understood. In this paper, we investigate local properties of [Formula: see text] with restarting applied to a basic gradient scheme ([Formula: see text]) in terms of function values. Specifically, we show that [Formula: see text] is a local descent method and that it can decrease the objective function at a rate no slower than the gradient method up to higher-order error terms. These new results theoretically support the good numerical performance of [Formula: see text] when heuristic descent conditions are used for globalization and they provide a novel perspective on the convergence analysis of [Formula: see text] that is more amenable to nonconvex optimization problems. Numerical experiments are conducted to illustrate our theoretical findings.<\/jats:p>","DOI":"10.1137\/22m151460x","type":"journal-article","created":{"date-parts":[[2024,1,19]],"date-time":"2024-01-19T04:32:12Z","timestamp":1705638732000},"page":"336-365","source":"Crossref","is-referenced-by-count":6,"title":["Descent Properties of an Anderson Accelerated Gradient Method with Restarting"],"prefix":"10.1137","volume":"34","author":[{"given":"Wenqing","family":"Ouyang","sequence":"first","affiliation":[{"name":"School of Data Science (SDS), Shenzhen Research Institute of Big Data (SRIBD), Chinese University of Hong Kong, Shenzhen, China."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang","family":"Liu","sequence":"additional","affiliation":[{"name":"Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6784-5417","authenticated-orcid":true,"given":"Andre","family":"Milzarek","sequence":"additional","affiliation":[{"name":"School of Data Science (SDS), Shenzhen Research Institute of Big Data (SRIBD), Chinese University of Hong Kong, Shenzhen, China."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,1,19]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/321296.321305"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0571-6"},{"key":"ref3","first-page":"2669","volume-title":"SEG Technical Program Expanded Abstracts","author":"Aravkin A.","year":"2011"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1088\/0953-8984\/20\/6\/064208"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/14.4.563"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/20M132938X"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/2021069"},{"key":"ref8","unstructured":"A. Coates , \nA. Ng , and \nH. Lee  , An analysis of single-layer networks in unsupervised feature learning, in Proceedings of AISTATS, 2011, pp. 215\u2013223."},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"M. Ermis  and \nI. Yang  , A3DQN: Adaptive Anderson acceleration for deep Q-networks, in Proceedings of the 2020 IEEE Symposium Series on Computational Intelligence, IEEE, 2020, pp. 250\u2013257.","DOI":"10.1109\/SSCI47803.2020.9308288"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/19M1245384"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1006\/jcph.1996.0059"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1002\/nla.617"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.24200\/squjs.vol17iss1pp44-62"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/19M1290097"},{"key":"ref15","unstructured":"M. Geist  and \nB. Scherrer  , Anderson Acceleration for Reinforcement Learning, preprint, arXiv:1809.09501, 2018."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"ref17","unstructured":"X. Guo , \nA. Hu , \nR. Xu , and \nJ. Zhang  , Consistency and Computation of Regularized MLEs for Multivariate Hawkes Processes, preprint, arXiv:1810.02955, 2018."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-46375-7_5"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2019.1594835"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"ref21","unstructured":"A. Krizhevsky  , Learning Multiple Layers of Features from Tiny Images, Master\u2019s thesis, University of Tront, 2009."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-34139-2_21"},{"key":"ref23","unstructured":"V. Mai  and \nM. Johansson  , Anderson acceleration of proximal gradient methods, in Proceedings of the International Conference on Machine Learning, PMLR, 2020, pp. 6620\u20136629."},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/0713057"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4"},{"key":"ref26","series-title":"Springer Ser. Oper. Res. Financ. Eng.","volume-title":"Numerical Optimization","author":"Nocedal J.","year":"2006","edition":"2"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14081"},{"key":"ref28","unstructured":"W. Ouyang , \nJ. Tao , \nA. Milzarek , and \nB. Deng  , Nonmonotone Globalization for Anderson Acceleration Using Adaptive Regularization, preprint, arXiv:2006.02559, 2020."},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355989"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"A. L. Pavlov , \nG. W. Ovchinnikov , \nD. Y. Derbyshev , \nD. Tsetserukou , and \nI. V. Oseledets  , AA-ICP: Iterative closest point with Anderson acceleration, in Proceedings of ICRA, IEEE, 2018, pp. 1\u20136.","DOI":"10.1109\/ICRA.2018.8461063"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/3197517.3201290"},{"key":"ref32","unstructured":"X.H. Pham , \nM. Alamir , \nF. Bonne , and \nP. Bonnay  , On the Use of Anderson Acceleration in Hierarchical Control, preprint, arXiv:2112.04299, 2021."},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/draa095"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1137\/18M1206151"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2012.09.008"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01593790"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1016\/j.cplett.2015.06.029"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s10910-011-9863-y"},{"key":"ref39","doi-asserted-by":"crossref","unstructured":"Y. Saad  , Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, 2003.","DOI":"10.1137\/1.9780898718003"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"ref41","first-page":"712","volume-title":"Advances in Neural Information Processing Systems 29","author":"Scieur D.","year":"2016"},{"key":"ref42","unstructured":"D. Scieur , \nA. d\u2019Aspremont , and \nF. Bach  , Nonlinear Acceleration of Stochastic Algorithms, preprint, arXiv:1706.07270, 2017."},{"key":"ref43","unstructured":"W. Shi , \nS. Song , \nH. Wu , \nY.C. Hsu , \nC. Wu , and \nG. Huang  , Regularized Anderson Acceleration for Off-Policy Deep Reinforcement Learning, preprint, arXiv:1909.03245, 2019."},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/BF02564277"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1007\/s11081-020-09585-w"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/130919398"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/10078356X"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-021-01548-2"},{"key":"ref49","first-page":"22995","volume":"34","author":"Wei F.","year":"2021","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref50","doi-asserted-by":"crossref","unstructured":"P. Xu , \nF. Roosta , and \nM. W. Mahoney  , Second-order optimization for non-convex machine learning: An empirical study, Proceedings of the International Conference on Data Mining, SIAM, Philadelphia, 2020, pp. 199\u2013207.","DOI":"10.1137\/1.9781611976236.23"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1137\/18M1232772"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1145\/3355089.3356491"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M151460X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:56:24Z","timestamp":1787338584000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M151460X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,19]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/22M151460X"],"URL":"https:\/\/doi.org\/10.1137\/22m151460x","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,19]]}}}