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

  • 3
    $\begingroup$ 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? $\endgroup$ – Artem Kaznatcheev Sep 11 '15 at 18:37
  • $\begingroup$ Papadimitriou's talk about MWU (from minute 35:40): youtube.com/watch?v=WoamKUfisVM $\endgroup$ – salmAn Sep 11 '15 at 20:30
  • 3
    $\begingroup$ 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. arxiv.org/abs/0901.3590 . $\endgroup$ – Yonatan N Sep 11 '15 at 23:21
  • 3
    $\begingroup$ 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.) $\endgroup$ – usul Sep 13 '15 at 11:45

Here's one way to look at it, based on usul's comment.

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.

| cite | improve this answer | |

The details are on page 3 of the paper Algorithms, games, and evolution by Erick Chastain, Adi Livnat, Christos Papadimitriou, and Umesh Vazirani. 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.