<p>The details are on page 3 of the paper <a href="http://www.pnas.org/content/pnas/111/29/10620.full.pdf" rel="nofollow noreferrer"><em>Algorithms, games, and evolution</em> by
Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani</a>. They explain how the multiplicative weights update rule $x_i^{t+1}(j) = \frac{x_i^t(j)}{Z^t} (1 + \epsilon u_i^t(j))$ can be recovered by imagining that we want to design an update rule that maximizes some convex combination of cumulative utility (expected) and entropy for each time $t$:</p>

<p>$$
\sum_j x_i^t(j) \sum_{t'=1}^t u_i^{t'}(j)
- \frac{1}{\epsilon} \sum_j x_i^t(j) \ln x_i^t(j).
$$</p>

<p>More details can be found in the <a href="http://www.pnas.org/content/pnas/suppl/2014/06/12/1406556111.DCSupplemental/pnas.201406556SI.pdf?targetid=nameddest%3DSTXT" rel="nofollow noreferrer">Supporting Information text that comes with the paper</a>.</p>

CC BY-SA 4.0
2018-05-03T11:08:52.400Z
2018-05-03T13:51:30.120Z
2018-05-03T13:51:30.120Z
Mmmh mmh
<p>Here's one way to look at it, based on <a href="https://cstheory.stackexchange.com/questions/32506/how-does-the-multiplicative-weights-update-method-maximize-entropy#comment74537_32506">usul's comment</a>.</p>

<p>Let the gains of each expert $i$ at time $t$ be given by $g_i^t$.</p>

<p>Then the expected gains of the algorithm are:</p>

<p>$$\sum_{u=1}^{t-1}\sum_i p_i^t g_i^u$$</p>

<p>We can then define the potential function</p>

<p>$$\Phi=\epsilon \sum_{u=1}^{t-1}\sum_i p_i^t g_i^u + \sum_i p_i^t \ln \left(\frac{1}{p_i^t}\right)$$</p>

<p>Where the right-hand term is the entropy and $\epsilon$ is a learning rate.</p>

<p>This function is maximized for</p>

<p>$$p_i^t = \exp\left(\epsilon \sum_{u=1}^{t-1} g_i^u-1\right)$$</p>

<p>We can find a similar expression that maximizes the function for $t+1$.</p>

<p>Taking the logarithms of these expressions and subtracting gives:</p>

<p>$$p_i^{t+1}=p_i^t \exp (\epsilon g_i^t)$$</p>

<p>Which is the MWU update rule.</p>

<p>Therefore, by applying this update rule we are maximizing a potential function of utility and entropy.</p>

CC BY-SA 3.0
2016-02-25T01:35:02.333Z
2016-02-25T01:35:02.333Z
Richard
<p>"The Multiplicative Weights Update (MWU) method is known to maximize both utility and entropy". This is a comment by C. Papadimitriou on MWU. I understand that MWU maximizes utility as it solves linear programming, for example. </p>

<p>The question is how MWU maximizes entropy? Can you give some example/information on this point?</p>

CC BY-SA 3.0
2015-09-11T18:37:55.170Z
Is there a context for the Papadimitriou quote? Is it from a paper or a talk or a private communication? If the former, do you have a link for people to take a look at?
Artem Kaznatcheev
CC BY-SA 3.0
2015-09-11T20:30:58.787Z
Papadimitriou's talk about MWU  (from minute 35:40):
https://www.youtube.com/watch?v=WoamKUfisVM
salmAn
CC BY-SA 3.0
2015-09-11T23:21:34.747Z
I don't know if this is what he was referring to, but I've seen this discussed in the context of Adaboost, which is more or less equivalent to MW. Adaboost is effectively coordinate descent on the solution space with the exponential loss function of the errors as the costs. Taking the Lagrangian dual of the corresponding program gets you an entropy maximization program. See e.g. http://arxiv.org/abs/0901.3590 .
Yonatan N
CC BY-SA 3.0
2015-09-13T11:45:24.123Z
Related (somehow): The multiplicative weights update rule for $h_t$ at time $t$ satisfies $$h_t = \max_h \left(\sum_{s\leq t} \text{util}_s(h)\right) + H(h), $$ where $H$ is entropy. (This is a special case of follow-the-regularized leader, though it is usually written as minimizing a loss not maximizing a utility.)
usul
<ds.algorithms><machine-learning><shannon-entropy>
How does the Multiplicative Weights Update method maximize entropy?
salmAn
# How does the Multiplicative Weights Update method maximize entropy?

(Asked by: username_0 on 2015-09-11)

"The Multiplicative Weights Update (MWU) method is known to maximize both utility and entropy". This is a comment by C. Papadimitriou on MWU. I understand that MWU maximizes utility as it solves linear programming, for example.

The question is how MWU maximizes entropy? Can you give some example/information on this point?

**Tags:** ds.algorithms, machine-learning, shannon-entropy
> **Comments:**
> **username_1**: Is there a context for the Papadimitriou quote? Is it from a paper or a talk or a private communication? If the former, do you have a link for people to take a look at?  
> **username_0**: Papadimitriou's talk about MWU  (from minute 35:40): https://www.youtube.com/watch?v=WoamKUfisVM  
> **username_2**: I don't know if this is what he was referring to, but I've seen this discussed in the context of Adaboost, which is more or less equivalent to MW. Adaboost is effectively coordinate descent on the solution space with the exponential loss function of the errors as the costs. Taking the Lagrangian dual of the corresponding program gets you an entropy maximization program. See e.g. http://arxiv.org/abs/0901.3590 .  
> **username_3**: Related (somehow): The multiplicative weights update rule for $h_t$ at time $t$ satisfies $$h_t = \max_h \left(\sum_{s\leq t} \text{util}_s(h)\right) + H(h), $$ where $H$ is entropy. (This is a special case of follow-the-regularized leader, though it is usually written as minimizing a loss not maximizing a utility.)  

---

## 2 answers

### Answer by username_5 on 2016-02-25. Score: 6 | Accepted answer

Here's one way to look at it, based on [usul's comment](https://cstheory.stackexchange.com/questions/32506/how-does-the-multiplicative-weights-update-method-maximize-entropy#comment74537_32506).

Let the gains of each expert $i$ at time $t$ be given by $g\_i^t$.

Then the expected gains of the algorithm are:

$$\sum\_{u=1}^{t-1}\sum\_i p\_i^t g\_i^u$$

We can then define the potential function

$$\Phi=\epsilon \sum\_{u=1}^{t-1}\sum\_i p\_i^t g\_i^u + \sum\_i p\_i^t \ln \left(\frac{1}{p\_i^t}\right)$$

Where the right-hand term is the entropy and $\epsilon$ is a learning rate.

This function is maximized for

$$p\_i^t = \exp\left(\epsilon \sum\_{u=1}^{t-1} g\_i^u-1\right)$$

We can find a similar expression that maximizes the function for $t+1$.

Taking the logarithms of these expressions and subtracting gives:

$$p\_i^{t+1}=p\_i^t \exp (\epsilon g\_i^t)$$

Which is the MWU update rule.

Therefore, by applying this update rule we are maximizing a potential function of utility and entropy.


---

### Answer by username_4 on 2018-05-03. Score: 2

The details are on page 3 of the paper [*Algorithms, games, and evolution* by
Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani](http://www.pnas.org/content/pnas/111/29/10620.full.pdf). They explain how the multiplicative weights update rule $x\_i^{t+1}(j) = \frac{x\_i^t(j)}{Z^t} (1 + \epsilon u\_i^t(j))$ can be recovered by imagining that we want to design an update rule that maximizes some convex combination of cumulative utility (expected) and entropy for each time $t$:

$$
\sum\_j x\_i^t(j) \sum\_{t'=1}^t u\_i^{t'}(j)
- \frac{1}{\epsilon} \sum\_j x\_i^t(j) \ln x\_i^t(j).
$$

More details can be found in the [Supporting Information text that comes with the paper](http://www.pnas.org/content/pnas/suppl/2014/06/12/1406556111.DCSupplemental/pnas.201406556SI.pdf?targetid=nameddest%3DSTXT).


---

