Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
Cong D. Dang (congddufl.edu)
Abstract: In this paper, we present a new stochastic algorithm, namely the stochastic block mirror descent (SBMD) method for solving large-scale nonsmooth and stochastic optimization problems. The basic idea of this algorithm is to incorporate the block-coordinate decomposition and an incremental block averaging scheme into the classic (stochastic) mirror-descent method, in order to significantly reduce the cost per iteration of the latter algorithm. We establish the rate of convergence of the SBMD method, along with its associated large-deviation results, for solving general nonsmooth and stochastic optimizaiton problems. We also introduce different variants of this method and establish their rate of convergence for solving strongly convex, smooth, and composite optimization problems, as well as certain nonconvex optimization problems. To the best of our knowledge, all these developments related to the SBMD methods are new in the stochastic optimization literature. Moreover, some of our results also seem to be new for block coordinate descent methods for deterministic optimization.
Keywords: Stochastic Optimization, Mirror Descent, Block Coordinate Descent, Nonsmooth Optimization, Stochastic Composite Optimization, Metric Learning
Category 1: Convex and Nonsmooth Optimization
Category 2: Nonlinear Optimization
Citation: Technical report, Department of Industrial and Systems Engineering, University of Florida, September 6, 2013.
Entry Submitted: 09/06/2013
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|