加速梯度流与结构保持离散化的标准化参数化方法

《Communications in Nonlinear Science and Numerical Simulation》：A Normalized Parametrization of Accelerated Gradient Flows and Structure-Preserving Discretizations

　　摘要：我们研究了凸优化中加速梯度流的标准化参数化方法。该参数化引入了一个大于0的缩放参数α，使得时间缩放、阻尼、李雅普诺夫耗散与离散稳定性之间的关联更加清晰。在连续时间下，这种标准化流具有以e?αt为速率的李雅普诺夫衰减特性。基于这一标准化形式，我们推导出一组保持结构的离散化方法，包括隐式格式、半隐式格式、预测-校正格式以及梯度校正格式。此外，我们还将该框架扩展到复合优化和近端分裂算法中，在这些算法中，先对与速度相关的变量应用近端算子，再通过流关系得到位置更新。最后，通过典型测试问题的数值实验，展示了α对收敛行为的影响。

引言：将离散优化算法视为连续时间常微分方程的离散化形式，已成为分析加速现象的一种有效框架。在本研究中，我们将这一连续时间视角应用于机器学习[1][2]和信号处理[3]中常见的基本凸优化问题min?xf(x)。具体而言，我们研究的是复合型问题f(x)=h(x)+g(x)，其中h为光滑凸函数，g为非光滑凸函数[4]。我们首先回顾标准的梯度下降更新规则xk+1=xk?η?f(xk)，其中η为学习率。尽管梯度下降是现代大规模学习的基石[5]，但其O(1/k)的收敛速率往往无法满足高维应用的需求。为了解决这一问题，涅斯捷罗夫提出的加速梯度法[NAG][6]引入了动量项：{yk+1=xk?η?f(xk),xk+1=yk+1+βk(yk+1?yk)}。NAG实现了最优的O(1/k2)收敛速率，但在离散域中其加速机制仍不清晰。为填补这一空白，[7]指出当步长趋近于零时，NAG可转化为二阶常微分方程：x¨(t)+rtx˙(t)+?f(x(t))=0。与描述过阻尼无质量粒子的的一阶梯度流x˙=??f(x)不同，NAG对应的常微分方程描述的是带阻尼的惯性系统。项(r/t)x˙起到了“趋近于零的粘性”作用，能够在早期迭代中保持稳定性，同时让算法在轨迹后期的低曲率区域快速移动[8][9][10][11]。这种动态视角不仅为基于动量的加速机制提供了直观的物理解释，有助于统一多类优化方法，如波利亚克的重球法[12][13][14]，还为基于李雅普诺夫的收敛性分析提供了基础[15]，同时也促使人们通过精心设计的常微分方程离散化方案，如龙格-库塔方法[15][16][17][18]，来系统地设计新的优化算法。近期的一些研究试图借助经典拉格朗日力学和哈密顿力学中的变分框架，将各类加速算法统一起来。[19]提出了一个广义欧拉-拉格朗日系统：{x˙(t)=ξ(t)(v(t)?x(t)),β(t)v˙(t)=?ξ(t)?f(x(t))}，其中ξ(t)?>?0，β(t)?>?0，且满足β˙(t)≥?ξ(t)β(t)，同时β(0)=β0≥0。通过构造李雅普诺夫（能量）函数Ξ(t)=e∫0tξ(s)ds(f(x(t))?f*)+1/2∥v(t)?x*∥2，作者证明了f(x(t))?f(x*)的收敛速率为指数级，即≤O(e?∫0tξ(s)ds)。[20]进一步将这一方法扩展到最小化μ-强凸函数的情形，当ξ=μ时即可恢复波利亚克的重球法动态，同时在离散时间环境下也为μ-强凸函数实现了加速算法，从而建立了连续时间下的阻尼行为与离散时间加速算法收敛性之间的直接对应关系。本文的主要贡献如下：我们提出并分析了一种动力学系统，即广义加速梯度流GAGF：{x˙(t)=v(t)?αx(t),?t≥0,γ(t)v˙(t)=μ(αx(t)?v(t))?α?f(x(t))}，其中α?>?0，而时变参数γ(t)遵循自身的演化规律，为该动力学系统带来了更多灵活性：γ˙(t)=μ?αγ(t)，且γ(0)>0。我们需要指出，这种连续时间下的指数衰减特性与已有关于时间缩放惯性动力学的研究结果是一致的，如[15][18][21][22]。特别地，当μ=0时，所提出的流可以改写为具有恒定粘性阻尼以及梯度项前带有指数增长系数的时间缩放惯性动力学模型，这类模型的收敛性是已知的；因此，连续时间下的这一收敛速率本身并非新发现。在我们的研究中，连续时间形式的意义在于引入一种标准化参数化方法，便于追踪离散化之后各离散参数的演化过程。我们在离散时间环境下提出了一整套保持结构的算法，这些算法能够将连续时间下的优势有效转化为离散域中的优势。其中包括适用于光滑函数和非光滑函数的无条件稳定隐式格式、计算效率较高的半隐式预测-校正格式及其梯度校正版本、用于非光滑复合优化问题的复合预测-校正格式，以及基于位置信息和速度信息的加速前后向格式。我们分析了这些算法在不同场景下的收敛性，并证明它们对应于所提连续时间GAGF模型的适当离散化形式，因而具备GAGF的几何能量衰减特性及其他稳定性特征。同时，我们还给出了明确的稳定性准则，为步长选择提供指导。基于α的标准化参数化可被视为一种工具，它使得我们的框架中连续时间到离散时间的转换更加清晰。它有助于理解α如何影响γk、vk以及步长ηk的离散演化过程，还能说明连续时间缩放因子（如e?αt）是如何转化为受允许步长条件约束的离散递归关系或乘积形式因子。这也解释了为何在离散化之后，连续时间下的加速效应可能无法完全保留。若一个可微函数q:Rn→R满足∥?q(y)??q(x)∥≤L∥y?x∥，则称其为L-光滑函数，这等价于以下二次上界：q(x)≤q(y)+〈?q(y),x?y〉+L2∥x?y∥2。若函数f:Rn→R满足f(y)≥f(x)+〈?f(x),y?x〉+μ2∥y?x∥2（其中μ?≥?0），则称其为μ-凸函数。在整个研究中，我们均假设解集是非空的。对于光滑凸问题，我们用Xf*:=arg minx∈Rnf(x)表示其解集，用f*:=minx∈Rnf(x)表示该解集对应的函数值。在本文中，x*表示Xf*中任意但固定的一个元素。当f为μ-凸函数且μ?>?0时，其解集Xf*为单点集。而在仅具有凸性的情况下，即μ=0时，所有涉及x*的估计结果都是相对于这一固定的最小化者而言的。我们还会使用以下标准的梯度残差估计公式：若f为凸函数且L-光滑，则对于任意x∈Rn，都有12L∥?f(x)∥2≤f(x)?f*。这一结论实际上是通过将下降引理应用于x?1L?f(x)得到的。本文的其余结构如下：第2节分析连续时间下的收敛性；第3节为min?f问题的保持结构离散化建立收敛速率；第4节将分析范围扩展到min(f+g)问题；第5节介绍数值实验结果；第6节总结全文。

章节节选：

连续时间下的收敛性分析：在本节中，我们建立了所提出的广义加速梯度流（1.2）的指数级收敛速率。首先，我们构造了一个李雅普诺夫函数[23]，该函数能够同时反映目标函数的误差以及到最优解的平方距离。

命题2.1：假设f是一个μ-凸函数，其解集Xf*非空，且固定x*∈Xf*。设(x(t), v(t))为GAGF（1.2）对应的轨迹，其中γ(t)满足条件（1.3），定义李雅普诺夫（能量）函数Ξ(t)=α(f(x(t))?f*)+γ(t)2∥v(t)?αx*∥2≥0。那么有dtΞ(t)+μ2∥

离散时间下的收敛性分析：在本节中，我们从GAGF系统（1.2）出发推导出离散时间算法，并分析它们的收敛性质。提出这些算法的目的并非是为了从不同实现方式中获得不同的渐近收敛速率，而是为了表明相同的李雅普诺夫衰减机制可以在不同的数值实现中得以保持。隐式格式可作为保持结构的基准离散化方法，而近端重构方法则可将该格式扩展到非光滑目标函数的处理中，此外还有两种

两块结构复合凸优化问题：现在我们来研究如下复合优化问题：minx∈Rnf(x):=h(x)+g(x)，其中h为μ-凸且L-光滑函数，g为凸函数但可能存在非光滑性。我们假设该问题的解集Xf*非空，且在整节讨论中，x*均表示Xf*中任意但固定的一个元素。连续时间下的GAGF动力学模型可以通过以下微分包含式自然地扩展到该复合优化问题中：{x˙(t)=v(t)?αx(t),v˙(t)∈μγ(t)(αx(t)?v(t))?αγ(t)(?h(x(t))+?g(x(t)))γ˙(t)=μ?αγ(t)}。该系统的收敛性可直接由

数值实验：在本节中，我们通过若干简单测试问题进行数值实验，以此展示前几节中所提出的离散算法的数值表现。

结论：我们提出了加速梯度流（1.2）的标准化参数化方法。参数α能够体现时间尺度和阻尼结构。通过标准化变量，该流与传统的加速流建立了联系。这一视角有助于得到不变的稳定性条件。基于这些条件，我们推导出了保持结构的离散化方法。对于复合优化问题，我们还提出了基于速度的近端分裂方法。最后，这种标准化参数化在随机优化领域也可能具有应用价值。

CRediT作者贡献声明：
费关：写作——审阅与编辑，写作——初稿撰写，方法论，形式分析，概念构建。
李子清：研究调查，形式分析，数据整理。
吕凯楠：形式分析，数据整理。
白一光：资金获取，数据整理。
袁静：写作——审阅与编辑，资金获取，形式分析。

利益冲突声明：作者声明不存在任何可能影响本文研究成果的已知财务利益或个人关系。

费关|李子清|吕凯楠|白一光|袁静
浙江师范大学数学科学学院数理医学系，中国金华市321004