In NIPS 2017, Ali Rahimi and Ben Recht won the test of time award for their paper “Random Features for Large-scale Kernel Machines”. Ali delivered the following acceptance speech (see also addendum) in which he said that Machine Learning has become “alchemy” in the sense that it involves more and more “tricks” or “hacks” that work well in practice, but are very poorly understood. (Apparently alchemists were also successful in making many significant practical discoveries.) Similarly, when I teach cryptography I often compare the state of “pre modern” cryptography (before Shannon and Diffie-Hellman) to alchemy.
Yann LeCun was not impressed with the speech, saying that sticking to using methods for which we have theoretical understanding is “akin to looking for your lost car keys under the street light knowing you lost them someplace else.” There is a sense in which LeCun is very right. For example, already in the seminal paper in which Jack Edmonds defined the notion of polynomial time he said that “it would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion.” But I do want to say something in defense of “looking under the streetlight”. When we want to understand the terrain, rather than achieve some practical goal, it can make a lot of sense to start in the simplest regime (e.g. “most visible” or “well lit”) and then expand our understanding (e.g., “shine new lights”). Heck, it may well be that when the super intelligent robots are here, then they would look for their keys by first making observations under the light and then extrapolating to the unlit area.