你好,游客 登录
背景:
阅读新闻

Fenchel-Lengendre Duality观点下的优化算法们

[日期:2018-03-07] 来源:推酷  作者: [字体: ]

Fenchel-Lengendre Duality观点下的优化算法们(I):前言

覃含章

2 天前

前两天 @Zeyuan AllenZhu大神到本组visit,与之交流一番后感慨泽园确实是在思想的深度上已经站在(非)凸优化算法理论领域的极前沿的。在他的眼里,繁杂多样的deterministic/stochastic (accelerated) first/second order methods早就已经化繁为简,其中虽有各种细微的差别然而大体不出乎primal,primal-dual和dual的三种观点出发而来。且其对各种方法间细微差别的来源理解已是极为深刻,短短的交流让我实在也是收益良多,感觉把很多之前觉得不相关的知识结构终于慢慢联系在了一起。

因此,基于我本人先前的知识积累和最近的一些归纳总结,我希望将泽园脑海里渐渐统一的框架也在一系列的文章里分享给大家。另外,我可能也会想自己写一些最近在优化理论、在线学习等相关领域的阅读思考所得,所以不见得发文顺序会是线性的(比如下一篇会集中讨论mirror descent以及variants),请大家多包涵。

本文主要是提纲挈领,将泽园的primal,primal-dual,dual的三种观点和与具体算法之间的联系大概指出。本系列主要参考的是泽园在ICML 2017的tutorial talk(下为youtube连接,国内观看需翻墙)。

https://www.youtube.com/watch?v=jPjhiaeYruQ&feature=youtu.bewww.youtube.com


本节定义预备知识:Fenchel-Legendre Duality.

给定一个

上良好的凸函数(proper convex function,可以简单认为该凸函数在有效定义域上不会达到负无穷)

,它的Fenchel dual定义为:

在这种条件下,我们拥有强对偶定理成立:即一个函数的对偶的对偶还是它自己。

还有其它值得注意的性质:

  1. 也是(proper)convex的。

  2. L-smooth等价于

    1/L strongly convex。

  3. m-strongly-convex等价于

    1/m-smooth。

其中假设函数足够光滑,f(x)是L-smooth的定义为:

,而f(x)是m-strongly-convex的定义为:

。可以统一用Hessian矩阵来刻画。


三种观点:primal,dual,primal-dual。原问题,对偶问题,原+对偶问题,分别对应针对原变量

,针对原变量

和对偶变量

和针对对偶变量

的优化问题。

  • Primal:

  • Primal-dual:

(从Primal的表达式中代入

)

  • Dual:

(从Primal-dual的表达式中代入

)

原问题自然是一般我们最熟悉的形式,目标函数由一个convex的loss function(常可以分解为data point数量个的损失函数

之和)加上一个同样是convex的regularizer

。比如SVM,Lasso,Ridge, Logistic Regression都是以这种形式最为常见在我们的视野当中。

至于问题的复杂度,我们可以用

是否是m-strongly-convex(

是否1/m-smooth)和

是否是L-smooth(

是否是1/L-strongly-convex)来刻画。也就是说,每种形式都可以分为四类:

  1. strongly-convex且smooth。

  2. strongly-convex但不smooth。

  3. 不strongly-convex但smooth。

  4. 不strongly-convex也不smooth。

用以上标准我们很容易知道,Ridge Regression属于第1类,L2-SVM属于第2类(L1-SVM就是第4类了),Lasso和Logistic Regression属于第3类。所以到这里我们其实就有一个很自然的想法,像第2类问题,因为在原问题space上不光滑然而到对偶空间却是光滑的,因此对偶算法会天然有优势(这也解释了L2-SVM的主流算法是对偶算法,因为在原空间上的话需要额外再人工添加regularizer)。第3类问题则反之。


同样的,我们在三种形式下可以得到某种程度意义上等价的同一类算法的三种形式,并且自然预计这三种形式应该拥有相同的算法复杂度。事实也是如此,比如我们Primal问题上最经典的gradient descent算法:

显然有Dual的版本

。而这种用gradient的反方向来update变量的最速下降法在primal-dual的观点上自然则会导出同时update变量

的mirror descent。泽园在他的talk里用Ridge Regression做例子表明了这三种形式确实具有同样的复杂度。

同样 ,我们也有三种对应的加速(accelerated)算法,primal和dual对应的accelerated gradient descent和primal-dual对应的mirror-prox/momentum算法,它们同样具有一致的复杂度(虽然形式上区别非常巨大)。


以此类推,我们当然对随机算法也可以推导出具有一致复杂度的三种形式的算法。这也是泽园tutorial最主要的内容。但是,作为我这个系列的内容来说,我还是希望先继续深入讨论确定性first-order methods的具体性质。因此,我打算稍稍放慢脚步,暂缓介绍随机性算法的故事:下篇文章,我将着重讨论拥有同一个名字,但在不同人笔下其实指的不是同一个东西的mirror descent算法。它的主流版本算法的性质,和gradient descent算法的关系,以及它的加速版本mirror prox/momentum算法的思路,以及mirror descent在在线学习(online learning)中的自然应用,也会指出一些关键性的推导步骤。

如果你对这个系列的内容比较期待,欢迎关注我,并催促我进行更新。那样的话,我应该会更有动力更新之后的内容O(∩_∩)O

收藏 推荐 打印 | 录入:Cstor | 阅读:
相关新闻      
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款