Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization
Saeed Ghadimi (sghadimiufl.edu)
Abstract: This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are taken at each iteration depending on the total budget of stochastic samples allowed. The RSPG algorithm also employs a general distance function to allow taking advantage of the geometry of the feasible region. Complexity of this algorithm is established in a unified setting, which shows nearly optimal complexity of the algorithm for convex stochastic programming. A post-optimization phase is also proposed to significantly reduce the variance of the solutions returned by the algorithm. In addition, based on the RSPG algorithm, a stochastic gradient free algorithm, which only uses the stochastic zeroth-order information, has been also discussed. Some preliminary numerical results are also provided.
Keywords: constrained stochastic programming, mini-batch of samples, stochastic approximation, nonconvex optimization, stochastic programming, first-order method, zeroth-order method
Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )
Category 2: Convex and Nonsmooth Optimization
Citation: Technical report, Department of Industrial and Systems Engineering, University of Florida, August 23, 2013.
Entry Submitted: 08/23/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|