近端算法：通过拆分问题求解“不可解”之题

0$，作用于点 $\mathbf{v}$ 的 $g$ 的[近端算子](/sciencepedia/feynman/keyword/proximal_operators)定义为： $$ \text{prox}_{\gamma g}(\mathbf{v}) = \arg\min_{\mathbf{u}} \left( g(\mathbf{u}) + \frac{1}{2\gamma} \|\mathbf{u} - \mathbf{v}\|_2^2 \right) $$ 这个定义可能看起来令人生畏，但其含义却非常直观。它告诉我们去寻找一个新的点 $\mathbf{u}$，这个点在两个相互竞争的目标之间达到了完美平衡： 1. 使 $g(\mathbf{u})$ 的值变小（这是“最小化 $g$”的部分）。 2. 保持与原始点 $\mathbf{v}$ 接近（这是二次惩罚项 $\|\mathbf{u} - \mathbf{v}\|_2^2$ 的部分）。 [近端算子](/sciencepedia/feynman/keyword/proximal_operators)是一种广义的投影。它取一个点 $\mathbf{v}$，然后找到一个“最佳”的邻近点，该点遵循由 $g$ 编码的结构。这是一种[去噪](/sciencepedia/feynman/keyword/denoising)、正则化或校正的操作。 真正的魔力在于当我们在实践中看到这个抽象算子的作用时。对于我们棘手的 L1 范数 $g(\mathbf{x}) = \lambda \|\mathbf{x}\|_1$，其[近端算子](/sciencepedia/feynman/keyword/proximal_operators)原来是一个非常简单而优雅的函数，称为**​[软阈值](/sciencepedia/feynman/keyword/soft_thresholding)算子** (soft-thresholding operator)。它作用于向量 $\mathbf{v}$ 的每个分量 $v_i$，形式如下： $$ S_{\gamma\lambda}(v_i) = \text{sign}(v_i) \max(|v_i| - \gamma\lambda, 0) $$ 这个函数的作用正合我们心意！它取一个值 $v_i$，将其向零收缩一个量 $\gamma\lambda$，如果这个值已经足够小（小于 $\gamma\lambda$），就将其精确地设为零。这个简单的非线性操作是实现稀疏性的基本构件。抽象的[近端算子](/sciencepedia/feynman/keyword/proximal_operators)概念具体化为一个强大而具体的工具。这个思想也是高度模块化的；对于更复杂的正则化项，如结合了 L1 和 L2 惩罚的[弹性网络](/sciencepedia/feynman/keyword/elastic_net)，类似的“微积分”法则使我们能够推导出其同样优雅的[近端算子](/sciencepedia/feynman/keyword/proximal_operators)。 ### 前向后向之舞 现在我们有了两个工具：用于光滑部分 $f$ 的梯度，和用于非光滑部分 $g$ 的[近端算子](/sciencepedia/feynman/keyword/proximal_operators)。**[近端梯度法](/sciencepedia/feynman/keyword/proximal_gradient_methods)** (proximal gradient method) 通过优美的两步舞将它们结合起来： $$ \mathbf{x}_{k+1} = \text{prox}_{\gamma g}(\mathbf{x}_k - \gamma \nabla f(\mathbf{x}_k)) $$ 让我们将这个迭代过程，也称为**前向后向分裂** (Forward-Backward Splitting)，分解为两个步骤： 1. **前向步（预测）：** 我们首先计算 $\mathbf{v}_k = \mathbf{x}_k - \gamma \nabla f(\mathbf{x}_k)$。这是对[光滑函数](/sciencepedia/feynman/keyword/smooth_functions) $f$ 的标准[梯度下降](/sciencepedia/feynman/keyword/gradient_descent)步。它是基于景观的光滑部分对我们应该走向何方做出的“前向”预测。 2. **后向步（校正）：** 然后我们将[近端算子](/sciencepedia/feynman/keyword/proximal_operators)应用于我们的预测：$\mathbf{x}_{k+1} = \text{prox}_{\gamma g}(\mathbf{v}_k)$。这是“后向”校正。它获取暂定点 $\mathbf{v}_k$，并将其轻轻[拉回](/sciencepedia/feynman/keyword/pullback)到一个更好地符合 $g$ 所要求的结构（例如，[稀疏性](/sciencepedia/feynman/keyword/sparsity)）的邻近点。 这种“梯度预测，近端校正”之舞是该[算法](/sciencepedia/feynman/keyword/algorithm)的核心。当然，这种舞蹈必须恰到好处。前向步不能太激进。我们必须选择一个足够小的步长 $\gamma$，通常满足 $\gamma \le 1/L$，其中 $L$ 是 $f$ 梯度的李普希兹常数（衡量其最大“陡峭度变化”的指标）。这能确保我们的预测不会偏离太远，以至于近端校正无法有效发挥作用。 ### 性能与回报 这支优雅的舞蹈值得付出努力吗？人们可能会怀疑这样一种复杂的[算法](/sciencepedia/feynman/keyword/algorithm)计算成本会很高。令人惊讶而又美妙的答案是：不会。 让我们将[近端梯度法](/sciencepedia/feynman/keyword/proximal_gradient_methods)与一种更朴素的非光滑问题解决方法——[次梯度法](/sciencepedia/feynman/keyword/subgradient_method)进行比较。在每次迭代的基础上，两种[算法](/sciencepedia/feynman/keyword/algorithm)的主要计算成本几乎总是光滑部分梯度 $\nabla f(\mathbf{x})$ 的计算，这通常涉及大型矩阵向量乘积。相比之下，[近端梯度法](/sciencepedia/feynman/keyword/proximal_gradient_methods)所做的“额外”工作——应用[软阈值](/sciencepedia/feynman/keyword/soft_thresholding)算子——在计算上是微不足道的，其复杂度与[向量的大小](/sciencepedia/feynman/keyword/magnitude_of_a_vector)成线性关系。因此，我们用几乎相同的每步计算成本，得到了一个好得多的[算法](/sciencepedia/feynman/keyword/algorithm)。 回报在于[收敛速度](/sciencepedia/feynman/keyword/rates_of_convergence)。当简单的[次梯度法](/sciencepedia/feynman/keyword/subgradient_method)以大约 $\mathcal{O}(1/\sqrt{k})$ 的[收敛速度](/sciencepedia/feynman/keyword/rates_of_convergence)缓慢地走向解时，[近端梯度法](/sciencepedia/feynman/keyword/proximal_gradient_methods)以快得多的 $\mathcal{O}(1/k)$ 速率飞速前进。这好比是走一条蜿蜒低效的山路，与走一系列聪明直接的Z字形回头弯路之间的区别。 ### 看不见的收敛机制 为什么这个过程能如此可靠地引导我们找到解？该[算法](/sciencepedia/feynman/keyword/algorithm)本质上是在寻找一个**​[不动点](/sciencepedia/feynman/keyword/fixed_points)** (fixed point)——一个特殊的点 $\mathbf{x}^*$，当它被代入更新规则时，会保持不变。这个[不动点方程](/sciencepedia/feynman/keyword/fixed_point_equation) $\mathbf{x}^* = \text{prox}_{\gamma g}(\mathbf{x}^* - \gamma \nabla f(\mathbf{x}^*))$，恰好是我们原始问题的[最优性条件](/sciencepedia/feynman/keyword/optimality_conditions)。[算法](/sciencepedia/feynman/keyword/algorithm)之所以收敛，是因为每次迭代都使我们更接近满足这个条件。 驱动这种收敛的引擎是[近端算子](/sciencepedia/feynman/keyword/proximal_operators)本身优美的几何性质。[近端算子](/sciencepedia/feynman/keyword/proximal_operators)是**非扩张的** (non-expansive)，意味着它们从不将两个点推得更远。事实上，它们是**强非扩张的** (firmly non-expansive)，这是一个更强的性质，保证它们总是在特定意义上将点拉得更近。这种收缩性质确保了迭代过程是稳定的，[并系](/sciencepedia/feynman/keyword/paraphyly)统地朝解集前进。 这个前进的速度取决于目标函数 $F(\mathbf{x})$ 的几何形状。如果函数在其最小值附近具有“碗状”形状——这一性质由[强凸性](/sciencepedia/feynman/keyword/strong_convexity)或更弱的**二次增长 (QG) 条件**等条件捕捉——收敛速度可以显著加快。对于满足 QG 条件的函数，即使是一个称为近端点[算法](/sciencepedia/feynman/keyword/algorithm)的非常简单的变体，也能以线性速率收敛，这意味着到解的距离在每一步都会缩小一个常数因子。这揭示了一个深刻而优美的联系：问题空间的几何形状决定了[算法](/sciencepedia/feynman/keyword/algorithm)的动力学。 ### 分裂[算法](/sciencepedia/feynman/keyword/algorithm)大观 前向后向之舞只是庞大而耀眼的[近端算法](/sciencepedia/feynman/keyword/proximal_algorithms)星系中的一颗星。它代表了一种已被多种强大方式扩展的设计原则。 - **处理更多的非光滑性：** 如果 $f$ 和 $g$ 都是非光滑的怎么办？[近端梯度法](/sciencepedia/feynman/keyword/proximal_gradient_methods)就[无能](/sciencepedia/feynman/keyword/anergy)为力了。但分裂原则可以被推广。像**​[交替方向乘子法](/sciencepedia/feynman/keyword/alternating_direction_method_of_multipliers) (ADMM)** 和 **Douglas-Rachford 分裂 (DRS)** 这样的[算法](/sciencepedia/feynman/keyword/algorithm)可以*仅*使用 $f$ 和 $g$ 各自的[近端算子](/sciencepedia/feynman/keyword/proximal_operators)来解决 $f(x) + g(x)$ 形式的问题，展示了近端框架令人难以置信的模块化特性。另一种策略是使用其 Moreau 包络对其中一个函数进行轻微的“平滑化”，然后应用标准的[近端梯度法](/sciencepedia/feynman/keyword/proximal_gradient_methods)。 - **追求速度：** 我们能更快吗？通过引入**动量** (momentum)——利用前几步的信息来指导当前步——我们得到了像 **[FISTA](/sciencepedia/feynman/keyword/fista)** 这样的“加速”方法。这些[算法](/sciencepedia/feynman/keyword/algorithm)为凸问题实现了最优的[收敛速率](/sciencepedia/feynman/keyword/convergence_rates)。但这种速度是有代价的。与其更简单的同类[算法](/sciencepedia/feynman/keyword/algorithm) ISTA 稳定、单调的下降路径不同，[FISTA](/sciencepedia/feynman/keyword/fista) 通往解的路径可能是[振荡](/sciencepedia/feynman/keyword/oscillation)和非单调的。这催生了巧妙的**自适应重启策略**的设计，其作用就像一个熟练的司机，知道何时轻踩刹车以防打滑，同时仍能高速过弯。 - **非凸前沿：** 也许最引人注目的是，[近端算法](/sciencepedia/feynman/keyword/proximal_algorithms)的力量远远超出了行为良好的[凸优化](/sciencepedia/feynman/keyword/convex_optimization)世界。机器学习中的许多前沿问题都是非凸的，具有许多局部最小值的复杂景观。令人惊讶的是，[近端梯度法](/sciencepedia/feynman/keyword/proximal_gradient_methods)在实践中对于这些问题也常常表现得非常好。理解这一现象的关键在于一个深刻的几何性质，称为**Kurdyka-Łojasiewicz (KL) 性质**​。一大[类函数](/sciencepedia/feynman/keyword/class_function)，包括实践中使用的几乎所有函数——即使是像 $\ell_0$ 伪范数（用于计数非零项）或 $\ell_p$ 拟范数这样的奇怪的非凸惩罚项——都满足这个条件。KL 性质充当了一种局部几何正则性，保证了即使在复杂、非凸的景观中，[算法](/sciencepedia/feynman/keyword/algorithm)的迭代也不会无限循环，而是被迫收敛到一个[临界点](/sciencepedia/feynman/keyword/critical_points)。 从[梯度下降](/sciencepedia/feynman/keyword/gradient_descent)的一个简单失效点出发，我们探索了一种强大的分裂原则，发现了一个能处理非光滑性的优雅算子，并将其组装成一个高效的[算法](/sciencepedia/feynman/keyword/algorithm)。我们已经看到，这个核心思想如何发展成一个丰富的方法家族，推动了可解问题的边界，揭示了函数几何与[计算动力学](/sciencepedia/feynman/keyword/computational_kinetics)之间深刻而统一的相互作用。 ]]>