优化方法速通
优化方法速通
近端算子(Proximal Operator) 是一种用来处理非平滑凸函数的极佳工具。标准数学定义为：对于一个凸函数 \(R(x)\) 和一个参数 \(\gamma > 0\)，点 \(v\) 的近端算子定义为：
\[
\text{prox}_{\gamma R}(v) = \arg\min_x \left( R(x) + \frac{1}{2\gamma} ||x - v||^2 \right)
\]
近端算子 \(\text{prox}_{\gamma R}\) 具有 非扩张性（Non-expansiveness） ，即对于任意 \(u, v\)，有 \(||\text{prox}_{\gamma R}(u) - \text{prox}_{\gamma R}(v)|| \le ||u - v||\)。
有一个特殊的性质，若 \(z=\text{prox}_{\gamma R}(v)\)，那么有
\[
0\in \partial R(z) + \frac{1}{\gamma}(z - v) \Longleftrightarrow v\in z + \gamma \partial R(z)
\]
反过来若 \(v\in z - \gamma \partial R(z)\)，则 \(z=\text{prox}_{\gamma R}(v)\)。
例题(Spring, 2025, C2) 假设 \(f(x)\) 是连续可导的 \(L\)-平滑且 \(\mu\)-强凸函数。
-
证明 \(g(x) = f(x) - \frac{\mu}{2}||x||^2\) 是连续可导的、凸的，并且是 \((L-\mu)\)-平滑的 。
-
利用性质 \(\frac{1}{L-\mu}||\nabla g(x)-\nabla g(y)||^2 \le \langle \nabla g(x)-\nabla g(y), x-y \rangle\) ，证明以下不等式成立 ：
\[
\mu||x-y||^2 + \frac{1}{L}||\nabla f(x)-\nabla f(y)||^2 \le (1+\frac{\mu}{L})\langle \nabla f(x)-\nabla f(y), x-y \rangle
\]
解答： \((1)\)： 首先，计算 \(g(x)\) 的梯度：
\[
\nabla g(x) = \nabla f(x) - \mu x
\]
由于 \(f(x)\) 是连续可导的，且 \(\mu x\) 也是连续可导的，因此 \(g(x)\) 也是连续可导的。
证明 \(g(x)\) 是凸的只需 \(\langle \nabla g(x) - \nabla g(y), x - y \rangle \ge 0\)，而
\[
\begin{aligned}
\langle \nabla g(x) - \nabla g(y), x - y \rangle &= \langle \nabla f(x) - \nabla f(y) - \mu (x - y), x - y \rangle\\
&= \langle \nabla f(x) - \nabla f(y), x - y \rangle - \mu ||x - y||^2\\
&\ge 0
\end{aligned}
\]
其中最后一步利用了 \(f(x)\) 的 \(\mu\)-强凸性质。
接下来证明 \(g(x)\) 是 \((L-\mu)\)-平滑的。只需证明 \(\frac{L-\mu}{2}||x||^2-g(x)\) 是凸函数。而
\[
\begin{aligned}
\frac{L-\mu}{2}||x||^2 - g(x) &= \frac{L-\mu}{2}||x||^2 - f(x) + \frac{\mu}{2}||x||^2\\
&= \frac{L}{2}||x||^2 - f(x)
\end{aligned}
\]
由于 \(f(x)\) 是 \(L\)-平滑的，所以 \(\frac{L}{2}||x||^2 - f(x)\) 是凸函数。
\((2)\)：纯计算。
例题(Spring, 2025, C3) 对于 \(g(x,\xi)=\nabla f(x) + \xi\)，其中 \(\xi\) 为零均值的噪声满足 \(\mathbb{E}[||\xi||^2]\le \sigma^2\)，SGD 的更新规则为 \(x^{k+1} = \text{prox}_{\gamma R}(x^k - \gamma g(x^k, \xi^k))\) 。利用近端算子的非扩张性（non-expansiveness）和 \(\text{prox}_{\gamma R}\) 的最优性条件，推导 \(||x^{k+1}-x^*||^2\) 的递推关系 ：
\[
||x^{k+1}-x^*||^2 \le ||x^k - x^* - \gamma(\nabla f(x^k) - \nabla f(x^*) + \xi^k)||^2
\]
解答： 对于最优解 \(x^*\)，它满足原问题 \(\min_x f(x) + R(x)\) 的一阶最优性条件：
\[
0 \in \nabla f(x^*) + \partial R(x^*)\implies x^* - \gamma \nabla f(x^*) \in x^* + \gamma \partial R(x^*)
\]
这等价于不动点形式 \(x^* = \text{prox}_{\gamma R}(x^* - \gamma \nabla f(x^*))\)。于是我们有：
\[
\begin{aligned}
||x^{k+1} - x^*|| &= ||\text{prox}_{\gamma R}(x^k - \gamma g(x^k, \xi^k)) - \text{prox}_{\gamma R}(x^* - \gamma \nabla f(x^*))||\\
&\le ||(x^k - \gamma g(x^k, \xi^k)) - (x^* - \gamma \nabla f(x^*))||\\
&= ||x^k - x^* - \gamma(\nabla f(x^k) - \nabla f(x^*) + \xi^k)||\\
\end{aligned}
\]
例题(Spring, 2025, C4) 解释什么是方差分解？说明如何将其应用于 \(||x^{k+1}-x^*||^2\) 并推导以下不等式 ：
\[
\mathbb{E}_k[||x^{k+1}-x^*||^2] \le ||x^k - x^* - \gamma(\nabla f(x^k) - \nabla f(x^*))||^2 + \gamma^2\sigma^2
\]
其中 \(\mathbb{E}_k[\cdot]\) 表示给定 \(\xi^k, ..., \xi^0\) 的条件期望 。
解答： 方差分解是概率论中的基本恒等式。对于任意随机向量 \(Z\)，它的二阶矩可以分解为：
\[
\mathbb{E}[||Z||^2] = ||\mathbb{E}[Z]||^2 + \mathbb{E}[||Z - \mathbb{E}[Z]||^2]
\]
在我们的例子中，设 \(Z = x^{k+1} - x^*\)，则：
\[
\begin{aligned}
\mathbb{E}_k[||x^{k+1}-x^*||^2] &= ||\mathbb{E}_k[x^{k+1}-x^*]||^2 + \mathbb{E}_k[||x^{k+1}-x^* - \mathbb{E}_k[x^{k+1}-x^*]||^2]\\
&= ||x^k - x^* - \gamma(\nabla f(x^k) - \nabla f(x^*))||^2 + \mathbb{E}_k[||\gamma \xi^k||^2]\\
&= ||x^k - x^* - \gamma(\nabla f(x^k) - \nabla f(x^*))||^2 + \gamma^2 \mathbb{E}_k[||\xi^k||^2]\\
&\le ||x^k - x^* - \gamma(\nabla f(x^k) - \nabla f(x^*))||^2 + \gamma^2\sigma^2
\end{aligned}
\]
例题(Spring, 2025, C5) 利用期望的塔式性质（tower property），证明当步长 \(\gamma=\frac{2}{\mu+L}\) 时，C.4 的递推式可以简化为：
\[
\mathbb{E}[||x^{k+1}-x^*||^2] \le (1-\rho)\mathbb{E}[||x^k-x^*||^2] + \gamma^2\sigma^2
\]
其中 \(\rho=\frac{4\mu L}{(\mu+L)^2}\) 。
解答： 由 \(C4\) 我们有 \(LHS\le ||x^k - x^* - \gamma(\nabla f(x^k) - \nabla f(x^*))||^2 + \gamma^2\sigma^2\)。而
\[
\begin{aligned}
&||x^k - x^* - \gamma(\nabla f(x^k) - \nabla f(x^*))||^2\\
=& ||x^k - x^*||^2 - 2\gamma \langle \nabla f(x^k) - \nabla f(x^*), x^k - x^* \rangle + \gamma^2 ||\nabla f(x^k) - \nabla f(x^*)||^2\\
\le& ||x^k - x^*||^2 - 2\gamma \langle \nabla f(x^k) - \nabla f(x^*), x^k - x^* \rangle + \gamma^2 L \langle \nabla f(x^k) - \nabla f(x^*), x^k - x^* \rangle\\
=& ||x^k - x^*||^2 - \gamma(2 - \gamma L) \langle \nabla f(x^k) - \nabla f(x^*), x^k - x^* \rangle\\
\le& ||x^k - x^*||^2 - \gamma(2 - \gamma L) \mu ||x^k - x^*||^2\\
=& (1 - \gamma(2 - \gamma L) \mu) ||x^k - x^*||^2
\end{aligned}
\]
当 \(\gamma = \frac{2}{\mu + L}\) 时，\(1 - \gamma(2 - \gamma L) \mu = 1 - \frac{4\mu L}{(\mu + L)^2} = 1 - \rho\)，代入根据全期望公式（塔式性质）\(\mathbb{E}[\cdot] = \mathbb{E}[\mathbb{E}_k[\cdot]]\) 即得。
例题(Spring, 2025, C6) 证明对于任意精度 \(\epsilon>0\)，存在一个步长使得
\[
k \ge \frac{L/\mu+3}{4}\log\frac{1}{\epsilon}
\]
时，满足：
\[
\mathbb{E}[||x^k-x^*||^2] \le \epsilon||x^0-x^*||^2 + \frac{\gamma\sigma^2}{\mu}
\]
解答： 由 \(C5\) 递推可得：
\[
\begin{aligned}
\mathbb{E}[||x^k-x^*||^2] &\le (1-\rho)^k \mathbb{E}[||x^0-x^*||^2] + \frac{\gamma^2\sigma^2}{\rho}\\
&\le \epsilon||x^0-x^*||^2 + \frac{\gamma^2\sigma^2}{\rho}
\end{aligned}
\]
一方面 \(\frac{\gamma^2\sigma^2}{\rho} = \frac{4\sigma^2}{\mu L}\cdot \frac{1}{(\mu + L)^2} \le \frac{\gamma\sigma^2}{\mu}\)，另一方面要让 \((1-\rho)^k \le \epsilon\)，只需 \(k \ge \frac{\log(1/\epsilon)}{\log(1/(1-\rho))}\)，又 \(\frac{\log(1/\epsilon)}{\log(1/(1-\rho))} \le \frac{1}{\rho}\log\frac{1}{\epsilon}\)，而 \(\frac{1}{\rho} = \frac{(\mu + L)^2}{4\mu L} = \frac{1}{4}(\frac{L}{\mu} + 2 + \frac{\mu}{L}) \le \frac{L/\mu + 3}{4}\)。