ADMM without a Fixed Penalty Parameter: Faster Convergence with New Adaptive Penalization
Alternating direction method of multipliers (ADMM) has received tremendous interest for solving numerous problems in machine learning, statistics and signal processing. However, it is known that the performance of ADMM and many of its variants is very sensitive to the penalty parameter of a quadratic penalty applied to the equality constraints. Although several approaches have been proposed for dynamically changing this parameter during the course of optimization, they do not yield theoretical improvement in the convergence rate and are not directly applicable to stochastic ADMM. In this paper, we develop a new ADMM and its linearized variant with a new adaptive scheme to update the penalty parameter. Our methods can be applied under both deterministic and stochastic optimization settings for structured non-smooth objective function. The novelty of the proposed scheme lies at that it is adaptive to a local sharpness property of the objective function, which marks the key difference from previous adaptive scheme that adjusts the penalty parameter per-iteration based on certain conditions on iterates. On theoretical side, given the local sharpness characterized by an exponent θ ∈ (0, 1], we show that the proposed ADMM enjoys an improved iteration complexity of O(1/ 1−θ ) 1 in the deterministic setting and an iteration complexity of O(1/ 2(1−θ) ) in the stochastic setting without smoothness and strong convexity assumptions. The complexity in either setting improves that of the standard ADMM which only uses a fixed penalty parameter. On the practical side, we demonstrate that the proposed algorithms converge comparably to, if not much faster than, ADMM with a fine-tuned fixed penalty parameter.
Summary: This paper shows that O(1/eps) iteration complexity of ADMM can be improved to O(1/eps^(1-theta)) where theta is a  parameter that characterizes how sharply the objective function increases with respect to increasing distance to the optimal solution. This improvement is shown under a locally adaptive version of the ADMM where the penalty parameter is increased after every $t$ steps of ADMM. The method is extended to stochastic ADMM whose O(1/eps^2) iteration complexity is shown to similarly improve.  The results are backed by experiments on generalized Lasso problems.
Overall, the paper is well written and makes an important contribution towards improving the analysis of ADMM under adaptive penalty parameters. On a practical note, I would have liked to see some comparisons against other "adaptive-rho" heuristics used the literature (see Boyd's monograph). As background, it may be valuable to some readers to see how the local error bound relates to the KL property, and some examples of "theta" for problems of interest in machine learning. 
There are lots of grammatical errors, typos and odd phrases in the the abstract: "tremendous interests" --> "tremendous interest", "variants are"-->"variants is", "penalty scheme of lies at it is...",  "iterate message"..
The LADMM-AP behavior in plot 1(e) is somewhat strange. Any explanations?
If factor of 2 in LA-ADMM optimal in any sense? In practice ADMM stopping criteria include primal-dual tolerance thresholds. Shouldnt LA-ADMM use those instead of fixed t? 
With regards to linearized ADMM, Eqn 7, please comment on its relationship to Chambelle-Pock updates (https://hal.archives-ouvertes.fr/hal-00490826/document)