Theory vs Practice, Take 2

Suresh Venkatasubramanian has an entertaining post on justifying theoretical results with experiments and, in particular, how this can be quite a pain for theory-oriented researchers:

So you're looking at practical ramifications of some nice theory result, or you're trying to apply formal algorithmic tools to some application problem. If you're lucky, the problem doesn't have an existing base of heuristics to compare against, and so even a straight-up implementation of your ideas is a reasonable contribution.

Of course, you're rarely this lucky, and there's usually some mish-mash of heuristics to compare against. Some of them might be head-scratchingly weird, in the "why on earth should this work" category, and some are possibly more principled. At any rate, you go and implement your idea, and you suddenly realize to your horror that worst-case bounds don't mean s*** when your principled method is ten times slower than the crazy heuristics. So now what ?

It's a nice post for anyone who has done work on "both sides of the aisle" and is definitely worth a read. He goes on to discuss how theoretically-inclined researchers are not trained for experimental work, which is an interesting point. (There's also a link to a nice post by Michael Mitzenmacher)

At a conference like NIPS, where you get a mix of submissions on both theory and applications, you see a common phenomenon: clearly-theoretical papers with a mildly-conspicuous experimental section, and clearly-experimental papers with one or two somewhat awkward theoretical results. The authors' strategy is essentially the same in both cases: this makes the paper "reviewer-proof", since you never know which "type" or researcher will be judging it.

Having spoken to several researchers on both sides, it's apparent that there's pretty strong distrust in each direction. The theoreticians, especially ones who've done a bit of experimental work (and tried to reproduce results e.g.), believe that performance comparisons are so easily manipulated by "fudging" -- tuning your parameters better than your competitor methods, choosing the right datasets, choosing the correct plots, etc. -- that they can't be trusted. On the other hand, experimentalists believe that most theorems are either (a) trivial once you look at what the algorithm is doing or (b) have been endowed with enough assumptions to make the result useless.

Suresh argues that, regarding experimental validation, theoreticians don't "get the right kind of training to do it well", but I would take this even further: theoretically minded folks don't get the right kind of training to even appreciate experimental results or to know how to interpret and judge them. And vice-versa for experimentalists. One occasionally finds crossovers, but I think this is somewhat rare.

In the end, I don't see this as a bad thing. The fact that mathematicians and empiricists can attend the same conferences and have useful discussions about research problems is great. But there's no reason we ought to expect them to do each other's job.