SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
arXiv:1711.05286
Abstract
We consider the structured stochastic convex program requiring the minimization of subject to the constraint . Motivated by the need for decentralized schemes and structure, we propose a stochastic inexact ADMM (SI-ADMM) framework where subproblems are solved inexactly via stochastic approximation schemes. Based on this framework, we prove the following: (i) under suitable assumptions on the associated batch-size of samples utilized at each iteration, the SI-ADMM scheme produces a sequence that converges to the unique solution almost surely; (ii) If the number of gradient steps (or equivalently, the number of sampled gradients) utilized for solving the subproblems in each iteration increases at a geometric rate, the mean-squared error diminishes to zero at a prescribed geometric rate; (iii) The overall iteration complexity in terms of gradient steps (or equivalently samples) is found to be consistent with the canonical level of . Preliminary applications on LASSO and distributed regression suggest that the scheme performs well compared to its competitors.
arXiv comment37 pages, 2 figures, 3 tables
References in corpus (6)
- The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
- Fast Image Recovery Using Variable Splitting and Constrained Optimization
- Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
- Distributed Optimization With Local Domains: Applications in MPC and Network Flows
- Online Alternating Direction Method (longer version)
- Accelerated Variance Reduced Stochastic ADMM