If machine learning techniques keep improving, what's the role of algorithmics in the future?

Question

Let's look at the future some 30 years from now. Let's be optimistic and assume that areas related to machine learning keep developing as quickly as what we have seen in the past 10 years. That would be great, but then what would be the role of traditional algorithmics in such a future?

Here by "traditional algorithmics" I refer to the usual process that we follow in TCS: formalise a well-defined computational problem, design algorithms for solving the problem, and prove formal performance guarantees.

Now what are the application areas in which we must use traditional algorithm design and analysis also in the future, and it is highly unlikely that any advances of machine learning will make traditional algorithmics mostly irrelevant?

At first this may seem like a silly question: Of course we will need to be able to do sorting, searching, indexing, etc. also in the future! Of course we will need to be able to do Fourier transforms efficiently, multiply large matrices, find shortest paths, solve linear optimisation problems!

But then again, once you start looking deeper at the applications in which we traditionally use the algorithms that we design, it is not at all clear that the traditional algorithm design and analysis is the right answer to such problems: In applications related to search, usually we are interested in finding something that is a close match for a human being in some vague ill-defined sense (e.g. semantic similarity), not something that is optimal in some mathematical sense (e.g. minimum edit distance). In applications related to route planning, usually we are interested in finding routes that are good based on examples (e.g. other people prefer it), not routes that are optimal in some mathematical sense (e.g. shortest distance or cheapest price). And once you have some vague, ill-defined human component in the picture, it might be the case that we are better off trying to teach the computer to produce good answers based on examples, instead of trying to let a TCS researcher to come up with a formal computational problem that we can tackle by means of traditional algorithm design and analysis.

So what are the application areas (preferably real and direct industrial applications) in which it is absolutely clear that what we have been doing in algorithmics in past is also going to be the right way (and the only possible way) of making progress in the future?

Algorithms that are used as subroutines in machine learning techniques looks like an obvious future-proof candidate, but this heavily depend on the particular machine learning technique that we use, and as we have seen in the past ten years or so, this might rapidly change.

Answer 1

This is a question that has been haunting me recently, so I am glad you asked it.
However, I am less interested in classifying the application areas for which machine learning will dominate the computational approach than I am in the impact on advancement in the field of (traditional) algorithms. What kind of "human-crafted algorithms" research will we still be interested in, in 30 years? Admittedly, this is the harder question to answer in general, because it is the application that determines what quality of result is required.

I think that enumeration algorithms will number among the survivors. There will continue to be a need to test all inputs to a chip, or conduct an exhaustive search. The object-specific attention, the finely-tuned design required to generate each object instance exactly (or at least) once; and the running-time amplification of any wasted effort (there may be an exponential number of instances, as a function of the description of the object) -- these factors make me skeptical that a general-purpose automated learning process can match a clever, purpose-designed solution in this area.

Answer 2

The problem with machine learning solutions is that there's no way to known if they really computed what you wanted.

I'd expect them to take over in all domains where a wrong result isn't catastrophic (i.e. everywhere where we currently use heuristics) or the result can easily be checked (search problems for which you know a solution exists (because checking "there is no solution" could be hard)).

For the remaining domains, I'd expect algorithms to be proved formally (for example using Coq/Gallina) icreasingly often. Hopefully, machine learning will eventually make proving things in such systems as easy as on paper (or even easier). It could even get to the point where humans only write the specification and the algorithm and its correctness proof are found using machine learning. (Note that the algorithm itself doesn't use machine learning, but it and its correctness proofs were found using machine learning)

So we may find ourselves writing only proof assistants, program specifications and machine learning algorithms.