<p>Also called exponentiated gradient.</p>

<p>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?</p>

<p>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?</p>

<p>Related papers on <a href="http://www.cs.cmu.edu/~maz/publications/ICML03.pdf" rel="nofollow">regret (pdf)</a>, <a href="http://www.sciencedirect.com/science/article/pii/S0167637702002316" rel="nofollow">mirror descent</a>, and
multiplicative weights application from S.A. Plotkin, D.B. Shmoys, and E. Tardos (1991).</p>

CC BY-SA 3.0
2012-01-09T06:22:21.237Z
Have you read the survey by Arora, Hazan and Kale ? http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf
Suresh Venkat
CC BY-SA 3.0
2012-01-09T18:09:04.080Z
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.
Elliot JJ
CC BY-SA 3.0
2012-01-09T19:38:04.030Z
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!)
Suresh Venkat
<optimization><lg.learning><online-algorithms>
View of Multiplicative Weights in contexts of combinatorial optimization, low-regret/online optimization, and entropy-regularized gradient descent?
Elliot JJ
# View of Multiplicative Weights in contexts of combinatorial optimization, low-regret/online optimization, and entropy-regularized gradient descent?

(Asked by: username_0 on 2012-01-09)

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)](http://www.cs.cmu.edu/~maz/publications/ICML03.pdf), [mirror descent](http://www.sciencedirect.com/science/article/pii/S0167637702002316), and
multiplicative weights application from S.A. Plotkin, D.B. Shmoys, and E. Tardos (1991).

**Tags:** optimization, lg.learning, online-algorithms

> **Comments:**
> **username_1**: Have you read the survey by Arora, Hazan and Kale ? http://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf  
> **username_0**: 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.  
> **username_1**: 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!)  

---

## 0 answers

