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.
Motivating example - Portfolio selection
Multiplicative weights update algorithm
Algorithm
- for i = 1 to n
![{\displaystyle w_{i}(t)\leftarrow 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a0ef09b27f9d65dd137d77c2fef6fb30241e513)
.
- for t = 1 to T
![{\displaystyle p_{i}(t)=w_{i}(t)/\Phi (t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d590b143bd46be485f933baff50e1851f2ebfcc1)
- Sample an i from the probability distribution
and follow expert i's advice.
- Observe the loss obtained by the experts -
![{\displaystyle m_{i}(t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f339727a72fb114936bbe7528749108fe115cd7)
![{\displaystyle w_{i}(t+1)=w_{i}(t).(1-\varepsilon )^{m_{i}(t)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d89b6c5c509b6b248e22cbe7b9d6dc0c8da14f6d)
![{\displaystyle \Phi (t+1)=\sum _{i}w_{i}(t+1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43b8304c202bf25146843bb4ff8246208d97f367)
Analysis
Theorem: For any
, the expected loss incurred by the above algorithm is bound as follows:
(The inequality holds for all i = 1 to n, and, in particular, for the expert that minimizes the losses).
Proof:
.
Since
, for
,
.
Since
for all
,
.
Therefore, by induction,
Furthermore,
.
The theorem follows immediately from the above two inequalities.
Solving LPs/SDPs using Multiplicative weights
Matrix multiplicative weights update algorithm
Algorithm
- for i = 1 to n
![{\displaystyle W(1)\leftarrow \mathbb {I} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/be29af9f4e2e59c27724a684c61b21e756be91f8)
.
- for t = 1 to T
![{\displaystyle \rho (t)=W(t)/\Phi (t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3790cff686211e358a9cf098a1b72bfcf92d0ee8)
- Follow expert's advice according to
![{\displaystyle \rho (t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a66f7a7ba345de9189b12ee79bdf43ba9499c25e)
- Observe the loss matrix for day t -
![{\displaystyle M(t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fec7adc70ea0e1d365e5f7244b6f7ddad9fbf485)
![{\displaystyle W(t+1)=\exp {\Big (}-\varepsilon \sum _{i=1}^{t}M(t){\Big )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/530db2ab3b86cc30922bce6c916d24996e19577f)
![{\displaystyle \Phi (t+1)={\text{Tr}}(W(t+1))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/552a396ffd0cff8f7ae26b3c4a9e70574bb4f5cf)
Analysis
Theorem: For any
and for any
, the expected loss incurred by the above algorithm is bound as follows:
Category:Algorithms