Ch6.Gradient

Differentiable Unconstrained Minimization

$$\begin{array}{cc}\min & f(\mathbf{x})\\ \text{subject to}& \mathbf{x}\in {\mathbb{R}}^n\end{array}$$

其中$f$可微

Convergence Rate

计算方法:

假设给定objective function能够转换成一个序列$r_k$, 计算极限

$$q=\underset{k\to \infty }{\lim }\frac{r_{k+1}}{r_k}$$

convergence rate就是$q$.

Convergence Type

• $q=0$: superlinearly
• $0<q<1$: linearly
• $q=1$: sublinearly
• $q>1$: non-convergence

Convergence Rate of Quadratic Minimization

假设${\lambda }_1(\mathbf{Q})$是$\mathbf{Q}$的最大的eigenvalue, ${\lambda }_n(\mathbf{Q})$是最小eigenvalue, 那么可以认为:

$$r=\frac{{\lambda }_1(\mathbf{Q})}{{\lambda }_n(\mathbf{Q})}=\frac{{\max }_x{\lambda }_1({\nabla }^{2}f(\mathbf{x}))}{{\min }_x{\lambda }_n({\nabla }^{2}f(\mathbf{x}))}$$

${\eta }_t\equiv \eta =\frac{2}{{\lambda }_1(\mathbf{Q})+{\lambda }_n(\mathbf{Q})}$, 那么

$$\Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }{\Vert }_2\le {\left(\frac{{\lambda }_1(\mathbf{Q})-{\lambda }_n(\mathbf{Q})}{{\lambda }_1(\mathbf{Q})+{\lambda }_n(\mathbf{Q})}\right)}^t\Vert {\mathbf{x}}^0-{\mathbf{x}}^{\ast }{\Vert }_2=\epsilon$$

Convergence Analysis:

$$\begin{array}{rl}1.& \Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }{\Vert }_2\le \epsilon \\ 2.& \Vert f({\mathbf{x}}^t)-f({\mathbf{x}}^{\ast }){\Vert }_2\le \epsilon \\ 3.& \Vert \nabla f(\mathbf{x}){\Vert }_2\le \epsilon \end{array}$$

Convergence Rate:

1. sublinear: $T>\frac{1}{{\epsilon }^k},o(\frac{1}{{\epsilon }^k})$
2. linear: $T>\log \frac{1}{\epsilon },o(\log \frac{1}{\epsilon })$
3. quadratic(super linear): $T>\log (\log \frac{1}{\epsilon }),o(\log (\log \frac{1}{\epsilon }))$

Iteration Function: 4. sublinear: $\Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }{\Vert }_2\le \frac{1}{t^{\frac{1}{k}}}\Vert {\mathbf{x}}^0-{\mathbf{x}}^{\ast }{\Vert }_2$ 5. linear: $\Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }{\Vert }_2\le \Vert {\mathbf{x}}^{q-1}-{\mathbf{x}}^{\ast }{\Vert }_2\Rightarrow \Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }{\Vert }_2\le q^t\Vert {\mathbf{x}}^0-{\mathbf{x}}^{\ast }{\Vert }_2$ 6. quadratic: $\Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }{\Vert }_2\leqq \Vert {\mathbf{x}}^{q-1}-{\mathbf{x}}^{\ast }{\Vert }_2^2$

Iterative descend algorithm

从$x_0$开始, 构造序列$\{{\mathbf{x}}^t\}$满足$f({\mathbf{x}}^{t+1})<f({\mathbf{x}}^t),t=0,1,\cdots$

下降方向(descend direction) $d$ 满足:

$$f^{\prime }(\mathbf{x};\mathbf{d}):=\underset{\tau \downarrow 0}{\lim }\frac{f(\mathbf{x}+\tau \mathbf{d})-f(\mathbf{x})}{\tau }=\nabla f(\mathbf{x}{)}^{\top }\mathbf{d}\le 0$$

每一次迭代中, 有${\mathbf{x}}^{t+1}={\mathbf{x}}^t-\eta {\mathbf{d}}^t$, 其中${\mathbf{d}}^t$是在${\mathbf{x}}^t$的时候的descend direction, $\eta$是步长.

在机器学习中, $f$通常是loss函数, $\mathbf{x}$通常是loss函数中的参数, $\eta$是学习率

Note

Steepest Descend 最陡下降法

• 最快优化objective function的方向:

mathop{\arg\min}_{\mathbf d:|\mathbf d|2\leq1}f’(\mathbf x;\mathbf d)=\mathop{\arg\min}{\mathbf d:|\mathbf d|_2\leq1}\nabla f(\mathbf x)^\top\mathbf d=-|\nabla f(\mathbf x)|_2$$

$$-\Vert \nabla f(\mathbf{x})\Vert \cdot \Vert d{\Vert }_2\le ⟨\nabla f(\mathbf{x}),\mathbf{d}⟩\le \Vert \nabla f(\mathbf{x})\Vert \cdot \Vert d{\Vert }_2$$

Quadratic Minimization

$$\begin{array}{cc}\min & f(\mathbf{x}):=\frac{1}{2}(\mathbf{x}-{\mathbf{x}}^{\ast }{)}^{\top }\mathbf{Q}(\mathbf{x}-{\mathbf{x}}^{\ast })\\ \text{subject to}& \mathbf{Q}\succ 0\end{array}$$

该方程的梯度为$\nabla f(\mathbf{x})=\mathbf{Q}(\mathbf{x}-{\mathbf{x}}^{\ast })$

参数更新:

$$x^{t+1}=(\mathbf{I}-{\eta }_t\mathbf{Q}){\mathbf{x}}^t+{\eta }_t\mathbf{Q}{\mathbf{x}}^{\ast }$$

step size($\eta$) rule:

$$\begin{array}{rl}& {\mathbf{x}}^{t+1}-{\mathbf{x}}^{\ast }=(\mathbf{I}-{\eta }_t\mathbf{Q})({\mathbf{x}}^t-{\mathbf{x}}^{\ast })\\ \Rightarrow & \Vert {\mathbf{x}}^{t+1}-{\mathbf{x}}^{\ast }\Vert \le \Vert \mathbf{I}-{\eta }_t\mathbf{Q}\Vert \cdot \Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }\Vert \\ \Rightarrow & \Vert \mathbf{I}-\eta \mathbf{Q}\Vert =\frac{{\lambda }_1(\mathbf{Q})-{\lambda }_n(\mathbf{Q})}{{\lambda }_1(\mathbf{Q})+{\lambda }_n(\mathbf{Q})}\\ \Rightarrow & \eta \equiv {\eta }_t=\frac{2}{{\lambda }_1(\mathbf{Q})+{\lambda }_n(\mathbf{Q})}\end{array}$$

Exact Line Search

${\eta }_t={\mathrm{argmin}}_{\eta \ge 0}f({\mathbf{x}}^t-\eta \nabla f({\mathbf{x}}^t))$

假设有$g^t=\nabla f({\mathbf{x}}^t)=\mathbf{Q}({\mathbf{x}}^t-{\mathbf{x}}^{\ast })$, 那么${\eta }_t=\frac{{g^t}^{\top }{g}^t}{{g^t}^{\top }\mathbf{Q}{g}^t}$

Kantorovich’s inequality:

$$\frac{\Vert \mathbf{y}{\Vert }_2^4}{({\mathbf{y}}^{\top }\mathbf{Qy})({\mathbf{y}}^{\top }{\mathbf{Q}}^{-1}\mathbf{y})}\ge \frac{4{\lambda }_1(\mathbf{Q}){\lambda }_n(\mathbf{Q})}{({\lambda }_1(\mathbf{Q})+{\lambda }_n(\mathbf{Q}){)}^2}$$

Smooth problem

$\mu$-strong和$L$-smooth定义:

$$0⪯\mu \mathbf{I}⪯{\nabla }^{2}f(\mathbf{x})⪯L\mathbf{I}$$

或者:

$${\lambda }_n(\mathbf{Q})\mathbf{I}⪯\mathbf{Q}⪯{\lambda }_1(\mathbf{Q})\mathbf{I}$$

Theorem

对于$\mu$-strong和$L$-smooth的问题, 有:

• step size: $\eta =\frac{2}{\mu +L}$ (v.s. $\frac{2}{{\lambda }_1+{\lambda }_n}$)
• contraction rate: $\frac{\kappa -1}{\kappa +1},\kappa =\frac{L}{\mu }$ (v.s. $\frac{{\lambda }_1-{\lambda }_n}{{\lambda }_n+{\lambda }_1}$)

iteration complexity: $o(\frac{\log \frac{1}{\epsilon }}{\log \frac{\kappa -1}{\kappa +1}})$

$$f({\mathbf{x}}^t)-f({\mathbf{x}}^{\ast })\le \frac{L}{2}{\left(\frac{\kappa -1}{\kappa +1}\right)}^{2t}\Vert {\mathbf{x}}^0-{\mathbf{x}}^{\ast }{\Vert }_2$$

Backtracking Line Search

Armijo Condition:

$$f({\mathbf{x}}^t-\eta \nabla f({\mathbf{x}}^t))<f({\mathbf{x}}^t)-\alpha \eta \Vert \nabla f({\mathbf{x}}^t){\Vert }_2^2,0<\alpha <1$$

algorithm:

1. initialize $\eta =1$, $0<\alpha <\frac{1}{2}$, $0<\beta <1$
2. while $f({\mathbf{x}}^t-\eta \nabla f({\mathbf{x}}^t))<f({\mathbf{x}}^t)-\alpha \eta \Vert \nabla f({\mathbf{x}}^t){\Vert }_2^2$, do:
   • $\eta \leftarrow \beta \eta$

上界: $f({\mathbf{x}}^t)-\eta \Vert \nabla f({\mathbf{x}}^t){\Vert }_2^2+\frac{L{\eta }^2}{2}\Vert \nabla f({\mathbf{x}}^t){\Vert }_2^2$

Theorem

$$f({\mathbf{x}}^t)-f({\mathbf{x}}^{\ast })\le (1-\min \{2\mu \alpha ,\frac{2\beta \alpha \mu }{L}\}{)}^t(f({\mathbf{x}}^0)-f({\mathbf{x}}^{\ast }))$$

收敛性:

$$\Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }\Vert \le \frac{\kappa -1}{\kappa +1}\Vert {\mathbf{x}}^{t-1}-{\mathbf{x}}^0\Vert$$

Regularity Condition

$\mu$-strong + $L$-smooth

$$\eta \equiv {\eta }_t=\frac{1}{L}$$ $$\Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }\Vert \le (1-\frac{\mu }{L}{)}^t\Vert {\mathbf{x}}^0-{\mathbf{x}}^{\ast }\Vert$$

Polyak-Lojasiewicz Condition

$$\Vert \nabla f(\mathbf{x}){\Vert }_2^2\ge 2\mu (f(\mathbf{x})-f({\mathbf{x}}^{\ast }))$$ $$f({\mathbf{x}}^t)-f({\mathbf{x}}^{\ast })\le (1-\frac{\mu }{L}{)}^t(f({\mathbf{x}}^0)-f({\mathbf{x}}^{\ast }))$$

Over-parameterized linear regression

over-parameterize: model dimension > sample size

定义

$$f(x)=\frac{1}{2}\sum _{i=1}^m({\mathbf{a}}_i^{\top }\mathbf{x}-y_i{)}^2=\frac{1}{2}(\mathbf{AX}-\mathbf{Y}{)}^2$$

有

$$\nabla f(x)=0\iff \mathbf{X}=({\mathbf{A}}^{\top }\mathbf{A}{)}^{-1}{\mathbf{A}}^{\top }\mathbf{Y}$$ $${\nabla }^{2}f(x)=\sum _{i=1}^m{\mathbf{a}}_i{\mathbf{a}}_i^{\top }$$

认为如果$\mathbf{A}=[{\mathbf{a}}_1,\cdots ,{\mathbf{a}}_m{]}^{\top }\in {\mathbf{R}}^{m\times n}$, 其rank为$m$, 且满足step size ${\eta }_t\equiv \eta =\frac{1}{{\lambda }_{\text{max}}({\mathbf{AA}}^{\top })}$, 有:

$$f({\mathbf{x}}^t)-f({\mathbf{x}}^{\ast })\le {\left(1-\frac{{\lambda }_{\text{min}}({\mathbf{AA}}^{\top })}{{\lambda }_{\text{max}}({\mathbf{AA}}^{\top })}\right)}^t(f({\mathbf{x}}^0)-f({\mathbf{x}}^{\ast })),\forall t$$

Convex and Smooth Problem

L-smooth

majorization-minimization

Theorem

如果是$L$-smooth的, 且有: $\eta =\frac{1}{L}$

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

Non-convex Problem

Theorem

• for general: $${\min }_{0\le k<t}\Vert \nabla f({\mathbf{x}}^k){\Vert }_2\le \sqrt{\frac{2L(f({\mathbf{x}}^0)-f({\mathbf{x}}^{\ast }))}{t}}$$
• for convex: $${\min }_{\frac{t}{2}\le k<t}\Vert \nabla f({\mathbf{x}}^k){\Vert }_2=\frac{4L\Vert {\mathbf{x}}^0-{\mathbf{x}}^{\ast }{\Vert }_2}{t}$$

Gradient methods for Constrained Problems

Frank-Wolfe algorithm

1. ${\mathbf{y}}^t:={\mathrm{argmin}}_{x\in \mathcal{C}}⟨\nabla f({\mathbf{x}}^t),{\mathbf{x}}^t⟩$
2. ${\mathbf{x}}^{t+1}=(1-{\eta }_t){\mathbf{x}}^t+{\eta }_t{\mathbf{y}}^t$

over a convex set: $f(x^t)+⟨\nabla f(x^t),x-x^t⟩$. 步长类似Exact Line Search: ${\eta }_t=\frac{2}{t+2}$

对于non-convex:

$$\begin{array}{cc}\text{minimize}& -{\mathbf{x}}^{\top }\mathbf{Qx}\\ \text{subject to}& \Vert \mathbf{x}{\Vert }_2\le 1\end{array}$$

有:

$$\begin{array}{rl}{\mathbf{y}}^t& ={\mathrm{argmin}}_{\mathbf{x}:\Vert \mathbf{x}{\Vert }_2\le 1}⟨\nabla f({\mathbf{x}}^t),\mathbf{x}⟩=-\frac{\nabla f({\mathbf{x}}^t)}{\Vert \nabla f({\mathbf{x}}^t){\Vert }_2}=\frac{{\mathbf{Qx}}^t}{\Vert {\mathbf{Qx}}^t{\Vert }_2}\\ \Rightarrow {\mathbf{x}}^{t+1}& =(1-{\eta }_t){\mathbf{x}}^t+{\eta }_t\frac{{\mathbf{Qx}}^t}{\Vert {\mathbf{Qx}}^t{\Vert }_2}\end{array}$$

Convergence

Theorem

假设$f$是convex的, 且是L-smooth的, 假设有${\eta }_t=\frac{2}{t+2}$, 那么有:

$$f({\mathbf{x}}^t)-f({\mathbf{x}}^{\ast })\le \frac{2L{d}_{\mathcal{C}}^2}{t+2}$$

其中$d_{\mathcal{C}}={\sup }_{\mathbf{x},\mathbf{y}\in \mathcal{C}}\Vert \mathbf{x}-\mathbf{y}{\Vert }_2$

对于compact约束集合, 效率可以达到 $\epsilon$-accuracy, 在$O(\frac{1}{\epsilon })$个迭代中

Example

假设有集合$\mathcal{C}$是$\mu$-convex的, 假设$\forall \lambda \in [0,1]$, $\forall x,z\in \mathcal{C}$, 定义$\mathcal{B}(\mathbf{a},r):=\{\mathbf{y}|\Vert \mathbf{y}-\mathbf{a}{\Vert }_2\le r\}$, 那么有:

$$\mathcal{B}(\lambda \mathbf{x}+(1-\lambda )\mathbf{z},\frac{\mu }{2}\lambda (1-\lambda )\Vert \mathbf{x}-\mathbf{z}{\Vert }_2^2)\in \mathcal{C}$$

Theorem

假设$f$是convex and L-smooth的, 假设$\mathcal{C}$是$\mu$-strongly convex的, 那么$0\le c\le \Vert \nabla f(\mathbf{x}){\Vert }_2,\forall x\in \mathcal{C}$

Projected Gradient Method

将一个在集合外的点映射到集合中

Definition

Euclidean projection(quadratic minimization):

$${\mathcal{P}}_C(\mathbf{x}):={\mathrm{argmin}}_{\mathbf{z}\in C}\Vert \mathbf{x}-\mathbf{z}{\Vert }_2^2$$

循环:

$${\mathbf{x}}^{t+1}={\mathcal{P}}_C({\mathbf{x}}^t-{\eta }_t\nabla f({\mathbf{x}}^t))$$

Theorem

假设有集合$\mathcal{C}$是close且convex的, 那么有:

$$(\mathbf{x}-{\mathcal{P}}_{\mathcal{C}}(\mathbf{x}){)}^{\top }(\mathbf{z}-{\mathcal{P}}_{\mathcal{C}}(\mathbf{x}))\le 0,\forall \mathbf{z}\in \mathcal{C}$$

从上图可知, 有$-\nabla f({\mathbf{x}}^t{)}^{\top }({\mathbf{x}}^{t+1}-{\mathbf{x}}^t)\ge 0$, 即${\mathbf{x}}^{t+1}-{\mathbf{x}}^t$和最速下降的方向是正相关的

Strongly Convex

Theorem

假设${\mathbf{x}}^{\ast }\in \text{int}(\mathcal{C})$, 假设$f$是$\mu$-strongly convex且L-smooth的. 令${\eta }_t=\frac{2}{\mu +L},\kappa =\frac{L}{\mu }$, 有

$$\Vert {\mathbf{x}}^t-{\mathbf{x}}^{\ast }{\Vert }_2\le {\left(\frac{\kappa -1}{\kappa +1}\right)}^t\Vert {\mathbf{x}}_0-{\mathbf{x}}^{\ast }{\Vert }_2$$

一些其他情况参见Smooth problem