SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs
Lists
Only you see this
Abstract
We consider the structured stochastic convex program requiring the minimization of E <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ξ</sub> [f̅(x, ξ)] + E <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ξ</sub> [g̅(y, ξ)] subject to the constraint Ax + By = b. Motivated by the need for decentralized schemes, we propose a stochastic inexact alternating direction method of multiplier (SI-ADMM) framework where subproblems are solved inexactly via stochastic approximation schemes. we propose a stochastic inexact alternating direction method of multiplier (SI-ADMM) framework where subproblems are solved inexactly via stochastic approximation schemes. Based on this framework, we prove the following: 1) 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; 2) 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; and 3) the overall iteration complexity in terms of gradient steps (or equivalently samples) is found to be consistent with the canonical level of O(1/ε). Preliminary applications on LASSO and distributed regression suggest that the scheme performs well compared to its competitors.
BibTeX
@article{xie2017si,
author = {Yue Xie and Uday V. Shanbhag},
title = {{SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs}},
journal = {IEEE Trans. Automatic Control},
year = {2017},
}Loading related content...