4 ms·
+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
by atq2119 5y ago
+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.
- p1esk 5y agoIntuitive way?
- atq2119 5y agoYes. 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.
- axiosgunnar 5y agoWhat is "l_\infty"?
- eigenket 5y agoA 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_dimensions https://en.wikipedia.org/wiki/Lp_space#The_p-norm_in_finite_...
- dandellion 5y agoIt's Latetx syntax, doesn't work in hn, but would be this: http://www.sciweavers.org/tex2img.php?eq=l_%5Cinfty&bc=White&fc=Black&im=jpg&fs=12&ff=arev&edit=0 http://www.sciweavers.org/tex2img.php?eq=l_%5Cinfty&bc=White...
- ponow 5y agoThat'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).
- TimonKnigge 5y agoMultiplicative 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 http://timonknigge.com/univ/msc-thesis.pdf