Online Convex Programming

Definition 1

一个 convex programming 问题给出凸集 和一个凸的损失函数

最优解是最小化损失函数的

Definition 2

一个 online convex programming 问题给出凸集 和一族凸的损失函数

算法在每一步选择 , 随后得到

Definition 3

定义距离

定义

Algorithm 1

Greedy Projection 给出学习率

选择初始化的

每一步迭代公式为

Definition 4
对于一个算法 , 总损失为

对于某一个点的总损失为

定义后悔值:

相当于一个离线算法提前知道了所有 , 去求解 的最小值

因此这个后悔值描述了当前算法 与一个离线算法之间的差距

Theorem 1

定义

如果一个 online convex programming 问题满足这两个上界

并且

那么 Greedy Projection 的后悔值满足

因此

由凸函数性质

所以

展开 得到

所以

前一部分错位相减:

由于前面假设参数有界

且

所以原式

由于

所以

所以成立

---

参考:

1. ON THE CONVERGENCE OF ADAM AND BEYOND