Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization
复制标题
DOI：
10.1137/130936361
复制
发表时间：
2013-09
期刊：
影响因子：
--
通讯作者：
Cong D. Dang;Guanghui Lan
中科院分区：
文献类型：
--
作者：
Cong D. Dang;Guanghui Lan
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 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 optimization problems. We also introduce 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 seem to be new for block coordinate descent methods for deterministic optimization.
