前两天 @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.be
- www.youtube.com
本节定义预备知识: Fenchel-Legendre Duality.
给定一个 上良好的凸函数(proper convex function, 可以简单认为该凸函数在有效定义域上不会达到负无穷) , 它的 Fenchel dual 定义为:
在这种条件下, 我们拥有强对偶定理成立: 即一个函数的对偶的对偶还是它自己
还有其它值得注意的性质:
也是(proper)convex 的
L-smooth 等价于 1/L strongly convex
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)来刻画也就是说, 每种形式都可以分为四类:
strongly-convex 且 smooth
strongly-convex 但不 smooth
不 strongly-convex 但 smooth
不 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) 中的自然应用, 也会指出一些关键性的推导步骤
来源: http://www.tuicool.com/articles/go/f22EBz2