数据科学优化：旧事重提
在这轮笔记中，我们试着回忆本学期《数据科学导论》PPT 中与优化有关的内容，主要包括：
- 梯度下降（Gradient Descent, GD）的下降性质、收敛速度及其所需条件；
- 随机梯度下降（Stochastic Gradient Descent, SGD）的基本不等式、期望界与高概率界；
- 强凸条件下 SGD 的收敛；
- 方差缩减方法 SVRG。
实际深度学习中还经常使用 AdamW 与 Muon，不过本文暂不展开。
1. 梯度下降
1.1 算法定义
设目标函数为
\[
\min_{x\in\mathbb R^d} f(x).
\]
给定初始点 \(x_0\)，梯度下降迭代为
\[
x_{k+1}=x_k-\alpha_k\nabla f(x_k),
\qquad k=0,1,\ldots,
\]
其中 \(\alpha_k>0\) 为步长。
为什么选择负梯度方向作为下降方向？
关键在于：如果 \(\nabla f\) 是 \(L\)-Lipschitz 连续的，即
\[
\|\nabla f(x)-\nabla f(y)\|_2\le L\|x-y\|_2,
\]
注：对于二阶可微的情况下，这等价于Hesse阵的2范数小于等于L
那么由下降引理（descent lemma），对任意 \(x,y\in\mathbb R^d\)，都有
\[
f(y)
\le
f(x)+\langle \nabla f(x),y-x\rangle
+\frac L2\|y-x\|_2^2.
\]
令
\[
y=x-\alpha\nabla f(x),
\]
则
\[
\begin{aligned}
f(y)
&\le
f(x)-\alpha\|\nabla f(x)\|_2^2
+\frac{L\alpha^2}{2}\|\nabla f(x)\|_2^2\\
&=
f(x)-\alpha\left(1-\frac{L\alpha}{2}\right)
\|\nabla f(x)\|_2^2.
\end{aligned}
\]
因此，只要下降的步长足够小，在此处可以写为\(0<\alpha_k<\frac{2}{L}\)
就有
\[
f(x_{k+1})\le f(x_k).
\]
1.2 梯度范数的次线性收敛
将上面的下降不等式应用于梯度下降，并对 \(k<t\) 求和：
\[
\begin{aligned}
\sum_{k< t}
\alpha_k\left(1-\frac{L\alpha_k}{2}\right)
\|\nabla f(x_k)\|_2^2
&\le
\sum_{k< t}\bigl(f(x_k)-f(x_{k+1})\bigr)\\
&=f(x_0)-f(x_t).
\end{aligned}
\]
若取常数步长
\[
\alpha_k=\alpha\in\left(0,\frac{2}{L}\right),
\]
则
\[
\begin{aligned}
\min_{k< t}\|\nabla f(x_k)\|_2^2
&\le
\frac1t\sum_{k< t}\|\nabla f(x_k)\|_2^2\\
&\le
\frac{2}{t\alpha(2-\alpha L)}
\bigl(f(x_0)-f(x_t)\bigr)\\
&\le
\frac{2}{t\alpha(2-\alpha L)}
\bigl(f(x_0)-f(x^*)\bigr).
\end{aligned}
\]
对 \(\alpha\) 优化可得 \(\alpha=1/L\)，于是
\[
\boxed{
\min_{k< t}\|\nabla f(x_k)\|_2^2
\le
\frac{2L}{t}\bigl(f(x_0)-f(x^*)\bigr)
}.
\]
这里并没有使用凸性。因此，对一般光滑非凸函数，梯度下降至少可以保证在 \(O(1/t)\) 的意义下找到近似驻点。
1.3 MM 算法视角
梯度下降也可以放在 MM（Majorization-Minimization）框架中理解。构造代理函数
\[
M(x,y)
=
f(x)+\langle\nabla f(x),y-x\rangle
+\frac L2\|y-x\|_2^2.
\]
由下降引理，
\[
M(x,y)\ge f(y),
\qquad
M(x,x)=f(x).
\]
然后令
\[
x_{k+1}\in\arg\min_y M(x_k,y).
\]
对 \(M(x_k,y)\) 关于 \(y\) 求最小值，便得到
\[
x_{k+1}=x_k-\frac1L\nabla f(x_k).
\]
当然，我们关于梯度下降算法，例如牛顿法，拟牛顿法等部分放在了优化对应的部分，还附上了一些数值实验。
2. 不要求凸性时的函数值收敛
2.1 一个广义星凸条件
假设存在 \(\gamma>0\)，使得
\[
\langle\nabla f(x),x-x^*\rangle
\ge
\gamma\bigl(f(x)-f(x^*)\bigr).
\tag{1}
\]
由 Cauchy--Schwarz 不等式，
\[
\gamma\bigl(f(x)-f(x^*)\bigr)
\le
\langle\nabla f(x),x-x^*\rangle
\le
\|\nabla f(x)\|_2\|x-x^*\|_2.
\]
采用步长 \(1/L\)：
\[
x_{k+1}=x_k-\frac1L\nabla f(x_k).
\]
记
\[
\varepsilon_k=f(x_k)-f(x^*),
\]
并定义初始水平集半径
\[
R=
\max_{f(x)\le f(x_0)}\|x-x^*\|_2.
\]
由于函数值单调下降，所有 \(x_k\) 都位于该水平集内。因此，由条件 (1)，
\[
\varepsilon_k
\le
\frac1\gamma\|x_k-x^*\|_2\|\nabla f(x_k)\|_2
\le
\frac R\gamma\|\nabla f(x_k)\|_2.
\]
另一方面，由下降引理，
\[
f(x_{k+1})
\le
f(x_k)-\frac1{2L}\|\nabla f(x_k)\|_2^2.
\]
于是
\[
\varepsilon_{k+1}
\le
\varepsilon_k-
\frac1{2L}
\left(\frac{\gamma\varepsilon_k}{R}\right)^2.
\]
即
\[
\varepsilon_k-\varepsilon_{k+1}
\ge
\frac{\gamma^2}{2LR^2}\varepsilon_k^2.
\]
由于 \(\varepsilon_{k+1}\le\varepsilon_k\)，
\[
\begin{aligned}
\frac1{\varepsilon_{k+1}}-
\frac1{\varepsilon_k}
&=
\frac{\varepsilon_k-\varepsilon_{k+1}}
{\varepsilon_k\varepsilon_{k+1}}\\
&\ge
\frac{\varepsilon_k-\varepsilon_{k+1}}
{\varepsilon_k^2}\\
&\ge
\frac{\gamma^2}{2LR^2}.
\end{aligned}
\]
若 \(x^*\) 是可微函数的极小点，则 \(\nabla f(x^*)=0\)。再由 \(L\)-光滑性，
\[
\varepsilon_0
=f(x_0)-f(x^*)
\le
\frac L2\|x_0-x^*\|_2^2
\le
\frac{LR^2}{2}.
\]
对 \(k=0,\ldots,t-1\) 求和：
\[
\begin{aligned}
\frac1{\varepsilon_t}
&\ge
\frac1{\varepsilon_0}
+\frac{t\gamma^2}{2LR^2}\\
&\ge
\frac{2}{LR^2}
+\frac{t\gamma^2}{2LR^2}\\
&=
\frac{\gamma^2t+4}{2LR^2}.
\end{aligned}
\]
因此
\[
\boxed{
f(x_t)-f(x^*)
\le
\frac{2LR^2}{\gamma^2t+4}
=O\left(\frac1t\right)
}.
\]
2.2 PL 条件与线性收敛
若希望函数值线性收敛，并不一定需要强凸性。一个常用条件是 Polyak--Łojasiewicz（PL）条件：存在 \(m>0\)，使得
\[
\|\nabla f(x)\|_2^2
\ge
2m\bigl(f(x)-f(x^*)\bigr),
\qquad \forall x.
\]
结合步长 \(1/L\) 时的下降不等式，
\[
f(x_{k+1})
\le
f(x_k)-\frac1{2L}\|\nabla f(x_k)\|_2^2,
\]
可得
\[
f(x_{k+1})-f(x^*)
\le
\left(1-\frac mL\right)
\bigl(f(x_k)-f(x^*)\bigr).
\]
因此
\[
\boxed{
f(x_k)-f(x^*)
\le
\left(1-\frac mL\right)^k
\bigl(f(x_0)-f(x^*)\bigr)
}.
\]
PL 条件不蕴含凸性。例如，PPT 中给出的非凸例子是
\[
f(x)=x^2+3\sin^2 x.
\]
PL 条件对于分析过参数化深度学习中的 GD 与 SGD 很重要。
3. 不可微优化与近端梯度
对于不可微但凸的函数，可以用次梯度代替梯度。例如，ReLU 在 \(x=0\) 处不可微，但存在次梯度。
需要注意的是，即使每一层所使用的函数本身是凸函数，函数复合后也未必保持凸性。因此，神经网络的整体优化问题通常仍然是非凸的。
考虑复合优化问题
\[
\min_{x\in\mathbb R^d} F(x)
=
\min_{x\in\mathbb R^d}\bigl(f(x)+h(x)\bigr),
\]
其中 \(f\) 光滑，\(h\) 可以不可微。近端梯度下降为
\[
\boxed{
x_{k+1}
=
\operatorname{Prox}_{\alpha_k h}
\bigl(x_k-\alpha_k\nabla f(x_k)\bigr)
},
\]
其中
\[
\operatorname{Prox}_{\alpha h}(v)
:=
\arg\min_x
\left\{
h(x)+\frac1{2\alpha}\|x-v\|_2^2
\right\}.
\]
4. 近似梯度与 SGD 的基本不等式
考虑凸优化问题
\[
\min_{x\in\mathbb R^d}f(x),
\]
并采用近似梯度迭代
\[
x_{k+1}=x_k-\alpha_k g_k,
\]
其中 \(g_k\) 是 \(\nabla f(x_k)\) 的近似。
4.1 Key step
取常数步长 \(\alpha_k=\alpha\)。对任意比较点 \(z\)，
\[
\begin{aligned}
\|x_{k+1}-z\|_2^2
&=
\|x_k-\alpha g_k-z\|_2^2\\
&=
\|x_k-z\|_2^2
-2\alpha\langle g_k,x_k-z\rangle
+\alpha^2\|g_k\|_2^2\\
&=
\|x_k-z\|_2^2
+2\alpha
\langle g_k-\nabla f(x_k)+\nabla f(x_k),z-x_k\rangle
+\alpha^2\|g_k\|_2^2.
\end{aligned}
\]
由凸性，
\[
\langle\nabla f(x_k),z-x_k\rangle
\le
f(z)-f(x_k).
\]
定义误差项
\[
\varepsilon_k
:=
\langle g_k-\nabla f(x_k),z-x_k\rangle.
\]
于是
\[
\|x_{k+1}-z\|_2^2
\le
\|x_k-z\|_2^2
+2\alpha\bigl(f(z)-f(x_k)+\varepsilon_k\bigr)
+\alpha^2\|g_k\|_2^2.
\]
整理得到基本不等式：
\[
\boxed{
f(x_k)
\le
f(z)
+\frac{\|x_k-z\|_2^2}{2\alpha}
-\frac{\|x_{k+1}-z\|_2^2}{2\alpha}
+\varepsilon_k
+\frac\alpha2\|g_k\|_2^2
}.
\]
4.2 平均迭代点的误差界
设
\[
G=
\max_k\max\bigl\{
\|g_k\|_2,
\|\nabla f(x_k)\|_2
\bigr\},
\]
并取
\[
\alpha=\frac c{\sqrt t}.
\]
定义平均迭代点
\[
\bar x_t=\frac1t\sum_{k< t}x_k.
\]
将基本不等式对 \(k<t\) 求和，再利用凸性，得到
\[
\begin{aligned}
f(\bar x_t)
&\le
\frac1t\sum_{k< t}f(x_k)\\
&\le
f(z)
+\frac{\|x_0-z\|_2^2}{2c\sqrt t}
+\frac{cG^2}{2\sqrt t}
+\frac1t\sum_{k< t}\varepsilon_k.
\end{aligned}
\]
5. SGD 的鞅差误差项
SGD 中假设随机梯度满足无偏性：
\[
\mathbb E\!\left[g_k\mid\mathcal F_{k-1}\right]
=
\nabla f(x_k),
\]
其中 \(\mathcal F_{k-1}\) 表示第 \(k\) 次采样前的历史信息。
由于 \(x_k\) 对 \(\mathcal F_{k-1}\) 可测，
\[
\begin{aligned}
\mathbb E\!\left[\varepsilon_k\mid\mathcal F_{k-1}\right]
&=
\mathbb E\!\left[
\langle g_k-\nabla f(x_k),z-x_k\rangle
\mid\mathcal F_{k-1}
\right]\\
&=
\left\langle
\mathbb E\!\left[g_k-\nabla f(x_k)
\mid\mathcal F_{k-1}\right],
z-x_k
\right\rangle\\
&=0.
\end{aligned}
\]
因此 \(\{\varepsilon_k\}\) 是鞅差序列，并且
\[
\mathbb E[\varepsilon_k]=0.
\]
若
\[
D=\max_k\|x_k-z\|_2,
\]
则
\[
\begin{aligned}
|\varepsilon_k|
&\le
\|g_k-\nabla f(x_k)\|_2\|z-x_k\|_2\\
&\le
2GD
=:B.
\end{aligned}
\]
5.1 高概率界
由条件 Hoeffding 引理，
\[
\mathbb E\!\left[e^{\lambda\varepsilon_k}
\mid\mathcal F_{k-1}\right]
\le
\exp\left(\frac{\lambda^2B^2}{2}\right).
\]
递推可得
\[
\mathbb E\exp\left(
\lambda\sum_{k< t}\varepsilon_k
\right)
\le
\exp\left(\frac{\lambda^2tB^2}{2}\right).
\]
因此，对任意 \(s>0\)，
\[
\begin{aligned}
\mathbb P\left(
\sum_{k< t}\varepsilon_k\ge s
\right)
&\le
\exp\left(-\lambda s+
\frac{\lambda^2tB^2}{2}\right)\\
&\le
\exp\left(-\frac{s^2}{2tB^2}\right),
\end{aligned}
\]
其中最后一步取
\[
\lambda=\frac{s}{tB^2}.
\]
令右端等于 \(\delta\)，则以至少 \(1-\delta\) 的概率，
\[
\sum_{k< t}\varepsilon_k
\le
B\sqrt{2t\log\frac1\delta}.
\]
取 \(z=x^*\)，可得
\[
\boxed{
f(\bar x_t)-f^*
\le
\frac{\|x_0-x^*\|_2^2}{2c\sqrt t}
+\frac{cG^2}{2\sqrt t}
+B\sqrt{\frac{2\log(1/\delta)}{t}}
}
\]
以至少 \(1-\delta\) 的概率成立。
5.2 期望界
由塔式法则，
\[
\mathbb E[\varepsilon_k]
=
\mathbb E\!\left[
\mathbb E[\varepsilon_k\mid\mathcal F_{k-1}]
\right]
=0.
\]
因此
\[
\boxed{
\mathbb E\bigl[f(\bar x_t)-f^*\bigr]
\le
\frac{\|x_0-x^*\|_2^2}{2c\sqrt t}
+\frac{cG^2}{2\sqrt t}
}.
\]
这给出了凸情形下 SGD 的典型 \(O(t^{-1/2})\) 收敛率。
6. SGD 在经验风险最小化中的形式
6.1 有限样本 ERM
经验风险最小化可以写成
\[
\min_x f(x),
\qquad
f(x)=\sum_{i=1}^n f_i(x),
\]
其中
\[
f_i(x)
=
\frac1n\ell\bigl(Y_i,\phi_x(X_i)\bigr),
\]
且 \((X_i,Y_i)\) 是来自分布 \(P\) 的 i.i.d. 样本。
在第 \(k\) 次迭代中，以概率
\[
\mathbb P(i_k=j)=p_j
\]
抽取样本指标 \(i_k\)，并令
\[
g_k
=
\frac{\nabla f_{i_k}(x_k)}{p_{i_k}}.
\]
则
\[
\mathbb E[g_k\mid x_k]
=
\sum_{j=1}^np_j
\frac{\nabla f_j(x_k)}{p_j}
=
\nabla f(x_k).
\]
6.2 总体风险最小化
总体风险写为
\[
\min_x f(x)
=
\mathbb E_{(X,Y)\sim P}
\bigl[\ell(\phi_x(X),Y)\bigr].
\]
第 \(k\) 次迭代抽取
\[
(X_k,Y_k)\sim P,
\]
并令
\[
g_k
=
\nabla_x\ell\bigl(\phi_{x_k}(X_k),Y_k\bigr).
\]
7. 强凸条件下的 SGD
假设：
- \(f\) 是 \(m\)-强凸函数；
- \(\nabla f\) 是 \(L\)-Lipschitz 连续的；
-
随机梯度满足
\[ \mathbb E\|g(x)\|_2^2 \le G^2+M_f\|\nabla f(x)\|_2^2. \]
取常数步长 \(\alpha_k=\alpha\)。有
\[
\begin{aligned}
\|x_{k+1}-x^*\|_2^2
&=
\|x_k-\alpha g_k-x^*\|_2^2\\
&=
\|x_k-x^*\|_2^2
-2\alpha\langle g_k,x_k-x^*\rangle
+\alpha^2\|g_k\|_2^2.
\end{aligned}
\]
对于 \(m\)-强凸且 \(L\)-光滑的函数，有强化余单调不等式
\[
\boxed{
\langle\nabla f(x)-\nabla f(y),x-y\rangle
\ge
\frac{mL}{m+L}\|x-y\|_2^2
+
\frac1{m+L}
\|\nabla f(x)-\nabla f(y)\|_2^2
}.
\]
令 \(y=x^*\)，并使用 \(\nabla f(x^*)=0\)，得到
\[
\langle\nabla f(x_k),x_k-x^*\rangle
\ge
\frac{mL}{m+L}\|x_k-x^*\|_2^2
+
\frac1{m+L}\|\nabla f(x_k)\|_2^2.
\]
对递推式取期望：
\[
\begin{aligned}
\mathbb E\|x_{k+1}-x^*\|_2^2
&\le
\left(1-\frac{2mL\alpha}{m+L}\right)
\mathbb E\|x_k-x^*\|_2^2\\
&\quad
+\alpha^2G^2\\
&\quad
+\left(
\alpha^2M_f-
\frac{2\alpha}{m+L}
\right)
\mathbb E\|\nabla f(x_k)\|_2^2.
\end{aligned}
\]
若选择
\[
0<\alpha
\le
\frac{2}{(m+L)M_f},
\]
则最后一项非正。又因为 \(L\ge m\)，
\[
\frac{2mL}{m+L}\ge m,
\]
从而
\[
\mathbb E\|x_{k+1}-x^*\|_2^2
\le
(1-\alpha m)
\mathbb E\|x_k-x^*\|_2^2
+\alpha^2G^2.
\]
递推得到
\[
\boxed{
\mathbb E\|x_k-x^*\|_2^2
\le
(1-\alpha m)^k\|x_0-x^*\|_2^2
+
\frac{\alpha G^2}{m}
}.
\]
这说明：使用常数步长时，SGD 在初期呈线性收敛，但最终只能收敛到一个半径由 \(\alpha G^2/m\) 控制的噪声邻域。若要继续提高精度，就需要减小步长或降低方差。
7.1 GD 与 SGD 的计算复杂度比较
在强凸有限和问题中，令条件数
\[
\kappa=\frac Lm.
\]
典型复杂度可概括为：
| 方法 | 迭代复杂度 | 单次迭代成本 | 总计算成本 |
|---|---|---|---|
| GD | \(O\!\left(\kappa\log\frac1\varepsilon\right)\) | \(O(n)\) | \(O\!\left(n\kappa\log\frac1\varepsilon\right)\) |
| SGD | \(O\!\left(\frac1\varepsilon\right)\) | \(O(1)\) | \(O\!\left(\frac1\varepsilon\right)\) |
因此，当样本量 \(n\) 很大且只要求中等精度时，SGD 往往更有吸引力。粗略地说，当
\[
\frac1\varepsilon
<
n\kappa\log\frac1\varepsilon
\]
时，SGD 的总计算量可能小于 GD。
8. 方差缩减：SVRG
8.1 控制变量思想
设
\[
Z_\theta
=
X-\theta\bigl(Y-\mathbb E[Y]\bigr).
\]
则
\[
\operatorname{Var}(Z_\theta)
=
\operatorname{Var}(X)
+\theta^2\operatorname{Var}(Y)
-2\theta\operatorname{Cov}(X,Y).
\]
如果 \(Y\) 与 \(X\) 正相关，并且 \(\mathbb E[Y]\) 容易计算，就可以通过适当选择 \(\theta\) 降低方差。
SVRG（Johnson--Zhang, 2013）使用
\[
X=
\frac{\nabla f_{i_k}(x_k)}{p_{i_k}},
\qquad
Y=
\frac{\nabla f_{i_k}(\tilde x)}{p_{i_k}},
\qquad
\theta=1,
\]
其中 \(\tilde x\) 是外层循环中保存的快照点，并且
\[
\mathbb E[Y]=\nabla f(\tilde x).
\]
8.2 SVRG 算法
考虑
\[
\min_x F(x)
=
f(x)+h(x),
\qquad
f(x)=\sum_{i=1}^n f_i(x).
\]
给定内层迭代次数 \(T\)。在第 \(s\) 个 epoch：
-
从上一 epoch 的内层点中选取快照
\[ \tilde x_{s-1}=x_{s-1,j}, \qquad j\sim\operatorname{Unif}\{0,\ldots,T-1\}. \] -
计算全梯度
\[ \tilde g_s=\nabla f(\tilde x_{s-1}). \] -
令
\[ x_{s,0}=\tilde x_{s-1}. \] -
对 \(k=0,\ldots,T-1\)：
- 以概率 \(\mathbb P(i_k=j)=p_j\) 抽取 \(i_k\)；
-
计算
\[ g_{s,k} = \frac{\nabla f_{i_k}(x_{s,k})}{p_{i_k}}, \qquad \tilde g_{s,k} = \frac{\nabla f_{i_k}(\tilde x_{s-1})}{p_{i_k}}; \] -
更新
\[ \boxed{ x_{s,k+1} = \operatorname{Prox}_{\alpha h} \left( x_{s,k} -\alpha \bigl(g_{s,k}-\tilde g_{s,k}+\tilde g_s\bigr) \right) }. \]
每个 epoch 大约需要 \(n+2T\) 次分量梯度计算。
8.3 线性收敛结论
假设：
- 每个 \(f_i\) 都是凸函数；
- 每个 \(\nabla f_i\) 都是 \(L\)-Lipschitz 连续的；
- \(f\) 是 \(m\)-强凸函数；
- 暂取 \(h=0\)。
若 \(T\) 足够大，并且
\[
\rho
=
\frac{1}{m\alpha(1-2L\alpha)T}
+
\frac{2L\alpha}{1-2L\alpha}
<1,
\]
则
\[
\boxed{
\mathbb E\bigl[f(\tilde x_s)-f^*\bigr]
\le
\rho^s
\bigl(f(\tilde x_0)-f^*\bigr)
}.
\]
例如，选择
\[
T\ge\frac{9L}{m}=9\kappa,
\qquad
\alpha=\frac1{6L},
\]
可得
\[
0<\rho<\frac56.
\]
因此达到精度 \(\varepsilon\) 需要
\[
O\left(\log\frac1\varepsilon\right)
\]
个 epoch。若 \(T\asymp\max\{n,\kappa\}\)，总计算成本为
\[
\boxed{
O\left(
(n+\kappa)
\log\frac1\varepsilon
\right)
}.
\]
相比之下，GD 的复杂度为
\[
O\left(
n\kappa\log\frac1\varepsilon
\right).
\]
9. SVRG 收敛证明梗概
为简化记号，令
\[
G_{s,k}
=
g_{s,k}-\tilde g_{s,k}+\tilde g_s,
\]
则内层更新为
\[
x_{s,k+1}=x_{s,k}-\alpha G_{s,k}.
\]
定义
\[
\varepsilon_{s,k}
=
\langle
G_{s,k}-\nabla f(x_{s,k}),
x^*-x_{s,k}
\rangle.
\]
由构造可知
\[
\mathbb E\!\left[G_{s,k}\mid\mathcal F_{s,k}\right]
=
\nabla f(x_{s,k}),
\qquad
\mathbb E[\varepsilon_{s,k}]=0.
\]
由前面的 key step，
\[
\begin{aligned}
\mathbb E\|x_{s,k+1}-x^*\|_2^2
&\le
\mathbb E\|x_{s,k}-x^*\|_2^2
+2\alpha
\mathbb E\bigl[f(x^*)-f(x_{s,k})\bigr]\\
&\quad
+\alpha^2\mathbb E\|G_{s,k}\|_2^2.
\end{aligned}
\]
SVRG 的核心是证明方差界
\[
\boxed{
\mathbb E\|G_{s,k}\|_2^2
\le
4L\,
\mathbb E\left[
f(x_{s,k})-f(x^*)
+f(\tilde x_{s-1})-f(x^*)
\right]
}.
\]
于是
\[
\begin{aligned}
\mathbb E\|x_{s,k+1}-x^*\|_2^2
&\le
\mathbb E\|x_{s,k}-x^*\|_2^2\\
&\quad
-2\alpha(1-2L\alpha)
\mathbb E\bigl[f(x_{s,k})-f^*\bigr]\\
&\quad
+4L\alpha^2
\mathbb E\bigl[f(\tilde x_{s-1})-f^*\bigr].
\end{aligned}
\]
对 \(k=0,\ldots,T-1\) 求和，并使用
\[
x_{s,0}=\tilde x_{s-1}
\]
以及强凸性给出的
\[
\|\tilde x_{s-1}-x^*\|_2^2
\le
\frac2m
\bigl(f(\tilde x_{s-1})-f^*\bigr),
\]
可得
\[
\begin{aligned}
2\alpha(1-2L\alpha)T\,
\mathbb E\bigl[f(\tilde x_s)-f^*\bigr]
&\le
\left(
\frac2m+4LT\alpha^2
\right)
\mathbb E\bigl[f(\tilde x_{s-1})-f^*\bigr].
\end{aligned}
\]
两边除以 \(2\alpha(1-2L\alpha)T\)，便得到
\[
\mathbb E\bigl[f(\tilde x_s)-f^*\bigr]
\le
\rho\,
\mathbb E\bigl[f(\tilde x_{s-1})-f^*\bigr],
\]
其中
\[
\rho
=
\frac{1}{m\alpha(1-2L\alpha)T}
+
\frac{2L\alpha}{1-2L\alpha}.
\]
只要 \(\rho<1\)，就得到按 epoch 计算的线性收敛。
9.1 方差界的标准推导
在均匀采样或适当归一化的记号下，可将 \(G_{s,k}\) 写成
\[
\begin{aligned}
G_{s,k}
&=
\bigl(\nabla f_{i_k}(x_{s,k})-
\nabla f_{i_k}(x^*)\bigr)\\
&\quad
-
\bigl(\nabla f_{i_k}(\tilde x_{s-1})-
\nabla f_{i_k}(x^*)\bigr)\\
&\quad
+\nabla f(\tilde x_{s-1}).
\end{aligned}
\]
利用
\[
\|a+b\|_2^2\le2\|a\|_2^2+2\|b\|_2^2
\]
以及
\[
\mathbb E\|Z-\mathbb E Z\|_2^2
\le
\mathbb E\|Z\|_2^2,
\]
可得
\[
\begin{aligned}
\mathbb E\|G_{s,k}\|_2^2
&\le
2\mathbb E
\|\nabla f_{i_k}(x_{s,k})-
\nabla f_{i_k}(x^*)\|_2^2\\
&\quad
+2\mathbb E
\|\nabla f_{i_k}(\tilde x_{s-1})-
\nabla f_{i_k}(x^*)\|_2^2.
\end{aligned}
\]
对凸且 \(L\)-光滑的 \(f_i\)，有
\[
\|\nabla f_i(x)-\nabla f_i(x^*)\|_2^2
\le
2L\left(
f_i(x)-f_i(x^*)
-\langle\nabla f_i(x^*),x-x^*\rangle
\right).
\]
对 \(i\) 取期望并利用 \(\nabla f(x^*)=0\)，最终得到
\[
\mathbb E\|G_{s,k}\|_2^2
\le
4L\,
\mathbb E\left[
f(x_{s,k})-f(x^*)
+f(\tilde x_{s-1})-f(x^*)
\right].
\]