Machine learning and fine-grained complexity

In traditional computational complexity, there is a convention that if a problem has a polynomial time algorithm it is already a simple problem. Obviously, in practice there is a huge difference between an algorithm with running time n^2 and one with running time n^100. This observation gave rise to a more modern approach: fine-grained complexity. The goal of it is to pinpoint the hardness of a problem as precisely as possible.
In this talk, we will cover some basic techniques used in fine-grained complexity and the limitations of these techniques. Then we will show that under widely believed assumptions we already have optimal algorithms for some of the cornerstone problems in Machine learning.