Bregman Alternating Direction Method of Multipliers
The mirror descent algorithm (MDA) generalizes gradient descent by using a Bregman divergence to replace squared Euclidean distance. In this paper, we similarly generalize the alternating direction method of multipliers (ADMM) to Bregman ADMM (BADMM), which allows the choice of different Bregman divergences to exploit the structure of problems. BADMM provides a unified framework for ADMM and its variants, including generalized ADMM, inexact ADMM and Bethe ADMM. We establish the global convergence and the O(1/T ) iteration complexity for BADMM. In some cases, BADMM can be faster than ADMM by a factor of O(n/ ln n) where n is the dimensionality. In solving the linear program of mass transportation problem, BADMM leads to massive parallelism and can easily run on GPU. BADMM is several times faster than highly optimized commercial software Gurobi.
The paper under review considers a generalization of the ADMM algorithm, named BADMM, where the quadratic penalty term is replaced by some Bregman divergence terms. Various convergence results (on the iterates, and on the objective values in an ergodic sense) are given. Moreover, the performance of BADMM is evaluated on a high dimensional linear program coming from a mass transportation problem. Promising results are obtained from an empirical point of view. The problem faced in the paper is interesting and deserves further investigation. The proof of convergence relies on different tools with respect to the ones tipically used for the ADMM algorithm. Nevertheless, I have one main concern about the proof of the main results. It seems to me that the optimality conditions stated in (29) for the lagrangean function of (1) refer to the unconstrained case (i.e. X=R^{n1} and Z=R^{n2}) (and indeed the normal cones of the two sets do not appear in the formulation). The same mistake is made also in equations (30)-(31), when the optimality conditions corresponding to (3) and (4) are derived. Then, in Theorem 1, the iterates are shown to converge to a point (x*,z*,y*) satisfying (29). Therefore, it seems to me that the proof of convergence given in this paper holds only for the unconstrained case. Convergence of the algorithm for the examples with explicit constraints given in the paper is not in principle proved. The organization of the paper could be improved. In particular, I think that the informal presentation at the beginning of pag 4 is hard to follow. FOr instance the definition of h as "the problematic term which need to be linearized" is not completely clear to me (maybe exampe 1 could be anticipated to guide the reader).Minor comments: 1) X and Z should be closed (otherwise the projection could be not well-defined)2)p.3, line 111: "since \phi is convex" should be replaced by "since \phi is strictly convex"3) p. 4: according to the definition of Bregman divergence given at the beginning of the section, the method described here works only if $\varphi_x$ is continuously differentiable and strictly convex (and not only convex as stated after eq. (15))4) p.6, line 311: I don't understand what $\tau=O(\rho)$ means here. Since in the previous result $\tau$ is a constant multiplied by \rho this is already satisfied.5) p. 8 Figure 1 (c) : I don't clearly see here that BADMM is faster here.  The authors in their reply stated that the constraints can be explicitly added and the proofs work also in this case. I suggest to add them to fix the error.