The weighted marjority algorithm

$$\begin{split} & 初始化 \eta\le \frac12,每个专家i的初始权重为w_i^1 = 1\\ & 对于第t个回合（1\le t\le T）\\ & \qquad 服从两类专家中权重更大的那一方\\ & \qquad 接受正确答案（上或者下），仅将回答错误的专家的权重缩减\\ & \qquad \qquad w_i^{t+1} = w_i^t(1-\eta) \end{split}$$

Theroem

在T回合结束后，记$m_i^T$为第i个专家的犯错次数，$M_i^T$为算法的犯错次数，那么有上界

$$M^T\le 2(1+\eta)m_i^T+\frac{2\ln n}{\eta}$$

对于任意的事后决策i都成立.

_pf_:

对于第t个回合来说，如果此回合中算法犯错，那么犯错专家的权重之和大于 $\frac 12$.根据定义，$w_i^{T+1} = (1-\eta)^{m_i^T}$

记$\phi^t = \sum_{i=1}^nw_i^t$

则有

$$\phi^t(1-\eta)\le\phi^{t+1}\le \frac{\phi^t}{2}(1-\eta)+\frac{\phi^t}{2}$$

若算法没有犯错，则有

$$\frac{\phi^t}{2}(1-\eta)+\frac{\phi^t}{2}\le\phi^{t+1}\le \phi^t$$

进而

$$\phi^{T+1}\le n(1-\frac\eta2)^{M^T}$$

且

$$\phi^{T+1}\ge w_i^{T+1}$$

对于$\eta<\frac12$, 有$-\ln (1-\eta)\le \eta+\eta^2$,命题成立

The Multiplicative Weights Algorithm

Setting

更为广义的设定是，每一个回合中我们有n个决策，在选择决策之后会知晓所有决策对应的损失，同时得到我们所作出的决策对应的损失。

Notation

对于第t个回合(t=1,$\dots$,T), 第i个决策对应的权重为$p_i^t$,对应的损失为$m_i^t$，那么这一个回合的期望损失为$$。从online learning的角度看，最后最小化$\sum_{t=1}^T<p^t,m^t>-\min_i \sum_{t=1}^Tm_i^t$

Algorithm

$$\begin{split} & 初始化：固定\eta\le \frac12，w_i^1 = 1\\ & 对于t=1 \dots,T\\ & \qquad p^t = w^t/\|w^t\|_1,根据p^t随机选择一个决策i\\ & \qquad 获得m^t\\ & \qquad 根据每个决策的损失更新权重 w_i^{t+1} = w_i^t(1-\eta m_i^t) \end{split}$$

Theorem

假设所有损失$m_i^t\in [-1,1]$,$\eta\le \frac12$，那么对于任意事后决策i成立：

$$\sum_{t=1}^T<p^t,m^t>\le \sum_{t=1}^T m_i^t+\eta\sum_{t=1}^T|m_i^t|+\frac{\ln n}{\eta}$$

_pf_:

$$\begin{split} & \|w^{t+1}\|_1 = \sum_{i=1}^n w_i^{t+1} \\ & = \sum_{i=1}^n w_i^{t}(1-\eta m_i^t) \\ & =\|w^t\|_1-\eta\|w^t\|_1\sum_{i=1}^n p_i^tm_i^t\\ & \le \|w^t\|_1 \exp(-\eta <p^t,m^t>) \end{split}$$ $$\|w^{T+1}\|_1\le n\exp(-\eta\sum_{t=1}^T <p^t,m^t>)$$

根据指数函数的凸性，

$$(1-\eta)^x\le (1-\eta x), \quad x\in [0,1]$$ $$(1+\eta)^{-x}\le 1-\eta x,\quad x\in [0,1]$$

因为$m_i^t\in [-1,1]$,对于所有决策i，

$$\|w^{T+1}\|_1\ge w_i^{T+1} = \prod_{t=1}^T(1-\eta m_i^t)\ge (1-\eta)^{\sum_{\ge 0}m_i^t}(1+\eta)^{-\sum_{< 0}m_i^t}$$

取对数，可知

$$\ln n - \eta\sum_{t=1}^T <p^t,m^t>\ge \sum_{\ge 0}m_i^t \ln (1-\eta) -\sum_{< 0}m_i^t\ln (1+\eta)$$

利用

$$\ln \frac1{1-\eta}\le \eta+\eta^2,\quad \ln (1+\eta)\ge \eta-\eta^2,\quad \eta\le \frac12$$

命题可证

如果将命题中的不等式加权相加，可知对任意后验的决策上的分布p，有

$$\sum_{t=1}^T<p^t,m^t>\le \sum_{t=1}^T <m^t+\eta|m^t|,p>+\frac{\ln n}{\eta}$$

Update with exponential factors: The Hedge algorithm

$$w_i^{t+1} = w_i^t\exp(-\eta m_i^t)$$

得到的上界略有不同，使用不等式$\exp(-\eta x)\le 1-\eta x+\eta^2x^2,\quad |\eta x|\le 1$替换前述不等式。

Theorem

假设$m_i^t\in [-1,1],\eta\le 1$。Hedge算法保证在T回合之后，对于任意决策i，有

$$\sum_{t=1}^T\langle p^t,m^t\rangle = \sum_{t=1}^T m_i^t + \eta \sum_{t=1}^T \langle p^t,(m^t)^2\rangle + \frac{\ln n}{\eta}$$

Proof via KL-divergence : why MW works

考虑以下情形：定义$\mathbb{P}$为在决策上的所有概率分布的凸子集，在每一个回合t中，决策者需要生成一个决策上的概率分布$p^t\in \mathbb{P}$，当做出决策之后，就会知晓$m^t$，决策者的期望损失是$\langle p^t,m^t \rangle$。在所有回合结束之后，我们希望比较决策者的总损失和后验的最佳决策概率分布(属于$\mathbb{P}$)带来的损失。

$$\min \quad \sum_{t=1}^T \langle p^t,m^t\rangle - \min_p \sum_{t=1}^T\langle p,m^t\rangle$$

Algorithm

$$\begin{split} & 初始化：固定\eta\le \frac12，选择p^1 = \frac1ne, e为全一向量\\ & 对于t = 1,\dots,T\\ & \qquad 根据p^t随机选择一个决策i\\ & \qquad 知晓所有决策对应的损失m^t\\ & \qquad 更新 \hat{p}_i^{t+1} = p_i^t(1-\eta m_i^t)/\phi^t，其中\phi^t是归一化常数\\ & \qquad 投影获得p^{t+1} = \argmin_{p\in \mathbb{P}} KL(p||\hat{p}^{t+1}) \end{split}$$

Theorem

假设$m_i^t\in [-1,1],\eta\le 1$。有限分布的MW算法保证在T回合之后，对于任意决策概率分布$p\in \mathbb{P}$，有

$$\sum_{t=1}^T \langle p^t,m^t\rangle \le \sum_{t=1}^T \langle(m^t+\eta|m^t|),p\rangle + \frac{KL(p||p^1)}{\eta}$$

_pf_:

使用$p$和$p^t$的KL散度作为potential function

$$\begin{split} & \mathrm{KL}(p||\hat{p}^{t+1}) - \mathrm{KL}(p||p^t) = \sum_i p_i\ln \frac{p_i^t}{\hat{p}_i^{t+1}}\\ & = \sum_i p_i\ln \frac{\phi^t}{1-\eta m_i^t}\\ & \le \ln \frac{1}{1-\eta}\sum_{\ge 0}p_im_i^t + \ln (1+\eta)\sum_{<0}p_im_i^t + \ln \phi^t\\ & \le \eta\langle p,m^t+\eta|m^t|\rangle + \ln \phi^t \end{split}$$

然后，我们有

$$\ln \phi^t = \ln \sum_{i}p_i^t(1-\eta m_i^t) = \ln (1-\eta \langle p^t,m^t\rangle)\le -\eta \langle p^t,m^t\rangle$$

从而有

$$\mathrm{KL}(p||\hat{p}^{t+1}) - \mathrm{KL}(p||p^t) \le \eta\langle p,m^t+\eta|m^t|\rangle -\eta \langle p^t,m^t\rangle$$

这个不等式说明了如果本回合的期望损失过大（相对于后验的p），那么$\hat{p}^{t+1}$在KL散度意义下比$p^t$距离$p$更近

根据Generalized Pythagorean inequality,

$$\mathrm{KL}(p||p^{t+1}) - \mathrm{KL}(p^{t+1}||\hat{p}^{t+1})\le \mathrm{KL}(p||\hat{p}^{t+1})$$

从而

$$\mathrm{KL}(p||p^{t+1}) - \mathrm{KL}(p||p^t) \le \eta\langle p,m^t+\eta|m^t|\rangle -\eta \langle p^t,m^t\rangle$$

求和，可得

$$- \mathrm{KL}(p||p^1) \le \mathrm{KL}(p||p^{T+1}) - \mathrm{KL}(p||p^1) \le \sum_{t=1}^T\eta\langle p,m^t+\eta|m^t|\rangle -\eta \langle p^t,m^t\rangle$$

QED.

Gains instead of loss

如果每一个回合获得的是收益$m_i^t$，只需要将前述定理中的$m_i^t$去负号