Linear Convergence and Error Bounds are Equivalent for Optimisation Algorithms

Several optimization algorithms, including the Alternating Direction Method of Multipliers (ADMM) and the Douglas-Rachford algorithm (DR), can be formulated as fixed-point iterations (FPI) of an averaged operator. The convergence of these algorithms is typically slow in the worst case, falling within a sublinear regime. We demonstrate that linear convergence of the FPI of averaged operators is equivalent to an error-bound condition on the operator. This implies that if linear convergence is not achieved, the algorithm not only exhibits slow performance but also has a generally weak stopping criterion. Our work encompasses several existing results regarding the linear convergence of ADMM and DR under less stringent assumptions. In particular, we establish bounds on the rate of convergence of the DR/ADMM when applied to linear and quadratic optimization problems.