在线凸优化

模型 ​

给定凸可行域 $K$。第 $t$ 轮学习器先选 $x_t\in K$，随后环境揭示凸函数 $f_t$ 并收取 $f_t(x_t)$。静态遗憾为

$$\sum _{t=1}^T{f}_t(x_t)-\underset{x\in K}{inf}\sum _{t=1}^T{f}_t(x).$$

比较器固定，不能把每轮各自最小化 $f_t$ 的动态 oracle 偷换进来。

在线线性损失 $f_t(x)=⟨g_t,x⟩$ 是核心特例。对一般凸损失，一阶条件给

$$f_t(x_t)-f_t(x)\le ⟨g_t,x_t-x⟩,$$

从而把遗憾归约到线性化损失。在线梯度下降在域直径有界、次梯度范数有界时给 $O(\sqrt{T})$ 界；若 $K$ 或梯度无界，这些常数不存在。

看到完整 $f_t$、只得到 $g_t$、或仅观察 $f_t(x_t)$ 是不同反馈模型。OCO 也不是反复求解已知总目标的静态凸优化：未来损失在行动时未知，难点是因果决策。

在线梯度下降取 $x_{t+1}={\mathrm{\Pi }}_K(x_t-\eta g_t)$。投影的非扩张性给

$$\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.$$

对时间求和时距离项望远镜消去，再用凸性把内积上界成 $f_t(x_t)-f_t(u)$。若域直径为 $D$、梯度范数至多 $G$，选择 $\eta =D/(G\sqrt{T})$ 便得到遗憾至多 $DG\sqrt{T}$。

每轮单独最小化刚揭示的 $f_t$ 是“追昨天的目标”，未必低遗憾；交替把最小点放在可行域两端即可让这种策略来回震荡。强凸性或光滑性可改善速率，但属于额外曲率，不能从普通凸性推出。

可行域投影是到闭凸集的最近点，不必是线性子空间投影。以 $K=[-1,1]$ 为例，${\mathrm{\Pi }}_K(y)$ 就是把 $y$ 截断到区间；这一步保证更新始终可行。换用 Bregman 投影和对偶几何便得到在线镜像下降，适合概率单纯形等非欧氏域。

若 $f_t$ 在行动前已知，学习器可以每轮选其最小点，协议变成另一问题；若只观察标量 $f_t(x_t)$，连次梯度 $g_t$ 都不可用，进入 bandit convex optimization。OCO 定理必须在反馈假设中说明获得完整函数还是一阶 oracle。

参考资料

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