hulu机器学习问题与解答系列|十六：经典优化算法

Happy New Year! 

新年伊始，我们都会在祝福他人之余，为自己暗暗定下几个小目标。那就从现在开始努力吧，跑得更快一点，才会让时间显得慢一些~

今天的内容是

【经典优化算法】

场景描述

针对我们遇到的各类优化问题，研究者们提出了多种有各自适用场景的求解算法，并逐渐发展出了有严格理论支撑的研究领域——凸优化[1]。在这众多的算法中，有几种经典的优化算法是值得被牢记的，了解它们的适用场景有助于我们在面对新的优化问题时有求解思路。

问题描述

有一道无约束优化问题摆在你面前

其中目标函数 L(·) 是光滑的。请问求解该问题的优化算法有哪些？它们的适用场景是什么？

先验知识：微积分、线性代数、凸优化基本概念

解答与分析

经典的优化算法可以分为两大类：直接法和迭代法。

直接法，顾名思义，就是能够直接给出优化问题最优解的方法。这个方法听起来非常厉害的样子，但它不是万能的。直接法要求目标函数满足两个条件。第一个条件是，L(·)是凸函数。什么是凸函数呢？它的严格定义可以参见文献[1]的第3章：对任意x和y，任意0≤λ≤1，都成立

一个直观的解释是，任取函数曲面上的两点连接成线段，该线段的任意一点都不会处于函数曲面的下方，示意图如下

任取函数曲面上的两点连接成线段，

该线段的任意一点都不会处于函数曲面的下方

若 L(·) 是凸函数，则文献[1]第140页的一个结论是，θ^*是优化问题最优解的充分必要条件是 L(·) 在θ^*处的梯度为0，即

因此，为了能够直接求解出θ^*，第二个条件是，上式有闭式解。同时满足这两个条件的经典例子是岭回归（ridge regression），其中目标函数为

稍加推导就能得到最优解为（要试着自己推导哟）

直接法的这两个要求限制了它的广泛应用，因此在很多实际问题中，我们会采用迭代法。这类方法迭代地修正对最优解的估计，即假设当前的估计为θ_t，我们希望求解优化问题

从而得到更好的估计θ_t+1＝θ_t﹢δ_t。迭代法又可以分为两类，一阶法和二阶法。

一阶法对函数 L(θ_t﹢δ) 做一阶泰勒展开，得到近似式

由于该近似式仅在δ较小时才比较准确，我们可以求解带l₂正则的近似优化问题

因此一阶法的迭代更新公式是

一阶法也称为梯度下减法，梯度是目标函数的一阶信息。

二阶法对函数 L(θ_t﹢δ) 做二阶泰勒展开，得到近似式

其中

是函数 L(·) 在θ_t处的Hessian矩阵。我们可以求解近似优化问题

从而得到二阶法的迭代更新公式

二阶法也称为牛顿法，Hessian矩阵是目标函数的二阶信息。二阶法的收敛速度一般要远快于一阶法，但是在高维情况下Hessian矩阵求逆的计算复杂度更大，而且当目标函数非凸时，二阶法有可能会收敛到鞍点（saddle point）。

扩展阅读

      俄罗斯著名数学家Yurii Nesterov于1983年提出了对一阶法的加速算法[2]，该算法的收敛速率能够达到一阶法收敛速率的理论界。针对二阶法矩阵求逆的计算复杂度过高的问题，Charles George Broyden，Roger Fletcher，Donald Goldfarb和David Shanno四人于1970年分别独立提出了后来被称为BFGS的伪牛顿算法[3-6]，1989年扩展为低存储的L-BFGS算法[7]。

Charles George Broyden，Roger Fletcher，Donald Goldfarb和David Shanno的合影

参考文献：

[1] Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[2] Nesterov, Yurii. "A method of solving a convex programming problem with convergence rate O (1/k2)." Soviet Mathematics Doklady. Vol. 27. No. 2. 1983.

[3] Broyden, Charles G. "The convergence of a class of double-rank minimization algorithms: 2. The new algorithm." IMA journal of applied mathematics 6.3 (1970): 222-231.

[4] Fletcher, Roger. "A new approach to variable metric algorithms." The computer journal 13.3 (1970): 317-322.

[5] Goldfarb, Donald. "A family of variable-metric methods derived by variational means." Mathematics of computation 24.109 (1970): 23-26.

[6] Shanno, David F. "Conditioning of quasi-Newton methods for function minimization." Mathematics of computation 24.111 (1970): 647-656.

[7] Liu, Dong C., and Jorge Nocedal. "On the limited memory BFGS method for large scale optimization." Mathematical programming 45.1 (1989): 503-528.

下一题预告

【随机梯度下降算法之经典变种】

场景描述

提到Deep Learning中的优化方法，人们都会想到Stochastic Gradient Descent (SGD)，但是SGD并不是理想的万金油，反而有时会成为一个坑。当你设计出一个deep neural network时，如果只知道用SGD来训练，不少情况下你得到一个很差的训练结果，于是你放弃继续在这个深度模型上投入精力。但可能的原因是，SGD在优化过程中失效了，导致你丧失了一次新发现的机会。

问题描述

Deep Learning中最常用的优化方法是SGD，但是SGD有时候会失效，无法给出满意的训练结果，这是为什么？为了改进SGD，研究者都做了哪些改动，提出了哪些SGD变种，它们各有哪些特点？