In spite of its wide applicability in machine learning, simulation-based optimization and financial engineering etc., the study on nonconvex stochastic optimization has been quite limited in the literature. In this talk, we introduce a new stochastic approximation type algorithm, namely the randomized stochastic gradient (RSG) method, and establish its complexity for computing an approximate stationary point of a general nonlinear programming problem. We show that this method possesses a nearly optimal rate of convergence if the problem is convex. We also discuss a variant of the algorithm which consists of applying a post-optimization phase to evaluate a short list of solutions generated by several independent runs of the RSG method, and show that such modification allows us to improve significantly the large-deviation properties of the algorithm. We then specialize these methods for solving a class of simulation-based optimization problems in which only stochastic zeroth-order information is available. We provide showcases to demonstrate the effectiveness of these techniques in machine learning and simulation-based optimization.
Mengshi Lu is a Ph.D. candidate in Industrial Engineering and Operations Research at the University of California, Berkeley, where he is advised by Prof. Max Shen. His research focuses on developing data-driven and robust methods for supply chain management problems under uncertainty to avoid loss from model misspecification and improve upon the status quo. He received his undergraduate degree in Industrial Engineering, a Master’s degree in Management Science and Engineering, both from Tsinghua University in China, and a Master’s degree in Statistics from UC Berkeley. From 2012 to 2013, he was a visiting research associate in the Analytics Lab at Hewlett-Packard Laboratories.