User:Diffeomorphicvoodoo/sandbox/Multiplicative weights update method

Multiplicative weights update algorithm

We have n experts who give advice about some decision each day. Each decision incurs a certain loss which is revealed only after we make the decision. The loss incurred at the t^th day if we follow expert i's advice is given by $m_{i}(t)$. The following algorithm picks the experts in a way such that the total loss incurred over T days is approximately the loss incurred by the best expert.

Algorithm

1. for i = 1 to n

   $w_{i}(t)\leftarrow 1$

2. $\Phi (1)\leftarrow n$.
3. for t = 1 to T

   $p_{i}(t)=w_{i}(t)/\Phi (t)$

   Sample an i from the probability distribution $p_{i}(t)$ and follow expert i's advice.

   Observe the loss obtained by the experts - $m_{i}(t)$

   $w_{i}(t+1)=w_{i}(t).(1-\varepsilon )^{m_{i}(t)}$

   $\Phi (t+1)=\sum _{i}w_{i}(t+1)$

Analysis

Theorem: For any $\varepsilon \leq 1/2$, the expected loss incurred by the above algorithm is bound as follows:

$\sum _{t=1}^{T}\langle p(t),m(t)\rangle \leq (1+\varepsilon )\sum _{t=1}^{T}m_{i}(t)+{\frac {\ln n}{\varepsilon }}$

(The inequality holds for all i = 1 to n, and, in particular, for the expert that minimizes the losses).

Proof:

$\Phi (t+1)=\sum _{i=1}^{n}w_{i}(t)(1-\varepsilon )^{m_{i}(t)}$.

Since $(1-\epsilon )^{x}\leq (1-\epsilon x)$, for $0\leq x\leq 1$,

$\Phi (t+1)\leq \sum _{i=1}^{n}w_{i}(t)(1-\varepsilon {m_{i}(t)})=\Phi (t)-\varepsilon \langle w(t),m(t)\rangle =\Phi (t)(1-\varepsilon \langle p(t),m(t)\rangle )$.

Since $e^{x}\geq 1+x$ for all $x$,

$\Phi (t+1)\leq \sum _{i=1}^{n}w_{i}(t)(1-\varepsilon {m_{i}(t)})=\Phi (t)-\varepsilon \langle w(t),m(t)\rangle =\Phi (t)(1-\varepsilon )^{\langle p(t),m(t)\rangle }$.

Therefore, by induction,

$\Phi (T+1)\geq n(1-\varepsilon )^{\sum _{i=1}^{T}\langle p(t),m(t)\rangle }$

Furthermore, $\Phi (T+1)=\sum _{i=1}^{n}w_{i}(T+1)\geq w_{i}(T+1)=(1-\varepsilon )^{\sum _{t=1}^{T}m_{i}(t)}$.

The theorem follows immediately from the above two inequalities.

Matrix multiplicative weights update algorithm

This is a matrix generalization of the multiplicative weights update algorithm. We associate an expert to every unit vector $v\in \mathbb {C} ^{n}$. The loss incurred by an expert $v$ on day t is given by $v^{\ast }M(t)v$, where $M(t)$ is the loss matrix for day t.

Algorithm

1. for i = 1 to n

   $W(1)\leftarrow \mathbb {I}$

2. $\Phi (1)\leftarrow {\text{Tr}}(W(1))=n$.
3. for t = 1 to T

   $\rho (t)=W(t)/\Phi (t)$

   Follow expert's advice according to $\rho (t)$

   Observe the loss matrix for day t - $M(t)$

   $W(t+1)=\exp {\Big (}-\varepsilon \sum _{i=1}^{t}M(t){\Big )}$

   $\Phi (t+1)={\text{Tr}}(W(t+1))$

Analysis

Theorem: For any $\varepsilon \leq 1/2$ and for any $v\in \mathbb {C} ^{n}$, the expected loss incurred by the above algorithm after T rounds is bound as follows:

$(1-\varepsilon )\sum _{t=1}^{T}\langle \rho (t),M(t)\rangle \leq \sum _{t=1}^{T}v^{\ast }M(t)v+{\frac {\ln n}{\varepsilon }}$

Category:Algorithms