Hacker News Reader

Comment by atq2119 | Hacker News Reader

+1 for Multiplicative Weights Update as a technique, and kudos for the nice write-up.

Having studied this myself a couple of years ago, I believe an intuitive way to understand its power is that MWU approximately optimizes an l_\infty-norm by approximating it with a sum of exponentials (the potential function from the proof). The analogy isn't perfect, but it helped me reason about it.

There is also a tentative link to tropical geometry because of this. When you have a problem that by its nature is "tropical" (using addition and taking maximums), the MWU method may be useful via translating into the non-tropical world of multiplication and addition, respectively.

View on HN

Multiplicative weights, like mirror descent, is a special case of a more general algorithm called mirror descent. You can indeed view it as optimizing an \ell_\infty norm, though I think the mirror descent perspective is more insightful. I wrote about this in my thesis, see section 2.4 here: http://timonknigge.com/univ/msc-thesis.pdf

Intuitive way?

Yes. Unlike l_\infty, sums of exponentials are smooth everywhere, and smooth functions are easier to optimize. But geometrically, the two can be brought arbitrarily close together by adjusting the exponents with a multiplicative constant.

What is "l_\infty"?

A norm (meaning a definition of "length") where the length of a vector is defined as the largest absolute value of any of its components. Its one of the standard lp norms, you get a norm for every p in the closed interval [1,infinity]. The standard Euclidian norm is the case p=2.

https://en.wikipedia.org/wiki/Lp_space#The_p-norm_in_finite_...

It's Latetx syntax, doesn't work in hn, but would be this: http://www.sciweavers.org/tex2img.php?eq=l_%5Cinfty&bc=White...

That's TeX for "l" with subscript infinity. It's a vector norm, and is equal to the element of the vector with maximal absolute value. It's also called the max-norm and sup-norm (for the infinite dimensional generalization, e.g., where the vector becomes a real-valued function of a single real variable).

Reply on news.ycombinator.com