在线梯度下降

OGD 把“今天损失上升最快的方向”当成下一步应避开的方向，再用投影把更新留在可行域。证明中的平方距离不是装饰：每次更新可能增加 ${\eta }^2\Vert g_t{\Vert }^2$，却会按比较器差距减少一项；把这些变化沿时间相加，距离预算便望远镜消去。

Regret 推导 ​

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

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

若 $K$ 直径至多 $D$ 且 $\Vert g_t{\Vert }_2\le G$，当 $D,G>0$ 且已知 $T\ge 1$ 时取 $\eta =D/(G\sqrt{T})$ 得 ${\mathrm{Reg}}_T\le DG\sqrt{T}$。

在线线性预测例子 ​

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

边界与变体 ​

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

欧氏投影版适合球或容易投影的凸集；概率单纯形等非欧氏几何通常由在线镜像下降理路在线镜像下降Online mirror descent · OMD以强凸势函数诱导的 Bregman 几何执行在线更新，并用三点恒等式得到对偶范数控制的遗憾界。用 Bregman 散度承接。若损失由 IID 样本依次产生，$O(\sqrt{T})$ 遗憾还可通过Online-to-Batch 转换理路Online-to-Batch 转换Online-to-batch conversion · 在线到批学习转换利用当前在线预测器只依赖过去样本的独立性，把平均在线遗憾转为批学习的期望超额风险。变成 $O(T^{-1/2})$ 的期望超额风险；这一步依赖本轮预测与本轮样本的独立性，不是 OGD 单独提供的性质。