Gradient Descent: The Mother of All Algorithms?

Presented as part of the Workshop on Algorithms and Randomness on May 14, 2018 at 11:30 a.m. in the Klaus Advanced Computing Building, Room 1116.Aleksander Mądry is an NBX Career Development Associate Professor of Computer Science in the MIT EECS Department. His research aims to identify and tackle key algorithmic challenges in today's computing. His goal is to develop theoretical ideas and tools that, ultimately, will change the way we approach optimization -- in all shapes and forms, both in theory and in practice.Runtime: 56:28 minutesMore than a half of century of research in theoretical computer science brought us a great wealth of advanced algorithmic techniques. These techniques can then be combined in a variety of ways to provide us with sophisticated, often beautifully elegant algorithms. This diversity of methods is truly stimulating and intellectually satisfying. But is it also necessary? In this talk, I will address this question by discussing one of the most, if not the most, fundamental continuous optimization techniques: the gradient descent method. I will briefly describe how this method can be applied, sometime in a quite non-obvious manner, to a number of classic algorithmic tasks, such as the maximum flow problem, the bipartite matching problems, the k-server problem, as well as matrix scaling and balancing. The resulting perspective will provide us with a broad, unifying view on this diverse set of problems. A perspective that was key to making the first in decades progress on each one of these tasks