Online Learning 4

Follow the Leader Against Quadratics

某些情况下,FTL是非常好的算法,比如一维的线性回归的情况,很容易推广到高维

  • 每一轮选择\(w_t\in[-1,1]\)
  • 对手选择\(y_t\in[-1,+1]\)
  • 计算\(f_t(w)=\frac{1}{2}(w-y_t)^2\)

使用FTL算法: $$ \begin{aligned} w_{t+1}&=f_{1:t}(w)\ f_t(w)&=(w-y_t)2=w2-wy_t+y_t^2\

\end{aligned} \[ 由于$y_t^2$是常数,所以我们令 \] \begin{aligned} f_t(w)&=w2-wy_t\ f_{1:t}(w)&=w2-y_{1:t}w \end{aligned} \[ 我们的目标就是求 \] w_{t+1}=f_{1:t}(w) \[ 对$w$求导并令导数为$0$,我们有 \] w_{t+1}= $$

定理1:如果\(f\)是一个凸函数,那么\(\forall w,w_t\in\mathcal{W}\),有 \[ \begin{aligned} f(w)& \geq f(w_t)+\triangledown f(w_t)(w-w_t) \\ \end{aligned} \]

所以我们有 \[ \begin{aligned} f(w_t) - f(w_{t+1}) & \leq \triangledown f(w_t)(w_t-w_{t+1}) \\ &\leq \|\triangledown f(w_t)\|\|w_t-w_{t+1}\| \end{aligned} \] 我们可以发现上述不等式右边,第一项小于梯度的界,第二项小于两次迭代间距离的界。现在我们可以计算二次情况下的悔恨值的界 \[ \begin{aligned} w_t-w_{t+1} &= \frac{y_{1:t-1}}{t-1}-(\frac{y_{1:t-1}}{t-1}\cdot\frac{t-1}{t}+\frac{y_t}{t})\\ &=\frac{y_{1:t-1}}{t(t-1)}-\frac{y_t}{t}\\ &\leq \frac{t-1}{t(t-1)}+\frac{1}{t}\\ &\leq \frac{2}{t} \end{aligned} \] 其中第三步是因为\(y_t\in[-1,+1]\),所以可以得到悔恨的界为 \[ \text{Regret} \leq\sum_t f_t(w_t)-f_t(w_{t+1}) \leq\sum_t2(\frac{2}{t}) \leq4\sum_t\frac{1}{t} \leq 4(\log(T)+1) \]

Playing Against Linear Functions

Linearizing Convex Functions

线性化一个凸函数会让在线学习变得更难,对于任意\(w^*\)\(g_t\in\part f_t(w_t)\)\[ \begin{aligned} w^* &= \underset{w\in\mathcal{W}}{\arg\min}f_{1:t}(w^*) \\ \text{Regret}(T) &= f_{1:t}(w_t)-f_{1:t}(w^*)\\ &=\sum^T_{t=1}[f_t(w_t)-f_t(w^*)]\\ &\leq \sum^T_{t=1}[w_t\cdot g_t-w^*\cdot g_t] \end{aligned} \] Linearization

正如上图所示,用线性近似的话,其他选择的损失是被降低的,因此会导致悔恨的增加。因此,线性情况下的悔恨(linearized regret)是凸函数情况下的悔恨(convex regret)的上界。使用这个性质,通过变换凸在线学习问题到线性在线学习问题,我们可以得到有界的悔恨值。线性情况下,我们最优的情况是\(\sqrt{T}\)的悔恨,在有严格凸的假设下,可以做得更好。

定义1:一个函数\(f:\mathbb{R}^n\rightarrow\mathbb{R}\),如果\(\forall w, w'\in\mathbb{R}^n\),有 \[ \|f(w)-f(w')\|\leq G\|w-w'\| \] 那么这个函数\(f\)是G-Lipschitz的。

定理2:对于一个凸函数\(f:\mathbb{R}^n\rightarrow\mathbb{R}\),如果是G-Lipschitz,当且仅当对于\(\forall w\in\mathbb{R}^n\)\(\forall g\in\part f_t(w_t)\),有\(|g|\leq G\)

证明:

必要性,选择\(w\in\mathcal{W}\)\(g\in\part f_t(w_t)\)\[ G\|w-w-\frac{g}{\|g\|}\|\geq f(w+\frac{g}{\|g\|})-f(w) \] 根据次梯度的定义 \[ f(w+\frac{g}{\|g\|})-f(w) \geq (w+\frac{g}{\|g\|}-w)g =\frac{g\cdot g}{\|g\|} =\|g\| \] 充分性,选择\(w'\in\mathcal{W}\)\(g\in\part f_t(w_t)\) \[ f(w')-f(w)\leq(w'-w)\cdot g\leq\|w'-w\|\cdot\|g\|\leq\|w'-w\|G \] 证毕。\(\Box\)

所以当我们用一个凸的Lipschitz函数时候,FTRL可以达到\(\mathcal{O}(\sqrt{T})\)的悔恨值。