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

Saeed Ghadimi, Guanghui Lan

SIAM Journal on Optimization · 2013 · 1.1K citations · 24 references

Concepts

TL;DR

The paper proposes the randomized stochastic gradient (RSG) method to solve nonlinear, possibly nonconvex, stochastic programming problems. The RSG algorithm is a randomized stochastic gradient method, extended with a post‑optimization phase that evaluates a shortlist of solutions from multiple independent runs, and is specialized to simulation‑based optimization problems with only zeroth‑order stochastic information. The RSG method achieves a provable complexity for finding approximate stationary points, attains a nearly optimal convergence rate in convex settings, and, with the post‑optimization variant, markedly improves its large‑deviation performance.

Abstract

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 large-deviation properties of the algorithm. These methods are then specialized for solving a class of simulation-based optimization problems in which only stochastic zeroth-order information is available.

References

24