次梯度

1 背景

• 可导的凸函数，我们通常使用常规的梯度下降法处理，但当目标函数不可导，引入次梯度（Subgradient）用于解决此类目标函数并不总是处处可导的问题
• 次梯度方法的优势是比传统方法能够处理的问题范围更大，不足之处就是算法收敛速度慢。

2 定义

2.1 凸函数定义

• 凸函数的一阶条件：对于凸函数$f​$，如果它可导，则对$\forall x, y\in dom_f​$, 有 $$f(y)\ge f(x)+\nabla f(x)^T(y-x)$$

• 简单讲就是对于凸函数，其切线总是在函数的下方。

2.2 次梯度

• 对给定的$f$, 对$\forall x, y\in dom_f$, 若满足 $$f(y)\ge f(x)+g^T(y-x)$$ 则$g$就是$f$在$x​$的次梯度

• 无论是凸函数还是非凸函数，只要满足上述条件，$g$就是$f$在$x$的次梯度。

• 次微分：将$f$在$x$处所有次梯度的集合称为$f$在$x$的次微分，记作$\partial f(x)$

• 次梯度不一定唯一，也可能不存在。次梯度是在函数凸的区域上加以定义的，凸函数总有次梯度，非凸函数即使可微也不一定有次梯度。凸函数的次微分总是非空，凹函数的次微分是空集。

2.3 计算

• 只考虑目标函数$f$是凸函数情况

• 考虑$f$在$x_0$的左导数 $$a=\lim_{x\rightarrow x_0^{-}} \frac{f(x)-f(x_0)}{x-x_0}$$

• 考虑$f$在$x_0$的右导数 $$b=\lim_{x\rightarrow x_0^{+}}\frac{f(x)-f(x_0)}{x-x_0}$$

• 因此对$f$的次微分是$[a,b]$, $\forall x \in [a,b]$ 都是次梯度

• 如果可导，则$a==b$，因此次梯度就是梯度

• 不可导，次梯度才有多个

• 例如

• 公式 $$f(x)=|x|$$

• 次梯度是 $$g=\left\{ \begin{matrix} sgn(x) & x \not =0\\ all \in [-1,1] \end{matrix} \right\}$$

3 优化条件(optimality condition)

• 点$x^*$是$f$的最优解（无论是否是凸的，凸的就是全局最优，非凸就是局），当且仅当次微分包含0 $$f(x^*)=\min_x f(x)\leftrightarrow 0\in \partial f(x^*)$$

• 证明：

• 若 $$0\in \partial f(x^*)$$

• 则$f(y)\ge f(x^*)+0(y-x^*)=f(x^*)$

• 若 $$0\not \in \partial f(x^*)$$

• 则必定存在$g^T(y-x^*)<0$, 使得$f(y)< f(x^*)​$

4 次梯度迭代算法

4.1 公式

• 类似于梯度下降算法，将梯度更换成了次梯度，重复 $$x^{(k)}=x^{(k-1)}-t_kg^{(k-1)}$$ 其中$g^{(k-1)}\in \partial f(x^{(k-1)})$，即从次微分中随机选择一个次梯度作为梯度

• 可以看出次梯度算法并不总是下降的，为了使更新的参数呈递减的趋势，对第 $k$ 次的参数更新同步使用如下策略： $$f(x_{best}^{(k)})=\min_{i=0,\dots,k}f(x^{(i)})$$ 即第$k$次更新时

• 若使用次梯度算法得到$f(\tilde x^{(k)}) \le f(x^{(k-1)})$使, 则另$x^{(k)}=\tilde x^{(k-1)}$

• 否则，另$\tilde x^{(k)}=x^{(k-1)}$

4.2 步长选择

• 固定步长，$t_k=t$

• 衰减步长，例如$t_k=\frac{1}{k}$，必须满足 $$\sum_{k=1}^{\infty} t_k^2<\infty,\sum_{k=1}^{\infty} t_k=\infty$$

• 只要选择的步长合适，算法总会收敛，只是算法收敛速度比较慢(TODO 证明：https://blog.csdn.net/qq_32742009/article/details/81704139)

5 例子

• 求解lasso问题

• 假设$X$是正交的

• Lasso公式为 $$f(\beta)=(y-X\beta)^T(y-X\beta)+\lambda \|\beta\|_{1}$$

• 求导得 $$0\in 2X^T(X\beta - y) + \lambda \frac{\partial \|\beta\|_{1}}{\partial \beta}$$

• 另 $$0= 2X^T(X\beta - y) + \lambda \frac{\partial \|\beta\|_{1}}{\partial \beta}\\ 2X^T(y-X\beta)=\lambda \frac{\partial \|\beta\|_{1}}{\partial \beta}\\ \beta=X^Ty-\frac{\lambda}{2}\frac{\partial \|\beta\|_{1}}{\partial \beta} = \hat \beta^{ls}-\frac{\lambda}{2}\frac{\partial \|\beta\|_{1}}{\partial \beta}$$

• 由于 $$ \frac{\partial |\beta|_{1}}{\partial \beta_i}= \left{ $$\begin{matrix} 1, \beta_i>0\\ -1, \beta_i<0\\ [-1,1],\beta_i=0 \end{matrix}$$

  \right} $$

• 因此分情况讨论得知

  • 若$\hat \beta^{ls}_j > \frac{\lambda}{2}​$, 有$\beta_j=\hat \beta^{ls}_j-\frac{\lambda}{2}\frac{\partial \|\beta\|_{1}}{\partial \beta_j}>0​$, 因此有 $$\beta_j=\hat \beta^{ls}_j-\frac{\lambda}{2}$$

  • 若$\hat \beta^{ls}_j < - \frac{\lambda}{2}​$, 有$\beta_j=\hat \beta^{ls}_j-\frac{\lambda}{2}\frac{\partial \|\beta\|_{1}}{\partial \beta_j}<0​$,因此有 $$\beta_j=\hat \beta^{ls}_j+\frac{\lambda}{2}$$

  • 若$- \frac{\lambda}{2}\le \hat \beta^{ls}_j \le \frac{\lambda}{2}​$, 使用反证

  • 若$\beta_j > 0​$, 则有$\beta_j=\hat \beta^{ls}_j-\frac{\lambda}{2}\frac{\partial \|\beta\|_{1}}{\partial \beta_j} = \hat \beta^{ls}_j-\frac{\lambda}{2}\le 0​$

  • 若$\beta_j < 0​$，则有$\beta_j=\hat \beta^{ls}_j-\frac{\lambda}{2}\frac{\partial \|\beta\|_{1}}{\partial \beta_j} = \hat \beta^{ls}_j+\frac{\lambda}{2}\ge 0​$
  • 因此可以得到，$\beta_j=0$，$\frac{\partial \|\beta\|_{1}}{\partial \beta_j}=\frac{2\hat\beta_j^{ls}}{\lambda}$

• 最后，总结情况可知（其中$x_+$指$max(x,0)$） $$\hat \beta^{lasso} = sign(\hat \beta^{ls})^T(|\hat \beta^{ls}|-\frac{\lambda}{2})_{+}$$