Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: a Generic Algorithmic Framework
Saeed Ghadimi (sghadimiufl.edu)
Abstract: In this paper we present a generic algorithmic framework, namely, the accelerated stochastic approximation (AC-SA) algorithm, for solving strongly convex stochastic composite optimization (SCO) problems. While the classical stochastic approximation (SA) algorithms are asymptotically optimal for solving differentiable and strongly convex problems, the AC-SA algorithm, when employed with proper stepsize policies, can achieve optimal or nearly optimal rates of convergence for solving different classes of SCO problems during a given number of iterations. Moreover, we investigate these AC-SA algorithms in more detail, such as, establishing the large-deviation results associated with the convergence rates and introducing efficient validation procedure to check the accuracy of the generated solutions.
Keywords: stochastic approximation, convex optimization, stochastic programming, complexity, optimal method, large deviation
Category 1: Convex and Nonsmooth Optimization (Convex Optimization )
Category 2: Stochastic Programming
Category 3: Applications -- Science and Engineering (Data-Mining )
Citation: Technical Report, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL.
Entry Submitted: 07/03/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|