"The Power of Non-Convex Relaxations for Stochastic Discrete Optimization"

Many procedures in statistics and artificial intelligence require solving non-convex problems. Historically, the focus has been to convexify the non-convex objectives. In recent years, however, there has been significant progress to optimize non-convex functions directly. This direct approach has led to provably good guarantees for specific problem instances such as latent variable models, non-negative matrix factorization, robust PCA, matrix completion, etc. Unfortunately, there is no free lunch and it is well known that in general finding the global optimum of a non-convex optimization problem is NP-hard. This computational barrier has mainly shifted the goal of non-convex optimization towards two directions: a) finding an approximate local minimum by avoiding saddle points or b) characterizing general conditions under which the underlying non-convex optimization is tractable.

In this talk, I will consider a broad class of non-convex optimization problems that possess special combinatorial structures. More specifically, I will focus on maximization of stochastic continuous submodular functions. Despite the apparent lack of convexity, we will see that first order methods can indeed provide strong approximation guarantees. We then see that by using stochastic continuous relaxation as an interface, we can also provide tight approximation guarantees for maximizing a stochastic submodular set function.
In this talk, I will not assume any particular background on submodularity or optimization and will try to motivate and define all the necessary concepts.

Bio: Amin Karbasi is currently an assistant professor of Electrical Engineering, Computer Science, and Statsitics at Yale University. He has been the recipient of AFOSR 2018 Young Investigator Award, Grainger Award 2017 from National Academy of Engineering for interdisciplinary research, Microsoft Azure research award 2017, DARPA 2016 Young Faculty Award, Simons-Berkeley fellowship 2016, Google Faculty Award 2015, and ETH fellowship 2013. His work has been recognized with a variety of paper awards, including Medical Image Computing and Computer Assisted Interventions Conference (MICCAI) 2017, International Conference on Artificial Intelligence and Statistics (AISTAT) 2015, IEEE ComSoc Data Storage 2013, International Conference on Acoustics, Speech, and Signal Processing (ICASSP) 2011, ACM SIGMETRICS 2010, and IEEE International Symposium on Information Theory (ISIT) 2010 (runner-up). His Ph.D. work received the Patrick Denantes Memorial Prize 2013 from the School of Computer and Communication Sciences at EPFL, Switzerland.