  In this paper, we introduce a new stochastic approximation (SA) type
algorithm, namely the randomized stochastic gradient (RSG) method, for solving
an important class of nonlinear (possibly nonconvex) stochastic programming
(SP) 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
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 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.
