  We study the Bregman Augmented Lagrangian method (BALM) for solving convex
problems with linear constraints. For classical Augmented Lagrangian method,
the convergence rate and its relation with the proximal point method is
well-understood. However, the convergence rate for BALM has not yet been
thoroughly studied in the literature. In this paper, we analyze the convergence
rates of BALM in terms of the primal objective as well as the feasibility
violation. We also develop, for the first time, an accelerated Bregman proximal
point method, that improves the convergence rate from
$O(1/\sum_{k=0}^{T-1}\eta_k)$ to $O(1/(\sum_{k=0}^{T-1}\sqrt{\eta_k})^2)$,
where $\{\eta_k\}_{k=0}^{T-1}$ is the sequence of proximal parameters. When
applied to the dual of linearly constrained convex programs, this leads to the
construction of an accelerated BALM, that achieves the improved rates for both
primal and dual convergences.
