机器学习中的优化方法小结

前几天听了林宙辰老师的一个报告，讲的是机器学习中的优化方法[1]，做个笔记。推荐机器学习的人去听听。林老师的主页：https://zhouchenlin.github.io/zhouchenlin.github.io

机器学习是离不开优化方法的，Pedro Domingos这样概括机器学习和优化方法的关系：

“Machine learning=Representation+Optimization+Evaluation”

后面三项对应于三步：建立模型，求解模型，验证模型。

首先介绍一下机器学习中常见的优化问题：

1.分类回归问题

很多的分类回归问题都可以写成问题（1）的一个特例，比如SVM，正则的logistic回归，多层感知器，线性回归，岭回归，Lasso问题等。

2.AdaBoost

通常数据的分类面可能是很复杂的，我们可以通过多个简单的线性分类器组合而成。

3.生成对抗网络

4.AutoML

自动超参数的选取，这是一个双层优化问题。

根据所需要的信息，算法大概分为三种：零阶、一阶、二阶。

机器学习中，一阶用的是最广泛的。当然也不排除有零阶和二阶的，这适用于那些具有特殊结构的问题。

1.基本模块：

通常的优化算法主要有以下几个模块，将这些模块以不同的方式组合一下就得到了不同的优化方法。

假设函数 是光滑的（如果不光滑，我们可以用次梯度，光滑化等）

• 梯度下降 
   
• 共轭梯度

当目标函数是二次的时候，选出来的方向 是共轭方向。

• 拟牛顿

是 处Hessian矩阵逆的近似，需要满足 ,主要有两类近似：秩1和秩2近似。

• L-BFGS

上面说到的逆牛顿需要存储一个大的矩阵 ,考虑到他是秩1或秩2近似，因此我们可以通过存储一些向量来代替。

• 临近梯度算法

考虑可分问题：

其中 光滑， 为非光滑。临近梯度算法对光滑的那部分做二次近似，每一步求解如下问题：

该算法需要假设对于g的proximal operator是容易计算的。

3.机器学习中的约束优化方法

考虑一般问题：

其中 是一个约束集合。

• 投影梯度方法

首先走一个梯度步，然后投影回去。

• 罚方法

通过罚参数将约束集放到目标函数上，其中 要满足一些条件：连续非负，以及 当且仅当 。该方法依赖于罚参数。

• 条件梯度

其中需要 是一个紧集（欧氏空间下等价于有界闭集）。方向 的求解相当于对函数 做泰勒一次展开。这个算法适用于稀疏低秩问题，这时候 可能是一个低秩范数球，这时候关于 的求解有很高效的算法。

• ADMM

当约束是线性约束并且可分的时，可以采用ADMM，考虑问题：

对应的增广拉格朗日函数为：

ADMM算法交替的去更新增广拉格朗日函数中的三个变量：

如果对于 还是不好求，我们可以对后面的二次项做线性化，得到线性化的ADMM。

• 坐标下降方法

如果问题中的变量可以分为多块，比如：

这种情况下可以采取块坐标下降方法：本质上是交替极小的一个扩展。

4.大数据的处理

考虑如下形式的问题：

• 随机梯度

找到一个近似的方向 近似梯度，只要满足 即可。有很多的变种，adam，adagrad，adadelta，ada...

通常情况下的加速策略都是利用内插和外推。

1.确定

• Heavy ball

后面那一项称为Momentum。

• Nesterov

• 加速临近梯度

将Nesterov加速应用到了非光滑的可分问题（2）上：

2.随机

考虑问题：

我们可以用梯度方法： , 如果n太大，每一步的计算量太大。

接着我们采用最初的随机梯度方法： ，也就是一次选一个去走。

这两个方法似乎都是一种极端，所以中间存在一种tradeoff。思考如何做到在降低variance的情况下计算量不要增长的太快。

• SVRG

这个方法的思想就是，每隔一段时间算一次完整梯度，用这个信息去矫正每一步的随机梯度方向。

• Katyusha

这个方法是Nesterov加速和variance reduction的结合。（这个名字取得真是让人摸不着头脑，包括下面的Catalyst，还有一个方法SARAH）

• Catalyst

注意到第三步，你可以使用任何一个可以计算的方法去求解第三步中的问题

• SPIDER

这个相对于SVRG方差更小。

大规模优化的展望主要有这几点：

• 随机化
• 分布式
• 异步
• learning based
• Quantum