分布式处理与计算：数值优化方法

大 O 符号#

定义:对于两个有相同定义域的函数 $f$ 与 $g$,如果存在常数 $C > 0$ 以及 $x_0$,使得当 $x \ge x_0$ 时 $|f(x)| \le C\,|g(x)|$ ，记 $f(x) = O(g(x))$

性质:$f = O(1)$ 表示 $f$ 是有界的;$f = O(g)$ 表示 $f$ 的增长不超过 $g$ 的量级。

证明思路:假设存在 $C_1, C_2$ 使得 $f_1 = O(g_1)$、$f_2 = O(g_2)$,则对和式有 $|f_1+f_2| \le C_1|g_1| + C_2|g_2| \le (C_1+C_2)\max(|g_1|,|g_2|)$,令 $C = C_1+C_2$ 即得 $f_1+f_2 = O(\max(g_1,g_2))$,得证。

一些简单关系:$O(g_1) + O(g_2) = O(\max(g_1, g_2))$,$O(g_1)\cdot O(g_2) = O(g_1 g_2)$。

小 o 符号#

定义:如果对每一个常数 $\epsilon > 0$ 都存在 $x_0$,使得当 $x \ge x_0$ 时，$|f(x)| \le \epsilon\,|g(x)|$ ， 记 $f(x) = o(g(x))$

等价于 $\lim_{x\to\infty}\frac{f(x)}{g(x)} = 0$,即 $f$ 的量级严格低于 $g$

性质:如果 $f = o(g)$,则也有 $f = O(g)$(小 o 比大 O 更强)。

一些简单关系:$o(g_1) + o(g_2) = o(\max(g_1,g_2))$,$o(g_1)\cdot o(g_2) = o(g_1 g_2)$。

Weierstrass 定理#

Weierstrass 定理:取值于闭区间 $[a,b]$ 上的连续函数 $f$,其最大值、最小值一定存在,并且在区间中取得。

平衡点(驻点):使得梯度 $\nabla f(x) = 0$ 的点称为平衡点。但 $\nabla f(x)=0$ 并不能保证是全局最优点,它可能只是局部最优点或鞍点。

凸函数#

凸函数:如果对任意 $x_1, x_2$ 及 $\lambda \in [0,1]$,有

$f\big(\lambda x_1 + (1-\lambda)x_2\big) \le \lambda f(x_1) + (1-\lambda)f(x_2)$

那么 $f$ 被称为凸函数。

严格凸函数:如果对任意 $x_1 \ne x_2$ 及 $\lambda \in (0,1)$,把上式的 $\le$ 换成严格的 $<$,那么 $f$ 被称为严格凸函数。凸函数的重要意义在于:局部最优即全局最优。

中值定理#

假设连续函数 $f$ 取值在闭区间 $[a,b]$ 上,并且在 $(a,b)$ 上可导,那么一定可以找到一点 $\xi \in (a,b)$ 使得

$f'(\xi) = \frac{f(b) - f(a)}{b - a}$

泰勒展开#

假设 $f$ 在点 $x_0$ 附近的区间中 $n$ 阶可导,那么对任意 $x$,都可以把 $f$ 在 $x_0$ 处泰勒展开:

$f(x) = f(x_0) + f'(x_0)(x-x_0) + \frac{f''(x_0)}{2!}(x-x_0)^2 + \cdots + \frac{f^{(n)}(x_0)}{n!}(x-x_0)^n + o\big((x-x_0)^n\big)$

算法的收敛速率#

如果存在常数 $q$ 使得

$\lim_{k\to\infty}\frac{\|x_{k+1} - x^*\|}{\|x_k - x^*\|^{\,q}} = C \quad (0 < C < \infty)$

那么称 $x_k$ 收敛到 $x^*$ 的速率为 $q$ 阶。当 $q=1$ 时称线性收敛速率,$q=2$ 时称二次收敛速率(牛顿法在良好条件下即二次收敛)。

梯度与 Hessian 矩阵#

梯度向量(一阶偏导组成的列向量):

$\nabla f(x) = \left(\frac{\partial f}{\partial x_1}, \dots, \frac{\partial f}{\partial x_p}\right)^{\top}$

Hessian 矩阵(二阶偏导组成的对称方阵):

$\nabla^2 f(x) = \left[\frac{\partial^2 f}{\partial x_i \partial x_j}\right]_{p\times p}$

NR 算法的一些问题#

• Hessian 矩阵求逆的计算量在某些情况下过大,并且 Hessian 可能不可逆;
• 在 NR 算法中,函数值 $f(x_k)$ 并不保证随每次迭代递减(步长可能太大冲过头);
• NR 算法对初值的依赖程度较高,初值不好可能不收敛。

回溯线搜索(Backtracking line search)#

提出背景:为了解决 NR 算法在某些情况下迭代步长太大、导致不收敛的问题,用回溯线搜索筛选出既足够长、又能保证 $f$ 递减的步长。

算法步骤:

1. 给定参数 $\alpha \in (0, 0.5)$、$\beta \in (0,1)$,令步长 $t = 1$;
2. 判断下面的充分下降条件是否成立:

$f(x + t\,\Delta x) \le f(x) + \alpha\,t\,\nabla f(x)^{\top}\Delta x$

若为真则进行第 3 步(接受这个 $t$),否则进行第 4 步;

3. 接受步长,更新 $x \leftarrow x + t\Delta x$;

4. 缩小步长 $t \leftarrow \beta t$,并重新回到第 2 步

解释:充分下降条件成立时,说明 $x$ 与 $x+t\Delta x$ 之间连线的斜率,比 $x$ 点处斜率的 $\alpha$ 倍还要平缓——若不满足就说明步子迈太大,需要缩小步长。

收敛标准#

• 绝对收敛标准:$\|x_{k+1} - x_k\| < \epsilon$;
• 相对收敛标准:$\dfrac{\|x_{k+1} - x_k\|}{\|x_k\|} < \epsilon$;
• 调整的相对收敛标准:$\dfrac{\|x_{k+1} - x_k\|}{\|x_k\| + 1} < \epsilon$(避免 $\|x_k\|$ 太小时分母失稳)。

例子:逻辑回归#

假设有一组样本 $(x_i, y_i)$,考虑逻辑回归 $p_i = \frac{1}{1+e^{-x_i^{\top}\beta}}$。似然函数与对数似然分别为

$L(\beta) = \prod_i p_i^{y_i}(1-p_i)^{1-y_i}, \qquad \ell(\beta) = \sum_i\big[y_i\log p_i + (1-y_i)\log(1-p_i)\big]$

对 $\beta$ 分别求一阶导(梯度)、二阶导(Hessian),得到

$\nabla\ell(\beta) = X^{\top}(y - p), \qquad \nabla^2\ell(\beta) = -X^{\top}W X$

其中 $W = \text{diag}\big(p_i(1-p_i)\big)$。因而 $\beta$ 可以通过下面的迭代(牛顿法 / IRLS)来估计

$\beta_{k+1} = \beta_k + (X^{\top}W X)^{-1}X^{\top}(y - p)$

每次迭代后计算变化量并与给定阈值比较,判断是否收敛。

例子#

Lasso 是带 $L_1$ 正则的回归:$\min_\beta \frac{1}{2}\|y - X\beta\|^2 + \lambda\|\beta\|_1$。引入辅助变量 $z$,写成约束形式 $\min \frac{1}{2}\|y-X\beta\|^2 + \lambda\|z\|_1$ s.t. $\beta - z = 0$。增广拉格朗日函数为

$L_\rho = \frac{1}{2}\|y - X\beta\|^2 + \lambda\|z\|_1 + u^{\top}(\beta - z) + \frac{\rho}{2}\|\beta - z\|^2$

对 $\beta$ 求导并令其为 0,得到 $\beta$ 更新是一个岭回归式解:

$\beta_{k+1} = (X^{\top}X + \rho I)^{-1}\big(X^{\top}y + \rho z_k - u_k\big)$

而 $z$ 的更新公式是软阈值(soft-thresholding)算子:

$z_{k+1} = S_{\lambda/\rho}\big(\beta_{k+1} + u_k/\rho\big), \qquad S_\kappa(a) = \text{sign}(a)\max(|a| - \kappa,\ 0)$

例子:分位数回归#

分位数的定义与损失:分位数回归希望找一条直线拟合样本的 $\tau$ 分位数。它用的是检验损失(pinball loss):

$\rho_\tau(u) = u\big(\tau - \mathbb{1}[u < 0]\big) = \begin{cases} \tau\,u, & u \ge 0 \\ (\tau-1)\,u, & u < 0 \end{cases}$

可以理解为:给小于分位数的点(残差为负)一个权重,给大于分位数的点另一个权重(给多数点小权重、少数点大权重)。

几何意义:希望回归曲线之下能够包含 $\tau$ 比例的数据点。

优化:对样本 $(x_i, y_i)$,考虑 $\min_\beta \sum_i \rho_\tau(y_i - x_i^{\top}\beta)$。同样引入辅助变量写成约束形式,构造增广拉格朗日函数,按 ADMM 交替更新 $\beta$、辅助变量、对偶变量;对 $\beta$ 子问题求偏导并令其为 0,得到 $\beta$ 的闭式更新(形如 $\beta = (X^{\top}X)^{-1}X^{\top}(\cdot)$),辅助变量更新则用与 pinball 损失对应的阈值算子。

梯度下降算法(GD)#

给定一组样本 $(x_i, y_i)$,考虑 $\min_\beta \frac{1}{n}\sum_i \ell(x_i, y_i; \beta)$。若只考虑线性模型 $\hat y_i = x_i^{\top}\beta$,目标就是均方误差。对当前估计 $\beta_k$,梯度下降的迭代步骤为

$\beta_{k+1} = \beta_k - t\,\nabla f(\beta_k), \qquad \nabla f(\beta_k) = \frac{1}{n}\sum_{i=1}^{n}\nabla\ell(x_i, y_i; \beta_k)$

其中 $t$ 为步长。

步长 $t$ 的选择:通常用 Backtracking line search 筛选出足够长、又能保证目标函数递减的步长。给定当前估计,若充分下降条件 $f(\beta - t\nabla f) \le f(\beta) - \alpha t\|\nabla f\|^2$ 不成立,就令 $t \leftarrow \beta t$ 缩小步长再试。

随机梯度下降法(SGD)#

给定当前估计值 $\beta_k$,随机梯度下降每步随机抽取一个样本 $(x_i, y_i)$,只用它算梯度来更新:

$\beta_{k+1} = \beta_k - t\,\nabla\ell(x_i, y_i; \beta_k)$

直到事先给定的收敛准则被满足后停止。

GD 与 SGD 对比#

• 梯度下降法:每步用全体样本求平均梯度;
• 随机梯度下降法:每步随机抽取一个样本估计梯度。

当样本数量巨大时,GD 每步都要算全体样本的平均,计算量极大。SGD 不能保证每一步都让目标函数下降,相比 GD 往往需要更多迭代次数,但每次迭代的计算量小得多。折中办法是小批量(mini-batch):每次随机抽取一小组样本估计梯度,兼顾稳定与速度。

BFGS 与 L-BFGS#

BFGS 算法适用条件:当 Hessian 矩阵维度超大时,求逆非常困难、计算复杂度极高。BFGS 通过迭代逼近 Hessian 的逆,即在牛顿迭代过程中,用一个矩阵 $B_k$ 来代替 $[\nabla^2 f(x_k)]^{-1}$,每步用梯度差和位置差对 $B_k$ 做秩更新,避免直接求逆。

L-BFGS 算法:由于 BFGS 每次都要存储 $p\times p$ 的近似矩阵,内存开销很大,数据维度高时机器可能吃不消。L-BFGS 只保存最近 $m$ 次迭代的信息(向量对)用于隐式重构更新方向,大幅节省内存,适合超高维问题。