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.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

Leave a Reply

Your email address will not be published. The comment form expects plain text. If you need to format your text, you can use HTML elements such strong, blockquote, cite, code and em. For formatting code as HTML automatically, I recommend

You may subscribe to this blog by email.