Faster and Non-ergodic O(1/K) Stochastic Alternating Direction Method of Multipliers
We study stochastic convex optimization subjected to linear equality constraints. Traditional Stochastic Alternating Direction Method of Multipliers [1] and its Nesterov's acceleration scheme [2]  can only achieve ergodic O(1/ √ K) convergence rates, where K is the number of iteration. By introducing Variance Reduction (VR) techniques, the convergence rates improve to ergodic O(1/K) [3,4]. In this paper, we propose a new stochastic ADMM which elaborately integrates Nesterov's extrapolation and VR techniques. With Nesterov's extrapolation, our algorithm can achieve a non-ergodic O(1/K) convergence rate which is optimal for separable linearly constrained non-smooth convex problems, while the convergence rates of VR based ADMM methods are actually tight O(1/ √ K) in non-ergodic sense. To the best of our knowledge, this is the first work that achieves a truly accelerated, stochastic convergence rate for constrained convex problems. The experimental results demonstrate that our algorithm is faster than the existing state-of-the-art stochastic ADMM methods.
The paper considers the acceleration of stochastic ADMM. The paper basically combines existing techniques like Nesterov's acceleration technique, and increasing penalty parameter and variance reduction technique. The clearness and readability of the paper needs to be improved. The algorithm is designed for purpose of the theoretical bounds but not for a practically faster algorithm. Overall, the paper needs to be improved. 
1. In the abstract and introduction, the paper does not clearly  point out the result is based on the average of the last m iterations when state non-ergodic convergence rate. The paper also does not point out the use of increasing penalty parameter which is an important trick to establish the theoretical result. 
2. Algorithm 2 looks like a warm start algorithm by increasing the penalty parameter (viz. step size). For a warm start algorithm, the theoretical result is expected for the average of the last loop iterates and outer-loop iterates.
3.  If the theoretical result could be established without increasing penalty parameter, it is desirable. Trading penalty parameter (speed) for theoretical bound is not a significant contribution.