Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization

Cong D. Dang (congddufl.edu)
Guanghui Lan (glanise.ufl.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.

Download: [PDF]

Entry Submitted: 09/06/2013
Entry Accepted: 09/06/2013
Entry Last Modified: 09/09/2013

Modify/Update this entry