Also called exponentiated gradient.

I understand these are three places where multiplicative weights shows up (i.e. $w_{t+1} = w_{t}e^{- \text{loss}(w_{t})}$ or variations. And I understand a bit about these interpretations. But what ties them all together? In particular, multiplicative weights has been around a long time and appeared in combinatorial optimization contexts that I understand much less well than the low-regret interpretation. I kind of understand the connection between convex optimization and low-regret learning, but I don't understand why entropy appears as the proximal gradient regularization term. Is there an information-theoretic interpretation of all this? And does it clarify anything?

In other words, there's a web of connections here, I know a lot of people are paying attention to this, and I understand bits and pieces, but what's the best lens to get at the big picture?

Related papers on regret (pdf), mirror descent, and multiplicative weights application from S.A. Plotkin, D.B. Shmoys, and E. Tardos (1991).

  • 1
    $\begingroup$ Have you read the survey by Arora, Hazan and Kale ? cs.princeton.edu/~arora/pubs/MWsurvey.pdf $\endgroup$ – Suresh Venkat Jan 9 '12 at 6:22
  • $\begingroup$ I have it on a stack. Does it help answer my questions? I know it was published before a lot of work started coming out from TTIC on the online convex optimization setting. $\endgroup$ – Elliot JJ Jan 9 '12 at 18:09
  • $\begingroup$ It gives numerous examples (more than three :)). My feeling, after spending some time recently studying the method, is that there isn't just one interpretation (which is what makes it neat!) $\endgroup$ – Suresh Venkat Jan 9 '12 at 19:38

Your Answer

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

Browse other questions tagged or ask your own question.