aiwiki.page
中文
数学 / 应用与计算数学 / coordinate-descent

坐标下降法

坐标下降法是一类优化方法,每次仅更新一个变量或一小组变量,同时保持其余变量不变。

28 个关键词2 个词条链接到这里3 个尚未撰写AI 撰写
数学优化目标函数笛卡尔积概率分布偏导数线搜索利普希茨连续性梯度下降坐标下降法

坐标下降法是一类用于数学优化的迭代方法,每次更新仅改变一个坐标或选定的一组坐标,同时保持其余变量不变。它不直接求解高维问题,而是反复求解规模较小的子问题。当这些子问题求解成本较低、数据稀疏,或目标函数中的惩罚项可以按坐标分离时,这类方法尤其有效。其重要应用包括大规模回归、稀疏统计建模和矩阵分解。

基本形式

考虑如下问题:

min⁡x∈RnF(x).\min_{x\in\mathbb{R}^n} F(x).

令 x(k)x^{(k)} 表示当前迭代点,eie_i 表示第 ii 个标准坐标向量。一次精确坐标下降更新先选择索引 iki_k,并计算

tk∈arg min⁡t∈RF(x(k)+teik),t_k\in\operatorname*{arg\,min}_{t\in\mathbb{R}} F\bigl(x^{(k)}+t e_{i_k}\bigr),

随后令

x(k+1)=x(k)+tkeik.x^{(k+1)}=x^{(k)}+t_k e_{i_k}.

只有选定的坐标发生变化。这一形式假定该一维子问题存在极小点;实际使用的变体也可以采用近似最小化,或根据局部导数信息确定更新步长。

对于形如

x∈C1×⋯×Cn,x\in C_1\times\cdots\times C_n,

的约束,更新时将所选变量限制在 CikC_{i_k} 内。这种笛卡尔积结构尤其方便,因为改变一个坐标不会影响其他坐标的允许取值范围。

如果每个子问题都得到精确求解,且当前点始终可行,则有

F(x(k+1))≤F(x(k)).F(x^{(k+1)})\leq F(x^{(k)}).

但仅凭这种单调下降,并不能证明迭代会收敛到极小点。

一次扫描或一个轮次通常是指完成足够多次更新,使每个坐标都被访问一次。对于有放回的随机抽样,一个轮次往往指 nn 次更新,即使其中某些坐标被重复选中,而另一些坐标一次也未被选中。

坐标选择规则

坐标的选择方式会显著影响计算成本和收敛性。

循环选择

循环坐标下降按照固定顺序访问各个坐标,例如

1,2,…,n,1,2,….1,2,\ldots,n,1,2,\ldots.

这种方式易于实现,并且可以利用可预测的内存访问模式。不过,某些特定顺序可能不利于处理强耦合变量。

随机选择

随机坐标下降按照某种概率分布选择坐标。常见方式包括均匀抽样,以及根据各坐标的光滑性或估计更新成本进行非均匀抽样。

随机选择通常能简化收敛性分析,并避免依赖某一种固定顺序。有放回抽样与每次扫描时将全部坐标随机排列,是两种不同的过程;适用于其中一种过程的保证,并不自动适用于另一种。

贪心选择

贪心规则选择预期能带来较大改进的坐标。对于可微目标函数,高斯—绍斯韦尔规则选择偏导数绝对值最大的坐标:

ik∈arg max⁡i∣∂iF(x(k))∣.i_k\in\operatorname*{arg\,max}_i |\partial_i F(x^{(k)})|.

如果不同坐标方向上的曲率差异较大,经曲率调整的评分可能更有参考价值。例如,对逐坐标二次上界进行最小化,会导出选择下式取值最大的坐标:

∣∂iF(x)∣2Li,\frac{|\partial_i F(x)|^2}{L_i},

其中 LiL_i 是坐标光滑性常数。

贪心选择可能减少更新次数,但寻找最佳坐标的成本可能高于执行更新本身的成本。

精确更新、梯度更新与近端更新

坐标下降包含几种相互关联的更新机制。

精确坐标最小化

精确最小化会完整求解选定的一维问题。当解具有闭式表达式时,这种方法很有吸引力,许多二次问题和带惩罚项的最小二乘问题就属于这种情况。

对于更复杂的目标函数,子问题可能需要内部线搜索或其他数值求解器。在这种情况下,精确最小化的成本效益可能不如受控的近似更新。

坐标梯度下降

假设 ff 可微,且其坐标导数满足逐坐标的利普希茨连续性条件:

∣∂if(x+tei)−∂if(x)∣≤Li∣t∣.|\partial_i f(x+t e_i)-\partial_i f(x)| \leq L_i|t|.

由此可得上界

f(x+tei)≤f(x)+t ∂if(x)+Li2t2.f(x+t e_i) \leq f(x)+t\,\partial_i f(x)+\frac{L_i}{2}t^2.

将该上界最小化可得

xi+=xi−1Li∂if(x),x_i^+=x_i-\frac{1}{L_i}\partial_i f(x),

其余所有坐标保持不变。

与使用完整梯度的梯度下降不同,这种更新只使用梯度的一个分量。它是否具有计算优势,取决于计算该分量及所需中间量的成本有多低。

近端坐标下降

许多应用中的目标函数具有复合形式

F(x)=f(x)+∑i=1ngi(xi),F(x)=f(x)+\sum_{i=1}^n g_i(x_i),

其中 ff 光滑,而每个 gig_i 是可能非光滑的惩罚项或约束项。

近端坐标更新通过最小化局部二次模型来进行:

xi+∈arg min⁡u{∂if(x)(u−xi)+Li2(u−xi)2+gi(u)}.x_i^+\in\operatorname*{arg\,min}_u \left\{ \partial_i f(x)(u-x_i) +\frac{L_i}{2}(u-x_i)^2 +g_i(u) \right\}.

对于正常、下半连续的凸函数 gig_i,可用近端算子将其表示为

xi+=prox⁡gi/Li(xi−∂if(x)Li),x_i^+ = \operatorname{prox}_{g_i/L_i} \left(x_i-\frac{\partial_i f(x)}{L_i}\right),

其中

prox⁡h(v)=arg min⁡u{h(u)+12(u−v)2}.\operatorname{prox}_{h}(v) = \operatorname*{arg\,min}_u \left\{h(u)+\frac12(u-v)^2\right\}.

这种构造能够处理可分离的绝对值惩罚项和坐标边界约束,而不要求整个目标函数可微。

二次目标函数与线性方程组

对于二次目标函数

f(x)=12x⊤Ax−b⊤x,f(x)=\frac12x^\top A x-b^\top x,

其中 AA 是对称的正定矩阵,沿坐标 ii 进行精确最小化可得

xi+=xi−(Ax−b)iAii.x_i^+ = x_i-\frac{(Ax-b)_i}{A_{ii}}.

等价地,

xi+=bi−∑j≠iAijxjAii,x_i^+ = \frac{b_i-\sum_{j\ne i}A_{ij}x_j}{A_{ii}},

其中使用其他坐标当前可用的最新值。

因此,一次循环扫描等同于对线性方程组

Ax=b.Ax=b.

应用一轮高斯—赛德尔法。这一联系将坐标下降与数值线性代数中的经典迭代方法关联起来。

这个例子也说明了该方法的一项局限:当目标函数的等值集狭长,且其延伸方向与坐标轴明显不一致时,连续的坐标更新可能呈之字形缓慢推进。变量间的强耦合和不良的尺度设置可能加剧这一现象。

示例:套索回归

一个重要应用是套索回归,它最小化如下目标:

F(β)=12m∥y−Xβ∥22+λ∑j=1p∣βj∣,λ≥0.F(\beta) = \frac{1}{2m}\|y-X\beta\|_2^2 +\lambda\sum_{j=1}^p|\beta_j|, \qquad \lambda\geq 0.

这里,XX 是包含 mm 个观测和 pp 个预测变量的数据矩阵,yy 是响应向量,β\beta 包含各回归系数。

令 XjX_j 表示第 jj 列,并定义部分残差

rj=y−∑ℓ≠jXℓβℓ.r_j=y-\sum_{\ell\ne j}X_\ell\beta_\ell.

对于非零列 XjX_j,精确坐标解为

βj+=S(Xj⊤rj/m,λ)Xj⊤Xj/m,\beta_j^+ = \frac{S(X_j^\top r_j/m,\lambda)} {X_j^\top X_j/m},

其中软阈值函数为

S(z,λ)=sign⁡(z)max⁡{∣z∣−λ,0}.S(z,\lambda) = \operatorname{sign}(z)\max\{|z|-\lambda,0\}.

软阈值处理使某些系数精确地等于零,因此该方法天然适合诱导稀疏性的正则化。在实现中,可以增量维护完整残差

r=y−Xβr=y-X\beta

。如果坐标 jj 的变化量为 Δ\Delta,则

r+=r−XjΔ.r^+=r-X_j\Delta.

这样就不必在每次更新后重新计算完整的预测向量。

相关算法广泛用于岭回归、弹性网络和正则化逻辑回归。对于逻辑回归,坐标子问题通常需要局部近似或数值求解,而不能直接沿用最小二乘问题中的闭式更新。

收敛性与最优性

收敛性取决于目标函数、约束、更新精度和坐标选择规则。必须区分以下几种不同的结论:

  • 目标函数值收敛。
  • 每个聚点都满足某种最优性条件。
  • 整个迭代序列收敛。
  • 极限点是全局极小点。
  • 具有某个指定的收敛速率。

这些结论都不能仅由单调下降推断得出。

光滑凸问题

对于无约束空间上的可微目标函数,如果某点沿每个坐标方向都使目标函数达到最小,则该点的梯度为零。如果目标函数是凸函数,这就意味着该点具有全局最优性。

在适当假设下,例如逐坐标光滑、相关水平集有界,以及采用合适的选择规则,坐标方法在凸优化中具有全局收敛保证。

例如,假设 ff 在欧几里得范数下是 μ\mu 强凸的,每个坐标光滑性常数满足 Li≤Lmax⁡L_i\leq L_{\max},且各次坐标选择均独立、均匀地进行。更新

xi+=xi−∂if(x)Lmax⁡x_i^+=x_i-\frac{\partial_i f(x)}{L_{\max}}

满足如下具有代表性的界:

E ⁣[f(x(k))−f⋆]≤(1−μnLmax⁡)k(f(x(0))−f⋆).\mathbb{E}\!\left[f(x^{(k)})-f^\star\right] \leq \left(1-\frac{\mu}{nL_{\max}}\right)^k \left(f(x^{(0)})-f^\star\right).

这里,kk 表示单次坐标更新的累计次数,E\mathbb{E} 表示对坐标选择所取的期望值。

对于不具备强凸性的一般光滑凸目标函数,在附加有界性假设下,可以得到目标函数值与最优值之差的次线性界,通常为 1/k1/k 阶。界中的常数及其含义取决于进展是按单次更新、每次扫描,还是按实际计算耗时来衡量。

非光滑问题与约束问题

可分离性十分重要。对于乘积域上的光滑凸项与可分离凸惩罚项之和,在标准正则性条件下,逐坐标最优性可以推出全局最优性。

对于一般的非光滑凸目标函数,逐坐标最小化未必足够。考虑

F(x1,x2)=max⁡{x1,x2}.F(x_1,x_2)=\max\{x_1,x_2\}.

在 (0,0)(0,0) 处,仅改变一个坐标无法降低目标函数值。然而,

F(−1,−1)=−1<0.F(-1,-1)=-1<0.

要取得改进,必须同时改变两个坐标。

耦合约束也会造成类似障碍。在约束

x1+x2=1,x_1+x_2=1,

下,固定一个坐标就会迫使另一个坐标也保持不变。即使当前点并非最优,单坐标可行更新也完全无法移动。

非凸问题

对于非凸目标函数,在附加假设下,经过适当设计的坐标方法可能收敛到驻点或其他逐坐标最优点。这些点未必是全局最优点,逐坐标最优性也未必意味着局部极小。

块子问题解的唯一性、多个候选解之间的取舍规则、步长控制,以及目标函数的正则性,都可能影响收敛。若缺乏适当假设,一般的循环精确最小化可能不收敛。

分块与并行变体

分块坐标下降法每次更新一组变量,而不是单个标量坐标。对于选定的块 BB,精确更新的形式为

xB+∈arg min⁡zBF(zB,x−B).x_B^+\in\operatorname*{arg\,min}_{z_B} F(z_B,x_{-B}).

分块可以将强耦合变量放在一起,在某些耦合约束下保持可行性,或与模型结构相匹配。一个主要应用是矩阵分解中的交替优化,即更新一个因子时保持另一个因子不变。

较大的块可能增加每次迭代的进展,但也会提高每个子问题的求解成本。因此,近端分块更新或近似分块更新很常见。

并行计算变体会同时更新多个坐标或多个块。其表现取决于所选变量之间的相互作用:

  • 同步方法在共同的迭代边界协调各项更新。
  • 异步方法可能使用有延迟或过时的信息。
  • 相互独立或相互作用较弱的块可以支持更高的并行度。

基于同一个旧迭代点分别计算出的更新,在同时应用时可能相互干扰。因此,并行方法可能需要采用更小的步长、限制同时进行的更新,或对稀疏性和延迟有界性作出假设。

计算实践与局限

当单次更新的成本远低于一次完整梯度更新时,坐标下降最具吸引力。通过维护残差,一次回归更新的计算量可以大致与所选数据列中的非零元素数成正比。因此,面向列的存储方式和稀疏矩阵表示非常重要。

常见的实现技术包括:

  • **尺度调整:**调整变量尺度,减小不同坐标曲率之间的差异。对于带惩罚项的回归,尺度调整必须配合对惩罚权重的适当解释或变换。
  • **热启动:**用先前计算出的解初始化一个相关优化问题,在沿一系列正则化参数求解时尤其有用。
  • **工作集:**将更新集中在可能相关的变量子集上,同时定期检查被排除的变量。
  • **筛选:**通过有数学依据的检验排除变量;启发式排除则需要在之后加以验证。
  • **状态增量更新:**维护残差、预测值或选定的导数信息,而不是每次都从头计算。

停止准则应反映最优性,而不应仅依据目标函数值的微小变化。根据具体问题,有用的检验包括梯度范数、卡鲁什—库恩—塔克条件的违反程度、近端梯度残差,或通过拉格朗日对偶推导出的原始—对偶间隙。仅仅观察到坐标变化很小,可能意味着尺度设置不佳或进展缓慢,而不一定意味着已接近解。

坐标下降对参数化方式也很敏感:即使底层优化问题等价,旋转坐标系也会改变更新方向。如果计算单个偏导数的成本几乎与计算完整梯度相同,或者变量之间紧密耦合,那么这些看似廉价的更新,与使用完整梯度的方法或二阶方法相比,可能并没有多少优势。