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 convergence rates in terms of the first-order optimality residual, successive iterates, and consensus error, compared to PG-EXTRA's ergodic 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 -regularised logistic regression.
Keywords: distributed optimization, proximal-gradient, convergence rates, sparse regression.
MSC2020: 47N10, 62J07, 65K10, 65B99, 68W15
Introduction
Consider a connected graph of agents coordinating to solve
where the functions are proper lsc convex, and the functions are convex and differentiable with -Lipschitz continuous gradient. We consider the setting where agent knows only and , can evaluate the proximal operator of and the gradient of , 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 (Definition 1.1) and a step size , where denotes the smallest eigenvalue of , the main iteration of PG-EXTRA is, for all agents ,
Note that, in each iteration, agent separately computes the gradient of the smooth function and the proximal operator of the nonsmooth function . The variables and are local to agent , and the summations involving model agents communicating their local variables as the coefficients are nonzero only if agents and are neighbours. Thus, encodes the communication graph.
Denote
Under this notation, the iteration for PG-EXTRA (2) can be expressed compactly as
Defining and , 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:
there exists such that
and
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 and 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 , the associated fixed point problem is
The (squared) fixed point residual associated with at can be defined by . 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 such that the main iteration of the algorithms can be compactly expressed as
By analysing these algorithms as fixed point iterations, one can show that they have non-ergodic 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 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 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 [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 , [36] proposed an algorithm that combines distributed gradient descent [6, 7] with gradient tracking [37], and achieves a non-ergodic convergence rate of 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 with , again in terms of objective values. Given additional strong assumptions, e.g. strong convexity of , 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 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 , step size , and parameters , , , and , the main iteration for our algorithm is
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 , compared to the ergodic rates of for PG-EXTRA. The main point of difference is the order, versus , rather than ergodicity or big- versus little- as we prove that, in general, PG-EXTRA has non-ergodic 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
Here, the updates in (10) and (11) are the same, and the update in (10) coincides with the update in (11). The main differences are a recursively defined sequence in (10), and the sequence in (10) is a linear combination of previous iterates and proximal evaluations. The effects of the parameters , , , and 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 and bold letters for elements of , as shown in (4). The diagonal subspace of is denoted by , and denotes the identity operator. The Landau symbols are denoted by and , and denote the standard inner product and induced norm on , respectively, and, given a positive definite matrix , and denote the inner product and norm induced by on , respectively.
Communication networks and matrices
Given a real symmetric matrix , the largest and smallest eigenvalues of are denoted and , respectively, and the kernel of is denoted . The Loewner order is denoted by , and the vector of ones is denoted by .
As discussed in § 1.1, communication amongst agents is modelled by a connected graph, , where is the set of nodes and is the set of edges. Each node represents an agent, and agents and can communicate only if . Communication between neighbours is modelled using a mixing matrix, which is defined as follows.
Definition 1.1 (Mixing matrix [8]) A matrix is a mixing matrix if it satisfies the following properties.
(i) (Decentralised) if and ,
(ii) (Symmetric) ,
(iii) (Null space) , and
(iv) (Spectrum) .
Given a mixing matrix , agent communicating with their neighbouring agents is modelled by , where is the local variable of agent .
Using the stacked vector notation (4), the matrix-vector product then models a round of communication amongst all agents.
Convex functions
The domain of a function is denoted . A function is proper if and for all , and is lower semicontinuous (lsc) if for all . The Fenchel conjugate of a function is denoted .
The indicator function for a set is denoted and takes the value if , and is otherwise. Given a proper lsc convex function , the subdifferential of at a point is defined as
if , and if f$ is given by
and the proximal operator of is the projection onto the set , denoted .
Operators
The set of fixed points of an operator is denoted . An operator is -Lipschitz continuous if and
is nonexpansive if it is -Lipschitz continuous, and is -averaged if and there exists a nonexpansive operator such that . In a slight abuse of terminology, it will sometimes be convenient to refer to a nonexpansive operator as a -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
where and are proper lsc convex, is convex and differentiable with -Lipschitz continuous gradient, and 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 or .
By writing in terms of its conjugate, (12) becomes the saddle point problem
A sufficient condition for the existence of a saddle point of (13) is that
where denotes the relative interior of a set [42 15.23, 19.1]. For further discussion of the existence of saddle points, see [43 §7].
Assuming saddle points of (13) exist, then is a saddle point of (13) if and only if solves (12) and solves the Fenchel dual problem given by
Given step sizes and , the Condat–Vũ operator is defined as
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 and parameter , the Condat–Vũ algorithm can be compactly expressed as
Using the definition of , (16) can be unravelled as
We now recall some properties of the Condat–Vũ operator (see, for example, [21]). Let denote the block matrix given by
Lemma 2.1 Suppose that and denote . Then the following hold.
(i) is -averaged w.r.t. where .
(ii) if and only if 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 in (15) and the proximal operator, it follows that if and only if satisfies
Since and have full domain, the subdifferential sum rule [42 Cor. 16.48] implies that (20) is equivalent to
Through first-order optimality, this is equivalent to being a saddle point of (13).
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 can be interpreted as controlling the contribution of , and is related to the averaged constant of , , by . The parameters and control the relative contribution of momentum terms such as , with larger values of and reducing their contribution. Finally, controls relaxation terms such as , in a similar manner to the role played by 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 and are proper lsc convex, is linear, is convex and differentiable with -Lipschitz continuous gradient, the step sizes satisfy , and a saddle point of (13) exists (for example, (14) holds). Denote , where and are the sequences generated by Algorithm 1. Then , where is a saddle point of (13). Additionally,
Algorithm 1 Fast Condat–Vũ algorithm for (13).
Choose initial points , and ;
Choose step sizes ;
Choose parameters , , and ;
Set and choose ;
Initialise variables:
for do
Update variables:
end for
and
Proof. Denote and . Then the generalised Fast Krasnosel’skiĭ–Mann algorithm [33 Alg. 1] applied to , where is the Condat–Vũ operator (15), yields the iteration
Using the definition of in (15) and yields (22)–(27). Since , Lemma 2.1(i) implies that is -averaged with respect to with . Further, Lemma 2.1(ii) implies that is equal to the set of saddle points of (13). Altogether, applying [32 Thm. 3.3] yields that where 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
where , , and are defined in (4) and , where is a mixing matrix (see Definition 1.1). Then a point solves (29) if and only if and solves (1) [44 §11.3.3]. As was done in § 2, by writing in terms of its conjugate, solving (29) becomes
Here, the sufficient condition (14) for the existence of a saddle point becomes
This follows from continuity of , , and the fact that given nonempty convex sets , we have that and [45 Prop. 2.4, 2.5, 2.7]. Furthermore, assuming a saddle point of (30) exists, we have that there exists such that solves (30) if and only if and solves (1). Moreover, the latter statement holds if and only if there exists and such that satisfy the first-order optimality conditions [13 Lem. 1]
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 ; 2: Choose a step size , and mixing matrix ; 3: Choose parameters , , and ; 4: Set and choose ; 5: Initialise variables:
6: for do
7: Update variables:
8: end for
Theorem 3.1 Consider the problem (1). Suppose are proper lsc convex, are convex and differentiable with -Lipschitz continuous gradient, , and a saddle point of (19 exists (for example, (31) holds). Then the sequences generated by Algorithm 2 satisfy , where is a solution of (1).
Additionally, define the sequence by . Then
the point satisfies
and
Proof. The Fast Condat–Vũ algorithm (Alg. 1) applied to (30) with and yields the initialisation
and, for all , the iteration
Define sequences and according to
Using (49) and (50), we deduce that
From (46), we deduce that
Then, substituting (46) followed by (53) into (48), we obtain
The initialisation (22) follows by substituting 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 to both sides of (54) together with the definitions of and yields (39). Thus, we have that Fast PG-EXTRA (Alg. 2) is an instance of Fast Condat–Vũ (Alg. 1).
Now, the definition of implies and hence implies . Noting that a saddle point of (30) exists, Theorem 2.3 yields that , where is a saddle point of (30). From this, we deduce that is a solution of (29) and hence where is a solution of (1).
Additionally, combining Theorem 2.3, the definition of , the identity and (46) yields
Since , for all , this establishes (40) and (42). Further, observe that, for all , (45) and (49) implies that satisfies
where the second equality follows from (50) and since . Combining (55), (56), Young’s inequality, the observation that , -Lipschitz continuity of , and the equivalence of and in , we deduce that
for some . 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 non-ergodic rates for the iterate, first-order optimality, and consensus residuals in Fast PG-EXTRA. In contrast, [13 Thm. 2] only provides ergodic rates for these quantities. The latter result can be improved to 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 , parameter , mixing matrix , and , the main iteration of NIDS is
The algorithms are compared across two problems: (distributed) robust power state system estimation and -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 in PG-EXTRA and Algorithm 2, and and in NIDS. For the parameters in Algorithm 2, we follow the recommendations in [33 §5] and set , and with . For the acceleration parameter , we use the linear cooling heuristic , where increases linearly from to for . This heuristic is compared against a constant (using ). Finally, we follow [13] in setting the initial point as and, given a connected communication graph , setting the mixing matrix to be the Metropolis constant edge weight matrix [8, 46, 47], given by
To facilitate a clear comparison between algorithms, we define for PG-EXTRA and NIDS the sequences , where are defined in {(4)} and {(35)} respectively. The reason for this is that, in Fast PG-EXTRA (Algorithm 2), is used to compute the fixed point residual, whereas is the successive iterate. In PG-EXTRA and NIDS these quantities coincide. The sequence 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 and . To that end, we define and
(PG-EXTRA)
(Alg. 2)
(NIDS)
The definition of follows from the evaluation of the proximal operator in each algorithm. The sequences 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:
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 by
for Fast PG-EXTRA it is given by
and for NIDS it is given by
The first-order optimality residuals measure the error in the optimality conditions in each iteration. For PG-EXTRA, these are given in each iteration by
for Fast PG-EXTRA, they are
and for NIDS, they are
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 for PG-EXTRA, for Fast PG-EXTRA, and for NIDS are all appropriate for measuring the error in the first-order optimality conditions (32), as and by definition and, following (50), we have that . Reporting the first-order optimality residuals in each iteration requires an additional gradient evaluation, , which can inflate algorithm runtime. In practice, one may simply measure the (squared) fixed point residual or the successive differences, .
Power system state estimation
Given a power system consisting of buses partitioned into control areas, measurement matrices , and (potentially faulty) noisy measurements , we seek to estimate the state of the system and the location of the faulty measurements , where if measurement is faulty, and zero otherwise [48]. Denoting the measurement noise by , the system state is the solution to the linear model
The system state and location of the faulty measurements, , can be estimated via least-squares with -regularisation for . Given regularisation parameters , agents collectively seek a solution to the regularised problem
Problem (60) is of the form (1) with , , and . The proximal and gradient operators can be computed by
and
where denotes the soft thresholding operator [49], applied element-wise for vectors, and is the standard basis vector with one in the th position. Note that is -Lipschitz continuous with .
For the communication graph, we follow [50 §4] in using the IEEE 14-bus test case partitioned into control areas, with corresponding measurement matrices . The non-faulty measurements have entries sampled i.i.d. from ; to simulate faults, we follow [50] and uniformly sample entries across all measurements and multiply them by 1.2. The number of faulty measurements is sampled from , such that at most 25% of measurements are faulty. Finally, are sampled i.i.d. from . Results are averaged over 20 realisations of and .
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 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 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.
| Metric | Alg. | Iters. | Time |
| Resid. | PG-EXTRA | 648.0 (388) | 0.103 (0.062) |
| Resid. | NIDS | 648.0 (383) | 0.191 (0.100) |
| Resid. | Alg. 2, | 6239.0 (3621) | 1.220 (0.670) |
| Resid. | Alg. 2, | 1319.0 (782) | 0.257 (0.146) |
| Resid. | Alg. 2, | 844.0 (504) | 0.169 (0.089) |
| Resid. | Alg. 2, | 717.5 (433) | 0.145 (0.084) |
| Resid. | Alg. 2, | 683.5 (415) | 0.132 (0.074) |
| Resid. | Alg. 2, | 656.5 (393) | 0.119 (0.074) |
| Optim. | PG-EXTRA | 1743.0 (955) | 0.390 (0.200) |
| Optim. | NIDS | 647.0 (382) | 0.190 (0.120) |
| Optim. | Alg. 2, | 6229.0 (3610) | 1.604 (0.921) |
| Optim. | Alg. 2, | 1317.0 (780) | 0.358 (0.201) |
| Optim. | Alg. 2, | 843.0 (502) | 0.215 (0.124) |
| Optim. | Alg. 2, | 716.5 (432) | 0.176 (0.105) |
| Optim. | Alg. 2, | 682.5 (414) | 0.174 (0.104) |
| Optim. | Alg. 2, | 655.5 (392) | 0.160 (0.096) |
| Consen. | PG-EXTRA | 1681.5 (1214) | 0.271 (0.186) |
| Consen. | NIDS | 1283.0 (894) | 0.340 (0.220) |
| Consen. | Alg. 2, | – | – |
| Consen. | Alg. 2, | 3417.5 (2474) | 0.664 (0.445) |
| Consen. | Alg. 2, | 2158.5 (1566) | 0.411 (0.279) |
| Consen. | Alg. 2, | 1825.5 (1325) | 0.351 (0.244) |
| Consen. | Alg. 2, | 1736.5 (1261) | 0.317 (0.228) |
| Consen. | Alg. 2, | 1702.5 (1229) | 0.320 (0.214) |
Table 1. PSSE: median (minimum) iterations and median (minimum) runtime in seconds to reduce the error metric to for residual and optimality, and to 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 , including the boundary value of , which corresponds to and is not supported by Theorem 3.1. Both and the linear cooling heuristic were competitive with PG-EXTRA and NIDS in iterate residuals and first-order optimality, however using constant consistently required fewer iterations to converge compared to the cooling heuristic.
Regularised logistic regression
Given a population of agents, sample matrices , and label vectors , we seek to recover a weight vector and intercept that minimise the average empirical logistic loss. Given regularisation parameters , agents collectively seek a sparse solution to the regularised problem
where
is the average logistic loss.
Problem (61) is of the form (1), with , , and . Consequently, the proximal and gradient operators can be computed by
where
with denoting Hadamard division. Note that is -Lipschitz continuous with
For the communication graph, we use a cycle communication graph with agents and . We follow [51] in using the following datasets for the sample matrices and label vectors : colon-cancer with , and the first two hundred samples of the real-sim dataset with and the rcv1 dataset with [52]. We set such that the solution has at least 90% sparsity: for colon-cancer and 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 -regularised logistic regression on the colon-cancer dataset.
Algorithm 2 performed better for larger values of , including the theoretically unsupported boundary value of , corresponding to . Both and the linear cooling heuristic were competitive with PG-EXTRA, however using constant 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 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 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 took a similar number of iterations, and between 11% less and 12% more time across all metrics. Algorithm 2 with 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 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.
| Metric | Alg. | colon-cancer Iters. | colon-cancer Time | real-sim Iters. | real-sim Time | rcv1 Iters. | rcv1 Time |
| Resid. | PG-EXTRA | 17 | 0.06 | 1427 | 87.72 | 43 | 5.91 |
| Resid. | NIDS | 15 | 0.06 | 1427 | 140.77 | 37 | 9.16 |
| Resid. | Alg. 2, | 190 | 0.75 | – | – | 794 | 156.73 |
| Resid. | Alg. 2, | 41 | 0.18 | 2958 | 245.19 | 149 | 24.89 |
| Resid. | Alg. 2, | 26 | 0.09 | 1850 | 152.96 | 87 | 18.33 |
| Resid. | Alg. 2, | 23 | 0.09 | 1558 | 133.94 | 69 | 11.23 |
| Resid. | Alg. 2, | 22 | 0.08 | 1479 | 127.25 | 64 | 10.97 |
| Resid. | Alg. 2, | 18 | 0.06 | 1446 | 125.15 | 45 | 7.99 |
| Optim. | PG-EXTRA | 18 | 0.08 | 1560 | 135.47 | 44 | 9.85 |
| Optim. | NIDS | 15 | 0.06 | 1426 | 141.15 | 37 | 9.69 |
| Optim. | Alg. 2, | 151 | 0.77 | – | – | 764 | 163.00 |
| Optim. | Alg. 2, | 41 | 0.20 | 2956 | 303.29 | 146 | 29.99 |
| Optim. | Alg. 2, | 26 | 0.09 | 1849 | 192.89 | 86 | 19.25 |
| Optim. | Alg. 2, | 23 | 0.09 | 1557 | 161.61 | 69 | 14.43 |
| Optim. | Alg. 2, | 22 | 0.10 | 1479 | 160.99 | 64 | 13.42 |
| Optim. | Alg. 2, | 18 | 0.07 | 1445 | 158.82 | 45 | 9.29 |
| Consen. | PG-EXTRA | 21 | 0.05 | 1420 | 71.91 | 45 | 5.59 |
| Consen. | NIDS | 17 | 0.06 | 1272 | 105.81 | 36 | 8.65 |
| Consen. | Alg. 2, | 508 | 2.04 | – | – | 1181 | 183.02 |
| Consen. | Alg. 2, | 77 | 0.23 | 2942 | 213.69 | 213 | 33.34 |
| Consen. | Alg. 2, | 41 | 0.17 | 1840 | 136.51 | 121 | 18.72 |
| Consen. | Alg. 2, | 32 | 0.11 | 1549 | 113.48 | 95 | 14.51 |
| Consen. | Alg. 2, | 27 | 0.08 | 1472 | 108.99 | 87 | 13.46 |
| Consen. | Alg. 2, | 22 | 0.07 | 1439 | 112.87 | 46 | 7.03 |
Table 2. Logistic regression: iterations and runtime in seconds to reduce the error metric to for residual and optimality, and 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 non-ergodic rates, compared to the corresponding ergodic rates for PG-EXTRA. We additionally prove non-ergodic convergence rates for PG-EXTRA, resolving an open question in the original paper. Numerical experiments for distributed power system state estimation and -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 and 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
and main iteration
The following theorem provides the non-ergodic convergence rates of PG-EXTRA.
Theorem A.1 Suppose (30) has a saddle point and . Then , where is a solution of (1). Additionally, define the sequence by . Then the sequences generated by PG-EXTRA (A1b) satisfy
the point satisfies
and
Proof. As discussed in [40, 44], the Condat–Vũ applied to (30) with step sizes and yields PG-EXTRA. Consequently, convergence of to , where 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 , the main iteration of the Condat–Vũ algorithm can be compactly expressed as
where is the Condat–Vũ operator, defined by
From Lemma 2.1(i), is -averaged, where with . Then, using the definition of an averaged operator, (A3) can be understood as an instance of the Krasnosel’skiĭ–Mann algorithm applied to with parameter . Applying [27 Thm. 1(4)], for example, we deduce that
Combining (A5) with (A4), the definition of , and the identity , we have
establishing (A2c). Since , this also establishes (A2a). Further, choosing in particular , we observe that (A4) implies that
and that satisfies
Combining (55), (A7), Young’s inequality, the observation that , -Lipschitz continuity of , and the equivalence of and in , we deduce that
for some . Combining (A8) with (A2a), (A2c), and the observation that yields (A2b) and completes the proof. □
References
- [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]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]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]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]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]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]Nedic, A., Ozdaglar, A.: Distributed subgradient methods for multi-agent optimization. IEEE Transactions on automatic control 54(1), 48–61 (2009)DOI
- [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]Nedić, A., Liu, J.: Distributed optimization for control. Annual Review of Control, Robotics, and Autonomous Systems 1(1), 77–103 (2018)DOI
- [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]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]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]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]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]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]Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale modeling & simulation 4(4), 1168–1200 (2005)DOI
- [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]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]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]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]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]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]He, B., Yuan, X.: On the convergence rate of Douglas–Rachford operator splitting method. Mathematical Programming 153(2), 715–722 (2015)
- [24]Krasnosel’skii, M.A.: Two remarks on the method of successive approximations. Uspekhi Matematicheskikh Nauk 10(1), 123–127 (1955)
- [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]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]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]Halpern, B.: Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society 73(6), 957–961 (1967)DOI
- [29]Lieder, F.: On the convergence rate of the Halpern-iteration. Optimization letters 15(2), 405–418 (2021)DOI
- [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]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]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]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]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]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]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]Zhu, M., Martínez, S.: Discrete-time dynamic average consensus. Automatica 46(2), 322–329 (2010)DOI
- [38]Qu, G., Li, N.: Accelerated distributed Nesterov gradient descent. IEEE Transactions on Automatic Control 65(6), 2566–2581 (2019)DOI
- [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]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]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]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]Rockafellar, R.T.: Conjugate Duality and Optimization. Society for Industrial and Applied Mathematics, Philadelphia (1974)DOI
- [44]Ryu, E.K., Yin, W.: Large-scale Convex Optimization: Algorithms & Analyses Via Monotone Operators. Cambridge University Press, Cambridge (2022)
- [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]Boyd, S., Diaconis, P., Xiao, L.: Fastest mixing Markov chain on a graph. SIAM review 46(4), 667–689 (2004)DOI
- [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]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]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]Korres, G.N.: A distributed multiarea state estimation. IEEE Transactions on Power Systems 26(1), 73–84 (2010)DOI
- [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]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

