投影梯度方法

投影梯度下降（PGD）是一种实用且通常直观的算法，用于处理约束优化问题。这种方法将大家熟悉的梯度下降算法推广，以处理解决方案必须位于特定可行集$\mathcal{C}$中的问题。

核心思想非常简单：执行标准梯度下降更新，如果此步骤导致结果超出可行集$\mathcal{C}$，则将结果点投影回该集合。当可以高效地计算到$\mathcal{C}$的投影时，这种方式特别有效。

约束优化问题

回顾PGD处理的约束优化问题的一般形式： $\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{服从于} \quad \mathbf{x} \in \mathcal{C}$ 在这里，$f(\mathbf{x})$是我们要最小化的目标函数（在机器学习中通常是损失函数），$\mathcal{C}$表示由参数$\mathbf{x}$上的约束定义的可行集。PGD假设$\mathcal{C}$是一个非空、闭合且凸的集合。

投影算子

PGD的重要思想是投影算子，表示为$\Pi_{\mathcal{C}}$。对于参数空间中的任何点$\mathbf{y}$，它在集合$\mathcal{C}$上的投影定义为$\mathcal{C}$中与$\mathbf{y}$欧几里得距离最近的点： $\Pi_{\mathcal{C}}(\mathbf{y}) = \arg \min_{\mathbf{x} \in \mathcal{C}} ||\mathbf{x} - \mathbf{y}||_2^2$ 直观地说，$\Pi_{\mathcal{C}}(\mathbf{y})$在允许的区域$\mathcal{C}$中找到$\mathbf{y}$的“最佳近似”。

PGD的可行性和效率完全取决于此投影的计算容易程度。幸运的是，对于机器学习中遇到的许多常见约束集，投影具有简单的闭合形式解或可以高效计算。

投影示例

1. 盒约束： 如果可行集由逐元素的下限和上限定义，即$\mathcal{C} = \{\mathbf{x} | l_i \le x_i \le u_i \text{ 对于所有 } i\}$，则投影很简单。对于点$\mathbf{y}$，通过裁剪每个分量来计算投影$\mathbf{x} = \Pi_{\mathcal{C}}(\mathbf{y})$： $x_i = \max(l_i, \min(y_i, u_i))$ 一个常见的特例是非负约束（$l_i=0, u_i=\infty$），此时$x_i = \max(0, y_i)$。

2. 欧几里得球（L2范数球）： 如果可行集是半径为$R$且以原点为中心的球体，即$\mathcal{C} = \{\mathbf{x} | ||\mathbf{x}||_2 \le R\}$，则投影为： $\Pi_{\mathcal{C}}(\mathbf{y}) = \begin{cases} \mathbf{y} & \text{如果 } ||\mathbf{y}||_2 \le R \\ R \frac{\mathbf{y}}{||\mathbf{y}||_2} & \text{如果 } ||\mathbf{y}||_2 > R \end{cases}$ 如果点$\mathbf{y}$已经在球体内部或边界上，它保持不变。如果它在外部，则会沿径向按比例缩小，使其位于边界上。

3. 概率单纯形： 如果可行集要求参数为非负且和为一，即$\mathcal{C} = \{\mathbf{x} | \sum_i x_i = 1, x_i \ge 0\}$，则投影更复杂，但存在高效算法，通常基于排序和寻找适当的阈值。

如果到$\mathcal{C}$的投影计算成本高昂（例如，需要解决另一个优化问题），那么PGD可能不是最实用的选择。

投影梯度下降算法

PGD算法通过两个步骤迭代更新参数$\mathbf{x}$：

1. 梯度步骤： 通过在负梯度方向上迈出一步来计算中间点$\mathbf{y}_{k+1}$，就像标准梯度下降一样： $\mathbf{y}_{k+1} = \mathbf{x}_k - \eta_k \nabla f(\mathbf{x}_k)$ 这里，$\mathbf{x}_k$是当前参数向量，$\nabla f(\mathbf{x}_k)$是目标函数在$\mathbf{x}_k$处的梯度，$\eta_k$是迭代$k$时的学习率。

2. 投影步骤： 将中间点$\mathbf{y}_{k+1}$投影回可行集$\mathcal{C}$以获得下一个迭代点$\mathbf{x}_{k+1}$： $\mathbf{x}_{k+1} = \Pi_{\mathcal{C}}(\mathbf{y}_{k+1})$

此过程重复进行，直到满足某个收敛标准（例如，$\mathbf{x}$或$f(\mathbf{x})$的变化很小，或达到最大迭代次数）。

单次PGD步骤的可视化。灰色阴影区域表示可行集$\mathcal{C}$。从$\mathbf{x}_k$开始，梯度步骤导致$\mathbf{y}_{k+1}$超出$\mathcal{C}$。投影$\Pi_{\mathcal{C}}$将$\mathbf{y}_{k+1}$映射到$\mathcal{C}$内最近的点$\mathbf{x}_{k+1}$。

学习率选择

学习率$\eta_k$的选择遵循与无约束梯度下降相似的原则。它可以是固定的，遵循衰减计划（例如，$\eta_k = \eta_0 / \sqrt{k}$），或者由适用于投影步骤的线搜索方法确定。一种常用的策略是回溯线搜索，其中$\eta$被减小直到投影步骤满足特定条件（例如，$f(\mathbf{x})$有足够的下降）。

收敛特性

当$f$是凸的且其梯度是Lipschitz连续的，并且可行集$\mathcal{C}$是闭合且凸的，PGD保证收敛到最优解$\mathbf{x}^* \in \mathcal{C}$。收敛速度通常为$O(1/k)$，与标准梯度下降相似。如果$f$也是强凸的，则可以实现线性收敛（对于某些$\rho < 1$为$O(\rho^k)$）。

对于非凸函数$f$，PGD通常收敛到满足一阶必要条件（与KKT条件相关）的驻点，但不保证全局最优性。

机器学习中的应用

PGD应用于涉及约束的各种机器学习情况：

1. 非负最小二乘/矩阵分解： 像非负矩阵分解（NMF）这样的问题要求因子矩阵具有非负的元素。带有到非负卦限（$\mathbf{x} \ge 0$）投影的PGD是一种常用方法。
2. 受约束的参数空间： 训练模型时，权重需要满足特定边界（例如，$|w_i| \le C$或$||\mathbf{w}||_2 \le R$）。带有盒约束或L2球投影的PGD可以强制执行这些约束。
3. 通过约束进行正则化： 有时，正则化被表述为约束（例如，在$||\mathbf{w}||_1 \le \lambda$的条件下最小化损失），而不是添加惩罚项。如果到相应范数球的投影是可行的（到L1球的投影是可能的，但比L2复杂），则可以应用PGD。
4. 对抗样本生成（PGD攻击）： 在对抗机器学习中，PGD是寻找对抗样本的标准方法。它对损失函数执行投影梯度上升，目标是输入数据，同时受约束于扰动输入与原始输入保持接近（例如，在$L_\infty$或$L_2$范数球内）。投影步骤确保扰动保持在允许的范围内。

实现考量与局限

实现PGD需要：

• 一个计算梯度$\nabla f(\mathbf{x})$的函数。
• 一个计算投影$\Pi_{\mathcal{C}}(\mathbf{y})$的函数。
• 选择学习率$\eta_k$的策略。

投影梯度下降的伪代码：

在C中初始化x_0
设置学习率策略（例如，固定η或计划）
k = 0
当未收敛时：
    # 计算梯度
    g_k = ∇f(x_k)

    # 梯度步骤
    y_{k+1} = x_k - η_k * g_k

    # 投影步骤
    x_{k+1} = Π_C(y_{k+1})

    # 更新迭代计数
    k = k + 1

返回 x_k

PGD的主要局限性在于它依赖于高效的投影算子。如果$\mathcal{C}$由复杂的、耦合的约束（例如，一般的线性或非线性等式/不等式）定义，计算投影可能与解决原始问题一样困难。在这种情况下，增广拉格朗日法或内点法等其他方法可能更合适。

此外，PGD有时会表现出收敛缓慢，特别是如果无约束梯度步骤经常指向远离可行集的方向，导致投影步骤显著缩短有效步长。这可能导致沿$\mathcal{C}$边界的“之字形”行为。

尽管存在这些局限，投影梯度下降仍然是处理参数受简单约束的优化问题的有价值且广泛使用的工具，它提供了梯度下降的一种自然扩展，在整个优化过程中明确保持可行性。