Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions

Introduction

The Douglas-Rachford splitting (DRS), Peaceman-Rachford splitting (PRS), and alternating direction method of multipliers (ADMM) algorithms are abstract splitting schemes that solve monotone inclusion and convex optimization problems lions1979splitting ; GlowinskiADMM ; gabay1976dual . The DRS and PRS algorithms solve monotone inclusion problems in which the operator is the sum of two (possibly) simpler operators by accessing each operator individually through its resolvent. The ADMM algorithm solves convex optimization problems in which the objective is the sum of two (possibly) simpler functions with variables linked through a linear constraint via an alternating minimization strategy. The variable splitting that occurs in each of these algorithms can give rise to parallel and even distributed implementations of minimization algorithms boyd2011distributed ; shi2013linear ; wei2012distributed , which are particularly suitable for large-scale applications. Since the 1950s, these methods were largely applied to solving partial differential equations (PDEs) and feasibility problems, and only recently has their power been utilized in (PDE and non-PDE related) image processing, statistical and machine learning, compressive sensing, matrix completion, finance, and control goldstein2009split ; boyd2011distributed .

In this paper, we consider two prototype optimization problems: the unconstrained problem

where ${\mathcal{H}}$ is a Hilbert space, and the linearly constrained variant

where ${\mathcal{H}}_{1},{\mathcal{H}}_{2}$, and ${\mathcal{G}}$ are Hilbert spaces, the vector $b$ is an element of ${\mathcal{G}}$, and $A:{\mathcal{H}}_{1}\rightarrow{\mathcal{G}}$ and $B:{\mathcal{H}}_{2}\rightarrow{\mathcal{G}}$ are linear operators. Problem (1) models a variety of tasks in signal recovery where one function corresponds to a data fitting term and the other enforces prior knowledge, such as sparsity, low rank, or smoothness combettes2011proximal . In this paper, we apply relaxed PRS (Algorithm 1) to solve Problem (1). On the other hand, Problem (2) models tasks in machine learning, image processing and distributed optimization. The linear constraint can be used to enforce data fitting, but it can also be used to split variables in a way that gives rise to parallel or distributed optimization algorithms bertsekas1989parallel ; boyd2011distributed . We will apply relaxed ADMM (Algorithm 2) to Problem (2).

This work improves the theoretical understanding of DRS, PRS, and ADMM, as well as their averaged versions. When applied to convex optimization problems, they are known to converge under rather general conditions (bauschke2011convex, , Corollary 27.4). This work seeks to complement the results of davis2014convergence , which are developed under general convexity assumptions, by deriving stronger rates under correspondingly stronger conditions on Problems 1 and 2. One of the main consequences of this work is that the relaxed PRS and ADMM algorithms automatically adapt to the regularity of the problem at hand and achieve convergence rates that improve upon the worst-case rates shown in davis2014convergence for the nonsmooth case. Thus, our results offer an explanation of the great performance of relaxed PRS and ADMM observed in practice, and together with davis2014convergence we now have a comprehensive convergence rate analysis of the relaxed PRS and ADMM algorithms.

In this paper, we derive the convergence rates of the objective error and fixed-point residual (FPR) of relaxed PRS applied to Problem (1); see Table 1. In addition, we derive the convergence rates of the constraint violations and objective errors for relaxed ADMM applied to Problem (2); see Table 2. By appealing to counterexamples in davis2014convergence , several of the rates in Table 1 can be shown to be tight up to constant factors.

The derived rates are useful for determining how many iterations of the relaxed PRS and ADMM algorithms are needed in order to reach a certain accuracy, to decide when to stop an algorithm, and to compare relaxed PRS and ADMM to other algorithms in terms of their worst-case complexities.

2 Notation

In what follows, ${\mathcal{H}},{\mathcal{H}}_{1},{\mathcal{H}}_{2},{\mathcal{G}}$ denote (possibly infinite dimensional) Hilbert spaces. In fixed-point iterations, $(\lambda_{j})_{j\geq 0}\subset{\mathbf{R}}_{+}$ will denote a sequence of relaxation parameters, and

is its $k$th partial sum. To ease notational memory, the reader may assume that $\lambda_{k}\equiv(1/2)$ and $\Lambda_{k}=(k+1)/2$ in the DRS algorithm, or that $\lambda_{k}\equiv 1$ and $\Lambda_{k}=(k+1)$ in the PRS algorithm. Given the sequence $(x^{j})_{j\geq 0}\subset{\mathcal{H}}$, we let $\overline{x}^{k}=({1}/{\Lambda_{k}})\sum_{i=0}^{k}\lambda_{i}x^{i}$ denote its $k$th average with respect to the sequence $(\lambda_{j})_{j\geq 0}$. A convergence result is ergodic if it applies to the sequence $(\overline{x}^{j})_{j\geq 0}$, and nonergodic if it applies to the sequence $(x^{j})_{j\geq 0}$.

Given a closed, proper, and convex function $f:{\mathcal{H}}\rightarrow(-\infty,\infty]$, the set $\partial f(x)$ denotes its subdifferential at $x$ and $\widetilde{\nabla}f(x)\in\partial f(x)$ denotes a subgradient. (This notation was used in (bertsekas2011incremental, , Eq. (1.10)).) The convex conjugate of a closed, proper, and convex function $f$ is $f^{\ast}(y):=\sup_{x\in{\mathcal{H}}}\langle y,x\rangle-f(x).$ Let $I_{{\mathcal{H}}}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ denote the identity map. For any point $x\in{\mathcal{H}}$ and $\gamma\in{\mathbf{R}}_{++}$, we let $\mathbf{prox}_{\gamma f}(x):=\operatorname*{arg\,min}_{y\in{\mathcal{H}}}f(y)+\frac{1}{2\gamma}\|y-x\|^{2}$ and $\mathbf{refl}_{\gamma f}:=2\mathbf{prox}_{\gamma f}-I_{{\mathcal{H}}},$ which are known as the proximal and reflection operators. In addition, we define the PRS operator:

Let $\lambda>0$. For every nonexpansive map $T:{\mathcal{H}}\rightarrow{\mathcal{H}}$ we define the averaged map:

We call the following identity the cosine rule:

3 Assumptions

We list the the assumptions used throughout this papers as follows.

Every function we consider is closed, proper, and convex.

Unless otherwise stated, a function is not necessarily differentiable.

Functions $f,g:{\mathcal{H}}\rightarrow(-\infty,\infty]$ satisfy

Note that this assumption is slightly stronger than the existence of a minimizer because $\operatorname*{zer}(\partial f+\partial g)\neq\operatorname*{zer}(\partial(f+g))$, in general (bauschke2011convex, , Remark 16.7). Nevertheless, this assumption is standard.

Every differentiable function is Fréchet differentiable (bauschke2011convex, , Def. 2.45).

4 The Douglas-Rachford and relaxed Peaceman-Rachford Splitting Algorithms

The results of this paper apply to several operator-splitting algorithms that are all based on the atomic evaluation of the proximal operator. By default, all algorithms start from an arbitrary $z^{0}\in{\mathcal{H}}$. The Douglas-Rachford splitting (DRS) algorithm applied to minimizing $f+g$ is as follows:

which has the equivalent operator-theoretic and subgradient form (Lemma 1):

The special cases $\lambda_{k}\equiv 1/2$ and $\lambda_{k}\equiv 1$ are called the DRS and PRS algorithms, respectively.

5 Practical implications: a comparison with forward-backward splitting

Suppose that the function $g$ in Problem 1 is differentiable and $\nabla g$ is $(1/\beta)$-Lipschitz. Under this smoothness assumption, we can apply FBS algorithm to Problem 1: given $z^{0}\in{\mathcal{H}}$, for all $k\geq 0$, define

To ensure convergence, the stepsize parameter $\gamma$ must be strictly less than $2\beta$.

Now because the gradient operator is often simpler to evaluate than the proximal operator, it may be preferable to use FBS instead of relaxed PRS whenever one of the objectives is differentiable. From our results, we can give two reasons why it may be preferable to use relaxed PRS over FBS:

If the Lipschitz constant of the gradient is known, our analysis indicates how to properly choose stepsizes of relaxed PRS so that both algorithms converge with the same rate (Theorem 3.2). In practice, relaxed PRS is often observed to converge faster than FBS, so our results at least indicate that we can do no worse by using relaxed PRS.

If the Lipschitz constant of the gradient is not known, a line search procedure can be used to guarantee convergence of FBS. If this procedure is more expensive than evaluating the proximal operator, then relaxed PRS should be used. Indeed, Theorem 3.1 shows that the “best iterate” of relaxed PRS will converge with rate $o(1/(k+1))$ regardless of the chosen stepsize, whereas FBS may fail to converge.

Thus, one of our main contributions is the “demystification” of parameter choices, and a partial explanation of the perceived practical advantage of relaxed PRS over FBS.

6 Basic properties of proximal operators

The following properties are included in textbooks such as bauschke2011convex .

Let $f,g:{\mathcal{H}}\rightarrow(-\infty,\infty)$ be closed, proper, and convex functions, and let $T:{\mathcal{H}}\rightarrow{\mathcal{H}}$ be nonexpansive. The the following are true:

Optimality conditions of $\mathbf{prox}$: Let $x\in{\mathcal{H}}$. Then $x^{+}=\mathbf{prox}_{\gamma f}(x)$ if, and only if,

The proximal operator $\mathbf{prox}_{\gamma f}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ is ${1}/{2}$-averaged:

7 Convergence rates of summable sequences

The following facts will be key to deducing Convergence rates in Sections 2 and 3. It originally appeared in (davis2014convergence, , Lemma 3).

Suppose that the nonnegative scalar sequences $(\lambda_{j})_{j\geq 0}$ and $(a_{j})_{j\geq 0}$ satisfy $\sum_{i=0}^{\infty}\lambda_{i}a_{i}<\infty$, and define $\Lambda_{k}$ as in Equation (3).

Monotonicity: If $(a_{j})_{j\geq 0}$ is monotonically nonincreasing, then

Faster rates: Suppose $(b_{j})_{j\geq 0}$ is a nonnegative scalar sequence, that $\sum_{i=0}^{\infty}b_{j}<\infty$, and that $\lambda_{k}a_{k}\leq b_{k}-b_{k+1}$ for all $k\geq 0$. Then the following sum is finite:

No monotonicity: For all $k\geq 0$, define the sequence of “best indices” with respect to $(a_{j})_{j\geq 0}$ as

8 Convergence of the fixed-point residual (FPR)

We will need to following facts in our analysis below:

$(\|z^{j}-z^{\ast}\|)_{j\geq 0}$ is monotonically nonincreasing;

The Fejér-type inequality holds: for all $\lambda\in(0,1]$

If $\underline{\tau}:=\inf_{j\geq 0}\lambda_{k}(1-\lambda_{k})>0$, then the following convergence rates hold:

9 Subgradients

Lemma 1 is key to deducing all of the algebraic relations necessary for relating the objective error to the FPR of the relaxed PRS iteration

Let $z\in{\mathcal{H}}$. Define auxiliary points $x_{g}:=\mathbf{prox}_{\gamma g}(z)$ and $x_{f}:=\mathbf{prox}_{\gamma f}(\mathbf{refl}_{\gamma g}(z))$. Then the identities hold:

10 Fundamental inequalities

Throughout the rest of the paper we will use the following notation: Every function $f$ is $\mu_{f}$-strongly convex and $\widetilde{\nabla}f$ is $(1/\beta_{f})$-Lipschitz. Note that if $\beta_{f}>0$, then $f$ is differentiable and $\widetilde{\nabla}f=\nabla f$. However, we also allow the strong convexity or Lipschitz differentiability constants to vanish, in which case $\mu_{f}=0$ or $\beta_{f}=0$ and $f$ may fail to posses either regularity property. Thus, we always have the inequality (bauschke2011convex, , Theorem 18.15):

Note that there is a slight technicality in that $S_{f}(x,y)$ is only defined where $\partial f(x)\neq\emptyset$. In particular, we only derive bounds on $S_{f}(x,y)$ where this is satisfied.

The following two fundamental inequalities are straightforward modifications of the fundamental inequalities that appeared in (davis2014convergence, , Propositions 4 and 5). When these bounds are iteratively applied, they bound the objective error by the sum of a telescoping sequence and a multiple of the FPR.

In our analysis below, we will use the upper inequality

which is obtained from (15) by letting $x=x^{*}$ and applying $\|z-x^{*}\|^{2}-\|z^{+}-x^{*}\|^{2}=\|z-z^{*}\|^{2}-\|z^{+}-z^{*}\|^{2}+2\langle z-z^{+},z^{*}-x^{*}\rangle.$

Strong convexity

The following theorem will deduce the convergence of $S_{f}(x_{f}^{k},x^{\ast})$ and $S(x_{g}^{k},x^{\ast})$ (see Equation (14)). In particular, if either $f$ or $g$ is strongly convex and the sequence $(\lambda_{j})_{j\geq 0}\subseteq(0,1]$ is bounded away from zero, then $x_{f}^{k}$ and $x_{g}^{k}$ converge strongly to a minimizer of $f+g$. Equation (18) is the main inequality needed to deduce linear convergence of the relaxed PRS algorithm (Section 4), and it will reappear several times.

Suppose that $(z^{j})_{j\geq 0}$ is generated by Algorithm 1. Then for all $k\geq 0$,

Therefore, $8\gamma\sum_{i=0}^{\infty}\lambda_{k}(S_{f}(x_{f}^{i},x^{\ast})+S_{g}(x_{g}^{i},x^{\ast}))\leq\|z^{0}-z^{\ast}\|^{2}$, and

Best iterate convergence: If $\underline{\lambda}:=\inf_{j\geq 0}\lambda_{j}>0$, then $\min_{i=0,\cdots,k}\left\{S_{f}(x_{f}^{i},x^{\ast})\right\}=o\left(1/(k+1)\right)$ and $\min_{i=0,\cdots,k}\left\{S_{g}(x_{g}^{i},x^{\ast})\right\}=o\left(1/(k+1)\right).$

Ergodic convergence: Let $\overline{x}_{f}^{k}=(1/\Lambda_{k})\sum_{i=0}^{k}\lambda_{i}x_{f}^{i}$ and $\overline{x}_{g}^{k}=(1/\Lambda_{k})\sum_{i=0}^{k}\lambda_{i}x_{g}^{i}$. Then

where \overline{S}_{f}(x_{f}^{k},x^{\ast}):=\max\bigg{\{}\frac{\mu_{f}}{2}\left\|\overline{x}_{f}^{k}-x^{\ast}\right\|^{2},~{}\frac{\beta_{f}}{2}\bigg{\|}\frac{1}{\Lambda_{k}}\sum_{i=0}^{k}\widetilde{\nabla}f(x_{f}^{k})-\widetilde{\nabla}f(x^{\ast})\bigg{\|}^{2}\bigg{\}} and $\overline{S}_{g}(x_{g}^{k},x^{\ast})$ is similarly defined.

Nonergodic convergence: If $\underline{\tau}=\inf_{j\geq 0}\lambda_{j}(1-\lambda_{j})>0$, then $S_{f}(x_{f}^{k},x^{\ast})+S_{g}(x_{g}^{k},x^{\ast})=o\left(1/\sqrt{k+1}\right).$

By assumption, the relaxation parameters satisfy $\lambda_{k}\leq 1$. Therefore, Equation (18) is a consequence of the following inequalities:

Note that the sum of Equation (19) over all $k$ is indeed bounded by $\|z^{0}-z^{\ast}\|^{2}$. Thus, Part 1 follows from Fact 1.1, and Part 2 follows from Jensen’s inequality applied to $\|\cdot\|^{2}.$

The little-$o$ convergence rate follows because $S_{f}(x_{f}^{k},x^{\ast})+S_{g}(x_{g}^{k},x^{\ast})$ is bounded by a multiple of the square root of the FPR. ∎

It is not clear whether the “best iterate” convergence results of Theorem 2.1 can be improved to a convergence rate for the entire sequence because the values $S_{f}(x_{f}^{k},x)$ and $S_{g}(x_{g}^{k},x)$ are not necessarily monotonic.

Lipschitz derivatives

In this section, we study the convergence rate of relaxed PRS under the following assumption.

The gradient of at least one of the functions $f$ and $g$ is Lipschitz.

Throughout this section, Fact 1.1 will be used repeatedly to deduce the convergence rates of summable sequences. In general, because we can only deduce the summability and not the monotonicity of the objective errors in Problem 1, we can only show that the smallest objective error after $k$ iterations is of order $o(1/(k+1))$. If $\lambda_{k}\equiv 1/2$, the implicit stepsize parameter $\gamma$ is small enough, and the gradient of $g$ is $(1/\beta)$-Lipschitz, we show that a sequence that dominates the objective error is monotonic and summable, and deduce a convergence rate for the entire sequence.

The next proposition bounds the objective error by a summable sequence. See Appendix A for a proof.

Proposition 4 shows that the the objective error is summable whenever $f$ or $g$ is Lipschitz and $(\lambda_{j})_{j\geq 0}$ is chosen properly. A direct application of Fact 1.1 yields a convergence rate for the objective error. Depending on the choice of $\gamma$ and $(\lambda_{j})_{j\geq 0}$, we can achieve several different rates. In the following Theorem we only analyze a few such choices.

Therefore, the proof follows from Part 3 of Lemma 1.1 applied to the summable upper bound in Proposition 4, which bounds the objective error. Note that under different choices of $(\lambda_{j})_{j\geq 0}$ and $\gamma$, we get the bounds:

This result should be compared with the known convergence properties of the FBS algorithm, which has order $o(1/(k+1))$ for a bounded $\gamma$, but may even fail to converge if $\gamma$ is too large. See Section 1.5 for more on the distinction between FBS and relaxed PRS.

2 Constant relaxation and better rates

In this section, we study the convergence rate of DRS under the assumption

The function $g$ is differentiable on ${\mathcal{H}}$, the gradient $\nabla g$ is $({1}/{\beta})$-Lipschitz, and the sequence of relaxation parameters $(\lambda_{j})_{j\geq 0}$ is constant and equal to ${1}/{2}$.

With these assumptions, we will show that for a special choice of $\theta^{\ast}$ (Lemma 3) and for $\gamma$ small enough, the following sequence is monotonic and summable (Propositions 14 and 16):

We then use Fact 1.1 to deduce $f(x_{f}^{j})+g(x_{f}^{j})-f(x)-g(x)=o(1/(k+1))$.

There are several other simpler monotonic and summable sequences that dominate the objective error. For example, if we choose $\theta^{\ast}=1$, we can drop the last term in Equation (20), but we can no longer use this sequence to help deduce the convergence rate of the FPR in Theorem 3.3. Thus, we choose to analyze the slightly complicated sequence in Equation (20) in order to provide a unified analysis for all results in this section.

We are now ready to deduce the objective error convergence rate for the DRS algorithm when $\nabla g$ is Lipschitz. Our bounds show that

Additionally, we show that the convergence rate of the best iterate has essentially the same constant for a large range of $\gamma$. When $\gamma$ is large, the best iterate still enjoys the convergence rate $o(1/(k+1))$, albeit with a larger constant (Theorem 3.1). The rates we derive are the best possible for this algorithm, as shown by (davis2014convergence, , Theorem 12).

Because each step of the relaxed PRS algorithm is generated by a proximal operator, it may seem strange that the choice of stepsize $\gamma$ affects the convergence rate of relaxed PRS. This is certainly not the case for the proximal point algorithm, which achieves an $o(1/(k+1))$ convergence rate by Fact 1.1. A possible explanation is that the reflection operator of a differentiable function is the composition of averaged operators

Let $\rho\approx 2.2056$ be the positive real root of $x^{3}-2x^{2}-1$. Then

and $\min_{i=0,\cdots,k}\{f(x_{f}^{i})+g(x_{f}^{i})-f(x^{\ast})-g(x^{\ast})\}=o\left(1/(k+1)\right).$ Furthermore, if $\kappa$ ($\approx 1.24698$) is the positive root of $x^{3}+x^{2}-2x-1$, and $\gamma<\kappa\beta$, then

where the last line follows from the bound $-\|x_{g}^{k}-x_{g}^{k+1}\|^{2}\leq-\beta^{2}\|\nabla g(x_{g}^{k})-\nabla g(x_{g}^{k+1})\|^{2}.$ Note that ${\gamma^{3}}/{\beta}-2\gamma\beta-\beta^{2}\leq 0$ if, and only if, $\gamma\leq\rho\beta$ where $\rho$ is the positive root of $x^{3}-2x^{2}-1$. Therefore, the result follows by summing Equation (21) and applying Fact 1.1.

If $\gamma\leq\kappa\beta$, then $({\gamma^{3}}/{\beta}-2\gamma\beta+\theta^{\ast}\gamma^{2})\leq 0$ and $(1-\theta^{\ast})\gamma^{2}/\beta^{2}\leq 1$. Therefore, Equation (B.71) shows that the sequence

is monotonic. In addition, Equation (B.76) shows the sum of this sequence is bounded by $\|x_{g}^{0}-x^{\ast}\|^{2}$. Therefore, the result follows by Fact 1.1. ∎

It was recently shown that the FPR convergence rate for the FBS algorithm is $o(1/(k+1)^{2}))$ (davis2014convergence, , Theorem 3). We complement this result by showing the same is true for DRS whenever $\gamma$ is small enough. This rate is optimal by (davis2014convergence, , Theorem 12).

Suppose that $\gamma<\kappa\beta$ where $\kappa$ ($\approx 1.24698$) is the positive root of $x^{3}+x^{2}-2x-1$. Then for all $k\geq 1$, we have

let $a_{k-1}=(\eta/(1+\gamma/\beta)^{2})\|z^{k+1}-z^{k}\|^{2}$, and let

Because $z^{k}=x_{g}^{k}+\gamma\nabla g(x_{g}^{k})$ and and $\nabla g$ is $(1/\beta)$-Lipschitz, we get

Therefore, Equation (B.71) shows that for all $k\geq 1$,

Fact 1.1 applied to the sequences $(a_{j})_{j\geq 0}$ and $(b_{j})_{j\geq 0}$ with weighting parameters $\lambda_{k}\equiv 1$, (not to be confused with the constant relaxation parameter of the relaxed PRS algorithm), yields

(davis2014convergence, , Part 2 of Theorem 1) shows that $(a_{j})_{j\geq 0}$ is monotonic. Therefore, the result follows from Fact 1.1. ∎

Note that the FBS algorithm achieves $o(1/(k+1))$ objective error rate and $o(1/(k+1)^{2})$ FPR rate as long as $\gamma<2\beta$ (davis2014convergence, , Theorem 3). For the DRS algorithm, our analysis only covers the smaller range $\gamma\leq\kappa\beta$. It is an open question whether $\kappa$ can be improved for the DRS algorithm.

Linear convergence

In this section, we study the convergence rate of relaxed PRS under the assumption

The gradient of at least one of the functions $f$ and $g$ is Lipschitz, and at least one of the functions $f$ and $g$ is strongly convex. In symbols: $(\mu_{f}+\mu_{g})(\beta_{f}+\beta_{g})>0$.

Linear convergence of relaxed PRS is expected whenever Assumption 6 is true. In addition, by the strong convexity of $f+g$, the minimizer of Problem (1) is unique.

The following proposition lists some consequences of linear convergence of the relaxed PRS sequence $(z^{j})_{j\geq 0}$.

Let $(C_{j})_{j\geq 0}\subseteq$ be a positive scalar sequence, and suppose that for all $k\geq 0$,

The bounds for $x_{g}^{k}$ and $x_{f}^{k}$ follow because $\|x_{g}^{k}-x^{\ast}\|^{2}+\gamma^{2}\|\nabla g(x_{g}^{k})-\nabla g(x^{\ast})\|^{2}\leq\|z^{k}-z^{\ast}\|^{2},$ and $\|x_{f}^{k}-x^{\ast}\|^{2}+\gamma^{2}\|\widetilde{\nabla}f(x_{f}^{k})-\widetilde{\nabla}f(x^{\ast})\|^{2}\leq\|\mathbf{refl}_{\gamma g}(z^{k})-\mathbf{refl}_{\gamma g}(z^{\ast})\|^{2}\leq\|z^{k}-z^{\ast}\|^{2}$ by Part 2 of Proposition 1, the nonexpansiveness of $\mathbf{refl}_{\gamma f}$, and Equation (23).

The FPR convergence rate follows from the Fejér-type inequality in Equation (9).

The objective error rate now follows from Equation (24) and the FPR convergence rate. ∎

Whenever $\sup_{j\geq 0}C_{j}<1$, Proposition 5 gives the linear convergence rates of the sequences $(z^{j})_{j\geq 0}$, $(x_{g}^{j})_{j\geq 0}$ and $(x_{f}^{j})_{j\geq 0}$, the subgradient error, the FPR, and the objective error. In the following sections, we will prove Inequality (23) holds under several different regularity assumptions on $f$ and $g$. In each case we leave it to the reader to apply Proposition 5.

Throughout this subsection, at least one of the functions $f$ and $g$ will carry both regularity properties. In symbols: $\mu_{f}\beta_{f}+\mu_{g}\beta_{g}>0$.

The following theorem recovers (lions1979splitting, , Proposition 4) as a special case ($\lambda_{k}\equiv 1/2$).

Theorem 2.1 bounds the distance of $x_{g}^{k}$ to the minimizer

Now we use the identity $z^{k}=x_{g}^{k}+\gamma\nabla g(x_{g}^{k})$ and the Lipschitz continuity of $\nabla g$ to upper bound $\|z^{k}-z^{\ast}\|^{2}$ by a multiple of $\|x_{g}^{k}-x^{\ast}\|^{2}$: $\|z^{k}-z^{\ast}\|^{2}\leq\left(1+\gamma/\beta_{g}\right)^{2}\|x_{g}^{k}-x^{\ast}\|^{2}.$ Rearrange Equation (25) with this bound to complete the proof. ∎

For all $\lambda\in$, the constant $C(\lambda)$ is minimal when $\gamma=\beta_{g}$, i.e. $C(\lambda)=\left(1-\lambda_{k}\mu_{g}\beta_{g}\right)^{{1}/{2}}$. Furthermore, for any choice of $\gamma$, we have the bound $C(1)\leq C(\lambda)$. In particular, for $g=({1}/{2})\|\cdot\|^{2}$, the PRS algorithm converges in one step ($C(1)=0$). Thus, this rate is tight.

The following theorem deduces linear convergence of relaxed PRS whenever $f$ carries both regularity properties. Note that linear convergence of the PRS algorithm ($\lambda_{k}\equiv 1$) does not follow.

Then for all $k\geq 0$, $\|z^{k+1}-z^{\ast}\|\leq C(\lambda_{k})\|z^{k}-z^{\ast}\|.$

Theorem 2.1 bounds the distance of $x_{f}^{k}$ to the minimizer (where we substitute $z^{k+1}-z^{k}=2\lambda_{k}(x_{f}^{k}-x_{g}^{k})$)

Therefore, by the convexity of $\|\cdot\|^{2}$, we can bound the distance of $z^{k}$ to the fixed point $z^{\ast}$

Equations (26) and (27) produce the contraction:

where $C^{\prime}={(\lambda_{k}/2)\min\left\{{4\gamma\mu_{f}}/{\left(1+{\gamma}/{\beta_{f}}\right)^{2}},(1-\lambda_{k})\right\}}.$ ∎

2 Complementary regularity of f𝑓f and g𝑔g

In this subsection, we assume that $f$ and $g$ share the regularity. In symbols: $\mu_{f}\beta_{g}+\mu_{g}\beta_{f}>0$. In this case, linear convergence is expected. To the best of our knowledge, the next result is new.

First assume that $\mu_{f}\beta_{g}>0$. Theorem 2.1 bounds the distance of $x_{f}^{k}$ to the minimizer and the distance of $\nabla g(x_{g}^{k})$ to the optimal gradient (where we substitute $z^{k+1}-z^{k}=2\lambda_{k}(x_{f}^{k}-x_{g}^{k})$):

Thus, from the convexity of $\|\cdot\|^{2}$,

We use Equation (29) to bound the distance of $z^{k}$ to the fixed point $z^{\ast}$ by the left hand side of Equation (28):

where $C^{\prime}={(4\lambda_{k}/3)\min\{\gamma\mu,{\beta}/{\gamma},(1-\lambda_{k})\}}.$ Therefore, we reach the contraction:

If $\mu_{g}\beta_{f}>0$, then the proof is nearly identical, but relies on the identity:

Feasibility Problems with regularity

In this section we consider the feasibility problem:

Throughout this section we assume that $\{C_{f},C_{g}\}$ is boundedly linearly regular:

Suppose that $C_{1},\cdots,C_{m}$ are closed convex subsets of ${\mathcal{H}}$ with nonempty intersection. We say that $\{C_{1},\cdots,C_{m}\}$ is boundedly linearly regular if the following holds: for all $\rho>0$, there exists $\mu_{\rho}>0$ such that for all $x\in B(0,\rho)$, (the open ball centered at the origin with radius $\rho$), we have

where for any subset $C\subseteq{\mathcal{H}}$, the distance function $d_{C}(x):=\inf_{y\in C}\|x-y\|.$ Evidently, if $B(0,\rho)\backslash(C_{1}\cap\cdots\cap C_{m})\neq\emptyset$, then $\mu_{\rho}\geq 1$.

We say that $\{C_{1},\cdots,C_{m}\}$ is linearly regular if it is boundedly linearly regular and $\mu_{\rho}$ does not depend on $\rho$, i.e. $\mu_{\rho}=\mu_{\infty}<\infty$. ∎

Intuitively, (bounded) linear regularity is the following implication:

This property will be key to deducing linear convergence of an application of the relaxed PRS algorithm. See davis2014convergence for the feasibility problem when no regularity is assumed.

There are several ways to model the feasibility problem, e.g. with $f$ and $g$ given by indicator functions, distance functions, or squared distance functions. In this section, we will model the feasibility problem using squared distance functions:

We briefly summarize some properties of squared distance functions.

Let $C$ be a nonempty closed convex subset of ${\mathcal{H}}$. Then the following properties hold:

The function $d_{C}^{2}$ is differentiable, and $\nabla d_{C}^{2}=2(I_{{\mathcal{H}}}-P_{C})$. In addition, $\nabla d_{C}^{2}$ is $2$-Lipschitz.

The proximal identity holds: for all $\gamma>0$,

For a proof see (bauschke2011convex, , Corollary 12.30). ∎

Given $z^{0}\in{\mathcal{H}}$, sequences of implicit stepsize parameters, $(\gamma_{f,j})_{j\geq 0}$, $(\gamma_{g,j})_{j\geq 0}$, and relaxation parameters, $(\lambda_{j})_{j\geq 0}$, we consider the iteration: for all $k\geq 0$, let

If $(\gamma_{f,j})_{j\geq 0},(\gamma_{g,j})_{j\geq 0}\subseteq(0,{1}/{2}]$ and $\lambda_{k}\equiv 1$, then the iteration in Equation (30) is the underrelaxed MAP (see bauschke1996projection for the parallel product space version and see bauschke2013method for the nonconvex case). In particular, Corollary 1 (below) shows that when all implicit stepsize parameters are equal to ${1}/{2}$ and all relaxation parameters are $1$, Equation (30) reduces to the MAP algorithm, where $P_{C_{g}}z^{k}=2x_{g}^{k}-z^{k}$, and $z^{k+1}=P_{C_{f}}P_{C_{g}}z^{k}$. This was already noticed in (luke2008finding, , Proposition 2.5) for the fixed $\gamma$ case.

We now specialize the fundamental inequality in Proposition 2 to the feasibility problem. See Appendix C for a proof.

We are now ready to prove the linear convergence of Algorithm (30) whenever $\{C_{f},C_{g}\}$ is (boundedly) linearly regular. The proof is a consequence of the upper inequality in Proposition 7.

Suppose that $(z^{j})_{j\geq 0}$ is generated by the iteration in Equation (30), and that $C_{f}$ and $C_{g}$ are (boundedly) linearly regular. Let $\rho>0$ and $\mu_{\rho}>0$ be such that $(z^{j})_{j\geq 0}\subseteq B(0,\rho)$ and the inequality

holds for all $x\in B(0,\rho)$. Then $(z^{j})_{j\geq 0}$ satisfies the following relation: for all $k\geq 0$,

In particular, if $\overline{C}=\sup_{j\geq 0}C(\gamma_{f,j},\gamma_{g,j},\lambda_{j},\mu)<1$, then $(z^{j})_{j\geq 0}$ converges linearly to a point in $x\in C_{f}\cap C_{g}$ with rate $\overline{C}$, and

For simplicity, throughout the proof we will drop the iteration index $k$ and denote $z^{+}:=z^{k+1}$ and $z:=z^{k}$, etc. Now recall the identities:

Thus, $x_{g}$ is a point on the line segment connecting $P_{C_{g}}(z)$ and $z$, and $x_{f}$ is a point on the line segment connecting $\mathbf{refl}_{\gamma_{g}g}(z)$ and $P_{C_{f}}(\mathbf{refl}_{\gamma_{g}g}(z))$. Hence, we have the projection identities: $P_{C_{g}}z=P_{C_{g}}x_{g}$ and $P_{C_{f}}(\mathbf{refl}_{\gamma_{g}g}(z))=P_{C_{f}}x_{f}$. We can also compute the distances to $C_{f}$ and $C_{g}$:

We will now bound $d^{2}_{C_{f}}(z)$. Because $x_{g}$ is a point on the line segment connecting $z$ and $P_{C_{g}}(z)$, Equation (35) shows that that $\|z-x_{g}\|=(2\gamma_{g}/(2\gamma_{g}+1))d_{C_{g}}(z)$. Thus, if $c_{1}:=c_{1}(\gamma_{g})={4\gamma_{g}}/({2\gamma_{g}+1})$, we have

Therefore, because $d_{C_{f}}$ is $1$-Lipschitz and by the convexity of $(\cdot)^{2}$,

Now we will simplify the upper bound in Equation (31) by using Equation (35)

Because ${1}/({2\max\{c_{1}^{2},1\}})<1$, we have

Now, recall the bounded linear regularity property: for all $x\in B(0,\rho)$,

Thus, for all $x\in C_{f}\cap C_{g}$, the lower bound in Equation (39) shows that (where we use $(1/\lambda-1)\geq 0$ in Equation (38))

and $x=P_{C_{f}\cap C_{g}}(z)$, then $d_{C_{f}\cap C_{g}}(z)=\|z-x\|$ and $d_{C_{f}\cap C_{g}}(z^{+})\leq\|z^{+}-x\|$. Therefore,

Linear convergence of $(z^{j})_{j\geq 0}$ to a point in $C_{f}\cap C_{g}$ follows from (bauschke2011convex, , Theorem 5.12). The rate follows from Equation (32). ∎

The constant $C(\gamma,\gamma^{\prime},\lambda,\mu)$ has the following form:

For fixed positive $\gamma,\lambda$ and $\mu$, the function $C(\gamma^{\prime},\gamma,\lambda,\mu)$ is minimized when $\gamma^{\prime}={1}/{2}$. Furthermore, it follows that that $C({1}/{2},\gamma,\lambda,\mu)$ is minimized over $\gamma$, at $\gamma={1}/{2}$. Finally, note that $C(\gamma^{\prime},\gamma,\lambda,\mu)$ is monotonically decreasing in $\lambda$ and monotonically increasing in $\mu$. Thus, in view of Corollary 1, we achieve the minimal constant for MAP: $C({1}/{2},{1}/{2},1,\mu)=\left(1-{1}/({2\mu^{2})}\right)^{{1}/{2}}$.

We can use Theorem 5.1 to deduce the linear convergence of MAP and give an explicit rate. In (deutsch2008rate, , Theorem 3.15), the authors show that $\mu$-linear regularity of a finite collection of sets is equivalent to the linear convergence of the method of cyclic projections applied to these sets and, they derive the rate $\left(1-{1}/({8\mu^{2}})\right)^{{1}/{2}}$. Corollary 1 is a special case of one direction of this result but with a better rate. It is not clear if the rate in (deutsch2008rate, , Theorem 3.15) can be improved for the general cyclic projections algorithm. The rate we show in Corollary 1 appears in (bauschke1993convergence, , Corollary 3.14) under the same assumptions.

Let $(z^{j})_{j\geq 0}$ be generated by the iteration in Equation (30) with $\gamma_{f,k}\equiv\gamma_{g,k}\equiv{1}/{2}$ and $\lambda_{k}\equiv 1$. Then for all $k\geq 0$, $z^{k+1}=P_{C_{f}}P_{C_{g}}z^{k}$. Thus, MAP is a special case of PRS. Consequently, under the assumptions of Theorem 5.1, the iterates of MAP converge linearly to a point in the intersection of $C_{f}\cap C_{g}$ with rate $\left(1-{1}/{\mu_{\rho}^{2}}\right)^{{1}/{2}}$.

Notice that $x_{g}^{k}=({1}/{2})z^{k}+({1}/{2})P_{C_{g}}z^{k}$ and $\mathbf{refl}_{({1}/{2})g}(z^{k})=P_{C_{g}}z^{k}$. Similarly, $x_{f}^{k}=({1}/{2})P_{C_{g}}(z^{k})+({1}/{2})P_{C_{f}}P_{C_{g}}z^{k}$ and $z^{k+1}=\mathbf{refl}_{({1}/{2})f}(P_{C_{g}}z^{k})=P_{C_{f}}P_{C_{g}}z^{k}$.

We see that $C({1}/{2},{1}/{2},1,\mu)=\left(1-{1}/({2\mu_{\rho}^{2}})\right)^{{1}/{2}}$. We can strengthen this rate to $\left(1-{1}/{\mu_{\rho}^{2}}\right)^{{1}/{2}}$ by observing that in Equation (37) we have $d_{C_{f}}(z^{k})=0$, and so we can set $c_{1}=0$. The proof then follows the same argument. ∎

If $C_{f}$ and $C_{g}$ are closed subspaces with Friedrichs angle $\cos^{-1}(c_{F})$, (bauschke1999strong, , Corollary 11) shows that $\mu\leq{2}/{\sqrt{1-c_{F}}}$. Therefore, Corollary 1 predicts that iterates of MAP converges with rate no less than $(({3+c_{F}})/{4})^{1/2}$. The actual rate for this problem is $c_{F}^{2}$ aronszajn1950theory ; kayalar1988error . See (bauschke2013rate, , Section 7) for a comparison between DRS and MAP for two subspaces.

With this interpretation of MAP we can examine the inconsistent case, $C_{f}\cap C_{g}=\emptyset$, from a different perspective than the current literature. A part of the following result appeared in (bauschke1994dykstra, , Theorem 4.8). In particular, if $x$ satisfies Equation (41), then $P_{C_{f}}x-P_{C_{g}}x$ is the gap vector of (bauschke1994dykstra, , Theorem 4.8).

Let $(z^{j})_{j\geq 0}$ be generated by MAP, and suppose that $C_{f}\cap C_{g}=\emptyset$. If there exists $x\in{\mathcal{H}}$ such that

then $(z^{j})_{j\geq 0}$ converges weakly to a point in the following set:

with FPR rate $\|z^{k+1}-z^{k}\|^{2}=o\left({1}/({k+1})\right)$. Furthermore, if $x$ satisfies Equation (41), then

In particular, the vector $P_{C_{g}}z^{k}-P_{C_{f}}P_{C_{g}}z^{k}$ strongly converges to the gap vector $P_{C_{g}}x-P_{C_{f}}x$, and

Note that that the condition $x-P_{C_{f}}x=x-P_{C_{g}}x$ is equivalent to $\|P_{C_{g}}x-P_{C_{f}}x\|^{2}=\min_{y\in{\mathcal{H}}}(d_{C_{f}}^{2}(y)+d_{C_{g}}^{2}(y))=\min_{x_{f}\in C_{f},x_{g}\in C_{g}}\|x_{g}-x_{f}\|^{2}$. See (bauschke1994dykstra, , Fact 5.1) for conditions that guarantee the infimum is attained in Corollary 2.

See Appendix D for the extension of the results of this section to finite collections of sets.

From relaxed PRS to ADMM

The relaxed PRS algorithm can be applied to problem (2). To this end we define the Lagrangian:

Section 6 presents Algorithm 1 applied to the Lagrange dual of (2), which reduces to the following algorithm:

If $\lambda_{k}\equiv 1/2$, Algorithm 2 recovers the standard ADMM.

It is well known that ADMM is equivalent to DRS applied to the Lagrange dual of Problem (2) gabay1983chapter . Thus, if we let

then relaxed ADMM is equivalent to relaxed PRS applied to the following problem:

We make two assumptions regarding $d_{f}$ and $d_{g}$.

Functions $f,g:{\mathcal{H}}\rightarrow(-\infty,\infty]$ satisfy

This is a restatement of Assumption 2, which we have used in our analysis of the primal case.

The following differentiation rule holds:

The next proposition shows how the strong convexity and the differentiability of a closed, proper, and convex function transfer to the dual function.

Suppose that $f:{\mathcal{H}}\rightarrow(-\infty,\infty]$ is closed, proper, and convex. Then the following implications hold:

If $f$ is $\mu_{f}$-strongly convex, then $f^{\ast}$ is differentiable and $\nabla f$ is $({1}/{\mu_{f}})$-Lipschitz.

If $f$ is differentiable and $\nabla f$ is $({1}/{\beta})$-Lipschitz, then $f^{\ast}$ is $\beta$-strongly convex.

See (bauschke2011convex, , Theorem 18.15). ∎

With Proposition 8, we can characterize the strong convexity and differentiability of the dual functions in terms of $A,B$ and $f$ and $g$. We first recall that a linear map $L:{\mathcal{G}}\rightarrow{\mathcal{G}}$ is $\alpha$-strongly monotone if for all $x\in{\mathcal{G}}$, the bound $\langle Lx,x\rangle_{\mathcal{G}}\geq\alpha\|x\|_{\mathcal{G}}^{2}$ holds.

If $\nabla f$, (respectively $\nabla g$), is $({1}/{\beta})$-Lipschitz and $AA^{\ast}$ (respectively $BB^{\ast}$) is $\alpha$-strongly monotone, then $d_{f}$ (respectively $d_{g}$) is $\alpha\beta$-strongly convex.

If $f$, (respectively $g$) is $\mu$-strongly convex, then $d_{f}$ (respectively $d_{g}$) is differentiable and $\nabla d_{f}$ (respectively $\nabla d_{g}$) is $({\|A\|^{2}}/{\mu})$ (respectively $({\|B\|^{2}}/{\mu})$)-Lipschitz.

The proof of Proposition 9 is straightforward, so we omit it. We note that $AA^{\ast}$ and $BB^{\ast}$ are always -strongly monotone. Thus, we assume that $AA^{\ast}$ and $BB^{\ast}$ are $\alpha_{A}$ and $\alpha_{B}$-strongly monotone, respectively, while allowing the cases $\alpha_{A}=0$ and $\alpha_{B}=0$. In addition, we use the convention that $\widetilde{\nabla}f$ and $\widetilde{\nabla}g$ are always $({1}/{\beta_{f}})$, and $({1}/{\beta_{g}})$-Lipschitz, respectively, by allowing the cases $\beta_{f}=0$ and $\beta_{g}=0$. We carry the following notation throughout the rest of Section 6:

Thus, $d_{f}$ and $d_{g}$ are $\mu_{d_{f}}$ and $\mu_{d_{g}}$-strongly convex, respectively. Finally, we always assume that $f$ and $g$ are $\mu_{f}$ and $\mu_{g}$-strongly convex, respectively, by allowing $\mu_{f}=0$ and $\mu_{g}=0$. We assume that $\|A\|\|B\|\neq 0$, and denote

If $\beta_{d_{f}}$ is strictly positive, then $d_{f}$ is differentiable and $\nabla d_{f}$ is $(1/\beta_{f})$-Lipschitz. A similar result holds for $d_{g}$.

Now we apply Algorithm 1 to the dual problem in Equation (44). Given $z^{0}\in{\mathcal{H}}$, Lemma 1 shows that we need to compute the following vectors for all $k\geq 0$:

A detailed proof of Proposition 10 recently appeared in (davis2014convergence, , Proposition 11).

Let $z^{0}\in{\mathcal{G}}$, and let $(z^{j})_{j\geq 0}$ be generated by the relaxed PRS algorithm applied to the dual formulation in Equation (44). Choose $w_{d_{g}}^{-1}=z^{0},x^{-1}=0$ and $y^{-1}=0$ and $\lambda_{-1}={1}/{2}$. Then we have the following identities starting from $k=-1$:

Proposition 10 proves that $w_{d_{f}}^{k+1}=w_{d_{g}}^{k+1}-\gamma(Ax^{k+1}+By^{k+1}-b)$. Recall that by Equation (48), $z^{k+1}-z^{k}=2\lambda_{k}(w_{d_{f}}^{k}-w_{d_{g}}^{k})$. Therefore, it follows that

The ADMM algorithm generates $5$ sequences of iterates:

2 Converting dual convergence rates to primal convergence rates

In this section, we use the inequalities deduced in Section 6.1 and the convergence rates proved in previous sections to derive convergence rates for the primal objective error and strong convergence of various quantities that appear in ADMM. In addition, we translate the results of the previous sections and use Proposition 9 to state all theorems in terms of purely primal quantities.

We recall the definition of the two auxiliary terms (Equation (14)):

The following is a direct translation of Theorem 2.1 to the current setting. Note that any of the Lipschitz, strong convexity, and strong monotonicity constants may be zero.

Suppose that $(z^{j})_{j\geq 0}$ is generated by Algorithm 2. Then

Best iterate convergence: If $(\lambda_{j})_{j\geq 0}$ is bounded away from zero, then $\min_{i=0,\cdots,k}\left\{S_{d_{f}}(w_{d_{f}}^{i},w^{\ast})\right\}=o\left(1/(k+1)\right)$ and $\min_{i=0,\cdots,k}\{S_{d_{g}}(w_{d_{g}}^{i},w^{\ast})\}=o\left(1/(k+1)\right).$

Ergodic convergence: Let $\overline{w}_{d_{f}}^{k}=(1/\Lambda_{k})\sum_{i=0}^{k}w_{d_{f}}^{i}$, let $\overline{w}_{d_{g}}^{k}=(1/\Lambda_{k})\sum_{i=0}^{k}\lambda_{i}w_{d_{g}}^{i}$, let $\overline{x}^{k}=(1/\Lambda_{k})\sum_{i=0}^{k}x^{i}$, and let $\overline{y}^{k}=(1/\Lambda_{k})\sum_{i=0}^{k}\lambda_{i}y^{i}$. Then

General convergence: If $\underline{\tau}=\inf_{j\geq 0}\lambda_{j}(1-\lambda_{j})>0$, then $S_{f}(w_{d_{f}}^{k},w^{\ast})+S_{g}(w_{d_{g}}^{k},w^{\ast})=o({1}/{\sqrt{k+1}})$.

The following proposition deduces $o(1/(k+1))$ objective error convergence of standard ADMM whenever $g$ is strongly convex, and $\gamma$ is small enough.

Suppose that $g$ is $\mu_{g}$-strongly convex. Let $\lambda_{k}\equiv 1/2$, and let $\gamma<\kappa\beta=\kappa\mu_{g}/\|B\|^{2}$ (see Theorem 3.2). Then for all $k\geq 1$, we have the constraint violations convergence rate:

Moreover, the primal objective errors satisfy

and $|f(x^{k})+g(y^{k})-f(x^{\ast})-g(y^{\ast})|=o\left(1/k\right).$

The constraint violations rate follows from the identity $z^{k+1}-z^{k}=-\gamma(Ax^{k}+By^{k}-b)$ (Equation (49)) and the FPR convergence rate in Theorem 3.3.

The lower bound follows from the lower fundamental inequality in Proposition 12 and the FPR convergence rate in Theorem 3.3:

Part 1 of Fact 1.2 bounds the norm: $\|z^{k+1}-(z^{\ast}-w^{\ast})\|\leq\|z^{k+1}-z^{\ast}\|+\|w^{\ast}\|\leq\|z^{0}-z^{\ast}\|+\|w^{\ast}\|$. Therefore, the upper bound follows from the upper fundamental inequality in Proposition 11 and the FPR convergence rate in Theorem 3.3:

The little $o$-rate follows because, as the above equations have shown, the objective error is upper and lower bounded by a multiple of the square root of the FPR, which has convergence rate $o(1/k)$ by Theorem 3.3. ∎

It would be nice to prove a convergence rate for the “best iterate” of the sequence of primal objective errors in the style of Theorem 3.1. Unfortunately the fundamental inequalities we developed in Section 6.1 do not immediately imply such a rate.

Now we shift our focus to linear convergence. The following proposition is a direct translation of the main results of Section 4 to the current setting. The interested reader is encouraged to read Appendix E to see how the following rates imply convergence rates for the primal and dual objective, and feasibility errors.

If $\mu_{g}\beta_{g}\alpha_{B}>0$, then $(z^{j})_{j\geq 0}$ converges linearly and

If $\mu_{f}\beta_{f}\alpha_{A}>0$, then $(z^{j})_{j\geq 0}$ converges linearly and

If $\mu_{f}\beta_{g}\alpha_{B}>0$, then $(z^{j})_{j\geq 0}$ converges linearly and

If $\mu_{g}\beta_{f}\alpha_{A}>0$, then $(z^{j})_{j\geq 0}$ converges linearly and

We can apply Proposition 20 to any of the scenarios that appear in Theorem 6.3 and deduce the rate of linear convergence of the objective error and constraint violations. We leave this application to the reader.

Linear convergence of ADMM has been deduced in a variety of scenarios. In denglinear2012 , the authors prove the linear convergence (in finite dimensions) of a generalized form of ADMM, which allows the possibility of adding proximal terms to the alternating minimization steps that appear in Algorithm 2. The four scenarios that appear in (denglinear2012, , Table 1.1)) have some overlap with our results. In the standard version of ADMM, (with no relaxation or extra proximal terms), scenarios 1 and 2 in (denglinear2012, , Table 1.1) are the finite-dimensional analogues of Part 1 of Theorem 4. Scenarios 3 and 4 in (denglinear2012, , Table 1.1) are not covered by our analysis because they require that we treat the structure of $A$ and $B$ more carefully than we have in this section. In addition, Parts 2, 3, and 4 of Theorem 6.3 are not discussed in denglinear2012 . Finally, we note that this paper and denglinear2012 use the opposite update orders in ADMM. They generally lead to different sequences except when at least one of $f$ and $g$ is quadratic yanyin2014 . Therefore, when comparing the results between the two papers, one must switch $f$ and $g$, as well as $A$ and $B$.

Examples

In this section, we apply DRS and ADMM to concrete problems and explicitly bound the associated objective errors and FPR with the convergence rates that we derived in the previous sections.

Suppose that $C_{f}$ and $C_{g}$ are closed convex subsets of ${\mathcal{H}}$ with nonempty intersection. The goal of the feasibility problem is the find a point in the intersection of $C_{f}$ and $C_{g}$. In this section, we present a comparison between MAP and the relaxed PRS algorithm.