Online Learning 2

The Online Optimization Game

在线优化问题,具体指如下过程:

The Online Optimization Game
The Online Optimization Game
  1. 在每回合中,玩家(palyer)选择\(\mathbf{w}_t\in\mathcal{W}\),其中\(\mathcal{W}\subseteq\mathbb{R}^n\)是操作的可行集合
  2. 对手(adversary)选择一个损失函数\(f_t:\mathcal{W}\rightarrow\mathbb{R}\)
  3. 玩家承受损失\(f_t(w_t)\)
  4. 玩家更新\(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})\)