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 Université du Québec (TELUQ).

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax