Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming

In this paper, we introduce a new stochastic approximation type algorithm, namely, the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this method possesses a nearly optimal rate of convergence if the problem is convex. We discuss a variant of the algorithm which consists of applying a postoptimization phase to evaluate a short list of solutions generated by several independent runs of the RSG method, and we show that such modification allows us to improve significantly the…

• NS
  National Science Foundation

  Awards: CMMI-1254446, 1254446, N00014-13-1-0036, 1000347, CAREER
• OO
  Office of Naval Research

  Awards: N00014-13-1-0036, N00014
• DO
  Division of Civil, Mechanical and Manufacturing Innovation

  Award: CAREER