Lecture 20 - Coordinate Descent

References

• Lecture Reference:
  • https://www.stat.cmu.edu/~ryantibs/convexopt-F18/
  • https://statr.me/teaching/compstat
• Reading Reference: 《最优化：建模、算法与理论》第 8.4 小节

1. Introduction

对于一个一般的非光滑问题, 直接进行全局的优化可能比较困难. 不过在一些具体的情况, 例如一元的场景下, 或许会有一些操作的空间.

Example (Lasso Regression). 给定数据 $\mathbf{X}\in {\mathbb{R}}^{n\times p}$ 和 $\mathbf{y}\in {\mathbb{R}}^n$, Lasso Regression 的优化问题为

$$\underset{\mathbf{\beta }}{\min }\ell (\mathbf{\beta }):=\underset{\mathbf{\beta }}{\min }\frac{1}{2n}\Vert \mathbf{y}-\mathbf{X}\mathbf{\beta }{\Vert }^2+\lambda \Vert \mathbf{\beta }{\Vert }_1$$

直接对于 $\mathbf{\beta }$ 进行全局优化比较困难. 不过如果我们固定 $\mathbf{\beta }$ 的其他分量, 只考虑其中一个分量 ${\beta }_j$, 则可以得到一个关于 ${\beta }_j$ 的一维优化问题, 并推导出 ${\beta }_j$ 的解析解. 推导如下.

• 记 ${\mathbf{X}}_i\in {\mathbb{R}}^n$ 为 $\mathbf{X}$ 的第 $i$ 列, ${\mathbf{X}}_{-j}\in {\mathbb{R}}^{n\times (p-1)}$ 为 $\mathbf{X}$ 除了第 $j$ 列后的剩余部分, ${\mathbf{\beta }}_{-j}\in {\mathbb{R}}^{p-1}$ 为 $\mathbf{\beta }$ 除了第 $j$ 个分量后的剩余部分.

• 则根据矩阵分块及 permutation 的性质, 有

  $$\mathbf{X}\mathbf{\beta }=\left[\begin{array}{cc}{\mathbf{X}}_{-j}& {\mathbf{X}}_j\end{array}\right]\left[\begin{array}{c}{\mathbf{\beta }}_{-j}\\ {\beta }_j\end{array}\right]={\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j}+{\beta }_j{\mathbf{X}}_j$$

  因此

  $$\begin{array}{rl}\ell (\mathbf{\beta })& =\frac{1}{2n}\Vert \mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j}-{\beta }_j{\mathbf{X}}_j{\Vert }^2+\lambda |{\beta }_j|+\lambda \Vert {\mathbf{\beta }}_{-j}{\Vert }_1\\ & =\frac{1}{2n}\left(\Vert \mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j}{\Vert }^2-2{\beta }_j{\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})+{\beta }_j^2\Vert {\mathbf{X}}_j{\Vert }^2\right)+\lambda |{\beta }_j|+\lambda \Vert {\mathbf{\beta }}_{-j}{\Vert }_1\\ & =C+\frac{1}{2n}\left({\beta }_j^2\Vert {\mathbf{X}}_j{\Vert }^2-2{\beta }_j{\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})\right)+\lambda |{\beta }_j|\end{array}$$

  其中 $C$ 是一个常数, 与 ${\beta }_j$ 无关.

• 因此, 考虑 $\tilde{\ell }({\beta }_j)\equiv \ell (\mathbf{\beta })$ 视作一个关于 ${\beta }_j$ 的一元函数, 则其 subgradient 为

  $$\partial \tilde{\ell }({\beta }_j)=\frac{1}{n}\left({\beta }_j\Vert {\mathbf{X}}_j{\Vert }^2-{\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})\right)+\lambda \partial |{\beta }_j|$$

• 故 ${\beta }_j$ 的最小值点满足 $0\in \partial \tilde{\ell }({\beta }_j)$. 通过分别讨论 ${\beta }_j>0$, ${\beta }_j<0$ 和 ${\beta }_j=0$ 的情况, 可以得到

  $${\beta }_j=\{\begin{array}{ll}\frac{1}{\Vert {\mathbf{X}}_j{\Vert }^2}\left({\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})-n\lambda \right),& \text{if }{\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})>n\lambda \\ \frac{1}{\Vert {\mathbf{X}}_j{\Vert }^2}\left({\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})+n\lambda \right),& \text{if }{\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})<-n\lambda \\ 0,& \text{if }|{\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})|\le n\lambda \end{array}$$

• 该解析解的形式为一个 soft-thresholding operator:

  $${\beta }_j=\frac{\text{sign}({\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})){\left(|{\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j})|-n\lambda \right)}_{+}}{\Vert {\mathbf{X}}_j{\Vert }^2}:=\frac{S({\mathbf{X}}_j^{\top }(\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j}),n\lambda )}{\Vert {\mathbf{X}}_j{\Vert }^2}$$

• 综上, 通过固定 $\mathbf{\beta }$ 的其他分量, 只考虑其中一个分量 ${\beta }_j$, 就可以得到一个关于 ${\beta }_j$ 的一维优化问题, 每次更新 ${\beta }_j$ 的时候, 都相当于对第 $j$ 个分量 ${\mathbf{X}}_j$ 与其余分量组成的 partial residual $\mathbf{y}-{\mathbf{X}}_{-j}{\mathbf{\beta }}_{-j}$ 之内积进行 soft-thresholding 操作. 这就是 Coordinate Descent 在 Lasso Regression 中的一个应用.

2. Coordinatewise Minima

对于优化问题

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

之前讨论的绝大多数做法都是每一步更新整个向量 $\mathbf{x}$. 而 Coordinate Descent 则是每一步只更新 $\mathbf{x}$ 的一个坐标分量:

$$x_i\leftarrow \arg \underset{z}{\min }f(x_1,\dots ,x_{i-1},z,x_{i+1},\dots ,x_n)$$

该方法收敛速度较慢, 但随着高维统计机器学习等领域的发展, 逐渐受到重视.

其中一个重要的问题是: 一个 Coordinatewise Minimum 是否能够保证是一个 Local 甚至 Global Minimum? 故首先给出 Coordinatewise Minimum 的定义.

Definition (Coordinatewise Minimum). ${\mathbf{x}}^{\ast }\in {\mathbb{R}}^n$ 是 $f$ 的一个 Coordinatewise Minimum, 如果对于任意 $i\in \{1,\dots ,n\}$ 和所有标准基向量 ${\mathbf{e}}_i=(0,\dots ,0,1,0,\dots ,0{)}^{\top }$ (第 $i$ 个位置为 1, 其他位置为 0), 都有

$$f({\mathbf{x}}^{\ast }+\delta {\mathbf{e}}_i)\ge f({\mathbf{x}}^{\ast }),\forall \delta \in \mathbb{R},\forall i\in \{1,\dots ,n\}$$

则 ${\mathbf{x}}^{\ast }$ 是 $f$ 的一个 Coordinatewise Minimum.

• 直观地讲, Coordinatewise Minimum 是指在每一个坐标方向上, 都无法通过改变该坐标的值来降低函数值.

Coordinatewise Minimum 与 Global Minimum 的关系如下:

• 若 $f$ 是凸且可微的, 则 Coordinatewise Minimum 就是 Global Minimum.

  Proof

  定义 ${\varphi }_i(\delta )=f({\mathbf{x}}^{\ast }+\delta {\mathbf{e}}_i)$. 根据 coordinatewise minimum 的定义, ${\varphi }_i(\delta )\ge {\varphi }_i(0)$ 对于所有 $\delta$ 都成立, 故 $\delta =0$ 为最小值点. 又因为 $f$ 是可微的, ${\varphi }_i^{\prime }(0)=\partial f({\mathbf{x}}^{\ast })/\partial x_i=0$ 对所有 $i$ 都成立. 因此 $\nabla f({\mathbf{x}}^{\ast })=0$, 从而又根据 $f$ 的凸性, ${\mathbf{x}}^{\ast }$ 是 $f$ 的 Global Minimum. $\square$

• 若 $f$ 是凸但不可微的, 则 Coordinatewise Minimum 不一定是 Global Minimum.

  • 说明:
    • 考虑函数 $f$ 的 subgrad: $\partial f(\mathbf{x})=\{\mathbf{g}\in {\mathbb{R}}^n:f(\mathbf{y})\ge f(\mathbf{x})+{\mathbf{g}}^{\top }(\mathbf{y}-\mathbf{x}),\forall \mathbf{y}\in {\mathbb{R}}^n\}$. 根据 Coordinatewise Minimum 的定义, 对于任意 $i$ 和 $\delta$, 都有 ${\varphi }_i(\delta ):=f({\mathbf{x}}^{\ast }+\delta {\mathbf{e}}_i)\ge {\varphi }_i(0)=f({\mathbf{x}}^{\ast })$. 因此, $0$ 是 ${\varphi }_i$ 的最小值点, $0\in \partial {\varphi }_i(0)$. 但 $\partial {\varphi }_i(0)=\{{\mathbf{g}}^{\top }{\mathbf{e}}_i:\mathbf{g}\in \partial f({\mathbf{x}}^{\ast })\}$ 只是 subgradient 在各个坐标上的投影, 因此对每个 $i$, 都存在某个 (可能各不相同的) ${\mathbf{g}}^{(i)}\in \partial f({\mathbf{x}}^{\ast })$ 使得 $({\mathbf{g}}^{(i)}{)}^{\top }{\mathbf{e}}_i=0$. 但这并不意味着存在单个 $\mathbf{g}$ 其所有坐标都为零, 即不能保证 $0\in \partial f({\mathbf{x}}^{\ast })$, 从而无法保证 ${\mathbf{x}}^{\ast }$ 是 Global Minimum.

• 若 $f$ 仍然是不可微的, 但是其能够分解为一个凸且可微的函数 $g:{\mathbb{R}}^n\to \mathbb{R}$ 和若干关于各个坐标分量的一维凸函数 (不要求可微) $h_i:\mathbb{R}\to \mathbb{R},i=1,\dots ,n$ 之和, 即

  $$f(\mathbf{x})=g(\mathbf{x})+\sum _{i=1}^n{h}_i(x_i)$$

  则此时可以说明, Coordinatewise Minimum 就是 Global Minimum.

  Proof

  定义一个一维函数 ${\varphi }_i(t):=f(x_1^{\ast },\dots ,x_{i-1}^{\ast },t,x_{i+1}^{\ast },\dots ,x_n^{\ast })$ 表示只考虑第 $i$ 个坐标, 将其他坐标都固定在 ${\mathbf{x}}^{\ast }$ 上的函数. 根据 coordinatewise minimum 的定义, ${\varphi }_i(t)\ge {\varphi }_i(x_i^{\ast })$ 对于所有 $t\in \mathbb{R}$ 都成立. 因此 $x_i^{\ast }$ 是 ${\varphi }_i$ 的最小值点, $0\in \partial {\varphi }_i(x_i^{\ast })$. 而又知 $\partial {\varphi }_i(x_i^{\ast })=\nabla g({\mathbf{x}}^{\ast }{)}_i+\partial h_i(x_i^{\ast })$, 因此 $0\in \nabla g({\mathbf{x}}^{\ast }{)}_i+\partial h_i(x_i^{\ast })$ 对所有 $i$ 都成立, 故存在某个 $s_i\in \partial h_i(x_i^{\ast })$ 使得 $\nabla g({\mathbf{x}}^{\ast }{)}_i+s_i=0$ 对所有 $i$ 都成立. 即可以拼成 $\mathbf{s}=[s_1,\dots ,s_n{]}^{\top }\in {\mathbb{R}}^n$ 使得 $\mathbf{s}\in \partial h({\mathbf{x}}^{\ast })$ 且 $\nabla g({\mathbf{x}}^{\ast })+\mathbf{s}=0$. 因此， 上文的 $0=\nabla g({\mathbf{x}}^{\ast })+\mathbf{s}\in \nabla g({\mathbf{x}}^{\ast })+\partial h({\mathbf{x}}^{\ast })=\partial f({\mathbf{x}}^{\ast })$, 从而 ${\mathbf{x}}^{\ast }$ 是 $f$ 的 Global Minimum. $\square$

  • 其整体意思即为, 对于可微分的部分, 我们可以要求其不可分离, 各分量是彼此耦合的, 这没有问题, 因为第一个性质保证了 Coordinatewise Minimum 就是 Global Minimum. 而对于不可微的部分, 我们要求其可分离, 各分量之间没有耦合, 这样各个分量的 subgradient 就是独立的, 从而能够保证 Coordinatewise Minimum 就是 Global Minimum.

3. Coordinate Descent Algorithm

3.1 Cyclic Coordinate Descent

给定优化问题

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

其中要求其是可分解的, 即

$$f(\mathbf{x})=g(\mathbf{x})+\sum _{i=1}^n{h}_i(x_i)$$

其中 $g$ 是一个凸且可微的函数 (事实上可以不要求 $g$ 是凸的), $h_i$ 是一个关于 $x_i$ 的一维凸函数 (不要求可微).

总体的更新过程类似内外循环的形式, 外循环为迭代次数 $k=1,2,\dots$, 一次外循环的迭代将依次完成对于 $x_1,x_2,\dots ,x_n$ 的更新. 内循环为具体对于每一个坐标分量 $x_i$ 的更新. 故对于第 $k$ 次外循环的第 $i$ 个内循环, 定义一个关于 $x_i$ 的一维辅助函数:

$$g_i^{(k)}(x_i):=g(x_1^{(k)},\dots ,x_{i-1}^{(k)},x_i,x_{i+1}^{(k-1)},\dots ,x_n^{(k-1)}).$$

其含义为, 整体的迭代过程将依序更新 $x_1,x_2,\dots ,x_n$, 在更新 $x_i$ 时, 将之前已经更新的 $x_1^{(k)},\dots ,x_{i-1}^{(k)}$ 和之后还未更新的 $x_{i+1}^{(k-1)},\dots ,x_n^{(k-1)}$ 固定, 只考虑更新 $x_i$ 的函数 $g_i^{(k)}(x_i)$.

在每一次更新中, 通常根据具体情况不同, 会选择如下三种方式中的一种来更新 $x_i$:

$$x_i^{(k)}=\arg \underset{x_i}{\min }{g}_i^{(k)}(x_i)+h_i(x_i)$$ $$x_i^{(k)}=\arg \underset{x_i}{\min }\{g_i^{(k)}(x_i)+\frac{L_i^{(k-1)}}{2}\Vert x_i-x_i^{(k-1)}{\Vert }^2+h_i(x_i)\}$$ $$x_i^{(k)}=\arg \underset{x_i}{\min }\{⟨\nabla g_i^{(k)}({\hat{x}}_i^{(k-1)}),x_i-{\hat{x}}_i^{(k-1)}⟩+\frac{L_i^{(k-1)}}{2}\Vert x_i-{\hat{x}}_i^{(k-1)}{\Vert }^2+h_i(x_i)\}$$

其中 $L_i^{(k-1)}>0$ 是常数, ${\hat{x}}_i^{(k-1)}$ 是一个外推点, 给定权重 ${\omega }_i^{(k-1)}\ge 0$, 可以定义为

$${\hat{x}}_i^{(k-1)}=x_i^{(k-1)}+{\omega }_i^{(k-1)}(x_i^{(k-1)}-x_i^{(k-2)}).$$

• 第一种方式为直接更新, 适用于 $g_i^{(k)}(x_i)+h_i(x_i)$ 的最小值点能够通过解析解或者高效的数值方法求解的情况.
• 第二种方式为 Proximal 更新
• 第三种方式为 Proximal 更新的基础上加入 Nesterov 加速.

3.2 Variants of Coordinate Descent

Coordinate Descent 还有许多变种, 例如:

• Randomized CD / Permutation CD: 在第 $k$ 次外循环的第 $i$ 个内循环, 随机等权重抽样一个坐标 $j\in \{1,\dots ,n\}$ 来更新. 二者的区别可以近似理解成一个是有放回, 一个是无放回的抽样.
• Block CD: 每次内循环中更新的不是一个坐标分量, 而是一个坐标块.
• Coordinate Proximal Gradient Descent: 每次内循环中通过 Proximal 更新的方式来更新坐标分量.

4. Convergence Property

这里我们仍然考虑

$$f(\mathbf{x})=g(\mathbf{x})+\sum _{i=1}^n{h}_i(x_i)$$

且 $g$ 是一个凸且可微的函数, $h_i$ 是一个关于 $x_i$ 的一维凸函数.

Paul Tseng [1] 证明, 只要服从上述结构, 并在一些 mild regularity 条件下, CD (包括 Cyclic CD, Randomized CD, Block CD 等) 可以保证 ${\mathbf{x}}^{(k)}$ 收敛到 $f$ 的一个全局最优解.

[1] Paul Tseng (2001). Convergence of a block coordinate descent method for nondifferentiable minimization. Journal of optimization theory and applications.

对于不同的 CD 的收敛性在不同假设下有不同的分析. 一个较为有代表性的结论如下. 假设 $g$ 是依坐标 Lipschitz 光滑的, 即对于任意 $i$ 和 $\mathbf{x}$, 都有

$$\Vert {\nabla }_{i}g(\mathbf{x}+t{\mathbf{e}}_i)-{\nabla }_{i}g(\mathbf{x})\Vert \le L_i|t|,\forall t\in \mathbb{R}$$

其中 ${\nabla }_{i}g(\mathbf{x})$ 表示 $g$ 关于 $x_i$ 的偏导数. 进一步定义在初始函数范围内, 所有点到最优集合 ${\mathcal{X}}^{\ast }$ 的加权距离上界为 $R_0$, 即

$$R_0:=\underset{\mathbf{y}}{\sup }\underset{{\mathbf{x}}^{\ast }\in {\mathcal{X}}^{\ast }}{\sup }\left\{{\left(\sum _{i=1}^n{L}_i(y_i-x_i^{\ast }{)}^2\right)}^{1/2}:f(\mathbf{y})\le f({\mathbf{x}}^{(0)})\right\}.$$

则考虑 Randomized CD. 给定 confidence parameter $\rho \in (0,1)$, 以及 accuracy level $\epsilon <\min \{R_0^2,f({\mathbf{x}}^{(0)})-f^{\ast }\}$, 则当迭代次数 $k$ 满足

$$k\ge \frac{2n{R}_0^2}{\epsilon }\log \frac{f({\mathbf{x}}^{(0)})-f^{\ast }}{\rho \epsilon }.$$

则有 $f({\mathbf{x}}^{(k)})-f^{\ast }\le \epsilon$ 以概率至少 $1-\rho$ 成立. 该结果表明, Randomized CD 在上述条件下具有以 $O(1/\epsilon )$ 的速率收敛到全局最优解的保证.

若进一步对 $g$ 增加 $m$-strongly convex 的假设, 并为方便起见假设所有分量的 Lipschitz 常数相同, 即 $L_i=L$ 对所有 $i$ 都成立, 则对于 Cyclic CD, 当迭代次数 $k$ 满足

$$k\ge \frac{4Ln}{m}\log \frac{f({\mathbf{x}}^{(0)})-f^{\ast }}{\epsilon \rho }$$

则有 $f({\mathbf{x}}^{(k)})-f^{\ast }\le \epsilon$ 以概率至少 $1-\rho$ 成立. 该结果表明, Cyclic CD 在上述条件下具有以 $O(\log (1/\epsilon ))$ 的速率收敛到全局最优解的保证.