包承龍， 韋福超

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

2.清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系，北京 100084

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

先簡(jiǎn)要介紹AM的基本迭代格式.考慮定點(diǎn)問題

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

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

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

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

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

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

1 基礎(chǔ)算法

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

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

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

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

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

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

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

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

其中sk=，k≥m.因?yàn)榭傆衧k∈[0，1 ]，因此當(dāng)sk?1時(shí)，殘差的一階分量迅速衰減.Pollock et al.（2021）給出了更精細(xì)的分析結(jié)果.由于sk是在迭代過程中才能確定的，結(jié)論（9）不能在迭代之初預(yù)測(cè)AM的收斂情況.

2 正則化的Anderson混合

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

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

3 隨機(jī)Anderson混合

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

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

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

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

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

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

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

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

并對(duì)αk，δk施加必要的條件，有

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

此外，Wei et al.（2021）還給出隨機(jī)AM的改進(jìn)方案，方案包括預(yù)處理和方差減少技術(shù).

預(yù)處理的隨機(jī)AM使用了預(yù)處理的混合步：

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

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

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

4 短遞歸的Anderson混合

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

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

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

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

對(duì)于求解一般的非線性定點(diǎn)問題，通過引入周期性重啟動(dòng)和對(duì)‖Pk-1ζk‖2， ‖Qk-1ζk‖2的有界性檢查，在對(duì)g的標(biāo)準(zhǔn)假設(shè)（Toth et al.，2015； Evans et al.，2020）下，短遞歸的AM具有局部線性收斂性：

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

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

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

對(duì)于求解優(yōu)化問題，因?yàn)楣饣瘮?shù)在最優(yōu)解的局部鄰域能用一個(gè)二次函數(shù)近似，所以如果優(yōu)化器能快速地優(yōu)化該二次函數(shù)，那么在優(yōu)化原目標(biāo)函數(shù)時(shí)也有望有良好的收斂效果.因此，考慮強(qiáng)凸二次優(yōu)化

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

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

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

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

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

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

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

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

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

6 總 結(jié)

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