Optimization Online


Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization

Saeed Ghadimi (sghadimi***at***ufl.edu)
Guanghui Lan (glan***at***ise.ufl.edu)
Hongchao Zhang (hozhang***at***math.lsu.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.

Download: [PDF]

Entry Submitted: 08/23/2013
Entry Accepted: 08/23/2013
Entry Last Modified: 08/24/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society