Does theory helps in algorithmic design?

Olivier Bousquet questions Statistical Learning Theory.

So, I think that the theoretical analysis is mainly a way to popularize an algorithm and to raise its visibility. The effect is then that more people try it out, and streamline it. So in the end, the algorithm may be adopted, but a theoretical analysis rarely justifies the algorithm and never provides guarantees. Hence theory is a way to attract attention to an algorithm. It should also be a way to get new insights for the development of new algorithms, but this happens much less frequently than is claimed!

I’m currently working on a paper where I spent a lot of time fiddling and proving some bounds, as Olivier points out we often do. Of course, not being a pure theory guy, I also run extensive experiments. I cannot help but notice a strong disconnect between the theory and the practice, not only in what I do, but in the papers I cite.

The counter-argument might be: but theory helps design better algorithms. Like Olivier, I don’t buy it.

Ah! I still do theory of course, but let’s not fool ourselves in thinking we are smarter than nature.