【待完成#3】优化算法

本文摘自刘铁岩等《分布式机器学习》的第4章和第5章。
[toc]

1. 确定性算法——一阶

1.1 梯度下降法

由Cauchy在1847年提出。基本思想是：最小化目标函数在当前状态的一阶泰勒展开，从而近似地优化目标函数本身。
$\underset{w}{\min}f\left( w \right) \approx \underset{w}{\min}f\left( w_t \right) +\nabla f\left( w_t \right) ^{\top}\left( w-w_t \right) \\$
更新规则如下：
$w_{t+1}=w_t - \eta \nabla f(w_t) \\$
其中 $\eta > 0$ 是步长，也常被称为学习率。

Initialize: $w_0$
Iterate: for $t=0, 1, \cdots, T-1$
1. 计算梯度 $\nabla f(w_t)$
2. 更新参数 $w_{t+1}=w_t - \eta \nabla f(w_t)$
end

当目标函数是强凸函数时，梯度下降法的收敛速率是线性的；当目标函数是凸函数时，其收敛速率是次线性的。

1.1.1 投影次梯度下降法

梯度下降法有两个局限：①只适用于无约束优化问题；②只适用于梯度存在的目标函数。
投影次梯度下降法可以解决这两个局限性。迭代公式如下：
$\begin{align} v_{t+1} &= v_t - \eta g_t\,\,,\,\, g_t \in \partial f(w_t)\\ w_{t+1} &= \prod_{\mathcal{W}}{w_{t+1}}\,\,,\,\,\prod_{\mathcal{W}}{x}=\arg \underset{v \in \mathcal{W}}{\min}\lVert x-v \rVert \end{align} \\$
其中， $\partial f(w_t)$ 为状态 $w_t$ 处目标函数的次梯度所构成的集合， $\prod_{\mathcal{W}}{w}$ 为变量 $w$ 到约束域 $\mathcal{W}$ 的投影。

Initialize: $w_0$ ，凸集合 $\mathcal{W}$
Iterate: for $t=0, 1, \cdots, T-1$
1. 随机选取一个次梯度 $g_t \in \partial f(w_t)$
2. 更新参数 $v_{t+1} = v_t - \eta g_t$
3. 将参数投影回集合 $\mathcal{W}$ ： $w_{t+1} = \prod_{\mathcal{W}}{w_{t+1}}$
end

对于光滑函数，在凸和强凸两种情形下，收敛速率与梯度下降法相同。

近端梯度下降法
是投影次梯度下降法的一种推广，适用于不可微的凸目标函数的优化问题。（个人理解是求解一个可微凸函数，再投影回原空间）
Frank-Wolfe算法
是投影次梯度下降法的另一个替代算法。如果投影的计算很复杂，投影次梯度下降的效率将会成为瓶颈。该算法可解决这个问题。

1.1.2 Nesterov加速法

Nesterov在1983年对光滑的目标函数提出了一种加快一阶优化算法收敛的方法。
在任意时刻 $t$ ，对当前状态 $w_t$ 计算梯度方，按照一定步长计算辅助变量 $v_{t+1}$ 。然后将新计算的辅助变量和上一时刻计算的辅助变量做线性加权，作为时刻 $t+1$ 的状态 $w_{t+1}$ 。更新规则如下：
$\begin{align} v_{t+1} &= w_t - \eta_t \nabla f(w_t) \\ w_{t+1} &= (1+\gamma_t)v_{t+1}-\gamma_t v_t \end{align} \\$

Initialize: $w_0$
Iterate: for $t=0, 1, \cdots, T-1$
1. 计算梯度 $\nabla f(w_t)$
2. 更新变量 $v_{t+1} = w_t - \eta_t \nabla f(w_t)$
3. 做加权： $w_{t+1} = (1+\gamma_t)v_{t+1}-\gamma_t v_t$
end

1.2 坐标下降法

其基本思想是，在迭代的每一步，算法选择一个维度，并更新这一维度，其他维度的参数保持不变，或者将维度分为多个快，每次只更新某块中的维度，其他维度保持不变。更新公式如下：
$w_{t+1,j} = \arg \min_{z \in \mathcal{W_j}}f(w_{t,1}, \cdots,w_{t,j-1},z,w_{t,j+1},\cdots,w_{t,d}) \\$
其中， $\mathcal{W_j}$ 为第 $j$ 个维度块的约束域。

Initialize: $w_0$
Iterate: for $t=0, 1, \cdots, T-1$
1. 令 $s=t\,\text{mod}\,d$
2. 更新参数 $w_{t+1,s} = w_{t,s} - \eta \cfrac{\partial f(w_t)}{\partial w_{t,s}}$
$w_{t+1,j} = w_{t,j}, j \ne s$
end

对强凸并且光滑的目标函数，循环坐标下降法具有线性的收敛速率。

2. 确定性算法——二阶

2.1 牛顿法

基本思想是将目标函数在当前状态进行二阶泰勒展开，然后最小化这个近似目标函数，即
$\min_{w \in \mathcal{W}}f(w) \approx \min_{w \in \mathcal{W}}f(w_t) + \nabla f(w_t)^{\top}(w-w_t) + \cfrac{1}{2}(w-w_t)^{\top} \nabla^{2}f(w+t)(w-w_t) \\$
更新公式如下：
$w_{t+1} = w_t - [\nabla^2f(w_t)]^{-1}\nabla f(w_t) \\$

Initialize: $w_0$
Iterate: for $t=0, 1, \cdots, T-1$
1. 计算梯度 $\nabla f(w_t)$
2. 计算海森矩阵 $\nabla^2f(w_t)$ ，并求逆矩阵 $[\nabla^2f(w_t)]^{-1}$
3. 更新参数 $w_{t+1} = w_t - [\nabla^2f(w_t)]^{-1}\nabla f(w_t)$
end

具有二次收敛速率。

2.2 拟牛顿法

解决牛顿法的两个问题：①海森矩阵计算量和存储代价大；②海森矩阵不一定是正定的。
主要思想是构造一个与海森矩阵相差不太远的正定矩阵作为其替代品。
记 $B_t=\nabla^2f(w_t)$ ， $H=[\nabla^2f(w_t)]^{-1}$ 。在时刻 $t+1$ ，对 $t$ 时刻的海森矩阵 $B_t$ 加一个或者两个秩为1的矩阵作为对 $t+1$ 时刻海森矩阵 $B_{t+1}$ 的估计，例如：
$B_{t+1} \approx B_t+aa^{\top}+bb^{\top} \\$
海森矩阵的更新需要满足一定的条件（拟牛顿条件）。
对一阶泰勒展开的左右两边计算梯度，
$\begin{align} f(w) &\approx f(w_t) + \nabla f(w_t)(w-w_t) \\ \nabla f(w) &\approx \nabla f(w_t) + B_t(w-w_t) \end{align} \\$
所以
$\delta_t^{'} \approx B_t \delta_t \\$
其中， $\delta_t^{'}=\nabla f(w_{t+1})-\nabla f(w_t)$ 为目标函数导数的更新量， $\delta_t=f(w_{t+1})-f(w_t)$ 为模型的更新量。
在拟牛顿条件下，更新规则为：
$\begin{align} B_0 &= I \\ B_t+1 &= B_t + \cfrac{\delta_t^{'} (\delta_t^{'})^{\top}}{(\delta_t^{'})^{\top} \delta_t^{'}} - \cfrac{B\delta_t (B\delta_t)^{\top}}{(\delta_t)^{\top} B\delta_t} \\ H_{t+1} &= \left(I - \cfrac{\delta_t (\delta_t^{'})^{\top}}{(\delta_t^{'})^{\top} \delta_t}\right)H_t \left(I - \cfrac{\delta_t^{'} (\delta_t)^{\top}}{(\delta_t^{'})^{\top} \delta_t}\right) + \cfrac{\delta_t (\delta_t)^{\top}}{(\delta_t^{'})^{\top} \delta_t} \end{align} \\$

Initialize: $w_0$ ， $B_0 = I$
1. $\nabla f(w_0)$
2. $H_0 = \nabla^2 f(w_0)^{-1}$

Iterate: for $t=0, 1, \cdots, T-1$
3. 计算 $w_{t+1} = w_t - \eta H_t \nabla f(w_t)$
4. 计算导数和模型的更新量： $\delta_t^{'}=\nabla f(w_{t+1})-\nabla f(w_t)$ ， $\delta_t=f(w_{t+1})-f(w_t)$
5. 利用更新量 $\delta_t^{'}$ 和 $\delta_t$ ，多次迭代更新海森矩阵和海森逆矩阵：
$\begin{align} B_t+1 &= B_t + \cfrac{\delta_t^{'} (\delta_t^{'})^{\top}}{(\delta_t^{'})^{\top} \delta_t^{'}} - \cfrac{B\delta_t (B\delta_t)^{\top}}{(\delta_t)^{\top} B\delta_t} \\ H_{t+1} &= \left(I - \cfrac{\delta_t (\delta_t^{'})^{\top}}{(\delta_t^{'})^{\top} \delta_t}\right)H_t \left(I - \cfrac{\delta_t^{'} (\delta_t)^{\top}}{(\delta_t^{'})^{\top} \delta_t}\right) + \cfrac{\delta_t (\delta_t)^{\top}}{(\delta_t^{'})^{\top} \delta_t} \end{align} \\$
end

还有DFP、Broyden、SR1等算法，当初始点离最优点足够近时，拟牛顿法和牛顿法同样具有二次收敛速率。

3. 确定性算法——对偶方法

前面各种优化算法都是直接求解原始优化问题。某些时候，把原始优化问题转化成对偶优化问题，会更容易求解。比如，当原始问题的变量维度很高，但是约束条件个数不太多时，对偶问题的复杂度（对偶变量的维度对应于约束条件的个数）会远小于原始问题的复杂度，因而更容易求解（这也是支持向量机方法高效的主要原因）。
如果一个优化问题需要通过求解其对偶问题来解决，我们可以首先推导出他所对应的对偶问题，并用各种一阶或者二阶方法来最大化对偶目标函数。

4. 随机算法——一阶

4.1 随机梯度下降法

SGD对训练数据做随机采样，其更新公式如下：
$w_{t+1} = w_t - \eta_t \nabla f_{i_t}(w_t) \\$
其中， $i_t$ 是第 $t$ 轮随机采样的数据标号， $f_{i_t} = l(w_t;x_{i_t},y_{i_t}) + R(w_t)$ 是模型 $w_i$ 关于第 $i_t$ 个训练数据的（正则化）损失函数取值。

Initialize: $w_0$
Iterate: for $t=0, 1, \cdots, T-1$
1. 随机选取一个样本 $i_t \in \left\{1, \cdots ,n \right\}$
2. 计算梯度 $\nabla f_{i_t}(w_t)$
3. 更新参数 $w_{t+1} = w_t - \eta_t \nabla f_{i_t}(w_t)$
end

收敛速率慢于梯度下降法，但当样本量很大时，计算复杂度低。

4.1.1 小批量随机梯度下降法

随机梯度下降法的一个推广是小批量（mini-batch）随机梯度下降法，该方法每次迭代时随机抽取多个样本来计算梯度。

Initialize: $w_0$
Iterate: for $t=0, 1, \cdots, T-1$
1. 随机选取一个小批量样本集合 $S_t \subset \left\{1, \cdots ,n \right\}$
2. 计算梯度 $\nabla f_{S_t}(w_t) = \cfrac{1}{|S_t|} \sum_{i \in S_t}\nabla f_{i}(w_t)$
3. 更新参数 $w_{t+1} = w_t - \eta_t \nabla f_{S_t}(w_t)$
end

4.2 随机坐标下降法

除了对样本进行随机采样外，还可以对模型的维度进行采样。其更新公式如下：
$w_{t+1,j_t} = w_{t,j_t} - \eta_t \nabla_{j_t} f(w_t) \\$
其中， $j_t$ 表示第 $t$ 次迭代中随机抽取的维度标号， $\nabla_{j_t} f(w_t)$ 是损失函数对于模型 $w_t$ 中的第 $j_t$ 个维度的偏导数。

Initialize: $w_0$
Iterate: for $t=0, 1, \cdots, T-1$
1. 随机选取一个维度 $j_t \in \left\{1, \cdots ,d \right\}$
2. 计算梯度 $\nabla_{j_t} f(w_t)$
3. 更新参数 $w_{t+1,j_t} = w_{t,j_t} - \eta_t \nabla_{j_t} f(w_t)$
end

收敛速率与梯度下降法相同。

4.2.1 随机快坐标下降法

随机坐标下降法的一个推广是随机快坐标下降法，也就是将参数维度分为几块，算法每次随机选取其中的一块，更新这一块中的所有维度。

Initialize: $w_0$
将 $d$ 个维度均等切分为 $J$ 块

Iterate: for $t=0, 1, \cdots, T-1$
1. 随机选取一块 $J_t \in \left\{1, \cdots ,d \right\}$
2. 计算梯度 $\nabla_{J_t} f(w_t)$
3. 更新参数 $w_{t+1,j_t} = w_{t,j_t} - \eta_t \nabla_{J_t} f(w_t),\,\,j \in J_t$
end

5. 随机算法——二阶

4.1 随机拟牛顿法

6. 随机算法——随机对偶坐标上升法

7. 随机算法——算法改进

7.1 方差缩减

7.2 算法组合

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 195,783评论 5赞 462
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 82,360评论 2赞 373
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 142,942评论 0赞 325
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 52,507评论 1赞 267
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 61,324评论 5赞 358
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 46,299评论 1赞 273
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 36,685评论 3赞 386
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 35,358评论 0赞 254
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 39,652评论 1赞 293
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 34,704评论 2赞 312
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 36,465评论 1赞 326
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,318评论 3赞 313
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 37,711评论 3赞 299
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 28,991评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,265评论 1赞 251
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 41,661评论 2赞 342
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 40,864评论 2赞 335