Introduction to online optimization: continuous exp strategy

534 浏览 0 回复 2020-02-16

sabo

+关注

extend exp strategy to continuous exp strategy

$a_t = \int_{a\in A}\frac{w_t(a)}{W_t}a da$
where

$w_t(a) = exp(-\eta\Sigma_{s=1}^{t-1}\ell(a,z_s)),W_t=\int_{a\in A}w_t(a) da$

For any convex loss taking values in [0,1], the continuous exp strategy satisfies $\forall \gamma$ >0:
图片说明 (虽然敲一遍有助于理解,但是太长了)

$log\frac{W_{t+1}}{W_1} \le -\eta\ell(a_t,z_t)+\frac{\eta^2}{8}$
$R_n \le \frac{dlog{\frac{1}{\gamma}}}{\eta} + \frac{n\eta}{8} + \gamma n$

For any $\sigma$ -exp-concave loss, the continuous exp strategy with parameter $\eta = \sigma$ satisfies: $R_n \le 1 + \frac{dlogn}{\sigma}$