在线梯度下降

算法 ​

在闭凸决策集 $K\subseteq {\mathbb{R}}^d$ 中选 $x_1$。第 $t$ 轮承受凸损失 $f_t(x_t)$ 后取 $g_t\in \partial f_t(x_t)$，更新

$$x_{t+1}={\mathrm{\Pi }}_K(x_t-\eta g_t),$$

其中 ${\mathrm{\Pi }}_K(y)=\arg \underset{x\in K}{min}\Vert x-y{\Vert }_2$ 是一般闭凸集的欧氏投影，不只限于线性子空间。

Regret 推导 ​

对任意比较器 $u\in K$，凸性给 $f_t(x_t)-f_t(u)\le ⟨g_t,x_t-u⟩$。投影的非扩张性又给

$$\Vert x_{t+1}-u{\Vert }^2\le \Vert x_t-u{\Vert }^2-2\eta ⟨g_t,x_t-u⟩+{\eta }^2\Vert g_t{\Vert }^2.$$

整理、求和，距离项望远镜消去：

$$\sum _{t=1}^T[f_t(x_t)-f_t(u)]\le \frac{\Vert x_1-u{\Vert }^2}{2\eta }+\frac{\eta }{2}\sum _t\Vert g_t{\Vert }^2.$$

若 $K$ 直径至多 $D$ 且 $\Vert g_t{\Vert }_2\le G$，取 $\eta =D/(G\sqrt{T})$ 得 ${\mathrm{Reg}}_T\le DG\sqrt{T}$。

在线线性预测例子 ​

每轮收到特征 $a_t$ 后选择 $x_t$，损失 $f_t(x)=⟨a_t,x⟩$，则 $g_t=a_t$。OGD 沿累计不利方向移动，再投影回可行集。对欧氏球投影有简单闭式；若 $K$ 是复杂多面体，求投影本身可能比一次梯度计算昂贵，这属于计算代价而非 regret 证明的一部分。

边界与变体 ​

上述不等式使用 $f_t$ 的凸性；非凸损失下次梯度内积不再上界比较器差，不能保留同一证明。一般范数几何中，梯度应以对偶范数界住，并改用镜像下降。未知 $T$ 可取 ${\eta }_t\propto 1/\sqrt{t}$ 或用 doubling。若把步长和 $D,G$ 的尺度配错，平方根界也会失去量纲一致性。

参考资料

• Martin Zinkevich, Online Convex Programming and Generalized Infinitesimal Gradient Ascent, ICML, 2003.
• Elad Hazan, Introduction to Online Convex Optimization.