On the improved conditions for some primal-dual algorithms

We consider the following minimization problem in the form of the sum of three functions

where $f$ is a differentiable convex function with $L$-Lipschitz continuous gradient and $g$, $h$ are proper, closed and convex functions taking values in $(-\infty,\infty].$ The third function $h$ is composited with a linear operator ${\mathbf{A}}\in\mathbb{R}^{n\times m}$, whose largest singular value is $\sigma$, i.e., $\sigma=\sqrt{\|{\mathbf{A}}{\mathbf{A}}^{\top}\|}$.

We use the asterisk superscript to denote the Legendre-Fenchel conjugate function, e.g., $h^{*}:\mathbb{R}^{m}\rightarrow\mathbb{R}$ is defined as

Then, the saddle-point form of problem (1) is

where ${\mathbf{x}}$ and ${\mathbf{s}}$ are primal and dual variables, respectively. With the existence of a solution pair $({\mathbf{x}}^{*},{\mathbf{s}}^{*})$, the first-order optimal condition is characterized as

where $\partial g({\mathbf{x}})=\{{\mathbf{v}}\in\mathbb{R}^{n}\ |\ g({\mathbf{y}})-g({\mathbf{x}})\geq\langle{\mathbf{v}},{\mathbf{y}}-{\mathbf{x}}\rangle,\forall{\mathbf{y}}\in\mathbb{R}^{n}\}$ is the subdifferential of $g$ at ${\mathbf{x}}$. The duality theorem (rockafellar1974conjugate, , Theorem 15) asserts that ${\mathbf{x}}^{*}$ is the solution of the problem (1) and ${\mathbf{s}}^{*}$ is the solution of the corresponding dual problem

where $f^{*}\mathrel{\raisebox{-1.0pt}{\framebox(1.0,1.0)[]{$\scriptstyle$}}}g^{*}$ is the infimal convolution of $f^{*}$ and $g^{*}$ that is defined as $f^{*}\mathrel{\raisebox{-1.0pt}{\framebox(1.0,1.0)[]{$\scriptstyle$}}}g^{*}({\mathbf{x}})=\inf_{{\mathbf{y}}\in\mathbb{R}^{n}}f^{*}({\mathbf{y}})+g^{*}({\mathbf{x}}-{\mathbf{y}})$ with the property that $(f^{*}\mathrel{\raisebox{-1.0pt}{\framebox(1.0,1.0)[]{$\scriptstyle$}}}g^{*})^{*}=f+g.$ Note that when $f=0$ (or $g=0$), the infimal convolution $f^{*}\mathrel{\raisebox{-1.0pt}{\framebox(1.0,1.0)[]{$\scriptstyle$}}}g^{*}$ boils down to $g^{*}$ (or $f^{*}$).

Existing primal-dual algorithms to solve the above saddle-point problem (2) include Condat-Vu condat2013primal ; vu2013splitting , Primal–Dual Fixed-Point algorithm(PDFP) chen2016primal , Asymmetric Forward–Backward-Adjoint splitting(AFBA) latafat2017asymmetric and Primal–Dual Three-Operator splitting(PD3O) yan2018new . When $f=0$, Condat-Vu and PD3O are reduced to Chambolle-Pock chambolle2011first . When $g=0,$ all algorithms except Condat-Vu are reduced to Proximal Alternating Predictor–Corrector(PAPC) or Primal–Dual Fixed-Point algorithm based on the Proximity Operator(PDFP²O) loris2011generalization ; chen2013primal ; drori2015simple . The conditions on their stepsizes to guarantee the convergence is associated with the singular value of the linear operator $\sigma$ and the Lipschitz constant $L$. With notations $\eta_{\text{p}}$ for the primal stepsize and $\eta_{\text{d}}$ for the dual stepsize, Table 1 lists the conditions on stepsizes of the aforementioned algorithms and their connections when either $f$ or $g$ vanishes.

The listed conditions in Table 1 are all sufficient to guarantee the convergence of the associated algorithms, and some cannot be relaxed any further. For PAPC, the first constraint, $\eta_{\text{p}}L/2<1$, cannot be relaxed since it reduces to gradient descent method with stepsize $\eta_{\text{p}}$ when there is only one $f$, i.e., $h=0$. However, it turns out that the upper bound of $\eta_{\text{p}}\eta_{\text{d}}\sigma^{2}$ can be relaxed to $4/3$. In  he2020optimal ; li2021linear , a special case of PAPC, linearized augumented Lagrangian method, and an application of PAPC on the decentralized optimization are shown to converge under the relaxed condition. The general convergence result of PAPC with relaxed condition is shown in li2021new . The $4/3$ bound is also shown to be tight in he2020optimal ; li2021new . This result raises an open question, i.e., can the similar relaxation be applied to Chambolle-Pock? The follow-up question is can this result be generalized to algorithms for the general problem (1)?.

The first question is implicitly answered by some work. A generalized Chambolle-Pock is proposed in he2021generalized to achieve the relaxation and its equivalence to the canonical Chambolle-Pock is proved for the following primal-dual problem

which covers the general form (2) with linear $h^{*}$. The necessity of the condition is also shown by a simple case.

In he2020optimally , a relaxed linearization parameter is considered in the linearized Alternating Direction Method of Multipliers(L-ADMM) so that a larger stepsize can be used in the linearized subproblem to converge faster. L-ADMM considers the following linearly constrained problem,

where $\widetilde{f}:\mathbb{R}^{n_{1}}\rightarrow\mathbb{R}$, $\widetilde{g}:\mathbb{R}^{n_{2}}\rightarrow\mathbb{R}$ are proper, closed and convex, $\widetilde{{\mathbf{A}}}\in\mathbb{R}^{m\times n_{1}}$, $\widetilde{{\mathbf{B}}}\in\mathbb{R}^{m\times n_{2}}$ are two linear operators and ${\mathbf{b}}\in\mathbb{R}^{m}$. When $\widetilde{f}=g^{*}$ and $\widetilde{g}=h^{*}$, the dual problem can be formulated via Lagrangian multiplier as

A special case of the above dual problem (5) is ${\mathbf{b}}=\mathbf{0}$, $\widetilde{{\mathbf{A}}}={\mathbf{I}}$, and $\widetilde{{\mathbf{B}}}^{\top}={\mathbf{A}}$. In this case, it reduces to the problem (1) with $f=0.$ It can be easily shown that L-ADMM applied to this special case of the problem (4) is equivalent to Chambolle-Pock applied to the corresponeding dual problem. Therefore, the result in he2020optimally suggests the improved condition on stepsizes of Chambolle-Pock, $\eta_{\text{p}}\eta_{\text{d}}\sigma^{2}<\frac{4}{3}.$ When ${\mathbf{b}}\not=0$ in the special case, the result in he2020optimally also indicates that the relaxed conditon is extensible to the problem (1) with a linear function $f$.

However, there is no result for general Lipschitz smooth $f$ in the literature. This work will address the second question for AFBA and PD3O by characterizing a more general upper bound for $\eta_{\text{p}}$ and $\eta_{\text{d}}$, and directly give an affirmative answer to the first question.

Throughout the rest of the paper, we assume that there exists a solution pair $({\mathbf{x}}^{*},{\mathbf{s}}^{*})$ of the problem (2). We use $({\mathbf{I}}+\lambda\partial g)^{-1}({\mathbf{x}})$ to represent the proximal operator of $g$ at ${\mathbf{x}}$, which is defined as

We use $\langle\cdot,\cdot\rangle$ and $\|\cdot\|$ as the standard inner product and norm defined over $\mathbb{R}^{n}$, and denote $\|\cdot\|_{\mathbf{M}}=\sqrt{\langle\cdot,{\mathbf{M}}(\cdot)\rangle}$ as the (semi)norm associated with the given positive (semi)definite matrix ${\mathbf{M}}\in\mathbb{R}^{n\times n}$.

The rest of this paper is organized as follows. We first derive a base algorithm that is later shown to be an equivalent form of AFBA and illustrate the connection between AFBA, PD3O and Chambolle-Pock in Section 2. We then prove the convergence of the base algorithm under the relaxed condition associated with the matrix ${\mathbf{A}}$ in Section 3. In the next section, we numerically show the performance of the algorithms under the proved weaker condition.

For simplicity, we set $\eta_{\text{p}}=r$ and $\eta_{\text{d}}=\lambda/r$. That is, the product of the primal and dual stepsizes is $\lambda$. The optimality condition of problem (2) can be reformulated as the following monotone inclusion problem

This problem is also equivalent to

Let $\zeta\in{\mathbf{x}}-r\nabla f({\mathbf{x}})-r\partial g({\mathbf{x}})$, then the above form can be decomposed as

Plug $({\mathbf{x}}^{k+1},{\mathbf{s}}^{k+1},\zeta^{k+1})$ into the right-hand side of (7) and let the rest $\zeta,{\mathbf{x}},{\mathbf{s}}$ on the left-hand side of (7) be the variables in $k$th iteration $({\mathbf{x}}^{k},{\mathbf{s}}^{k},\zeta^{k})$. Then, we can solve for the next-step variables of the system (7) in the ${\mathbf{s}}\mathchar 45\relax{\mathbf{x}}\mathchar 45\relax\zeta$ order by Gaussian elimination. The base algorithm follows

where $r$ and $\lambda/r$ are primal and dual stepsizes, respectively.

In Section 3, we will show the convergence of the algorithm when $r<\frac{4\theta-3}{2\theta-1}\frac{2}{L}$ and $\lambda\leq\frac{1}{\theta\sigma^{2}}$ with any $\theta\in(3/4,1].$ Notice that, when $\theta=1,$ the conditions on $r$ and $\lambda$ is reduced to $r<\frac{2}{L}$ and $\lambda\leq\frac{1}{\sigma^{2}}$. As listed in Table 1, this condition is the sufficient condition on stepizes for PDFP shown in chen2016primal and PD3O shown in yan2018new , which is apparently weaker than that for Condat-Vu shown in condat2013primal ; vu2013splitting and AFBA shown in latafat2017asymmetric . This general form of the upper bound gives a larger range of $\lambda$ and accordingly narrows the range of values of $r$.

However, the compromise on $r$ will disappear when $f$ is linear ($L=0$). In this case, $r$ can take any value in $(0,\infty)$ and consequently, $\lambda$ can take value as large as $\frac{4}{3\sigma^{2}}$. We will later show in Section 2.3 that the base algorithm recovers Chambolle-Pock applied to the dual problem (3) with $f=0$. The range on $\lambda$ is significantly better than the previously used for Chambolle-Pock, which is $\lambda\leq\frac{1}{\sigma^{2}}.$ Therefore, the first question is answered.

Next, we will discuss the connection of the base algorithm with AFBA, PD3O ,Chambolle-Pock and PAPC(PDFP²O). We say an algorithm is equivalent to another one if and only if we can find an one-one map between the sequences generated by two algorithms with appropriate initialization.