Ch7.SubGradient

前置: Ch5.Convex

Non-differentiable Problems

(Projected) Sub-gradient Method

Definition

当且仅当$\mathbf{g}$满足

$$f(\mathbf{z})\ge f(\mathbf{x})+{\mathbf{g}}^{\top }(\mathbf{z}-\mathbf{x}),\forall \mathbf{z}$$

的时候, 称之为sub-gradient

$${\mathbf{x}}^{t+1}={\mathcal{P}}_{\mathcal{C}}({\mathbf{x}}^t-{\eta }_t{g}^t)$$

其中$g^t$是$f$的任意的sub-gradient

Theorem

$$\partial f(ax)=a\partial f(x)\forall a>0$$ $$\partial (f_1+f_2)=\partial f_1+\partial f_2$$ $$\partial f(\mathbf{Ax}+\mathbf{b})={\mathbf{A}}^{\top }\partial f(\mathbf{Ax}+\mathbf{b})$$

chain rule: $\partial g\circ f=g^{\prime }(f)\partial f$

composition: $f(\mathbf{x})=h(f({\mathbf{x}}_1),\cdots ,f({\mathbf{x}}_m))$, 假设$\mathbf{q}=\nabla h(\mathbf{y}){|}_{\mathbf{y}=[f_1(\mathbf{x}),\cdots ,f_n(\mathbf{x})]}$, 且${\mathbf{g}}_i\in \nabla f_i(\mathbf{x})$, 那么有: $q_1{\mathbf{g}}_1+\cdots +q_n{\mathbf{g}}_n(\mathbf{x})\in \partial f(\mathbf{x})$

pointwise maximum: 如果有$f(\mathbf{x})={\max }_{1\le i\le k}{f}_i(\mathbf{x})$, 那么有: $\partial f(\mathbf{x})=\text{conv}\left\{\cup \{\partial f_i(\mathbf{x})|f_i(\mathbf{x})=f(\mathbf{x})\}\right\}$, $\text{conv}$指的是convex hull of subdifferentials of all active functions

pointwise supremum: 对于$f(\mathbf{x})={\sup }_{\alpha \in \mathcal{F}}{f}_{\alpha }(\mathbf{x})$, 有: $\partial f(\mathbf{x})=\text{closure}(\text{conv}\left\{\cup \{\partial f_{\alpha }(\mathbf{x})|f_{\alpha }(\mathbf{x})=f(\mathbf{x})\}\right\})$, closure的定义参见闭包仿射部分

Example

假设有norm: $f(\mathbf{x})=\Vert \mathbf{x}\Vert$, 对于$\mathbf{g}$满足$\Vert \mathbf{g}{\Vert }_{\ast }\le 1$, 有

$$\mathbf{g}\in \partial f(0)$$

其中, $\Vert \cdot {\Vert }_{\ast }$是原始norm的对偶: $\Vert \mathbf{x}{\Vert }_{\ast }={\sup }_{\mathbf{z}:\Vert \mathbf{z}\Vert \le 1}⟨\mathbf{z},\mathbf{x}⟩$

Example

l1-norm:

$$f(\mathbf{x})=\Vert \mathbf{x}{\Vert }_1=\sum _{i=1}^n|x_i|$$

因为

$$\partial f_i(\mathbf{x})=\{\begin{array}{cc}\text{sgn}(x_i){\mathbf{e}}_i& \text{if }{x}_1\ne 0\\ [-1,1]\cdot {\mathbf{e}}_i& \text{if }{x}_i=0\end{array}$$

因此有

$$\sum _{i:x_i\ne 0}\text{sgn}(x_i){\mathbf{e}}_i\in \partial f(\mathbf{x})$$

Fundamental inequality for projected sub-gradient methods

majorization-minimization

找到另一个函数majorizes $\Vert {\mathbf{x}}^{t+1}-{\mathbf{x}}^{\ast }{\Vert }_2^2$, 然后优化这个函数

Lemma

Projected sub-gradient 更新规则 满足:

$$\Vert {\mathbf{x}}^{t+1}-{\mathbf{x}}^{\ast }{\Vert }_2^2\le \underset{\text{majorizing function}}{\underbrace{\underset{\text{fixed}}{\underbrace{\Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }{\Vert }_2^2}}-2{\eta }_t(f({\mathbf{x}}^t)-f^{\text{opt}})+{\eta }_t^2\Vert {\mathbf{g}}^t{\Vert }_2^2}}$$

Polyak’s step size rule

推荐的step size: ${\eta }_t=\frac{f({\mathbf{x}}^t)-f^{\text{opt}}}{\Vert {\mathbf{g}}^t{\Vert }_2^2}$, 其error reduction为:

$$\Vert {\mathbf{x}}^{t+1}-{\mathbf{x}}^{\ast }{\Vert }_2^2\le \Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }{\Vert }_2^2-\frac{(f({\mathbf{x}}^t)-f({\mathbf{x}}^{\ast }){)}^2}{\Vert {\mathbf{g}}^t{\Vert }_2^2}$$

当已知$f^{\text{opt}}$的时候很有用

Convergence Rate是sublinear,

Theorem

假设$f$是convex且$L_f$-Lipschitz continuous的. 那么projected sub-gradient method 应用Polyak’s step size有:

$$f^{\text{best},t}-f^{\text{opt}}\le \frac{L_f\Vert {\mathbf{x}}^0-{\mathbf{x}}^{\ast }{\Vert }_2}{\sqrt{t+1}}$$

Theorem

假设$f$是convex且$L_f$-Lipschitz continuous的. 那么projected sub-gradient method, 但是没有应用Polyak’s step size, 有:

$$f^{\text{best},t}-f^{\text{opt}}\le \frac{L\Vert {\mathbf{x}}^0-{\mathbf{x}}^{\ast }{\Vert }_2+L_f^2{\sum }_{i=0}^t{\eta }_i^2}{2{\sum }_{i=0}^t{\eta }_i}$$

summary:

Convex-concave saddle point problems

saddle point