Convergence Rates with Inexact Non-expansive Operators

Understand

In this paper, we present a convergence rate analysis for the inexact Krasnosel'skii-Mann iteration built from nonexpansive operators.

• Our results include two main parts: we first establish global pointwise and ergodic iteration-complexity bounds, and then, under a metric subregularity assumption, we establish local linear convergence for the distance of the iterates to the set of fixed points.
• The obtained iteration-complexity result can be applied to analyze the convergence rate of various monotone operator splitting methods in the literature, including the Forward-Backward, the Generalized Forward-Backward, Douglas-Rachford, alternating direction method of multipliers (ADMM) and Primal-Dual splitting methods.
• For these methods, we also develop easily verifiable termination criteria for finding an approximate solution, which can be seen as a generalization of the termination criterion for the classical gradient descent method.