Towards Understanding First Order Algorithms for Nonconvex Optimization in Machine Learning

Presented on February 11, 2019 at 11:00 a.m. as part of the ARC12 Distinguished Lecture in the Klaus Advanced Computing Building, Room 1116.Tuo Zhao is an assistant professor in the H. Milton Stewart School of Industrial and Systems Engineering and the school of Computational Science and Engineering at Georgia Tech. His current research focuses on developing a new generation of optimization algorithms with statistical and computational guarantees, as well as user-friendly open source software for machine learning and scientific computing.Runtime: 25:25 minutesStochastic Gradient Descent-type (SGD) algorithms have been widely applied to many non-convex optimization problems in machine learning, e.g., training deep neural networks, variational Bayesian inference and collaborative filtering. Due to current technical limit, however, establishing convergence properties of SGD for these highly complicated practical non-convex problems is generally infeasible. Therefore, we propose to analyze the behavior of the SGD-type algorithms through two simpler but non-trivial non-convex problems – (1) Streaming Principal Component Analysis and (2) Training Non-overlapping Two-layer Convolutional Neural Networks. Specifically, we prove that for both examples, SGD attains a sub-linear rate of convergence to the global optima with high probability. Our theory not only helps us better understand SGD, but also provides new insights on more complicated non-convex optimization problems in machine learning