作者：李沐

Primal-dual的观点

《红楼梦》第三一回云：天地间都赋阴阳二气所生。世间有阴便有阳，在优化界也是如此。我们将需要最小化的目标函数称之为primal problem. 其对应就有dual problem. 例如常见的Lagrange Duality. 如果primal是凸的，那么dual便是凹的。且在常见情况下，最小化primal等价于最大化dual. 有时候直接求解primal problem很麻烦，但dual却方便很多。或是通过考察dual problem的性质能得到最优解的一些性质。一个经典的案例就是SVM.

上节我们通过子空间投影 $\Pi_{\mathcal{H}}$ 来处理罚，这里我们直接考虑最小化损失+罚的形式，既 $\min_w f(w) + \sum_{t=1}^T\ell_t(w)$ （罚前的参数 $\lambda$ 在这里写进了 $f(w)$ 里了）。注意到罚 $f(w)$ 的存在，使得目标函数不能如前面那样自然的分成 $T$ 块，从而不能直接对每块做梯度下降得到online gradient descent. 于是我们转向dual problem.

Shai Shalev-Shwartz提出可以用Fenchel Duality来研究其对偶式。Shai最近在online/stochastic界相当活跃。虽然和他不熟，不过因为他姓比较长，所以下面亲切的用Shai来称呼他。Shai 毕业于耶路撒冷希伯来大学，PHD论文便是online learning. 然后他去了online learning重地TTIC, 更是习得满身武艺，现在又回了耶路撒冷希伯来大学任教。他的数学直觉敏锐，善于将一些工具巧妙的应用到一些问题上。

两个概念

对一个凸函数，如下图所示，我们可以用两种不同的描述方式。一种就是函数上的所有点，函数曲线变由这些点构成；另外一种是每一个点所对应的切线，此时函数由所有切线形成的区域的上边缘确定。

函数上每一个点可由 $(w,f(w))$ 表示，每一条切线可由斜率 $\theta$ 及与y轴交点，记为 $-f^\star(\theta)$ ，来确定。前一种表示是函数的primal form, 而后者则被称之为Fenchel conjudate, 是一种dual form, 其定义为

$\displaystyle f^\star(\theta) = \max_w \langle w, \theta \rangle - f(w).$

既然我们称它们为primal-dual, 当然意味着可以相互转换。实际上，对于一个闭凸函数，有 $f^{\star\star}=f$ .

另外一个概念是关于函数凸的程度的。一个函数被称为 $\sigma$ -强凸（strongly convex），那意味着对任意的 $w$ 和 $u$ , 有

$\displaystyle f(w)-f(u)-\langle \nabla f(u), w-u\rangle\ge \frac{\sigma^2}{2}\|u-w\|^2.$

示意图如下。直观上来说就是这个凸函数要凸得足够弯。这个定义可以拓展到一般的范数和次导数上来处理诸如稀疏罚 $\|\cdot\|_1$ 之类，此乃后话了。

Regret Bound分析

使用这两个概念可以得到一个重要定理。假设 $f$ 是 $\sigma$ -强凸的，且 $f^\star(0)=0$ . 对任意的向量序列 $v_1,\ldots,v_T$ , 记 $w_t=\nabla f^\star\big(\sum_{j<t}v_j\big)$ 。那么对任意的向量 $u$ , 有

$\displaystyle \sum_t \langle u, v_t \rangle - f(u) \le f^\star \big(\sum_t v_t\big) \le \sum_t \big( \langle w_t, v_t\rangle + \frac{1}{2\sigma}\|v_t\|^2\big).$

此定理可以为Boosting, learning theory里的Rademecher Bound提供简单的证明，不过我们先关注它在online上的应用。不等式两边左右移项得 $\sum_t \langle u - w_t, v_t\rangle \le f(u) + \frac{1}{2\sigma} \sum_t \|v_t\|^2$ . 注意到 $w_t$ 只和比 $t$ 小 $v_j$ 相关，所以我们可以取 $v_t=-\nabla \ell_t(w_t)$ ，立即由 $f$ 是凸函数有 $f(w_t)-f(u)\le \langle u - w_t, v_t \rangle$ . 同前记 $w^*$ 是离线最优解，且假设 $\|\nabla \ell_t(w_t)\|\le L$ , 联立上面两不等式有， $R(T)\le f(w^*) + \frac{TL^2}{2\sigma}$ .

如果我们用 $\ell_2$ 罚，那么 $f=\lambda \|\cdot\|^2$ , 且 $\sigma=2\lambda$ . 如果 $\lambda=\frac{L\sqrt{T}}{2\|w^*\|}$ ，则有 $R(T)\le LD\sqrt{T}$ , 这里 $D=2\|w^*\|$ 是对子空间 $\mathcal{H}$ 直径的一个估计。与上节Online Gradient Descent的regret bound比较，他们一样！

一般化的online算法

不小心先把理论讲完了，下面来解释下算法。接回一开始我们谈到的要考虑dual problem. 先观察到primal problem可以写成

$\displaystyle \min_{w_0,\ldots,w_T}\left( f(w_0) + \sum_{t} \ell_t(w_t) \right)\quad \textrm{s.t.}\quad \forall t,\ w_t=w_0.$

引入 $T$ 个拉格朗日乘子 $u_t$ , 那么拉格朗日形式就是

$\displaystyle \mathcal{L}(w_0,\ldots,u_1,\ldots) = f(w_0) + \sum_t\ell_t(w_t) + \sum_t\langle u_t,w_0-w_t\rangle.$

这样dual problem就是最大化函数 $\min_{w_t} \mathcal{L}(w_0,\ldots,u_1,\ldots)$ ，记为 $\mathcal{D}(\cdot)$ . 套进Fenchel conjugate的定义，就有

$\displaystyle \mathcal{D}(u_1,\ldots,u_T)=-f^\star\big(-\textstyle \sum_t u_t\big)-\displaystyle \sum_t \ell^\star_t(u_t).$

注意到与primal problem不同，这时罚里面的变量也被拆成了 $T$ 份，所以在 $t$ 时刻我们可以假设比 $t$ 大的 $u_j$ 都是0, 从而只更新 $u_t$ 来增大 $\mathcal{D}$ .

总结下算法。在 $t$ 时刻，我们先计算 $w_t = \nabla f^\star\big(-\sum_{i<t} u_i\big)$ ，在收到数据的label后，选择 $u_t$ 来保证足够大的增加dual:

$\displaystyle \mathcal{D}(u_1,\ldots,u_{t-1},u_t,0,\ldots) \ge \mathcal{D}(u_1,\ldots,u_{t-1},\nabla \ell_t(w_t), 0, \ldots).$

下面是一个示意图。在每个时间里我们根据新来的数据不断的增大dual, 同时使得primal变小。

一个值得讨论的是，在这里我们可以控制算法的aggressive的程度。例如，如果我们每次只取 $u_t=\ell_t(w_t)$ ，就是意味着维持最小但使得理论分析成立的步伐长度。我们也可以使用更加激进的步伐， $u_t = \arg\max_u\mathcal{D}(\ldots,u_{t-1},u,0,\ldots)$ ，来最大限度的增加dual以期望收敛更快。不过这样通常使得每一步的计算开销更大。所以是仁者见仁智者见智了。

这个算法框架可以解释一系列算法，例如前面提到的Halving, 它使用激进步伐，或是WM, 使用平缓的步伐，以及Adaboost. 当然，我们可以从这个算法框架里推出新的有no-regret保证的新的online算法。

到这里，我们介绍的三个算法（前面是Online Gradient Descent, Weighted Majority）的regret bound都是 $\mathcal{O}(\sqrt{T})$ 。事实上，对于强凸的目标函数，目前已知最优的regret bound是 $\mathcal{O}(\log T)$ 。记得在OGD中我们使用固定的 $\mathcal{O}(1/\sqrt{T})$ 的学习率，如果我们将其改成变长的 $\mathcal{O}(1/t)$ ，那么变可以达到这个最优上界。对于这节介绍的方法，我们可以通常将罚 $f(w)$ 里面的 $\lambda$ 分成 $T$ 份给每个loss $\ell_t$ , 这样前 $t$ 个loss的和就是 $t\lambda/T$ -强凸，从而达到使用变长学习率的效果。具体可见Shai的NIPS ’08.