Journal
MATHEMATICAL PROGRAMMING
Volume 133, Issue 1-2, Pages 365-397Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-010-0434-y
Keywords
Stochastic approximation; Convex optimization; Stochastic programming; Complexity; Optimal method; Quadratic penalty method; Large deviation
Categories
Funding
- NSF [CMMI-1000347, CCF-0430644, CCF-0808863]
- ONR [N000140811104, N00014-08-1-0033]
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [1000347] Funding Source: National Science Foundation
Ask authors/readers for more resources
This paper considers an important class of convex programming (CP) problems, namely, the stochastic composite optimization (SCO), whose objective function is given by the summation of general nonsmooth and smooth stochastic components. Since SCO covers non-smooth, smooth and stochastic CP as certain special cases, a valid lower bound on the rate of convergence for solving these problems is known from the classic complexity theory of convex programming. Note however that the optimization algorithms that can achieve this lower bound had never been developed. In this paper, we show that the simple mirror-descent stochastic approximation method exhibits the best-known rate of convergence for solving these problems. Our major contribution is to introduce the accelerated stochastic approximation (AC-SA) algorithm based on Nesterov's optimal method for smooth CP (Nesterov in Doklady AN SSSR 269:543-547, 1983; Nesterov in Math Program 103:127-152, 2005), and show that the AC-SA algorithm can achieve the aforementioned lower bound on the rate of convergence for SCO. To the best of our knowledge, it is also the first universally optimal algorithm in the literature for solving non-smooth, smooth and stochastic CP problems. We illustrate the significant advantages of the AC-SA algorithm over existing methods in the context of solving a special but broad class of stochastic programming problems.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available