Georgia Institute of Technology College of Sciences

Information-based complexity is an alternative to Turing complexity that is well-suited for understanding a broad class of convex optimization algorithms. The groundbreaking work of Nemirovski and Yudin provided the basis of the theory, establishing tight lower bounds on the running time of first-order methods in a number of settings. There has been a recent interest on these classical techniques, because of exciting new applications on Machine Learning, Signal Processing, Stochastic Programming, among others. In this talk, we will introduce the rudiments of the theory, some examples, and open problems. Based on joint work with Gábor Braun and Sebastian Pokutta.