在线凸优化

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

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

追逐上一轮最小点 ​

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

区间投影与非欧氏几何 ​

可行域投影是到闭凸集的最近点，不必是线性子空间投影。以 $K=[-1,1]$ 为例，${\mathrm{\Pi }}_K(y)$ 就是把 $y$ 截断到区间；这一步保证更新始终可行。换用 Bregman 投影和对偶几何便得到在线镜像下降公理库在线镜像下降Online mirror descent · OMD以强凸势函数诱导的 Bregman 几何执行在线更新，并用三点恒等式得到对偶范数控制的遗憾界。，适合概率单纯形等非欧氏域。

反馈边界 ​

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

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

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

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

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