5 ms·

The Reasonable Effectiveness of the Multiplicative Weights Update Algorithm

106 points by seycombi 10y ago

amelius 10y ago
This is the first time I'm reading pseudocode of an algorithm before it is explained what the algorithm is supposed to do.
- vanderZwan 10y ago
  Then again, I feel you can kind of infer what will happen when the algorithm runs, just by looking at said pseudocode
- aljungberg 10y ago
  I'd like if this were the norm. I found the pseudocode much more readable than the mathematical description of what it was supposed to do. I'm (obviously) biased as a programmer rather than a mathematician but sometimes I think the study of mathematics would benefit tremendously from the same kind of "readability is more important than conciseness" thinking we have in software development. Here's my proposal for a "contributing style" for mathematics: Don't use short cryptic variable names like "wt". Do use informative full variable names like "weight" and "step". Don't use a subscript for something like "step": it's just tiny and hard to read, especially once you start doing math in it. You have a series and you want to talk about the nth element? Use programming like array indexing, "weight[step]". It has the added benefit of being writable in pure ASCII without a math formula editor. Don't omit your binary operators, e.g. "wt(1 + G)". Write it out: "weight[step] * (1 + reward)". You only write your formula once, but it will be read many times. Saving 1 character is not a win in total, especially not when it creates an ambiguous reading (are you using the function wt on 1 + G or are you multiplying? No way to know without resolving wt which can involve backtracking in the text for your reader.) Optimise for reading, not for writing. Don't use sigma for sums. Again readability trumps terseness. Instead of "S" with a little "t from 1 to T" and a formula like "Rt/B" on the right, just write it out: "sum(R[t] / B for t in range(1, T))". Actually it would be neat if there existed a Chrome or Safari extension that converted math notation to pseudo-Python. It wouldn't be able to assign sensible variable names automatically but at least it'd save me so much time and leaning in to stare at tiny subscripts. I might be exceptionally lazy but sometimes when I read a math paper and the dense piles of tiny script formulas begin to pile up my eyes just glaze over even that in theory I understand every component. It's just so much effort to mentally parse it. Like reading sample code in assembly. If readability was improved I'm certain me and others like me would finish reading many more papers and we'd all get a little smarter.
  - j2kun 10y ago
    Problem is you can't efficiently do everything math needs to do if you write out everything like that. Notation is designed for the efficiency of reasoning after you've fully absorbed the ideas being expressed.
    - aljungberg 10y ago
      Right. You could define functions. The function itself is stated in a readable form yet it is concise when later called upon. And just like you desire, this gives the reader a chance to first absorb the idea being expressed by the function (in clear pseudo-code), without making your expressions later overly verbose. The counterargument might be "but then it's harder to break it down again into components when doing algebra". But that's no different from substituting in identities as needed. Substitute in the function body whenever you need to. As long as you don't need to, don't and you both have concise writing and reduced cognitive overhead. Each time the user sees a function they have previously mentally absorbed and understood they don't need to re-read it in detail to confirm it's still the same idea.
      - j2kun 10y ago
        > And just like you desire, this gives the reader a chance to first absorb the idea being expressed by the function (in clear pseudo-code), without making your expressions later overly verbose. This is already the case in math, just with a combination of English and algebraic notation and pictures, whatever is best to convey the idea. Either way, it seems orthogonal to your complaints about notation. I'm saying that pseudocode (as I think you mean it, pythonesque) is not nearly expressive enough to convey the ideas that mathematical notation conveys. It really does help reduce cognitive overload to distinguish two parameters, say one depending on time and one depending on position, by putting one in a subscript. (And that's still at the base of the ladder of abstraction) Sigma notation is one particularly helpful example, far more compact and easier to analyze than a for/while loop. (And, for what it's worth, list comprehensions come from mathematical set-builder notation) I'm not saying math is perfect, but having spent a lot of time doing both math and software, I like to think I understand the reasons for the pitfalls of both fields relatively well.
orasis 10y ago
In the context of bandits, how does this perform compared to Thompson Sampling?
- sdenton4 10y ago
  Seems closely related. The update of the distributions in a Thompson sampler can be thought of as a multiplicative update, considering the old dist as a prior. Those updates become relatively smaller with time though, as the distributions become better known. So TS has a more complicated update rule. Then there's the decision rule. I think of TS as approximating the probability that a given observable is the best, by drawing from the distributions. This effectively just uses a softmax on the weights. Which seems close in spirit, and probably more open to analysis than TS, which often gets complicated under analysis.
- j2kun 10y ago
  For bandit learning MWUA is called EXP3, and it's close to optimal (off from the information-theoretical lower bound by a factor of log n, I believe). Various improvements like EXP4 and EXP4p keep improving this bound. The difference is it's optimizing for a different mathematical model, one which assumes no stochasticity and the rewards can be arbitrary, and adversarially chosen with full knowledge of the algorithm. This "full knowledge" guarantee is what makes MWUA all about "adaptability" (and it's what makes the linear programming example work so spectacularly in the post: the roles are flipped and we as the algorithm designers get to be MWUA's adversaries!) I don't have a direct empirical comparison of EXP3 and Thompson sampling, but I am delighted to say my blog post [1] comes up first when you google "Exp3" [1]: https://jeremykun.com/2013/11/08/adversarial-bandits-and-the-exp3-algorithm/ https://jeremykun.com/2013/11/08/adversarial-bandits-and-the...
hervature 10y ago
> Sanjeev Arora and his coauthors consider it “a basic tool [that should be] taught to all algorithms students together with divide-and-conquer, dynamic programming, and random sampling.” As someone who took Sanjeev's Advanced Algorithms course this past semester, I can confirm that he himself does indeed teach this.

106 points by seycombi 10y ago

This is the first time I'm reading pseudocode of an algorithm before it is explained what the algorithm is supposed to do.

vanderZwan 10y ago
Then again, I feel you can kind of infer what will happen when the algorithm runs, just by looking at said pseudocode
aljungberg 10y ago
I'd like if this were the norm. I found the pseudocode much more readable than the mathematical description of what it was supposed to do. I'm (obviously) biased as a programmer rather than a mathematician but sometimes I think the study of mathematics would benefit tremendously from the same kind of "readability is more important than conciseness" thinking we have in software development. Here's my proposal for a "contributing style" for mathematics: Don't use short cryptic variable names like "wt". Do use informative full variable names like "weight" and "step". Don't use a subscript for something like "step": it's just tiny and hard to read, especially once you start doing math in it. You have a series and you want to talk about the nth element? Use programming like array indexing, "weight[step]". It has the added benefit of being writable in pure ASCII without a math formula editor. Don't omit your binary operators, e.g. "wt(1 + G)". Write it out: "weight[step] * (1 + reward)". You only write your formula once, but it will be read many times. Saving 1 character is not a win in total, especially not when it creates an ambiguous reading (are you using the function wt on 1 + G or are you multiplying? No way to know without resolving wt which can involve backtracking in the text for your reader.) Optimise for reading, not for writing. Don't use sigma for sums. Again readability trumps terseness. Instead of "S" with a little "t from 1 to T" and a formula like "Rt/B" on the right, just write it out: "sum(R[t] / B for t in range(1, T))". Actually it would be neat if there existed a Chrome or Safari extension that converted math notation to pseudo-Python. It wouldn't be able to assign sensible variable names automatically but at least it'd save me so much time and leaning in to stare at tiny subscripts. I might be exceptionally lazy but sometimes when I read a math paper and the dense piles of tiny script formulas begin to pile up my eyes just glaze over even that in theory I understand every component. It's just so much effort to mentally parse it. Like reading sample code in assembly. If readability was improved I'm certain me and others like me would finish reading many more papers and we'd all get a little smarter.
- j2kun 10y ago
  Problem is you can't efficiently do everything math needs to do if you write out everything like that. Notation is designed for the efficiency of reasoning after you've fully absorbed the ideas being expressed.
  - aljungberg 10y ago
    Right. You could define functions. The function itself is stated in a readable form yet it is concise when later called upon. And just like you desire, this gives the reader a chance to first absorb the idea being expressed by the function (in clear pseudo-code), without making your expressions later overly verbose. The counterargument might be "but then it's harder to break it down again into components when doing algebra". But that's no different from substituting in identities as needed. Substitute in the function body whenever you need to. As long as you don't need to, don't and you both have concise writing and reduced cognitive overhead. Each time the user sees a function they have previously mentally absorbed and understood they don't need to re-read it in detail to confirm it's still the same idea.
    - j2kun 10y ago
      > And just like you desire, this gives the reader a chance to first absorb the idea being expressed by the function (in clear pseudo-code), without making your expressions later overly verbose. This is already the case in math, just with a combination of English and algebraic notation and pictures, whatever is best to convey the idea. Either way, it seems orthogonal to your complaints about notation. I'm saying that pseudocode (as I think you mean it, pythonesque) is not nearly expressive enough to convey the ideas that mathematical notation conveys. It really does help reduce cognitive overload to distinguish two parameters, say one depending on time and one depending on position, by putting one in a subscript. (And that's still at the base of the ladder of abstraction) Sigma notation is one particularly helpful example, far more compact and easier to analyze than a for/while loop. (And, for what it's worth, list comprehensions come from mathematical set-builder notation) I'm not saying math is perfect, but having spent a lot of time doing both math and software, I like to think I understand the reasons for the pitfalls of both fields relatively well.

orasis 10y ago

In the context of bandits, how does this perform compared to Thompson Sampling?

sdenton4 10y ago
Seems closely related. The update of the distributions in a Thompson sampler can be thought of as a multiplicative update, considering the old dist as a prior. Those updates become relatively smaller with time though, as the distributions become better known. So TS has a more complicated update rule. Then there's the decision rule. I think of TS as approximating the probability that a given observable is the best, by drawing from the distributions. This effectively just uses a softmax on the weights. Which seems close in spirit, and probably more open to analysis than TS, which often gets complicated under analysis.
j2kun 10y ago
For bandit learning MWUA is called EXP3, and it's close to optimal (off from the information-theoretical lower bound by a factor of log n, I believe). Various improvements like EXP4 and EXP4p keep improving this bound. The difference is it's optimizing for a different mathematical model, one which assumes no stochasticity and the rewards can be arbitrary, and adversarially chosen with full knowledge of the algorithm. This "full knowledge" guarantee is what makes MWUA all about "adaptability" (and it's what makes the linear programming example work so spectacularly in the post: the roles are flipped and we as the algorithm designers get to be MWUA's adversaries!) I don't have a direct empirical comparison of EXP3 and Thompson sampling, but I am delighted to say my blog post [1] comes up first when you google "Exp3" [1]: https://jeremykun.com/2013/11/08/adversarial-bandits-and-the-exp3-algorithm/ https://jeremykun.com/2013/11/08/adversarial-bandits-and-the...

hervature 10y ago

> Sanjeev Arora and his coauthors consider it “a basic tool [that should be] taught to all algorithms students together with divide-and-conquer, dynamic programming, and random sampling.” As someone who took Sanjeev's Advanced Algorithms course this past semester, I can confirm that he himself does indeed teach this.