Mirror descent：统一框架下的一阶算法

『运筹OR帷幄』原创

『运筹OR帷幄』专栏发布

作者：覃含章

作者: @覃含章 美国麻省理工学院（MIT）计算科学与工程方向博士在读，清华大学工业工程及数学与应用数学（第二学位）本科。研究兴趣主要为优化理论，机器学习算法在运营管理中的应用。

『运筹OR帷幄』责任编辑： @文雨之（东北大学系统工程博士生）

本文首发于知乎专栏【Optimizers' Garden】：http://t.cn/Rnb7cE8

敬请关注和扩散本公众号及知乎同名专栏，会邀请全球知名学者陆续发布运筹学、人工智能中优化理论等相关干货、知乎Live及行业动态：

『运筹OR帷幄』大数据人工智能时代的运筹学--知乎专栏：http://t.cn/RlNoO3P『运筹OR帷幄』专栏有奖征稿专帖

一、序言：Mirror descent方法概述

Mirror descent方法第一次引起人们的广泛注意是在20年前，Aharon Ben-Tal，Tamar Margalit和Arkadi Nemirovski三人在[1]中引用了该方法，解决了在一个几百万维的单纯形（unit simplex）上

的凸优化问题，并应用在了 positron emission tomography （PET）相关的三维医学图像重构问题：一个最大似然问题（Maximum Likelihood Estimate）。

他们的成功之处便是拓展了其实是在欧式距离上定义的投影梯度下降算法（projected gradient descent method），利用了一种更general的迫近点梯度下降算法（proximal gradient descent method）的观点，也就是重新定义了这种gradient descent算法中的“距离”。具体来说，在上述问题中，即所谓的simplex setup，如果选取的“距离”为entropy function（熵函数），这类proximal algorithm在做prox step的时候（也就是投影，projection）在simplex上基本上是免费的。因此，他们成功给出了如上所述的一个大规模凸优化的算法解决方案。

因此，从这个意义上我们知道proximal algorithm是一种比传统的gradient descent方法更广泛（适用于任何合理的"非欧式（non Euclidean）"距离）的观点，本文我们主要就探究这一点。当然，对于mirror descent算法还可以有很多其它的理解方式，如Zeyuan Allen-Zhu和学Lorenzo Orecchia[2]的研究观点：gradient descent算法可以看作从primal space出发的某种upper bounding，mirror descent算法可以看作从primal-dual space出发的某种lower bounding。我之后会在个人专栏进行讨论。

本文主要的参考资料是Ben-Tal和Nemirovski的讲义[3]的第五章，和本校Prof. Robert Freund的“地下讲义”。

二、问题描述

我们本文考虑的general问题为：

其中，是我们的目标函数，它可以被分解为两个函数之和：是凸（convex）且光滑（比如Lipschitz连续）的，是convex但可以不光滑，不过至少有一些方便计算的性质。另外，是有限维的向量空间。

具体的例子比如说Lasso Regression，，，，我们知道是处处可导的，而虽然不可导但是也是很容易处理的。或者也可以表达任意的凸集约束，即取且。当然这个时候我们希望凸集的结构不太复杂（比如ball，box或unit simplex）。

三、预备知识

一些必要的预备知识。

首先是范数（norm）。我们用表示向量空间上的范数，那么我们在对偶空间所取的一点的范数定义是：，这也是的对偶范数。

容易验证我们有“范数的对偶的对偶是它自己”。 且我们指出以下两条性质：

(Hölder's inequality)

给定一个strongly convex的函数我们定义Bregman divergence function为。

我们指出，便是mirror descent algorithm更general的关键，即是用来刻画各种非欧距离的要素。在proximal algorithm的框架里，它也被称作prox(imal) function/prox(imal) term等等，因为它便是用来衡量两个点的接近（proximity）程度的。有很多性质，如它也是strongly convex的（given），它不对称，等等，更深层次的探讨可以见我之前的一个知乎回答[4]。

本节最后，我们指出mirror descent算法分析里需要用的一个核心引理（“三点”性质），它最早由Paul Tseng[5]发现：

引理1（Three-Point Property）：对任意凸函数和Bregman function，对给定一点定义，则我们有

熟悉projected gradient算法分析的同学可能已经注意到了，其实相当于做了一步projection（实际上，在mirror descent的分析里这一步叫做prox(imal) step）。而这个性质即表明了任给两点，将看成算法迭代1次之后的结果，他们所导致的目标函数上的差可以用三个点之间的距离lower bound住，这也是保证mirror descent算法能收敛的关键，我们可以由此导出mirror descent每一步都在降低的值。这个引理的证明只需要利用convexity和的性质，留作练习。

四、光滑情形下的算法复杂度分析

本节我们假设可微，且导数Lipschitz连续：，并证明mirror descent的收敛速度定理。那么我们General 的prox gradient algorithm可以表示如下：即给定初始值，

注意到上式其实有很多对min来说的常数项（只是为了分析方便），等价于

本节我们证明收敛性定理：

定理1（光滑mirror descent收敛速度）：.

显然，在以上定理的基础上，如果我们考虑，即“半径”为的范围内，令最优解就有也就是说，为了达到的绝对误差，我们需要步。

我们的证明还需要一个额外的引理，对导数L-Lipshitz连续的函数我们有如下的二次函数上界：

引理2：

证明基于微积分基本定理，留作练习。

现在我们就有了足够的预备知识，可以证明本节主要定理了（非常短）！具体来说，我们进行如下推导：

也就是说我们得到了，即算法每步的效果大概是。如果我们在这个式子中取则得到，即mirror descent每步确实递减了，再对这个式子两边对t求和，经过裂项相消就能得到定理1。

思考题1：对比gradient descent的收敛性分析，你发现有什么相似的地方么，对应的区别在哪里？（提示：考虑gradient descent中的）以及，如果我们取我们的算法会是怎么样的？（提示：gradient descent?!）

思考题2：L不知道的情况如何继续用这个算法，这里我们假设理论分析也找不到一个合适的L的上界。（提示：利用引理2，然后考虑线搜索方法）

五、非光滑情形下的算法复杂性分析

本节我们讨论前一节mirror descent算法的variant：不再可微（即问题nonsmooth）的情况（当然，仍然是convex的），我们引入次梯度（subgradient）的记号，即当且仅当然后我们假设Lipschitz连续：

这个时候，我们的prox subgradient算法如下：给定初始值我们需要定义一列步长（stepsizes），并每步进行如下迭代：

其中，也就是说我们利用次梯度代替梯度来进行迭代。另外，我们的步长选取也和光滑情况不太一样。

我们指出，subgradient method不能保证算法每步一定能减小的值！收敛速度定理如下。

定理2（非光滑mirror descent收敛速度）：也就是说，如果我们同样考虑，且，那么为了达到绝对误差我们如果选取,我们需要至少步，和定理1一比较我们就知道subgradient method确实是比graident method（即光滑情况下）要慢了1个次方的。当然，这是为了估计步数，我们指出一般来说一个更合理的步长选择应该是

思考题3：在的情况下化简定理2。

思考题4：证明定理2。（提示：利用下面两个引理，考虑的一个下界，其中，即和的一阶线性近似的差的下界）

引理3：

引理4：

六、光滑情形下加速算法的复杂性分析

本节我们考虑如何对光滑情况下的mirror descent进行加速。注意，不光滑情况的subgradient method一般来说没有加速的办法。我们的给出accelerated prox subgradient算法如下：给定初始值我们需要定义一列步长（stepsizes）并每步进行如下迭代：

定义

这种Nesterov式的加速方法，其几何意义是不容易理解的，我这里不多做赘述。我们指出，一种常用的步长为：

可以想象的是，加速方法的证明比前两节会更复杂一些（虽然说如果你理解的足够好，完整的proof篇幅也是不长的），我们这里就步介绍了，只介绍主要结果（假设步长已经如上选取好了）。

定理3（光滑情况下加速算法的收敛速度）：

也就是说，同样考虑，我们知道绝对误差 达到的步数是，比smooth情况下naive的mirror descent又快了1个次方！也就是说，实际上在光滑情况下你永远应该考虑使用加速版本（除非你要用coordinate descent，没有对应的加速方法，不过本文我们不讨论这点了）

思考题5：思考加速算法的几何意义。这点其实历史上已经有很多著名的讨论了。

思考题6：证明定理3。（其实你仍然只需要利用Bregman function和convex function的性质，引理1，引理2，但需要你有更好的理解：)）

七、在单纯形上的应用

本节我们讨论mirror descent算法的一个实际应用：在unit simplex上的凸优化问题，也就是让题头那篇paper名声大噪的原因。此时，我们的可以是任意可微凸函数，不过本节为了讨论方便起见我们认为它是光滑可微的。也就是说，我们本节考虑是的indicator function，即在的时候取值0，不然取值且我们考虑所谓的simplex/entropy setup，让我们的Bregman function由entropy function组成：

也就是说，prox step实际上就是要计算我们指出，这一步实际上是很快的，即有closed form如下：

思考题7：证明上述迭代公式成立。（提示：entropy的引入很关键，strongly convex的unit simplex约束优化问题）

也就是说，这一步实际上相当于只是作normalization！而且实际上，由于都是exponents，实际update的时候可能只需要update很少的一部分component（这里涉及到numerical details，略过），另外，这一步也可以再被并行化！

于是，我们看到了mirror descent的一个具体应用，当然，为了更好的理解其优势我们需要作如下的思考。

思考题8：考虑对同样问题的projected gradient descent的算法复杂度。（提示：主要比较projection的复杂度）

思考题9：给出对同样问题的accelerated mirror descent算法。

八、拓展：在线学习中的应用

本文的最后，我们指出first order methods在online learning中的自然应用，比如我们的问题改变定义，即我们在每个时间 t 都有一个adversary选择一个并report它在的(sub)gradient给我们。那么显然我们的算法可以直接用来进行"learning"，我们的regret是（注意这里我们假设了目标是固定的），即我们的算法可以某种程度上minimize这个regret。

当然，更有意思的地方在于比如是IID（独立同分布）地从一个分布中被选取，mirror descent仍然能保证的regret。对mirror descent和相关online learning的应用有兴趣的同学可以进一步参阅参考文献[3][6][7]。

参考文献

[1] Ben-Tal, Aharon, Tamar Margalit, and Arkadi Nemirovski. "The ordered subsets mirror descent optimization method with applications to tomography."SIAM Journal on Optimization12.1 (2001): 79-108.

[2] Allen-Zhu, Zeyuan, and Lorenzo Orecchia. "Linear coupling: An ultimate unification of gradient and mirror descent."arXiv preprint arXiv:1407.1537(2014).

[3] Aharon Ben-Tal, and Arkadi Nemirovski. "Lectures on Modern Convex Optimization".https://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf

[4] 覃含章. "如何理解Bregman Divergence?"http://t.cn/RnG9Dsc

[5] Tseng, Paul. "Approximation accuracy, gradient methods, and error bound for structured convex optimization." Mathematical Programming 125.2 (2010): 263-295.

[6] Beck, Amir, and Marc Teboulle. "Mirror descent and nonlinear projected subgradientmethods for convex optimization."Operations Research Letters31.3 (2003): 167-175.

[7] Bubeck, Sébastien. "Introduction to online optimization."Lecture Notes(2011): 1-86.

转载请联系本公众号获得授权

如果你是运筹学/人工智能硕博或在读，请在本公众号后台留言：“加微信群”系统会自动辨认你的关键字，并提示您进一步的加群要求和步骤。

如果你是运筹学/人工智能/数据科学爱好者，请扫下图二维码加入qq群。