在线凸优化 | Codeboy's Blog

形式陈述

协议与静态比较器

在在线学习协议中，给定非空凸可行域 $K\subseteq\mathbb R^d$ 。第 $t$ 轮学习器先选 $x_t\in K$ ，随后环境揭示实值凸函数 $f_t:K\to\mathbb R$ 并收取 $f_t(x_t)$ 。相对最好固定点的静态遗憾为

\sum_{t=1}^Tf_t(x_t)-\inf_{x\in K}\sum_{t=1}^Tf_t(x).

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

凸线性化

在线线性损失 $f_t(x)=\langle g_t,x\rangle$ 是核心特例。对一般凸损失，当本轮点存在有限次梯度 $g_t\in\partial f_t(x_t)$ 时，一阶条件给

f_t(x_t)-f_t(x)\le\langle g_t,x_t-x\rangle,

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

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

在线梯度下降界

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

\|x_{t+1}-u\|^2\le\|x_t-u\|^2-2\eta\langle g_t,x_t-u\rangle+\eta^2\|g_t\|^2.

这里要求 $K$ 非空、闭且凸，使欧氏投影存在且唯一。对时间求和时距离项望远镜消去；凸性给的是损失差不超过内积，而不是反方向。因此对每个固定 $u\in K$ ，

\sum_t[f_t(x_t)-f_t(u)]\le\frac{\|x_1-u\|^2}{2\eta}+\frac{\eta}{2}\sum_t\|g_t\|^2.

若域直径为 $D$ 、次梯度范数至多 $G$ ，选择 $\eta=D/(G\sqrt T)$ 得到遗憾至多 $DG\sqrt T$ ；退化情形 $D=0$ 或 $G=0$ 可直接处理，无需使用这个商。

直觉

在线凸优化像在不断移动的地形上行走：学习器踩下 $x_t$ 后才看见当轮坡面。次梯度给出当前位置朝哪个方向损失上升，投影则把更新拉回可行域。凸性保证这一条局部坡度足以控制与任意固定比较点的当轮差距，不必预先知道未来地形。

证明中的平方距离是一份势能账本。一次梯度更新若朝比较器靠近，距离下降会支付当轮线性化损失；步长造成的二次项是移动成本。对所有轮求和后，中间距离互相抵消，只剩初始直径与累计梯度代价，平衡二者便出现 $\sqrt T$ 速率。

例子与边界

追逐上一轮最小点

取 $K=[-1,1]$ 、 $f_t(x)=(-1)^t x$ ，初始 $x_1=0$ 。若总选上一轮损失的最小点，则 $x_2=1,x_3=-1$ ，以后继续交替，每轮从第二轮起都付损失 $1$ 。偶数 $T$ 时任意固定点的累计损失都是零，这个追逐策略的遗憾却是 $T-1$ 。强凸性等额外结构可改善速率；仅有光滑性并不足以排除此反例，因为线性函数本身已有光滑梯度。

区间投影与非欧氏几何

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

反馈边界

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

推论与应用

Follow-the-Regularized-Leader在每轮最小化过去累计损失加正则项，以正则曲率稳定相邻决策并导出遗憾界。它适合能够有效求解该正则化子问题的凸域；若每轮优化本身不可计算或只给 bandit 值反馈，就必须再加入近似优化或梯度估计误差。

在线梯度下降把 OCO 的一般模型具体化为一个只需当前次梯度和凸投影的算法；在线镜像下降则按域的几何选择正则函数，在概率单纯形上可恢复与指数权重相近的更新。不同算法共享同一个静态遗憾目标，但势函数和范数必须配套。

若损失强凸，可用递减步长得到对数级遗憾；若只具普通凸性， $O(\sqrt T)$ 是典型尺度；若只有函数值反馈，则需要随机扰动构造梯度估计并付出维度与方差代价。这些改进都来自额外结构或额外信息，不能只改学习率便获得。

在随机 IID 损失下，OCO 的平均遗憾还可通过在线到批转换变成总体风险界。应用于大规模学习时，这让单遍梯度法同时具有序贯保证与批学习解释；转换仍需明确输出平均迭代点、损失凸性和样本顺序，不能把最后一个迭代点默认当作低风险解。

参考资料

Martin Zinkevich, “Online Convex Programming and Generalized Infinitesimal Gradient Ascent,” in Proceedings of the 20th International Conference on Machine Learning (ICML 2003), pp. 928–936.
Elad Hazan, Introduction to Online Convex Optimization, Foundations and Trends in Optimization 2(3–4), 2016, pp. 157–325.

形式陈述 ​

协议与静态比较器 ​

凸线性化 ​

在线梯度下降界 ​

追逐上一轮最小点 ​

区间投影与非欧氏几何 ​

反馈边界 ​