betaFeedback

WorksMathematics

A Fast Proximal-Gradient Algorithm for Decentralised Optimisation

Abstract

We consider a connected multi-agent network where agents coordinate to minimise a finite sum of convex functions. Each function in the sum can be further expressed as the sum of a smooth and nonsmooth component and is known only to a single agent in the network. We propose a decentralised proximal-gradient-type algorithm for solving this problem, which we term Fast PG-EXTRA. In each iteration, agents evaluate the gradient of the smooth component of their local objective functions and the proximal operator of the nonsmooth component, followed by communicating the results with neighbouring agents in the network. Fast PG-EXTRA can be viewed as an accelerated variant of PG-EXTRA, in the sense that it enjoys non-ergodic o(1/k2)o(1/k^2) convergence rates in terms of the first-order optimality residual, successive iterates, and consensus error, compared to PG-EXTRA's ergodic O(1/k)O(1/k) convergence rates. Our analysis of Fast PG-EXTRA is based on an accelerated variant of the Condat–Vũ algorithm for non-distributed convex minimisation, which has similarly improved convergence rates compared to the Condat–Vũ algorithm. We validate our convergence results for Fast PG-EXTRA and demonstrate its potential advantages compared to PG-EXTRA with numerical experiments for power state system estimation and l1l_1-regularised logistic regression.

Keywords: distributed optimization, proximal-gradient, convergence rates, sparse regression.

MSC2020: 47N10, 62J07, 65K10, 65B99, 68W15

Introduction

Consider a connected graph of nn agents coordinating to solve

min⁡x∈Rp∑i=1ngi(x)+fi(x),(1)\min_{x\in\mathbb{R}^{p}} \sum_{i=1}^{n} g_i(x) + f_i(x), \tag*{(1)}

where the functions g1,…,gn:Rp→R∪{+∞}g_1,\ldots,g_n:\mathbb{R}^{p}\to\mathbb{R}\cup\{+\infty\} are proper lsc convex, and the functions f1,…,fn:Rp→Rf_1,\ldots,f_n:\mathbb{R}^{p}\to\mathbb{R} are convex and differentiable with LL-Lipschitz continuous gradient. We consider the setting where agent i∈{1,…,n}i\in\{1,\ldots,n\} knows only gig_i and fif_i, can evaluate the proximal operator of gig_i and the gradient of fif_i, and can communicate information with other agents only if they are connected by an edge in the graph. The structure of this problem arises in optimisation and control applications involving the coordination of multiple independent agents. For example, coordination of smart grids [1] and electric vehicle fleets [2], and statistics and machine learning applications where the data is partitioned amongst agents such as group LASSO [3] and system identification [4].

Background and contribution

Decentralised algorithms

In this work, we consider decentralised algorithms for solving (1), by which we mean algorithms where agents communicate with their neighbours in the graph, and there is no central authority that collects, manipulates, and distributes information to all agents [5, 6, 7]. Algorithms of this type are a subclass of distributed algorithms. Decentralised structures may be necessary when the problem data are naturally decentralised, and have potential benefits such as the absence of the central authority as a communication/computational bottleneck and single point of failure [8, 9].

This work focuses on decentralised proximal-gradient-type algorithms, where agents have access to first-order information of their local objective functions via the gradient of smooth terms and the proximal operator of nonsmooth terms. Algorithms of this type include decentralised (sub)gradient descent [6, 7], which requires diminishing step sizes, NIDS [10], which decouples step size requirements from the network topology, and decentralised proximal linearised ADMM [11, 12].

One important algorithm in this framework that is particularly relevant to this work is PG-EXTRA [8, 13]. Given a mixing matrix W=(wij)W=(w_{ij}) (Definition 1.1) and a step size τ<1+λmin⁡(W)L\tau< \frac{1+\lambda_{\min}(W)}{L}, where λmin⁡(W)\lambda_{\min}(W) denotes the smallest eigenvalue of WW, the main iteration of PG-EXTRA is, for all agents i=1,…,ni=1,\ldots,n,

uik=uik−1+∑j=1nwijxjk−12(xik−1+∑j=1nwijxjk−1)−τ(∇fi(xik)−∇fi(xik−1))(2)u_i^k=u_i^{k-1}+\sum_{j=1}^{n}w_{ij}x_j^k-\frac{1}{2}\left(x_i^{k-1}+\sum_{j=1}^{n}w_{ij}x_j^{k-1}\right)-\tau\left(\nabla f_i(x_i^k)-\nabla f_i(x_i^{k-1})\right) \tag*{(2)}
xik+1=prox⁡τgi(uik).(3)x_i^{k+1}=\operatorname{prox}_{\tau g_i}(u_i^k). \tag*{(3)}

Note that, in each iteration, agent ii separately computes the gradient of the smooth function fif_i and the proximal operator of the nonsmooth function gig_i. The variables uiku_i^k and xikx_i^k are local to agent ii, and the summations involving wijw_{ij} model agents communicating their local variables as the coefficients wijw_{ij} are nonzero only if agents ii and jj are neighbours. Thus, wijw_{ij} encodes the communication graph.

Denote

x=(−x1T−⋮−xnT−)∈Rn×p,g(x)=∑i=1ngi(xi),andf(x)=∑i=1nfi(xi).(4)\mathbf{x}=\begin{pmatrix}-x_1^{\mathsf{T}}-\\ \vdots\\ -x_n^{\mathsf{T}}-\end{pmatrix}\in\mathbb{R}^{n\times p},\quad g(\mathbf{x})=\sum_{i=1}^{n}g_i(x_i),\quad\text{and}\quad f(\mathbf{x})=\sum_{i=1}^{n}f_i(x_i). \tag*{(4)}

Under this notation, the iteration for PG-EXTRA (2) can be expressed compactly as

uk=uk−1+Wxk−(I+W2)xk−1−τ(∇f(xk)−∇f(xk−1))(5)\mathbf{u}^k=\mathbf{u}^{k-1}+W\mathbf{x}^k-\left(\frac{I+W}{2}\right)\mathbf{x}^{k-1}-\tau\left(\nabla f(\mathbf{x}^k)-\nabla f(\mathbf{x}^{k-1})\right) \tag*{(5)}
xk+1=prox⁡τg(uk).(6)\mathbf{x}^{k+1}=\operatorname{prox}_{\tau g}(\mathbf{u}^k). \tag*{(6)}

Defining K=((I−W)/2)1/2K=((I-W)/2)^{1/2} and qk=∑t=0kKxt\mathbf{q}^k=\sum_{t=0}^{k}K\mathbf{x}^t, Shi, Ling, Wu, and Yin [13 Thm. 2] proved that PG-EXTRA has the following ergodic convergence rates for the successive iterates, first-order optimality, and consensus residuals:

1k∑t=1k(∥xt+1−xt∥(I+W)/22+∥qt+1−qt∥2)=O(1k),(7)\frac{1}{k}\sum_{t=1}^{k}\left(\left\|\mathbf{x}^{t+1}-\mathbf{x}^t\right\|_{(I+W)/2}^{2}+\left\|\mathbf{q}^{t+1}-\mathbf{q}^t\right\|^2\right)=O\left(\frac{1}{k}\right), \tag*{(7)}

there exists rt∈∂g(xt)\mathbf{r}^t\in\partial g(\mathbf{x}^t) such that

1k∑t=1k∥τ∇f(xt)+τrt+Kqt∥(I+W)/22=O(1k),(8)\frac{1}{k}\sum_{t=1}^{k}\left\|\tau\nabla f(\mathbf{x}^t)+\tau\mathbf{r}^t+K\mathbf{q}^t\right\|_{(I+W)/2}^{2}=O\left(\frac{1}{k}\right), \tag*{(8)}

and

1k∑t=1k∥Kxt∥2=O(1k).(9)\frac{1}{k}\sum_{t=1}^{k}\left\|K\mathbf{x}^t\right\|^2=O\left(\frac{1}{k}\right). \tag*{(9)}

In general, PG-EXTRA is known to have sublinear non-ergodic convergence rate in the worst case, in terms of the distance to the solution [14]. In the specific case where g1=⋯=gn=0g_1=\cdots=g_n=0 and f1,…,fnf_1,\ldots,f_n are strongly convex, PG-EXTRA is known to converge linearly, again in terms of the distance to the solution [8, 15].

Convergence rates and acceleration techniques

Given an operator T:Rp→RpT : \mathbb{R}^{p} \to\mathbb{R}^{p}, the associated fixed point problem is

find x∈Rp s.t. x=T(x).\text{find } x \in\mathbb{R}^{p} \text{ s.t. } x = T(x).

The (squared) fixed point residual associated with TT at xx can be defined by ∥x−T(x)∥2\lVert x-T(x)\rVert^{2}. Using this framework, the convergence rates (5) can all be derived from a convergence rate in terms of the fixed point residual, following from casting (1) as a fixed point problem for a particular operator.

Many methods from convex optimisation can be cast as fixed point iterations, such as the proximal-gradient [16], Douglas-Rachford [17, 18], primal-dual hybrid gradient [19, 20], and Condat–Vũ [21, 22] algorithms. In other words, we can define an operator TT such that the main iteration of the algorithms can be compactly expressed as

xk+1=T(xk).x^{k+1} = T(x^{k}).

By analysing these algorithms as fixed point iterations, one can show that they have non-ergodic o(1/k)o(1/k) convergence rates in terms of the fixed point residual [20, 23]. These convergence rates follow from the general theory of Krasnosel’skii–Mann iterations [24, 25], which enjoys a non-ergodic o(1/k)o(1/k) convergence rate [26, 27]. This connection explains the convergence rates for PG-EXTRA given in (5), as PG-EXTRA can be understood as an instance of the Condat–Vũ algorithm, and motivates studying acceleration techniques for fixed point algorithms.

Acceleration in the context of fixed point algorithms has attracted attention in recent years. Halpern iterations [28] have been used to achieve a non-ergodic convergence rate of O(1/k2)O(1/k^{2}) in terms of the fixed point residual [29, 30]. Other works have used the concept of Nesterov momentum updates [31] to achieve a non-ergodic convergence rate of o(1/k2)o(1/k^{2}) [32, 33], also in terms of the fixed point residual. This approach has also been used to develop accelerated algorithms for structured (non-distributed) convex minimisation [34, 35].

Given the developments in accelerated fixed point algorithms, one may ask: how can decentralised algorithms for solving (1) achieve similar convergence rates without restricting the class of problems? Currently, the few existing works require restrictive assumptions to achieve accelerated convergence rates, with no rates provided for the successive iterates or optimality conditions. In the setting of g1=⋯=gn=0g_{1} = \cdots= g_{n} = 0, [36] proposed an algorithm that combines distributed gradient descent [6, 7] with gradient tracking [37], and achieves a non-ergodic convergence rate of O(1/k2)O(1/k^{2}) in terms of the objective values. The same authors later proposed an algorithm [38] which incorporates Nesterov momentum updates to achieve a non-ergodic rate of O(1/k2.8−ε)O(1/k^{2.8-\varepsilon}) with ε∈(0,2.8)\varepsilon\in(0, 2.8), again in terms of objective values. Given additional strong assumptions, e.g. strong convexity of f1,…,fnf_{1}, \ldots, f_{n}, some works have developed accelerated algorithms with near-optimal (linear) convergence rates [39]. Note that, given these assumptions, linear convergence is expected of decentralised proximal-gradient algorithms [14], and hence acceleration focuses on optimising the convergence rate coefficient.

In this work, we consider the setting of (1) without additional assumptions, that is the general setting of PG-EXTRA. Since (1) can be cast as a fixed point problem via its first-order optimality condition, we draw on the existing body of accelerated fixed point algorithms to develop an accelerated decentralised algorithm. In particular, the (generalised) Fast Krasnosel’skiĭ–Mann algorithm [32, 33] uses momentum updates to achieve a non-ergodic o(1/k2)o(1/k^2) convergence rate in terms of the fixed point residuals.

Contribution

We propose Fast PG-EXTRA (10), a decentralised proximal-gradient-type algorithm applicable to (1). Given a mixing matrix WW, step size τ<1+λmin⁡(W)L\tau< \frac{1+\lambda_{\min}(W)}{L}, and parameters α>2\alpha> 2, β>0\beta> 0, ρ∈(1,α−1)\rho\in(1,\alpha-1), δ=1+λmin⁡(W)2τL\delta= \frac{1+\lambda_{\min}(W)}{2\tau L} and s∈(0,2−1/(2δ)]s \in(0,2-1/(2\delta)], the main iteration for our algorithm is

uk=uk−1+xk−xk−1−vk−τ(∇f(xk)−∇f(xk−1))x‾k=prox⁡τg(uk)xk+1=(1−sρk+β)xk+(1−s)(k+β−α)k+β(xk−xk−1)+sρk+βx‾k+s(k+β−α)k+β(x‾k−x‾k−1)vk+1=k+β−αk+βvk+(W−I2)(2sρk+βxk+2s(k+β−α)k+β(xk−xk−1)−2sρk+βx‾k−2s(k+β−α)k+β(x‾k−x‾k−1)).(10)\begin{aligned} \mathbf{u}^{k} &= \mathbf{u}^{k-1}+\mathbf{x}^{k}-\mathbf{x}^{k-1}-\mathbf{v}^{k}-\tau\left(\nabla f(\mathbf{x}^{k})-\nabla f(\mathbf{x}^{k-1})\right) \\ \overline{\mathbf{x}}^{k} &= \operatorname{prox}_{\tau g}(\mathbf{u}^{k}) \\ \mathbf{x}^{k+1} &= \left(1-\frac{s\rho}{k+\beta}\right)\mathbf{x}^{k}+\frac{(1-s)(k+\beta-\alpha)}{k+\beta}\left(\mathbf{x}^{k}-\mathbf{x}^{k-1}\right) \\ &\quad+\frac{s\rho}{k+\beta}\overline{\mathbf{x}}^{k}+\frac{s(k+\beta-\alpha)}{k+\beta}\left(\overline{\mathbf{x}}^{k}-\overline{\mathbf{x}}^{k-1}\right) \\ \mathbf{v}^{k+1} &= \frac{k+\beta-\alpha}{k+\beta}\mathbf{v}^{k}+\left(\frac{W-I}{2}\right)\left(\frac{2s\rho}{k+\beta}\mathbf{x}^{k}+\frac{2s(k+\beta-\alpha)}{k+\beta}\left(\mathbf{x}^{k}-\mathbf{x}^{k-1}\right)\right. \\ &\quad\left.-\frac{2s\rho}{k+\beta}\overline{\mathbf{x}}^{k}-\frac{2s(k+\beta-\alpha)}{k+\beta}\left(\overline{\mathbf{x}}^{k}-\overline{\mathbf{x}}^{k-1}\right)\right). \tag*{(10)} \end{aligned}

We term (10) Fast PG-EXTRA as it can be viewed as an accelerated variant of the PG-EXTRA algorithm in the following sense: taking the view of PG-EXTRA as an instance of the Condat–Vũ algorithm [40, 41] and hence a Krasnosel’skiĭ–Mann iteration, the derivation of Fast PG-EXTRA matches that of PG-EXTRA except for adding a momentum update to the underlying Krasnosel’skiĭ–Mann iteration. Moreover, Fast PG-EXTRA has non-ergodic convergence rates of o(1/k2)o(1/k^2), compared to the ergodic rates of O(1/k)O(1/k) for PG-EXTRA. The main point of difference is the order, 1/k21/k^2 versus 1/k1/k, rather than ergodicity or big-OO versus little-oo as we prove that, in general, PG-EXTRA has non-ergodic o(1/k)o(1/k) convergence rates. This result resolves an open question posed in [13] (see Appendix § 7).

To aid comparison between PG-EXTRA and our proposed algorithm, observe that the main iteration for PG-EXTRA (4) can be alternately expressed as

uk=uk−1+xk−xk−1−vk−τ(∇f(xk)−∇f(xk−1))x‾k+1=prox⁡τg(uk)vk+1=(I−W2)(2xk+1−xk).(11)\begin{aligned} \mathbf{u}^{k} &= \mathbf{u}^{k-1}+\mathbf{x}^{k}-\mathbf{x}^{k-1}-\mathbf{v}^{k}-\tau\left(\nabla f(\mathbf{x}^{k})-\nabla f(\mathbf{x}^{k-1})\right) \\ \overline{\mathbf{x}}^{k+1} &= \operatorname{prox}_{\tau g}(\mathbf{u}^{k}) \\ \mathbf{v}^{k+1} &= \left(\frac{I-W}{2}\right)\left(2\mathbf{x}^{k+1}-\mathbf{x}^{k}\right). \tag*{(11)} \end{aligned}

Here, the uk\mathbf{u}^{k} updates in (10) and (11) are the same, and the x‾k\overline{\mathbf{x}}^{k} update in (10) coincides with the xk+1\mathbf{x}^{k+1} update in (11). The main differences are a recursively defined vk+1\mathbf{v}^{k+1} sequence in (10), and the xk+1\mathbf{x}^{k+1} sequence in (10) is a linear combination of previous iterates and proximal evaluations. The effects of the parameters ss, ρ\rho, α\alpha, and β\beta are explored in § 4, motivated by the numerical experiments in [32, 33].

The remainder of this paper is organised as follows. The remainder of § 1 covers background information on convex optimisation and operator theory. § 2 details an accelerated variant of the Condat–Vũ algorithm [21, 22] for (non-distributed) convex optimisation. § 3 uses the accelerated Condat–Vũ algorithm to prove convergence of our proposed distributed algorithm. § 4 provides numerical experiments to validate the convergence analysis of Fast PG-EXTRA. Finally, § 5 summarises the contributions of this paper and discusses future directions.

Notation and preliminaries

We will use normal letters to denote elements of Rp\mathbb{R}^{p} and bold letters for elements of Rn×p\mathbb{R}^{n \times p}, as shown in (4). The diagonal subspace of Rn×p\mathbb{R}^{n \times p} is denoted by R1={(x,…,x)∈Rn×p∣x∈Rp}\mathbb{R}1 = \{(x,\ldots,x) \in\mathbb{R}^{n \times p} \mid x \in\mathbb{R}^{p}\}, and I:Rp→RpI : \mathbb{R}^{p} \to\mathbb{R}^{p} denotes the identity operator. The Landau symbols are denoted by O(⋅)O(\cdot) and o(⋅)o(\cdot), ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle and ∥⋅∥\|\cdot\| denote the standard inner product and induced norm on Rp\mathbb{R}^{p}, respectively, and, given a positive definite matrix M:Rp→RpM : \mathbb{R}^{p} \to\mathbb{R}^{p}, ⟨⋅,⋅⟩M\langle\cdot,\cdot\rangle_{M} and ∥⋅∥M\|\cdot\|_{M} denote the inner product and norm induced by MM on Rp\mathbb{R}^{p}, respectively.

Communication networks and matrices

Given a real symmetric matrix MM, the largest and smallest eigenvalues of MM are denoted λmax⁡(M)\lambda_{\max}(M) and λmin⁡(M)\lambda_{\min}(M), respectively, and the kernel of MM is denoted ker⁡M\ker M. The Loewner order is denoted by ⪰\succeq, and the vector of ones is denoted by 1=(1,…,1)T∈Rn\mathbf{1} = (1,\ldots,1)^{\mathsf{T}} \in\mathbb{R}^{n}.

As discussed in § 1.1, communication amongst agents is modelled by a connected graph, (V,E)(\mathcal{V},\mathcal{E}), where V={1,…,n}\mathcal{V} = \{1,\ldots,n\} is the set of nodes and E\mathcal{E} is the set of edges. Each node i∈Vi \in\mathcal{V} represents an agent, and agents ii and jj can communicate only if (i,j)∈E(i,j) \in\mathcal{E}. Communication between neighbours is modelled using a mixing matrix, which is defined as follows.

Definition 1.1 (Mixing matrix [8]) A matrix W=(wij)∈Rn×nW = (w_{ij}) \in\mathbb{R}^{n \times n} is a mixing matrix if it satisfies the following properties.

(i) (Decentralised) wij=0w_{ij} = 0 if i≠ji \ne j and (i,j)∉E(i,j) \notin\mathcal{E},

(ii) (Symmetric) W=WTW = W^{\mathsf{T}},

(iii) (Null space) ker⁡(I−W)=R1\ker(I-W) = \mathbb{R}1, and

(iv) (Spectrum) −I≺W⪯I-I \prec W \preceq I.

Given a mixing matrix WW, agent ii communicating with their neighbouring agents is modelled by ∑j=1nwijxj\sum_{j=1}^{n} w_{ij}x_{j}, where xjx_{j} is the local variable of agent j∈{1,…,n}j \in\{1,\ldots,n\}.

Using the stacked vector notation (4), the matrix-vector product WxW\mathbf{x} then models a round of communication amongst all agents.

Convex functions

The domain of a function f:Rp→R∪{+∞}f:\mathbb{R}^{p}\to\mathbb{R}\cup\{+\infty\} is denoted dom⁡f={x∈Rp∣f(x)<+∞}\operatorname{dom} f=\{x\in\mathbb{R}^{p}\mid f(x)<+\infty\}. A function ff is proper if dom⁡f≠∅\operatorname{dom} f\ne\varnothing and f(x)>−∞f(x)>-\infty for all x∈Rpx\in\mathbb{R}^{p}, and ff is lower semicontinuous (lsc) if f(x)≤lim inf⁡u→xf(u)f(x)\le\liminf_{u\to x}f(u) for all x∈Rpx\in\mathbb{R}^{p}. The Fenchel conjugate of a function f:Rp→R∪{+∞}f:\mathbb{R}^{p}\to\mathbb{R}\cup\{+\infty\} is denoted f∗:x↦sup⁡u∈Rp(⟨x,u⟩−f(u))f^{*}:x\mapsto\sup_{u\in\mathbb{R}^{p}}(\langle x,u\rangle-f(u)).

The indicator function for a set CC is denoted ιC(x)\iota_{C}(x) and takes the value ιC(x)=0\iota_{C}(x)=0 if x∈Cx\in C, and is +∞+\infty otherwise. Given a proper lsc convex function f:Rp→R∪{+∞}f:\mathbb{R}^{p}\to\mathbb{R}\cup\{+\infty\}, the subdifferential of ff at a point x∈Rpx\in\mathbb{R}^{p} is defined as

∂f(x)={u∈Rp∣⟨y−x,u⟩+f(x)≤f(y), ∀y∈Rp}\partial f(x)=\{u\in\mathbb{R}^{p}\mid\langle y-x,u\rangle+f(x)\le f(y),\ \forall y\in\mathbb{R}^{p}\}

if x∈dom⁡fx\in\operatorname{dom} f, and ∂f(x)=∅\partial f(x)=\varnothing if x∉dom⁡f.The∗proximaloperator∗ofx\notin\operatorname{dom} f. The *proximal operator* off$ is given by

prox⁡f(x)=arg min⁡y∈Rp{f(y)+12∥x−y∥2},∀x∈Rp,\operatorname{prox}_{f}(x)=\mathop{\operatorname{arg\,min}}_{y\in\mathbb{R}^{p}}\left\{f(y)+\frac{1}{2}\lVert x-y\rVert^{2}\right\},\quad\forall x\in\mathbb{R}^{p},

and the proximal operator of ιC\iota_{C} is the projection onto the set CC, denoted proj⁡C(x)=prox⁡ιC(x)\operatorname{proj}_{C}(x)=\operatorname{prox}_{\iota_{C}}(x).

Operators

The set of fixed points of an operator A:Rp→RpA:\mathbb{R}^{p}\to\mathbb{R}^{p} is denoted Fix⁡A={x∈Rp:x=A(x)}\operatorname{Fix}A=\{x\in\mathbb{R}^{p}:x=A(x)\}. An operator A:Rp→RpA:\mathbb{R}^{p}\to\mathbb{R}^{p} is LL-Lipschitz continuous if L≥0L\ge0 and

∥A(x)−A(x′)∥≤L∥x−x′∥,∀x,x′∈dom⁡A,\lVert A(x)-A(x')\rVert\le L\lVert x-x'\rVert,\quad\forall x,x'\in\operatorname{dom} A,

is nonexpansive if it is 11-Lipschitz continuous, and is θ\theta-averaged if θ∈(0,1)\theta\in(0,1) and there exists a nonexpansive operator R:Rp→RpR:\mathbb{R}^{p}\to\mathbb{R}^{p} such that A=(1−θ)I+θRA=(1-\theta)I+\theta R. In a slight abuse of terminology, it will sometimes be convenient to refer to a nonexpansive operator as a 11-averaged operator.

Fast Condat–Vũ algorithm

In this section, we propose an accelerated variant of the Condat–Vũ algorithm [21, 22] for (non-distributed) convex minimisation. This algorithm will then be used to derive an accelerated variant of PG-EXTRA in § 3.

To this end, consider the convex minimisation problem

min⁡x∈Rpg(x)+f(x)+h(Kx),(12)\min_{x\in\mathbb{R}^{p}} g(x)+f(x)+h(Kx), \tag*{(12)}

where g:Rp→R∪{+∞}g:\mathbb{R}^{p}\to\mathbb{R}\cup\{+\infty\} and h:Rd→R∪{+∞}h:\mathbb{R}^{d}\to\mathbb{R}\cup\{+\infty\} are proper lsc convex, f:Rp→Rf:\mathbb{R}^{p}\to\mathbb{R} is convex and differentiable with LL-Lipschitz continuous gradient, and K:Rp→RdK:\mathbb{R}^{p}\to\mathbb{R}^{d} is linear. The Condat–Vũ algorithm is well suited to solving (12) due to the structure of the objective function, namely the sum of nonsmooth, smooth, and composite terms, and avoids having to compute terms such as prox⁡g+f\operatorname{prox}_{g+f} or prox⁡h∘K\operatorname{prox}_{h\circ K}.

By writing hh in terms of its conjugate, (12) becomes the saddle point problem

min⁡x∈Rpmax⁡y∈Rdg(x)+f(x)−h∗(y)+⟨Kx,y⟩.(13)\min_{x\in\mathbb{R}^{p}}\max_{y\in\mathbb{R}^{d}} g(x) + f(x) - h^{*}(y) + \langle Kx,y\rangle. \tag*{(13)}

A sufficient condition for the existence of a saddle point of (13) is that

0∈ri⁡(Kdom⁡g−dom⁡h),(14)0 \in\operatorname{ri}(K\operatorname{dom}g-\operatorname{dom}h), \tag*{(14)}

where ri⁡S\operatorname{ri}S denotes the relative interior of a set SS [42 15.23, 19.1]. For further discussion of the existence of saddle points, see [43 §7].

Assuming saddle points of (13) exist, then z=(xy)∈Rp×Rdz=\binom{x}{y}\in\mathbb{R}^{p}\times\mathbb{R}^{d} is a saddle point of (13) if and only if x∈Rpx\in\mathbb{R}^{p} solves (12) and y∈Rdy\in\mathbb{R}^{d} solves the Fenchel dual problem given by

max⁡y∈Rd−(g+f)∗(−KTy)−h∗(y).\max_{y\in\mathbb{R}^{d}} -(g+f)^{*}(-K^{\mathsf{T}}y)-h^{*}(y).

Given step sizes τ>0\tau>0 and σ>0\sigma>0, the Condat–Vũ operator T:Rp×Rd→Rp×RdT:\mathbb{R}^{p}\times\mathbb{R}^{d}\to\mathbb{R}^{p}\times\mathbb{R}^{d} is defined as

T((xy))=(x‾y‾)=(prox⁡τg(x−τKTy−τ∇f(x))prox⁡σh∗(y+σK(2x‾−x))).(15)T\left(\binom{x}{y}\right)=\binom{\overline{x}}{\overline{y}}=\binom{\operatorname{prox}_{\tau g}(x-\tau K^{\mathsf{T}}y-\tau\nabla f(x))}{\operatorname{prox}_{\sigma h^{*}}(y+\sigma K(2\overline{x}-x))}. \tag*{(15)}

The Condat–Vũ algorithm can be viewed as an instance of the Krasnosel’skiĭ–Mann algorithm [24, 25] applied to the Condat–Vũ operator. More precisely, given an initial point (x00y00)∈Rp×Rd\binom{x_{0}^{0}}{y_{0}^{0}}\in\mathbb{R}^{p}\times\mathbb{R}^{d} and parameter ρ∈R\rho\in\mathbb{R}, the Condat–Vũ algorithm can be compactly expressed as

(xk+1yk+1)=(1−ρ)(xkyk)+ρT((xkyk)).(16)\binom{x^{k+1}}{y^{k+1}}=(1-\rho)\binom{x^{k}}{y^{k}}+\rho T\left(\binom{x^{k}}{y^{k}}\right). \tag*{(16)}

Using the definition of TT, (16) can be unravelled as

x‾k=prox⁡τg(xk−τKTyk−τ∇f(xk))y‾k=prox⁡σh∗(yk+σK(2x‾k−xk))(xk+1yk+1)=(1−ρ)(xkyk)+ρ(x‾ky‾k).(17)\begin{aligned} \overline{x}^{k}&=\operatorname{prox}_{\tau g}(x^{k}-\tau K^{\mathsf{T}}y^{k}-\tau\nabla f(x^{k})) && \\ \overline{y}^{k}&=\operatorname{prox}_{\sigma h^{*}}(y^{k}+\sigma K(2\overline{x}^{k}-x^{k})) && \\ \binom{x^{k+1}}{y^{k+1}}&=(1-\rho)\binom{x^{k}}{y^{k}}+\rho\binom{\overline{x}^{k}}{\overline{y}^{k}}. && \tag*{(17)} \end{aligned}
y‾k=prox⁡σh∗(yk+σK(2x‾k−xk))(18)\overline{y}^{k}=\operatorname{prox}_{\sigma h^{*}}(y^{k}+\sigma K(2\overline{x}^{k}-x^{k})) \tag*{(18)}
(xk+1yk+1)=(1−ρ)(xkyk)+ρ(x‾ky‾k).(19)\binom{x^{k+1}}{y^{k+1}}=(1-\rho)\binom{x^{k}}{y^{k}}+\rho\binom{\overline{x}^{k}}{\overline{y}^{k}}. \tag*{(19)}

We now recall some properties of the Condat–Vũ operator (see, for example, [21]). Let M:Rp×Rd→Rp×RdM:\mathbb{R}^{p}\times\mathbb{R}^{d}\to\mathbb{R}^{p}\times\mathbb{R}^{d} denote the block matrix given by

M=[1τI−KT−K1σI].M=\begin{bmatrix} \frac{1}{\tau}I & -K^{\mathsf{T}}\\ -K & \frac{1}{\sigma}I \end{bmatrix}.

Lemma 2.1 Suppose that τL2+τσ∥K∥2<1\frac{\tau L}{2}+\tau\sigma\lVert K\rVert^2<1 and denote δ:=1τL(1−τσ∥K∥2)>12\delta:=\frac{1}{\tau L}(1-\tau\sigma\lVert K\rVert^2)>\frac{1}{2}. Then the following hold.

(i) TT is θ\theta-averaged w.r.t. ⟨⋅,⋅⟩M\langle\cdot,\cdot\rangle_M where θ=2δ4δ−1\theta=\frac{2\delta}{4\delta-1}.

(ii) z∈Fix⁡Tz\in\operatorname{Fix}T if and only if z=(xy)z=\begin{pmatrix}x\\y\end{pmatrix} is a saddle point of (13).

Proof. (i) Follows by combining the proofs of Theorem 3.1 and Lemma 4.4 in [21].

(ii) From the definition of TT in (15) and the proximal operator, it follows that z∈Fix⁡Tz\in\operatorname{Fix}T if and only if z=(xy)z=\begin{pmatrix}x\\y\end{pmatrix} satisfies

(00)∈(∂g(x)+KTy+∇f(x)∂h∗(y)−Kx)(20)\begin{pmatrix}0\\0\end{pmatrix}\in\begin{pmatrix}\partial g(x)+K^{\mathsf{T}}y+\nabla f(x)\\\partial h^*(y)-Kx \tag*{(20)}\end{pmatrix}

Since ff and (x,y)↦⟨Kx,y⟩(x,y)\mapsto\langle Kx,y\rangle have full domain, the subdifferential sum rule [42 Cor. 16.48] implies that (20) is equivalent to

(00)∈(∂x(g+⟨⋅,KTy⟩+f)(x)∂y(h∗−⟨Kx,⋅⟩)(y)).\begin{pmatrix}0\\0\end{pmatrix}\in\begin{pmatrix}\partial_x\left(g+\langle\cdot,K^{\mathsf{T}}y\rangle+f\right)(x)\\\partial_y\left(h^*-\langle Kx,\cdot\rangle\right)(y)\end{pmatrix}.

Through first-order optimality, this is equivalent to z=(xy)z=\begin{pmatrix}x\\y\end{pmatrix} being a saddle point of (13). □\square

We are now ready to present an accelerated variant of the Condat–Vũ algorithm, which can be understood as an instance of the generalised Fast Krasnosel’skiĭ–Mann algorithm applied to the Condat–Vũ operator. Our proposed Fast Condat–Vũ algorithm for solving (13) is given in Algorithm 1.

Remark 2.2 (Intuition for parameters) The parameter ss can be interpreted as controlling the contribution of TT, and is related to the averaged constant of TT, θ=2δ4δ−1\theta=\frac{2\delta}{4\delta-1}, by s∈(1/θ]s\in(1/\theta]. The parameters α\alpha and β\beta control the relative contribution of momentum terms such as k+β−αk+β(xˉk−xˉk−1)\frac{k+\beta-\alpha}{k+\beta}(\bar{x}^k-\bar{x}^{k-1}), with larger values of β\beta and α\alpha reducing their contribution. Finally, ρ\rho controls relaxation terms such as sρk+β(xˉk−xk)\frac{s\rho}{k+\beta}(\bar{x}^k-x^k), in a similar manner to the role played by ρ\rho in (16). For a discussion of parameter choices, see [33 §5.2].

We now state the main result on convergence of Algorithm (1) for a problem of the form (13).

Theorem 2.3 Suppose gg and hh are proper lsc convex, KK is linear, ff is convex and differentiable with LL-Lipschitz continuous gradient, the step sizes τ,σ>0\tau,\sigma>0 satisfy τL2+τσ∥K∥2<1\frac{\tau L}{2}+\tau\sigma\lVert K\rVert^2<1, and a saddle point of (13) exists (for example, (14) holds). Denote zk=(xkyk)∈Rp×Rdz^k=\begin{pmatrix}x^k\\y^k\end{pmatrix}\in\mathbb{R}^p\times\mathbb{R}^d, where (xk)k≥0(x^k)_{k\geq0} and (yk)k≥0(y^k)_{k\geq0} are the sequences generated by Algorithm 1. Then zk→z∗∈Rp×Rdz^k\to z^*\in\mathbb{R}^p\times\mathbb{R}^d, where z∗z^* is a saddle point of (13). Additionally,

∥zk+1−zk∥M2=o(1k2),(21)\lVert z^{k+1}-z^k\rVert_M^2=o\left(\frac{1}{k^2}\right), \tag*{(21)}

Algorithm 1 Fast Condat–Vũ algorithm for (13).

  1. Choose initial points xˉ0,xˉ1∈Rp\bar{x}^{0},\bar{x}^{1}\in\mathbb{R}^{p}, and yˉ0,yˉ1∈Rd\bar{y}^{0},\bar{y}^{1}\in\mathbb{R}^{d};

  2. Choose step sizes τ,σ>0\tau,\sigma>0;

  3. Choose parameters α>2\alpha>2, β>0\beta>0, and ρ∈(1,α−1)\rho\in(1,\alpha-1);

  4. Set δ=1L(1τ−σ∥K∥2)\delta=\frac{1}{L}\left(\frac{1}{\tau}-\sigma\|K\|^{2}\right) and choose s∈(0,2−1/(2δ)]s\in(0,2-1/(2\delta)];

  5. Initialise variables:

xˉ0=prox⁡τg(x0−τKTy0−τ∇f(x0))(22)\bar{x}^{0}=\operatorname{prox}_{\tau g}\left(x^{0}-\tau K^{\mathsf{T}}y^{0}-\tau\nabla f(x^{0})\right) \tag*{(22)}
yˉ0=prox⁡σh∗(y0+σK(2xˉ0−x0)).(23)\bar{y}^{0}=\operatorname{prox}_{\sigma h^{*}}\left(y^{0}+\sigma K(2\bar{x}^{0}-x^{0})\right). \tag*{(23)}
  1. for k≥1k\geq1 do

  1. Update variables:

xˉk=prox⁡τg(xk−τKTyk−τ∇f(xk))(24)\bar{x}^{k}=\operatorname{prox}_{\tau g}\left(x^{k}-\tau K^{\mathsf{T}}y^{k}-\tau\nabla f(x^{k})\right) \tag*{(24)}
yˉk=prox⁡σh∗(yk+σK(2xˉk−xk))(25)\bar{y}^{k}=\operatorname{prox}_{\sigma h^{*}}\left(y^{k}+\sigma K(2\bar{x}^{k}-x^{k})\right) \tag*{(25)}
xk+1=(1−sρk+β)xk+(1−s)(k+β−α)k+β(xk−xk−1)+sρk+βxˉk+s(k+β−α)k+β(xˉk−xˉk−1).(26)\begin{aligned} x^{k+1} ={}&\left(1-\frac{s\rho}{k+\beta}\right)x^{k} +\frac{(1-s)(k+\beta-\alpha)}{k+\beta}(x^{k}-x^{k-1})\\ &+\frac{s\rho}{k+\beta}\bar{x}^{k} +\frac{s(k+\beta-\alpha)}{k+\beta}(\bar{x}^{k}-\bar{x}^{k-1}). \tag*{(26)} \end{aligned}
yk+1=(1−sρk+β)yk+(1−s)(k+β−α)k+β(yk−yk−1)+sρk+βyˉk+s(k+β−α)k+β(yˉk−yˉk−1).(27)\begin{aligned} y^{k+1} ={}&\left(1-\frac{s\rho}{k+\beta}\right)y^{k} +\frac{(1-s)(k+\beta-\alpha)}{k+\beta}(y^{k}-y^{k-1})\\ &+\frac{s\rho}{k+\beta}\bar{y}^{k} +\frac{s(k+\beta-\alpha)}{k+\beta}(\bar{y}^{k}-\bar{y}^{k-1}). \tag*{(27)} \end{aligned}
  1. end for

and

∥zk−T(zk)∥M2=o(1k2).(28)\|z^{k}-T(z^{k})\|_{M}^{2}=o\left(\frac{1}{k^{2}}\right). \tag*{(28)}

Proof. Denote z0=(x0y0)z^{0}=\binom{x^{0}}{y^{0}} and z1=(x1y1)z^{1}=\binom{x^{1}}{y^{1}}. Then the generalised Fast Krasnosel’skiĭ–Mann algorithm [33 Alg. 1] applied to (1−s)I+sT(1-s)I+sT, where TT is the Condat–Vũ operator (15), yields the iteration

zk+1=(1−sρk+β)zk+(1−s)(k+β−α)k+β(zk−zk−1)+sρk+βT(zk)+s(k+β−α)k+β(T(zk)−T(zk−1)).\begin{aligned} z^{k+1} ={}&\left(1-\frac{s\rho}{k+\beta}\right)z^{k} +\frac{(1-s)(k+\beta-\alpha)}{k+\beta}(z^{k}-z^{k-1})\\ &+\frac{s\rho}{k+\beta}T(z^{k}) +\frac{s(k+\beta-\alpha)}{k+\beta}\left(T(z^{k})-T(z^{k-1})\right). \end{aligned}

Using the definition of TT in (15) and zk=(xkyk)z^{k}=\binom{x^{k}}{y^{k}} yields (22)–(27). Since τL2+τσ∥K∥2<1\frac{\tau L}{2}+\tau\sigma\|K\|^{2}<1, Lemma 2.1(i) implies that TT is θ\theta-averaged with respect to ⟨⋅,⋅⟩M\langle\cdot,\cdot\rangle_{M} with θ=2δ4δ−1∈(0,1]\theta=\frac{2\delta}{4\delta-1}\in(0,1]. Further, Lemma 2.1(ii) implies that Fix⁡T\operatorname{Fix}T is equal to the set of saddle points of (13). Altogether, applying [32 Thm. 3.3] yields that zk→z∗z^{k}\to z^{*} where z∗z^{*} is a saddle point of (13), and establishes (21)–(28). This completes the proof. □

Fast PG-EXTRA

In this section, we propose and analyse Fast PG-EXTRA, a decentralised proximal-gradient-type algorithm for solving (1). To this end, we reformulate (1) as

min⁡x∈Rn×pg(x)+f(x)+ι{0}(Kx),(29)\min_{x\in\mathbb{R}^{n\times p}} g(x) + f(x) + \iota_{\{0\}}(Kx), \tag*{(29)}

where xx, gg, and ff are defined in (4) and K=((I−W)/2)1/2K = ((I-W)/2)^{1/2}, where WW is a mixing matrix (see Definition 1.1). Then a point x∗∈Rn×px^* \in\mathbb{R}^{n\times p} solves (29) if and only if x∗=(x∗,…,x∗)Tx^* = (x^*,\ldots,x^*)^{\mathsf{T}} and x∗∈Rpx^* \in\mathbb{R}^p solves (1) [44 §11.3.3]. As was done in § 2, by writing ι{0}\iota_{\{0\}} in terms of its conjugate, solving (29) becomes

min⁡x∈Rn×pmax⁡y∈Rn×pg(x)+f(x)−ι{0}∗(y)+⟨Kx,y⟩.(30)\min_{x\in\mathbb{R}^{n\times p}}\max_{y\in\mathbb{R}^{n\times p}} g(x) + f(x) - \iota_{\{0\}}^*(y) + \langle Kx,y\rangle. \tag*{(30)}

Here, the sufficient condition (14) for the existence of a saddle point becomes

∅≠ri⁡(⋂i=1ndom⁡gi).(31)\varnothing\ne\operatorname{ri}\left(\bigcap_{i=1}^{n}\operatorname{dom}g_i\right). \tag*{(31)}

This follows from continuity of ff, ker⁡K=R1\ker K = \mathbb{R}1, and the fact that given nonempty convex sets C1,C2⊂Rn×pC_1, C_2 \subset\mathbb{R}^{n\times p}, we have that ri⁡(C1∩C2)=ri⁡C1∩ri⁡C2\operatorname{ri}(C_1 \cap C_2) = \operatorname{ri}C_1 \cap\operatorname{ri}C_2 and K(ri⁡C1)⊂ri⁡(KC1)K(\operatorname{ri}C_1) \subset\operatorname{ri}(KC_1) [45 Prop. 2.4, 2.5, 2.7]. Furthermore, assuming a saddle point of (30) exists, we have that there exists y∗∈Rn×py^* \in\mathbb{R}^{n\times p} such that z∗=(x∗y∗)∈Rn×p×Rn×pz^* = \binom{x^*}{y^*} \in\mathbb{R}^{n\times p} \times\mathbb{R}^{n\times p} solves (30) if and only if x∗=(x∗,…,x∗)∈Rn×px^* = (x^*,\ldots,x^*) \in\mathbb{R}^{n\times p} and x∗∈Rpx^* \in\mathbb{R}^p solves (1). Moreover, the latter statement holds if and only if there exists r∗∈∂g(x∗)r^* \in\partial g(x^*) and q∗∈ran⁡K=(R1)⊥q^* \in\operatorname{ran} K = (\mathbb{R}1)^\perp such that (r∗q∗)\binom{r^*}{q^*} satisfy the first-order optimality conditions [13 Lem. 1]

τ∇f(x∗)+τr∗+q∗=0andKx∗=0.(32)\tau\nabla f(x^*) + \tau r^* + q^* = 0 \quad\text{and}\quad Kx^* = 0. \tag*{(32)}

The derivation of Fast PG-EXTRA will use the Fast Condat–Vũ algorithm from § 2 applied to (30). The proposed algorithm is given in Algorithm 2. A similar correspondence can be used to derive PG-EXTRA from the Condat–Vũ algorithm. For further details, see [40, 41, 44].

The following theorem is our main result on convergence of Fast PG-EXTRA (Algorithm 2) for minimisation problems of the form (1).

Algorithm 2 Fast PG-EXTRA algorithm for (1).

1: Choose initial points x0,x1∈Rn×p\mathbf{x}^{0},\mathbf{x}^{1}\in\mathbb{R}^{n\times p}; 2: Choose a step size τ>0\tau>0, and mixing matrix W∈Rn×nW\in\mathbb{R}^{n\times n}; 3: Choose parameters α>2\alpha>2, β>0\beta>0, and ρ∈(1,α−1)\rho\in(1,\alpha-1); 4: Set δ=1+λmin⁡(W)2τL\delta=\frac{1+\lambda_{\min}(W)}{2\tau L} and choose s∈(0,2−12δ]s\in(0,2-\frac{1}{2\delta}]; 5: Initialise variables:

u0=x0−τ∇f(x0)(33)\mathbf{u}^{0}=\mathbf{x}^{0}-\tau\nabla f(\mathbf{x}^{0}) \tag*{(33)}
x‾0=prox⁡τg(u0)(34)\overline{\mathbf{x}}^{0}=\operatorname{prox}_{\tau g}(\mathbf{u}^{0}) \tag*{(34)}
v1=0.(35)\mathbf{v}^{1}=0. \tag*{(35)}

6: for k≥1k\ge1 do

7: Update variables:

uk=uk−1+xk−xk−1−vk−τ(∇f(xk)−∇f(xk−1))(36)\mathbf{u}^{k}=\mathbf{u}^{k-1}+\mathbf{x}^{k}-\mathbf{x}^{k-1}-\mathbf{v}^{k}-\tau\left(\nabla f(\mathbf{x}^{k})-\nabla f(\mathbf{x}^{k-1})\right) \tag*{(36)}
x‾k=prox⁡τg(uk)(37)\overline{\mathbf{x}}^{k}=\operatorname{prox}_{\tau g}(\mathbf{u}^{k}) \tag*{(37)}
xk+1=(1−sρk+β)xk+(1−s)(k+β−α)k+β(xk−xk−1)+sρk+βx‾k+s(k+β−α)k+β(x‾k−x‾k−1).(38)\begin{aligned} \mathbf{x}^{k+1}={}&\left(1-\frac{s\rho}{k+\beta}\right)\mathbf{x}^{k} +\frac{(1-s)(k+\beta-\alpha)}{k+\beta}\left(\mathbf{x}^{k}-\mathbf{x}^{k-1}\right)\\ &+\frac{s\rho}{k+\beta}\overline{\mathbf{x}}^{k} +\frac{s(k+\beta-\alpha)}{k+\beta}\left(\overline{\mathbf{x}}^{k}-\overline{\mathbf{x}}^{k-1}\right). \tag*{(38)} \end{aligned}
vk+1=k+β−αk+βvk+(W−I2)(sρk+βxk+s(k+β−α)k+β(xk−xk−1)−2sρk+βx‾k−2s(k+β−α)k+β(x‾k−x‾k−1)).(39)\begin{aligned} \mathbf{v}^{k+1}={}&\frac{k+\beta-\alpha}{k+\beta}\mathbf{v}^{k}\\ &+\left(\frac{W-I}{2}\right)\left(\frac{s\rho}{k+\beta}\mathbf{x}^{k} +\frac{s(k+\beta-\alpha)}{k+\beta}\left(\mathbf{x}^{k}-\mathbf{x}^{k-1}\right)\right.\\ &\left.-\frac{2s\rho}{k+\beta}\overline{\mathbf{x}}^{k} -\frac{2s(k+\beta-\alpha)}{k+\beta}\left(\overline{\mathbf{x}}^{k}-\overline{\mathbf{x}}^{k-1}\right)\right). \tag*{(39)} \end{aligned}

8: end for

Theorem 3.1 Consider the problem (1). Suppose g1,…,gng_1,\ldots,g_n are proper lsc convex, f1,…,fnf_1,\ldots,f_n are convex and differentiable with LL-Lipschitz continuous gradient, 0<τ<(1+λmin⁡(W))/L0<\tau<(1+\lambda_{\min}(W))/L, and a saddle point of (19 exists (for example, (31) holds). Then the sequences generated by Algorithm 2 satisfy xk→x∗=(x∗,…,x∗)T∈Rn×p\mathbf{x}^{k}\to\mathbf{x}^{*}=(x^{*},\ldots,x^{*})^{\mathsf{T}}\in\mathbb{R}^{n\times p}, where x∗∈Rpx^{*}\in\mathbb{R}^{p} is a solution of (1).

Additionally, define the sequence {qk}k≥1\{\mathbf{q}^{k}\}_{k\ge1} by qk=∑t=0k−1Kx‾t\mathbf{q}^{k}=\sum_{t=0}^{k-1}K\overline{\mathbf{x}}^{t}. Then

∥x‾k−xk∥(I+W)/22+∥qk+1−qk∥2=o(1k2),(40)\left\|\overline{\mathbf{x}}^{k}-\mathbf{x}^{k}\right\|_{(I+W)/2}^{2}+\left\|\mathbf{q}^{k+1}-\mathbf{q}^{k}\right\|^{2}=o\left(\frac{1}{k^{2}}\right), \tag*{(40)}

the point rk=1τ(uk−xˉk)∈∂g(xˉk)r^k=\frac{1}{\tau}(u^k-\bar{x}^k)\in\partial g(\bar{x}^k) satisfies

∥τ∇f(xˉk)+τrk+∑t=1kvt∥I+W22=o(1k2),(41)\left\|\tau\nabla f(\bar{x}^k)+\tau r^k+\sum_{t=1}^{k}v^t\right\|^2_{\frac{I+W}{2}}=o\left(\frac{1}{k^2}\right), \tag*{(41)}

and

∥Kxˉk∥2=o(1k2).(42)\left\|K\bar{x}^k\right\|^2=o\left(\frac{1}{k^2}\right). \tag*{(42)}

Proof. The Fast Condat–Vũ algorithm (Alg. 1) applied to (30) with y0=y1=0y^0=y^1=0 and σ=1τ\sigma=\frac{1}{\tau} yields the initialisation

xˉ0=prox⁡τg(x0−τ∇f(x0))(43)\bar{x}^0=\operatorname{prox}_{\tau g}(x^0-\tau\nabla f(x^0)) \tag*{(43)}
yˉ0=1τK(2xˉ0−x0).(44)\bar{y}^0=\frac{1}{\tau}K(2\bar{x}^0-x^0). \tag*{(44)}

and, for all k≥1k\ge1, the iteration

xˉk=prox⁡τg(xk−τK⊤yk−τ∇f(xk))(45)\bar{x}^k=\operatorname{prox}_{\tau g}(x^k-\tau K^\top y^k-\tau\nabla f(x^k)) \tag*{(45)}
yˉk=yk+1τK(2xˉk−xk)(46)\bar{y}^k=y^k+\frac{1}{\tau}K(2\bar{x}^k-x^k) \tag*{(46)}
xk+1=(1−sρk+β)xk+(1−s)(k+β−α)k+β(xk−xk−1)+sρk+βxˉk+s(k+β−α)k+β(xˉk−xˉk−1)(47)x^{k+1}=\left(1-\frac{s\rho}{k+\beta}\right)x^k+\frac{(1-s)(k+\beta-\alpha)}{k+\beta}(x^k-x^{k-1})+\frac{s\rho}{k+\beta}\bar{x}^k+\frac{s(k+\beta-\alpha)}{k+\beta}(\bar{x}^k-\bar{x}^{k-1}) \tag*{(47)}
yk+1=(1−sρk+β)yk+(1−s)(k+β−α)k+β(yk−yk−1)+sρk+βyˉk+s(k+β−α)k+β(yˉk−yˉk−1).(48)y^{k+1}=\left(1-\frac{s\rho}{k+\beta}\right)y^k+\frac{(1-s)(k+\beta-\alpha)}{k+\beta}(y^k-y^{k-1})+\frac{s\rho}{k+\beta}\bar{y}^k+\frac{s(k+\beta-\alpha)}{k+\beta}(\bar{y}^k-\bar{y}^{k-1}). \tag*{(48)}

Define sequences (uk)k≥0(u^k)_{k\ge0} and (vk)k≥1(v^k)_{k\ge1} according to

uk=xk−τKyk−τ∇f(xk)(49)u^k=x^k-\tau Ky^k-\tau\nabla f(x^k) \tag*{(49)}
vk=τK(yk−yk−1).(50)v^k=\tau K(y^k-y^{k-1}). \tag*{(50)}

Using (49) and (50), we deduce that

uk−uk−1+τ(∇f(xk)−∇f(xk−1))=xk−xk−1−τK(yk−yk−1)(51)u^k-u^{k-1}+\tau\bigl(\nabla f(x^k)-\nabla f(x^{k-1})\bigr)=x^k-x^{k-1}-\tau K(y^k-y^{k-1}) \tag*{(51)}
=xk−xk−1−vk.(52)=x^k-x^{k-1}-v^k. \tag*{(52)}

From (46), we deduce that

yˉk−yˉk−1=yk−yk−1+1τK(2(xˉk−xˉk−1)−(xk−xk−1)).(53)\bar{y}^k-\bar{y}^{k-1}=y^k-y^{k-1}+\frac{1}{\tau}K\left(2(\bar{x}^k-\bar{x}^{k-1})-(x^k-x^{k-1})\right). \tag*{(53)}

Then, substituting (46) followed by (53) into (48), we obtain

yk+1−yk=(1−s)(k+β−α)k+β(yk−yk−1)+sρk+β(yˉk−yk)+skk+β(yˉk−yˉk−1)=(1−s)(k+β−α)k+β(yk−yk−1)+sρk+β1τK(2xˉk−xk)+skk+β(yˉk−yˉk−1)=k+β−αk+β(yk−yk−1)+1τK(sρk+β(2xˉk−xk)+s(k+β−α)k+β(2(xˉk−xˉk−1)−(xk−xk−1))).(54)\begin{aligned} y^{k+1}-y^k &=\frac{(1-s)(k+\beta-\alpha)}{k+\beta}(y^k-y^{k-1})+\frac{s\rho}{k+\beta}(\bar{y}^k-y^k)+\frac{sk}{k+\beta}(\bar{y}^k-\bar{y}^{k-1})\\ &=\frac{(1-s)(k+\beta-\alpha)}{k+\beta}(y^k-y^{k-1})+\frac{s\rho}{k+\beta}\frac{1}{\tau}K(2\bar{x}^k-x^k)+\frac{sk}{k+\beta}(\bar{y}^k-\bar{y}^{k-1})\\ &=\frac{k+\beta-\alpha}{k+\beta}(y^k-y^{k-1})\\ &\quad+\frac{1}{\tau}K\left(\frac{s\rho}{k+\beta}(2\bar{x}^k-x^k)+\frac{s(k+\beta-\alpha)}{k+\beta}\left(2(\bar{x}^k-\bar{x}^{k-1})-(x^k-x^{k-1})\right)\right). \tag*{(54)} \end{aligned}

The initialisation (22) follows by substituting y0=y1=0y^0=y^1=0 into (27) to get (33) and (35), and combining (43) and (33) to get (34). The main update (23) is established as follows: (51) becomes (36), substituting (49) into (45) gives (37), (47) becomes (38), and applying τK\tau K to both sides of (54) together with the definitions of vk\mathbf{v}^k and KK yields (39). Thus, we have that Fast PG-EXTRA (Alg. 2) is an instance of Fast Condat–Vũ (Alg. 1).

Now, the definition of KK implies ∥K∥2=(1−λmin⁡(W))/2\lVert K\rVert^2=(1-\lambda_{\min}(W))/2 and hence τ<(1+λmin⁡(W))/L\tau<(1+\lambda_{\min}(W))/L implies τL/2+∥K∥2<1\tau L/2+\lVert K\rVert^2<1. Noting that a saddle point of (30) exists, Theorem 2.3 yields that (xˉk,yˉk)→(x∗,y∗)∈Rn×p×Rn×p(\bar{x}^k,\bar{y}^k)\to(x^*,y^*)\in\mathbb{R}^{n\times p}\times\mathbb{R}^{n\times p}, where (x∗,y∗)(x^*,y^*) is a saddle point of (30). From this, we deduce that x∗x^* is a solution of (29) and hence x∗=(x∗,…,x∗)⊤\mathbf{x}^*=(x^*,\ldots,x^*)^\top where x∗x^* is a solution of (1).

Additionally, combining Theorem 2.3, the definition of MM, the identity I=(I+W)/2+K2I=(I+W)/2+K^2 and (46) yields

o(1k2)=τ∥(xˉkyˉk)−(x∗y∗)∥M2=∥xk−xˉk∥2+τ2∥yk−yˉk∥2−2τ⟨K(xk−xˉk),yk−yˉk⟩=∥xk−xˉk∥(I+W)/22+∥xk−xˉk∥K22−2τ⟨K(xk−xˉk),yk−yˉk⟩+τ2∥yk−yˉk∥2=∥xk−xˉk∥(I+W)/22+∥K(xk−xˉk)−τ(yk−yˉk)∥2=∥xk−xˉk∥(I+W)/22+∥Kxˉk∥2.(55)\begin{aligned} o\left(\frac{1}{k^2}\right)=\tau\left\|\begin{pmatrix}\bar{x}^k\\ \bar{y}^k\end{pmatrix}-\begin{pmatrix}x^*\\ y^*\end{pmatrix}\right\|_M^2 = \lVert x^k-\bar{x}^k\rVert^2+\tau^2\lVert y^k-\bar{y}^k\rVert^2-2\tau\langle K(x^k-\bar{x}^k),y^k-\bar{y}^k\rangle\\ &= \lVert x^k-\bar{x}^k\rVert_{(I+W)/2}^2+\lVert x^k-\bar{x}^k\rVert_{K^2}^2-2\tau\langle K(x^k-\bar{x}^k),y^k-\bar{y}^k\rangle+\tau^2\lVert y^k-\bar{y}^k\rVert^2 \\ &= \lVert x^k-\bar{x}^k\rVert_{(I+W)/2}^2+\left\|K(x^k-\bar{x}^k)-\tau(y^k-\bar{y}^k)\right\|^2 \\ &= \lVert x^k-\bar{x}^k\rVert_{(I+W)/2}^2+\lVert K\bar{x}^k\rVert^2. \tag*{(55)} \end{aligned}

Since qk+1−qk=Kxˉkq^{k+1}-q^k=K\bar{x}^k, for all k≥1k\ge1, this establishes (40) and (42). Further, observe that, for all k≥1k\ge1, (45) and (49) implies that rk=1τ(uk−xˉk)∈∂g(xˉk)r^k=\frac{1}{\tau}(u^k-\bar{x}^k)\in\partial g(\bar{x}^k) satisfies

xk−xˉk=τ∇f(xk)+τrk+τKyk=τ∇f(xk)+τrk+∑t=1kvt,(56)x^k-\bar{x}^k=\tau\nabla f(x^k)+\tau r^k+\tau K y^k=\tau\nabla f(x^k)+\tau r^k+\sum_{t=1}^{k}v^t, \tag*{(56)}

where the second equality follows from (50) and y0=0y^0=0 since ∑t=1kvt=τK(yk−y0)=τKyk\sum_{t=1}^{k}v^t=\tau K(y^k-y^0)=\tau K y^k. Combining (55), (56), Young’s inequality, the observation that I+W2⪯I\frac{I+W}{2}\preceq I, LL-Lipschitz continuity of ∇f\nabla f, and the equivalence of ∥⋅∥(I+W)/2\lVert\cdot\rVert_{(I+W)/2} and ∥⋅∥\lVert\cdot\rVert in Rn×p\mathbb{R}^{n\times p}, we deduce that

∥τ∇f(xˉk)+τrk+∑t=1kvk∥(I+W)/22=∥τ∇f(x∗)+τrk+∑t=1kvk∥(I+W)/22+∥τ∇f(xˉk)−τ∇f(x∗)∥(I+W)/22+2⟨τ∇f(x∗)+τrk+∑t=1kvk,τ∇f(xˉk)−τ∇f(x∗)⟩(I+W)/2≤2∥τ∇f(xk)+τrk+∑t=1kvk∥(I+W)/22+2∥τ∇f(xˉk)−τ∇f(xk)∥(I+W)/22≤2∥τ∇f(xk)+τrk+∑t=1kvk∥(I+W)/22+2∥τ∇f(xˉk)−τ∇f(xk)∥2≤2∥τ∇f(xk)+τrk+∑t=1kvk∥(I+W)/22+2τ2L2∥xˉk−xk∥2=2∥xˉk−xk∥(I+W)/22+2τ2L2∥xˉk−xk∥2≤2(1+γτ2L2)∥xˉk−xk∥(I+W)/22,(57)\begin{aligned} \left\|\tau\nabla f(\bar{x}^k)+\tau r^k+\sum_{t=1}^{k}v^k\right\|_{(I+W)/2}^2 ={}&\left\|\tau\nabla f(x^*)+\tau r^k+\sum_{t=1}^{k}v^k\right\|_{(I+W)/2}^2\\ &+\left\|\tau\nabla f(\bar{x}^k)-\tau\nabla f(x^*)\right\|_{(I+W)/2}^2\\ &+2\left\langle\tau\nabla f(x^*)+\tau r^k+\sum_{t=1}^{k}v^k,\tau\nabla f(\bar{x}^k)-\tau\nabla f(x^*)\right\rangle_{(I+W)/2}\\ \le{}&2\left\|\tau\nabla f(x^k)+\tau r^k+\sum_{t=1}^{k}v^k\right\|_{(I+W)/2}^2+2\left\|\tau\nabla f(\bar{x}^k)-\tau\nabla f(x^k)\right\|_{(I+W)/2}^2\\ \le{}&2\left\|\tau\nabla f(x^k)+\tau r^k+\sum_{t=1}^{k}v^k\right\|_{(I+W)/2}^2+2\left\|\tau\nabla f(\bar{x}^k)-\tau\nabla f(x^k)\right\|^2\\ \le{}&2\left\|\tau\nabla f(x^k)+\tau r^k+\sum_{t=1}^{k}v^k\right\|_{(I+W)/2}^2+2\tau^2L^2\lVert\bar{x}^k-x^k\rVert^2\\ ={}&2\lVert\bar{x}^k-x^k\rVert_{(I+W)/2}^2+2\tau^2L^2\lVert\bar{x}^k-x^k\rVert^2\\ \le{}&2(1+\gamma\tau^2L^2)\lVert\bar{x}^k-x^k\rVert_{(I+W)/2}^2, \tag*{(57)} \end{aligned}

for some γ>0\gamma>0. Combining (57) with (40) establishes (41), which completes the proof. □

Remark 3.2 The convergence rates for Fast PG-EXTRA established in Theorem 3.1 improve on the equivalent rates for PG-EXTRA [13 Thm. 2] in several ways. Precisely, Theorem 3.1 provides o(1/k2)o(1/k^2) non-ergodic rates for the iterate, first-order optimality, and consensus residuals in Fast PG-EXTRA. In contrast, [13 Thm. 2] only provides O(1/k)O(1/k) ergodic rates for these quantities. The latter result can be improved to o(1/k)o(1/k) non-ergodic (see Appendix § 7), however this is still improved on by Theorem 3.1.

Numerical experiments

In this section, we numerically compare Fast PG-EXTRA (Algorithm 2) with two other decentralised prox-gradient algorithms applicable to the general setting of {(1)}: PG-EXTRA [8, 13] and NIDS [10]. Recall that, given a step size τ>0\tau> 0, parameter β>0\beta> 0, mixing matrix WW, and W~=I−β(I−W2)\widetilde{W}=I-\beta\left(\frac{I-W}{2}\right), the main iteration of NIDS is

uk=uk−1−xk+W~(2xk−xk−1−τ(∇f(xk)−∇f(xk−1)))(58)u^k=u^{k-1}-x^k+\widetilde{W}\left(2x^k-x^{k-1}-\tau\left(\nabla f(x^k)-\nabla f(x^{k-1})\right)\right) \tag*{(58)}
xk+1=prox⁡τg(uk)(59)x^{k+1}=\operatorname{prox}_{\tau g}(u^k) \tag*{(59)}

The algorithms are compared across two problems: (distributed) robust power state system estimation and l1l_1-regularised logistic regression. All experiments were implemented in Python 3.15.0 using NumPy v2.5.4 on a virtual machine running Windows 11 with 16GB RAM and one core of an AMD EPYC 7763 CPU @ 2.45 GHz.

For the algorithm parameters, we use constant step sizes τ=0.91+λmin⁡(W)L\tau=0.9\frac{1+\lambda_{\min}(W)}{L} in PG-EXTRA and Algorithm 2, and τ=0.9×2/L\tau=0.9\times2/L and β=0.9/∥τ(I−W)/2∥\beta=0.9/\lVert\tau(I-W)/2\rVert in NIDS. For the parameters in Algorithm 2, we follow the recommendations in [33 §5] and set s=0.9(2−1/(2δ))s=0.9(2-1/(2\delta)), β=α\beta=\alpha and ρ=1−η+η(α−1)\rho=1-\eta+\eta(\alpha-1) with η∈{0.1,0.5,0.8,0.95,1}\eta\in\{0.1,0.5,0.8,0.95,1\}. For the acceleration parameter α\alpha, we use the linear cooling heuristic α={αk}k=010000\alpha=\{\alpha^k\}_{k=0}^{10000}, where αk\alpha^k increases linearly from α0=5\alpha^0=5 to αk=500\alpha^k=500 for k≥5000k\geq5000. This heuristic is compared against a constant α=500\alpha=500 (using η=1\eta=1). Finally, we follow [13] in setting the initial point as x0=x1=0x^0=x^1=0 and, given a connected communication graph (V,E)(\mathcal{V},\mathcal{E}), setting the mixing matrix W=(wij)W=(w_{ij}) to be the Metropolis constant edge weight matrix [8, 46, 47], given by

wij={1max⁡{deg⁡(i),deg⁡(j)}+1i≠j, (i,j)∈E,0i≠j, (i,j)∉E,1−∑k∈V∖{i}wiki=j.w_{ij}= \begin{cases} \frac{1}{\max\{\deg(i),\deg(j)\}+1} & i\ne j,\ (i,j)\in\mathcal{E},\\ 0 & i\ne j,\ (i,j)\notin\mathcal{E},\\ 1-\sum_{k\in\mathcal{V}\setminus\{i\}}w_{ik} & i=j. \end{cases}

To facilitate a clear comparison between algorithms, we define for PG-EXTRA and NIDS the sequences xˉk=xk+1\bar{x}^k=x^{k+1}, where xk+1x^{k+1} are defined in {(4)} and {(35)} respectively. The reason for this is that, in Fast PG-EXTRA (Algorithm 2), xˉk\bar{x}^k is used to compute the fixed point residual, whereas xk+1x^{k+1} is the successive iterate. In PG-EXTRA and NIDS these quantities coincide. The sequence xˉk\bar{x}^k will be used to evaluate both the iterate residuals and the error in the first-order optimality conditions. To evaluate the latter, recall from {(21)} that we also require the sequences r∈∂g(xˉk)\mathbf{r}\in\partial g(\bar{x}^k) and qk∈ran⁡K\mathbf{q}^k\in\operatorname{ran}K. To that end, we define rk=1τ(uk−xˉk)\mathbf{r}^k=\frac{1}{\tau}(u^k-\bar{x}^k) and

  • (PG-EXTRA) qPk=∑t=0k−1Kxˉt\mathbf{q}_{P}^k=\sum_{t=0}^{k-1}K\bar{x}^t

  • (Alg. 2) qFk=∑t=0k−1Kx‾t\mathbf{q}_{F}^{k}=\sum_{t=0}^{k-1}K\overline{\mathbf{x}}^{t}

  • (NIDS) qNk=∑t=0k−1Kx‾t−τK(∇f(xk)−∇f(x0))\mathbf{q}_{N}^{k}=\sum_{t=0}^{k-1}K\overline{\mathbf{x}}^{t}-\tau K\left(\nabla f(\mathbf{x}^{k})-\nabla f(\mathbf{x}^{0})\right)

The definition of rk\mathbf{r}^{k} follows from the evaluation of the proximal operator in each algorithm. The sequences qk\mathbf{q}^{k} can be understood as the dual variables for each algorithm. The definitions above can be derived from the dual variable component of the underlying fixed point iteration, using the Condat–Vũ operator for PG-EXTRA and Algorithm 2 and the Davis-Yin operator for NIDS (see e.g. (A6)). With this notation, algorithm performance is then evaluated using the metrics described in Theorems 3.1 and A.1:

  1. The (squared) fixed point residual measures the residual in terms of the underlying fixed point operator. For PG-EXTRA, this is given in each iteration kk by

residual⁡k=∥x‾k−xk∥(I+W)/22+∥qPk+1−qPk∥2\operatorname{residual}^{k}=\left\|\overline{\mathbf{x}}^{k}-\mathbf{x}^{k}\right\|_{(I+W)/2}^{2}+\left\|\mathbf{q}_{P}^{k+1}-\mathbf{q}_{P}^{k}\right\|^{2}

for Fast PG-EXTRA it is given by

residual⁡k=∥x‾k−xk∥(I+W)/22+∥qFk+1−qFk∥2=o(1k2)\operatorname{residual}^{k}=\left\|\overline{\mathbf{x}}^{k}-\mathbf{x}^{k}\right\|_{(I+W)/2}^{2}+\left\|\mathbf{q}_{F}^{k+1}-\mathbf{q}_{F}^{k}\right\|^{2}=o\left(\frac{1}{k^{2}}\right)

and for NIDS it is given by

residual⁡k=∥x‾k−xk∥(I+W)/22+∥qNk+1−qNk∥2=o(1k)\operatorname{residual}^{k}=\left\|\overline{\mathbf{x}}^{k}-\mathbf{x}^{k}\right\|_{(I+W)/2}^{2}+\left\|\mathbf{q}_{N}^{k+1}-\mathbf{q}_{N}^{k}\right\|^{2}=o\left(\frac{1}{k}\right)
  1. The first-order optimality residuals measure the error in the optimality conditions in each iteration. For PG-EXTRA, these are given in each iteration kk by

optimality⁡k=∥τ∇f(x‾k)+τrk+KqPk∥(I+W)/22\operatorname{optimality}^{k}=\left\|\tau\nabla f(\overline{\mathbf{x}}^{k})+\tau\mathbf{r}^{k}+K\mathbf{q}_{P}^{k}\right\|_{(I+W)/2}^{2}
consensus⁡k=∥Kx‾k∥2,\operatorname{consensus}^{k}=\left\|K\overline{\mathbf{x}}^{k}\right\|^{2},

for Fast PG-EXTRA, they are

optimality⁡k=∥τ∇f(x‾k)+τrk+∑t=1kvt∥(I+W)/22\operatorname{optimality}^{k}=\left\|\tau\nabla f(\overline{\mathbf{x}}^{k})+\tau\mathbf{r}^{k}+\sum_{t=1}^{k}\mathbf{v}^{t}\right\|_{(I+W)/2}^{2}
consensus⁡k=∥Kx‾k∥2,\operatorname{consensus}^{k}=\left\|K\overline{\mathbf{x}}^{k}\right\|^{2},

and for NIDS, they are

optimality⁡k=∥τ∇f(x‾k)+τrk+τβKqNk∥(I+W)/22\operatorname{optimality}^{k}=\left\|\tau\nabla f(\overline{\mathbf{x}}^{k})+\tau\mathbf{r}^{k}+\tau\beta K\mathbf{q}_{N}^{k}\right\|_{(I+W)/2}^{2}
consensus⁡k=∥Kx‾k∥2.\operatorname{consensus}^{k}=\left\|K\overline{\mathbf{x}}^{k}\right\|^{2}.

The first quantity in the first-order optimality residuals measures the error in the optimality condition for the primal variable (see (30)). The second quantity measures the error in consensus amongst agents in each iteration. Note that the points (xˉk,KqPk)(\bar{x}^k,Kq_{\mathrm{P}}^k) for PG-EXTRA, (xˉk,∑t=1kvt)(\bar{x}^k,\sum_{t=1}^k v^t) for Fast PG-EXTRA, and (xˉk,KqNk)(\bar{x}^k,Kq_{\mathrm{N}}^k) for NIDS are all appropriate for measuring the error in the first-order optimality conditions (32), as KqPk∈ran⁡KKq_{\mathrm{P}}^k \in\operatorname{ran} K and KqNk∈ran⁡KKq_{\mathrm{N}}^k \in\operatorname{ran} K by definition and, following (50), we have that ∑t=1kvt=τKyk∈ran⁡K\sum_{t=1}^k v^t=\tau K y^k \in\operatorname{ran} K. Reporting the first-order optimality residuals in each iteration requires an additional gradient evaluation, ∇f(xˉk)\nabla f(\bar{x}^k), which can inflate algorithm runtime. In practice, one may simply measure the (squared) fixed point residual or the successive differences, ∥xk+1−xk∥2\lVert x^{k+1}-x^k\rVert^2.

Power system state estimation

Given a power system consisting of pp buses partitioned into nn control areas, measurement matrices Hi∈Rdi×pH_i \in\mathbb{R}^{d_i \times p}, and (potentially faulty) noisy measurements mi∈Rdim_i \in\mathbb{R}^{d_i}, we seek to estimate the state of the system u∗∈Rpu^* \in\mathbb{R}^p and the location of the faulty measurements v∗=(v1∗,…,vn∗)∈R∑idiv^*=(v_1^*,\ldots,v_n^*) \in\mathbb{R}^{\sum_i d_i}, where vij∗≠0v_{ij}^* \ne0 if measurement mijm_{ij} is faulty, and zero otherwise [48]. Denoting the measurement noise by ei∈Rdie_i \in\mathbb{R}^{d_i}, the system state is the solution to the linear model

mi=Hiu+vi+ei.m_i=H_i u+v_i+e_i.

The system state and location of the faulty measurements, (u∗,v∗)(u^*,v^*), can be estimated via least-squares with l1l_1-regularisation for vv. Given regularisation parameters λi>0\lambda_i>0, agents collectively seek a solution to the regularised problem

min⁡u,v∑i=1n12∥Hiu+vi−mi∥2+λi∥vi∥1.(60)\min_{u,v}\sum_{i=1}^{n}\frac{1}{2}\lVert H_i u+v_i-m_i\rVert^2+\lambda_i\lVert v_i\rVert_1. \tag*{(60)}

Problem (60) is of the form (1) with x=(u⊤,v⊤)⊤x=(u^\top,v^\top)^\top, fi(x)=12∥Hiu+vi−mi∥2f_i(x)=\frac{1}{2}\lVert H_i u+v_i-m_i\rVert^2, and gi(x)=λi∥vi∥1g_i(x)=\lambda_i\lVert v_i\rVert_1. The proximal and gradient operators can be computed by

prox⁡τgi(x)=(x⊤ v1⊤ … vi−1⊤ Sτλi(vi)⊤ vi+1⊤ … vn⊤)⊤\operatorname{prox}_{\tau g_i}(x)=\left(x^\top\ v_1^\top\ \ldots\ v_{i-1}^\top\ S_{\tau\lambda_i}(v_i)^\top\ v_{i+1}^\top\ \ldots\ v_n^\top\right)^\top

and

∇fi(x)=(Hi⊤(Hiu+vi−mi)Hiu+vi−mi)\nabla f_i(x)=\begin{pmatrix} H_i^\top(H_i u+v_i-m_i) \\ H_i u+v_i-m_i \end{pmatrix}

where Sγ(x)=sign⁡(x)max⁡{∣x∣−γ,0}S_\gamma(x)=\operatorname{sign}(x)\max\{\lvert x\rvert-\gamma,0\} denotes the soft thresholding operator [49], applied element-wise for vectors, and eje_j is the standard basis vector with one in the jjth position. Note that ∇fi\nabla f_i is LiL_i-Lipschitz continuous with Li=(∥Hi∥22+1)max⁡{∥Hi∥22,1}L_i=(\lVert H_i\rVert_2^2+1)\max\{\lVert H_i\rVert_2^2,1\}.

For the communication graph, we follow [50 §4] in using the IEEE 14-bus test case partitioned into n=4n=4 control areas, with corresponding measurement matrices HiH_i. The non-faulty measurements mim_i have entries sampled i.i.d. from U(−0.25,0.75)U(-0.25,0.75); to simulate faults, we follow [50] and uniformly sample MM entries across all measurements mim_i and multiply them by 1.2. The number of faulty measurements MM is sampled from U(1,⌊0.25∑i=1ndi⌋)U(1, \lfloor0.25\sum_{i=1}^{n} d_i\rfloor), such that at most 25% of measurements are faulty. Finally, λi\lambda_i are sampled i.i.d. from U(0.4,0.6)U(0.4, 0.6). Results are averaged over 20 realisations of mim_i and MM.

As illustrated in Figure 1, Algorithm 2 performs well in terms of the optimality residual compared to PG-EXTRA and is comparable to NIDS, whilst not performing worse than either PG-EXTRA or NIDS in terms of the iterate residuals and consensus error. The performance of Algorithm 2 is similar to that of NIDS, with the main difference being runtime. Table 1 shows that, for the optimality residuals, Algorithm 2 with α=500\alpha= 500 had a 60% decrease in iterations and runtime compared to PG-EXTRA. Whilst PG-EXTRA and NIDS had better performances in terms of iterate residuals, Algorithm 2 with α=500\alpha= 500 only took 1.3% longer on the same instances. However, NIDS took significantly fewer iterations to reduce the consensus error.

Figure 1. (Squared) fixed point residual and first-order optimality residuals versus iterations, for PSSE on one randomly generated instance.

MetricAlg.Iters.Time
Resid.PG-EXTRA648.0 (388)0.103 (0.062)
Resid.NIDS648.0 (383)0.191 (0.100)
Resid.Alg. 2, η=0.10\eta= 0.106239.0 (3621)1.220 (0.670)
Resid.Alg. 2, η=0.50\eta= 0.501319.0 (782)0.257 (0.146)
Resid.Alg. 2, η=0.80\eta= 0.80844.0 (504)0.169 (0.089)
Resid.Alg. 2, η=0.95\eta= 0.95717.5 (433)0.145 (0.084)
Resid.Alg. 2, η=1.00\eta= 1.00683.5 (415)0.132 (0.074)
Resid.Alg. 2, α=500\alpha= 500656.5 (393)0.119 (0.074)
Optim.PG-EXTRA1743.0 (955)0.390 (0.200)
Optim.NIDS647.0 (382)0.190 (0.120)
Optim.Alg. 2, η=0.10\eta= 0.106229.0 (3610)1.604 (0.921)
Optim.Alg. 2, η=0.50\eta= 0.501317.0 (780)0.358 (0.201)
Optim.Alg. 2, η=0.80\eta= 0.80843.0 (502)0.215 (0.124)
Optim.Alg. 2, η=0.95\eta= 0.95716.5 (432)0.176 (0.105)
Optim.Alg. 2, η=1.00\eta= 1.00682.5 (414)0.174 (0.104)
Optim.Alg. 2, α=500\alpha= 500655.5 (392)0.160 (0.096)
Consen.PG-EXTRA1681.5 (1214)0.271 (0.186)
Consen.NIDS1283.0 (894)0.340 (0.220)
Consen.Alg. 2, η=0.1\eta= 0.1––
Consen.Alg. 2, η=0.50\eta= 0.503417.5 (2474)0.664 (0.445)
Consen.Alg. 2, η=0.80\eta= 0.802158.5 (1566)0.411 (0.279)
Consen.Alg. 2, η=0.95\eta= 0.951825.5 (1325)0.351 (0.244)
Consen.Alg. 2, η=1.00\eta= 1.001736.5 (1261)0.317 (0.228)
Consen.Alg. 2, α=500\alpha= 5001702.5 (1229)0.320 (0.214)

Table 1. PSSE: median (minimum) iterations and median (minimum) runtime in seconds to reduce the error metric to 10−610^{-6} for residual and optimality, and to 10−1210^{-12} for consensus. Bolded entries are the best performance for a given metric. “–”: error larger than tolerance at 10 000 iterations.

Algorithm 2 performed better for larger values of η\eta, including the boundary value of η=1\eta= 1, which corresponds to ρ=α−1\rho= \alpha- 1 and is not supported by Theorem 3.1. Both α=500\alpha= 500 and the linear cooling heuristic were competitive with PG-EXTRA and NIDS in iterate residuals and first-order optimality, however using constant α=500\alpha= 500 consistently required fewer iterations to converge compared to the cooling heuristic.

Regularised logistic regression

Given a population of nn agents, sample matrices Ai∈Rdi×pA_i \in\mathbb{R}^{d_i \times p}, and label vectors bi∈{−1,+1}dib_i \in\{-1, +1\}^{d_i}, we seek to recover a weight vector u∗∈Rpu^* \in\mathbb{R}^{p} and intercept v∈Rv \in\mathbb{R} that minimise the average empirical logistic loss. Given regularisation parameters λi>0\lambda_i > 0, agents collectively seek a sparse solution to the regularised problem

min⁡u,v∑i=1nli(u,v)+λi∥u∥1(61)\min_{u,v} \sum_{i=1}^{n} l_i(u,v) + \lambda_i\lVert u\rVert_1 \tag*{(61)}

where

li(u,v)=1di∑j=1dilog⁡(1+exp⁡(−bij(⟨u,aij⟩+v))),l_i(u,v) = \frac{1}{d_i}\sum_{j=1}^{d_i}\log\left(1+\exp\left(-b_{ij}\left(\langle u,a_{ij}\rangle+v\right)\right)\right),

is the average logistic loss.

Problem (61) is of the form (1), with x⊤=(u⊤,v)x^\top=(u^\top,v), fi(x)=li(u,v)f_i(x)=l_i(u,v), and gi(x)=λi∥u∥1g_i(x)=\lambda_i\lVert u\rVert_1. Consequently, the proximal and gradient operators can be computed by

prox⁡τgi(x)=(Sτλi(u)v),and∇fi(x)=−1di(A~i⊤(1−pi(x))bi⊤(1−pi(x))),\operatorname{prox}_{\tau g_i}(x)=\begin{pmatrix}S_{\tau\lambda_i}(u)\\v\end{pmatrix},\quad\text{and}\quad\nabla f_i(x)=-\frac{1}{d_i}\begin{pmatrix}\widetilde{A}_i^\top(1-p_i(x))\\b_i^\top(1-p_i(x))\end{pmatrix},

where

A~i=diag⁡(bi1,…,bidi)Aiandpi(x)=1⊘(1+exp⁡(−A~iu−vbi)),\widetilde{A}_i=\operatorname{diag}(b_{i1},\ldots,b_{id_i})A_i\quad\text{and}\quad p_i(x)=1\oslash\left(1+\exp\left(-\widetilde{A}_iu-vb_i\right)\right),

with ⊘\oslash denoting Hadamard division. Note that ∇fi\nabla f_i is LiL_i-Lipschitz continuous with

Li=14di∥AiAi⊤+11⊤∥2.L_i=\frac{1}{4d_i}\left\lVert A_iA_i^\top+11^\top\right\rVert_2.

For the communication graph, we use a cycle communication graph (V,E)(\mathcal{V},\mathcal{E}) with V={1,…,20}\mathcal{V}=\{1,\ldots,20\} agents and E={(1,2),(2,3),…,(19,20),(20,1)}\mathcal{E}=\{(1,2),(2,3),\ldots,(19,20),(20,1)\}. We follow [51] in using the following datasets for the sample matrices AiA_i and label vectors bib_i: colon-cancer with (p,d)=(2000,62)(p,d)=(2000,62), and the first two hundred samples of the real-sim dataset with (p,d)=(20958,200)(p,d)=(20958,200) and the rcv1 dataset with (p,d)=(47236,200)(p,d)=(47236,200) [52]. We set λi\lambda_i such that the solution x∗x^* has at least 90% sparsity: λi=0.015\lambda_i=0.015 for colon-cancer and λi=0.0005\lambda_i=0.0005 for real-sim and rcv1.

As illustrated in Figure 2, Algorithm 2 performs well in terms of the optimality residual compared to PG-EXTRA and is comparable to NIDS, whilst not performing worse than either PG-EXTRA or NIDS in terms of the iterate residuals. NIDS reduces the consensus error noticeably faster than either Algorithm 2 or PG-EXTRA.

Figure 2. (Squared) fixed point residual and first-order optimality residuals versus iterations, for l1l_1-regularised logistic regression on the colon-cancer dataset.

Algorithm 2 performed better for larger values of η\eta, including the theoretically unsupported boundary value of η=1\eta=1, corresponding to ρ=α−1\rho=\alpha-1. Both α=500\alpha=500 and the linear cooling heuristic were competitive with PG-EXTRA, however using constant α=500\alpha=500 consistently required fewer iterations and a shorter runtime to converge compared to the cooling heuristic.

Table 2 shows that, in terms of the optimality residual, Algorithm 2 with α=500\alpha=500 took at best 7% fewer iterations and at worst 2% more iterations than PG-EXTRA, and taking less time on the colon and rcv1 datasets. In terms of the fixed point residuals and consensus error, Algorithm 2 with α=500\alpha=500 took a similar amount of iterations to PG-EXTRA but took up to 56% more time. Compared to the performance of NIDS on the real-sim dataset, Algorithm 2 with α=500\alpha=500 took a similar number of iterations, and between 11% less and 12% more time across all metrics. Algorithm 2 with α=500\alpha=500 took 20-30% more iterations than NIDS on colon and rcv1 datasets and up to 28% more time on the colon dataset, although it took up to 18% less time than NIDS on the rcv1 dataset. Regarding the iterate and optimality residuals, whilst Algorithm 2 with α=500\alpha=500 took more iterations than NIDS, in many instances it had a similar if not smaller runtime. However, NIDS notably converged faster in both iterations and runtime for the consensus error.

MetricAlg.colon-cancer Iters.colon-cancer Timereal-sim Iters.real-sim Timercv1 Iters.rcv1 Time
Resid.PG-EXTRA170.06142787.72435.91
Resid.NIDS150.061427140.77379.16
Resid.Alg. 2, η=0.1\eta= 0.11900.75––794156.73
Resid.Alg. 2, η=0.5\eta= 0.5410.182958245.1914924.89
Resid.Alg. 2, η=0.8\eta= 0.8260.091850152.968718.33
Resid.Alg. 2, η=0.95\eta= 0.95230.091558133.946911.23
Resid.Alg. 2, η=1.0\eta= 1.0220.081479127.256410.97
Resid.Alg. 2, α=500\alpha= 500180.061446125.15457.99
Optim.PG-EXTRA180.081560135.47449.85
Optim.NIDS150.061426141.15379.69
Optim.Alg. 2, η=0.1\eta= 0.11510.77––764163.00
Optim.Alg. 2, η=0.5\eta= 0.5410.202956303.2914629.99
Optim.Alg. 2, η=0.8\eta= 0.8260.091849192.898619.25
Optim.Alg. 2, η=0.95\eta= 0.95230.091557161.616914.43
Optim.Alg. 2, η=1.0\eta= 1.0220.101479160.996413.42
Optim.Alg. 2, α=500\alpha= 500180.071445158.82459.29
Consen.PG-EXTRA210.05142071.91455.59
Consen.NIDS170.061272105.81368.65
Consen.Alg. 2, η=0.1\eta= 0.15082.04––1181183.02
Consen.Alg. 2, η=0.5\eta= 0.5770.232942213.6921333.34
Consen.Alg. 2, η=0.8\eta= 0.8410.171840136.5112118.72
Consen.Alg. 2, η=0.95\eta= 0.95320.111549113.489514.51
Consen.Alg. 2, η=1.0\eta= 1.0270.081472108.998713.46
Consen.Alg. 2, α=500\alpha= 500220.071439112.87467.03

Table 2. Logistic regression: iterations and runtime in seconds to reduce the error metric to 10−810^{-8} for residual and optimality, and 10−1210^{-12} for consensus. Bolded entries are the best performance result for a given metric. “–”: error larger than tolerance at 10 000 iterations.

Conclusion

We proposed an accelerated variant of PG-EXTRA for decentralised optimisation, based on the generalised Fast Krasnosel’skiĭ–Mann algorithm [32, 33]. Our proposed algorithm, referred to as Fast PG-EXTRA (Algorithm 2), improves on the convergence rates of PG-EXTRA by providing o(1/k2)o(1/k^2) non-ergodic rates, compared to the corresponding O(1/k)O(1/k) ergodic rates for PG-EXTRA. We additionally prove o(1/k)o(1/k) non-ergodic convergence rates for PG-EXTRA, resolving an open question in the original paper. Numerical experiments for distributed power system state estimation and l1l_1-regularised logistic regression demonstrate the practical advantages of our algorithm, namely faster convergence in terms of first-order optimality residuals whilst maintaining similar iterate residuals and consensus errors to PG-EXTRA. Future directions include proving convergence of Fast PG-EXTRA when the parameters α\alpha and β\beta are non-constant, and establishing linear convergence under stronger assumptions such as strong convexity of the objective function.

Acknowledgements

MKT is supported in part by Australian Research Council grant DP23010174. LT is supported by a Melbourne Research Scholarship. This research was supported by The University of Melbourne’s Research Computing Services and the Petascale Campus.

Data availability

Part of the data used in the numerical experiments were obtained from http://www.csie.ntu.edu.tw/cjlin/libsvm, and the remainder were generated randomly and the procedures for reproducing them are detailed in § 4.

Code availability

Code is available at github.com/Timms42/Fast_PGEXTRA.

Declarations

Conflicts of interest

The authors declare that they have no conflict of interest.

Non-ergodic convergence rates of PG-EXTRA

In Section 2, we analysed Fast PG-EXTRA as an application of the Fast Condat–Vũ algorithm and hence the generalised Fast Krasnosel’skiĭ–Mann algorithm. In a similar manner, we can analyse PG-EXTRA as an application of the Krasnosel’skiĭ–Mann algorithm to resolve the open question of the non-ergodic convergence rates of PG-EXTRA [13].

To aid comparison with Fast PG-EXTRA (Algorithm 2), observe that PG-EXTRA (4) can be alternately expressed by the initialisation

x0∈Rp,u0=(I+W2)x0−τ∇f(x0),x^{0} \in\mathbb{R}^{p},\quad u^{0} = \left(\frac{I+W}{2}\right)x^{0} - \tau\nabla f(x^{0}),
x1=prox⁡τg(u0),andv1=(I−W2)(2x1−x0).(62)x^{1} = \operatorname{prox}_{\tau g}(u^{0}),\quad\text{and}\quad v^{1} = \left(\frac{I-W}{2}\right)(2x^{1}-x^{0}). \tag*{(62)}

and main iteration

uk=uk−1+xk−xk−1−vk−τ(∇f(xk)−∇f(xk−1))(63)u^k = u^{k-1} + x^k - x^{k-1} - v^k - \tau\left(\nabla f(x^k) - \nabla f(x^{k-1})\right) \tag*{(63)}
xk+1=prox⁡τg(uk)(64)x^{k+1} = \operatorname{prox}_{\tau g}(u^k) \tag*{(64)}
vk+1=(I−W2)(2xk+1−xk).(65)v^{k+1} = \left(\frac{I-W}{2}\right)\left(2x^{k+1} - x^k\right). \tag*{(65)}

The following theorem provides the non-ergodic convergence rates of PG-EXTRA.

Theorem A.1 Suppose (30) has a saddle point and 0<τ<(1+λmin⁡(W))/L0 < \tau< (1+\lambda_{\min}(W))/L. Then xk→x∗=(x∗,…,x∗)⊤∈Rn×px^k \to x^* = (x^*,\ldots,x^*)^\top\in\mathbb{R}^{n\times p}, where x∗∈Rpx^* \in\mathbb{R}^p is a solution of (1). Additionally, define the sequence {qk}k≥0\{q^k\}_{k\geq0} by qk=∑t=0kKxtq^k = \sum_{t=0}^k Kx^t. Then the sequences generated by PG-EXTRA (A1b) satisfy

∥xk+1−xk∥(I+W)/22+∥qk+1−qk∥2=o(1k),(66)\left\|x^{k+1}-x^k\right\|_{(I+W)/2}^2+\left\|q^{k+1}-q^k\right\|^2=o\left(\frac{1}{k}\right), \tag*{(66)}

the point rk=1τ(uk−xk+1)∈∂g(xk+1)r^k=\frac{1}{\tau}(u^k-x^{k+1})\in\partial g(x^{k+1}) satisfies

∥τ∇f(xk+1)+τrk+Kqk∥(I+W)/22=o(1k),(67)\left\|\tau\nabla f(x^{k+1})+\tau r^k+Kq^k\right\|_{(I+W)/2}^2=o\left(\frac{1}{k}\right), \tag*{(67)}

and

∥Kxk+1∥2=o(1k).(68)\left\|Kx^{k+1}\right\|^2=o\left(\frac{1}{k}\right). \tag*{(68)}

Proof. As discussed in [40, 44], the Condat–Vũ applied to (30) with step sizes τ\tau and σ=1τ\sigma=\frac{1}{\tau} yields PG-EXTRA. Consequently, convergence of {xk}k≥0\{x^k\}_{k\geq0} to x∗=(x∗,…,x∗)⊤x^*=(x^*,\ldots,x^*)^\top, where x∗∈Rpx^*\in\mathbb{R}^p is a solution of (1), follows from [21 Thm. 3.1].

It then remains to establish the rates given in (A2). Observe that, given initial points x0∈Rn×p,y0∈Rn×px^0\in\mathbb{R}^{n\times p},y^0\in\mathbb{R}^{n\times p}, the main iteration of the Condat–Vũ algorithm can be compactly expressed as

\begin{pmatrix}x^{k+1}\\y^{k+1}\end{pmatrix} = T\begin{pmatrix}x^k\\y^k\end{pmatrix}, \tag*{(69)}\end{pmatrix}

where T:Rn×p×Rn×p→Rn×p×Rn×pT:\mathbb{R}^{n\times p}\times\mathbb{R}^{n\times p}\to\mathbb{R}^{n\times p}\times\mathbb{R}^{n\times p} is the Condat–Vũ operator, defined by

T(xkyk)=(prox⁡τg(xk−τ∇f(xk)−τKyk)yk+1τK(2xk+1−xk)).(70)T\begin{pmatrix}x^k\\y^k\end{pmatrix} = \begin{pmatrix} \operatorname{prox}_{\tau g}(x^k-\tau\nabla f(x^k)-\tau Ky^k)\\ y^k+\frac{1}{\tau}K(2x^{k+1}-x^k) \end{pmatrix}. \tag*{(70)}

From Lemma 2.1(i), TT is θ\theta-averaged, where θ=2δ/(4δ−1)∈(0,1)\theta=2\delta/(4\delta-1)\in(0,1) with δ=1τ(1τ−σ∥K∥2)>12\delta=\frac{1}{\tau}\left(\frac{1}{\tau}-\sigma\|K\|^2\right)>\frac{1}{2}. Then, using the definition of an averaged operator, (A3) can be understood as an instance of the Krasnosel’skiĭ–Mann algorithm applied to 1−θθI+1θT\frac{1-\theta}{\theta}I+\frac{1}{\theta}T with parameter θ\theta. Applying [27 Thm. 1(4)], for example, we deduce that

∥(xk+1yk+1)−(xkyk)∥M2=o(1k).(71)\left\| \begin{pmatrix}x^{k+1}\\y^{k+1}\end{pmatrix} - \begin{pmatrix}x^k\\y^k\end{pmatrix} \right\|_M^2=o\left(\frac{1}{k}\right). \tag*{(71)}

Combining (A5) with (A4), the definition of qkq^k, and the identity I=(I+W)/2+K2I=(I+W)/2+K^2, we have

τ∥(xk+1−xkyk+1−yk)∥M2=∥xk+1−xk∥2+τ2∥yk+1−yk∥2−2τ⟨K(xk+1−xk),yk+1−yk⟩=∥xk+1−xk∥(I+W)/22+∥xk+1−xk∥K22−2⟨K(xk+1−xk),yk+1−yk⟩+τ2∥yk+1−yk∥2=∥xk+1−xk∥(I+W)/22+∥K(xk+1−xk)−τ(yk+1−yk)∥2=∥xk+1−xk∥(I+W)/22+∥Kxk+1∥2,\begin{aligned} \tau\left\|\begin{pmatrix}x^{k+1}-x^k\\y^{k+1}-y^k\end{pmatrix}\right\|_M^2 =\|x^{k+1}-x^k\|^2+\tau^2\|y^{k+1}-y^k\|^2-2\tau\langle K(x^{k+1}-x^k),y^{k+1}-y^k\rangle\\ &=\|x^{k+1}-x^k\|_{(I+W)/2}^2+\|x^{k+1}-x^k\|_{K^2}^2 -2\langle K(x^{k+1}-x^k),y^{k+1}-y^k\rangle+\tau^2\|y^{k+1}-y^k\|^2 \\ &=\|x^{k+1}-x^k\|_{(I+W)/2}^2+\|K(x^{k+1}-x^k)-\tau(y^{k+1}-y^k)\|^2 \\ &=\|x^{k+1}-x^k\|_{(I+W)/2}^2+\|Kx^{k+1}\|^2, \end{aligned}

establishing (A2c). Since qk+1−qk=Kxk+1q^{k+1}-q^k=Kx^{k+1}, this also establishes (A2a). Further, choosing in particular y0=1τKx0y^0=\frac{1}{\tau}Kx^0, we observe that (A4) implies that

τyk+1=∑t=0k+1Kxt+Kxk+1+τy0−Kx0=qk+1+Kxk+1∀k≥1,(72)\tau y^{k+1}=\sum_{t=0}^{k+1}Kx^t+Kx^{k+1}+\tau y^0-Kx^0=q^{k+1}+Kx^{k+1}\quad\forall k\ge1, \tag*{(72)}

and that rk=1τ(uk−xk+1)∈∂g(xk+1)r^k=\frac{1}{\tau}(u^k-x^{k+1})\in\partial g(x^{k+1}) satisfies

xk−xk+1=τ∇f(xk)+τrk+τKyk=τ∇f(xk)+τrk+Kqk+K2xk.(73)x^k-x^{k+1}=\tau\nabla f(x^k)+\tau r^k+\tau Ky^k=\tau\nabla f(x^k)+\tau r^k+Kq^k+K^2x^k. \tag*{(73)}

Combining (55), (A7), Young’s inequality, the observation that I+W2⪯I\frac{I+W}{2}\preceq I, LL-Lipschitz continuity of ∇f\nabla f, and the equivalence of ∥⋅∥(I+W)/2\|\cdot\|_{(I+W)/2} and ∥⋅∥\|\cdot\| in Rn×p\mathbb{R}^{n\times p}, we deduce that

∥τ∇f(xk+1)+τrk+Kqk∥(I+W)/22=∥τ∇f(xk)+τrk+Kqk∥(I+W)/22+∥τ∇f(xk+1)−τ∇f(xk)∥(I+W)/22+2⟨τ∇f(xk)+τrk+Kqk,τ∇f(xk+1)−τ∇f(xk)⟩(I+W)/2≤2∥τ∇f(xk)+τrk+Kqk∥(I+W)/22+2∥τ∇f(xk+1)−τ∇f(xk)∥(I+W)/22=2∥τ∇f(xk)+τrk+Kqk+K2xk∥(I+W)/22+2∥K2xk∥(I+W)/22−4⟨τ∇f(xk)+τrk+Kqk+K2xk,K2xk⟩(I+W)/2+2τ2∥∇f(xk+1)−∇f(xk)∥(I+W)/22≤4∥τ∇f(xk)+τrk+Kqk+K2xk∥(I+W)/22+4∥K2xk∥(I+W)/22+2τ2∥∇f(xk+1)−∇f(xk)∥(I+W)/22≤4∥xk+1−xk∥(I+W)/22+4∥K∥2∥Kxk∥2+2τ2∥∇f(xk+1)−∇f(xk)∥2≤4∥xk+1−xk∥(I+W)/22+4∥K∥2∥Kxk∥2+2τ2L2∥xk+1−xk∥2≤(4+2γτ2L2)∥xk+1−xk∥(I+W)/22+4∥K∥2∥Kxk∥2,(74)\begin{aligned} \|\tau\nabla f(x^{k+1})+\tau r^k+Kq^k\|_{(I+W)/2}^2 ={}&\|\tau\nabla f(x^k)+\tau r^k+Kq^k\|_{(I+W)/2}^2\\ &+\|\tau\nabla f(x^{k+1})-\tau\nabla f(x^k)\|_{(I+W)/2}^2\\ &+2\langle\tau\nabla f(x^k)+\tau r^k+Kq^k,\tau\nabla f(x^{k+1})-\tau\nabla f(x^k)\rangle_{(I+W)/2}\\ \le{}&2\|\tau\nabla f(x^k)+\tau r^k+Kq^k\|_{(I+W)/2}^2\\ &+2\|\tau\nabla f(x^{k+1})-\tau\nabla f(x^k)\|_{(I+W)/2}^2\\ ={}&2\|\tau\nabla f(x^k)+\tau r^k+Kq^k+K^2x^k\|_{(I+W)/2}^2+2\|K^2x^k\|_{(I+W)/2}^2\\ &-4\langle\tau\nabla f(x^k)+\tau r^k+Kq^k+K^2x^k,K^2x^k\rangle_{(I+W)/2}\\ &+2\tau^2\|\nabla f(x^{k+1})-\nabla f(x^k)\|_{(I+W)/2}^2\\ \le{}&4\|\tau\nabla f(x^k)+\tau r^k+Kq^k+K^2x^k\|_{(I+W)/2}^2+4\|K^2x^k\|_{(I+W)/2}^2\\ &+2\tau^2\|\nabla f(x^{k+1})-\nabla f(x^k)\|_{(I+W)/2}^2\\ \le{}&4\|x^{k+1}-x^k\|_{(I+W)/2}^2+4\|K\|^2\|Kx^k\|^2+2\tau^2\|\nabla f(x^{k+1})-\nabla f(x^k)\|^2\\ \le{}&4\|x^{k+1}-x^k\|_{(I+W)/2}^2+4\|K\|^2\|Kx^k\|^2+2\tau^2L^2\|x^{k+1}-x^k\|^2\\ \le{}&(4+2\gamma\tau^2L^2)\|x^{k+1}-x^k\|_{(I+W)/2}^2+4\|K\|^2\|Kx^k\|^2, \tag*{(74)} \end{aligned}

for some γ>0\gamma>0. Combining (A8) with (A2a), (A2c), and the observation that ∥K∥≤1\|K\|\le1 yields (A2b) and completes the proof. □

References

  1. [1]Braun, P., Grüne, L., Kellett, C.M., Weller, S.R., Worthmann, K.: A distributed optimization algorithm for the predictive control of smart grids. IEEE Transactions on Automatic Control 61(12), 3898–3911 (2016) https://doi.org/10.1109/TAC.2016.2525808
  2. [2]Belgioioso, G., Grammatico, S.: Semi-decentralized generalized Nash equilibrium seeking in monotone aggregative games. IEEE Transactions on Automatic Control 68, 140–155 (2023) https://doi.org/10.1109/TAC.2021.3135360
  3. [3]Bazerque, J.A., Mateos, G., Giannakis, G.B.: Group-Lasso on splines for spectrum cartography. IEEE Transactions on Signal Processing 59(10), 4648–4663 (2011) https://doi.org/10.1109/TSP.2011.2160858
  4. [4]You, K., Tempo, R., Xie, P.: Distributed algorithms for robust convex optimization via the scenario approach. IEEE Transactions on Automatic Control 64(3), 880–895 (2019) https://doi.org/10.1109/TAC.2018.2828093
  5. [5]Tsitsiklis, J.N.: Problems in decentralized decision making and computation. PhD Thesis, Department of Electrical Engineering and Computer Science. Massachusetts Institute of Technology, Cambridge, MA (1984)
  6. [6]Cattivelli, F.S., Lopes, C.G., Sayed, A.H.: A diffusion RLS scheme for distributed estimation over adaptive networks. In: 2007 IEEE 8th Workshop on Signal Processing Advances in Wireless Communications, Helsinki, pp. 1–5 (2007). IEEEDOI
  7. [7]Nedic, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Transactions on automatic control 54(1), 48–61 (2009)DOI
  8. [8]Shi, W., Ling, Q., Wu, G., Yin, W.: EXTRA: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal on Optimization 25(2), 944–966 (2014) https://doi.org/10.1137/14096668X
  9. [9]Nedić, A., Liu, J.: Distributed optimization for control. Annual Review of Control, Robotics, and Autonomous Systems 1(1), 77–103 (2018)DOI
  10. [10]Li, Z., Shi, W., Yan, M.: A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing 67(17), 4494–4506 (2019) https://doi.org/10.1109/TSP.2019.2926022
  11. [11]Chang, T.-H., Hong, M., Wang, X.: Multi-agent distributed optimization via inexact consensus ADMM. IEEE Transactions on Signal Processing 63(2), 482–497 (2014)DOI
  12. [12]Aybat, N.S., Wang, Z., Lin, T., Ma, S.: Distributed linearized alternating direction method of multipliers for composite convex consensus optimization. IEEE Transactions on Automatic Control 63(1), 5–20 (2018) https://doi.org/10.1109/TAC.2017.2713046
  13. [13]Shi, W., Ling, Q., Wu, G., Yin, W.: A proximal gradient algorithm for decentralized composite optimization. IEEE Transactions on Signal Processing 63(22), 6013–6023 (2015) https://doi.org/10.1109/TSP.2015.2461520
  14. [14]Alghunaim, S.A., Ryu, E.K., Yuan, K., Sayed, A.H.: Decentralized proximal gradient algorithms with linear convergence rates. IEEE Transactions on Automatic Control 66(6), 2787–2794 (2021) https://doi.org/10.1109/TAC.2020.3009363
  15. [15]Li, Y., Yan, M.: On the linear convergence of two decentralized algorithms. Journal of Optimization Theory and Applications 189(1), 271–290 (2021) https://doi.org/10.1007/s10957-021-01833-y
  16. [16]Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale modeling & simulation 4(4), 1168–1200 (2005)DOI
  17. [17]Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Transactions of the American Mathematical Society 82(2), 421–439 (1956)DOI
  18. [18]Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming 55(1), 293–318 (1992) https://doi.org/10.1007/BF01581204
  19. [19]Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision 40(1), 120–145 (2011)DOI
  20. [20]He, B., Yuan, X.: Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM Journal on Imaging Sciences 5(1), 119–149 (2012)
  21. [21]Condat, L.: A primal–dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. Journal of Optimization Theory and Applications 158(2), 460–479 (2013) https://doi.org/10.1007/s10957-012-0245-9
  22. [22]Vũ, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Advances in Computational Mathematics 38(3), 667–681 (2013) https://doi.org/10.1007/s10444-011-9254-8
  23. [23]He, B., Yuan, X.: On the convergence rate of Douglas–Rachford operator splitting method. Mathematical Programming 153(2), 715–722 (2015)
  24. [24]Krasnosel’skii, M.A.: Two remarks on the method of successive approximations. Uspekhi Matematicheskikh Nauk 10(1), 123–127 (1955)
  25. [25]Mann, W.R.: Mean value methods in iteration. Proceedings of the American Mathematical Society 4(3), 506–510 (1953) https://doi.org/10.1090/S0002-9939-1953-0054846-3
  26. [26]Baillion, J., Bruck, R.E.: The rate of asymptotic regularity is o(1/n). In: Kartsatos, A.G. (ed.) Theory and Applications of Nonlinear Operators of Accretive and Monotone Types, Lecture Notes in Pure and Applied Mathematics, vol. 178, pp. 51–82. Marcel Dekker, Inc., New York (1996)
  27. [27]Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. In: Glowinski, R., Osher, S.J., Yin, W. (eds.) Splitting Methods in Communication, Imaging, Science, and Engineering, pp. 115–163. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41589-5_4
  28. [28]Halpern, B.: Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society 73(6), 957–961 (1967)DOI
  29. [29]Lieder, F.: On the convergence rate of the Halpern-iteration. Optimization letters 15(2), 405–418 (2021)DOI
  30. [30]Park, J., Ryu, E.K.: Exact optimal accelerated complexity for fixed-point iterations. In: International Conference on Machine Learning, pp. 17420–17457 (2022). PMLRarxiv.org/abs/2201.11413
  31. [31]Nesterov, Y.: A method for solving the convex programming problem with convergence rate o(1/k²). In: Dokl Akad Nauk SSSR, vol. 269. Moscow, p. 543 (1983)
  32. [32]Boṭ, R.I., Nguyen, D.-K.: Fast Krasnosel’skii–Mann algorithm with a convergence rate of the fixed point iteration of o(1/k). SIAM Journal on Numerical Analysis 61(6), 2813–2843 (2023)
  33. [33]Boṭ, R.I., Chenchene, E., Fadili, J.M.: Fast Krasnosel’skii–Mann method with overrelaxation and preconditioners. arXiv:2411.18574 (2025)arxiv.org/abs/2411.18574
  34. [34]Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences 2(1), 183–202 (2009)DOI
  35. [35]Condat, L., Sadiev, A., Richtárik, P.: A Nesterov-accelerated primal-dual splitting algorithm for convex nonsmooth optimization. arXiv:2604.09245 (2026)arxiv.org/abs/2604.09245
  36. [36]Qu, G., Li, N.: Harnessing smoothness to accelerate distributed optimization. IEEE Transactions on Control of Network Systems 5(3), 1245–1260 (2018) https://doi.org/10.1109/TCNS.2017.2698261
  37. [37]Zhu, M., Martínez, S.: Discrete-time dynamic average consensus. Automatica 46(2), 322–329 (2010)DOI
  38. [38]Qu, G., Li, N.: Accelerated distributed Nesterov gradient descent. IEEE Transactions on Automatic Control 65(6), 2566–2581 (2019)DOI
  39. [39]Ye, H., Zhou, Z., Luo, L., Zhang, T.: Decentralized accelerated proximal gradient descent. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M.F., Lin, H. (eds.) Advances in Neural Information Processing Systems, vol. 33, pp. 18308–18317. Curran Associates, Inc., Red Hook (2020)
  40. [40]Wu, T., Yuan, K., Ling, Q., Yin, W., Sayed, A.H.: Decentralized consensus optimization with asynchrony and delays. IEEE Transactions on Signal and Information Processing over Networks 4(2), 293–307 (2017)arxiv.org/abs/1612.00150
  41. [41]Li, Z., Yan, M.: New convergence analysis of a primal-dual algorithm with large stepsizes. Advances in Computational Mathematics 47(1), 9 (2021)DOI
  42. [42]Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edn. CMS Books in Mathematics. Springer, Berlin (2017). https://doi.org/10.1007/978-3-319-48311-5
  43. [43]Rockafellar, R.T.: Conjugate Duality and Optimization. Society for Industrial and Applied Mathematics, Philadelphia (1974)DOI
  44. [44]Ryu, E.K., Yin, W.: Large-scale Convex Optimization: Algorithms & Analyses Via Monotone Operators. Cambridge University Press, Cambridge (2022)
  45. [45]Borwein, J.M., Lewis, A.S.: Partially finite convex programming. Part I: Quasi relative interiors and duality theory. Mathematical Programming 57(1-3), 15–48 (1992) https://doi.org/10.1007/bf01581072
  46. [46]Boyd, S., Diaconis, P., Xiao, L.: Fastest mixing Markov chain on a graph. SIAM review 46(4), 667–689 (2004)DOI
  47. [47]Xiao, L., Boyd, S., Kim, S.-J.: Distributed average consensus with least-mean-square deviation. Journal of parallel and distributed computing 67(1), 33–46 (2007)DOI
  48. [48]Kekatos, V., Giannakis, G.B.: Distributed robust power system state estimation. IEEE Transactions on Power Systems 28(2), 1617–1626 (2012)arxiv.org/abs/1204.0991
  49. [49]Tibshirani, R.: Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology 58(1), 267–288 (1996)
  50. [50]Korres, G.N.: A distributed multiarea state estimation. IEEE Transactions on Power Systems 26(1), 73–84 (2010)DOI
  51. [51]Liu, J., Chen, J., Ye, J.: Large-scale sparse logistic regression. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery And Data Mining, pp. 547–556. ACM, Paris (2009). https://doi.org/10.1145/1557019.1557082
  52. [52]Chang, C.-C., Lin, C.-J.: LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology 2, 1–27 (2011). Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm

Paper details

vlnc:W_ntvergn3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents