User:Shitikanth/sandbox/Multiplicative Weights Update Method

In computer science, multiplicative weights update method (MWU) is an algorithm design paradigm for various optimization problems based on the idea of maintaining a distribution over a set and using the multiplicative update rule to change these weights iteratively.

Multiplicative weights update algorithm

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 {\frac {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

Category:Algorithms