本文是自己学习凸优化的笔记和总结。挂在这里主要是方便自己查。当然，如果能帮到手滑点进来的人也是极好的。

本节关于无约束光滑凸优化的梯度下降法的收敛分析。

上一集传送 : 凸函数，Lipschitz smooth, strongly convex

Gradient descent

梯度下降是一类极为有效的一阶最优化算法。一个无约束的凸优化问题可以写成

min⁡ f(x)\min \, f(x)

最原始的梯度下降的迭代公式可以写作：

xt+1=xt−γ∇f(xt)x_{t+1} = x_t - \gamma \nabla f(x_t)

其中 α\alpha 为步长，∇f(xt)\nabla f(x_t) 为梯度。这个迭代公式其实可以解释为对 f(x)f(x) 的二阶近似。

f(x)≈f(xt)+∇f(xt)(x−xt)+12γ∥x−xt∥2f(x) \approx f(x_t) + \nabla f(x_t)(x-x_t) + \frac{1}{2\gamma} \|x-x_t\|^2

对右侧求导 =0，可推出

∇f(xt)+1γ(x−xt)=0\nabla f(x_t) + \frac{1}{\gamma}(x-x_t)=0

即梯度下降迭代公式。

Convergence analysis

为方便推导，约定如下简写：

ft:=f(xt)​f_t := f(x_t) ​

ft′:=∇f(xt)​f'_t := \nabla f(x_t)​

rt:=∥xt−x⋆∥​r_t := \| x_t-x_\star \|​

Δt:=ft−f⋆​\Delta_t := f_t - f_\star​

其中 x⋆:=arg⁡min⁡ f(x)​x_\star := \arg\min \, f(x)​.

首先用下表总结一下原始梯度下降法的收敛速率。

L-smooth convex L-smooth μ\mu-strongly convex
Δt≤\Delta_t \leq 2Ltr02\frac{2L}{t} r_0^2 (k−1k+1)2tr02\big(\frac{k-1}{k+1}\big)^{2t} r_0^2
Δt≤ϵ\Delta_t \leq \epsilon 所需步数 O(1ϵ)O\big(\frac{1}{\epsilon}\big), sub-linear O(klog⁡(1ϵ))O\big(k \log (\frac{1}{\epsilon})\big), linear

其中 k:=Lμk:=\frac{L}{\mu} 又称条件数 (condition number).

L-smooth convex function

首先证明以下几个结论成立：

  1. rt+12≤rt2−γ(2L−γ)∥ft′∥2r_{t+1}^2 \leq r_t^2 - \gamma(\frac{2}{L} - \gamma) \| f'_t \|^2
  2. Δt+1−Δt≤−γ(1−Lγ2)∥ft′∥2\Delta_{t+1} - \Delta_t \leq - \gamma (1-\frac{L\gamma}{2}) \| f'_t\|^2
  3. Δt≤rt∥ft′∥\Delta_t \leq r_t \| f'_t\|

证明

(1)

rt+12=∥xt+1−x⋆∥2(GD iteration)=∥xt−γft′−x⋆∥2=rt2−2γ⟨ft′,xt−x⋆⟩+γ2∥ft′∥2(co-coercivity)≤rt2−2γL∥ft′∥2+γ2∥ft′∥2=rt2−γ(2L−γ)∥ft′∥2\begin{aligned} r_{t+1}^2 &= \| x_{t+1}-x_\star \|^2 \\ \href{./#gradient-descent}{\text{(GD iteration)}} \quad &= \| x_t - \gamma f'_t - x_\star \|^2 \\ &= r_t^2 - 2\gamma \langle f'_t, x_t- x_\star \rangle + \gamma^2 \| f'_t\|^2 \\ \href{/posts/20190217-convex-function-lipschitz-smooth-strongly-convex/# 等价条件}{\text{(co-coercivity)}} \quad &\leq r_t^2 - \frac{2\gamma}{L}\| f'_t\|^2 + \gamma^2 \| f'_t\|^2 \\ &= r_t^2 - \gamma(\frac{2}{L} - \gamma) \| f'_t \|^2 \end{aligned}

如果 γ∈[0,2L]\gamma \in [0, \frac{2}{L}], 则 rt+12≤rt2r_{t+1}^2 \leq r_t^2. 显然, 最优步长 γ=1L\gamma = \frac{1}{L}.

(2)

(quadratic upper bound)ft+1≤ft+⟨ft′,xt+1−xt⟩+L2∥xt+1−xt∥2(GD iteration)=ft−γ∥ft′∥2+Lγ22∥ft′∥2=ft−γ(1−Lγ2)∥ft′∥2  ⟹  Δt+1−Δt≤−γ(1−Lγ2)∥ft′∥2\begin{aligned} \href{/posts/20190217-convex-function-lipschitz-smooth-strongly-convex/# 等价条件}{\text{(quadratic upper bound)}} \quad f_{t+1} &\leq f_t + \langle f'_t, x_{t+1} - x_t \rangle + \frac{L}{2} \| x_{t+1} - x_t \|^2 \\ \href{./#gradient-descent}{\text{(GD iteration)}} \quad & = f_t - \gamma \| f'_t\|^2 + \frac{L\gamma^2}{2} \| f'_t\|^2 \\ &= f_t - \gamma (1-\frac{L\gamma}{2}) \| f'_t\|^2 \\ \implies \quad \Delta_{t+1} - \Delta_t &\leq - \gamma (1-\frac{L\gamma}{2}) \| f'_t\|^2 \end{aligned}

(3)

(first-order condition)Δt=ft−f⋆≤⟨ft′,xt−x⋆⟩(Cauchy-Schwartz)≤rt∥ft′∥\begin{aligned} \text{(first-order condition)} \quad \Delta_t = f_t - f_\star &\leq \langle f'_t, x_t - x_\star \rangle \\ \text{(Cauchy-Schwartz)} \quad &\leq r_t \| f'_t\| \end{aligned}

令 h=γ(1−Lγ2)h=\gamma (1-\frac{L\gamma}{2}). 如果 γ∈[0,2L]\gamma \in [0, \frac{2}{L}]，则 h≥0h \geq 0. 若 γ=1L\gamma = \frac{1}{L} 则 hh 取到最大值 12L\frac{1}{2L}.

以下开始分析 L-smooth convex 情况下梯度下降的收敛.

(since 2)Δt+1−Δt≤−h∥ft′∥2(since 3)≤−hrt2Δt2(since 1)≤−hr02Δt21Δt−1Δt+1≤−hr02ΔtΔt+1(since 2)≤−hr02\begin{aligned} \text{(since 2)} \quad \Delta_{t+1} - \Delta_t &\leq - h \| f'_t\|^2 \\ \text{(since 3)} \quad &\leq -\frac{h}{r_t^2} \Delta_t^2 \\ \text{(since 1)} \quad &\leq -\frac{h}{r_0^2} \Delta_t^2 \\ \frac{1}{\Delta_{t}} - \frac{1}{\Delta_{t+1}} &\leq -\frac{h}{r_0^2} \frac{\Delta_t}{\Delta_{t+1}} \\ \text{(since 2)} \quad &\leq -\frac{h}{r_0^2} \end{aligned}

相加以上不等式抵消中间项，得

1Δt≥1Δ0+htr02≥htr02  ⟹  Δt≤r02ht(use max h=1/2L)=2Lr02t\begin{aligned} \frac{1}{\Delta_t} &\geq \frac{1}{\Delta_0} + \frac{ht}{r_0^2} \\ &\geq \frac{ht}{r_0^2} \\ \implies \Delta_t &\leq \frac{r_0^2}{ht} \\ \text{(use max h=1/2L)}\quad &= \frac{2L r_0^2}{t} \end{aligned}

即

ft−f⋆≤2Lt∥x0−x⋆∥2f_t - f_\star \leq \frac{2L}{t} \|x_0 - x_\star \|^2

可知达到 ft−f⋆≤ϵf_t - f_\star \leq \epsilon 需要 O(2Lϵ∥x0−x⋆∥2)=O(1ϵ)O\big(\frac{2L}{\epsilon} \|x_0 - x_\star \|^2\big) = O\big(\frac{1}{\epsilon}\big) 次迭代。此为 sub-linear convergence.

L-smooth and μ-strongly convex function

首先证明

Proposition 1. Suppose ff is L-smooth and μ\mu-strongly convex. Then we have

⟨fx′−fy′,x−y⟩≥μLμ+L∥x−y∥2+1μ+L∥fx′−fy′∥2.\langle f'_x -f'_y, x-y \rangle \geq \frac{\mu L}{\mu+L} \| x-y\|^2 + \frac{1}{\mu+L} \| f'_x -f'_y\|^2.

证明

(1） μ=L\mu = L. 由 L-smooth 的 co-coercivity 和 \mu-strongly convex 的 coercivity 相加可得。

(2） μ<L\mu < L.

首先令 ϕ(x)=f(x)−μ2∣x∣2\phi(x) = f(x) - \frac{\mu}{2} | x|^2, 易证其为 (L-μ\mu)-smooth.

所以

⟨ϕx′−ϕy′,x−y⟩≥1L−μ∥ϕx′−ϕy′∥2⟨fx′−μx−fy′+μy,x−y⟩≥1L−μ∥fx′−μx−fy′+μy∥2⟨fx′−fy′,x−y⟩−μ∥x−y∥2≥1L−μ∥fx′−fy′∥2−2μL−μ⟨fx′−fy′,x−y⟩+μ2L−μ∥x−y∥2⟨fx′−fy′,x−y⟩≥μLμ+L∥x−y∥2+1μ+L∥fx′−fy′∥2\begin{aligned} \langle \phi'_x - \phi'_y, x-y\rangle &\geq \frac{1}{L-\mu} \| \phi'_x - \phi'_y\|^2 \\ \langle f'_x - \mu x - f'_y + \mu y, x-y\rangle &\geq \frac{1}{L-\mu} \| f'_x - \mu x - f'_y + \mu y\|^2 \\ \langle f'_x - f'_y , x-y\rangle - \mu \| x-y\|^2 &\geq \frac{1}{L-\mu} \| f'_x - f'_y \|^2 -\frac{2\mu}{L-\mu}\langle f'_x - f'_y , x-y\rangle + \frac{\mu^2}{L-\mu} \| x-y\|^2 \\ \langle f'_x -f'_y, x-y \rangle &\geq \frac{\mu L}{\mu+L} \| x-y\|^2 + \frac{1}{\mu+L} \| f'_x -f'_y\|^2 \end{aligned}

接下来我们分析 L-smooth and \mu-strongly convex 函数的收敛速率。

∥xt+1−x⋆∥2=∥xt−γft′−x⋆∥2=∥xt−x⋆∥2−2γ⟨ft′−f⋆′,xt−x⋆⟩+γ2∥ft′∥2(Proposition 1)≤∥xt−x⋆∥2−2γμLμ+L∥xt−x⋆∥2−2γμ+L∥ft′∥2+γ∥ft′∥2(let γ=2μ+L)=(L−μL+μ)2∥xt−x⋆∥2(let k=Lμ)=(k−1k+1)2∥xt−x⋆∥2\begin{aligned} \|x_{t+1} - x_\star\|^2 &= \| x_t - \gamma f'_t - x_\star\|^2 \\ &= \| x_t - x_\star\|^2 - 2\gamma \langle f'_t - f'_\star, x_t-x_\star \rangle + \gamma^2\| f'_t\|^2 \\ \text{(Proposition 1)}\quad &\leq \| x_t - x_\star\|^2 - \frac{2\gamma \mu L}{\mu+L}\| x_t - x_\star\|^2 - \frac{2\gamma}{\mu+L} \| f'_t\|^2 + \gamma\| f'_t\|^2 \\ \text{(let}\gamma=\frac{2}{\mu+L}\text{)}\quad &= \bigg(\frac{L-\mu}{L+\mu}\bigg)^2 \| x_t - x_\star\|^2 \\ \text{(let}k=\frac{L}{\mu}\text{)}\quad &= \bigg(\frac{k-1}{k+1}\bigg)^2 \| x_t - x_\star\|^2 \end{aligned}

则

∥xt−x⋆∥2≤(k−1k+1)2t∥x0−x⋆∥2\| x_t - x_\star\|^2 \leq \bigg(\frac{k-1}{k+1}\bigg)^{2t} \| x_0 - x_\star\|^2

由 L-smoothness quadratic upper bound

ft−f⋆≤L2∥xt−x⋆∥2≤(k−1k+1)2t∥x0−x⋆∥2f_t - f_\star \leq \frac{L}{2} \| x_t - x_\star\|^2\leq \bigg(\frac{k-1}{k+1}\bigg)^{2t} \| x_0 - x_\star\|^2

kk 又叫 condition number, 表示 ff 的 hession 的最大特征值和最小特征值的比值。当 kk 比较大时 k−1k+1≈1−1k\frac{k-1}{k+1} \approx 1- \frac{1}{k}. 另外有不等式 1−a≤e−a1-a \leq e^{-a}. 那么可得

ft−f⋆≤(1−1k)2t∥x0−x⋆∥2≤e−2tk∥x0−x⋆∥2 f_t - f_\star\leq \bigg(1- \frac{1}{k}\bigg)^{2t}\| x_0 - x_\star\|^2 \leq e^{-\frac{2t}{k}} \| x_0 - x_\star\|^2

可知达到 ft−f⋆≤ϵf_t - f_\star \leq \epsilon 需要 O(klog⁡(1ϵ))O\big(k \log (\frac{1}{\epsilon})\big) 次迭代，此为 linear convergence， 远快于 sub-linear 收敛. 还可以推出条件数 kk 越大，收敛速率越糟糕。