投影梯度方法

投影梯度下降 (gradient descent)（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})$是我们要最小化的目标函数（在机器学习 (machine learning)中通常是损失函数 (loss function)），$\mathcal{C}$表示由参数 (parameter)$\mathbf{x}$上的约束定义的可行集。PGD假设$\mathcal{C}$是一个非空、闭合且凸的集合。

投影算子

PGD的重要思想是投影算子，表示为$\Pi_{\mathcal{C}}$。对于参数 (parameter)空间中的任何点$\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的可行性和效率完全取决于此投影的计算容易程度。幸运的是，对于机器学习 (machine learning)中遇到的许多常见约束集，投影具有简单的闭合形式解或可以高效计算。

投影示例

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可能不是最实用的选择。

投影梯度下降 (gradient descent)算法

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

1. 梯度步骤： 通过在负梯度方向上迈出一步来计算中间点$\mathbf{y}_{k+1}$，就像标准梯度下降一样： $\mathbf{y}_{k+1} = \mathbf{x}_k - \eta_k \nabla f(\mathbf{x}_k)$ 这里，$\mathbf{x}_k$是当前参数向量 (vector)，$\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)$，与标准梯度下降 (gradient descent)相似。如果$f$也是强凸的，则可以实现线性收敛（对于某些$\rho < 1$为$O(\rho^k)$）。

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

机器学习 (machine learning)中的应用

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

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

实现考量与局限

实现PGD需要：

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

投影梯度下降 (gradient descent)的伪代码：

在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}$边界的“之字形”行为。

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