关于Anderson混合的研究进展*

包承龙， 韦福超

1.清华大学丘成桐数学科学中心，北京 100084

2.清华大学计算机科学与技术系，北京 100084

由 Anderson（1965）提出的Anderson 混合（AM，Anderson mixing）最早被用于非线性积分方程的计算，现已成为加速定点迭代的一种经典算法.在量子化学领域，AM又被称为Pulay混合（Pulay，1980）或DIIS方法（Rohwedder et al.，2011），在自洽场迭代的加速中发挥了重要作用（Arora et al.，2017）.AM 本质是一种外推方法（Brezinski et al.，2018； Anderson，2019），它通过对历史迭代外推，生成与定点迭代不同的新迭代序列.由于AM 通常能够显著减少迭代过程收敛到定点的迭代次数，因此和定点迭代相较，当定点算子的计算开销很大时，AM 算法能够节省大量的计算时间.所以，AM 在科学计算中也常被称为Anderson 加速（Walker et al.，2011）.近几年来，得益于其实现的简易性和优异的数值表现，AM在科学计算和机器学习领域得到了广泛的关注，研究者们成功地将AM应用于各种定点问题的求解当中，例如，解Navier-Stokes方程（Pollock et al.，2019）、解地震波反演问题（Yang，2021）、加速机器学习中的EM 算法（Henderson et al.，2019）、强化学习训练（Sun et al.，2021）等.此外，AM 的理论性质也引起计算数学界的极大兴趣，对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）实际是一个残差极小化问题，能够让外推系数的确定符合某个最优条件.如果限制外推系数均非负，即≥0，j= 0，…，mk，就得到EDIIS方法（Kudin et al.，2002）.

相较于定点迭代，AM的迭代更新过程的主要开销在于存储历史序列并对之完成外推计算，而并不需要多余的关于g的计算.在之后的研究中，人们基于AM 的迭代格式发展得到更多的算法，这些算法在一些更具体的问题求解中比原始的AM有更好的性质和表现.

由于定点问题广泛存在于科学与工程的各个领域，AM有相当广阔的适用场景，因此在各类应用中围绕AM的算法设计和理论分析是目前科学界的前沿热点，本文将对关于AM的研究进展加以介绍.接下来，本文深入剖析AM 的迭代格式，随后重点介绍关于AM 的几个改进算法，算法包括正则化的AM、随机AM、短递归AM和具有极小内存开销的AM算法，这些算法能够在很大程度上拓展AM的应用范围.

这里给出文中的符号定义：符号Δ 为前向差分符号，例如Δxk=xk+1-xk；符号†表示取Penrose-Moore 逆.对任意矩阵A，range(A)表示由A的列向量张成的子空间.矩阵范数‖ ‖·F(W)的定义为对任意X∈Rd×d，有‖X‖F(W)=‖W1/2XW1/2‖F.

1 基础算法

本节在投影-混合框架下分析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步的迭代信息，从而限制内存占用，这被称为有限内存的方法，将第一类AM 和第二类AM 分别记为AM-I（m）和AM-II（m）.由于AM 的外推计算的开销在mk较大时较为可观，因此一种节省开销并保留一定的AM 加速效果的方式是使用定点迭代和AM 交替迭代（Pratapa et al.，2016； Suryanarayana et al.，2019）.在该方案中，每p步迭代中先执行(p- 1)步定点迭代，再执行1步AM迭代.

关于AM的理论分析主要分为两部分，一个是线性定点问题中全记忆的AM和Krylov子空间方法的关系，另一个是非线性定点问题中有限内存的第二类AM的收敛性.以下加以叙述.

对于求解线性方程组，两类AM与Arnoldi方法（Saad，1981）、GMRES方法（Saad et al.，1986）这两类典型的Krylov 子空间方法有着本质的联系.设问题（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 的投影条件实质对应于两类Galerkin 条件（Saad，2003），因此可以证明基本等价性.这种等价性解释了AM 在线性方程组求解中能快速收敛的原因，AM 也因此被称为非线性Krylov 子空间法（Calef et al.，2013）.同时，Walker et al.（2011）也指出AM 在线性方程组求解中不如GMRES 可靠.此外，前述交替迭代方法也和GMRES在一定情形下有等价性（Lupo Pasini，2019）.

AM 在非线性定点问题中的收敛性分析直到2015 年才有实质的突破，目前的主要工作集中在对第二类AM 的分析上.Toth et al.（2015）在一定的假设条件下证明了AM-II（m）的局部线性收敛性.设问题（1）中g在定点的一个邻域内Lipschitz 连续可微，Lipschitz 常数为κ∈( 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 迭代的稳定性.在AM 的外推计算中，求解最小二乘问题可能会带来数值稳定性问题，因此Walker et al.（2011）建议使用QR分解求解问题（7），这样在Rk的列接近线性相关时可以确保求解的精度.即便如此，对于求解非线性问题，如果算得的过大，也会使得迭代不稳定.因此，正则化的AM 在问题（7）中引入正则项以限制‖Γk‖2的大小，Γk的确定方式为

正则化的AM 是人们应用AM 求解实际问题的一种常用方案.Scieur et al.（2020）在交替迭代算法中引入该正则化，得到适用于无约束最优化的优化算法，并且通过正则化的Chebyshev多项式给出了收敛性分析.Fu et al.（2020）将正则化的AM 用于Douglas-Rachford 算子分裂迭代的加速，算法能够求解带线性等式约束的非光滑凸优化问题.Henderson et al.（2019）在正则化的AM 基础上引入重启动和单调性检验，将算法应用于机器学习中的EM 算法的加速.Sun et al.（2021）将正则化的AM 用于强化学习的训练加速.在这些实践中，正则化对算法的稳定性起到了重要作用.

3 随机Anderson混合

随机Anderson混合（Wei et al.，2021）是AM的一种随机版本，适用于求解随机优化问题.问题描述为

其中函数F：Rd× Ξ →R 是连续可微并且可能非凸的函数，ξ∈Ξ 是随机变量.因为通常情况下F(·；ξ)的具体形式难以显式给出，如ξ服从一个未知的概率分布，或者显式计算f开销过大，所以实践中只能获得问题（11）的带噪声的一阶信息，即带噪声的梯度估计.通过对ξ采样，得到问题（11）的一个特例，即经验风险极小化问题：

其中fi：Rd→R 是关于第i个数据样本的函数，T是样本总数.问题（12）广泛存在于机器学习的各种算法之中.通常T很大，造成遍历数据集得到全梯度∇f(x)的代价昂贵，因此实用的方式是在T个样本中随机采样，得到样本集上的梯度作为全梯度的估计.

使用AM 求解优化问题是一个自然的想法，因为梯度下降法xk+1=g(xk)≔xk- ∇f(xk)是一个定点迭代，可以尝试用AM 加速，此时残差为rk=g(xk)-xk= -∇f(xk).然而，随机优化有本质的难度，由于不能得到精确的梯度，如果使用带噪声的梯度定义残差，传统的AM 没有任何收敛性保证.随机AM 将AM推广到求解随机优化，拓展了AM的应用范围.

在随机AM 算法中，定义残差rk= -g(xk)，其中g(xk)是无偏的梯度估计.相应地，如式（5）所示可以得到历史序列Xk，Rk∈Rd×mk，其中mk= min{}m，k.随机AM 在AM-II（m）的基础上引入了阻尼投影和自适应正则化，其投影步和混合步为：

其中αk∈[]0，1 为阻尼参数，系数Γk由以下正则化的最小二乘问题确定：

其中δk≥0 为正则化参数.由于投影步的变化可能过大，导致中间步越过目标函数当前的信赖域，因此阻尼投影使得=(1 -αk)xk+αk(xk-XkΓk)=xk-αkXkΓk.同时，正则化也起到限制‖XkΓk‖2的大小的作用.这些操作可以改善算法在随机场景中的鲁棒性和稳定性，确保算法的收敛性.

随机AM 在非凸随机优化中有全局收敛性.假设f连续可微且有下界，∇f全局Lipschitz 连续；各样本独立无关，并且与之前的迭代步无关，梯度估计是全梯度的无偏估计，且方差一致有界.对于随机AM，使用递减的混合参数

并对αk，δk施加必要的条件，有

如果还有梯度估计g(xk)一致有界，那么有= 0 以概率1成立.此外，如果从历史迭代步里随机选取解，那么为了确保E≤ϵ，所需的梯度采样总次数为O(ϵ-2)，这表明随机AM 达到了一阶黑盒随机优化的最优复杂度.

此外，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），适用于求解经验风险极小化问题.如果在随机AM 中使用方差减少的梯度估计，那么为了确保≤ϵ，所需的梯度采样总次数为O(T+(T2/3/ϵ))，即算法复杂度得到了改进.

随机AM 已经被成功用于深度学习的神经网络训练.在图像分类和语言模型等任务上，随机AM 相比现有的随机优化器有明显更好的收敛性，在大部分任务上节约了总的计算时间，因此继承了AM在确定性问题中的优良效果，在非凸随机优化中有很好的适用性.

4 短递归的Anderson混合

短递归的Anderson 混合（Wei et al.，2022a）减少AM 的内存开销，适用于高维问题的求解.与各种类型的拟Newton 法类似，AM 需要存储历史序列Xk，Rk∈Rd×mk，因此相比定点迭代需要额外存储2mk个维数为d的向量.如果历史序列长度较大，内存开销将成为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).进而迭代为

当求解对称正定线性方程组（或强凸二次优化问题）时，由式（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的导数的Lipschitz 常数.因此短递归AM 在理论上没有减弱AM 的收敛性.对于求解非凸优化问题，通过引入阻尼投影和正则化，短递归的AM 具有全局收敛性，并且在非凸随机优化中有收敛性保证.因此，如果应用对迭代算法的内存占用有限制，那么相较于有限内存的AM和随机AM，短递归的AM更有优势.

5 具有极小内存开销的Anderson混合

具有极小内存开销的Anderson 混合（Wei et al.，2022b）（Min-AM）是一种基于AM 的高效优化算法，适用于大规模优化问题的求解.Min-AM 的历史序列长度为1，因此具有极小的内存开销.同时，Min-AM 在优化问题中仍有不输于拟Newton法的收敛性.

对于求解优化问题，因为光滑函数在最优解的局部邻域能用一个二次函数近似，所以如果优化器能快速地优化该二次函数，那么在优化原目标函数时也有望有良好的收敛效果.因此，考虑强凸二次优化

可以看到Hk是对称的.迭代公式（22）即为Min-AM的基础形式.

在求解强凸二次优化问题（19）中，Wei et al.（2022b）揭示了Min-AM 与共轭梯度法、Newton 法、BFGS（Nocedal et al.，2006）的本质联系.以下介绍有关结论.

关于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.对优化问题（19），在第k步迭代，将x∈Rd写为x=xk-Pkγ-Vkη，其中γ∈Rk，η∈Rd-k.先在子空间range(Pk)上运用Newton法，接着在range(Pk)⊥上以步长βk梯度下降，最后再在range(Pk)上运用Newton法，得到

这表明在求解强凸二次优化问题时，Min-AM 和B迭代完全等价.而B迭代由Newton法和梯度下降法导出，并且是一种对称化的多重割线拟Newton法，当k=d时，B迭代在全空间上使用Newton法.这就建立了Min-AM和Newton法的联系，可以认为Min-AM隐式地构造了Hessian阵的近似逆矩阵

进一步地，如果Min-AM和B迭代的参数βk为常数β，那么有=βI，随后的求解了

如果将pk，qk替换为sk，tk，那么式（26）导出BFGS 算法.这个关系表明，B 迭代使用修正的历史序列构造Hessian阵的近似逆矩阵，由于Min-AM和B迭代等价，因此Min-AM相较于BFGS能够减少大量的内存占用.

对于求解一般的非线性光滑优化乃至随机优化，Min-AM 也有明确的收敛性结论.在确定性的光滑优化中，通过在迭代格式（22）上引入重启动和必要的检验，可以证明Min-AM的收敛率最优地依赖于问题的条件数，Min-AM 和使用精确线搜索的非线性共轭梯度法有相当的收敛性.在随机优化中，与随机AM 类似，引入阻尼项和正则化，Min-AM有全局收敛性并达到了最优的迭代复杂度.因此，Min-AM不仅将AM在优化问题中的内存开销降到极小，而且保证了算法的收敛性，在优化问题的求解中具备明显的优势.此外，对于确定性的光滑优化，Wei et al.（2022b）指出Min-AM 可以使用很小的附加计算代价估计Hessian矩阵的特征值信息，从而估计混合参数βk的最优选取，这对于算法的实际应用也是有益的.

6 总 结

Anderson 混合是加速定点迭代的一种强有力的算法，现有的研究揭示了其与Krylov 子空间方法和拟Newton 法的深刻联系.目前Anderson 混合的收敛性问题还没有得到完全解决，仍需要有更好的理论分析结果来更精确地刻画Anderson混合在非线性定点问题中的收敛行为.为了改善算法的稳定性、增大算法的使用范围，一些Anderson混合的改进算法被提出并得到了成功应用.本文介绍了其中一些有代表性的改进算法，结论表明基于Anderson 混合的新算法能够被用于随机优化等更困难的问题，并且能够在内存开销上相较于传统的拟Newton法有明显的优势，有望解决科学计算和机器学习等领域中具有挑战性的实际问题，值得被进一步研究.