《机器学习理论导引》笔记目录
0 感言
感觉这章整体而言自己理解得并不充分,更多像是把周老师的教材进行打印,之后有时间我会重新进行整理的。
7.3 随机优化
7.3.1 凸函数
下给出随机优化的代表性算法——随机梯度下降法 (Stochastic Gradient Descent,SGD) 的流程。
其中要求 wtboldsymbol{w}_t 的随机梯度 gtboldsymbol{g}_t 是真实梯度 ∇f(wt)nabla f(boldsymbol{w}_t) 的无偏估计,即 :
E[gt]=∇f(wt)mathbb{E}[boldsymbol{g}_t] = nabla f(boldsymbol{w}_t)
上述方法非常适合机器学习问题。下面以监督学习为例,监督学习的最终目标是最小化泛化风险,令数据分布为 Dmathcal{D},可以用风险最小化 (Risk Minimization) 的方法来描述监督学习的目标 :
minw∈Wf(w)=Ez∼D[ℓ(w,z)]min _{boldsymbol{w} in mathcal{W}} f(boldsymbol{w})=mathbb{E}_{boldsymbol{z} sim mathcal{D}}[ell(boldsymbol{w}, boldsymbol{z})]
其中 z∈Dboldsymbol{z} in mathcal{D} 表示 zboldsymbol{z} 是从数据分布 Dmathcal{D} 中采样获得,ℓ(⋅,⋅)ell(cdot,cdot) 为损失函数,但是在现实场景中很难直接获得真实的数据分布 Dmathcal{D},因此经常采用经验风险最小化 (Empirical Risk Minimization,ERM) 的方法来近似风险最小化的目标 : 从数据分布 Dmathcal{D} 中采样获得 mm 个样本 z1,z2,⋯ ,zm,∀zi=(xi,yi)boldsymbol{z}_1,boldsymbol{z}_2,cdots,boldsymbol{z}_m,forall boldsymbol{z}_i=(boldsymbol{x}_i,y_i),xiboldsymbol{x}_i 为样本特征,yiy_i 为样本标记,然后用这 nn 个样本来近似风险最小化的目标 :
minw∈Wf(w)=1m∑i=1mℓ(w,zi)min_{boldsymbol{w} in mathcal{W}} f(boldsymbol{w})=frac{1}{m} sum_{i=1}^{m} ell(boldsymbol{w}, boldsymbol{z}_i)
当 mm 很大的时候计算代价很高,因此采用随机梯度下降法 (Stochastic Gradient Descent,SGD) 来近似风险最小化的目标,将上述算法中第 3 步改为下式即可 :
wt+1′=wt−ηt∇ℓ(wt,zt)boldsymbol{w}_{t+1}’=boldsymbol{w}_{t}-eta_{t}nabla ellleft(boldsymbol{w}_{t}, boldsymbol{z}_{t}right)
其中 ztboldsymbol{z}_t 表示从数据分布 Dmathcal{D} 中随机采样获得的样本,从上面的描述可以看出随机梯度下降每轮迭代只需要利用 1 个样本。而对于一般的 Lipschitz 连续凸函数,随机梯度下降法的收敛速度为 O(1T)O(frac{1}{sqrt{T}}),具体有如下定理 :
定理 7.4 随机梯度下降收敛率 假设目标函数的随机梯度有上界,且可行域有界,则随机梯度下降的收敛率为 O(1T)O(frac{1}{sqrt{T}})。
证明 假设随机梯度上界为 ll,可行域 Wmathcal{W} 直径为 ΓGamma,即对于任意 t∈[T],u,v∈Wtin[T],u,vinmathcal{W}
∥gt∥⩽l∥u−v∥⩽Γbegin{array}{r}
left|mathbf{g}_tright| leqslant l \
|boldsymbol{u}-boldsymbol{v}| leqslant Gamma
end{array}
同样为了简化分析,考虑固定的步长 ηt=ηeta_t=eta,则对于任意的 w∈Wwinmathcal{W},
f(wt)−f(w)⩽⟨∇f(wt),wt−w⟩=⟨gt,wt−w⟩+⟨∇f(wt)−gt,wt−w⟩=1η⟨wt−wt+1′,wt−w⟩+⟨∇f(wt)−gt,wt−w⟩=12η(∥wt−w∥2−∥wt+1′−w∥2+∥wt−wt+1′∥2)+⟨∇f(wt)−gt,wt−w⟩=12η(∥wt−w∥2−∥wt+1′−w∥2)+η2∥gt∥2+⟨∇f(wt)−gt,wt−w⟩(利用∥ΠW(x)−ΠW(z)∥⩽∥x−z∥,∀x,z)⩽12η(∥wt−w∥2−∥wt+1−w∥2)+η2∥gt∥2+⟨∇f(wt)−gt,wt−w⟩⩽12η(∥wt−w∥2−∥wt+1−w∥2)+η2l2+⟨∇f(wt)−gt,wt−w⟩begin{aligned}
& fleft(boldsymbol{w}_tright)-f(boldsymbol{w}) \
& leqslantleftlanglenabla fleft(boldsymbol{w}_tright), boldsymbol{w}_t-boldsymbol{w}rightrangle=leftlanglemathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle+leftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle \
& =frac{1}{eta}leftlangleboldsymbol{w}_t-boldsymbol{w}_{t+1}^{prime}, boldsymbol{w}_t-boldsymbol{w}rightrangle+leftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle \
& =frac{1}{2 eta}left(left|boldsymbol{w}_t-boldsymbol{w}right|^2-left|boldsymbol{w}_{t+1}^{prime}-boldsymbol{w}right|^2+left|boldsymbol{w}_t-boldsymbol{w}_{t+1}^{prime}right|^2right)+leftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle \
& =frac{1}{2 eta}left(left|boldsymbol{w}_t-boldsymbol{w}right|^2-left|boldsymbol{w}_{t+1}^{prime}-boldsymbol{w}right|^2right)+frac{eta}{2}left|mathbf{g}_tright|^2+leftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle \
&quadtext{(利用}left|Pi_{mathcal{W}}(boldsymbol{x})-Pi_{mathcal{W}}(boldsymbol{z})right| leqslant|boldsymbol{x}-boldsymbol{z}|, quad forall boldsymbol{x}, boldsymbol{z})
\
& leqslant frac{1}{2 eta}left(left|boldsymbol{w}_t-boldsymbol{w}right|^2-left|boldsymbol{w}_{t+1}-boldsymbol{w}right|^2right)+frac{eta}{2}left|mathbf{g}_tright|^2+leftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle \
& leqslant frac{1}{2 eta}left(left|boldsymbol{w}_t-boldsymbol{w}right|^2-left|boldsymbol{w}_{t+1}-boldsymbol{w}right|^2right)+frac{eta}{2} l^2+leftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle
end{aligned}
对上面的不等式从 t=1t=1 到 t=Tt=T 求和,得到
∑t=1Tf(wt)−Tf(w)⩽12η(∥w1−w∥2−∥wT+1−w∥2)+ηT2l2+∑t=1T⟨∇f(wt)−gt,wt−w⟩⩽12η∥w1−w∥2+ηT2l2+∑t=1T⟨∇f(wt)−gt,wt−w⟩⩽12ηΓ2+ηT2l2+∑t=1T⟨∇f(wt)−gt,wt−w⟩begin{aligned}
& sum_{t=1}^T fleft(boldsymbol{w}_tright)-T f(boldsymbol{w}) \
& quad leqslant frac{1}{2 eta}left(left|boldsymbol{w}_1-boldsymbol{w}right|^2-left|boldsymbol{w}_{T+1}-boldsymbol{w}right|^2right)+frac{eta T}{2} l^2+sum_{t=1}^Tleftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle \
& quad leqslant frac{1}{2 eta}left|boldsymbol{w}_1-boldsymbol{w}right|^2+frac{eta T}{2} l^2+sum_{t=1}^Tleftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle \
& quad leqslant frac{1}{2 eta} Gamma^2+frac{eta T}{2} l^2+sum_{t=1}^Tleftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle
end{aligned}
最后,依据 Jensen 不等式,有
f(w‾T)−f(w)=f(1T∑t=1Twt)−f(w)⩽1T∑t=1Tf(wt)−f(w)⩽Γ22ηT+ηl22+1T∑t=1T⟨∇f(wt)−gt,wt−w⟩begin{aligned}
fleft(overline{boldsymbol{w}}_Tright)-f(boldsymbol{w}) & =fleft(frac{1}{T} sum_{t=1}^T boldsymbol{w}_tright)-f(boldsymbol{w}) \
& leqslant frac{1}{T} sum_{t=1}^T fleft(boldsymbol{w}_tright)-f(boldsymbol{w}) \
& leqslant frac{Gamma^2}{2 eta T}+frac{eta l^2}{2}+frac{1}{T} sum_{t=1}^Tleftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle
end{aligned}
可以看出,上式与章节 7.2.1 中梯度下降分析的结果的区别在于多了一项 1T∑t=1T⟨∇f(wt)−gt,wt−w⟩frac{1}{T} sum_{t=1}^Tleftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle
下面证明随机梯度下降算法期望意义上的收敛率,利用 wtboldsymbol{w}_t 的随机梯度 gtboldsymbol{g}_t 是真实梯度 ∇f(wt)nabla f(boldsymbol{w}_t) 的无偏估计,有
E[∑t=1T⟨∇f(wt)−gt,wt−w⟩]=E[∑t=1T⟨∇f(wt),wt−w⟩]−E[∑t=1T⟨gt,wt−w⟩]=∑t=1T[E[⟨∇f(wt),wt−w⟩]−E[⟨gt,wt−w⟩]]=∑t=1T[E[⟨E[gt],wt−w⟩]−E[⟨gt,wt−w⟩]]=∑t=1T[E[gt,wt−w⟩]−E[⟨gt,wt−w⟩]]=0begin{aligned}
&mathbb{E}left[sum_{t=1}^Tlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rangleright] \
=&mathbb{E}left[sum_{t=1}^Tlanglenabla fleft(boldsymbol{w}_tright), boldsymbol{w}_t-boldsymbol{w}rangleright]-mathbb{E}left[sum_{t=1}^Tlanglemathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rangleright] \
=&sum_{t=1}^Tleft[mathbb{E}left[langlenabla fleft(boldsymbol{w}_tright), boldsymbol{w}_t-boldsymbol{w}rangleright]-mathbb{E}left[langlemathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rangleright]right] \
=&sum_{t=1}^Tleft[mathbb{E}left[langlemathbb{E}left[mathbf{g}_tright], boldsymbol{w}_t-boldsymbol{w}rangleright]-mathbb{E}left[langlemathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rangleright]right] \
=&sum_{t=1}^Tleft[mathbb{E}left[mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rangleright]-mathbb{E}left[langlemathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rangleright]right] \
=&0
end{aligned}
对于上面的不等式求期望有
E[f(w‾T)]−f(w)⩽Γ22ηT+ηl22=lΓTmathbb{E}left[fleft(overline{boldsymbol{w}}_Tright)right]-f(boldsymbol{w}) leqslant frac{Gamma^2}{2 eta T}+frac{eta l^2}{2}=frac{l Gamma}{sqrt{T}}
其中令 η=Γ/(lT)eta=Gamma/(lsqrt{T})
前面的分析证明了从期望意义上的收敛率,为了分析随机梯度下降算法的理论保障,将利用针对鞅差序列的 Azuma 不等式,利用 wtboldsymbol{w}_t 的随机梯度 gtboldsymbol{g}_t 是真实梯度 ∇f(wt)nabla f(boldsymbol{w}_t) 的无偏估计,可知 ⟨∇f(w1)−g1,w1−w⟩,…langlenabla f(boldsymbol{w}_1)-g_1,boldsymbol{w}_1-boldsymbol{w}rangle,ldots 组成一个鞅差序列,有
∣⟨∇f(wt)−gt,wt−w⟩∣⩽∥∇f(wt)−gt∥∥wt−w∥⩽Γ(∥∇f(wt)∥+∥gt∥)⩽2lΓbegin{aligned}
left|leftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangleright| & leqslantleft|nabla fleft(boldsymbol{w}_tright)-mathbf{g}_tright|left|boldsymbol{w}_t-boldsymbol{w}right| \
& leqslant Gammaleft(left|nabla fleft(boldsymbol{w}_tright)right|+left|boldsymbol{g}_tright|right) leqslant 2 l Gamma
end{aligned}
上式的推导过程中利用了 Jensen 不等式获得 ∥∇f(wt)∥lVertnabla f(boldsymbol{w}_t)rVert 的上界
∥∇f(wt)∥=∥E[gt]∥⩽E[∥gt∥]⩽lleft|nabla fleft(boldsymbol{w}_tright)right|=left|mathbb{E}left[mathbf{g}_tright]right| leqslant mathbb{E}left[left|mathbf{g}_tright|right] leqslant l
根据 Azuma 不等式推论 P(∑i=1mXi⩾ϵ)⩽e−ϵ2/2∑i=1mci2Pleft(sum_{i=1}^m X_i geqslant epsilonright) leqslant e^{-epsilon^2 / 2 sum_{i=1}^m c_i^2},以至少 1−δ1-delta 的概率有
∑t=1T⟨∇f(wt)−gt,wt−w⟩⩽2lΓ2Tlog1δsum_{t=1}^Tleftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}rightrangle leqslant 2 l Gamma sqrt{2 T log frac{1}{delta}}
将上式代入前面的不等式,以至少 1−δ1-delta 的概率有
f(w‾T)−f(w)⩽Γ22ηT+ηl22+2lΓ2Tlog1δ=lΓT(1+22log1δ)=O(1T)begin{aligned}
fleft(overline{boldsymbol{w}}_Tright)-f(boldsymbol{w}) & leqslant frac{Gamma^2}{2 eta T}+frac{eta l^2}{2}+2 l Gamma sqrt{frac{2}{T} log frac{1}{delta}}\&=frac{l Gamma}{sqrt{T}}left(1+2 sqrt{2 log frac{1}{delta}}right)
=Oleft(frac{1}{sqrt{T}}right)
end{aligned}
7.3.2 强凸函数
为了处理强凸函数,引入阶段随机梯度下降 (Epoch-GD) 算法,其流程如下 :
若目标函数 f:W↦Rf:mathcal{W}mapstomathbb{R} 是 λlambda-强凸的,在期望意义上的 Epoch-GD 的额外风险界为 O(1/[λT])O(1/[lambda T]),下进行相关证明
引理 7.1 将 Epoch-GD 的参数设置为 T1=4T_1=4 和 η1=1/λeta_1=1/lambda,ll 为随机梯度的上界,令 Δk=f(w1k)−f(w∗),Vk=l2/(λ2k−2)Delta_k=f(boldsymbol{w}_1^k)-f(boldsymbol{w}^*),V_k=l^2/(lambda2^{k-2}),对于任意的 kk
E[Δk]⩽Vkmathbb{E}left[Delta_kright] leqslant V_k
证明 当随机梯度的上界为 ll 时,根据先前推论 ∥∇f(wt)∥=∥E[gt]∥⩽E[∥gt∥]⩽lleft|nabla fleft(boldsymbol{w}_tright)right|=left|mathbb{E}left[mathbf{g}_tright]right| leqslant mathbb{E}left[left|mathbf{g}_tright|right] leqslant l 可知,真实梯度的上界也为 ll。因此,定理 7.2 成立。然后易知下面式子成立 :
Tk=8l2λVk=2k+1ηk=Vk2l2=1λ2k−1begin{aligned}
T_k & =frac{8 l^2}{lambda V_k}=2^{k+1} \
eta_k & =frac{V_k}{2 l^2}=frac{1}{lambda 2^{k-1}}
end{aligned}
下使用数学归纳法来进行证明
-
当 k=1k=1 时,引理成立 :
E[Δ1]=E[f(w11)−f(w∗)]⩽2l2λ=l2λ21−2=V1 mathbb{E}left[Delta_1right]=mathbb{E}left[fleft(boldsymbol{w}_1^1right)-fleft(boldsymbol{w}^*right)right] leqslant frac{2 l^2}{lambda}=frac{l^2}{lambda 2^{1-2}}=V_1
-
假设对于某正整数 k⩾1kgeqslant1,引理仍成立 E[Δk]⩽Vk=l2/(λ2k−2)mathbb{E}left[Delta_kright] leqslant V_k=l^2/(lambda2^{k-2})
-
对于正整数 k+1k+1,令 Ek[X]mathbb{E}_k[X] 为前 kk 轮的期望,则有
Ek[f(w1k+1)]−f(w∗)⩽ηkl22+∥w∗−w1k∥22ηkTk⩽ηkl22+ΔkηkTkλ. begin{aligned}
mathbb{E}_kleft[fleft(boldsymbol{w}_1^{k+1}right)right]-fleft(boldsymbol{w}^*right) & leqslant frac{eta_k l^2}{2}+frac{left|boldsymbol{w}^*-boldsymbol{w}_1^kright|^2}{2 eta_k T_k} \
& leqslant frac{eta_k l^2}{2}+frac{Delta_k}{eta_k T_k lambda} .
end{aligned}
因此,k+1k+1 的时候情况也成立 :
E[Δk+1]⩽ηkl22+E[Δk]ηkTkλ⩽ηkl22+l22k−2ηkTkλ2=l22k−1λbegin{aligned}
mathbb{E}left[Delta_{k+1}right] & leqslant frac{eta_k l^2}{2}+frac{mathbb{E}left[Delta_kright]}{eta_k T_k lambda} \
& leqslant frac{eta_k l^2}{2}+frac{l^2}{2^{k-2} eta_k T_k lambda^2}=frac{l^2}{2^{k-1} lambda}
end{aligned}
引理得证。
定理 7.5 Epoch-GD 的收敛率 当目标函数 f(⋅)f(cdot) 为 λlambda-强凸时,Epoch-GD 期望意义上的收敛率为 O(1T)O(frac{1}{T})。
证明 Epoch-GD 外层循环的轮数,是由满足 ∑i=1kTi⩽Tsum_{i=1}^kT_ileqslant T 的最大 kk 决定的。由于
∑i=1k2i−1T1=(2k−1)T1⩽Tsum_{i=1}^k 2^{i-1} T_1=left(2^k-1right) T_1 leqslant T
因此,最后一轮迭代的轮数 k†=⌊log2(T/T1+1)⌋k^{dagger}=leftlfloorlog _2left(T / T_1+1right)rightrfloor,而算法的最后输出是 w1k†+1boldsymbol{w}_1^{k^{dagger}+1},根据引理 7.1,有
E[f(w1k†+1)]−f(w∗)=E[Δk†+1]⩽Vk†+1=l22k†−1λ⩽16l2λT=O(1λT)begin{aligned}
mathbb{E}left[fleft(boldsymbol{w}_1^{k^{dagger}+1}right)right]&-fleft(boldsymbol{w}^*right) =mathbb{E}left[Delta_{k^{dagger}+1}right] \
& leqslant V_{k^{dagger}+1}=frac{l^2}{2^{k^{dagger}-1} lambda} \
& leqslant frac{16 l^2}{lambda T}=Oleft(frac{1}{lambda T}right)
end{aligned}
定理得证。
定理 7.6 针对鞅的 Bernstein 不等式 假设 X1,…,XnX_1,ldots,X_n 是定义在 f=(fi)1⩽i⩽nf=(f_i)_{1leqslant ileqslant n} 上的有界鞅差分序列,且满足 ∣Xi∣⩽Mleft|X_iright|leqslant M,令
Si=∑j=1iXjS_i=sum_{j=1}^i X_j
为对应的鞅,将条件方差 (conditional variance) 记为
Vn2=∑t=1nE[δt2∣ft−1]V_n^2=sum_{t=1}^n mathbb{E}left[delta_t^2 mid f_{t-1}right]
那么对于任意的正数 tt 和 vv,有
P(maxi=1,…,nSi>t and Vn2⩽ν)⩽exp(−t22(ν+Kt/3))Pleft(max _{i=1, ldots, n} S_i>t text { and } V_n^2 leqslant nuright) leqslant exp left(-frac{t^2}{2(nu+K t / 3)}right)
因此可以得到
P(maxiSi>2ντ+23Kτ and Vn2⩽ν)⩽e−τPleft(max _i S_i>sqrt{2 nu tau}+frac{2}{3} K tau text { and } V_n^2 leqslant nuright) leqslant e^{-tau}
分析内层循环的随机梯度下降在强凸函数下的收敛性质,有以下引理 :
引理 7.2 假设随机梯度上界为 ll,目标函数 f(⋅)f(cdot) 为 λlambda-强凸。运行 TT 轮的随机梯度下降更新
wt+1=ΠW(wt−ηgt)boldsymbol{w}_{t+1}=Pi_{mathcal{W}}left(boldsymbol{w}_t-eta mathbf{g}_tright)
其中 gtmathbf{g}_t 是函数 f(⋅)f(cdot) 在 wtboldsymbol{w}_t 处的随机梯度,以至少 1−δ1-delta 的概率有
∑t=1Tf(wt)−Tf(w∗)⩽ηTl22+∥w1−w∗∥22η+4l2λ(1+83logmδ)sum_{t=1}^T fleft(boldsymbol{w}_tright)-T fleft(boldsymbol{w}^*right) leqslant frac{eta T l^2}{2}+frac{left|boldsymbol{w}_1-boldsymbol{w}^*right|^2}{2 eta}+frac{4 l^2}{lambda}left(1+frac{8}{3} log frac{m}{delta}right)
其中 m=⌈2log2T⌉m=lceil2log_2Trceil
证明 由于 f(⋅)f(cdot) 是强凸的,因此
f(wt)−f(w∗)⩽⟨∇f(wt),wt−w∗⟩−λ2∥wt−w∗∥2=⟨gt,wt−w∗⟩+⟨∇f(wt)−gt,wt−w∗⟩−λ2∥wt−w∗∥2begin{aligned}
fleft(boldsymbol{w}_tright)-fleft(boldsymbol{w}^*right) & leqslantleftlanglenabla fleft(boldsymbol{w}_tright), boldsymbol{w}_t-boldsymbol{w}^*rightrangle-frac{lambda}{2}left|boldsymbol{w}_t-boldsymbol{w}^*right|^2 \
& =leftlanglemathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}^*rightrangle+leftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}^*rightrangle-frac{lambda}{2}left|boldsymbol{w}_t-boldsymbol{w}^*right|^2
end{aligned}
对其从 t=1t=1 到 TT 进行求和,有
∑t=1Tf(wt)−Tf(w∗)⩽ηTl22+∥w1−w∗∥22η+∑t=1T⟨∇f(wt)−gt,wt−w∗⟩−λ2∑t=1T∥wt−w∗∥2begin{aligned}
sum_{t=1}^T fleft(boldsymbol{w}_tright)- & T fleft(boldsymbol{w}^*right) leqslant frac{eta T l^2}{2}+frac{left|boldsymbol{w}_1-boldsymbol{w}^*right|^2}{2 eta} \
& +sum_{t=1}^Tleftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}^*rightrangle-frac{lambda}{2} sum_{t=1}^Tleft|boldsymbol{w}_t-boldsymbol{w}^*right|^2
end{aligned}
定义鞅差序列
δt=⟨∇f(wt)−gt,wt−w∗⟩delta_t=leftlanglenabla fleft(boldsymbol{w}_tright)-mathbf{g}_t, boldsymbol{w}_t-boldsymbol{w}^*rightrangle
为了得到 ∑tδtsum_tdelta_t 的上界,将利用剥离技术 (peeling technique) 和针对鞅的 Bernstein 不等式。首先,注意到上面的鞅差序列是有界的 :
∣δt∣⩽∥∇f(wt)−gt∥∥wt−w∗∥⩽2l2lλ=4l2λ定义AT=∑t=1T∥wt−w∗∥2⩽4l2Tλ2begin{aligned}
left|delta_tright| &leqslantleft|nabla fleft(boldsymbol{w}_tright)-mathbf{g}_tright|left|boldsymbol{w}_t-boldsymbol{w}^*right| leqslant 2 l frac{2 l}{lambda}=frac{4 l^2}{lambda}\
text{定义}&quad A_T=sum_{t=1}^Tleft|boldsymbol{w}_t-boldsymbol{w}^*right|^2 leqslant frac{4 l^2 T}{lambda^2}
end{aligned}
对于条件方差,下面的不等式成立 :
VT2=∑t=1TEt−1[δt2]⩽4l2∑t=1T∥wt−w∗∥2=4l2ATV_T^2=sum_{t=1}^T mathbb{E}_{t-1}left[delta_t^2right] leqslant 4 l^2 sum_{t=1}^Tleft|boldsymbol{w}_t-boldsymbol{w}^*right|^2=4 l^2 A_T
- 当 AT⩽4l2λ2TA_T leqslant frac{4 l^2}{lambda^2 T} 时
∑t=1Tδt⩽2l∑t=1T∥wt−w∗∥⩽2lT∑t=1T∥wt−w∗∥2⩽4l2λsum_{t=1}^T delta_t leqslant 2 l sum_{t=1}^Tleft|boldsymbol{w}_t-boldsymbol{w}^*right| leqslant 2 l sqrt{T} sqrt{sum_{t=1}^Tleft|boldsymbol{w}_t-boldsymbol{w}^*right|^2} leqslant frac{4 l^2}{lambda} - 当 AT∈(4l2λ2T,4l2Tλ2]A_T inleft(frac{4 l^2}{lambda^2 T}, frac{4 l^2 T}{lambda^2}right] 时,分解成 m=⌈2log2T⌉m=lceil2log_2Trceil 种可能,即
AT∈(2i−14l2λ2T,2i4l2λ2T],i=1,…,⌈2log2T⌉A_T inleft(2^{i-1} frac{4 l^2}{lambda^2 T}, 2^i frac{4 l^2}{lambda^2 T}right], i=1, ldots,leftlceil 2 log _2 Trightrceil
综合上面两种情况,通过一系列变换可以证明
P(∑t=1Tδt⩾24l2ATτ+234l2λτ+4l2λ)=P(∑t=1Tδt⩾24l2ATτ+234l2λτ+4l2λ,AT⩽4l2λ2T)+P(∑t=1Tδt⩾24l2ATτ+234l2λτ+4l2λ,4l2λ2T<AT⩽4l2Tλ2)=P(∑t=1Tδt⩾24l2ATτ+234l2λτ+4l2λ,VT2⩽4l2AT,4l2λ2T<AT⩽4l2Tλ2)(利用上面的分解)⩽∑i=1mP(∑t=1Tδt⩾24l2ATτ+234l2λτ+4l2λ,VT2⩽4l2AT,4l2λ2T2i−1<AT⩽4l2λ2T2i)(利用 AT 的上下界来化简不等式)⩽∑i=1mP(∑t=1Tδt⩾216l42iλ2Tτ+234l2λτ,VT2⩽16l42iλ2T](利用定理 7.6)⩽me−τbegin{aligned}
& Pleft(sum_{t=1}^T delta_t geqslant 2 sqrt{4 l^2 A_T tau}+frac{2}{3} frac{4 l^2}{lambda} tau+frac{4 l^2}{lambda}right) \
=& Pleft(sum_{t=1}^T delta_t geqslant 2 sqrt{4 l^2 A_T tau}+frac{2}{3} frac{4 l^2}{lambda} tau+frac{4 l^2}{lambda}, A_T leqslant frac{4 l^2}{lambda^2 T}right) \
+&Pleft(sum_{t=1}^T delta_t geqslant 2 sqrt{4 l^2 A_T tau}+frac{2}{3} frac{4 l^2}{lambda} tau+frac{4 l^2}{lambda}, frac{4 l^2}{lambda^2 T}<A_T leqslant frac{4 l^2 T}{lambda^2}right)\
=& Pleft(sum_{t=1}^T delta_t geqslant 2 sqrt{4 l^2 A_T tau}+frac{2}{3} frac{4 l^2}{lambda} tau+frac{4 l^2}{lambda}, V_T^2 leqslant 4 l^2 A_T, frac{4 l^2}{lambda^2 T}<A_T leqslant frac{4 l^2 T}{lambda^2}right) \
&qquadtext{(利用上面的分解)}\
leqslant& sum_{i=1}^m Pleft(sum_{t=1}^T delta_t geqslant 2 sqrt{4 l^2 A_T tau}+frac{2}{3} frac{4 l^2}{lambda} tau+frac{4 l^2}{lambda}, right. \
&qquad left.V_T^2 leqslant 4 l^2 A_T,frac{4 l^2}{lambda^2 T} 2^{i-1}<A_T leqslant frac{4 l^2}{lambda^2 T} 2^iright) \
&qquadtext{(利用 } A_T text{ 的上下界来化简不等式)}\
leqslant & sum_{i=1}^m Pleft(sum_{t=1}^T delta_t geqslant sqrt{2 frac{16 l^4 2^i}{lambda^2 T} tau}+frac{2}{3} frac{4 l^2}{lambda} tau, V_T^2 leqslant frac{16 l^4 2^i}{lambda^2 T}right] \
&qquadtext{(利用定理 7.6)}\
leqslant & m e^{-tau}
end{aligned}
然后令 τ=logmδ=log⌈2log2T⌉δtau=logfrac{m}{delta}=logfrac{lceil2log_2Trceil}{delta} 可得,以至少 1−δ1-delta 的概率有
∑t=1Tδt⩽24l2ATlogmδ+8l23λlogmδ+4l2λsum_{t=1}^T delta_t leqslant 2 sqrt{4 l^2 A_T log frac{m}{delta}}+frac{8 l^2}{3 lambda} log frac{m}{delta}+frac{4 l^2}{lambda}
将其代入上面的累加式,以至少 1−δ1-delta 的概率有
∑t=1Tf(wt)−Tf(w∗)⩽ηTl22+∥w1−w∗∥22η+24l2ATlogmδ+8l23λlogmδ+4l2λ−λ2AT⩽ηTl22+∥w1−w∗∥22η+32l23λlogmδ+4l2λbegin{aligned}
& sum_{t=1}^T fleft(boldsymbol{w}_tright)-T fleft(boldsymbol{w}^*right) \
& leqslant frac{eta T l^2}{2}+frac{left|boldsymbol{w}_1-boldsymbol{w}^*right|^2}{2 eta}+2 sqrt{4 l^2 A_T log frac{m}{delta}}+frac{8 l^2}{3 lambda} log frac{m}{delta}+frac{4 l^2}{lambda}-frac{lambda}{2} A_T \
& leqslant frac{eta T l^2}{2}+frac{left|boldsymbol{w}_1-boldsymbol{w}^*right|^2}{2 eta}+frac{32 l^2}{3 lambda} log frac{m}{delta}+frac{4 l^2}{lambda}
end{aligned}
引理得证。
利用引理 7.2 分析 Epoch-GD 外层循环的性质,得到如下引理 :
引理 7.3 令 δ∈(0,1)deltain(0,1) 表示失败的概率,定义
δ~=δk†k†=⌊log2(2Tα+1)⌋begin{aligned}
tilde{delta} & =frac{delta}{k^{dagger}} \
k^{dagger} & =leftlfloorlog _2left(frac{2 T}{alpha}+1right)rightrfloor
end{aligned}
其中 αalpha 为满足以下条件的最小偶数
α⩾24+1283log⌊log2(T12+1)⌋⌈2log2T⌉δalpha geqslant 24+frac{128}{3} log frac{leftlfloorlog _2left(frac{T}{12}+1right)rightrfloorleftlceil 2 log _2 Trightrceil}{delta}
将 Epoch-GD 的参数设置为 T1=α/2T_1=alpha/2 和 η1=1/λeta_1=1/lambda,对于任意的 kk,以至少 (1−δ~)k−1(1-tilde{delta})^{k-1} 的概率有
Δk=f(w1k)−f(w∗)⩽Vk=l2λ2k−2Delta_k=fleft(boldsymbol{w}_1^kright)-fleft(boldsymbol{w}^*right) leqslant V_k=frac{l^2}{lambda 2^{k-2}}
证明 根据 αalpha 的满足条件可知,α⩾24alphageqslant24,因此
k†⩽⌊log2(T12+1)⌋δ~=δk†⩾δ⌊log2(T12+1)⌋begin{aligned}
k^{dagger} & leqslantleftlfloorlog _2left(frac{T}{12}+1right)rightrfloor \
tilde{delta} & =frac{delta}{k^{dagger}} geqslant frac{delta}{leftlfloorlog _2left(frac{T}{12}+1right)rightrfloor}
end{aligned}
由上式解出 δdelta 代回,可得
α⩾24+1283log⌈2log2T⌉δ~alpha geqslant 24+frac{128}{3} log frac{leftlceil 2 log _2 Trightrceil}{tilde{delta}}
对引理 7.1 中的部分推论进行改写
Tk=8l2λVk=2k+1⇒Tk=αl2λVk=α2k−2T_k=frac{8 l^2}{lambda V_k}=2^{k+1}Rightarrow T_k=frac{alpha l^2}{lambda V_k}=alpha2^{k-2}
继续使用数学归纳法
- k=1k=1 时,根据定理 7.2,命题显然成立
- 假设对于正整数 k⩾1kgeqslant1,Δk⩽VkDelta_kleqslant V_k 以至少 (1−δ~)k−1(1-tilde{delta})^{k-1} 的概率成立
- 考虑 k+1k+1 时,结合定理 7.2,以至少 (1−δ~)⋅(1−δ~)k−1=(1−δ~)k(1-tilde{delta})cdot(1-tilde{delta})^{k-1}=(1-tilde{delta})^{k} 的概率有
Δk+1=f(w1k+1)−f(w∗)⩽1Tk∑t=1Tkf(wtk)−f(w∗)⩽ηkl22+∥w1k−w∗∥22ηkTk+1Tk(1+83logmkδ~)4l2λ⩽ηkl22+ΔkηkTkλ+1Tk(1+83logmkδ~)4l2λ⩽Vk4+2Vkα+λVkαl2(1+83logmkδ~)4l2λ=Vk4+Vkα(6+323logmkδ~)begin{aligned}
Delta_{k+1} & =fleft(boldsymbol{w}_1^{k+1}right)-fleft(boldsymbol{w}^*right) \
& leqslant frac{1}{T_k} sum_{t=1}^{T_k} fleft(boldsymbol{w}_t^kright)-fleft(boldsymbol{w}^*right) \
& leqslant frac{eta_k l^2}{2}+frac{left|boldsymbol{w}_1^k-boldsymbol{w}^*right|^2}{2 eta_k T_k}+frac{1}{T_k}left(1+frac{8}{3} log frac{m_k}{tilde{delta}}right) frac{4 l^2}{lambda} \
& leqslant frac{eta_k l^2}{2}+frac{Delta_k}{eta_k T_k lambda}+frac{1}{T_k}left(1+frac{8}{3} log frac{m_k}{tilde{delta}}right) frac{4 l^2}{lambda} \
& leqslant frac{V_k}{4}+frac{2 V_k}{alpha}+frac{lambda V_k}{alpha l^2}left(1+frac{8}{3} log frac{m_k}{tilde{delta}}right) frac{4 l^2}{lambda} \
& =frac{V_k}{4}+frac{V_k}{alpha}left(6+frac{32}{3} log frac{m_k}{tilde{delta}}right)
end{aligned}
其中 mk=⌈2log2Tk⌉m_k=lceil2log_2T_krceil,结合 αalpha 的限制,以至少 (1−δ~)k(1-tilde{delta})^{k} 的概率有
Δk+1⩽Vk2=Vk+1Delta_{k+1}leqslantfrac{V_k}{2}=V_{k+1}
k+1k+1 的时候递归成立,数学归纳法成立,命题得证。
定理 7.7 Epoch-GD 大概率情况下的收敛率 若目标函数 f(⋅)f(cdot) 为 λlambda-强凸函数,Epoch-GD 以大概率取得 O(loglogTλT)O(frac{loglog T}{lambda T}) 的收敛率
证明 Epoch-GD 外层循环的轮数,是由满足 ∑i=1kTi⩽Tsum_{i=1}^kT_ileqslant T 的最大 kk 决定的,由于
∑i=1kTi=∑i=1kα2i−2=α2(2k−1)sum_{i=1}^k T_i=sum_{i=1}^k alpha 2^{i-2}=frac{alpha}{2}left(2^k-1right)
因此,最后一轮迭代的轮数 k†k^{dagger} 与引理 7.3 中的定义相吻合,算法最终输出是 w1k†+1boldsymbol{w}^{k^{dagger}+1}_1。根据引理 7.3,以至少 (1−δ~)k†(1-tilde{delta})^{k^{dagger}} 的概率有
f(w1k†+1)−f(w∗)=Δk†+1⩽Vk†+1=l22k†−1λ⩽2αl2λTbegin{aligned}
fleft(boldsymbol{w}_1^{k^{dagger}+1}right)-fleft(boldsymbol{w}^*right) & =Delta_{k^{dagger}+1} \
& leqslant V_{k^{dagger}+1}=frac{l^2}{2^{k^{dagger}-1} lambda} leqslant frac{2 alpha l^2}{lambda T}
end{aligned}
然后,证明概率 (1−δ~)k†>1−δ(1-tilde{delta})^{k^{dagger}}>1-delta,由于函数 (1−1x)x(1-frac{1}{x})^x 在 x>1x>1 时是增函数,因此
(1−δ~)k†=(1−δk†)k†=((1−1k†/δ)k†/δ)δ⩾((1−11/δ)1/δ)δ=1−δbegin{aligned}
(1-tilde{delta})^{k^{dagger}}=left(1-frac{delta}{k^{dagger}}right)^{k^{dagger}} & =left(left(1-frac{1}{k^{dagger} / delta}right)^{k^{dagger} / delta}right)^delta \
& geqslantleft(left(1-frac{1}{1 / delta}right)^{1 / delta}right)^delta=1-delta
end{aligned}
由上面两式可知,以至少 1−δ1-delta 的概率有
f(w1k†+1)−f(w∗)⩽2αl2λT=O(loglogTλT)fleft(boldsymbol{w}_1^{k^{dagger}+1}right)-fleft(boldsymbol{w}^*right) leqslant frac{2 alpha l^2}{lambda T}=Oleft(frac{log log T}{lambda T}right)
定理得证。
7.4 实例分析
7.4.1 支持向量机
首先引入如何使用确定优化方法来求解支持向量机 (Supporting Vector Machine, SVM) : 令 (x1,y1),…,(xm,ym)(boldsymbol{x}_1,y_1),ldots,(boldsymbol{x}_m,y_m) 为 mm 个训练样本,其中 xi∈Rd,yi∈{−1,+1}boldsymbol{x}_iinmathbb{R}^d,y_iin{-1,+1},支持向量机的优化问题为 :
minwf(w)=∑i=1mmax(0,1−yiwTxi) s.t. ∥w∥⩽Λbegin{aligned}
& min _{boldsymbol{w}} f(boldsymbol{w})=sum_{i=1}^m max left(0,1-y_i boldsymbol{w}^{mathrm{T}} boldsymbol{x}_iright) \
& text { s.t. }|boldsymbol{w}| leqslant Lambda
end{aligned}
由于 hinge 损失并不光滑,需要对梯度进行如下的计算替换,称之为次梯度 (sub-gradient) :
∇f(w)=∑i=1mgi,gi={−yixi,1−yiwTxi⩾00,1−yiwTxi<0begin{aligned}
nabla f(boldsymbol{w}) & =sum_{i=1}^m mathbf{g}_i, \
mathbf{g}_i & = begin{cases}-y_i boldsymbol{x}_i, & 1-y_i boldsymbol{w}^{mathrm{T}} boldsymbol{x}_i geqslant 0 \
0, & 1-y_i boldsymbol{w}^{mathrm{T}} boldsymbol{x}_i<0 end{cases}
end{aligned}
由于目标函数是凸函数,可以将 7.2.1 节中的梯度下降算法来进行求解。具体如下 :
根据定理 7.1 的分析,可以得到如下收敛率。
定理 7.8 优化支持向量机的收敛率 梯度下降求解支持向量机的收敛率为 O(1T)O(frac{1}{sqrt{T}})
证明 假设 ∥xi∥⩽r,i∈[m]lVertboldsymbol{x}_irVertleqslant r,iin[m],根据定理 7.1 步长的设置依赖于梯度的上界,梯度上界为
∥∇f(w)∥⩽∑i=1m∥yixi∥⩽mr|nabla f(boldsymbol{w})| leqslant sum_{i=1}^mleft|y_i boldsymbol{x}_iright| leqslant m r
可行域的直径为 Γ=2ΛGamma=2Lambda,根据定理 7.1,将步长设置为 η=2Λ/(mrT)eta=2Lambda/(mrsqrt{T}) 有
f(w‾T)−min∥w∥⩽Λf(w)⩽2mrΛT=O(1T)fleft(overline{boldsymbol{w}}_Tright)-min _{|boldsymbol{w}| leqslant Lambda} f(boldsymbol{w}) leqslant frac{2 m r Lambda}{sqrt{T}}=Oleft(frac{1}{sqrt{T}}right)
定理得证。
7.4.2 对率回归
给定训练数据集 D={(x1,y1),…,(xm,ym)}D={(boldsymbol{x}_1,y_1),ldots,(boldsymbol{x}_m,y_m)},对率回归的优化问题如下 :
minwf(w)=1m∑i=1mln(1+exp(−yiwTxi)) s.t. ∥w∥⩽Λbegin{aligned}
min _{boldsymbol{w}} f(boldsymbol{w})&=frac{1}{m} sum_{i=1}^m ln left(1+exp left(-y_i boldsymbol{w}^{mathrm{T}} boldsymbol{x}_iright)right) \
text { s.t. }&quad|boldsymbol{w}| leqslant Lambda
end{aligned}
为了计算随机梯度,将在每一轮均匀随机选择 1 个样本作为输入,将 tt 轮迭代选取的样本记为 (xt,yt)(boldsymbol{x}_t,y_t),则 f(⋅)f(cdot) 在当前解 wtboldsymbol{w}_t 处的随机梯度可以计算为
gt=ytexp(−ytwtTxt)1+exp(−ytwiTxt)xtmathbf{g}_t=frac{y_t exp left(-y_t boldsymbol{w}_t^{mathrm{T}} boldsymbol{x}_tright)}{1+exp left(-y_t boldsymbol{w}_i^{mathrm{T}} boldsymbol{x}_tright)} boldsymbol{x}_t
根据定理 7.4 的分析,可以得到如下收敛率
定理 7.9 优化对率回归的收敛率 随机梯度下降求解对率回归的收敛率为 O(1T)O(frac{1}{sqrt{T}})
证明 假设 ∥xi∥⩽r,i∈[m]lVertboldsymbol{x}_irVertleqslant r,iin[m],首先计算随机梯度的上界
∥exp(−ytwtTxt)1+exp(−ytwtTxt)ytxt∥⩽∥xt∥⩽rleft|frac{exp left(-y_t boldsymbol{w}_t^{mathrm{T}} boldsymbol{x}_tright)}{1+exp left(-y_t boldsymbol{w}_t^{mathrm{T}} boldsymbol{x}_tright)} y_t boldsymbol{x}_tright| leqslantleft|boldsymbol{x}_tright| leqslant r
因为可行域的直径 Γ=2ΛGamma=2Lambda,依据定理 7.4,调整步长为 η=2Λ/(rT)eta=2Lambda/(rsqrt{T}),则以至少 1−δ1-delta 的概率有
f(wˉT)−min∥w∥⩽Λf(w)⩽2ΛrT(1+22log1δ)=O(1T)fleft(bar{boldsymbol{w}}_Tright)-min _{|boldsymbol{w}| leqslant Lambda} f(boldsymbol{w}) leqslant frac{2 Lambda r}{sqrt{T}}left(1+2 sqrt{2 log frac{1}{delta}}right)=Oleft(frac{1}{sqrt{T}}right)
定理得证