User:Shitikanth/sandbox/Multiplicative Weights Update Method

In computer science, multiplicative weights update method (MWU) is an algorithm design paradigm that is used for various optimization and learning problems. A multiplicative weights update algorithms works by maintaining a distribution over a set and using the multiplicative update rule to change these weights iteratively.

Multiplicative weights update method were proposed as an algorithm design paradigm by Arora, Hazan and Kale in 2008, who noticed that this idea was at the back of many algorithms in economics, machine learning and convex optimization.

The analysis of a multiplicative weights update algorithm usually involves quantifying the change in a potential function in each iteration.

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

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 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