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

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.

• This seems to depend on whether the problem naturally corresponds to a clean problem that can be approximated in DTIME($n^c$) for some $c$ that is neither too big nor too small, but is not believed to be approximable in DTIME($n^{c-\varepsilon}$). If the task is either quite "easy" from an algorithms perspective, but requires real time guarantees, or is hard but it is not clear how to abstract out the hardness to solve it via off-the-shelf methods, then the model of the underlying process offered by machine learning (and other statistical techniques) might just be the most practical approach. Apr 30, 2017 at 14:54
• I'm skeptical of the view that the approaches are exclusive. Do we have reason to think that it will not be possible to formally define the problems that machine-learning algorithms solve, and build good theoretical models that analyze their performance? This might require better models for data-driven algorithms (which I think of as algorithms with high descriptive complexity), but is that an obstacle that can't be overcome? May 12, 2017 at 17:58