We study regularized stochastic convex optimization subject to linear equality constraints. This class of problems was recently also studied by Ouyang et al. (2013) and Suzuki (2013); both introduced similar stochastic alternating direction method of multipliers (SADMM) algorithms. However, the analysis of both papers led to suboptimal convergence rates. This paper presents two new SADMM methods: (i) the first attains the minimax optimal rate of O(1/k) for nonsmooth strongly-convex stochastic problems; while (ii) the second progresses towards an optimalrate by exhibiting an O(1/k2) rate for the smooth part. We present several experiments with our new methods; the results indicate improved performance over competing ADMM methods.
['Samaneh Azadi', 'Suvrit Sra']
Towards an optimal stochastic alternating direction method of multipliers