Convergence Rates of Stochastic Algorithms in Nonsmooth Nonconvex Optimization

Thu, Nov 14, 2019, 4:30 pm to 5:30 pm
Speaker(s): 
Sponsor(s): 
Electrical Engineering
Center for Statistics and Machine Learning

Abstract:

Stochastic iterative methods lie at the core of large-scale optimization and its modern applications to data science. Though such algorithms are routinely and successfully used in practice on highly irregular problems (e.g. deep neural networks), few performance guarantees are available outside of smooth or convex settings. In this talk, I will describe a framework for designing and analyzing stochastic methods on a large class of nonsmooth and nonconvex problems, with provable efficiency guarantees. The problem class subsumes such important tasks as phase retrieval, robust PCA, and minimization of risk measures, while the methods include stochastic subgradient, Gauss-Newton, and proximal point iterations. The main thread of the proposed framework is appealingly intuitive. I will show that a wide variety of stochastic methods can be interpreted as inexact gradient descent on an implicit smoothing of the problem.

Optimal learning rates and novel sample-complexity guarantees (for various signal and matrix recovery problems) follow quickly from this viewpoint.

Bio:

Dmitriy Drusvyatskiy received his PhD from the Operations Research and Information Engineering department at Cornell University in 2013, followed by a post doctoral appointment in the Combinatorics and Optimization department at Waterloo, 2013-2014. He joined the Mathematics department at University of Washington as an Assistant Professor in 2014, and was promoted to an Associate Professor in 2019.

Dmitriy’s research broadly focuses on designing and analyzing algorithms for large-scale optimization problems, primarily motivated by applications in data science. Dmitriy has received a number of awards, including the Air Force Office of Scientific Research (AFOSR) Young Investigator Program (YIP) Award, NSF CAREER, INFORMS Optimization Society Young Researcher Prize 2019, and finalist citations for the Tucker Prize 2015 and the Young Researcher Best Paper Prize at ICCOPT 2019. Dmitriy is currently a co-PI of the NSF funded Transdisciplinary Research in Principles of Data Science (TRIPODS) institute at University of Washington.