Optimization Online


Efficient Methods for Stochastic Composite Optimization

Guanghui Lan(glan***at***isye.gatech.edu)

Abstract: This paper considers an important class of convex programming problems whose objective function $\Psi$ is given by the summation of a smooth and non-smooth component. Further, it is assumed that the only information available for the numerical scheme to solve these problems is the subgradient of $\Psi$ contaminated by stochastic noise. Our contribution mainly consists of the following aspects. Firstly, with a novel analysis, it is demonstrated that the simple robust mirror-descent stochastic approximation method applied to the aforementioned problems exhibits the best known so far rate of convergence guaranteed by a more involved stochastic mirror-prox algorithm. Moreover, by incorporating some ideas of the optimal method for smooth minimization, we propose an accelerated scheme, which can achieve, uniformly in dimension, the theoretically optimal rate of convergence for solving this class of problems. Finally, the significant advantages of the accelerated scheme over the existing algorithms are illustrated in the context of solving a class of stochastic programming problems whose feasible region is a simple compact convex set intersected with an affine manifold.

Keywords: stochastic approximation, convex optimization,stochastic programming, complexity, optimal method

Category 1: Convex and Nonsmooth Optimization

Category 2: Stochastic Programming

Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, June, 2008.

Download: [PDF]

Entry Submitted: 08/05/2008
Entry Accepted: 08/05/2008
Entry Last Modified: 08/05/2008

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 Programming Society