Robins-Monro Augmented Lagrangian Method for Stochastic Convex Optimization

Abstract

In this paper, we propose a Robbins-Monro augmented Lagrangian method (RMALM) to solve a class of constrained stochastic convex optimization, which can be regarded as a hybrid of the Robbins-Monro type stochastic approximation method and the augmented Lagrangian method of convex optimizations. Under mild conditions, we show that the proposed algorithm exhibits a linear convergence rate. Moreover, instead of verifying a computationally intractable stopping criteria, we show that the RMALM with the increasing subproblem iteration number has a global complexity $\mathcal{O}(1/{\epsilon }^{1+q})$ for the $\epsilon$-solution (i.e., $\mathbb{E}\left(\Vert x^k-x^{\ast }{\Vert }^2\right)<\epsilon$), where $q$ is any positive number. Numerical results on synthetic and real data demonstrate that the proposed algorithm outperforms the existing algorithms.