Lecture 08 · Proximal Gradient Descent

References

• Lecture: https://www.stat.cmu.edu/~ryantibs/convexopt-F18/
• Reading: 最优化：建模、算法与理论，刘浩洋等，第 8.1 节、第 8.3 节.

1. Proximal Gradient Descent

1.1 Decomposable Functions (Composite Objective)

在统计建模中, 目标函数经常能够分解成两个部分的和, 其中一个部分是光滑的, 另一个部分是非光滑的. 例如, Lasso 回归中的目标函数可以分解为平方损失函数(光滑)和 L1 正则化项(非光滑). 形式化地, (暂时只考虑凸函数) 我们可以将目标函数表示为:

$$F(x)=\varphi (x)+h(x)$$

• $\varphi$ 是光滑凸函数, 不妨令 $\text{dom}(\varphi )={\mathbb{R}}^n$. (更一般地, 只需 $\varphi$ 在算法迭代点所在区域可微且 $\nabla \varphi$ 满足 Lipschitz 条件; 若 $\varphi$ 的定义域带来约束, 可将对应指示函数并入 $h$.)
• $h$ 是非光滑的凸函数, 但具有简单的结构, 使得我们能够高效地计算其近端算子(proximal operator).

在处理这样的优化问题时传统的梯度下降方法可能无法直接应用, 因为 $h$ 的非光滑性会导致梯度不存在; 而若直接使用次梯度方法, 则可能会导致收敛速度较慢.

因此我们需要一种新的优化方法来处理这种分解结构的目标函数, 这就是近端梯度下降(Proximal Gradient Descent) 方法. 其对于光滑的部分 $\varphi$ 使用梯度信息, 对于非光滑的部分 $h$ 则利用其近端算子来进行优化.

回顾一下, 传统的梯度下降方法在每一步迭代中更新参数 $x$ 的方式为: $x^{+}=x-t\Delta x$. 我们选择 $\Delta x=\nabla f(x)$, 是因为对 $f(z)$ 在 $x$ 处做一阶近似并加上二次正则后, 有:

$$f(z)\approx f(x)+\nabla f(x{)}^{\top }(z-x)+\frac{1}{2t}\Vert z-x{\Vert }^2$$

• 其中, 二次项是相当于将泰勒展开中的二次项 $\frac{1}{2}(z-x{)}^{\top }{\nabla }^{2}f(x)(z-x)$ 用 $\frac{1}{t}I\approx {\nabla }^{2}f(x)$ 来近似的结果.
• 也可理解为: 给一阶线性化模型加上一个强凸的 proximal 正则项, 从而得到步长为 $t$ 的显式更新.
• 而 $\Delta x=\nabla f(x)$ 的选择使得 $x^{+}$ 成为上述近似目标函数的最小值: $x^{+}=\arg {\min }_{z}f(x)+\nabla f(x{)}^{\top }(z-x)+\frac{1}{2t}\Vert z-x{\Vert }^2$.

在当前的 Decomposable/Composite Objective 设置中, 先区分原问题的全局最优点与一步更新点:

$$x^{\ast }=\arg \underset{z}{\min }\left[\varphi (z)+h(z)\right].$$

在当前点 $x$ 处定义局部上界模型(surrogate)

$$\boxed{x^{+}:=\arg \underset{z}{\min }{Q}_t(z,x),Q_t(z,x):=\varphi (x)+\nabla \varphi (x{)}^{\top }(z-x)+\frac{1}{2t}\Vert z-x{\Vert }^2+h(z).}$$

对 $Q_t(z,x)$ 做配方并去掉与 $z$ 无关项, 可得

$$\boxed{x^{+}=\arg \underset{z}{\min }\left[h(z)+\frac{1}{2t}{\Vert z-(x-t\nabla \varphi (x))\Vert }^2\right]={\mathrm{prox}}_{th}(x-t\nabla \varphi (x)).}$$

• 这个更新步骤的核心思想是: 在每次迭代中, 首先对光滑部分 $\varphi$ 进行梯度下降的更新, 得到一个临时变量 $x^{\prime }=x-t\nabla \varphi (x)$; 然后通过最小化包含非光滑部分 $h$ 的二次近似目标函数来得到新的参数 $x^{+}$.

1.2 Proximal Operator

事实上, 上述推导的最后一步, 若将 $x-t\nabla \varphi (x)$ 当作一个新的输入, 那么这就是一个在给定非光滑函数 $h$ 的情况下, 进行近端映射的过程. 即:

$$x^{+}:={\text{prox}}_{th}(x-t\nabla \varphi (x))=\arg \underset{z}{\min }\left[\frac{1}{2t}\Vert z-(x-t\nabla \varphi (x)){\Vert }^2+h(z)\right]$$

Definition (近端算子). 对于一个凸函数 $h:{\mathbb{R}}^n\to (-\infty ,+\infty ]$ (proper, closed, convex), 其近端算子 ${\text{prox}}_h:{\mathbb{R}}^n\to {\mathbb{R}}^n$ 定义为:

$${\text{prox}}_h(x)=\arg \underset{z}{\min }\left[\frac{1}{2}\Vert z-x{\Vert }^2+h(z)\right]$$

• 其中, $x$ 是输入向量, $z$ 是优化变量, 与 $x$ 在同一空间中. 该算子相当于在 $x$ 的基础上进行一个平滑的调整, 使得调整后的点能够在最小化非光滑函数 $h$ 的同时尽可能接近 $x$.

其具有如下性质: 对于适当的闭凸函数 $h$:

• 对任意 $x\in {\mathbb{R}}^n$, ${\text{prox}}_h(x)$ 都是存在且唯一的.
  • 这保证了近端梯度下降方法在每次迭代中都能够得到一个明确的更新结果.
• $u={\text{prox}}_h(x)$ 等价于 $x-u\in \partial h(u)$, 其中 $\partial h(u)$ 是 $h$ 在 $u$ 处的次微分.

  • 近端算子所得到的点 $u$ 与输入点 $x$ 之间的差异正好对应于 $h$ 在 $u$ 处的次梯度信息.

  Proof of the prox/subgradient equivalence

  • 若已知 $u={\text{prox}}_h(x)$, 则 $u$ 是以下优化问题的最小值: ${\min }_v\psi (v):=\frac{1}{2}\Vert v-x{\Vert }^2+h(v)$. 因此 $0\in \partial \psi (u)=u-x+\partial h(u)$, 从而 $x-u\in \partial h(u)$

  • 若 $x-u\in \partial h(u)$, 则由次梯度定义可知 $h(v)\ge h(u)+(x-u{)}^{\top }(v-u)$, 从而

    $$h(v)+\frac{1}{2}\Vert v-x{\Vert }^2\ge h(u)+(x-u{)}^{\top }(v-u)+\frac{1}{2}\Vert v-x{\Vert }^2=h(u)+\frac{1}{2}\Vert u-x{\Vert }^2+\frac{1}{2}\Vert v-u{\Vert }^2\ge h(u)+\frac{1}{2}\Vert u-x{\Vert }^2,$$

    从而 $u={\text{prox}}_h(x)$.

  $\square$

进一步, 用 $t>0$ 来缩放函数 $h$, 则有:

Definition (缩放的近端算子). 对于一个凸函数 $h:{\mathbb{R}}^n\to (-\infty ,+\infty ]$ 以及一个正标量 $t>0$, 其缩放的近端算子 ${\text{prox}}_{th}:{\mathbb{R}}^n\to {\mathbb{R}}^n$ 定义为:

$$\boxed{{\text{prox}}_{th}(x)=\arg \underset{z}{\min }\left[h(z)+\frac{1}{2t}\Vert z-x{\Vert }^2\right]}$$

• 该算子与未缩放的近端算子类似, 但在优化目标中对函数 $h$ 进行了缩放, 这在实际应用中可以调整近端映射的强度.
• 与 $\arg {\min }_z\left[\frac{1}{2}\Vert z-x{\Vert }^2+th(z)\right]$ 的写法完全等价 (只差一个正数倍缩放).
• 上述和次梯度的关系同样成立: $u={\text{prox}}_{th}(x)$ 等价于 $\frac{x-u}{t}\in \partial h(u)$.

Example (${\ell }_1$ 的 prox 算子). 对于 $h(x)=\Vert x{\Vert }_1$ 其中 $x\in {\mathbb{R}}^n$ 及 $t>0$, 其 prox 算子 $u={\text{prox}}_{th}(x)$ 的计算结果为:

$${\text{prox}}_{th}(x)=\text{sign}(x)\odot \max \{|x|-t,0\}$$

1.3 Proximal Gradient Descent Algorithm

对于可分解的凸优化问题:

$$\underset{x\in {\mathbb{R}}^n}{\min }F(x)=\varphi (x)+h(x)$$

• 其中 $\varphi$ 是光滑凸函数, $h$ 是非光滑凸函数. 我们可以通过近端梯度下降算法来求解该问题.
• 事实上, 对于含约束的优化问题同样也可以令 $h(x)={\delta }_{\mathcal{C}}(x)$ (其中 $\mathcal{C}$ 为非空闭凸集) 来将约束条件隐式地包含在非光滑函数中, 从而使得近端梯度下降算法同样适用.

Proximal Gradient Descent 的迭代更新步骤如下:

1. 初始化: 选择一个初始点 $x^{(0)}\in {\mathbb{R}}^n$ 和一个步长参数 $t_0>0$.

2. 迭代更新: 对于 $k=0,1,2,\dots$ 进行以下更新:

   $$\boxed{x^{(k+1)}={\text{prox}}_{t_{k}h}(x^{(k)}-t_k\nabla \varphi (x^{(k)}))}$$
   • 其中, $x^{(k)}$ 是当前迭代的参数, $\nabla \varphi (x^{(k)})$ 是光滑部分 $\varphi$ 在 $x^{(k)}$ 处的梯度, $t_k$ 是步长参数且同样可以设置为常数或通过线搜索等方法自适应调整, ${\text{prox}}_{t_{k}h}$ 是非光滑部分 $h$ 的缩放近端算子.

• 当 $h(x)=0$ 时, 该算法退化为传统的梯度下降方法:

  $$x^{(k+1)}=x^{(k)}-t_k\nabla \varphi (x^{(k)})$$

• 当 $h(x)={\delta }_{\mathcal{C}}(x)$ 时, 该算法退化为投影梯度下降方法:

  $$x^{(k+1)}={\text{Proj}}_{\mathcal{C}}(x^{(k)}-t_k\nabla \varphi (x^{(k)}))$$

观察上述迭代更新, 其还可以等价表述为:

$$\begin{array}{rl}{x}^{(k+1)}& ={\text{prox}}_{t_{k}h}\left(x^{(k)}-t_k\nabla \varphi (x^{(k)})\right)\\ & =x^{(k)}-t_k\cdot \frac{x^{(k)}-{\text{prox}}_{t_{k}h}(x^{(k)}-t_k\nabla \varphi (x^{(k)}))}{t_k}\\ & :=\boxed{x^{(k)}-t_k{G}_{t_k}(x^{(k)})}\\ & =\boxed{x^{(k)}-t_k\nabla \varphi (x^{(k)})-t_k{g}^{(k)}}\end{array}$$

• 其中第三个等式中

  $$G_{t_k}(x^{(k)})=\frac{x^{(k)}-{\text{prox}}_{t_{k}h}[x^{(k)}-t_k\nabla \varphi (x^{(k)})]}{t_k}$$

  被称为近端梯度映射(proximal gradient mapping).

  • 其在某种意义上可以看作是一个综合了光滑部分梯度信息和非光滑部分次梯度信息的复合梯度, 其作用也相当于传统梯度下降法中的搜索方向.

  • Proximal Gradient Mapping 与次梯度的关系为:

    $$\boxed{G_{t_k}(x^{(k)})-\nabla \varphi (x^{(k)})\in \partial h(x^{(k+1)})=\partial h\left(x^{(k)}-t_k{G}_{t_k}(x^{(k)})\right)}(†)$$

  • 此外 $G_{t_k}(x^{(k)})$ 还具有如下性质: $G_{t_k}(x^{(k)})=0$ 当且仅当 $x^{(k)}$ 是 $F(x)=\varphi (x)+h(x)$ 的一个最优解.

• 第四个等式也显式地展示了近端梯度下降相当于对光滑部分进行梯度下降的同时, 对非光滑部分进行隐式梯度下降. 推导如下:

  • 根据更新规则 $x^{(k+1)}={\text{prox}}_{t_{k}h}(x^{(k)}-t_k\nabla \varphi (x^{(k)})):={\text{prox}}_{t_{k}h}(x^{\prime })$ 以及 prox 算子与次梯度的关系, 可知: $x^{\prime }-x^{(k+1)}\in t_k\partial h(x^{(k+1)})$

  • 从而存在 $g^{(k)}\in \partial h(x^{(k+1)})$ 使得 $x^{\prime }-x^{(k+1)}=t_k{g}^{(k)}$, 即

    $$x^{(k+1)}=x^{(k)}-t_k\nabla \varphi (x^{(k)})-t_k{g}^{(k)}$$

2. Examples

2.1 ISTA for Lasso Regression

给定 $y\in {\mathbb{R}}^n$ 和 $X\in {\mathbb{R}}^{n\times p}$, Lasso 回归的目标函数为:

$$\underset{\beta \in {\mathbb{R}}^p}{\min }\underset{\varphi (\beta )}{\underbrace{\frac{1}{2}\Vert y-X\beta {\Vert }_2^2}}+\underset{h(\beta )}{\underbrace{\lambda \Vert \beta {\Vert }_1}}$$

• 其中 $\varphi (\beta )=\frac{1}{2}\Vert y-X\beta {\Vert }_2^2$ 是光滑凸函数, $h(\beta )=\lambda \Vert \beta {\Vert }_1$ 是非光滑凸函数.

• 利用 proximal gradient descent 方法, 首先分别求解梯度与近端算子:

  • $\nabla \varphi (\beta )=X^{\top }(X\beta -y)$
  • ${\text{prox}}_{th}(\beta )=\text{sign}(\beta )\odot \max \{|\beta |-t\lambda ,0\}:=S_{t\lambda }(\beta )$, 其中 $S_{t\lambda }(\cdot )$ 是软阈值函数(soft-thresholding function).

• 因此, proximal gradient descent 的迭代更新步骤为:

  $${\beta }^{(k+1)}=S_{t\lambda }({\beta }^{(k)}-t{X}^{\top }(X{\beta }^{(k)}-y))$$

  该步骤也可以化作如下分步进行的形式:

  • 首先计算一个临时变量 ${\beta }^{\prime }={\beta }^{(k)}-t{X}^{\top }(X{\beta }^{(k)}-y)$, 这相当于对光滑部分 $\varphi$ 进行梯度下降的更新.
  • 然后对 ${\beta }^{\prime }$ 进行软阈值处理 ${\beta }^{(k+1)}=S_{t\lambda }({\beta }^{\prime })=\text{sign}({\beta }^{\prime })\odot \max \{|{\beta }^{\prime }|-t\lambda ,0\}$, 这相当于对非光滑部分 $h$ 进行近端映射的处理.

• 该算法被称为迭代软阈值算法(Iterative Soft-Thresholding Algorithm, ISTA), 是一种求解 Lasso 回归问题的经典方法.

2.2 Low-rank Matrix Completion

给定一个矩阵 $M\in {\mathbb{R}}^{m\times n}$ 以及一个索引集合 $\Omega \subseteq \{1,\dots ,m\}\times \{1,\dots ,n\}$ 表示已知的矩阵元素索引, 低秩矩阵补全的目标函数为:

$$\begin{array}{rlrl}& \underset{X\in {\mathbb{R}}^{m\times n}}{\min }& & \text{rank}(X)\\ & \text{subject to}& & X_{ij}=M_{ij},\forall (i,j)\in \Omega \end{array}$$

该优化问题进一步可以通过 Nuclear Norm 的松弛来转化为如下形式:

$$\begin{array}{rlrl}& \underset{X\in {\mathbb{R}}^{m\times n}}{\min }& & \Vert X{\Vert }_{\ast }\\ & \text{subject to}& & X_{ij}=M_{ij},\forall (i,j)\in \Omega \end{array}$$

• 可以证明该形式是一个凸优化问题.

若进一步考虑到观测数据中可能存在噪声, 则可以将约束条件松弛为一个正则项, 从而得到如下优化问题:

$$\underset{X\in {\mathbb{R}}^{m\times n}}{\min }\mu \Vert X{\Vert }_{\ast }+\frac{1}{2}\sum _{(i,j)\in \Omega }(X_{ij}-M_{ij}{)}^2=\underset{X\in {\mathbb{R}}^{m\times n}}{\min }\underset{h(X)}{\underbrace{\mu \Vert X{\Vert }_{\ast }}}+\underset{\varphi (X)}{\underbrace{\frac{1}{2}\Vert P\odot (X-M){\Vert }_F^2}}$$

• 其中 $\mu >0$ 是一个正则化参数, 用于平衡核范数正则项与数据拟合项之间的权重. $P_{ij}=1$ 当 $(i,j)\in \Omega$ 时, 否则 $P_{ij}=0$. $\odot$ 表示元素级乘法. $\Vert \cdot {\Vert }_F$ 是 Frobenius 范数, 定义为 $\Vert A{\Vert }_F=\sqrt{{\sum }_{i,j}{A}_{ij}^2}$.
• 该优化问题同样可以通过 proximal gradient descent 方法来求解:
  • $\nabla \varphi (X)=P\odot (X-M)$
  • ${\text{prox}}_{t_{k}h}(Y)=U\cdot \text{Diag}((d-t_k\mu {)}_{+})\cdot V^{\top }$, 其中 $Y=U\cdot \text{Diag}(d)\cdot V^{\top }$ 是 $Y$ 的奇异值分解(SVD), 且 $(a{)}_{+}:=\max \{a,0\}$ 对向量逐元素作用.
• 因此, proximal gradient descent 的迭代更新步骤为:

$$\begin{array}{rl}{Y}^{(k)}& =X^{(k)}-t_k\nabla \varphi (X^{(k)})=X^{(k)}-t_k(P\odot (X^{(k)}-M)),\\ Y^{(k)}& =U^{(k)}\cdot \text{Diag}(d^{(k)})\cdot (V^{(k)}{)}^{\top },\\ X^{(k+1)}& =U^{(k)}\cdot \text{Diag}((d^{(k)}-t_k\mu {)}_{+})\cdot (V^{(k)}{)}^{\top }.\end{array}$$

3. Backtracking Line Search for Proximal Gradient Descent

对于 proximal gradient descent 方法, backtracking line search 同样成立, 只不过其搜索对象是分解后光滑部分 $\varphi$ 的梯度.

整体而言, 给定 $\rho \in (0,1)$ 及初始化 $t_0>0$, backtracking line search 的步骤如下:

• 先计算

  $$x^{+}(t)={\text{prox}}_{th}(x-t\nabla \varphi (x)),G_t(x)=\frac{x-x^{+}(t)}{t}.$$

• 检查条件

  $$\varphi (x-t\cdot G_t(x))\le \varphi (x)+(\nabla \varphi (x){)}^{\top }(-t\cdot G_t(x))+\frac{1}{2t}\Vert t\cdot G_t(x){\Vert }^2.$$

• 若不满足, 则令 $t\leftarrow \rho t$, 并重新计算 $x^{+}(t)$ 与 $G_t(x)$ 后再次检查.

• 等价地, 也可写成更常见的上界模型检验: $F(x^{+}(t))\le Q_t(x^{+}(t),x)$.

  $$Q_t(z,x):=\varphi (x)+\nabla \varphi (x{)}^{\top }(z-x)+\frac{1}{2t}\Vert z-x{\Vert }^2+h(z).$$

  且有

  $$F(x^{+}(t))\le Q_t(x^{+}(t),x)⟺\varphi (x^{+}(t))\le \varphi (x)+\nabla \varphi (x{)}^{\top }(x^{+}(t)-x)+\frac{1}{2t}\Vert x^{+}(t)-x{\Vert }^2.$$

在搜索过程中, 由于 $G_t(x)$ 本身依赖于 $t$, 每次缩步长都必须重新计算 prox 映射.

不过还需要额外指出, 在 proximal gradient descent 中, 存在比 backtracking line search 更加高效的步长选择方法.

4. Convergence Analysis

4.1 Algorithm and Assumptions

回顾完整的 proximal gradient descent 算法. 考虑如下优化问题:

$$\underset{x\in {\mathbb{R}}^n}{\min }F(x)=\varphi (x)+h(x)$$

• 其中 $\varphi$ 是光滑凸函数, $h$ 是非光滑的凸函数.

Proximal gradient descent 的迭代更新步骤为:

$$x^{(k+1)}={\text{prox}}_{t_{k}h}(x^{(k)}-t_k\nabla \varphi (x^{(k)})):=x^{(k)}-t_k{G}_{t_k}(x^{(k)})$$

• 其中 $G_{t_k}(x^{(k)})=\frac{1}{t_k}(x^{(k)}-{\text{prox}}_{t_{k}h}(x^{(k)}-t_k\nabla \varphi (x^{(k)})))$ 是 proximal gradient mapping.

在进行收敛性分析之前, 明确如下假设:

1. $\varphi$ 在定义域 ${\mathbb{R}}^n$ 上是凸且其梯度 $\nabla \varphi$ 是 $L$-Lipschitz 连续的, 即对于任意 $x,y\in {\mathbb{R}}^n$, 都有 $\Vert \nabla \varphi (x)-\nabla \varphi (y)\Vert \le L\Vert x-y\Vert$.
2. $h$ 是一个适当的闭凸函数, 使得其近端算子 ${\text{prox}}_{th}$ 是良好定义的.
3. 目标函数 $F(x)=\varphi (x)+h(x)$ 的最小值 $F^{\ast }=F(x^{\ast })$ 是可达且有限的, 并在某个点 $x^{\ast }$ 处达到. 不过这里并不要求 $x^{\ast }$ 是唯一的.

4.2 Convergence Rate

在上述假设条件下, proximal gradient descent 方法的收敛性由以下定理保证:

Theorem (Proximal Gradient Descent 的收敛率). 在满足上述条件, 并给定步长 $t_k=t\in (0,1/L]$ 的情况下, 迭代序列 $\{x^{(k)}\}$ 满足

$$F(x^{(k)})-F^{\ast }\le \frac{\Vert x^{(0)}-x^{\ast }{\Vert }^2}{2tk}$$

即迭代点 $x^{(k)}$ 的函数值以 $\mathcal{O}(1/k)$ 的速率收敛到最优值 $F^{\ast }$.

Proof of the convergence rate

• 根据假设中的 $L$-Lipschitz 连续性, 对 $\varphi$ 进行二阶泰勒展开的上界估计, 可得对于任意 $x,y\in {\mathbb{R}}^n$, 都有:

  $$\varphi (y)\le \varphi (x)+\nabla \varphi (x{)}^{\top }(y-x)+\frac{L}{2}\Vert y-x{\Vert }^2$$
  • 令此处的 $y=x-t{G}_t(x)$, 则有:
  $$\varphi (x-t{G}_t(x))\le \varphi (x)-t\nabla \varphi (x{)}^{\top }{G}_t(x)+\frac{L{t}^2}{2}\Vert G_t(x){\Vert }^2$$
  • 根据步长假设 $t\le 1/L$, 可得 $\frac{L{t}^2}{2}\Vert G_t(x){\Vert }^2\le \frac{t}{2}\Vert G_t(x){\Vert }^2$. 从而:
  $$\varphi (x-t{G}_t(x))\le \varphi (x)-t\nabla \varphi (x{)}^{\top }{G}_t(x)+\frac{t}{2}\Vert G_t(x){\Vert }^2,(1)$$

• 另一方面, 根据假设 $\varphi (x),h(x)$ 均为凸函数, 对于任意 $z\in \text{dom}(F)$, 都有:

  • $\varphi (x)\le \varphi (z)-\nabla \varphi (x{)}^{\top }(z-x),(2)$

  • $h(x^{\prime })\le h(z)-g^{\top }(z-x^{\prime })$ 其中 $g\in \partial h(x^{\prime })$, $x^{\prime }=x-t{G}_t(x)$. 从而若将 $x^{\prime }$ 代入 $h$ 的不等式中, 则有

    $$h(x-t{G}_t(x))\le h(z)-(G_t(x)-\nabla \varphi (x){)}^{\top }(z-x+t{G}_t(x)),(3)$$
    • 其中 $g=G_t(x)-\nabla \varphi (x)\in \partial h(x-t{G}_t(x))$ 是根据 prox 算子与次梯度的关系得到的结果, 见 $(†)$.

• 将 $(1),(2),(3)$ 三个不等式相加, 并根据 composite objective 的定义 $F(x)=\varphi (x)+h(x)$, 经整理化简, 对任意 $z\in \text{dom}(F)$ 都有:

  $$\begin{array}{rl}F(x-t{G}_t(x))& \le F(z)+G_t(x{)}^{\top }(x-z)-\frac{t}{2}\Vert G_t(x){\Vert }^2\end{array}$$

  若另记 $x^{+}=x-t{G}_t(x)$, 则上式可以化作如下形式:

  $$F(x^{+})\le F(z)+G_t(x{)}^{\top }(x-z)-\frac{t}{2}\Vert G_t(x){\Vert }^2$$

• 令 $z=x$, 则有:

  $$F(x^{+})\le F(x)-\frac{t}{2}\Vert G_t(x){\Vert }^2$$
  • 这表明每次迭代都会使得函数值至少下降 $\frac{t}{2}\Vert G_t(x){\Vert }^2$, 从而保证了函数值的单调不增.

• 特别地, 令 $z=x^{\ast }$, 则有:

  $$\begin{array}{rl}F(x^{+})-F^{\ast }& \le G_t(x{)}^{\top }(x-x^{\ast })-\frac{t}{2}\Vert G_t(x){\Vert }^2\\ & =\frac{1}{2t}(\Vert x-x^{\ast }{\Vert }^2-\Vert x-x^{\ast }-t{G}_t(x){\Vert }^2)\\ & =\frac{1}{2t}(\Vert x-x^{\ast }{\Vert }^2-\Vert x^{+}-x^{\ast }{\Vert }^2)\end{array}$$
  • 其中第二行的等式是通过单纯的代数整理得到的: $v^{\top }u-\frac{t}{2}\Vert v{\Vert }^2=\frac{1}{2t}(\Vert u{\Vert }^2-\Vert u-tv{\Vert }^2)$.

• 因此从 $x^{(0)}$ 开始迭代, 可以得到如下递推关系:

  $$F(x^{(k+1)})-F^{\ast }\le \frac{1}{2t}(\Vert x^{(k)}-x^{\ast }{\Vert }^2-\Vert x^{(k+1)}-x^{\ast }{\Vert }^2)$$

  将上述不等式两边同时求和, 则有:

  $$\sum _{i=0}^{k-1}(F(x^{(i+1)})-F^{\ast })\le \frac{1}{2t}\Vert x^{(0)}-x^{\ast }{\Vert }^2$$

  从而由于 $F(x^{(i+1)})$ 是单调不增的, 可得:

  $$k(F(x^{(k)})-F^{\ast })\le \sum _{i=0}^{k-1}(F(x^{(i+1)})-F^{\ast })\le \frac{1}{2t}\Vert x^{(0)}-x^{\ast }{\Vert }^2$$

  从而得到最终的收敛率结果:

  $$F(x^{(k)})-F^{\ast }\le \frac{\Vert x^{(0)}-x^{\ast }{\Vert }^2}{2tk}$$

$\square$

如果我们使用 backtracking line search 来选择步长, 我们可以从某个 $t=t_0>0$ 开始, 通过不断缩小 $t\leftarrow \rho t$ 来不断回溯, 直到满足条件:

$$\varphi (x-t{G}_t(x))\le \varphi (x)-t\nabla \varphi (x{)}^{\top }{G}_t(x)+\frac{t}{2}\Vert G_t(x){\Vert }^2$$

并且每次缩放 $t$ 后都要重新计算 $x^{+}(t)={\text{prox}}_{th}(x-t\nabla \varphi (x))$ 与 $G_t(x)$. 并且可以由类似的分析过程来证明, 在满足上述条件的情况下, 其收敛情况为:

$$F(x^{(k)})-F^{\ast }\le \frac{\Vert x^{(0)}-x^{\ast }{\Vert }^2}{2k\underline{t}},\underline{t}:=\underset{0\le i\le k-1}{\min }{t}_i$$

并且在常见 backtracking 设置下, $\underline{t}$ 可由 $\min \{t_0,\rho /L\}$ 给出一个粗下界.

5. Special Cases

根据 Decomposable/Composite Objective 的组成不同, 我们还有一些特殊的优化算法可以看作是 Proximal Gradient Descent 的特例.

5.1 Projected Gradient Descent

由 Proximal Gradient Descent 的定义可知, 当非光滑部分 $h$ 是一个指示函数 ${\delta }_{\mathcal{C}}$ 且 $\mathcal{C}$ 为非空闭凸集时, 其近端算子 ${\text{prox}}_{th}$ 就退化为一个投影算子 ${\text{Proj}}_{\mathcal{C}}$ 且解唯一. 因此, 在这种特殊情况下, Proximal Gradient Descent 就退化为传统的投影梯度下降(Projected Gradient Descent) 方法. 其迭代更新步骤为:

$$x^{(k+1)}={\text{Proj}}_{\mathcal{C}}(x^{(k)}-t_k\nabla \varphi (x^{(k)}))$$

• 其中 ${\text{Proj}}_{\mathcal{C}}(x)=\arg {\min }_{z\in \mathcal{C}}\Vert z-x\Vert$ 是将 $x$ 投影到集合 $\mathcal{C}$ 上的操作.
• 其含义即为: 在每次迭代中, 首先对光滑部分 $\varphi$ 进行梯度下降的更新, 得到一个临时变量 $x^{\prime }=x^{(k)}-t_k\nabla \varphi (x^{(k)})$; 然后将 $x^{\prime }$ 投影到约束集合 $\mathcal{C}$ 上, 从而得到新的参数 $x^{(k+1)}$.

Figure: Projected gradient descent.

5.2 Proximal Point Algorithm

当光滑部分 $\varphi$ 恒为零时, 考虑如下优化问题:

$$\underset{x\in {\mathbb{R}}^n}{\min }F(x)$$

• 其中 $F$ 是一个适当的闭凸函数, 并不要求其具有可微性.

对于上述优化问题, Proximal Gradient Descent 的迭代更新步骤退化为:

$$x^{(k+1)}={\text{prox}}_{t_{k}F}(x^{(k)})=\arg \underset{z}{\min }\left[\frac{1}{2t_k}\Vert z-x^{(k)}{\Vert }^2+F(z)\right]$$

6. Acceleration: Nesterov’s Accelerated Gradient Method

对于优化问题

$$\underset{x\in {\mathbb{R}}^n}{\min }F(x)=\varphi (x)+h(x)$$

使用 Proximal Gradient Descent, 如果光滑部分的函数 $\varphi$ 是 $L$-smooth 的, 则目标函数的收敛速度为 $\mathcal{O}(1/k)$. 但是, 通过一些加速技巧, 可以将收敛速度提升到 $\mathcal{O}(1/k^2)$. Nesterov 在 1983, 1988, 2005 年提出了三种改进的一阶算法. Beck 和 Teboulle 在 2008 年给出了 Nesterov 1983 算法的 Proximal Gradient 版本, 被称为 FISTA(Fast Iterative Shrinkage-Thresholding Algorithm).

6.1 FISTA Algorithm

FISTA 的算法步骤如下:

1. 初始化: 选择一个初始点 $x^{(0)}\in {\mathbb{R}}^n$, 并令 $x^{(-1)}=x^{(0)}$
2. 迭代更新: 对于 $k=1,2,\dots$ 进行以下更新直到满足收敛条件:
   • $v^{(k)}=x^{(k-1)}+\frac{k-2}{k+1}(x^{(k-1)}-x^{(k-2)})$
   • $x^{(k)}={\text{prox}}_{t_{k}h}(v^{(k)}-t_k\nabla \varphi (v^{(k)}))$

其还有一种表述形式:

1. 初始化: 选择一个初始点 $x^{(0)}\in {\mathbb{R}}^n$, 并令 $v^{(0)}=x^{(0)}$. 选定加速参数 ${\gamma }_k$.
2. 迭代更新: 对于 $k=1,2,\dots$ 进行以下更新直到满足收敛条件:
   • 计算 $y^{(k)}=(1-{\gamma }_k)x^{(k-1)}+{\gamma }_k{v}^{(k-1)}$
   • 选择 $t_k>0$, 计算 $x^{(k)}={\text{prox}}_{t_{k}h}(y^{(k)}-t_k\nabla \varphi (y^{(k)}))$
   • 计算 $v^{(k)}=x^{(k-1)}+\frac{1}{{\gamma }_k}(x^{(k)}-x^{(k-1)})$

当 ${\gamma }_k=\frac{2}{k+1}$ 且步长固定时, 上述两种表述形式是等价的.

对于 FISTA 算法, 在步长 $t_k$ 和加速参数 ${\gamma }_k$ 满足如下条件的情况下 (此处 notation 以第二种表达形式为准), 其收敛率为 $\mathcal{O}(1/k^2)$:

1. $\varphi (x^{(k)})\le \varphi (y^{(k)})+⟨\nabla \varphi (y^{(k)}),x^{(k)}-y^{(k)}⟩+\frac{1}{2t_k}\Vert x^{(k)}-y^{(k)}{\Vert }_2^2$
2. ${\gamma }_1=1$; 对于 $j\ge 2$, $\frac{(1-{\gamma }_j)t_j}{{\gamma }_j^2}\le \frac{t_{j-1}}{{\gamma }_{j-1}^2}$
3. $\frac{{\gamma }_k^2}{t_k}=\mathcal{O}(1/k^2)$.

在满足上述假设条件, 并在固定步长 $t_k=t\in (0,1/L]$ 的情况下, FISTA 迭代序列 $\{x^{(k)}\}$ 满足

$$F(x^{(k)})-F^{\ast }\le \frac{2\Vert x^{(0)}-x^{\ast }{\Vert }^2}{t(k+1{)}^2}$$

• 特别地, 当取 $t=1/L$ 时, 上式退化为常见形式:

$$F(x^{(k)})-F^{\ast }\le \frac{2L\Vert x^{(0)}-x^{\ast }{\Vert }^2}{(k+1{)}^2}$$

6.2 Line Search for FISTA

对于 FISTA 算法, 其步长 $t_k$ 的选择同样可以通过 backtracking line search 来进行调整.

最基础的一个版本的 line search 过程如下:

1. 初始化: 选择一个初始点 $x^{(0)}\in {\mathbb{R}}^n$, 并令 $v^{(0)}=x^{(0)}$. 选定加速参数 ${\gamma }_k$.
2. 迭代更新: 对于 $k=1,2,\dots$ 进行以下更新直到满足收敛条件:
   • 计算 $y^{(k)}=(1-{\gamma }_k)x^{(k-1)}+{\gamma }_k{v}^{(k-1)}$
   • 通过 line search 来选择 $t_k$ 并更新 $x^{(k)}$ (给定迭代起始搜索步长 $t_k=t_{k-1}>0$, 以及缩放因子 $\rho \in (0,1)$):
     • 计算 $x^{(k)}={\text{prox}}_{t_{k}h}(y^{(k)}-t_k\nabla \varphi (y^{(k)}))$
     • 若 $\varphi (x^{(k)})>\varphi (y^{(k)})+⟨\nabla \varphi (y^{(k)}),x^{(k)}-y^{(k)}⟩+\frac{1}{2t_k}\Vert x^{(k)}-y^{(k)}{\Vert }_2^2$, 则
       • 令 $t_k\leftarrow \rho t_k$ ,
       • 重复上述计算 $x^{(k)}$ 和条件检查, 直到满足条件为止.
     • 返回满足条件的 $t_k$ 和对应的 $x^{(k)}$.
   • 计算 $v^{(k)}=x^{(k-1)}+\frac{1}{{\gamma }_k}(x^{(k)}-x^{(k-1)})$

其问题在于: 对于第 $k$ 次迭代, 其 line search 的初始步长 $t_k$ 的选择总是取为 $t_{k-1}$, 这导致其在迭代过程中是不断缩小步长的, 从而可能会导致步长过小, 进而影响算法的收敛速度.

通过其他一些改进的 line search 方法, 可令条件 2 取等号

$$\frac{(1-{\gamma }_k)t_k}{{\gamma }_k^2}=\frac{t_{k-1}}{{\gamma }_{k-1}^2},$$

等价地

$$t_{k-1}{\gamma }_k^2=t_k{\gamma }_{k-1}^2(1-{\gamma }_k),$$

这是关于 ${\gamma }_k$ 的二次方程. 通过求解该方程来动态调整 ${\gamma }_k$ 和 $t_k$, 可以在保证满足 line search 条件的同时, 使得步长 $t_k$ 不会过快地缩小, 从而提升算法的收敛效率.

6.3 Several Remarks on FISTA

加速方法并不是适用于所有问题的.

• 例如在 warm start 的情况下 (例如在求解 Lasso 路径问题 ${\min }_{\beta }\frac{1}{2}\Vert y-X\beta {\Vert }^2+\lambda \Vert \beta {\Vert }_1$, 其中 ${\lambda }_1>{\lambda }_2>\dots >{\lambda }_m>0$ 是一系列递减的正则化参数), 由于每次迭代的初始点 $x^{(0)}$ 已经非常接近最优解, 因此加速方法可能会导致过度震荡, 从而反而降低收敛效率.

• 另外还比如在矩阵补全问题中, prox 的计算涉及到奇异值分解(SVD), 其计算复杂度较高. 需要区分两点:

  • 若固定步长且不做回溯, ISTA 与 FISTA 的单次迭代主成本通常都由一次 prox(SVD) 主导, 基本同阶.
  • 若使用 backtracking line search, 一次迭代内可能触发多次 prox(SVD) 重算, 这才会显著提高单次迭代开销.