Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization
From MaRDI portal
Publication:6265487
Abstract: Block coordinate descent methods and stochastic subgradient methods have been extensively studied in optimization and machine learning. By combining randomized block sampling with stochastic subgradient methods based on dual averaging, we present stochastic block dual averaging (SBDA)---a novel class of block subgradient methods for convex nonsmooth and stochastic optimization. SBDA requires only a block of subgradients and updates blocks of variables and hence has significantly lower iteration cost than traditional subgradient methods. We show that the SBDA-based methods exhibit the optimal convergence rate for convex nonsmooth stochastic optimization. More importantly, we introduce randomized stepsize rules and block sampling schemes that are adaptive to the block structures, which significantly improves the convergence rate w.r.t. the problem parameters. This is in sharp contrast to recent block subgradient methods applied to nonsmooth deterministic or stochastic optimization. For strongly convex objectives, we propose a new averaging scheme to make the regularized dual averaging method optimal, without having to resort to any accelerated schemes.
This page was built for publication: Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6265487)
