A New Alternating Direction Method for Linear Programming
It is well known that, for a linear program (LP) with constraint matrix A ∈ R m×n , the Alternating Direction Method of Multiplier converges globally and linearly at a rate O(( A 2 F + mn) log(1/ )). However, such a rate is related to the problem dimension and the algorithm exhibits a slow and fluctuating "tail convergence" in practice. In this paper, we propose a new variable splitting method of LP and prove that our method has a convergence rate of O( A 2 log(1/ )). The proof is based on simultaneously estimating the distance from a pair of primal dual iterates to the optimal primal and dual solution set by certain residuals. In practice, we result in a new first-order LP solver that can exploit both the sparsity and the specific structure of matrix A and a significant speedup for important problems such as basis pursuit, inverse covariance matrix estimation, L1 SVM and nonnegative matrix factorization problem compared with the current fastest LP solvers.
This paper develops a novel alternating direction based method for linear programming problems. The paper presents global convergence results, and a linear rate, for their algorithm. As far as I could see, the mathematics appears to be sound, although I did not check thoroughly. Numerical experiments were also presented that support the practical benefits of this new approach; this new algorithm is compared with two other algorithms and the results seem favorable. 
Note that the authors call their algorithm FADMM - my suggestion is that the authors choose a different acronym because (i) there are several other ADMM variants already called FADMM, and (ii) this is an ADMM for LP so it might be more appropriate to call it something like e.g., LPADMM, which is a more descriptive acronym. 
The convergence results and numerical experiments are good, but the thing that I liked most about this paper is that the algorithm seems very practical because the first ADMM subproblem can be solved *inexactly*. This is a very nice feature. The authors also put effort to explain how to solve this first subproblem efficiently from a practical perspective (Section 5), which I felt was an important contribution of the paper.
One of the reasons that I did not give this paper a higher score is that there are a couple of typos in the paper and the descriptions and language could be clearer in places. For example, $n_b$ is used in (1) but is not defined; $n_f$ is used at the end of Section 2.1 but is not defined; the Hessian in Section 2.1 is not correct; throughout the paper the authors use minus signs instead of hyphens (e.g., $n-$dimensional should be $n$-dimensional, $l_1-$regularized should be $l_1$-regularized etc); the bibliography has several typos especially with $ signs missing: [4] should have $\ell_1$-problems; [11] D and R should be capitalized 'Douglas-Rachford'; [16,17] should be capitalized ADMM. All these are minor, but the bar for NIPS is very high and these should be corrected, and the paper should be thoroughly proofread for English mistakes.
Overall I liked this paper.