Convergence rate analysis of the forward-Douglas-Rachford splitting scheme

Introduction

Operator-splitting schemes are algorithms for splitting complicated problems arising in PDE, monotone inclusions, optimization, and control into many simpler subproblems. The achieved decomposition can give rise to inherently parallel and, in some cases, distributed algorithms. These characteristics are particularly desirable for large-scale problems that arise in machine learning, finance, control, image processing, and PDE .

In optimization, the Douglas-Rachford splitting (DRS) algorithm minimizes sums of (possibly) nonsmooth functions $f,g:{\mathcal{H}}\rightarrow(-\infty,\infty]$ on a Hilbert space ${\mathcal{H}}$:

During each step of the algorithm, DRS applies the proximal operator, which is the basic subproblem in nonsmooth minimization, to $f$ and $g$ individually rather than to the sum $f+g$. Thus, the key assumption in DRS is that $f$ and $g$ are easy to minimize independently, but the sum $f+g$ is difficult to minimize. We note that many complex objectives arising in machine learning and signal processing are the sum of nonsmooth terms with simple or closed-form proximal operators.

The forward-backward splitting (FBS) algorithm is another technique for solving (1) when $g$ is known to be smooth. In this case, the proximal operator of $g$ is never evaluated. Instead, FBS combines gradient (forward) steps with respect to $g$ and proximal (backward) steps with respect to $f$. FBS is especially useful when the proximal operator of $g$ is complex and its gradient is simple to compute.

Recently, the forward-Douglas-Rachford splitting (FDRS) algorithm was proposed to combine DRS and FBS and extend their applicability (see Algorithm 1). More specifically, let $V\subseteq{\mathcal{H}}$ be a closed vector space and suppose $g$ is smooth. Then FDRS applies to the following constrained problem:

Throughout the course of the algorithm, the proximal operator of $f$, the gradient of $g$, and the projection operator onto $V$ are all employed separately.

The FDRS algorithm can also apply to affinely constrained problems. Indeed, if $V=V_{0}+b$ for a closed vector subspace $V_{0}\subseteq{\mathcal{H}}$ and a vector $b\in{\mathcal{H}}$, then Problem (2) can be reformulated as

For simplicity, we only consider linearly constrained problems.

The FDRS algorithm is a generalization of the generalized forward-backward splitting (GFBS) algorithm , which solves the problem $\operatorname*{minimize}_{x\in{\mathcal{H}}}\sum_{i=1}^{n}f_{i}(x)+g(x)$ where $f_{i}:{\mathcal{H}}\rightarrow(-\infty,\infty]$ are closed, proper, convex and (possibly) nonsmooth. In the GFBS algorithm, the proximal mapping of each function $f_{i}$ is evaluated in parallel. We note that GFBS can be derived as an application of FDRS to the equivalent problem:

In this case, the vector space $V=\{(x,\ldots,x)\in{\mathcal{H}}^{n}\mid x\in{\mathcal{H}}\}$ is the diagonal set of ${\mathcal{H}}^{n}$ and the function $f$ is separable in the components of $(x_{1},\cdots,x_{n})$.

The FDRS algorithm is the only primal operator-splitting method capable of using all structure in Equation (2). In order to achieve good practical performance, the other primal splitting methods require stringent assumptions on $f,g,$ and $V$. Primal DRS cannot use the smooth structure of $g$, so the proximal operator of $g$ must be simple. On the other hand, primal FBS and forward-backward-forward splitting (FBFS) cannot separate the coupled nonsmooth structure of $f$ and $V$, so minimizing $f(x)$ subject to $x\in V$ must be simple. In contrast, FDRS achieves good practical performance if it is simple to minimize $f$, evaluate $\nabla g$, and project onto $V$.

Modern primal-dual splitting methods can also decompose problem (2), but they introduce extra variables and are, thus, less memory efficient. It is unclear whether FDRS will perform better than primal-dual methods when memory is not a concern. However, it is easier to choose algorithm parameters for FDRS and, hence, it can be more convenient to use in practice.

Let $d$ and $m$ be natural numbers. Suppose that $Q\in{\mathbf{R}}^{d\times d}$ is a symmetric positive semi-definite matrix, $c\in{\mathbf{R}}^{d}$ is a vector, $C\subseteq{\mathbf{R}}^{d}$ is a constraint set, $A\in{\mathbf{R}}^{m\times d}$ is a linear map, and $b\in{\mathbf{R}}^{m}$ is a vector. Consider the problem:

Problem (5) arises in the dual form soft-margin kernelized support vector machine classifier in which $C$ is a box constraint, $b$ is , and $A$ has rank one. Note that by the argument in (3), we can always assume that $b=0$.

Define the smooth function $g(x):=(1/2)\langle Qx,x\rangle+\langle c,x\rangle$, the indicator function $f(x):=\chi_{C}(x)$ (which is on $C$ and $\infty$ elsewhere), and the vector space $V:=\{x\in{\mathbf{R}}^{d}\mid Ax=0\}$. With this notation, (5) is in the form (2) and, thus, FDRS can be applied. This splitting is nice because $\nabla g(x)=Qx+c$ is simple whereas the proximal operator of $g$ requires a matrix inversion $\mathbf{prox}_{\gamma g}=(I_{{\mathbf{R}}^{d}}+\gamma Q)^{-1}\circ(I_{{\mathbf{R}}^{d}}-\gamma c),$ which is expensive for large-scale problems.

1 Goals, challenges, and approaches

This work seeks to characterize the convergence rate of the FDRS algorithm applied to Problem (2). Recently, has shown that the sharp convergence rate of the fixed-point residual (FPR) (see Equation (21)) of the FDRS algorithm is $o(1/(k+1))$ . To the best of our knowledge, nothing is else is known about the convergence rate of FDRS. Furthermore, it is unclear how the FDRS algorithm relates to other algorithms. We seek to fill this gap.

The techniques used in this paper are based on . These techniques are quite different from those used in classical objective error convergence rate analysis. The classical techniques do not apply because the FDRS algorithm is driven by the fixed-point iteration of a nonexpansive operator, not by the minimization of a model function. Thus, we must explicitly use the properties of nonexpansive operators in order to derive convergence rates for the objective error.

We summarize our contributions and techniques as follows:

We analyze the objective error convergence rates (Theorems 12 and 15) of the FDRS algorithm under general convexity assumptions. We show that FDRS is, in the worst case, nearly as slow as the subgradient method yet nearly as fast as the proximal point algorithm (PPA) in the ergodic sense. Our nonergodic rates are shown by relating the objective error to the FPR through a fundamental inequality. We also show that the derived rates are sharp through counterexamples (Remarks 4 and 5).

We show that if $f$ or $g$ is strongly convex, then a natural sequence of points converges strongly to a minimizer. Furthermore, the best iterate converges with rate $o(1/(k+1))$, the ergodic iterate converges with rate $O(1/(k+1))$, and the nonergodic iterate converges with rate $o(1/\sqrt{k+1})$. The results follow by showing that a certain sequence of squared norms is summable. We also show that some of the derived rates are sharp by constructing a novel counterexample (Theorem 25).

We show that if $f$ is differentiable and $\nabla f$ is Lipschitz, then the best iterate of the FDRS algorithm has objective error of order $o(1/(k+1))$ (Theorem 19). This rate is an improvement over the sharp $o(1/\sqrt{k+1})$ convergence rate for nonsmooth $f$. The result follows by showing that the objective error is summable.

We establish scenarios under which FDRS converges linearly (Theorem 20) and show that linear convergence is impossible under other scenarios (Theorem 25).

We show that even if $f$ and $g$ are strongly convex, the FDRS algorithm can converge arbitrarily slowly (Theorem 24).

We show that the FDRS algorithm is the limiting case of a recently developed primal-dual forward-backward splitting algorithm (Section 7) and, thus, clarify how FDRS relates to existing algorithms.

Our analysis builds on the techniques and results of . The rest of this section contains a brief review of these results.

2 Notation and facts

Most of the definitions and notation that we use in this paper are standard and can be found in . Throughout this paper, we use ${\mathcal{H}}$ to denote (a possibly infinite dimensional) Hilbert space. In fixed-point iterations, $(\lambda_{j})_{j\geq 0}\subset{\mathbf{R}}_{+}$ will denote a sequence of relaxation parameters, and

For any subset $C\subseteq{\mathcal{H}}$, we define the distance function:

In addition, we define the indicator function $\chi_{C}:{\mathcal{H}}\rightarrow\{0,\infty\}$ of $C$: for all $x\in C$ and $y\in{\mathcal{H}}\backslash C$, we have $\chi_{C}(x)=0$ and $\chi_{C}(y)=\infty$.

Given a closed, proper, and convex function $f:{\mathcal{H}}\rightarrow(-\infty,\infty]$, the set $\partial f(x)=\{p\in{\mathcal{H}}\mid\text{for all }y\in{\mathcal{H}},f(y)\geq f(x)+\langle y-x,p\rangle\}$ denotes its subdifferential at $x$ and

denotes a subgradient. (This notation was used in [4, Eq. (1.10)].) If $f$ is Gâteaux differentiable at $x\in{\mathcal{H}}$, we have $\partial f(x)=\{\nabla f(x)\}$ [3, Proposition 17.26].

Let $I_{{\mathcal{H}}}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ be the identity map on ${\mathcal{H}}$. For any $x\in{\mathcal{H}}$ and $\gamma\in{\mathbf{R}}_{++}$, we let

which are known as the proximal and reflection operators, respectively.

The subdifferential of the indicator function $\chi_{V}$ where $V\subseteq{\mathcal{H}}$ is a closed vector subspace is defined as follows: for all $x\in{\mathcal{H}}$,

where $V^{\perp}$ is the orthogonal complement of $V$. Evidently, if $P_{V}(\cdot)=\operatorname*{arg\,min}_{y\in V}\|y-\cdot\|^{2}$ is the projection onto $V$, then

and these operators are independent of $\gamma$.

Let $\lambda>0$, let $L\geq 0$, and let $T:{\mathcal{H}}\rightarrow{\mathcal{H}}$ be a map. The map $T$ is called $L$-Lipschitz continuous if $\|Tx-Ty\|\leq L\|x-y\|$ for all $x,y\in{\mathcal{H}}$. The map $T$ is called nonexpansive if it is $1$-Lipschitz. We also use the notation:

If $\lambda\in(0,1)$ and $T$ is nonexpansive, then $T_{\lambda}$ is called $\lambda$-averaged [3, Definition 4.23].

We call the following identity the cosine rule:

Young’s inequality is the following: for all $a,b\geq 0$ and $\varepsilon>0$, we have

3 Assumptions

$f$ and $g$ are closed, proper, and convex.

We also assume the existence of a particular solution to (2)

$\operatorname*{zer}(\partial f+\nabla g+\partial\chi_{V})\neq\emptyset$

Finally we assume that $\nabla g$ is sufficiently nice.

The function $g$ is differentiable, $\nabla g$ is $(1/\beta)$-Lipschitz, and $P_{V}\circ\nabla g\circ P_{V}$ is $(1/\beta_{V})$-Lipschitz.

4 The FDRS algorithm

For now, we do not specify the stepsize parameters. See section 1.6 for choices that ensure convergence and, see Lemma 6 and Figure 1 for intuition.

By choosing particular $f,g$ and $V$, we recover several other splitting algorithms:

For general $f,g$ and $V$, the primal DRS and FBS algorithms are not capable splitting Problem (2) in the same way as (12). Indeed, the DRS algorithm cannot use the smooth structure of $g$, and the FBS algorithm requires the evaluation of $\mathbf{prox}_{\gamma(f+\chi_{V})}(\cdot)=\operatorname*{arg\,min}_{x\in V}\left(f(x)+(1/2\gamma)\|x-\cdot\|^{2}\right).$ The FDRS algorithm eliminates these difficult problems and replaces them with (possibly) more tractable ones.

5 Proximal, averaged, and FDRS operators

We briefly review some operator-theoretic properties.

Let $\lambda>0$, let $\gamma>0$, let $\alpha>0$, and let $f:{\mathcal{H}}\rightarrow(-\infty,\infty]$ be closed, proper, and convex.

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

Optimality conditions of $\mathbf{prox}_{\chi_{V}}$: Let $x\in{\mathcal{H}}$. Then $x^{+}=\mathbf{prox}_{\gamma\chi_{V}}(x)$ if, and only if, $\widetilde{\nabla}\chi_{V}(x^{+}):=(1/\gamma)(x-x^{+})\in\partial\chi_{V}(x^{+}).$ Also, $\gamma\widetilde{\nabla}\chi_{V}(x^{+})=P_{V^{\perp}}x\in V^{\perp}$.

Averaged operator contraction property: A map $T:{\mathcal{H}}\rightarrow{\mathcal{H}}$ is $\alpha$-averaged (see (9)) if, and only if, for all $x,y\in{\mathcal{H}}$,

Composition of averaged operators: Let $\alpha_{1},\alpha_{2}\in(0,1)$. Suppose $T_{1}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ and $T_{2}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ are $\alpha_{1}$ and $\alpha_{2}$-averaged operators, respectively. Then for all $x,y\in{\mathcal{H}}$, the map $T_{1}\circ T_{2}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ is averaged with parameter

Wider relaxations: A map $T:{\mathcal{H}}\rightarrow{\mathcal{H}}$ is $\alpha$-averaged if, and only if, $T_{\lambda}$ (see (9)) is $\lambda\alpha$-averaged for all $\lambda\in(0,1/\alpha)$.

Proximal operators are $(1/2)$-averaged: The operator $\mathbf{prox}_{\gamma f}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ is $(1/2)$-averaged and, hence, the operator $\mathbf{refl}_{\gamma f}=2\mathbf{prox}_{\gamma f}-I_{{\mathcal{H}}}$ is nonexpansive.

Parts 1, 2, 3, 5, and 6 can be found in . Part 4 can be found in . Part 7 follows from two facts: The operator $(({1}/{2})I_{{\mathcal{H}}}+(1/2)\mathbf{refl}_{\gamma f}\circ\mathbf{refl}_{\chi_{V}})$ is $(1/2)$-averaged by Part 6, and $I-\gamma P_{V}\circ\nabla g\circ P_{V}$ is $(\gamma/2\beta)$-averaged by [7, Proposition 4.1 (ii)]. Thus, Part 4 proves Part 7. ∎

The proof of the following Proposition is essentially contained in [12, Theorem 2.4]. We reproduce it in Appendix B.1 in order to derive a bound. The reader should note the following inequality before reading the proof.

Let $\varepsilon\in(0,1)$. Then it is easy to show that

Let $\alpha_{1},\alpha_{2}\in(0,1)$. Suppose that $T_{1}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ and $T_{2}:{\mathcal{H}}\rightarrow{\mathcal{H}}$ are $\alpha_{1}$ and $\alpha_{2}$-averaged operators, respectively, and that $z^{\ast}$ is a fixed-point of $T_{1}\circ T_{2}$. Define $\alpha_{1,2}\in(0,1)$ as in (14). Let $z^{0}\in{\mathcal{H}}$, let $\varepsilon\in(0,1)$, and consider a sequence $(\lambda_{j})_{j\geq 0}\subseteq(0,{(1-\varepsilon)(1+\varepsilon\alpha_{1,2})}/{\alpha_{1,2}})$. Let $(z^{j})_{j\geq 0}$ be generated by the following iteration: for all $k\geq 0$, let $z^{k+1}=(T_{1}\circ T_{2})_{\lambda_{k}}(z^{k}).$ Then

6 Convergence properties of FDRS

Most of our results do not require that $(z^{j})_{j\geq 0}$ converges. However, for completeness we include the following weak convergence result.

The following theorem recalls several results on convergence rates for the iteration of averaged operators . In addition, we show that $(\lambda_{j}\|\nabla h(z^{j})-\nabla h(z^{\ast})\|^{2})_{j\geq 0}$ is a summable sequence whenever $(\lambda_{j})_{j\geq 0}$ is chosen properly.

Summable fixed-point residual: The sum is finite:

Gradient summability: Let $\varepsilon\in(0,1)$ and suppose that

Then the following gradient sum is finite:

We call the following term the fixed-point residual (FPR):

Subgradients and fundamental inequalities

In this section, we prove several algebraic identities of the FDRS algorithm. In addition, we prove a relationship between the FPR and the objective error (Propositions 9 and 10).

In first-order optimization algorithms, we only have access to (sub)gradients and function values. Consequently, the FPR is usually the squared norm of a linear combination of (sub)gradients of the objective functions. For example, the gradient descent algorithm for a smooth function $f$ generates a sequence of iterates by using forward gradient steps: $z^{k+1}:=z^{k}-\nabla f(z^{k})$; the FPR is $\|z^{k+1}-z^{k}\|^{2}=\|\nabla f(z^{k})\|^{2}.$

In splitting algorithms, the FPR is more complex because the subgradients are generated via forward-gradient or proximal (backward) steps (see Part 1 of Proposition 1) at different points. Thus, unlike the gradient descent algorithm where the objective error $f(z^{k})-f(x^{\ast})\leq\langle z^{k}-x^{\ast},\nabla f(x^{k})\rangle$ can be bounded with the subgradient inequality, splitting algorithms for two or more functions can only bound the objective error when some or all of the functions are evaluated at separate points — unless a Lipschitz assumption is imposed. In order to use this Lipschitz assumption, we enforce consensus among the variables, which is why the FPR rate is useful.

The following lemma is proved in Appendix B.2.

Let $z\in{\mathcal{H}}$. Define points $x_{h}$ and $x_{f}$:

where $\widetilde{\nabla}\chi_{V}(x_{h})=(1/\gamma)P_{V^{\perp}}(z)$ and $\widetilde{\nabla}f(x_{f})$ is uniquely defined by Part 1 of Proposition 1. In addition, each FDRS step has the following form:

Let $(z^{j})_{j\geq 0}$ be generated by Algorithm 1 and define $(x_{h}^{j})_{j\geq 0}$ and $(x_{f}^{j})_{j\geq 0}$ as in (22) (with $z=z^{j}$). Then define ergodic iterates:

2 Optimality conditions of FDRS

The following lemma is proved in Appendix B.3.

3 Fundamental inequalities

In this section, we prove two fundamental inequalities that relate the FPR (see (21)) to the objective error.

Throughout the rest of the paper, we use the following notation: The functions $f$ and $g$ are $\mu_{f}$ and $\mu_{g}$-strongly convex, respectively, where we allow $\mu_{f}$ or $\mu_{g}$ to be zero (i.e., no strong convexity). In addition, we assume that $f$ is $(1/\beta_{f})$-Lipschitz differentiable, where we allow $\beta_{f}=0$. If $\beta_{f}>0$, then $\widetilde{\nabla}f=\nabla f$. With these assumptions, we get the following lower bounds [3, Theorem 18.15]:

where $\widetilde{\nabla}f(y)\in\partial f(y)$, and for any $x,y\in{\mathcal{H}}$,

See Appendices B.4, B.5, and B.6 for the proofs of the following inequalities:

where $x_{f}$ and $x_{h}$ are defined as in Lemma 6.

Objective convergence rates

In this section, we analyze the ergodic and nonergodic convergence rates of the FDRS algorithm applied to (2).

All of our bounds will be produced on objective errors of the form:

The objective error on the left hand side of (33) can be negative. Thus, we bound its absolute value. In addition, we bound $\|x_{f}^{k}-x_{h}^{k}\|$. Because $x_{h}^{k}\in V$, the objective error on the right hand size of (33) is positive. Consequently, $x_{h}^{k}$ is the natural point at which to measure the convergence rate. To derive such a bound, we assume $f$ is Lipschitz. Note that in both cases, we have the identity $h(x_{h}^{k})=(g\circ P_{V})(x_{h}^{k})=g(x_{h}^{k})$.

In this section, we analyze the ergodic convergence rate of the FDRS algorithm. The key idea is to use the telescoping property of the upper and lower fundamental inequalities, together with the summability of the difference of gradients shown in Part 4 of Theorem 5. See Section 1.2 for the distinction between ergodic and nonergodic convergence rates.

Let $\gamma\in(0,2\beta_{V})$, let $\varepsilon\in(0,1)$, and suppose that $(\lambda_{j})_{j\geq 0}$ satisfies (19). Define $(\overline{x}_{f}^{j})_{j\geq 0}$ and $(\overline{x}_{h}^{j})_{j\geq 0}$ as in (25). Then we have the following convergence rate: for all $k\geq 0$,

In addition the following feasibility bound holds: $\|\overline{x}_{f}^{k}-\overline{x}_{h}^{k}\|\leq(2/\Lambda_{k})\|z^{0}-z^{\ast}\|.$

Proof. Fix $k\geq 0$. The feasibility bound follows from Part 1 of Theorem 5:

Therefore, by Jensen’s inequality, the Cauchy-Schwarz inequality, (30), and the bound $\|z^{0}-z^{k+1}\|\leq 2\|z^{0}-z^{\ast}\|$ (see (34)), we have

The lower bound in Proposition 10 and the Cauchy-Schwarz inequality show that

To use this fact, we need to show that the sequences $(x_{f}^{j})_{j\geq 0}$, and $(x_{h}^{j})_{j\geq 0}$ are bounded. Recall that $x_{h}^{s}=P_{V}(z^{s})$ and $x_{f}^{s}=\mathbf{prox}_{\gamma f}\circ\mathbf{refl}_{\chi_{V}}\circ(I_{\mathcal{H}}-\gamma\nabla h)(z^{s})$ for $s\in\{\ast,k\}$. Proximal, reflection, and forward-gradient maps are nonexpansive (see Proposition 1, the Baillon-Haddad Theorem , and [3, Proposition 4.33]), so we have $\max\{\|x_{f}^{k}-x^{\ast}\|,\|x_{h}^{k}-x^{\ast}\|\}\leq\|z^{k}-z^{\ast}\|\leq\|z^{0}-z^{\ast}\|$ for all $k\geq 0$. Thus, $(x_{f}^{j})_{j\geq 0},(x_{h}^{j})_{j\geq 0}\subseteq\overline{B(x^{\ast},\|z^{0}-z^{\ast}\|)}.$ The ball is convex, so $(\overline{x}_{f}^{j})_{j\geq 0},(\overline{x}_{h}^{j})_{j\geq 0}\subseteq\overline{B(x^{\ast},\|z^{0}-z^{\ast}\|)}.$

Let the notation be as in Theorem 12. Let $L\geq 0$ and suppose $f$ is $L$-Lipschitz on $\overline{B(x^{\ast},\|z^{0}-z^{\ast}\|)}$. Then

Proof. The proof follows from by combining the upper bound in Theorem 12 with the following bound: $f(\overline{x}_{h}^{k})\leq f(\overline{x}_{f}^{k})+L\|\overline{x}_{f}^{k}-\overline{x}_{h}^{k}\|\leq f(\overline{x}_{f}^{k})+2L\|z^{0}-z^{\ast}\|/\Lambda_{k}.\qquad\end@proof$

Corollary 14 is sharp [16, Proposition 8].

2 Nonergodic convergence rates

and $|f(x_{f}^{k})+h(x_{h}^{k})-f(x^{\ast})-g(x^{\ast})|=o(1/\sqrt{k+1})$.

First we note that $\left(\|\nabla h(x_{h}^{j})\|\right)_{j\geq 0}$ is bounded: for all $k\geq 0$,

because $(\|z^{j}-z^{\ast}\|)_{j\geq 0}$ is decreasing (see Part 1 of Theorem 5).

where we use $\|z_{1}-x^{\ast}\|\leq\|z_{1}-z^{\ast}\|+\|z^{\ast}-x^{\ast}\|\leq\|z^{0}-z^{\ast}\|+\|z^{\ast}-x^{\ast}\|$ (Theorem 5).

The lower bound follows from (31) and Part 3 of Theorem 5:

If $f$ is Lipschitz continuous, we can evaluate the entire objective function at $x_{h}^{k}$. The proof of the following corollary is analogous to Corollary 14. We ask the reader to recall from Section 3.1 that $(x_{f}^{j})_{j\geq 0},(x_{h}^{j})_{j\geq 0}\subseteq\overline{B(x^{\ast},\|z^{0}-z^{\ast}\|)}.$

Let the notation be as in Theorem 15. Let $L\geq 0$ and suppose $f$ is $L$-Lipschitz on $\overline{B(x^{\ast},\|z^{0}-z^{\ast}\|)}$. Then

and $f(x_{h}^{k})+h(x_{h}^{k})-f(x^{\ast})-h(x^{\ast})=o(1/\sqrt{k+1})$.

Strong convexity

In this section, we show that $(x_{f}^{j})_{j\geq 0}$, $(x_{h}^{j})_{j\geq 0}$, and their ergodic variants converge strongly whenever $f$ or $g$ is strongly convex. The techniques in this section are similar to those in Section 3, so we defer the proof to Appedix B.7

“Best” iterate convergence: Let $\varepsilon\in(0,1)$ and suppose that $(\lambda_{j})_{j\geq 0}$ satisfies (19). If $\underline{\lambda}:=\inf_{j\geq 0}\lambda_{j}>0$, then

and $\min_{0\leq j\leq k}S_{f}(x_{f}^{j},x^{\ast})=o({1}/{(k+1)})$ and $\min_{0\leq j\leq k}S_{h}(x_{h}^{j},x^{\ast})=o({1}/{(k+1)})$.

Ergodic convergence: If $\varepsilon\in(0,1)$, and $(\lambda_{j})_{j\geq 0}$ satisfies (19), then

See Section 6.1 for a proof that the nonergodic “best” rates are sharp. It is not clear if we can improve the general nonergodic rates to $o(1/(k+1))$.

Lipschitz differentiability

In this section, we assume $f$ is smooth:

$f$ is differentiable and $\nabla f$ is $(1/\beta_{f})$-Lipschitz where $\beta_{f}>0$.

Under Assumption 4, we will show that the objective value

is summable. Therefore, by [16, Lemma 3] the minimal objective error after $k$ iterations is of order $o(1/(k+1))$. We will need the following upper bound to prove this. See Appendix B.8 for the proof.

The next theorem shows that the upper bound in Proposition 18 is summable and, as a consequence, we will have $o(1/(k+1))$ convergence.

Next, we use the Cauchy-Schwarz inequality and (11) to show that

If we combine the previous two sum bounds with (39), we get

The convergence rate now follows from [16, Lemma 3]. ∎

Theorem 19 is sharp under Assumption 4 [16, Theorem 12].

Linear convergence

In this section, we prove FDRS converges linearly when $\beta_{f}(\mu_{g}+\mu_{f})>0$.

(32) shows that for all $k\geq 0$, we have

In addition, by the Cauchy-Schwarz inequality and (11), we have

Recall that we assume $1-(2c-1)/(c\lambda_{k})<0$ and $\beta_{V}-c\gamma>0$.

Now suppose that $\beta_{f}\mu_{g}>0$. The following identity follows from from Lemma 6:

Now, fix $k\geq 0$, and let $C_{1}^{\prime}:=3\max\left\{(1+\gamma/\beta_{V})^{2}/(\gamma\lambda_{k}\mu_{g}),\gamma^{2}/(\gamma\lambda_{k}\beta_{f}),(1/\lambda_{k}^{2})\left(\frac{2c-1}{c\lambda_{k}}-1\right)^{-1}\right\}.$ By the convexity of $\|\cdot\|^{2}$, we have

Therefore, $\|z^{k+1}-z^{\ast}\|\leq\left(1-(1/C_{1}^{\prime})\right)^{1/2}\|z^{k}-z^{\ast}\|.$

Now assume that $\beta_{f}\mu_{f}>0$. Observe that:

where we use the identity $x_{h}^{k}-x_{f}^{k}=(1/\lambda_{k})(z^{k}-z^{k+1})$ (see (24)). The proof of this case is similar to the case $\beta_{f}\mu_{h}>0$ except that we use the above identity for $z^{k}$, the bound $\|(x_{f}^{k}-\gamma\nabla f(x_{f}^{k}))-(x^{\ast}-\gamma\nabla f(x^{\ast}))\|^{2}\leq(1+\gamma/\beta_{f})^{2}\|x_{f}^{k}-x^{\ast}\|^{2}$, and the constant $C_{2}^{\prime}:=3\max\left\{(1+\gamma/\beta_{f})^{2}/(\gamma\lambda_{k}\mu_{f}),\gamma^{2}/(\gamma\lambda_{k}(\beta_{V}-c\gamma)),(4/\lambda_{k}^{2})\left(\frac{2c-1}{c\lambda_{k}}-1\right)^{-1}\right\}$ in place of $C_{1}^{\prime}$. Then the contraction $\|z^{k+1}-z^{\ast}\|\leq\left(1-1/C_{2}^{\prime}\right)^{1/2}\|z^{k}-z^{\ast}\|$ follows.

In both cases, the linear rate for $(z^{j})_{j\geq 0}$ follows by unfolding (40). ∎

Note that smaller $c$ lead to larger $\gamma$ and smaller $(\lambda_{j})_{j\geq 0}$, while larger $c$ lead to smaller $\gamma$ and larger $(\lambda_{j})_{j\geq 0}$.

In general, we cannot expect linear convergence of FDRS when $f$ is not differentiable—even if $f$ and $g$ are strongly convex. In this section, we construct an example to prove this claim. The following example is based on [2, Section 7] and [16, Example 1].

Note that [2, Section 7] proves the projection identities

Define $N:{\mathcal{H}}\rightarrow{\mathcal{H}}$ on each 2-dimensional component of ${\mathcal{H}}$ as follows: for all $i\geq 0$,

where the second equality follows by direct expansion. Therefore, we have

Slow convergence proofs

The following is a simple corollary of Lemma 22.

Let the notation be as in Lemma 22. Then for all $\eta\in(0,1)$, we can find a sequence $(b_{j})_{j\geq 0}\subseteq(\eta,1)$ that satisfies the conditions of the lemma.

For any $\varepsilon\in(0,1-\eta)$, replace the sequence $(b_{j})_{j\geq 0}$ in Lemma 22 with $(\max\{b_{j},\eta+\varepsilon\})_{j\geq 0}$. ∎

We are now ready to show that FDRS can converge arbitrarily slowly.

Now, recall that $z^{\ast}=0$. Thus, for all $n\geq 0$ and $k\geq 0$, we have

Thus, $\|z^{k+1}-z^{\ast}\|\geq b_{n}^{k+1}/(n+1)$. Choose $b_{n}$ and the sequence $(n_{j})_{j\geq 0}$ using Corollary 23 with $\eta\in(a/(a+1),1)$. Then solve $c_{n}=\sqrt{b_{n}(1+a)-a}>0.$ ∎

Theorems 24 and 17 show that the sequence $(z^{j})_{j\geq 0}$ can converge arbitrarily slowly even if $(x_{f}^{j})_{j\geq 0}$ and $(x_{h}^{j})_{j\geq 0}$ converge with rate $o(1/\sqrt{k+1})$.

The following theorem shows that $(x_{f}^{j})_{j\geq 0}$ and $(x_{h}^{j})_{j\geq 0}$ do not converge linearly. See Appendix B.9 for the proof.

There exists a sequence $(c_{i})_{i\geq 0}$ so that $(x_{h}^{j})_{j\geq 0}$ and $(x_{f}^{j})_{j\geq 0}$ converge strongly, but not linearly. In particular, for any $\alpha>1/2$, there is an initial point $z^{0}\in{\mathcal{H}}$ so that for all $k\geq 1$,

Thus, the nonergodic “best” convergence rates in Part 3 of Theorem 17 are sharp.

Primal-dual splittings

In this section, we reformulate FDRS as a primal-dual algorithm applied to the dual of the following problem: $\operatorname*{minimize}_{x\in V}f(x)+h(x)$.

Let $\tau:=1/\gamma$, and suppose that $(z^{j})_{j\geq 0}$ is generated by the FDRS algorithm with $\lambda_{k}\equiv 1$. For all $k\geq 0$, let $y^{k}:=-\widetilde{\nabla}\chi_{V}(x_{h}^{k}).$ Then for all $k\geq 0$, we have the recursive update rule:

Proof. Fix $k\geq 0$. By Lemma 6, $z^{k+1}=x_{f}^{k}-\gamma y^{k}$, so $(-1/\gamma)z^{k+1}=y^{k}-\tau x_{f}^{k}$. Thus, the formula for $(y^{j})_{j\geq 0}$ follows from $y^{k+1}=-\widetilde{\nabla}\chi_{V}(x_{h}^{k+1})=-(1/\gamma)P_{V^{\perp}}z^{k+1}$.

Furthermore, $\nabla h(x_{f}^{k})=\nabla h(P_{V}x_{f}^{k})=\nabla h(P_{V}(z^{k+1}+\gamma y^{k}))=\nabla h(x_{h}^{k+1})$. Thus,

The algorithm in (46) is the primal-dual forward-backward algorithm of Vũ and Condat applied to the following dual problem: $\operatorname*{minimize}_{x\in V^{\perp}}\;(f+h)^{\ast}(x)$ where $(f+h)^{\ast}(\cdot)=\sup_{x\in{\mathcal{H}}}\langle x,\cdot\rangle-(f+h)(x)$ is the Legendre-Fenchel transform of $f+h$ [3, Definition 13.1]. For convergence, [26, Theorem 3.1] requires $\gamma\tau<1$ and $2\beta_{V}>\left(\min\{1/\gamma,1/\tau\}\left(1-\sqrt{\gamma\tau}\right)\right)^{-1}$ whereas FDRS requires $\gamma<2\beta_{V}$ (and $\tau=1/\gamma$).

Thus, the FDRS algorithm is a limiting case of Vũ and Condat’s algorithm, much like the DRS algorithm is a limiting case of Chambolle and Pock’s primal-dual algorithm . In addition, the convergence rate analysis in Section 3 cannot be subsumed by the recent convergence rate analysis of the primal-dual gap of Vũ and Condat’s algorithm , which only applies when $\gamma\tau<1$. The original FDRS paper did not show this connection [7, Remark 6.3 (iii)].

Conclusion

In this paper, we provided a comprehensive convergence rate analysis of the FDRS algorithm under general convexity, strong convexity, and Lipschitz differentiability assumptions. In almost all cases, the derived convergence rates are shown to be sharp. In addition, we showed that the FDRS algorithm is the limiting case of a recently developed primal-dual forward-backward operator splitting algorithm and, thus, clarify how it relates to existing algorithms. Future work on FDRS might evaluate the performance of the algorithm on realistic problems.

Acknowledgement

We thank Prof. Wotao Yin and the anonymous reviewers for helpful comments. We also thank the two anonymous referees for their insightful and detailed comments.

In this section, we briefly illustrate the benefits of using $\beta_{V}$ in place of $\beta$ on a Kernelized SVM problem, which is discussed in Section 1; see (5) for notation. In Figure 2 we plot the FPR associated to the FDRS algorithm applied to a 1000-dimensional quadratic program. To generate the quadratic program, we use a random 1000-element subset of the the “a7a” dataset (available from the LIBSVM website ) denoted by $X=\{(x_{1},y_{1})^{T},\cdots,(x_{1000},y_{1000})^{T}\}\subseteq{\mathbf{R}}^{123}$ where for each $i=1,\cdots,1000$, $x_{i}\in{\mathbf{R}}^{122}$ is a data point and $y_{i}\in\{-1,1\}$ is a class label. We use the matrix $Q\in{\mathbf{R}}^{1000\times 1000}$ with $i,j$ entry given by the formula $Q_{i,j}=y_{i}y_{j}\exp(-2^{-3}\|x_{i}-x_{j}\|^{2})$ for $i,j\in\{1,\cdots,1000\}$ (i.e., we use the radial basis function kernel). The matrix $A$ is the row vector $(y_{1},\cdots,y_{1000})\in{\mathbf{R}}^{1\times 1000}$, and the set $C$ is the box $^{1000}\subseteq{\mathbf{R}}^{1000}$. In this case, $P_{V}$ has rank $999$, but the maximal eigenvalue $(1/\beta_{V}\approx 3.5159)$ of $P_{V}\circ Q\circ P_{V}$ is approximately $275.8248$ times smaller than the maximal eigenvalue $(1/\beta\approx 969.7836)$ of $Q$. Figure 2 shows that choosing $\gamma=1.99\beta_{V}$ results in a tremendous speedup. (In both examples, we chose $\lambda_{k}\equiv 1$.)

Appendix B Proofs of technical results

For the proof, we ask the reader to recall (15).

By applying (13) twice, we get $\|T_{1}\circ T_{2}(z^{k})-T_{1}\circ T_{2}(z^{\ast})\|^{2}\leq\|z^{k}-z^{\ast}\|^{2}-p^{k}.$

Part 5 of Proposition 1 shows that $(T_{1}\circ T_{2})_{\lambda_{k}}$ is $(\alpha_{1,2}\lambda_{k})$-averaged. Thus,

Therefore, $\sum_{i=0}^{\infty}\frac{\lambda_{i}(1-\alpha_{1,2}\lambda_{i})}{\alpha_{1,2}}\|T_{1}\circ T_{2}(z^{i})-z^{i}\|^{2}\leq\|z^{0}-z^{\ast}\|^{2}.$

By [3, Corollary 2.14], the following holds: for all $x,y\in{\mathcal{H}}$ and all $\lambda\in{\mathbf{R}}$, we have $\|\lambda x+(1-\lambda)y\|^{2}=\lambda\|x\|^{2}+(1-\lambda)\|y\|^{2}-\lambda(1-\lambda)\|x-y\|^{2}.$ Therefore, we have

Thus, take $k\rightarrow\infty$ in the following inequality to get the result:

B.2 Proof of Lemma 6

The identity for $x_{h}=z-\gamma\widetilde{\nabla}\chi_{V}(x_{h})$ follows from Part 1 of Proposition 1. Note that by the Moreau identity $P_{V^{\perp}}=I-P_{V}$, we have $\gamma\widetilde{\nabla}\chi_{V}(x_{h})=P_{V^{\perp}}z$. Note that by definition, $\nabla h(z)=P_{V}\circ\nabla g\circ P_{V}(z)=P_{V}\circ\nabla g(x_{h})=\nabla h(x_{h})$ and $\nabla h(z)\in V$. Thus, we get the identity for $x_{f}$:

B.3 Proof of Lemma 8

B.4 Proof of Proposition 9

In the following derivation, we use (26) and (27), Lemma 6, the cosine rule, and the inclusion $\widetilde{\nabla}\chi_{V}(x_{h})\in V^{\perp}$:

B.5 Proof of Proposition 10

By (26) and (27) and because $\widetilde{\nabla}\chi_{V}(x^{\ast})\in V^{\perp}$, we have

B.6 Proof of Corollary 11

By (10), we have $\|z-x^{\ast}\|^{2}-\|z^{+}-x^{\ast}\|^{2}=\|z-z^{\ast}\|^{2}-\|z^{+}-z^{\ast}\|^{2}+2\langle z-z^{+},z^{\ast}-x^{\ast}\rangle.$ Therefore, by Proposition 9,

Equation (32) now follows from (47) and (31):

B.7 Proof of Theorem 17

Let $\eta_{k}=2/\lambda_{k}-1$. By (35), we have

Hence, for all $k\geq 0$, we have (using $1/\eta_{k}\leq\lambda_{k}/\varepsilon^{2}$ as in (35) and (15))

The “best” convergence rates now follow by taking $k\rightarrow\infty$ and using [16, Lemma 3]. In addition, we apply Jensen’s inequality to $\|\cdot\|^{2}$ in the first term to get

where (49) uses the ($1/\beta_{V}$)-Lipschitz continuity of $\nabla h$ and the identity $\nabla h(x_{h}^{k})-\nabla h(x^{\ast})=\nabla h(z^{k})-\nabla h(z^{\ast})$, and the last line uses the Fejér property $\|z_{1}-z^{\ast}\|\leq\|z^{k}-z^{\ast}\|\leq\|z^{0}-z^{\ast}\|$ (see Part 1 of Theorem 5). The $o(1/\sqrt{k+1})$ rates follow from (49) and the corresponding rates for the FPR in (18).

B.8 Proof of Proposition 18

Because $\nabla f$ is ($1/\beta_{f}$)-Lipschitz, we have

where the first inequality follows from [3, Theorem 18.15(iii)]. By applying the identity $z^{\ast}-x^{\ast}=\gamma\widetilde{\nabla}\chi_{V}(x^{\ast})=-\gamma\nabla f(x^{\ast})-\gamma\nabla h(x^{\ast})$, the cosine rule (10), and the identity $z-z^{+}=\lambda(x_{h}-x_{f})$ (see (24)) multiple times, we have

By (24) (i.e., $z-z^{+}=\lambda(x_{h}-x_{f})$), we have

If $\gamma\leq\beta_{f}$, then we can drop the last term. If $\gamma>\beta_{f}$, then use (32) to get

B.9 Proof of Theorem 25

For all $i\geq 0$, let $c_{i}:=(i/(i+1))^{1/2}$. Let $\kappa_{a}:=(1/2)+2(a+1)^{2}$, and let $z^{0}:=\sqrt{2\alpha\kappa_{a}}e^{(1/(a+1))}\times\left((\|z_{i}\|^{-1}/(i+1)^{\alpha})z_{i}\right)_{i\geq 0}.$ Then $\|z^{0}\|^{2}=2\alpha\kappa_{a}e^{2/(a+1)}\sum_{i=0}^{\infty}(1/(i+1)^{2\alpha})<\infty$ and, hence, $z^{0}\in{\mathcal{H}}$. Now for all $i\geq 1$, we have

because $c_{i}^{2}\in[1/2,1)$. In addition, for all $i\geq 1$, we have

where the third equality follows because $1-c_{i}^{2}=1-i/(i+1)=1/(i+1)$.

where we use $x^{\ast}=0$ and the lower integral approximation of the sum.

where the last inequality follows because $1-c_{i}^{2}=1-i/(i+1)=1/(i+1)$ and $\kappa_{a}/\|z_{i}\|^{2}\geq(a+c_{i}^{2})^{2}/c_{i}^{2}$. Note that for all $i\geq 1$, we have $(a+c_{i}^{2})^{2}/c_{i}^{2}\geq(a+1/2)^{2}$ because $c_{i}^{2}\in[1/2,1)$. Therefore, for all $k\geq 1$, we have

where we use similar arguments to those used in (55).

References