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.
Citation
Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, June, 2008.
Article
View Efficient Methods for Stochastic Composite Optimization