The Online Optimization Game
在线优化问题，具体指如下过程：
- 在每回合中，玩家（palyer）选择\(\mathbf{w}_t\in\mathcal{W}\)，其中\(\mathcal{W}\subseteq\mathbb{R}^n\)是操作的可行集合
- 对手（adversary）选择一个损失函数\(f_t:\mathcal{W}\rightarrow\mathbb{R}\)
- 玩家承受损失\(f_t(w_t)\)
- 玩家更新\(w_{t+1}\)
累计损失，\(T\)轮游戏后的累积损失，\(\sum^T_{t=1}f_t(w_t)\)。
玩家的悔恨（regret），\(T\)轮游戏后，\(\sum^T_{t=1}f_t(w_t)-\underset{\mathbf{w}\in\mathcal{W}}{\min}\sum^T_{t=1}f_t(w)\)，每一步的累积损失，和令累计损失最小的全局最优动作，所对应累积损失之差，即实际累计损失与事后的最小损失的差距。
Online Binary Predcition
上一篇说到的在线二分类预测问题是在线优化问题的一种特例，对比如下
| 在线二分类预测问题 | 在线优化问题 |
|---|---|
| 每一轮\(t\in{1,2,\cdots,T}\)选择一个\(h_t\in\mathcal{H}\) | 每一轮\(t\in{1,2,\cdots,T}\)选择一个\(w_t\in\mathcal{W}\) |
| 对手（adversary）选择\((x_t,y_t)\) | 对手选择损失\(f_t\) |
| 第\(t\)轮的损失是\(\mathbf{1}_{h_t(x_t)\neq y_t}\) | 第\(t\)轮的损失是\(f_t(w_t)\) |
我们可以认为假设\(h_t\)是以\(w_t\)为参数的假设，损失函数在线优化问题中的\(f_t(w)\)，\(f_t(w)=\mathbf{1}_{h_t(x_t)\neq y_t}\)。
Online Convex Optimization
相比于一般的在线优化问题，在线凸优化问题，
- \(\mathcal{W}\)是\(\mathbb{R}^n\)的凸的子集
- \(f_t\)是凸函数，\(\forall t\)
以下是一些例子：
- 在线线性回归，\(\mathbf{w}_t\in\mathcal{W}=\mathbb{R}^n\)，\(\mathbf{x}_t\in\mathbb{R}^n\)，\(y_t\in\mathbb{R}\)，\(f_t=(\mathbf{w}_t\cdot\mathbf{x}_t-y_t)^2\)
- 二次线性回归，\((\mathbf{w}_t,\mathbf{A_t})\in(\mathbb{R}^n\times\mathbb{R}^{n\times n})\)，\(\mathbf{x}_t\in\mathbb{R}^n\)，\(y_t\in\mathbb{R}\)，\(f_t=(\mathbf{w}_t\cdot\mathbf{x}_t+\mathbf{x}_t^T\mathbf{A}_t\mathbf{x}_t-y_t)^2\)
- ...
Follow The Leader(FTL) Algorithm
FTL算法更新方式如下： \[ \begin{aligned} \mathbf{w}_t & =\underset{\mathbf{w}\in\mathcal{W}}{\arg\min} \sum^t_{s=1}f_s(\mathbf{w})\\ &=\underset{\mathbf{w}\in\mathcal{W}}{\arg\min}f_{1:t}(\mathbf{w}) \end{aligned} \] 其中\(f_{1:t}(\mathbf{w})=\sum^t_{s=1}f_s(\mathbf{w})\)。