包承龍， 韋福超

1.清華大學丘成桐數(shù)學科學中心，北京 100084

2.清華大學計算機科學與技術系，北京 100084

由 Anderson（1965）提出的Anderson 混合（AM，Anderson mixing）最早被用于非線性積分方程的計算，現(xiàn)已成為加速定點迭代的一種經(jīng)典算法.在量子化學領域，AM又被稱為Pulay混合（Pulay，1980）或DIIS方法（Rohwedder et al.，2011），在自洽場迭代的加速中發(fā)揮了重要作用（Arora et al.，2017）.AM 本質(zhì)是一種外推方法（Brezinski et al.，2018； Anderson，2019），它通過對歷史迭代外推，生成與定點迭代不同的新迭代序列.由于AM 通常能夠顯著減少迭代過程收斂到定點的迭代次數(shù)，因此和定點迭代相較，當定點算子的計算開銷很大時，AM 算法能夠節(jié)省大量的計算時間.所以，AM 在科學計算中也常被稱為Anderson 加速（Walker et al.，2011）.近幾年來，得益于其實現(xiàn)的簡易性和優(yōu)異的數(shù)值表現(xiàn)，AM在科學計算和機器學習領域得到了廣泛的關注，研究者們成功地將AM應用于各種定點問題的求解當中，例如，解Navier-Stokes方程（Pollock et al.，2019）、解地震波反演問題（Yang，2021）、加速機器學習中的EM 算法（Henderson et al.，2019）、強化學習訓練（Sun et al.，2021）等.此外，AM 的理論性質(zhì)也引起計算數(shù)學界的極大興趣，對AM在定點問題中的收斂性給出理論分析仍是目前一個重要的研究問題（Toth et al.，2015； Evans et al.，2020；Bian et al.，2021）.

先簡要介紹AM的基本迭代格式.考慮定點問題

其中x∈Rd，g：Rd→Rd.如果g是收縮算子，那么由壓縮映射原理，定點迭代

收斂.為加速迭代（2），AM 對歷史迭代序列進行外推來生成新的迭代值.具體地，設第k次迭代用到的歷史序列的長度為mk，AM使用下式更新得到

隨后將看到問題（4）實際是一個殘差極小化問題，能夠讓外推系數(shù)的確定符合某個最優(yōu)條件.如果限制外推系數(shù)均非負，即≥0，j= 0，…，mk，就得到EDIIS方法（Kudin et al.，2002）.

相較于定點迭代，AM的迭代更新過程的主要開銷在于存儲歷史序列并對之完成外推計算，而并不需要多余的關于g的計算.在之后的研究中，人們基于AM 的迭代格式發(fā)展得到更多的算法，這些算法在一些更具體的問題求解中比原始的AM有更好的性質(zhì)和表現(xiàn).

由于定點問題廣泛存在于科學與工程的各個領域，AM有相當廣闊的適用場景，因此在各類應用中圍繞AM的算法設計和理論分析是目前科學界的前沿熱點，本文將對關于AM的研究進展加以介紹.接下來，本文深入剖析AM 的迭代格式，隨后重點介紹關于AM 的幾個改進算法，算法包括正則化的AM、隨機AM、短遞歸AM和具有極小內(nèi)存開銷的AM算法，這些算法能夠在很大程度上拓展AM的應用范圍.

這里給出文中的符號定義：符號Δ 為前向差分符號，例如Δxk=xk+1-xk；符號?表示取Penrose-Moore 逆.對任意矩陣A，range(A)表示由A的列向量張成的子空間.矩陣范數(shù)‖ ‖·F(W)的定義為對任意X∈Rd×d，有‖X‖F(xiàn)(W)=‖W1/2XW1/2‖F(xiàn).

1 基礎算法

本節(jié)在投影-混合框架下分析AM的迭代格式，給出第一類AM方法，并介紹已有的結論.

對于求解問題（4），一種方式是通過Lagrange 乘子法求解，另一種方式是將其轉換為無約束問題.具體地，定義xk處的殘差為rk=g(xk)-xk，歷史序列被存儲為兩個矩陣Xk，Rk∈Rd×mk(mk≥1)：

AM的迭代格式可以被分解為投影步和混合步：

在AM 的使用中需要確定歷史序列長度mk.一種做法是取mk=k，即使用全部的歷史信息，因此這被稱為全記憶的方法；另一種做法是取mk= min{m，k}，即使用最近m步的迭代信息，從而限制內(nèi)存占用，這被稱為有限內(nèi)存的方法，將第一類AM 和第二類AM 分別記為AM-I（m）和AM-II（m）.由于AM 的外推計算的開銷在mk較大時較為可觀，因此一種節(jié)省開銷并保留一定的AM 加速效果的方式是使用定點迭代和AM 交替迭代（Pratapa et al.，2016； Suryanarayana et al.，2019）.在該方案中，每p步迭代中先執(zhí)行(p- 1)步定點迭代，再執(zhí)行1步AM迭代.

關于AM的理論分析主要分為兩部分，一個是線性定點問題中全記憶的AM和Krylov子空間方法的關系，另一個是非線性定點問題中有限內(nèi)存的第二類AM的收斂性.以下加以敘述.

對于求解線性方程組，兩類AM與Arnoldi方法（Saad，1981）、GMRES方法（Saad et al.，1986）這兩類典型的Krylov 子空間方法有著本質(zhì)的聯(lián)系.設問題（1）中g(x) =(I-A)x+b，A∈Rd×d非奇異，b∈Rd.令和分別為全記憶的第一類和全記憶的第二類AM 生成的序列，令和為Arnoldi 方法和GMRES 生成的序列.如果各算法的迭代初值相同，那么，在一定假設下，有關系式和成立，即AM 的中間步和對應的一類Krylov子空間方法的迭代步相同.Walker et al.（2011）最早對此關系給出嚴格證明，并在文中稱之為“基本等價”，本文沿用這樣的說法.簡要來說，在線性情形，可以證明range(Xk)是Krylov 子空間，AM 的投影條件實質(zhì)對應于兩類Galerkin 條件（Saad，2003），因此可以證明基本等價性.這種等價性解釋了AM 在線性方程組求解中能快速收斂的原因，AM 也因此被稱為非線性Krylov 子空間法（Calef et al.，2013）.同時，Walker et al.（2011）也指出AM 在線性方程組求解中不如GMRES 可靠.此外，前述交替迭代方法也和GMRES在一定情形下有等價性（Lupo Pasini，2019）.

AM 在非線性定點問題中的收斂性分析直到2015 年才有實質(zhì)的突破，目前的主要工作集中在對第二類AM 的分析上.Toth et al.（2015）在一定的假設條件下證明了AM-II（m）的局部線性收斂性.設問題（1）中g在定點的一個鄰域內(nèi)Lipschitz 連續(xù)可微，Lipschitz 常數(shù)為κ∈( 0，1).對?∈(κ，1) ，如果初值足夠好，并且迭代中保證一致有界，那么對殘差rk，有

之后，類似的收斂性結論對于EDIIS也被證明成立（Chen et al.，2019），并于近期被推廣到針對非光滑問題的分析中（Mai et al.，2020； Bian et al.，2021； Bian et al.，2022）.然而，這些理論結果還非常局限.Anderson（2019）在其評論中指出，結論（8）不能解釋AM 在實踐中比定點迭代明顯更好的收斂性，因為后者q-線性收斂并且q-因子為κ.為此，Evans et al.（2020）給出了一個改進的結論：

其中sk=，k≥m.因為總有sk∈[0，1 ]，因此當sk?1時，殘差的一階分量迅速衰減.Pollock et al.（2021）給出了更精細的分析結果.由于sk是在迭代過程中才能確定的，結論（9）不能在迭代之初預測AM的收斂情況.

2 正則化的Anderson混合

正則化的Anderson 混合（Scieur et al.，2020）是AM 的一種改進算法，通常能夠改善AM 迭代的穩(wěn)定性.在AM 的外推計算中，求解最小二乘問題可能會帶來數(shù)值穩(wěn)定性問題，因此Walker et al.（2011）建議使用QR分解求解問題（7），這樣在Rk的列接近線性相關時可以確保求解的精度.即便如此，對于求解非線性問題，如果算得的過大，也會使得迭代不穩(wěn)定.因此，正則化的AM 在問題（7）中引入正則項以限制‖Γk‖2的大小，Γk的確定方式為

正則化的AM 是人們應用AM 求解實際問題的一種常用方案.Scieur et al.（2020）在交替迭代算法中引入該正則化，得到適用于無約束最優(yōu)化的優(yōu)化算法，并且通過正則化的Chebyshev多項式給出了收斂性分析.Fu et al.（2020）將正則化的AM 用于Douglas-Rachford 算子分裂迭代的加速，算法能夠求解帶線性等式約束的非光滑凸優(yōu)化問題.Henderson et al.（2019）在正則化的AM 基礎上引入重啟動和單調(diào)性檢驗，將算法應用于機器學習中的EM 算法的加速.Sun et al.（2021）將正則化的AM 用于強化學習的訓練加速.在這些實踐中，正則化對算法的穩(wěn)定性起到了重要作用.

3 隨機Anderson混合

隨機Anderson混合（Wei et al.，2021）是AM的一種隨機版本，適用于求解隨機優(yōu)化問題.問題描述為

其中函數(shù)F：Rd× Ξ →R 是連續(xù)可微并且可能非凸的函數(shù)，ξ∈Ξ 是隨機變量.因為通常情況下F(·；ξ)的具體形式難以顯式給出，如ξ服從一個未知的概率分布，或者顯式計算f開銷過大，所以實踐中只能獲得問題（11）的帶噪聲的一階信息，即帶噪聲的梯度估計.通過對ξ采樣，得到問題（11）的一個特例，即經(jīng)驗風險極小化問題：

其中fi：Rd→R 是關于第i個數(shù)據(jù)樣本的函數(shù)，T是樣本總數(shù).問題（12）廣泛存在于機器學習的各種算法之中.通常T很大，造成遍歷數(shù)據(jù)集得到全梯度?f(x)的代價昂貴，因此實用的方式是在T個樣本中隨機采樣，得到樣本集上的梯度作為全梯度的估計.

使用AM 求解優(yōu)化問題是一個自然的想法，因為梯度下降法xk+1=g(xk)?xk- ?f(xk)是一個定點迭代，可以嘗試用AM 加速，此時殘差為rk=g(xk)-xk= -?f(xk).然而，隨機優(yōu)化有本質(zhì)的難度，由于不能得到精確的梯度，如果使用帶噪聲的梯度定義殘差，傳統(tǒng)的AM 沒有任何收斂性保證.隨機AM 將AM推廣到求解隨機優(yōu)化，拓展了AM的應用范圍.

在隨機AM 算法中，定義殘差rk= -g(xk)，其中g(xk)是無偏的梯度估計.相應地，如式（5）所示可以得到歷史序列Xk，Rk∈Rd×mk，其中mk= min{}m，k.隨機AM 在AM-II（m）的基礎上引入了阻尼投影和自適應正則化，其投影步和混合步為：

其中αk∈[]0，1 為阻尼參數(shù)，系數(shù)Γk由以下正則化的最小二乘問題確定：

其中δk≥0 為正則化參數(shù).由于投影步的變化可能過大，導致中間步越過目標函數(shù)當前的信賴域，因此阻尼投影使得=(1 -αk)xk+αk(xk-XkΓk)=xk-αkXkΓk.同時，正則化也起到限制‖XkΓk‖2的大小的作用.這些操作可以改善算法在隨機場景中的魯棒性和穩(wěn)定性，確保算法的收斂性.

隨機AM 在非凸隨機優(yōu)化中有全局收斂性.假設f連續(xù)可微且有下界，?f全局Lipschitz 連續(xù)；各樣本獨立無關，并且與之前的迭代步無關，梯度估計是全梯度的無偏估計，且方差一致有界.對于隨機AM，使用遞減的混合參數(shù)

并對αk，δk施加必要的條件，有

如果還有梯度估計g(xk)一致有界，那么有= 0 以概率1成立.此外，如果從歷史迭代步里隨機選取解，那么為了確保E≤?，所需的梯度采樣總次數(shù)為O(?-2)，這表明隨機AM 達到了一階黑盒隨機優(yōu)化的最優(yōu)復雜度.

此外，Wei et al.（2021）還給出隨機AM的改進方案，方案包括預處理和方差減少技術.

預處理的隨機AM使用了預處理的混合步：

其中Mk是對Hessian 陣?2f(xk)的近似.將式（13）中的投影步和式（15）結合即為預處理的隨機AM.設整體的迭代式為xk+1=xk+Gkrk，那么在αk= 1，δk= 0時，Gk求解了

方差減少技術起源于SVRG 算法（Johnson et al.，2013），適用于求解經(jīng)驗風險極小化問題.如果在隨機AM 中使用方差減少的梯度估計，那么為了確保≤?，所需的梯度采樣總次數(shù)為O(T+(T2/3/?))，即算法復雜度得到了改進.

隨機AM 已經(jīng)被成功用于深度學習的神經(jīng)網(wǎng)絡訓練.在圖像分類和語言模型等任務上，隨機AM 相比現(xiàn)有的隨機優(yōu)化器有明顯更好的收斂性，在大部分任務上節(jié)約了總的計算時間，因此繼承了AM在確定性問題中的優(yōu)良效果，在非凸隨機優(yōu)化中有很好的適用性.

4 短遞歸的Anderson混合

短遞歸的Anderson 混合（Wei et al.，2022a）減少AM 的內(nèi)存開銷，適用于高維問題的求解.與各種類型的擬Newton 法類似，AM 需要存儲歷史序列Xk，Rk∈Rd×mk，因此相比定點迭代需要額外存儲2mk個維數(shù)為d的向量.如果歷史序列長度較大，內(nèi)存開銷將成為AM 的瓶頸，致使算法無法在存儲資源受限的機器上求解高維問題.短遞歸的AM將歷史序列的長度降到2，同時能夠保證良好的收斂性.

首先介紹短遞歸AM 的基礎形式.與AM 不同，短遞歸的AM 使用修正的歷史序列Pk，Qk∈Rd×2，在每步迭代之初需要對向量對Δxk-1，Δrk-1作修正.初始化P0，Q0= 0，在第k步迭代，構造pk，qk∈Rd：

其中選取ζk= arg minζ‖‖Δrk-1-Qk-1ζ2.從而得到Pk=(pk-1，pk)，Qk=(qk-1，qk).進而迭代為

當求解對稱正定線性方程組（或強凸二次優(yōu)化問題）時，由式（16）～（17）定義的短遞歸AM 和全記憶的第二類AM 完全等價，這意味著短遞歸的AM 雖然僅使用長度為2 的歷史序列，但是卻與AM-II（∞）有相同的收斂性，因此不存在歷史信息的遺忘.

對于求解一般的非線性定點問題，通過引入周期性重啟動和對‖Pk-1ζk‖2， ‖Qk-1ζk‖2的有界性檢查，在對g的標準假設（Toth et al.，2015； Evans et al.，2020）下，短遞歸的AM具有局部線性收斂性：

其中sk=≤1，κ和κ?分別為g和g的導數(shù)的Lipschitz 常數(shù).因此短遞歸AM 在理論上沒有減弱AM 的收斂性.對于求解非凸優(yōu)化問題，通過引入阻尼投影和正則化，短遞歸的AM 具有全局收斂性，并且在非凸隨機優(yōu)化中有收斂性保證.因此，如果應用對迭代算法的內(nèi)存占用有限制，那么相較于有限內(nèi)存的AM和隨機AM，短遞歸的AM更有優(yōu)勢.

5 具有極小內(nèi)存開銷的Anderson混合

具有極小內(nèi)存開銷的Anderson 混合（Wei et al.，2022b）（Min-AM）是一種基于AM 的高效優(yōu)化算法，適用于大規(guī)模優(yōu)化問題的求解.Min-AM 的歷史序列長度為1，因此具有極小的內(nèi)存開銷.同時，Min-AM 在優(yōu)化問題中仍有不輸于擬Newton法的收斂性.

對于求解優(yōu)化問題，因為光滑函數(shù)在最優(yōu)解的局部鄰域能用一個二次函數(shù)近似，所以如果優(yōu)化器能快速地優(yōu)化該二次函數(shù)，那么在優(yōu)化原目標函數(shù)時也有望有良好的收斂效果.因此，考慮強凸二次優(yōu)化

可以看到Hk是對稱的.迭代公式（22）即為Min-AM的基礎形式.

在求解強凸二次優(yōu)化問題（19）中，Wei et al.（2022b）揭示了Min-AM 與共軛梯度法、Newton 法、BFGS（Nocedal et al.，2006）的本質(zhì)聯(lián)系.以下介紹有關結論.

關于Min-AM 的一個重要結論是Min-AM 與第一類AM 和共軛梯度法基本等價.考慮求解問題（19），設{xk}是Min-AM 生成的迭代序列，是第k步迭代中的第一個中間步（見迭代格式（20））；設{}是第一類AM 生成的迭代序列，是第k步迭代中的中間步（見迭代格式（6））；{}是共軛梯度法生成的迭代序列.基本等價性指如果迭代初值相同，那么

這意味著3個算法的收斂性基本相同.

定義Pk=(p1，…，pk)，Qk=(q1，…，qk)，并定義Vk∈Rd×(d-k)使得VTk Pk= 0.對優(yōu)化問題（19），在第k步迭代，將x∈Rd寫為x=xk-Pkγ-Vkη，其中γ∈Rk，η∈Rd-k.先在子空間range(Pk)上運用Newton法，接著在range(Pk)⊥上以步長βk梯度下降，最后再在range(Pk)上運用Newton法，得到

這表明在求解強凸二次優(yōu)化問題時，Min-AM 和B迭代完全等價.而B迭代由Newton法和梯度下降法導出，并且是一種對稱化的多重割線擬Newton法，當k=d時，B迭代在全空間上使用Newton法.這就建立了Min-AM和Newton法的聯(lián)系，可以認為Min-AM隱式地構造了Hessian陣的近似逆矩陣

進一步地，如果Min-AM和B迭代的參數(shù)βk為常數(shù)β，那么有=βI，隨后的求解了

如果將pk，qk替換為sk，tk，那么式（26）導出BFGS 算法.這個關系表明，B 迭代使用修正的歷史序列構造Hessian陣的近似逆矩陣，由于Min-AM和B迭代等價，因此Min-AM相較于BFGS能夠減少大量的內(nèi)存占用.

對于求解一般的非線性光滑優(yōu)化乃至隨機優(yōu)化，Min-AM 也有明確的收斂性結論.在確定性的光滑優(yōu)化中，通過在迭代格式（22）上引入重啟動和必要的檢驗，可以證明Min-AM的收斂率最優(yōu)地依賴于問題的條件數(shù)，Min-AM 和使用精確線搜索的非線性共軛梯度法有相當?shù)氖諗啃?在隨機優(yōu)化中，與隨機AM 類似，引入阻尼項和正則化，Min-AM有全局收斂性并達到了最優(yōu)的迭代復雜度.因此，Min-AM不僅將AM在優(yōu)化問題中的內(nèi)存開銷降到極小，而且保證了算法的收斂性，在優(yōu)化問題的求解中具備明顯的優(yōu)勢.此外，對于確定性的光滑優(yōu)化，Wei et al.（2022b）指出Min-AM 可以使用很小的附加計算代價估計Hessian矩陣的特征值信息，從而估計混合參數(shù)βk的最優(yōu)選取，這對于算法的實際應用也是有益的.

6 總 結

Anderson 混合是加速定點迭代的一種強有力的算法，現(xiàn)有的研究揭示了其與Krylov 子空間方法和擬Newton 法的深刻聯(lián)系.目前Anderson 混合的收斂性問題還沒有得到完全解決，仍需要有更好的理論分析結果來更精確地刻畫Anderson混合在非線性定點問題中的收斂行為.為了改善算法的穩(wěn)定性、增大算法的使用范圍，一些Anderson混合的改進算法被提出并得到了成功應用.本文介紹了其中一些有代表性的改進算法，結論表明基于Anderson 混合的新算法能夠被用于隨機優(yōu)化等更困難的問題，并且能夠在內(nèi)存開銷上相較于傳統(tǒng)的擬Newton法有明顯的優(yōu)勢，有望解決科學計算和機器學習等領域中具有挑戰(zhàn)性的實際問題，值得被進一步研究.