CAM Colloquium, 2017-02-10 - Damek Davis: A SMART Stochastic Algorithm for Nonconvex Optimization with Applications to Robust Machine Learning

Abstract:    In this talk, we show how to transform any optimization problem that arises from fitting a machine learning model into one that (1) detects and removes contaminated data from the training set while (2) simultaneously fitting the trimmed model on the uncontaminated data that remains. To solve the resulting nonconvex optimization problem, we introduce a fast stochastic gradient algorithm. For datasets of size $n$, our approach requires $O(n^{2/3}/\varepsilon)$ gradient evaluations to reach $\varepsilon$-accuracy and, when a certain error bound holds, the complexity improves to $O(\kappa n^{2/3}\log(1/\varepsilon))$. These rates are $n^{1/3}$ times better than those achieved by typical, full gradient methods.  This talk will assume minimal background in optimization beyond knowledge of the gradient descent algorithm.

Biography:  Damek Davis received his PhD in mathematics from University of California, Los Angeles in 2015. In July 2016 he joined Cornell University's School of Operations Research and Information Engineering as an Assistant Professor. In his research, Damek formulates and solves continuous optimization problems, with a focus on those which arise in machine learning and signal processing. In the past, his research has received several awards including both the NSF graduate (2010) and math postdoctoral fellowships (2015), the Pacific Journal of Mathematics Dissertation Prize (2015), and the INFORMS Optimization Society student paper prize (2014).