SIAM Journal on Optimization · 2013 · 1.1K citations · 24 references
Natural SciencesComputer ScienceAlgorithmsOptimizationStochastic ProcessesApproximation AlgorithmsConvex OptimizationNonlinear ProgrammingSimulation-based OptimizationStochastic OptimizationStochastic ProgrammingOptimization-based SimulationRandomized Approximation AlgorithmsSimulation-based Stochastic OptimizationStationary Point AnalysisStochastic ApproximationStochastic Gradient DescentStochastic Nonlinear Programming
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.
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.
24
A Stochastic Approximation Method
Herbert Robbins, Sutton Monro · The Annals of Mathematical Statistics · 1951 · 9.6K citations · Full text
Online dictionary learning for sparse coding
Julien Mairal, Francis Bach, Jean Ponce et al. · 2009 · 2.1K citations · Full text
Robust Stochastic Approximation Approach to Stochastic Programming
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan et al. · SIAM Journal on Optimization · 2009 · 2.1K citations