[yummyfajitas]

This is in Notices of the AMS, which is about as mainstream (together with SIAM Review) as mathematical publications get.

Randomization improves algorithms.

This is a contentious claim. Random choices are actually very rarely the best - they are often good enough and versatile, but they are rarely the best.

For example, consider Monte Carlo integration. You get O(N^{-1/2}) convergence. If you use a deterministic set of points explicitly designed to have low discrepancy (aka "Quasi-Monte Carlo"), you can get O(N^{-1 + logarithmic stuff}) convergence.

http://www.chrisstucchio.com/blog/2014/adversarial_bandit_is...

Eliezer Yudkowsky also wrote a great critique of this issue, though I can't find it right now.

[zwegner]

I believe the article you're referring to is: http://lesswrong.com/lw/vp/worse_than_random/

Choice quote: > As a general principle, on any problem for which you know that a particular unrandomized algorithm is unusually stupid - so that a randomized algorithm seems wiser - you should be able to use the same knowledge to produce a superior derandomized algorithm.

An interesting counterexample to this, an example which to me illustrates a very powerful aspect of randomness, is the monte-carlo revolution in computer Go (AI for the ancient Asian board game). For years, computer progress stagnated, as the techniques were mostly focused on encoding human knowledge into code. While most of this human knowledge is generally correct, it introduces significant bias in the way positions are evaluated. The way these rules-of-thumb interact is very hard to predict, and tree search algorithms are quite good at finding positions that are incorrectly evaluated. Because of this, the worst-case behavior of an evaluation function is much more important than it's best-case or average behavior.

Computers started making lots of progress when a new technique was used: rather than try to evaluate positions by a large set of heuristics, they were evaluated by playing random games. Go positions are quite hard to evaluate from simple rules of thumb, and this random game approach gives a much more balanced, long-term view of positions. And most importantly, there is much less bias.

Obviously, an entirely random game, with a uniform distribution over possible moves, is easy to improve upon. But computer go programmers noticed an interesting phenomenon: while certain types of knowledge incorporated into the random move distribution (to make it "more intelligent", as judged by a human) were helpful, others were not (even after taking into account the computational cost of adding the knowledge), and it wasn't always clear why. The same observation about heuristic evaluation noted above applied: having a balanced distribution of move choices, with a reasonable probabilistic lower bound of effectiveness, is more important than making an intelligent choice that is usually correct, but has unpredictable, extreme worst-case performance.

So we see that randomness does have an important property: it avoids the downside of "knowledge" that generally seems correct but can go horribly wrong in unexpected ways.

I don't know of a good writeup of this phenomenon. My understanding of it is mostly assembled from following informal discussions on the computer-go mailing list for several years. In a quick search through my gmail archives I can't find much on the subject, but here's an interesting post about related topics in the computer chess world (that incidentally doesn't talk about randomness, but illustrates well the benefits of avoiding bias): http://www.talkchess.com/forum/viewtopic.php?topic_view=thre...

[yummyfajitas]

I don't know a lot about this Go example, but using a uniform distribution for the evaluation function sounds surprisingly similar to another phenomenon I observed.

Suppose you have a linear evaluation function - h(x) is the value of something. Suppose also the coefficients of h are all positive. Then you'll be right 75% of the time (averaged over all possible h, drawn uniformly from the unit simplex) if you just approximate h=[h1,h2,...] by u=[1,1,...,1].

http://www.chrisstucchio.com/blog/2014/equal_weights.html

So I agree with this claim - uniform distributions are fairly robust to errors. But I don't think that's particularly related to randomness - Monte Carlo is only needed to integrate the distribution.

It's also worth noting that adversarial situations (like Go or Chess) are considerably different than most other cases. In a true adversarial problem, there is no probability distribution - the opponent is omnipotent. The purpose of randomness is simply to reduce the power of the adversary's intelligence - in a completely random world, intelligence is useless.

[zwegner]

That's not too different from a pretty old observation in the chess world: the presence/absence of an evaluation term is more important than the weighting given to it.

> So I agree with this claim - uniform distributions are fairly robust to errors. But I don't think that's particularly related to randomness - Monte Carlo is only needed to integrate the distribution.

Ah, that's an interesting distinction, thanks. I'll have to think about this some more. But given a situation where exact integration is intractable (like chess or Go), I'm not too sure what the difference really is, because it is those cases (on first thought) where the uniform distribution is useful--if you can see to the end, you don't need to care about bias, right? I mean, "randomness" in the strictest sense is not really necessary; all these programs I speak of used deterministic pseudorandom generators of course. It's really just about ensuring lack of bias given finite sampling. I'm happy to hear your take on it though--you definitely seem to have a lot more knowledge of math/statistics/etc. than I do.

(That does remind me of another fascinating tidbit from the Go world: programmers noticed that using a low-quality PRNG, like libc's LCG rand(), produced significantly weaker players than more evenly-distributed PRNGs, even though it would seem that playing lots of random games of indeterminate length (with the PRNG called at least once per move) would not correlate at all with the PRNG's distribution.)

The adversarial-or-not issue is also good food for thought. I'm not convinced that it explains much in this case, though, since I believe most of these observations were made by playing computer-computer games with each program using very similar algorithms, or with old hand-tuned programs against the newer Monte-Carlo based programs.

[yummyfajitas]

But given a situation where exact integration is intractable (like chess or Go), I'm not too sure what the difference really is, because it is those cases (on first thought) where the uniform distribution is useful--if you can see to the end, you don't need to care about bias, right?

Put it this way - suppose I can cook up a deterministic quadrature rule, e.g. quasi monte carlo or an asymptotic expansion. I assert that the quasi monte carlo will work just as well as monte carlo, probably better if convergence is faster.

If I'm right, this is a situation of "yay for uniform distributions". If I'm wrong, it's a "yay randomness" situation. It's nice to know which situation you are in - if I'm wrong, there is no point cooking up better deterministic quadrature rules.

Incidentally, LCG is known to be useless for monte carlo due to significant autocorrelation. So it's quite possible that people using LCG are incorrectly estimating their evaluation term.

Also for me, it's nice to know these things just for theoretical purposes and to enhance my understanding.

[wisty]

Yeah, but having some random noise still often helps.