Randomized Block Subgradient Methods for Convex Nonsmooth and Stochastic Optimization

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.

References in corpus (7)

• Stochastic Optimization with Importance Sampling
• Efficient Learning with Partially Observed Attributes
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Randomized Block Coordinate Descent for Online and Stochastic Optimization
• Linear Regression with Limited Observation
• Large-scale randomized-coordinate descent methods with non-separable linear constraints
• Attribute Efficient Linear Regression with Data-Dependent Sampling

Cited by in corpus (2)

• Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem
• Accelerated Randomized Coordinate Descent Algorithms for Stochastic Optimization and Online Learning