Introduction
Federated Learning (FL) has emerged as a powerful collaborative learning framework in which multiple clients jointly train machine learning models without sharing their local data [17 , 22 , 24 , 28 ] . In classical FL, clients perform local computations on private data and periodically communicate through a central server to optimize a shared global model, often using methods such as Local SGD [12 , 21 , 28 , 39 ] . While it is typically assumed that clients in FL work toward a common objective, it can be restrictive in multi-agent systems where participants have distinct or competing objectives. In such settings, the goal is no longer to find a shared minimizer, but an equilibrium of a multiplayer game. Such problems arise naturally in economic competition, network resource allocation, electricity markets, energy systems, and control [1 , 18 , 33 , 35 , 44 ] .
Multiplayer Federated Learning (MpFL) was recently introduced by [45 ] to model this setting. In MpFL, clients are viewed as rational players with individual objectives, seeking an equilibrium while keeping their training data decentralized. A natural baseline algorithm for MpFL is Per-Player Local SGD (PEARL-SGD) [45 ] , which extends the idea of local updates to the multiplayer game setting. In each communication round, each player performs several local stochastic gradient steps on its own strategy while keeping the strategies of the other players fixed at the latest synchronization point, after which the server collects the updated strategies, concatenates them, and broadcasts the synchronized joint strategy back to all players.
Local updates reduce the frequency of communication, but synchronization is still a significant overhead because the full joint strategy has to be shared. A natural way to further reduce this communication cost is to compress the communicated information, as is commonly done in distributed [2 , 9 , 20 , 25 , 38 , 40 ] and federated optimization [15 , 34 ] . However, PEARL-SGD synchronizes the players’ updated strategies, and directly compressing the strategy vectors can prevent convergence, even when deterministic gradients are used (Figure 2 ). This can be addressed by letting the players instead communicate the strategy increments , i.e., changes in local strategies from the local descent loops, rather than the updated strategies themselves. Mathematically, without compression, the strategy-sharing and increment-sharing formulations of PEARL-SGD are equivalent, producing the exact same iterates. However, the distinction is critical when compression is applied; it turns out that increment sharing is a correct reformulation allowing the compressed variant C-PEARL-SGD to converge to equilibrium in the deterministic setting.
Figure 2. Comparison of convergence for versions of C-PEARL-SGD compressing x τ p i x_{\tau_p}^{i} x τ p i x τ ( p + 1 ) i − x τ p i x_{\tau(p+1)}^{i}-x_{\tau_p}^{i} x τ ( p + 1 ) i − x τ p i Δ \Delta Δ n n n § 5 with deterministic gradients.
In this work, we take this new formulation of PEARL-SGD as a starting point and design more advanced PEARL-type algorithms. We provide a unified framework for convergence analysis that incorporates both compression and standard variance reduction techniques. Consequently, we show that exact convergence is achievable under both compression errors and gradient stochasticity, significantly reducing the communication overhead and improving the learning dynamics of MpFL.
Main contributions
Our main contributions are summarized as follows.
Exact Convergence via Increment Sharing. We introduce an increment-sharing reformulation of PEARL-SGD, and show that it is equivalent to the original formulation without compression (Proposition 2.1 ). On the other hand, we show that the increment-sharing variant allows exact convergence to the equilibrium with compression in the deterministic setting (Corollary 4.6).
Advanced MpFL methods. Building on increment sharing, we design new per-player local (PEARL) methods for MpFL. We develop a generalized PEARL-SGD (Algorithm 1) algorithm and a unified convergence framework that allows different local gradient estimators and compression maps. Consequently, we analyze PEARL-SGD, PEARL-SVRG and their compressed variants C-PEARL-SGD and C-PEARL-SVRG in a unified manner (all as corollaries of the main result Theorem 4.3 ), the latter three being new methods.
Numerical evaluation. We complement our theory with experiments showing practical effects of local updates, compression, and variance reduction in MpFL.
Multiplayer Federated Learning and Generalized PEARL-SGD
In this section, we review the MpFL setting and the PEARL-SGD algorithm from [45 ] , and prove its equivalence to our increment-sharing variant. We then introduce a generalized PEARL-SGD framework that incorporates variance reduction and compression.
Multiplayer games and equilibrium. We begin by introducing the concept of a multiplayer game and the corresponding notion of equilibrium. Throughout this work, players are indexed by i ∈ [ n ] i \in[n] i ∈ [ n ] x i ∈ R d i x^i \in\mathbb{R}^{d_i} x i ∈ R d i x = ( x 1 , … , x n ) ∈ R D \mathbf{x} = (x^1,\ldots,x^n) \in\mathbb{R}^D x = ( x 1 , … , x n ) ∈ R D D = ∑ i = 1 n d i D = \sum_{i=1}^n d_i D = ∑ i = 1 n d i i ∈ [ n ] i \in[n] i ∈ [ n ] f i ( x i ; x − i ) = f i ( x 1 , … , x n ) : R D → R f_i(x^i;x^{-i}) = f_i(x^1,\ldots,x^n): \mathbb{R}^D \to\mathbb{R} f i ( x i ; x − i ) = f i ( x 1 , … , x n ) : R D → R x i ∈ R d i x^i \in\mathbb{R}^{d_i} x i ∈ R d i x − i = ( x 1 , … , x i − 1 , x i + 1 , … , x n ) ∈ R D − d i x^{-i} = (x^1,\ldots,x^{i-1},x^{i+1},\ldots,x^n) \in\mathbb{R}^{D-d_i} x − i = ( x 1 , … , x i − 1 , x i + 1 , … , x n ) ∈ R D − d i x ⋆ = ( x ⋆ 1 , … , x ⋆ n ) ∈ R D \mathbf{x}_\star= (x_\star^1,\ldots,x_\star^n) \in\mathbb{R}^D x ⋆ = ( x ⋆ 1 , … , x ⋆ n ) ∈ R D
f i ( x ⋆ i ; x ⋆ − i ) ≤ f i ( x i ; x ⋆ − i ) , ∀ x i ∈ R d i , ∀ i ∈ [ n ] . (1) f_i(x_\star^i;x_\star^{-i}) \leq f_i(x^i;x_\star^{-i}), \quad\forall x^i \in\mathbb{R}^{d_i}, \quad\forall i \in[n]. \tag*{(1)} f i ( x ⋆ i ; x ⋆ − i ) ≤ f i ( x i ; x ⋆ − i ) , ∀ x i ∈ R d i , ∀ i ∈ [ n ] . (1) We consider stochastic objectives of the form f i ( x i ; x − i ) = E ξ i ∼ D i [ f i , ξ i ( x i ; x − i ) ] f_i(x^i;x^{-i}) = \mathbb{E}_{\xi^i \sim\mathcal{D}_i}[f_{i,\xi^i}(x^i;x^{-i})] f i ( x i ; x − i ) = E ξ i ∼ D i [ f i , ξ i ( x i ; x − i )] D i \mathcal{D}_i D i i i i f i , ξ i f_{i,\xi^i} f i , ξ i ξ i \xi^i ξ i D i \mathcal{D}_i D i f i ( x i ; x − i ) = 1 M i ∑ m = 1 M i f i , m ( x i ; x − i ) f_i(x^i;x^{-i}) = \frac{1}{M_i}\sum_{m=1}^{M_i} f_{i,m}(x^i;x^{-i}) f i ( x i ; x − i ) = M i 1 ∑ m = 1 M i f i , m ( x i ; x − i ) i i i f i f_i f i 1 , … , M i 1,\ldots,M_i 1 , … , M i
The algorithms considered in this paper may involve two sources of randomness: the mini-batch ξ k i \xi_k^i ξ k i g k i g_k^i g k i Q i Q^i Q i u p i u_p^i u p i E ξ k i \mathbb{E}_{\xi_k^i} E ξ k i E Q i \mathbb{E}_{Q^i} E Q i E Q \mathbb{E}_Q E Q E [ ⋅ ] \mathbb{E}[\cdot] E [ ⋅ ] ∇ f i ( x i ; x − i ) \nabla f_i(x^i;x^{-i}) ∇ f i ( x i ; x − i ) ∇ x i f i ( x i ; x − i ) \nabla_{x^i}f_i(x^i;x^{-i}) ∇ x i f i ( x i ; x − i ) x i x^i x i x − i x^{-i} x − i
Multiplayer federated learning (MpFL). The MpFL framework focuses on solving an n n n (1) ) when the players communicate via a central server to reach an equilibrium. Players exchange their strategy vectors x i x^i x i communication/synchronization through the central server occurs. Between synchronizations, each player adjusts their strategies based on the recently received information of the other players’ strategies through local optimization loops. These parallel local computations are called a single communication round .
Figure 1. Illustration of the MpFL setting. Each player i i i x i x^i x i f i ( x 1 , … , x n ) f_i(x^1,\ldots,x^n) f i ( x 1 , … , x n ) x ⋆ ∈ R D \mathbf{x}_\star\in\mathbb{R}^D x ⋆ ∈ R D
PEARL-SGD algorithm. In order to find x ⋆ \mathbf{x}_\star x ⋆ (1) in a communication-efficient manner, [45 ] proposed PEARL-SGD , where each player runs a fixed number of iterations τ \tau τ p p p x τ p i x_{\tau p}^i x τ p i i ∈ [ n ] i \in[n] i ∈ [ n ] x τ p \mathbf{x}_{\tau p} x τ p i ∈ [ n ] i \in[n] i ∈ [ n ] τ \tau τ x i x^i x i f i f_i f i x − i x^{-i} x − i
One limitation of PEARL-SGD is that the full joint strategy vector x \mathbf{x} x x \mathbf{x} x i ∈ [ n ] i \in[n] i ∈ [ n ] Q i Q^{i} Q i Q i Q^{i} Q i x ~ τ p i \widetilde{x}_{\tau_p}^{i} x τ p i Figure 2 .
Instead, we use an increment-sharing reformulation of PEARL-SGD. In this form, after the local training round p p p i i i u p i = x ~ τ ( p + 1 ) i − x ~ τ p i u_{p}^{i}=\widetilde{x}_{\tau(p+1)}^{i}-\widetilde{x}_{\tau_p}^{i} u p i = x τ ( p + 1 ) i − x τ p i x ~ τ ( p + 1 ) i \widetilde{x}_{\tau(p+1)}^{i} x τ ( p + 1 ) i Δ \Delta Δ Figure 2 , we introduce the Generalized PEARL-SGD (Algorithm 1) update rule based on this increment-sharing mechanism and provide its convergence analysis.
Equivalence between strategy and increment sharing
Let us consider the special case of the generalized PEARL-SGD (Algorithm 1) where Q i = I d Q^{i}=\mathrm{Id} Q i = Id g k i g_{k}^{i} g k i
g k i = ∇ f i , ξ k i ( x ~ k i ; x τ p − i ) : = 1 ∣ ξ k i ∣ ∑ m ∈ ξ k i ∇ f i , m ( x ~ k i ; x τ p − i ) . (2) g_{k}^{i}=\nabla f_{i,\xi_{k}^{i}}(\widetilde{x}_{k}^{i};x_{\tau_p}^{-i}) := \frac{1}{\lvert\xi_{k}^{i}\rvert}\sum_{m\in\xi_{k}^{i}}\nabla f_{i,m}(\widetilde{x}_{k}^{i};x_{\tau_p}^{-i}). \tag*{(2)} g k i = ∇ f i , ξ k i ( x k i ; x τ p − i ) := ∣ ξ k i ∣ 1 m ∈ ξ k i ∑ ∇ f i , m ( x k i ; x τ p − i ) . (2) Here ξ k i \xi_{k}^{i} ξ k i D i \mathcal{D}_{i} D i Δ \Delta Δ [45 ] only in what is communicated. In PEARL-SGD, the vectors sent from player i i i x τ ( p + 1 ) i x_{\tau(p+1)}^{i} x τ ( p + 1 ) i x τ ( p + 1 ) x_{\tau(p+1)} x τ ( p + 1 ) q p i = u p i = x ~ τ ( p + 1 ) i − x ~ τ p i q_{p}^{i}=u_{p}^{i}=\widetilde{x}_{\tau(p+1)}^{i}-\widetilde{x}_{\tau_p}^{i} q p i = u p i = x τ ( p + 1 ) i − x τ p i q p q_{p} q p Δ \Delta Δ
Proposition 2.1. PEARL-SGD-Δ \Delta Δ Q i = I d Q^{i}=\mathrm{Id} Q i = Id g k i = ∇ f i , ξ k i ( x ~ k i ; x τ p − i ) g_{k}^{i}=\nabla f_{i,\xi_{k}^{i}}(\widetilde{x}_{k}^{i};x_{\tau_p}^{-i}) g k i = ∇ f i , ξ k i ( x k i ; x τ p − i )
x ~ k i for all k = 0 , … , τ R and i = 1 , … , n . \tilde{x}^{i}_{k}\text{ for all }k=0,\ldots,\tau R\text{ and }i=1,\ldots,n. x ~ k i for all k = 0 , … , τ R and i = 1 , … , n . Proof. We use induction on k k k x k i x^{i}_{k} x k i i = 1 , … , n i=1,\ldots,n i = 1 , … , n k = 0 k=0 k = 0 0 ≤ p ≤ R − 1 0\le p\le R-1 0 ≤ p ≤ R − 1 ℓ = 0 , … , τ p \ell=0,\ldots,\tau p ℓ = 0 , … , τ p x ~ τ p i = x τ p i \tilde{x}^{i}_{\tau p}=x^{i}_{\tau p} x ~ τ p i = x τ p i Δ \Delta Δ x ~ k + 1 i = x ~ k i − γ k g k i \tilde{x}^{i}_{k+1}=\tilde{x}^{i}_{k}-\gamma_k g^{i}_{k} x ~ k + 1 i = x ~ k i − γ k g k i k = τ p , … , τ ( p + 1 ) − 1 k=\tau p,\ldots,\tau(p+1)-1 k = τ p , … , τ ( p + 1 ) − 1
x τ ( p + 1 ) i = x τ p i + q p i = x ~ τ p i + ( x ~ τ ( p + 1 ) i − x ~ τ p i ) = x ~ τ ( p + 1 ) i x^{i}_{\tau(p+1)}=x^{i}_{\tau p}+q^{i}_{p}=\tilde{x}^{i}_{\tau p}+\left(\tilde{x}^{i}_{\tau(p+1)}-\tilde{x}^{i}_{\tau p}\right)=\tilde{x}^{i}_{\tau(p+1)} x τ ( p + 1 ) i = x τ p i + q p i = x ~ τ p i + ( x ~ τ ( p + 1 ) i − x ~ τ p i ) = x ~ τ ( p + 1 ) i because q p i = Q i ( u p i ) = x ~ τ ( p + 1 ) i − x ~ τ p i q^{i}_{p}=Q^{i}(u^{i}_{p})=\tilde{x}^{i}_{\tau(p+1)}-\tilde{x}^{i}_{\tau p} q p i = Q i ( u p i ) = x ~ τ ( p + 1 ) i − x ~ τ p i k = τ p + 1 , … , τ ( p + 1 ) k=\tau p+1,\ldots,\tau(p+1) k = τ p + 1 , … , τ ( p + 1 ) x ~ k i = x ~ τ p i − ∑ ℓ = τ p k − 1 γ ℓ g ℓ i \tilde{x}^{i}_{k}=\tilde{x}^{i}_{\tau p}-\sum_{\ell=\tau p}^{k-1}\gamma_{\ell}g^{i}_{\ell} x ~ k i = x ~ τ p i − ∑ ℓ = τ p k − 1 γ ℓ g ℓ i
For the remainder of the paper, we refer to PEARL-SGD-Δ \Delta Δ
Exact convergence via increment sharing
The comparison in Figure 2 raises a natural question: why does compressing local increments work while directly compressing strategies might not? In this section, we provide an intuitive explanation of this difference. We start by stating a standard condition for compressors in the literature [2 , 12 , 16 ] .
Assumption 2.2. A randomized operator Q : R D → R D Q:\mathbb{R}^{D}\to\mathbb{R}^{D} Q : R D → R D ω ≥ 0 \omega\ge0 ω ≥ 0 v ∈ R D v\in\mathbb{R}^{D} v ∈ R D E [ Q ( v ) ∣ v ] = v \mathbb{E}[Q(v)\mid v]=v E [ Q ( v ) ∣ v ] = v
E [ ∥ Q ( v ) − v ∥ 2 ∣ v ] ≤ ω ∥ v ∥ 2 \mathbb{E}\left[\left\|Q(v)-v\right\|^{2}\mid v\right]\le\omega\left\|v\right\|^{2} E [ ∥ Q ( v ) − v ∥ 2 ∣ v ] ≤ ω ∥ v ∥ 2 where Q ( v ) = ( Q 1 ( v 1 ) , … , Q n ( v n ) ) Q(v)=(Q^{1}(v^{1}),\ldots,Q^{n}(v^{n})) Q ( v ) = ( Q 1 ( v 1 ) , … , Q n ( v n ))
Here ω \omega ω ω = 0 \omega=0 ω = 0 Q = I d Q=\mathrm{Id} Q = Id v v v v v v
Analogously, in distributed optimization, quantized SGD [2 ] may not converge to the global minimizer x ∗ x_{\ast} x ∗ x ∗ x_{\ast} x ∗ [29 ] , which incorporates an additional memory vector to make the compressed quantity approach zero as the algorithm trajectory approaches x ∗ x_{\ast} x ∗ § 12 .
Assumptions for convergence analysis
For our convergence analysis, we use the same assumptions on the multiplayer game and the joint gradient operator as in the original analysis of vanilla PEARL-SGD [45 ] , which are standard in stochastic games and variational inequalities [4 , 8 , 10 , 13 , 26 ] . For the variance-reduced methods, PEARL-SVRG and C-PEARL-SVRG, we additionally require the finite-sum structure introduced above and component-wise smoothness (Assumption 3.1 ), as is standard for SVRG-type methods.
Assumptions on the multiplayer game For every player i ∈ [ n ] i \in[n] i ∈ [ n ] f i ( ⋅ ; x − i ) f_i(\cdot; x^{-i}) f i ( ⋅ ; x − i ) i i i
Assumption 2.3 (Convexity (CVX)). For every i ∈ [ n ] i \in[n] i ∈ [ n ] x − i ∈ R D − d i x^{-i} \in\mathbb{R}^{D-d_i} x − i ∈ R D − d i x i , y i ∈ R d i x^i,y^i \in\mathbb{R}^{d_i} x i , y i ∈ R d i
f i ( y i ; x − i ) ≥ f i ( x i ; x − i ) + ⟨ ∇ f i ( x i ; x − i ) , y i − x i ⟩ . f_i(y^i;x^{-i}) \ge f_i(x^i;x^{-i}) + \langle\nabla f_i(x^i;x^{-i}), y^i-x^i\rangle. f i ( y i ; x − i ) ≥ f i ( x i ; x − i ) + ⟨ ∇ f i ( x i ; x − i ) , y i − x i ⟩ . Assumption 2.4 (Smoothness (SM)). For every i ∈ [ n ] i \in[n] i ∈ [ n ] x − i ∈ R D − d i x^{-i} \in\mathbb{R}^{D-d_i} x − i ∈ R D − d i x i , y i ∈ R d i x^i,y^i \in\mathbb{R}^{d_i} x i , y i ∈ R d i
∥ ∇ f i ( x i ; x − i ) − ∇ f i ( y i ; x − i ) ∥ ≤ L i ∥ x i − y i ∥ . \lVert\nabla f_i(x^i;x^{-i})-\nabla f_i(y^i;x^{-i})\rVert\le L_i\lVert x^i-y^i\rVert. ∥ ∇ f i ( x i ; x − i ) − ∇ f i ( y i ; x − i )∥ ≤ L i ∥ x i − y i ∥ . For the non-variance-reduced methods, we additionally assume bounded variance of the stochastic gradients.
Assumption 2.5 (Unbiased stochastic gradients and bounded variance (BV)). For every player i ∈ [ n ] i \in[n] i ∈ [ n ] ξ i ∼ D i \xi^i \sim D_i ξ i ∼ D i x i ∈ R d i x^i \in\mathbb{R}^{d_i} x i ∈ R d i x − i ∈ R D − d i x^{-i} \in\mathbb{R}^{D-d_i} x − i ∈ R D − d i E ξ i [ ∇ f i , ξ i ( x i ; x − i ) ] = ∇ f i ( x i ; x − i ) \mathbb{E}_{\xi^i}[\nabla f_{i,\xi^i}(x^i;x^{-i})]=\nabla f_i(x^i;x^{-i}) E ξ i [ ∇ f i , ξ i ( x i ; x − i )] = ∇ f i ( x i ; x − i ) σ i ≥ 0 \sigma_i \ge0 σ i ≥ 0
E ξ i [ ∥ ∇ f i , ξ i ( x i ; x − i ) − ∇ f i ( x i ; x − i ) ∥ 2 ] ≤ σ i 2 . \mathbb{E}_{\xi^i}\left[\lVert\nabla f_{i,\xi^i}(x^i;x^{-i})-\nabla f_i(x^i;x^{-i})\rVert^2\right]\le\sigma_i^2. E ξ i [ ∥ ∇ f i , ξ i ( x i ; x − i ) − ∇ f i ( x i ; x − i ) ∥ 2 ] ≤ σ i 2 . Assumptions on the joint gradient operator We now state the assumptions on the joint gradient operator F : R D → R D F:\mathbb{R}^D\to\mathbb{R}^D F : R D → R D F ( x ) = ( ∇ f 1 ( x 1 ; x − 1 ) , … , ∇ f n ( x n ; x − n ) ) F(x)=(\nabla f_1(x^1;x^{-1}),\ldots,\nabla f_n(x^n;x^{-n})) F ( x ) = ( ∇ f 1 ( x 1 ; x − 1 ) , … , ∇ f n ( x n ; x − n )) x ⋆ = ( x ⋆ 1 , … , x ⋆ n ) x_\star=(x_\star^1,\ldots,x_\star^n) x ⋆ = ( x ⋆ 1 , … , x ⋆ n ) F ( x ⋆ ) = 0 F(x_\star)=0 F ( x ⋆ ) = 0 F F F [3 , 26 ] . As a result, quasi-strong monotonicity can hold for some non-monotone games, while star-cocoercivity can hold beyond the globally Lipschitz case.
Assumption 2.6 (Quasi-strong monotonicity (QSM)). There exists μ > 0 \mu> 0 μ > 0 x ∈ R D x \in\mathbb{R}^D x ∈ R D
⟨ F ( x ) , x − x ⋆ ⟩ ≥ μ ∥ x − x ⋆ ∥ 2 . \langle F(x),x-x_\star\rangle\ge\mu\lVert x-x_\star\rVert^2. ⟨ F ( x ) , x − x ⋆ ⟩ ≥ μ ∥ x − x ⋆ ∥ 2 . Assumption 2.7 (Star-cocoercivity (SCO)). There exists ℓ > 0 \ell> 0 ℓ > 0 x ∈ R D x \in\mathbb{R}^D x ∈ R D
⟨ F ( x ) , x − x ⋆ ⟩ ≥ 1 ℓ ∥ F ( x ) ∥ 2 . \langle F(x),x-x_\star\rangle\ge\frac{1}{\ell}\lVert F(x)\rVert^2. ⟨ F ( x ) , x − x ⋆ ⟩ ≥ ℓ 1 ∥ F ( x ) ∥ 2 . Together, (QSM) and (SCO) imply μ ∥ x − x ⋆ ∥ ≤ ∥ F ( x ) ∥ ≤ ℓ ∥ x − x ⋆ ∥ \mu\lVert x-x_\star\rVert\le\lVert F(x)\rVert\le\ell\lVert x-x_\star\rVert μ ∥ x − x ⋆ ∥ ≤ ∥ F ( x )∥ ≤ ℓ ∥ x − x ⋆ ∥ x ∈ R D x \in\mathbb{R}^D x ∈ R D μ ≤ ℓ \mu\le\ell μ ≤ ℓ κ = ℓ / μ ≥ 1 \kappa=\ell/\mu\ge1 κ = ℓ / μ ≥ 1 condition number of the game.
Advanced PEARL Variants for MpFL
Algorithm 1 provides two directions of flexibility: the local gradient estimator g k i g_k^i g k i Q i Q^i Q i g k i g_k^i g k i Q i Q^i Q i
Algorithm 1 Generalized PEARL-SGD
Input: Step-size γ k > 0 \gamma_k > 0 γ k > 0 τ ≥ 1 \tau\ge1 τ ≥ 1 R ≥ 1 R \ge1 R ≥ 1 { Q i } i = 1 n \{Q^i\}_{i=1}^n { Q i } i = 1 n { x 0 i } i = 1 n \{x_0^i\}_{i=1}^n { x 0 i } i = 1 n
Master collects x 0 i x_0^i x 0 i i ∈ [ n ] i \in[n] i ∈ [ n ]
Master broadcasts x − τ = x 0 \mathbf{x}_{-\tau} = \mathbf{x}_0 x − τ = x 0
for p = 0 , … , R − 1 p = 0, \ldots, R - 1 p = 0 , … , R − 1 do
for i = 1 , … , n i = 1, \ldots, n i = 1 , … , n do
Set x τ p ← x τ ( p − 1 ) + q p − 1 \mathbf{x}_{\tau p} \leftarrow\mathbf{x}_{\tau(p-1)} + \mathbf{q}_{p-1} x τ p ← x τ ( p − 1 ) + q p − 1 q − 1 = 0 \mathbf{q}_{-1} = 0 q − 1 = 0
x ~ τ p i ← x τ p i \widetilde{x}_{\tau p}^i \leftarrow x_{\tau p}^i x τ p i ← x τ p i
for k = τ p , … , τ ( p + 1 ) − 1 k = \tau p, \ldots, \tau(p+1) - 1 k = τ p , … , τ ( p + 1 ) − 1 do
Sample a mini-batch ξ k i ∼ D i \xi_k^i \sim D_i ξ k i ∼ D i
Compute an estimator g k i g_k^i g k i E ξ k i [ g k i ∣ x ~ k i , x τ p − i ] = ∇ f i ( x ~ k i ; x τ p − i ) \mathbb{E}_{\xi_k^i}[g_k^i \mid\widetilde{x}_k^i, x_{\tau p}^{-i}] = \nabla f_i(\widetilde{x}_k^i; x_{\tau p}^{-i}) E ξ k i [ g k i ∣ x k i , x τ p − i ] = ∇ f i ( x k i ; x τ p − i )
x ~ k + 1 i ← x ~ k i − γ k g k i \widetilde{x}_{k+1}^i \leftarrow\widetilde{x}_k^i - \gamma_k g_k^i x k + 1 i ← x k i − γ k g k i
end for
u p i ← x ~ τ ( p + 1 ) i − x ~ τ p i u_p^i \leftarrow\widetilde{x}_{\tau(p+1)}^i - \widetilde{x}_{\tau p}^i u p i ← x τ ( p + 1 ) i − x τ p i
q p i ← Q i ( u p i ) q_p^i \leftarrow Q^i(u_p^i) q p i ← Q i ( u p i )
Player i i i q p i q_p^i q p i
end for
Master collects q p i q_p^i q p i i ∈ [ n ] i \in[n] i ∈ [ n ]
Master broadcasts q p = ( q p 1 , … , q p n ) \mathbf{q}_p = (q_p^1, \ldots, q_p^n) q p = ( q p 1 , … , q p n )
end for
Output: x τ ( R − 1 ) + q R − 1 = x τ R ∈ R D x_{\tau(R-1)} + q_{R-1} = x_{\tau R} \in\mathbb{R}^D x τ ( R − 1 ) + q R − 1 = x τ R ∈ R D
Variance Reduction via PEARL-SVRG
PEARL-SVRG is a variance-reduced [5 , 11 , 32 , 42 ] MpFL method obtained as a special case of Algorithm 1 with Q i = I d Q^i = \mathrm{Id} Q i = Id
g k i = ∇ f i , ξ k i ( x ~ k i ; x τ p − i ) − ∇ f i , ξ k i ( x τ p i ; x τ p − i ) + ∇ f i ( x τ p i ; x τ p − i ) . (3) g_k^i = \nabla f_{i,\xi_k^i}(\widetilde{x}_k^i; x_{\tau p}^{-i}) - \nabla f_{i,\xi_k^i}(x_{\tau p}^i; x_{\tau p}^{-i}) + \nabla f_i(x_{\tau p}^i; x_{\tau p}^{-i}). \tag*{(3)} g k i = ∇ f i , ξ k i ( x k i ; x τ p − i ) − ∇ f i , ξ k i ( x τ p i ; x τ p − i ) + ∇ f i ( x τ p i ; x τ p − i ) . (3) At the beginning of communication round p p p i i i ∇ f i ( x τ p i ; x τ p − i ) \nabla f_i(x_{\tau p}^i; x_{\tau p}^{-i}) ∇ f i ( x τ p i ; x τ p − i ) x τ p x_{\tau p} x τ p τ \tau τ g k i g_k^i g k i (3) ) and updates its local strategy as in Algorithm 1. Since Q i = I d Q^i = \mathrm{Id} Q i = Id f i , m f_{i,m} f i , m
Assumption 3.1. For all i ∈ [ n ] i \in[n] i ∈ [ n ] m ∈ [ M i ] m \in[M_i] m ∈ [ M i ] x − i ∈ R D − d i x^{-i} \in\mathbb{R}^{D-d_i} x − i ∈ R D − d i f i , m ( ⋅ ; x − i ) : R d i → R f_{i,m}(\cdot; x^{-i}): \mathbb{R}^{d_i} \to\mathbb{R} f i , m ( ⋅ ; x − i ) : R d i → R L i L_i L i u , v ∈ R d i u, v \in\mathbb{R}^{d_i} u , v ∈ R d i
∥ ∇ f i , m ( u ; x − i ) − ∇ f i , m ( v ; x − i ) ∥ ≤ L i ∥ u − v ∥ . \left\lVert\nabla f_{i,m}(u; x^{-i}) - \nabla f_{i,m}(v; x^{-i}) \right\rVert\le L_i \lVert u - v \rVert. ∇ f i , m ( u ; x − i ) − ∇ f i , m ( v ; x − i ) ≤ L i ∥ u − v ∥ . Table 1: Special cases recovered by Algorithm 1. Id is the identity map, and Q i Q^i Q i
Table 1.
Compressed PEARL Variants
Both PEARL-SGD and PEARL-SVRG communicate the full strategy increment at synchronization. We introduce C-PEARL-SGD and C-PEARL-SVRG as their compressed variants, where players communicate compressed local strategy increments rather than the full increments.
C-PEARL-SGD algorithm
C-PEARL-SGD uses the same gradient estimator (2) and local updates as PEARL-SGD, but applies the compression maps Q i Q^i Q i i i i q p i = Q i ( u p i ) q_p^i=Q^i(u_p^i) q p i = Q i ( u p i )
C-PEARL-SVRG algorithm
C-PEARL-SVRG is the compressed variant of PEARL-SVRG, or equivalently, the variance-reduced variant of C-PEARL-SGD. It is obtained from Algorithm 1 by choosing the variance-reduced gradient estimator (3) and applying compression to the strategy increments. This algorithm combines the benefits of both variants by allowing compression to reduce communication overhead while retaining exact convergence to the equilibrium in the stochastic finite-sum setting, as shown in Corollary 4.7 .
Convergence Guarantees
In this section, we establish convergence guarantees for PEARL variants. Algorithm 1 provides a generalized algorithmic skeleton that recovers all of them as special cases, and we follow the same viewpoint in our analysis. We identify a common bound (4) tracking the progress of the algorithms over communication rounds, and formalize it in Assumption 4.1 . We then show in Lemma 4.2 that all four algorithms satisfy this bound with algorithm-specific constants. Our “Master Theorem” 4.3 uses this bound to establish the convergence guarantees for all variants.
Unified Parametric Assumption
We introduce a unified parametric assumption used in all our convergence results, similar to the unified approaches of [3 , 11 , 12 , 14 ] . Unlike these works, which bound the second moment of the stochastic gradient or operator at every iteration, we bound the distance to the equilibrium after each communication round. We do not require an auxiliary sequence of non-negative variables since we do not maintain separate memory vectors as in certain compression-based methods [29 ] .
Assumption 4.1. Let F p \mathcal{F}_p F p σ \sigma σ p p p x τ p x_{\tau p} x τ p F p \mathcal{F}_p F p E p [ ⋅ ] : = E [ ⋅ ∣ F p ] \mathbb{E}_p[\cdot] := \mathbb{E}[\cdot\mid\mathcal{F}_p] E p [ ⋅ ] := E [ ⋅ ∣ F p ] γ k ≡ γ > 0 \gamma_k \equiv\gamma> 0 γ k ≡ γ > 0 A τ , B τ ≥ 0 A_\tau,B_\tau\ge0 A τ , B τ ≥ 0 τ \tau τ γ \gamma γ p p p
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ ) . (4) \mathbb{E}_p\left[\left\|x_{\tau(p+1)}-x_\star\right\|^2\right] \le\left\|x_{\tau p}-x_\star\right\|^2 - 2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle+ \gamma^2\tau^2\left(A_\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle+B_\tau\right). \tag*{(4)} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ ) . (4) Here, E p \mathbb{E}_p E p p p p g k i g_k^i g k i Q i Q^i Q i (4) , A τ A_\tau A τ B τ B_\tau B τ B τ = 0 B_\tau=0 B τ = 0 (4) is satisfied for each of the proposed PEARL methods.
Lemma 4.2. Assume ( C V X ) (CVX) ( C V X ) ( S M ) (SM) ( S M ) ( Q S M ) (QSM) ( QS M ) ( S C O ) (SCO) ( S C O ) κ = ℓ / μ \kappa=\ell/\mu κ = ℓ / μ σ 2 = ∑ i = 1 n σ i 2 \sigma^2=\sum_{i=1}^n\sigma_i^2 σ 2 = ∑ i = 1 n σ i 2
A τ G D : = ℓ + 2 ( τ − 1 ) τ L max κ 3 , A_\tau^{\mathrm{GD}} := \ell+\frac{2(\tau-1)}{\tau}L_{\max}\sqrt{\frac{\kappa}{3}}, A τ GD := ℓ + τ 2 ( τ − 1 ) L m a x 3 κ , B τ G D : = σ 2 τ [ 1 + ( τ − 1 ) L max ( 4 γ τ + 1 + 4 γ τ 2 L max 2 τ ℓ μ / 3 ) ] , B_\tau^{\mathrm{GD}} := \frac{\sigma^2}{\tau}\left[1+(\tau-1)L_{\max}\left(4\gamma\tau+\frac{1+4\gamma\tau^2L_{\max}}{2\tau\sqrt{\ell\mu/3}}\right)\right], B τ GD := τ σ 2 [ 1 + ( τ − 1 ) L m a x ( 4 γ τ + 2 τ ℓ μ /3 1 + 4 γ τ 2 L m a x ) ] , U τ : = σ 2 τ ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L max ) , U_\tau:= \frac{\sigma^2}{\tau}\left(1+2(\tau-1)(\tau+1)\gamma L_{\max}\right), U τ := τ σ 2 ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L m a x ) , A τ V R : = 4 ℓ + 4 ( τ − 1 ) τ L max κ 3 , A_\tau^{\mathrm{VR}} := 4\ell+\frac{4(\tau-1)}{\tau}L_{\max}\sqrt{\frac{\kappa}{3}}, A τ VR := 4 ℓ + τ 4 ( τ − 1 ) L m a x 3 κ , and L max = max { L 1 , … , L n } L_{\max}=\max\{L_1,\ldots,L_n\} L m a x = max { L 1 , … , L n }
PEARL-SGD. A τ = A τ G D A_\tau=A_\tau^{\mathrm{GD}} A τ = A τ GD B τ = B τ G D B_\tau=B_\tau^{\mathrm{GD}} B τ = B τ GD ( B V ) (BV) ( B V ) 0 < γ k ≡ γ ≤ 1 ℓ τ + 2 ( τ − 1 ) L max κ 0<\gamma_k\equiv\gamma\le\frac{1}{\ell\tau+2(\tau-1)L_{\max}\sqrt{\kappa}} 0 < γ k ≡ γ ≤ ℓ τ + 2 ( τ − 1 ) L m a x κ 1
PEARL-SVRG. A τ = A τ V R A_\tau=A_\tau^{\mathrm{VR}} A τ = A τ VR B τ = 0 B_\tau=0 B τ = 0 0 < γ k ≡ γ ≤ 1 2 L max τ 0<\gamma_k\equiv\gamma\le\frac{1}{2L_{\max}\tau} 0 < γ k ≡ γ ≤ 2 L m a x τ 1
C-PEARL-SGD. A τ = A τ G D + ω ℓ A_\tau=A_\tau^{\mathrm{GD}}+\omega\ell A τ = A τ GD + ω ℓ B τ = B τ G D + ω U τ B_\tau=B_\tau^{\mathrm{GD}}+\omega U_\tau B τ = B τ GD + ω U τ ( B V ) (BV) ( B V ) 0 < γ k ≡ γ ≤ 1 ℓ τ + 2 ( τ − 1 ) L max κ 0<\gamma_k\equiv\gamma\le\frac{1}{\ell\tau+2(\tau-1)L_{\max}\sqrt{\kappa}} 0 < γ k ≡ γ ≤ ℓ τ + 2 ( τ − 1 ) L m a x κ 1
C-PEARL-SVRG. A τ = A τ V R + 4 ω ℓ A_\tau=A_\tau^{\mathrm{VR}}+4\omega\ell A τ = A τ VR + 4 ω ℓ B τ = 0 B_\tau=0 B τ = 0 0 < γ k ≡ γ ≤ 1 2 L max τ 0<\gamma_k\equiv\gamma\le\frac{1}{2L_{\max}\tau} 0 < γ k ≡ γ ≤ 2 L m a x τ 1
The differences among the algorithms are encoded in the constants A τ A_\tau A τ B τ B_\tau B τ B τ = 0 B_\tau=0 B τ = 0 ω \omega ω A τ A_\tau A τ B τ B_\tau B τ
Convergence of PEARL Variants
We now present our general convergence result under Assumption 4.1 and ( Q S M ) (QSM) ( QS M )
Table 2. Overview of the PEARL variants and their convergence guarantees with constant γ \gamma γ
Theorem 4.3. Assume ( Q S M ) (QSM) ( QS M ) Assumption 4.1 hold. Suppose A τ ≥ μ A_{\tau} \ge\mu A τ ≥ μ 0 < γ < 2 τ A τ 0 < \gamma< \frac{2}{\tau A_{\tau}} 0 < γ < τ A τ 2 ζ : = 2 − γ τ A τ > 0 \zeta:= 2-\gamma\tau A_{\tau} > 0 ζ := 2 − γ τ A τ > 0 R ≥ 0 R \ge0 R ≥ 0
E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ ) R ∥ x 0 − x ⋆ ∥ 2 + γ τ B τ μ ζ . \mathbb{E}\left[\left\|x_{\tau R}-x_{\star}\right\|^{2}\right] \le\left(1-\gamma\tau\mu\zeta\right)^{R}\left\|x_{0}-x_{\star}\right\|^{2}+\frac{\gamma\tau B_{\tau}}{\mu\zeta}. E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ ) R ∥ x 0 − x ⋆ ∥ 2 + μ ζ γ τ B τ . This result gives linear convergence to a neighborhood of x ⋆ x_{\star} x ⋆ B τ = 0 B_{\tau}=0 B τ = 0 Lemma 4.2 to obtain convergence guarantees for each PEARL variant.
Corollary 4.4. Under the assumptions of Lemma 4.2 , if 0 < γ < min { 1 ℓ τ + 2 ( τ − 1 ) L max κ , 2 τ A τ G D } 0 < \gamma< \min\left\{\frac{1}{\ell_{\tau+2(\tau-1)L_{\max}\sqrt{\kappa}}},\frac{2}{\tau A_{\tau}^{\mathrm{GD}}}\right\} 0 < γ < min { ℓ τ + 2 ( τ − 1 ) L m a x κ 1 , τ A τ GD 2 } ζ G D : = 2 − γ τ A τ G D \zeta^{\mathrm{GD}}:=2-\gamma\tau A_{\tau}^{\mathrm{GD}} ζ GD := 2 − γ τ A τ GD
E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ G D ) R ∥ x 0 − x ⋆ ∥ 2 + γ τ B τ G D μ ζ G D . \mathbb{E}\left[\left\|x_{\tau R}-x_{\star}\right\|^{2}\right] \le\left(1-\gamma\tau\mu\zeta^{\mathrm{GD}}\right)^{R}\left\|x_{0}-x_{\star}\right\|^{2}+\frac{\gamma\tau B_{\tau}^{\mathrm{GD}}}{\mu\zeta^{\mathrm{GD}}}. E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ GD ) R ∥ x 0 − x ⋆ ∥ 2 + μ ζ GD γ τ B τ GD . Corollary 4.4 gives linear convergence to a stochastic neighborhood and recovers the convergence guarantee of the original PEARL-SGD [45 Theorem 3.4] (up to some typo corrections in constants). When τ = 1 \tau=1 τ = 1 [3 ] , while increasing τ \tau τ [45 Corollary 3.5] .
Corollary 4.5. Under the assumptions of Lemma 4.2 , if 0 < γ < min { 1 2 L max τ , 2 τ A τ V R } 0 < \gamma< \min\left\{\frac{1}{2L_{\max}\tau},\frac{2}{\tau A_{\tau}^{\mathrm{VR}}}\right\} 0 < γ < min { 2 L m a x τ 1 , τ A τ VR 2 } ζ V R : = 2 − γ τ A τ V R \zeta^{\mathrm{VR}}:=2-\gamma\tau A_{\tau}^{\mathrm{VR}} ζ VR := 2 − γ τ A τ VR
E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ V R ) R ∥ x 0 − x ⋆ ∥ 2 . \mathbb{E}\left[\left\|x_{\tau R}-x_{\star}\right\|^{2}\right] \le\left(1-\gamma\tau\mu\zeta^{\mathrm{VR}}\right)^{R}\left\|x_{0}-x_{\star}\right\|^{2}. E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ VR ) R ∥ x 0 − x ⋆ ∥ 2 . Unlike PEARL-SGD with a constant step-size and nonzero stochastic gradient variance, the bound contains no neighborhood term. Hence, PEARL-SVRG converges linearly to the exact equilibrium, consistent with standard variance-reduced methods like SVRG or L-SVRG [3 , 11 , 32 ] .
Corollary 4.6. Under the assumptions of Lemma 4.2 , if 0 < γ < min { 1 ℓ τ + 2 ( τ − 1 ) L max κ , 2 τ ( A τ G D + ω ℓ ) } 0 < \gamma< \min\left\{\frac{1}{\ell_{\tau+2(\tau-1)L_{\max}\sqrt{\kappa}}},\frac{2}{\tau(A_{\tau}^{\mathrm{GD}}+\omega\ell)}\right\} 0 < γ < min { ℓ τ + 2 ( τ − 1 ) L m a x κ 1 , τ ( A τ GD + ω ℓ ) 2 }
and ζ C G D : = 2 − γ τ ( A τ G D + ω ℓ ) \zeta^{\mathrm{CGD}} := 2-\gamma\tau(A_{\tau}^{\mathrm{GD}}+\omega\ell) ζ CGD := 2 − γ τ ( A τ GD + ω ℓ )
E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ C G D ) R ∥ x 0 − x ⋆ ∥ 2 + γ τ ( B τ G D + ω U τ ) μ ζ C G D . \mathbb{E}\left[\left\|x_{\tau R}-x_{\star}\right\|^{2}\right] \leq\left(1-\gamma\tau\mu\zeta^{\mathrm{CGD}}\right)^{R}\left\|x_{0}-x_{\star}\right\|^{2}+\frac{\gamma\tau\left(B_{\tau}^{\mathrm{GD}}+\omega U_{\tau}\right)}{\mu\zeta^{\mathrm{CGD}}}. E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ CGD ) R ∥ x 0 − x ⋆ ∥ 2 + μ ζ CGD γ τ ( B τ GD + ω U τ ) . C-PEARL-SGD converges linearly to a neighborhood of the equilibrium, with a potentially larger neighborhood bound than PEARL-SGD due to the additional error from compression. When ω = 0 \omega=0 ω = 0 B τ G D B_{\tau}^{\mathrm{GD}} B τ GD U τ U_{\tau} U τ
Corollary 4.7. Under the assumptions of Lemma 4.2, suppose 0 < γ < min { 1 2 L max τ , 2 τ ( A τ V R + 4 ω ℓ ) } 0<\gamma<\min\left\{\frac{1}{2L_{\max}\tau},\frac{2}{\tau(A_{\tau}^{\mathrm{VR}}+4\omega\ell)}\right\} 0 < γ < min { 2 L m a x τ 1 , τ ( A τ VR + 4 ω ℓ ) 2 } ζ C V R : = 2 − γ τ ( A τ V R + 4 ω ℓ ) \zeta^{\mathrm{CVR}}:=2-\gamma\tau(A_{\tau}^{\mathrm{VR}}+4\omega\ell) ζ CVR := 2 − γ τ ( A τ VR + 4 ω ℓ )
E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ C V R ) R ∥ x 0 − x ⋆ ∥ 2 . \mathbb{E}\left[\left\|x_{\tau R}-x_{\star}\right\|^{2}\right]\leq\left(1-\gamma\tau\mu\zeta^{\mathrm{CVR}}\right)^{R}\left\|x_{0}-x_{\star}\right\|^{2}. E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ CVR ) R ∥ x 0 − x ⋆ ∥ 2 . C-PEARL-SVRG converges linearly to the equilibrium despite using stochastic gradients and communicating compressed strategy increments, and when ω = 0 \omega=0 ω = 0
Numerical Experiments
In this section, we present experiments to illustrate our theoretical results and demonstrate the practical benefits of our proposed algorithms. We consider two settings: a quadratic n n n
Quadratic n n n
We consider a quadratic n n n [6 , 30 , 36 , 37 , 43 ] . Player i ∈ [ n ] i\in[n] i ∈ [ n ]
f i ( x i ; x − i ) : = 1 M ∑ m = 1 M f i , m ( x i ; x − i ) , (5) f_i(x^i;x^{-i}):=\frac{1}{M}\sum_{m=1}^{M}f_{i,m}(x^i;x^{-i}), \tag*{(5)} f i ( x i ; x − i ) := M 1 m = 1 ∑ M f i , m ( x i ; x − i ) , (5) where f i , m ( x i ; x − i ) = 1 2 ⟨ x i , A i , m x i ⟩ + ∑ 1 ≤ j ≤ n j ≠ i ⟨ x i , B i , j , m x j ⟩ + ⟨ a i , m , x i ⟩ f_{i,m}(x^i;x^{-i})=\frac{1}{2}\langle x^i,A_{i,m}x^i\rangle+\sum_{1\leq j\leq n \atop j\neq i}\langle x^i,B_{i,j,m}x^j\rangle+\langle a_{i,m},x^i\rangle f i , m ( x i ; x − i ) = 2 1 ⟨ x i , A i , m x i ⟩ + ∑ j = i 1 ≤ j ≤ n ⟨ x i , B i , j , m x j ⟩ + ⟨ a i , m , x i ⟩ A i , m ∈ R d i × d i A_{i,m}\in\mathbb{R}^{d_i\times d_i} A i , m ∈ R d i × d i B i , j , m ∈ R d i × d j B_{i,j,m}\in\mathbb{R}^{d_i\times d_j} B i , j , m ∈ R d i × d j a i , m ∈ R d i a_{i,m}\in\mathbb{R}^{d_i} a i , m ∈ R d i n = 5 n=5 n = 5 d i = d = 10 d_i=d=10 d i = d = 10 M = 100 M=100 M = 100 A i , m A_{i,m} A i , m B i , j , m B_{i,j,m} B i , j , m i < j i<j i < j d × d d\times d d × d [ μ A , L A ] [\mu_A,L_A] [ μ A , L A ] [ μ B , L B ] [\mu_B,L_B] [ μ B , L B ] d × d d\times d d × d B j , i , m = − B i , j , m T B_{j,i,m}=-B_{i,j,m}^{\mathsf{T}} B j , i , m = − B i , j , m T j > i j>i j > i F F F μ A = 0.01 \mu_A=0.01 μ A = 0.01 L A = 0.1 L_A=0.1 L A = 0.1 μ B = 0 \mu_B=0 μ B = 0 L B = 1.0 L_B=1.0 L B = 1.0 k k k [3 ] with k = 5 k=5 k = 5 k k k k k k d / k d/k d / k
We measure the performance of the PEARL variants using the relative error ∥ x τ p − x ⋆ ∥ 2 ∥ x 0 − x ⋆ ∥ 2 \frac{\left\|x_{\tau p}-x_{\star}\right\|^{2}}{\left\|x_{0}-x_{\star}\right\|^{2}} ∥ x 0 − x ⋆ ∥ 2 ∥ x τ p − x ⋆ ∥ 2 10 8 10^{8} 1 0 8 τ \tau τ { 10 − 2 , 10 − 3 , 10 − 4 , 10 − 5 } \{10^{-2},10^{-3},10^{-4},10^{-5}\} { 1 0 − 2 , 1 0 − 3 , 1 0 − 4 , 1 0 − 5 } Figure 3 a demonstrates that PEARL-SGD converges to a neighborhood, while PEARL-SVRG converges linearly to the exact solution.
Figure 3. Performance plot of PEARL algorithm variants on the quadratic n n n (5) using tuned step-sizes. The first two plots illustrate the convergence of PEARL-SVRG to the exact solution, traded off with increased oracle complexity. The rightmost plot compares all variants with τ = 20 \tau= 20 τ = 20
For both algorithms, larger τ \tau τ Figure 3 b.
When we additionally compare the compressed variants, Figure 3 c shows that they require fewer communicated bits than their non-compressed counterparts during the initial phase where the error decreases nearly linearly. C-PEARL-SGD converges to a larger neighborhood than PEARL-SGD and has the worst final performance, whereas C-PEARL-SVRG converges to the solution and performs best at high accuracy in terms of communicated bits.
Remark. Figure 2 uses the same setup as in this experiment with τ = 5 \tau= 5 τ = 5 γ = 10 − 3 \gamma= 10^{-3} γ = 1 0 − 3 L B = 2 L_B = 2 L B = 2 5 × 10 4 5 \times10^4 5 × 1 0 4
Distributed spectrum sensing
We consider the distributed spectrum sensing problem of [6 ] . We are given primary users q = 1 , … , N P q = 1, \ldots, N_P q = 1 , … , N P i = 1 , … , N S i = 1, \ldots, N_S i = 1 , … , N S q q q S q ( f ) = ∑ m = 1 N B α q , m ϕ m ( f ) S_q(f) = \sum_{m=1}^{N_B} \alpha_{q,m}\phi_m(f) S q ( f ) = ∑ m = 1 N B α q , m ϕ m ( f ) ϕ m \phi_m ϕ m f f f α q , m \alpha_{q,m} α q , m α ⋆ ∈ R N P N B \alpha_\star\in\mathbb{R}^{N_P N_B} α ⋆ ∈ R N P N B x i ∈ R N P N B x^i \in\mathbb{R}^{N_P N_B} x i ∈ R N P N B N R N_R N R ℓ \ell ℓ r i ℓ , s = Φ i ℓ , s α ⋆ + z i ℓ , s ∈ R N F r_{i\ell,s} = \Phi_{i\ell,s}\alpha_\star+ z_{i\ell,s} \in\mathbb{R}^{N_F} r i ℓ , s = Φ i ℓ , s α ⋆ + z i ℓ , s ∈ R N F s ∈ [ M ] s \in[M] s ∈ [ M ] z i ℓ , s z_{i\ell,s} z i ℓ , s Φ i ℓ , s ∈ R N F × N P N B \Phi_{i\ell,s} \in\mathbb{R}^{N_F \times N_P N_B} Φ i ℓ , s ∈ R N F × N P N B Φ ^ i ℓ , s ∈ R N F × N P N B \widehat{\Phi}_{i\ell,s} \in\mathbb{R}^{N_F \times N_P N_B} Φ i ℓ , s ∈ R N F × N P N B
i i i
f i ( x i ; x − i ) = 1 M ∑ s = 1 M ∑ ℓ = 1 N R 1 2 ∥ r i ℓ , s − Φ ^ i ℓ , s x i ∥ 2 + η N R 2 ∑ j ∈ N i ρ i j ∥ x i − x j ∥ 2 (6) f_i(x^i;x^{-i}) = \frac{1}{M}\sum_{s=1}^{M}\sum_{\ell=1}^{N_R}\frac{1}{2}\left\|r_{i\ell,s}-\widehat{\Phi}_{i\ell,s}x^i\right\|^2+\frac{\eta N_R}{2}\sum_{j\in\mathcal{N}_i}\rho_{ij}\left\|x^i-x^j\right\|^2 \tag*{(6)} f i ( x i ; x − i ) = M 1 s = 1 ∑ M ℓ = 1 ∑ N R 2 1 r i ℓ , s − Φ i ℓ , s x i 2 + 2 η N R j ∈ N i ∑ ρ ij x i − x j 2 (6) where J i , 1 ( x i ) J_{i,1}(x^i) J i , 1 ( x i ) J i , 2 ( x i ; x − i ) J_{i,2}(x^i;x^{-i}) J i , 2 ( x i ; x − i ) N i \mathcal{N}_i N i i i i ρ i j ≥ 0 \rho_{ij} \ge0 ρ ij ≥ 0 η > 0 \eta> 0 η > 0
We take N S = 10 N_S = 10 N S = 10 N P = 2 N_P = 2 N P = 2 N R = 10 N_R = 10 N R = 10 N B = 4 N_B = 4 N B = 4 N F = 20 N_F = 20 N F = 20 M = 100 M = 100 M = 100 d = N P N B = 8 d = N_PN_B = 8 d = N P N B = 8 α ⋆ ( 1 ) = ( 0.3 , 0.3 , 0.3 , 0 ) \alpha_{\star}^{(1)} = (0.3, 0.3, 0.3, 0) α ⋆ ( 1 ) = ( 0.3 , 0.3 , 0.3 , 0 ) α ⋆ ( 2 ) = ( 0 , 0.3 , 0.3 , 0.3 ) \alpha_{\star}^{(2)} = (0, 0.3, 0.3, 0.3) α ⋆ ( 2 ) = ( 0 , 0.3 , 0.3 , 0.3 ) α ⋆ = ( α ⋆ ( 1 ) , α ⋆ ( 2 ) ) \alpha_{\star} = (\alpha_{\star}^{(1)}, \alpha_{\star}^{(2)}) α ⋆ = ( α ⋆ ( 1 ) , α ⋆ ( 2 ) ) N i \mathcal{N}_i N i ρ i , i − 1 = ρ i , i + 1 = 1 / 2 \rho_{i,i-1} = \rho_{i,i+1} = 1/2 ρ i , i − 1 = ρ i , i + 1 = 1/2 ρ i j = 0 \rho_{ij} = 0 ρ ij = 0 η = 1.0 \eta= 1.0 η = 1.0 k k k k = 4 k = 4 k = 4 ∥ x τ p − x ⋆ ∥ 2 2 ∥ x 0 − x ⋆ ∥ 2 2 \frac{\left\|x_{\tau p}-x_{\star}\right\|_2^2}{\left\|x_0-x_{\star}\right\|_2^2} ∥ x 0 − x ⋆ ∥ 2 2 ∥ x τ p − x ⋆ ∥ 2 2 τ ∈ { 1 , 20 } \tau\in\{1, 20\} τ ∈ { 1 , 20 } { 10 − 3 , 10 − 4 , 10 − 5 , 10 − 6 } \{10^{-3}, 10^{-4}, 10^{-5}, 10^{-6}\} { 1 0 − 3 , 1 0 − 4 , 1 0 − 5 , 1 0 − 6 } 2 × 10 8 2 \times10^8 2 × 1 0 8
We observe in Figure 4 a that PEARL-SVRG with τ = 20 \tau= 20 τ = 20 10 3 10^3 1 0 3 τ = 20 \tau= 20 τ = 20 Figure 4 b shows that PEARL-SVRG still reaches the exact solution with fewer oracle calls in this experiment. Finally, Figure 4 c shows that the compressed variants of PEARL-SGD and PEARL-SVRG reach the solution or its neighborhood using fewer communicated bits, as expected.
Figure 4. Performance plot of PEARL algorithm variants on the distributed spectrum sensing problem (6) using tuned step-sizes. The first two plots illustrate the convergence of PEARL-SVRG to the exact solution, traded off with increased oracle complexity. The rightmost plot compares all variants with τ = 20 \tau= 20 τ = 20
Conclusion
We develop generalized and advanced PEARL methods for MpFL based on an equivalent increment-sharing reformulation of PEARL-SGD, incorporating compressed communication and variance reduction.
We provide a unified convergence analysis for all variants, including the newly developed C-PEARL-SGD, PEARL-SVRG and C-PEARL-SVRG. Numerical experiments support the theory and illustrate the practical benefits of the proposed methods. Our results offer several natural extensions for future work, including different variance-reduced estimators or baseline algorithms using history-dependent update directions such as momentum or anchoring methods.
Acknowledgments
The authors’ contribution to this work was supported by NSF CCF 2504626, NSF CAREER 2542902, and AFOSR YIP FA9550-26-1-B353.
AI use statement
In this work, we used generative AI tools to assist with polishing the paper, including improving clarity and LaTeX formatting. We also used generative AI tools to assist with mathematical derivations and proof checking, as well as the development and debugging of experimental code. We did not use generative AI tools to generate the ideas or concepts of the project, or to generate citations. All AI-assisted mathematical arguments and proofs were checked, and all AI-assisted code was reviewed and tested by the authors. Generative AI was not used to generate experimental data or results. We take responsibility for the final content of this work, including all text, claims, and artifacts produced with the aid of generative AI.
Appendix
We organize the appendix as follows: Section A provides a discussion on related works, Section B provides the proofs of the main convergence results in § 4 , and Section C provides details on the increment-sharing mechanism as well as its comparison with algorithms in distributed minimization discussed in § 2 .
Related Works
Multiplayer Games under Distributed Systems
Multiplayer Federated Learning (MpFL). Multiplayer games have been studied in different distributed settings, including MpFL [45 ] , which is the focus of this paper. A main objective of MpFL is to find an equilibrium in as few communication rounds as possible. To reduce communication, PEARL-SGD [45 ] allows players to perform several local updates between communication rounds. However, excessive local updates may result in player drift , where players’ actions approach minimizers of individual objectives while fixing the outdated strategies of the other players, which causes the convergence to equilibrium to fail. This issue is addressed in PEARL-Prox [46 ] by incorporating proximal updates into each player’s local training loop. A closely related work, Decoupled SGD [47 ] , also uses the idea of performing several local updates while keeping the strategies of the other players fixed, and exhibits the same update rule as PEARL-SGD. However, unlike PEARL-SGD, its analysis focuses on communication efficiency gain for weakly coupled games in the deterministic setting. More recently, [27 ] extended this line of work by developing decoupled methods for distributed saddle-point problems and monotone variational inequalities.
Distributed Nash Equilibrium Seeking. Another related setting is distributed Nash equilibrium seeking [19 , 23 ] , where each player performs computations using its own objective while exchanging partial information of action vectors with other players to find an equilibrium. While MpFL focuses on reducing communication between players under the orchestration of a central server, works within this literature, including [31 , 41 ] , generally study communication over decentralized networks, with greater emphasis on convergence under different network topologies rather than communication complexity.
Overview of Compression Techniques in Federated Learning and Multiplayer Games
Compression in Distributed and Federated Optimization. The technique of compressing the communicated information has been extensively studied in distributed and federated optimization. Common approaches include stochastic quantization [2 , 38 ] and sparsification [25 , 40 ] , along with error-feedback mechanisms [9 , 20 ] to address compression errors. Compression has also been incorporated into federated learning algorithms that perform multiple local updates between communication rounds [15 , 34 ] . These methods reduce communication overhead by transmitting compressed gradients/model updates instead of full vectors. Beyond the choice of compression schemes, another important consideration is the choice of quantities to compress. For example, in distributed minimization, directly compressing local gradients can prevent exact convergence with a constant step-size, even when deterministic gradients are used, since gradients of local objectives need not vanish at the global minimizer. DIANA [29 ] addresses this issue by maintaining auxiliary reference sequences and compressing the differences between local gradients and these references, so that the compression error vanishes as the algorithm converges. We provide a more detailed explanation of this in Section C.
Compression in Nash Equilibrium Seeking. Compression has also been explored in distributed Nash equilibrium seeking. One such method is C-DNES [7 ] , which, like DIANA, maintains an auxiliary reference sequence and compresses the difference between each player’s estimate of the joint strategy vector and this reference. On the other hand, in our increment-sharing reformulation of PEARL-SGD, an additional reference sequence is not needed; see Appendix § 12 for explanation.
Missing proofs from Section 4
Auxiliary Bounds for PEARL-SGD
Here we present Lemmas B.1 and B.2 from [45 ] , which were used in establishing convergence guarantees for PEARL-SGD. Lemma B.1 shows that one communication round of PEARL-SGD behaves like a large single descent step. However, it also introduces local error terms caused by running multiple SGD steps locally, and Lemma B.2 bounds these local terms.
Lemma B.1. [45 Lemma C.1] Assume ( S M ) (SM) ( S M ) L max = max { L 1 , … , L n } L_{\max} = \max\{L_1,\ldots,L_n\} L m a x = max { L 1 , … , L n } 0 ≤ p ≤ R − 1 0 \le p \le R-1 0 ≤ p ≤ R − 1 γ k ≡ γ > 0 \gamma_k \equiv\gamma> 0 γ k ≡ γ > 0 k = τ p , … , τ ( p + 1 ) − 1 k=\tau p,\ldots,\tau(p+1)-1 k = τ p , … , τ ( p + 1 ) − 1 α > 0 \alpha> 0 α > 0
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ( 1 + ( τ − 1 ) α γ ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ L max 2 α ∑ j = τ p + 1 τ p + τ − 1 E p [ ∥ x τ p − x j ∥ 2 ] + E p [ ∥ x τ p − x τ ( p + 1 ) ∥ 2 ] . \mathbb{E}_p\left[\left\|x_{\tau(p+1)}-x_\star\right\|^2\right] \le\left(1+(\tau-1)\alpha\gamma\right)\left\|x_{\tau p}-x_\star\right\|^2 - 2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle+ \frac{\gamma L_{\max}^2}{\alpha}\sum_{j=\tau p+1}^{\tau p+\tau-1}\mathbb{E}_p\left[\left\|x_{\tau p}-x_j\right\|^2\right] + \mathbb{E}_p\left[\left\|x_{\tau p}-x_{\tau(p+1)}\right\|^2\right]. E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ( 1 + ( τ − 1 ) α γ ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + α γ L m a x 2 j = τ p + 1 ∑ τ p + τ − 1 E p [ ∥ x τ p − x j ∥ 2 ] + E p [ x τ p − x τ ( p + 1 ) 2 ] . Lemma B.2. [45 Lemma C.2] Assume ( C V X ) (CVX) ( C V X ) ( S M ) (SM) ( S M ) ( B V ) (BV) ( B V ) i ∈ [ n ] i \in[n] i ∈ [ n ] 0 ≤ p ≤ R − 1 0 \le p \le R-1 0 ≤ p ≤ R − 1 γ k ≡ γ \gamma_k \equiv\gamma γ k ≡ γ k = τ p , … , τ ( p + 1 ) − 1 k=\tau p,\ldots,\tau(p+1)-1 k = τ p , … , τ ( p + 1 ) − 1 0 < γ ≤ 1 L i min { 1 , 1 τ − 1 } 0 < \gamma\le\frac{1}{L_i}\min\left\{1,\frac{1}{\tau-1}\right\} 0 < γ ≤ L i 1 min { 1 , τ − 1 1 } t = 0 , … , τ t=0,\ldots,\tau t = 0 , … , τ
E p [ ∥ x τ p i − x τ p + t i ∥ 2 ] ≤ γ 2 t 2 ∥ ∇ f i ( x τ p i ; x τ p i ) ∥ 2 + γ 2 t ( 1 + 2 ( t − 1 ) ( t + 1 ) γ L i ) σ i 2 . \mathbb{E}_p\left[\left\|x_{\tau p}^i-x_{\tau p+t}^i\right\|^2\right] \le\gamma^2t^2\left\|\nabla f_i(x_{\tau p}^i;x_{\tau p}^i)\right\|^2+\gamma^2t\left(1+2(t-1)(t+1)\gamma L_i\right)\sigma_i^2. E p [ x τ p i − x τ p + t i 2 ] ≤ γ 2 t 2 ∇ f i ( x τ p i ; x τ p i ) 2 + γ 2 t ( 1 + 2 ( t − 1 ) ( t + 1 ) γ L i ) σ i 2 . Note: We use the convention 1 / ( τ − 1 ) = + ∞ 1/(\tau-1)=+\infty 1/ ( τ − 1 ) = + ∞ τ = 1 \tau=1 τ = 1 min { 1 , 1 / ( τ − 1 ) } = 1 \min\{1,1/(\tau-1)\}=1 min { 1 , 1/ ( τ − 1 )} = 1
Lemma B.3 follows from Lemma B.1 and Lemma B.2. We use Lemma B.3 throughout our analysis as it helps us verify (4) from Assumption 4.1 in the analysis of our special cases.
Lemma B.3. Suppose the assumptions of Lemma B.1 and Lemma B.2 hold. Assume ( Q S M ) (QSM) ( QS M ) ( S C O ) (SCO) ( S C O ) 0 ≤ p ≤ R − 1 0 \le p \le R-1 0 ≤ p ≤ R − 1 γ k ≡ γ ≤ 1 ℓ τ + 2 ( τ − 1 ) L max κ \gamma_k \equiv\gamma\le\frac{1}{\ell\tau+2(\tau-1)L_{\max}\sqrt{\kappa}} γ k ≡ γ ≤ ℓ τ + 2 ( τ − 1 ) L m a x κ 1 k = τ p , … , τ ( p + 1 ) − 1 k=\tau p,\ldots,\tau(p+1)-1 k = τ p , … , τ ( p + 1 ) − 1
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( ℓ + 2 ( τ − 1 ) τ L max κ 3 ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 σ 2 τ ( τ − 1 ) ( 4 γ τ L max + L max 2 τ ℓ μ / 3 + 2 γ τ L max 2 ℓ μ / 3 ) + γ 2 σ 2 τ . \begin{aligned}
\mathbb{E}_p\left[\left\|x_{\tau(p+1)}-x_\star\right\|^2\right]
&\le\left\|x_{\tau p}-x_\star\right\|^2-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&\quad+\gamma^2\tau^2\left(\ell+\frac{2(\tau-1)}{\tau}L_{\max}\sqrt{\frac{\kappa}{3}}\right)\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&\quad+\gamma^2\sigma^2\tau(\tau-1)\left(4\gamma\tau L_{\max}+\frac{L_{\max}}{2\tau\sqrt{\ell\mu/3}}+\frac{2\gamma\tau L_{\max}^2}{\sqrt{\ell\mu/3}}\right)+\gamma^2\sigma^2\tau.
\end{aligned} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( ℓ + τ 2 ( τ − 1 ) L m a x 3 κ ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 σ 2 τ ( τ − 1 ) ( 4 γ τ L m a x + 2 τ ℓ μ /3 L m a x + ℓ μ /3 2 γ τ L m a x 2 ) + γ 2 σ 2 τ . where κ = ℓ / μ \kappa=\ell/\mu κ = ℓ / μ σ 2 = ∑ i = 1 n σ i 2 \sigma^2=\sum_{i=1}^n\sigma_i^2 σ 2 = ∑ i = 1 n σ i 2
Proof. For τ ≥ 2 \tau\ge2 τ ≥ 2 γ ≤ 1 ℓ τ + 2 ( τ − 1 ) L max κ ≤ 1 L max min { 1 , 1 τ − 1 } \gamma\le\frac{1}{\ell\tau+2(\tau-1)L_{\max}\sqrt{\kappa}} \le\frac{1}{L_{\max}}\min\left\{1,\frac{1}{\tau-1}\right\} γ ≤ ℓ τ + 2 ( τ − 1 ) L m a x κ 1 ≤ L m a x 1 min { 1 , τ − 1 1 } τ = 1 \tau=1 τ = 1 γ > 0 \gamma> 0 γ > 0 ( B V ) (BV) ( B V )
E [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ∣ F p ] ≤ ( 1 + α γ ( τ − 1 ) ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( γ 2 τ 2 + γ 3 L max 2 τ 2 ( τ − 1 ) 3 α ) ∥ F ( x τ p ) ∥ 2 + γ 2 σ 2 τ ( τ − 1 ) γ L max ( 2 ( τ + 1 ) + L max 2 α + γ L max 2 2 α ( τ + 1 ) 2 ) + γ 2 σ 2 τ ≤ ( Q S M ) , ( S C O ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( α γ ( τ − 1 ) μ + ℓ γ 2 τ 2 + ℓ γ 3 L max 2 τ 2 ( τ − 1 ) 3 α ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 σ 2 τ ( τ − 1 ) γ L max ( 2 ( τ + 1 ) + L max 2 α + γ L max 2 2 α ( τ + 1 ) 2 ) + γ 2 σ 2 τ . \begin{aligned}
\mathbb{E}\left[\left\|x_{\tau(p+1)}-x_{\star}\right\|^{2}\mid\mathcal{F}_{p}\right]
&\leq\left(1+\alpha\gamma(\tau-1)\right)\left\|x_{\tau p}-x_{\star}\right\|^{2}
-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_{\star}\right\rangle\\
&\quad+\left(\gamma^{2}\tau^{2}+\frac{\gamma^{3}L_{\max}^{2}\tau^{2}(\tau-1)}{3\alpha}\right)\left\|F(x_{\tau p})\right\|^{2}\\
&\quad+\gamma^{2}\sigma^{2}\tau(\tau-1)\gamma L_{\max}
\left(2(\tau+1)+\frac{L_{\max}}{2\alpha}+\frac{\gamma L_{\max}^{2}}{2\alpha}(\tau+1)^{2}\right)\\
&\quad+\gamma^{2}\sigma^{2}\tau\\
&\underset{(QSM),(SCO)}{\leq}
\left\|x_{\tau p}-x_{\star}\right\|^{2}
-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_{\star}\right\rangle\\
&\quad+\left(\frac{\alpha\gamma(\tau-1)}{\mu}+\ell\gamma^{2}\tau^{2}
+\frac{\ell\gamma^{3}L_{\max}^{2}\tau^{2}(\tau-1)}{3\alpha}\right)
\left\langle F(x_{\tau p}),x_{\tau p}-x_{\star}\right\rangle\\
&\quad+\gamma^{2}\sigma^{2}\tau(\tau-1)\gamma L_{\max}
\left(2(\tau+1)+\frac{L_{\max}}{2\alpha}+\frac{\gamma L_{\max}^{2}}{2\alpha}(\tau+1)^{2}\right)\\
&\quad+\gamma^{2}\sigma^{2}\tau.
\end{aligned} E [ x τ ( p + 1 ) − x ⋆ 2 ∣ F p ] ≤ ( 1 + α γ ( τ − 1 ) ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( γ 2 τ 2 + 3 α γ 3 L m a x 2 τ 2 ( τ − 1 ) ) ∥ F ( x τ p ) ∥ 2 + γ 2 σ 2 τ ( τ − 1 ) γ L m a x ( 2 ( τ + 1 ) + 2 α L m a x + 2 α γ L m a x 2 ( τ + 1 ) 2 ) + γ 2 σ 2 τ ( QS M ) , ( S C O ) ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( μ α γ ( τ − 1 ) + ℓ γ 2 τ 2 + 3 α ℓ γ 3 L m a x 2 τ 2 ( τ − 1 ) ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 σ 2 τ ( τ − 1 ) γ L m a x ( 2 ( τ + 1 ) + 2 α L m a x + 2 α γ L m a x 2 ( τ + 1 ) 2 ) + γ 2 σ 2 τ . Now substituting α = γ τ L max ℓ μ 3 \alpha=\gamma\tau L_{\max}\sqrt{\frac{\ell\mu}{3}} α = γ τ L m a x 3 ℓ μ
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( ℓ + 2 ( τ − 1 ) τ L max κ 3 ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 σ 2 τ ( τ − 1 ) ( 2 γ L max ( τ + 1 ) + L max 2 τ ℓ μ / 3 + γ L max 2 ( τ + 1 ) 2 2 τ ℓ μ / 3 ) + γ 2 σ 2 τ ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( ℓ + 2 ( τ − 1 ) τ L max κ 3 ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 σ 2 τ ( τ − 1 ) ( 4 γ τ L max + L max 2 τ ℓ μ / 3 + 2 γ τ L max 2 ℓ μ / 3 ) + γ 2 σ 2 τ , \begin{aligned}
\mathbb{E}_{p}\left[\left\|x_{\tau(p+1)}-x_{\star}\right\|^{2}\right]
&\leq\left\|x_{\tau p}-x_{\star}\right\|^{2}
-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_{\star}\right\rangle\\
&\quad+\gamma^{2}\tau^{2}\left(\ell+\frac{2(\tau-1)}{\tau}L_{\max}\sqrt{\frac{\kappa}{3}}\right)
\left\langle F(x_{\tau p}),x_{\tau p}-x_{\star}\right\rangle\\
&\quad+\gamma^{2}\sigma^{2}\tau(\tau-1)\left(2\gamma L_{\max}(\tau+1)
+\frac{L_{\max}}{2\tau\sqrt{\ell\mu/3}}
+\frac{\gamma L_{\max}^{2}(\tau+1)^{2}}{2\tau\sqrt{\ell\mu/3}}\right)\\
&\quad+\gamma^{2}\sigma^{2}\tau\\
&\leq\left\|x_{\tau p}-x_{\star}\right\|^{2}
-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_{\star}\right\rangle\\
&\quad+\gamma^{2}\tau^{2}\left(\ell+\frac{2(\tau-1)}{\tau}L_{\max}\sqrt{\frac{\kappa}{3}}\right)
\left\langle F(x_{\tau p}),x_{\tau p}-x_{\star}\right\rangle\\
&\quad+\gamma^{2}\sigma^{2}\tau(\tau-1)\left(4\gamma\tau L_{\max}
+\frac{L_{\max}}{2\tau\sqrt{\ell\mu/3}}
+\frac{2\gamma\tau L_{\max}^{2}}{\sqrt{\ell\mu/3}}\right)\\
&\quad+\gamma^{2}\sigma^{2}\tau,
\end{aligned} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( ℓ + τ 2 ( τ − 1 ) L m a x 3 κ ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 σ 2 τ ( τ − 1 ) ( 2 γ L m a x ( τ + 1 ) + 2 τ ℓ μ /3 L m a x + 2 τ ℓ μ /3 γ L m a x 2 ( τ + 1 ) 2 ) + γ 2 σ 2 τ ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( ℓ + τ 2 ( τ − 1 ) L m a x 3 κ ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 σ 2 τ ( τ − 1 ) ( 4 γ τ L m a x + 2 τ ℓ μ /3 L m a x + ℓ μ /3 2 γ τ L m a x 2 ) + γ 2 σ 2 τ , where for the last inequality, we use τ + 1 ≤ 2 τ \tau+1\leq2\tau τ + 1 ≤ 2 τ
Proof of Lemma 4.2
Before giving the proof, we restate the lemma.
Lemma B.4. Assume (CVX), (SM), (QSM), and (SCO) hold. Let κ = ℓ / μ \kappa=\ell/\mu κ = ℓ / μ σ 2 = ∑ i = 1 n σ i 2 \sigma^{2}=\sum_{i=1}^{n}\sigma_{i}^{2} σ 2 = ∑ i = 1 n σ i 2
A τ G D : = ℓ + 2 ( τ − 1 ) τ L max κ 3 , A_{\tau}^{\mathrm{GD}} := \ell+ \frac{2(\tau-1)}{\tau}L_{\max}\sqrt{\frac{\kappa}{3}}, A τ GD := ℓ + τ 2 ( τ − 1 ) L m a x 3 κ , B τ G D : = σ 2 τ [ 1 + ( τ − 1 ) L max ( 4 γ τ + 1 + 4 γ τ 2 2 τ ℓ μ / 3 ) ] , B_{\tau}^{\mathrm{GD}} := \frac{\sigma^2}{\tau}\left[1+(\tau-1)L_{\max}\left(4\gamma\tau+\frac{1+4\gamma\tau^2}{2\tau\sqrt{\ell\mu/3}}\right)\right], B τ GD := τ σ 2 [ 1 + ( τ − 1 ) L m a x ( 4 γ τ + 2 τ ℓ μ /3 1 + 4 γ τ 2 ) ] , U τ : = σ 2 τ ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L max ) , U_{\tau} := \frac{\sigma^2}{\tau}\left(1+2(\tau-1)(\tau+1)\gamma L_{\max}\right), U τ := τ σ 2 ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L m a x ) , A τ V R : = 4 ℓ + 4 ( τ − 1 ) τ L max κ 3 . A_{\tau}^{\mathrm{VR}} := 4\ell+\frac{4(\tau-1)}{\tau}L_{\max}\sqrt{\frac{\kappa}{3}}. A τ VR := 4 ℓ + τ 4 ( τ − 1 ) L m a x 3 κ . Then the following instances of Algorithm 1 satisfy Assumption 4.1.
A τ = A τ G D and B τ = B τ G D . A_{\tau}=A_{\tau}^{\mathrm{GD}}\quad\text{and}\quad B_{\tau}=B_{\tau}^{\mathrm{GD}}. A τ = A τ GD and B τ = B τ GD . A τ = A τ V R and B τ = 0. A_{\tau}=A_{\tau}^{\mathrm{VR}}\quad\text{and}\quad B_{\tau}=0. A τ = A τ VR and B τ = 0. A τ = A τ G D + ω ℓ and B τ = B τ G D + ω U τ . A_{\tau}=A_{\tau}^{\mathrm{GD}}+\omega\ell\quad\text{and}\quad B_{\tau}=B_{\tau}^{\mathrm{GD}}+\omega U_{\tau}. A τ = A τ GD + ω ℓ and B τ = B τ GD + ω U τ . A τ = A τ V R + 4 ω ℓ and B τ = 0. A_{\tau}=A_{\tau}^{\mathrm{VR}}+4\omega\ell\quad\text{and}\quad B_{\tau}=0. A τ = A τ VR + 4 ω ℓ and B τ = 0. PEARL-SGD
Proof. PEARL-SGD is obtained by choosing Q i = I d d i \mathcal{Q}^{i}=\mathrm{Id}_{d_i} Q i = Id d i g k i = ∇ f i , ξ k i ( x ~ k i ; x τ p i ) g_k^i=\nabla f_{i,\xi_k^i}(\widetilde{x}_k^i;x_{\tau p}^i) g k i = ∇ f i , ξ k i ( x k i ; x τ p i ) i ∈ [ n ] i\in[n] i ∈ [ n ] q p i = u τ ( p + 1 ) i = x τ p i − x ~ τ p i q_p^i=u_{\tau(p+1)}^i=x_{\tau p}^i-\widetilde{x}_{\tau p}^i q p i = u τ ( p + 1 ) i = x τ p i − x τ p i x ~ τ p i = x τ p i \widetilde{x}_{\tau p}^i=x_{\tau p}^i x τ p i = x τ p i
x τ ( p + 1 ) i = x τ p i + q p i = x τ p i + x ~ τ ( p + 1 ) i − x ~ τ p i = x ~ τ ( p + 1 ) i . x_{\tau(p+1)}^i=x_{\tau p}^i+q_p^i=x_{\tau p}^i+\widetilde{x}_{\tau(p+1)}^i-\widetilde{x}_{\tau p}^i=\widetilde{x}_{\tau(p+1)}^i. x τ ( p + 1 ) i = x τ p i + q p i = x τ p i + x τ ( p + 1 ) i − x τ p i = x τ ( p + 1 ) i . Therefore, the synchronized iterates coincide with the PEARL-SGD iterates. From Lemma B.3, we have an inequality of the form
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ ) . (7) \mathbb{E}_p\left[\left\|x_{\tau(p+1)}-x_{\star}\right\|^2\right]\le\left\|x_{\tau p}-x_{\star}\right\|^2-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_{\star}\right\rangle+\gamma^2\tau^2\left(A_{\tau}\left\langle F(x_{\tau p}),x_{\tau p}-x_{\star}\right\rangle+B_{\tau}\right). \tag*{(7)} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ ) . (7) Therefore Assumption 4.1 holds with A τ = A τ G D A_{\tau}=A_{\tau}^{\mathrm{GD}} A τ = A τ GD B τ = B τ G D B_{\tau}=B_{\tau}^{\mathrm{GD}} B τ = B τ GD
PEARL-SVRG
To verify that PEARL-SVRG satisfies Assumption 4.1, we first present two lemmas that are required in our proof. For a fixed communication round p p p
g k i = ∇ f i , ξ k i ( x ~ k i ; x τ p − i ) − ∇ f i , ξ k i ( x τ p i ; x τ p − i ) + ∇ f i ( x τ p i ; x τ p − i ) , g_k^i = \nabla f_{i,\xi_k^i}(\widetilde{x}_k^i; x_{\tau p}^{-i}) - \nabla f_{i,\xi_k^i}(x_{\tau p}^i; x_{\tau p}^{-i}) + \nabla f_i(x_{\tau p}^i; x_{\tau p}^{-i}), g k i = ∇ f i , ξ k i ( x k i ; x τ p − i ) − ∇ f i , ξ k i ( x τ p i ; x τ p − i ) + ∇ f i ( x τ p i ; x τ p − i ) , where ξ k i \xi_k^i ξ k i g k i g_k^i g k i x ~ k i \widetilde{x}_k^i x k i F p \mathcal{F}_p F p
Note that for a fixed communication round p p p x ~ k i \widetilde{x}_k^i x k i i i i τ \tau τ x ~ τ p i = x τ p i \widetilde{x}_{\tau p}^i=x_{\tau p}^i x τ p i = x τ p i k = τ p , … , τ ( p + 1 ) − 1 k=\tau p,\ldots,\tau(p+1)-1 k = τ p , … , τ ( p + 1 ) − 1
x ~ k + 1 i = x ~ k i − γ g k i . \widetilde{x}_{k+1}^i=\widetilde{x}_k^i-\gamma g_k^i. x k + 1 i = x k i − γ g k i . We use this notation only for the local strategy of player i i i x τ p \mathbf{x}_{\tau p} x τ p
Lemma B.5. Under Assumption 3.1, for every communication round p p p i ∈ [ n ] i\in[n] i ∈ [ n ] k = τ p , … , τ ( p + 1 ) − 1 k=\tau p,\ldots,\tau(p+1)-1 k = τ p , … , τ ( p + 1 ) − 1
E [ g k i ∣ x ~ k i , F p ] = ∇ f i ( x ~ k i ; x τ p − i ) , (8) \mathbb{E}\left[g_k^i\mid\widetilde{x}_k^i,\mathcal{F}_p\right]=\nabla f_i(\widetilde{x}_k^i;x_{\tau p}^{-i}), \tag*{(8)} E [ g k i ∣ x k i , F p ] = ∇ f i ( x k i ; x τ p − i ) , (8) and
E [ ∥ g k i ∥ 2 ∣ x ~ k i , F p ] ≤ 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 + 2 L i 2 ∥ x ~ k i − x τ p i ∥ 2 . (9) \mathbb{E}\left[\left\|g_k^i\right\|^2\mid\widetilde{x}_k^i,\mathcal{F}_p\right]\leq2\left\|\nabla f_i(x_{\tau p}^i;x_{\tau p}^{-i})\right\|^2+2L_i^2\left\|\widetilde{x}_k^i-x_{\tau p}^i\right\|^2. \tag*{(9)} E [ g k i 2 ∣ x k i , F p ] ≤ 2 ∇ f i ( x τ p i ; x τ p − i ) 2 + 2 L i 2 x k i − x τ p i 2 . (9) Proof. The unbiasedness in (8) follows from E [ ∇ f i , ξ k i ( x ~ k i ; x τ p − i ) ∣ x ~ k i , F p ] = ∇ f i ( x ~ k i ; x τ p − i ) \mathbb{E}\left[\nabla f_{i,\xi_k^i}(\widetilde{x}_k^i;x_{\tau p}^{-i})\mid\widetilde{x}_k^i,\mathcal{F}_p\right]=\nabla f_i(\widetilde{x}_k^i;x_{\tau p}^{-i}) E [ ∇ f i , ξ k i ( x k i ; x τ p − i ) ∣ x k i , F p ] = ∇ f i ( x k i ; x τ p − i ) E [ ∇ f i , ξ k i ( x τ p i ; x τ p − i ) ∣ x ~ k i , F p ] = ∇ f i ( x τ p i ; x τ p − i ) \mathbb{E}\left[\nabla f_{i,\xi_k^i}(x_{\tau p}^i;x_{\tau p}^{-i})\mid\widetilde{x}_k^i,\mathcal{F}_p\right]=\nabla f_i(x_{\tau p}^i;x_{\tau p}^{-i}) E [ ∇ f i , ξ k i ( x τ p i ; x τ p − i ) ∣ x k i , F p ] = ∇ f i ( x τ p i ; x τ p − i )
E [ ∥ g k i ∥ 2 ∣ x ~ k i , F p ] ≤ 2 E [ ∥ ∇ f i , ξ k i ( x ~ k i ; x τ p − i ) − ∇ f i , ξ k i ( x τ p i ; x τ p − i ) ∥ 2 ∣ x ~ k i , F p ] + 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 \mathbb{E}\left[\left\|g_k^i\right\|^2\mid\widetilde{x}_k^i,\mathcal{F}_p\right]\leq2\mathbb{E}\left[\left\|\nabla f_{i,\xi_k^i}(\widetilde{x}_k^i;x_{\tau p}^{-i})-\nabla f_{i,\xi_k^i}(x_{\tau p}^i;x_{\tau p}^{-i})\right\|^2\mid\widetilde{x}_k^i,\mathcal{F}_p\right]+2\left\|\nabla f_i(x_{\tau p}^i;x_{\tau p}^{-i})\right\|^2 E [ g k i 2 ∣ x k i , F p ] ≤ 2 E [ ∇ f i , ξ k i ( x k i ; x τ p − i ) − ∇ f i , ξ k i ( x τ p i ; x τ p − i ) 2 ∣ x k i , F p ] + 2 ∇ f i ( x τ p i ; x τ p − i ) 2 ≤ 2 L i 2 ∥ x ~ k i − x τ p i ∥ 2 + 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 . \leq2L_i^2\left\|\widetilde{x}_k^i-x_{\tau p}^i\right\|^2+2\left\|\nabla f_i(x_{\tau p}^i;x_{\tau p}^{-i})\right\|^2. ≤ 2 L i 2 x k i − x τ p i 2 + 2 ∇ f i ( x τ p i ; x τ p − i ) 2 . where the last inequality uses Assumption 3.1. □ \square □
Lemma B.6. Under Assumption 3.1, suppose 0 < γ ≤ 1 2 L i τ 0<\gamma\leq\frac{1}{2L_i\tau} 0 < γ ≤ 2 L i τ 1 p p p i i i t = 0 , … , τ t=0,\ldots,\tau t = 0 , … , τ
E p [ ∥ x ~ τ p + t i − x τ p i ∥ 2 ] ≤ 4 γ 2 τ 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 . \mathbb{E}_p\left[\left\|\widetilde{x}_{\tau p+t}^i-x_{\tau p}^i\right\|^2\right]\leq4\gamma^2\tau^2\left\|\nabla f_i(x_{\tau p}^i;x_{\tau p}^{-i})\right\|^2. E p [ x τ p + t i − x τ p i 2 ] ≤ 4 γ 2 τ 2 ∇ f i ( x τ p i ; x τ p − i ) 2 . Proof. Fix a communication round p p p i i i x ~ τ p + t i − x τ p i = − γ ∑ s = 0 t − 1 g τ p + s i \widetilde{x}_{\tau p+t}^i-x_{\tau p}^i=-\gamma\sum_{s=0}^{t-1}g_{\tau p+s}^i x τ p + t i − x τ p i = − γ ∑ s = 0 t − 1 g τ p + s i
E p [ ∥ x ~ τ p + t i − x τ p i ∥ 2 ] = γ 2 E [ ∥ ∑ s = 0 t − 1 g τ p + s i ∥ 2 | F p ] ≤ γ 2 t ∑ s = 0 t − 1 E [ ∥ g τ p + s i ∥ 2 | F p ] . (10) \mathbb{E}_p\left[\left\|\widetilde{x}_{\tau p+t}^i-x_{\tau p}^i\right\|^2\right]=\gamma^2\mathbb{E}\left[\left\|\sum_{s=0}^{t-1}g_{\tau p+s}^i\right\|^2\middle|\mathcal{F}_p\right]\leq\gamma^2t\sum_{s=0}^{t-1}\mathbb{E}\left[\left\|g_{\tau p+s}^i\right\|^2\middle|\mathcal{F}_p\right]. \tag*{(10)} E p [ x τ p + t i − x τ p i 2 ] = γ 2 E s = 0 ∑ t − 1 g τ p + s i 2 F p ≤ γ 2 t s = 0 ∑ t − 1 E [ g τ p + s i 2 F p ] . (10) By Lemma B.5 and the tower property,
E [ ∥ g ~ τ p + s ∥ 2 ∣ F p ] ≤ 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 + 2 L i 2 E [ ∥ x ~ τ p + s − x τ p i ∥ 2 ∣ F p ] . \mathbb{E}\left[\left\|\widetilde{g}_{\tau p+s}\right\|^2 \mid\mathcal{F}_p\right] \le2\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^{-i}\right)\right\|^2 + 2L_i^2\mathbb{E}\left[\left\|\widetilde{x}_{\tau p+s}-x_{\tau p}^i\right\|^2 \mid\mathcal{F}_p\right]. E [ ∥ g τ p + s ∥ 2 ∣ F p ] ≤ 2 ∇ f i ( x τ p i ; x τ p − i ) 2 + 2 L i 2 E [ x τ p + s − x τ p i 2 ∣ F p ] . Substituting this into (10) we obtain
E p [ ∥ x ~ τ p + t − x τ p i ∥ 2 ] ≤ 2 γ 2 t 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 + 2 γ 2 L i 2 t ∑ s = 0 t − 1 E [ ∥ x ~ τ p + s − x τ p i ∥ 2 ∣ F p ] . (11) \mathbb{E}_p\left[\left\|\widetilde{x}_{\tau p+t}-x_{\tau p}^i\right\|^2\right] \le2\gamma^2t^2\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^{-i}\right)\right\|^2+2\gamma^2L_i^2t\sum_{s=0}^{t-1}\mathbb{E}\left[\left\|\widetilde{x}_{\tau p+s}-x_{\tau p}^i\right\|^2\mid\mathcal{F}_p\right]. \tag*{(11)} E p [ x τ p + t − x τ p i 2 ] ≤ 2 γ 2 t 2 ∇ f i ( x τ p i ; x τ p − i ) 2 + 2 γ 2 L i 2 t s = 0 ∑ t − 1 E [ x τ p + s − x τ p i 2 ∣ F p ] . (11) We now prove the claim by induction on t t t t = 0 t=0 t = 0 x ~ τ p i = x τ p i \widetilde{x}_{\tau p}^i=x_{\tau p}^i x τ p i = x τ p i s = 0 , … , t − 1 s=0,\ldots,t-1 s = 0 , … , t − 1
E p [ ∥ x ~ τ p + s i − x τ p i ∥ 2 ] ≤ 4 γ 2 s 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 . \mathbb{E}_p\left[\left\|\widetilde{x}_{\tau p+s}^i-x_{\tau p}^i\right\|^2\right]\le4\gamma^2s^2\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^{-i}\right)\right\|^2. E p [ x τ p + s i − x τ p i 2 ] ≤ 4 γ 2 s 2 ∇ f i ( x τ p i ; x τ p − i ) 2 . Then (11) gives
E p [ ∥ x ~ τ p + t i − x τ p i ∥ 2 ] ≤ 2 γ 2 t 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 + 8 γ 4 L i 2 t ∑ s = 0 t − 1 s 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 \mathbb{E}_p\left[\left\|\widetilde{x}_{\tau p+t}^i-x_{\tau p}^i\right\|^2\right]\le2\gamma^2t^2\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^{-i}\right)\right\|^2+8\gamma^4L_i^2t\sum_{s=0}^{t-1}s^2\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^{-i}\right)\right\|^2 E p [ x τ p + t i − x τ p i 2 ] ≤ 2 γ 2 t 2 ∇ f i ( x τ p i ; x τ p − i ) 2 + 8 γ 4 L i 2 t s = 0 ∑ t − 1 s 2 ∇ f i ( x τ p i ; x τ p − i ) 2 ≤ 2 γ 2 t 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 + 8 3 γ 4 L i 2 t 4 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 , \le2\gamma^2t^2\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^{-i}\right)\right\|^2+\frac{8}{3}\gamma^4L_i^2t^4\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^{-i}\right)\right\|^2, ≤ 2 γ 2 t 2 ∇ f i ( x τ p i ; x τ p − i ) 2 + 3 8 γ 4 L i 2 t 4 ∇ f i ( x τ p i ; x τ p − i ) 2 , where we used ∑ s = 0 t − 1 s 2 ≤ t 3 / 3 \sum_{s=0}^{t-1}s^2\le t^3/3 ∑ s = 0 t − 1 s 2 ≤ t 3 /3 t ≤ τ t\le\tau t ≤ τ γ ≤ 1 / ( 2 L i τ ) \gamma\le1/(2L_i\tau) γ ≤ 1/ ( 2 L i τ ) γ 2 L i 2 t 2 ≤ γ 2 L i 2 τ 2 ≤ 1 4 \gamma^2L_i^2t^2\le\gamma^2L_i^2\tau^2\le\frac{1}{4} γ 2 L i 2 t 2 ≤ γ 2 L i 2 τ 2 ≤ 4 1 8 3 γ 4 L i 2 t 4 ≤ 2 3 γ 2 t 2 \frac{8}{3}\gamma^4L_i^2t^4\le\frac{2}{3}\gamma^2t^2 3 8 γ 4 L i 2 t 4 ≤ 3 2 γ 2 t 2
E p [ ∥ x ~ τ p + t i − x τ p i ∥ 2 ] ≤ ( 2 + 2 3 ) γ 2 t 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 \mathbb{E}_p\left[\left\|\widetilde{x}_{\tau p+t}^i-x_{\tau p}^i\right\|^2\right]\le\left(2+\frac{2}{3}\right)\gamma^2t^2\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^{-i}\right)\right\|^2 E p [ x τ p + t i − x τ p i 2 ] ≤ ( 2 + 3 2 ) γ 2 t 2 ∇ f i ( x τ p i ; x τ p − i ) 2 ≤ 4 γ 2 t 2 ∥ ∇ f i ( x τ p i ; x τ p − i ) ∥ 2 . \le4\gamma^2t^2\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^{-i}\right)\right\|^2. ≤ 4 γ 2 t 2 ∇ f i ( x τ p i ; x τ p − i ) 2 . This closes the induction and proves the claim.
We now verify that PEARL-SVRG satisfies Assumption 4.1 .
Proof. For PEARL-SVRG, since g k i g_k^i g k i ∇ f i ( x ~ k i ; x τ p − i ) \nabla f_i(\widetilde{x}_k^i;x_{\tau p}^{-i}) ∇ f i ( x k i ; x τ p − i ) Lemma B.1 directly applies. Hence, for any α > 0 \alpha>0 α > 0
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ( 1 + ( τ − 1 ) α γ ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ L max 2 α ∑ j = τ p + 1 τ ( p + 1 ) − 1 E p [ ∥ x τ p − x ~ j ∥ 2 ] + E p [ ∥ x τ p − x ~ τ ( p + 1 ) ∥ 2 ] . (12) \begin{aligned}
\mathbb{E}_p\left[\left\|x_{\tau(p+1)}-x_\star\right\|^2\right]\le\left(1+(\tau-1)\alpha\gamma\right)\left\|x_{\tau p}-x_\star\right\|^2-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&+\frac{\gamma L_{\max}^2}{\alpha}\sum_{j=\tau p+1}^{\tau(p+1)-1}\mathbb{E}_p\left[\left\|x_{\tau p}-\widetilde{x}_j\right\|^2\right]+\mathbb{E}_p\left[\left\|x_{\tau p}-\widetilde{x}_{\tau(p+1)}\right\|^2\right]. \tag*{(12)}
\end{aligned} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ( 1 + ( τ − 1 ) α γ ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + α γ L m a x 2 j = τ p + 1 ∑ τ ( p + 1 ) − 1 E p [ ∥ x τ p − x j ∥ 2 ] + E p [ x τ p − x τ ( p + 1 ) 2 ] . (12) Here x ~ j = ( x ~ j 1 , … , x ~ j n ) \widetilde{x}_j=(\widetilde{x}_j^1,\ldots,\widetilde{x}_j^n) x j = ( x j 1 , … , x j n ) t = 1 , … , τ t=1,\ldots,\tau t = 1 , … , τ
E p [ ∥ x τ p − x ~ τ p + t ∥ 2 ] = ∑ i = 1 n E p [ ∥ x ~ τ p + t i − x τ p i ∥ 2 ] \mathbb{E}_p\left[\left\|x_{\tau p}-\widetilde{x}_{\tau p+t}\right\|^2\right]=\sum_{i=1}^n\mathbb{E}_p\left[\left\|\widetilde{x}_{\tau p+t}^i-x_{\tau p}^i\right\|^2\right] E p [ ∥ x τ p − x τ p + t ∥ 2 ] = i = 1 ∑ n E p [ x τ p + t i − x τ p i 2 ] ≤ 4 γ 2 t 2 ∥ F ( x τ p ) ∥ 2 . \le4\gamma^2t^2\left\|F(x_{\tau p})\right\|^2. ≤ 4 γ 2 t 2 ∥ F ( x τ p ) ∥ 2 . Substituting this into (12) and using the elementary fact ∑ t = 1 τ − 1 t 2 = ( τ − 1 ) τ ( 2 τ − 1 ) 6 ≤ ( τ − 1 ) τ 2 3 \sum_{t=1}^{\tau-1}t^2=\frac{(\tau-1)\tau(2\tau-1)}{6}\le\frac{(\tau-1)\tau^2}{3} ∑ t = 1 τ − 1 t 2 = 6 ( τ − 1 ) τ ( 2 τ − 1 ) ≤ 3 ( τ − 1 ) τ 2
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ( 1 + ( τ − 1 ) α γ ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( 4 γ 2 τ 2 + 4 γ 3 L max 2 τ 2 ( τ − 1 ) 3 α ) ∥ F ( x τ p ) ∥ 2 = ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( τ − 1 ) α γ ∥ x τ p − x ⋆ ∥ 2 + ( 4 γ 2 τ 2 + 4 γ 3 L max 2 τ 2 ( τ − 1 ) 3 α ) ∥ F ( x τ p ) ∥ 2 ≤ ( Q S M ) , ( S C O ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( τ − 1 ) α γ μ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ℓ ( 4 γ 2 τ 2 + 4 γ 3 L max 2 τ 2 ( τ − 1 ) 3 α ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ = ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( ( τ − 1 ) α γ μ + 4 ℓ γ 2 τ 2 + 4 ℓ γ 3 L max 2 τ 2 ( τ − 1 ) 3 α ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 A τ ( α ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ , \begin{aligned}
\mathbb{E}_p\left[\left\|x_{\tau(p+1)}-x_\star\right\|^2\right]
&\le\left(1+(\tau-1)\alpha\gamma\right)\left\|x_{\tau p}-x_\star\right\|^2-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&\quad+\left(4\gamma^2\tau^2+\frac{4\gamma^3L_{\max}^2\tau^2(\tau-1)}{3\alpha}\right)\left\|F(x_{\tau p})\right\|^2\\
&=\left\|x_{\tau p}-x_\star\right\|^2-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&\quad+(\tau-1)\alpha\gamma\left\|x_{\tau p}-x_\star\right\|^2\\
&\quad+\left(4\gamma^2\tau^2+\frac{4\gamma^3L_{\max}^2\tau^2(\tau-1)}{3\alpha}\right)\left\|F(x_{\tau p})\right\|^2\\
&\underset{(QSM),(SCO)}{\le}\left\|x_{\tau p}-x_\star\right\|^2-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&\quad+\frac{(\tau-1)\alpha\gamma}{\mu}\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&\quad+\ell\left(4\gamma^2\tau^2+\frac{4\gamma^3L_{\max}^2\tau^2(\tau-1)}{3\alpha}\right)\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&=\left\|x_{\tau p}-x_\star\right\|^2-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&\quad+\left(\frac{(\tau-1)\alpha\gamma}{\mu}+4\ell\gamma^2\tau^2+\frac{4\ell\gamma^3L_{\max}^2\tau^2(\tau-1)}{3\alpha}\right)\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&\le\left\|x_{\tau p}-x_\star\right\|^2-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle\\
&\quad+\gamma^2\tau^2A_\tau(\alpha)\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle,
\end{aligned} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ( 1 + ( τ − 1 ) α γ ) ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( 4 γ 2 τ 2 + 3 α 4 γ 3 L m a x 2 τ 2 ( τ − 1 ) ) ∥ F ( x τ p ) ∥ 2 = ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( τ − 1 ) α γ ∥ x τ p − x ⋆ ∥ 2 + ( 4 γ 2 τ 2 + 3 α 4 γ 3 L m a x 2 τ 2 ( τ − 1 ) ) ∥ F ( x τ p ) ∥ 2 ( QS M ) , ( S C O ) ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + μ ( τ − 1 ) α γ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ℓ ( 4 γ 2 τ 2 + 3 α 4 γ 3 L m a x 2 τ 2 ( τ − 1 ) ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ = ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + ( μ ( τ − 1 ) α γ + 4 ℓ γ 2 τ 2 + 3 α 4 ℓ γ 3 L m a x 2 τ 2 ( τ − 1 ) ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 A τ ( α ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ , where A τ ( α ) : = ( τ − 1 ) α μ γ τ 2 + 4 ℓ + 4 ℓ γ L max 2 ( τ − 1 ) 3 α A_\tau(\alpha):=\frac{(\tau-1)\alpha}{\mu\gamma\tau^2}+4\ell+\frac{4\ell\gamma L_{\max}^2(\tau-1)}{3\alpha} A τ ( α ) := μ γ τ 2 ( τ − 1 ) α + 4 ℓ + 3 α 4 ℓ γ L m a x 2 ( τ − 1 ) α = 2 γ τ L max ℓ μ 3 \alpha=2\gamma\tau L_{\max}\sqrt{\frac{\ell\mu}{3}} α = 2 γ τ L m a x 3 ℓ μ A τ ( α ) A_\tau(\alpha) A τ ( α ) α \alpha α
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 A τ V R ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ . (13) \mathbb{E}_p\left[\left\|x_{\tau(p+1)}-x_\star\right\|^2\right]\le\left\|x_{\tau p}-x_\star\right\|^2-2\gamma\tau\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle+\gamma^2\tau^2A_\tau^{\mathrm{VR}}\left\langle F(x_{\tau p}),x_{\tau p}-x_\star\right\rangle. \tag*{(13)} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 A τ VR ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ . (13) where
A τ ( α ) = 4 ℓ + 4 ( τ − 1 ) τ L max κ 3 = : A τ V R . A_\tau(\alpha)=4\ell+\frac{4(\tau-1)}{\tau}L_{\max}\sqrt{\frac{\kappa}{3}}=:A_\tau^{\mathrm{VR}}. A τ ( α ) = 4 ℓ + τ 4 ( τ − 1 ) L m a x 3 κ =: A τ VR . Thus Assumption 4.1 holds with A τ = A τ V R A_\tau=A_\tau^{\mathrm{VR}} A τ = A τ VR B τ = 0 B_\tau=0 B τ = 0
C-PEARL-SGD
Proof. For each player i ∈ [ n ] i\in[n] i ∈ [ n ] x ~ τ ( p + 1 ) i \widetilde{x}_{\tau(p+1)}^i x τ ( p + 1 ) i i i i τ \tau τ p p p u p i = x ~ τ ( p + 1 ) i − x ~ τ p i = x ~ τ ( p + 1 ) i − x τ p i u_p^i=\widetilde{x}_{\tau(p+1)}^i-\widetilde{x}_{\tau p}^i=\widetilde{x}_{\tau(p+1)}^i-x_{\tau p}^i u p i = x τ ( p + 1 ) i − x τ p i = x τ ( p + 1 ) i − x τ p i q p i = Q i ( u p i ) q_p^i=Q^i(u_p^i) q p i = Q i ( u p i ) q p = ( q p 1 , … , q p n ) q_p=(q_p^1,\ldots,q_p^n) q p = ( q p 1 , … , q p n ) x τ ( p + 1 ) = x τ p + q p x_{\tau(p+1)}=x_{\tau p}+q_p x τ ( p + 1 ) = x τ p + q p
Let x ~ τ ( p + 1 ) = ( x ~ τ ( p + 1 ) 1 , … , x ~ τ ( p + 1 ) n ) \widetilde{x}_{\tau(p+1)}=(\widetilde{x}_{\tau(p+1)}^1,\ldots,\widetilde{x}_{\tau(p+1)}^n) x τ ( p + 1 ) = ( x τ ( p + 1 ) 1 , … , x τ ( p + 1 ) n ) x ~ τ ( p + 1 ) = x τ p + u p \widetilde{x}_{\tau(p+1)}=x_{\tau p}+u_p x τ ( p + 1 ) = x τ p + u p x τ ( p + 1 ) − x ⋆ = x ~ τ ( p + 1 ) − x ⋆ + q p − u p x_{\tau(p+1)}-x_\star=\widetilde{x}_{\tau(p+1)}-x_\star+q_p-u_p x τ ( p + 1 ) − x ⋆ = x τ ( p + 1 ) − x ⋆ + q p − u p
∥ x τ ( p + 1 ) − x ⋆ ∥ 2 = ∥ x ~ τ ( p + 1 ) − x ⋆ ∥ 2 + 2 ⟨ x ~ τ ( p + 1 ) − x ⋆ , q p − u p ⟩ + ∥ q p − u p ∥ 2 . (14) \left\|x_{\tau(p+1)}-x_\star\right\|^2
=\left\|\widetilde{x}_{\tau(p+1)}-x_\star\right\|^2+2\left\langle\widetilde{x}_{\tau(p+1)}-x_\star,q_p-u_p\right\rangle+\left\|q_p-u_p\right\|^2. \tag*{(14)} x τ ( p + 1 ) − x ⋆ 2 = x τ ( p + 1 ) − x ⋆ 2 + 2 ⟨ x τ ( p + 1 ) − x ⋆ , q p − u p ⟩ + ∥ q p − u p ∥ 2 . (14) By Assumption 2.2, E Q [ q p − u p ] = E [ q p − u p ∣ F p , u p ] = 0 \mathbb{E}_{\mathsf{Q}}[\mathbf{q}_p-\mathbf{u}_p]=\mathbb{E}[\mathbf{q}_p-\mathbf{u}_p\mid\mathcal{F}_p,\mathbf{u}_p]=0 E Q [ q p − u p ] = E [ q p − u p ∣ F p , u p ] = 0 E Q [ ∥ q p − u p ∥ 2 ] = E [ ∥ q p − u p ∥ 2 ∣ F p , u p ] ≤ ω ∥ u p ∥ 2 \mathbb{E}_{\mathsf{Q}}\left[\|\mathbf{q}_p-\mathbf{u}_p\|^2\right]=\mathbb{E}\left[\|\mathbf{q}_p-\mathbf{u}_p\|^2\mid\mathcal{F}_p,\mathbf{u}_p\right]\leq\omega\|\mathbf{u}_p\|^2 E Q [ ∥ q p − u p ∥ 2 ] = E [ ∥ q p − u p ∥ 2 ∣ F p , u p ] ≤ ω ∥ u p ∥ 2
Moreover, x ~ τ ( p + 1 ) − x ⋆ = x τ p + u p − x ⋆ \widetilde{\mathbf{x}}_{\tau(p+1)}-\mathbf{x}_\star=\mathbf{x}_{\tau p}+\mathbf{u}_p-\mathbf{x}_\star x τ ( p + 1 ) − x ⋆ = x τ p + u p − x ⋆ F p \mathcal{F}_p F p u p \mathbf{u}_p u p (14) given F p \mathcal{F}_p F p u p \mathbf{u}_p u p
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] = E p [ E Q [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ] ≤ E p [ ∥ x ~ τ ( p + 1 ) − x ⋆ ∥ 2 ] + ω E p [ ∥ u p ∥ 2 ] . (15) \mathbb{E}_p\left[\|\mathbf{x}_{\tau(p+1)}-\mathbf{x}_\star\|^2\right]=\mathbb{E}_p\left[\mathbb{E}_{\mathsf{Q}}\left[\|\mathbf{x}_{\tau(p+1)}-\mathbf{x}_\star\|^2\right]\right]
\leq\mathbb{E}_p\left[\|\widetilde{\mathbf{x}}_{\tau(p+1)}-\mathbf{x}_\star\|^2\right]+\omega\mathbb{E}_p\left[\|\mathbf{u}_p\|^2\right]. \tag*{(15)} E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] = E p [ E Q [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ] ≤ E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] + ω E p [ ∥ u p ∥ 2 ] . (15) We first bound the first term in (15) . Since x ~ τ ( p + 1 ) \widetilde{\mathbf{x}}_{\tau(p+1)} x τ ( p + 1 ) τ \tau τ Lemma B.3 gives
E p [ ∥ x ~ τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ G D ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ G D ) . (16) \mathbb{E}_p\left[\|\widetilde{\mathbf{x}}_{\tau(p+1)}-\mathbf{x}_\star\|^2\right]\leq\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\|^2-2\gamma\tau\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\rangle+\gamma^2\tau^2\left(A_{\tau}^{\mathrm{GD}}\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\rangle+B_{\tau}^{\mathrm{GD}}\right). \tag*{(16)} E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ GD ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ GD ) . (16) Next, using Lemma B.2 with t = τ t=\tau t = τ i = 1 , … , n i=1,\ldots,n i = 1 , … , n L i ≤ L max L_i\leq L_{\max} L i ≤ L m a x
E p [ ∥ u p ∥ 2 ] = E p [ ∑ i = 1 n ∥ x ~ τ ( p + 1 ) i − x τ p i ∥ 2 ] ≤ γ 2 τ 2 ∑ i = 1 n ∥ ∇ f i ( x τ p i ; x τ p i ) ∥ 2 + γ 2 τ ∑ i = 1 n ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L i ) σ i 2 ≤ γ 2 τ 2 ∥ F ( x τ p ) ∥ 2 + γ 2 τ ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L max ) σ 2 = γ 2 τ 2 ( ∥ F ( x τ p ) ∥ 2 + U τ ) ≤ ( S C O ) γ 2 τ 2 ( ℓ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + U τ ) . (17) \begin{aligned}
\mathbb{E}_p\left[\|\mathbf{u}_p\|^2\right]
&=\mathbb{E}_p\left[\sum_{i=1}^{n}\|\widetilde{\mathbf{x}}_{\tau(p+1)}^i-\mathbf{x}_{\tau p}^i\|^2\right]\\
&\leq\gamma^2\tau^2\sum_{i=1}^{n}\|\nabla f_i(\mathbf{x}_{\tau p}^i;\mathbf{x}_{\tau p}^i)\|^2+\gamma^2\tau\sum_{i=1}^{n}\left(1+2(\tau-1)(\tau+1)\gamma L_i\right)\sigma_i^2\\
&\leq\gamma^2\tau^2\|F(\mathbf{x}_{\tau p})\|^2+\gamma^2\tau\left(1+2(\tau-1)(\tau+1)\gamma L_{\max}\right)\sigma^2\\
&=\gamma^2\tau^2\left(\|F(\mathbf{x}_{\tau p})\|^2+U_\tau\right)\\
&\overset{\mathrm{(SCO)}}{\leq}\gamma^2\tau^2\left(\ell\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\rangle+U_\tau\right). \tag*{(17)}
\end{aligned} E p [ ∥ u p ∥ 2 ] = E p [ i = 1 ∑ n ∥ x τ ( p + 1 ) i − x τ p i ∥ 2 ] ≤ γ 2 τ 2 i = 1 ∑ n ∥∇ f i ( x τ p i ; x τ p i ) ∥ 2 + γ 2 τ i = 1 ∑ n ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L i ) σ i 2 ≤ γ 2 τ 2 ∥ F ( x τ p ) ∥ 2 + γ 2 τ ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L m a x ) σ 2 = γ 2 τ 2 ( ∥ F ( x τ p ) ∥ 2 + U τ ) ≤ ( SCO ) γ 2 τ 2 ( ℓ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + U τ ) . (17) where U τ : = σ 2 τ ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L max ) U_\tau:=\frac{\sigma^2}{\tau}\left(1+2(\tau-1)(\tau+1)\gamma L_{\max}\right) U τ := τ σ 2 ( 1 + 2 ( τ − 1 ) ( τ + 1 ) γ L m a x ) (16) and (17) into (15) yields,
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ G D ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ G D ) + ω γ 2 τ 2 ( ℓ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + U τ ) = ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( ( A τ G D + ω ℓ ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ G D + ω U τ ) . \begin{aligned}
\mathbb{E}_p\left[\|\mathbf{x}_{\tau(p+1)}-\mathbf{x}_\star\|^2\right]
&\leq\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\|^2-2\gamma\tau\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\rangle\\
&\quad+\gamma^2\tau^2\left(A_\tau^{\mathrm{GD}}\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\rangle+B_\tau^{\mathrm{GD}}\right)\\
&\quad+\omega\gamma^2\tau^2\left(\ell\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\rangle+U_\tau\right)\\
&=\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\|^2-2\gamma\tau\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\rangle\\
&\quad+\gamma^2\tau^2\left((A_\tau^{\mathrm{GD}}+\omega\ell)\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\rangle+B_\tau^{\mathrm{GD}}+\omega U_\tau\right).
\end{aligned} E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ GD ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ GD ) + ω γ 2 τ 2 ( ℓ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + U τ ) = ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( ( A τ GD + ω ℓ ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ GD + ω U τ ) . This is exactly (4) with A τ = A τ G D + ω ℓ A_\tau=A_\tau^{\mathrm{GD}}+\omega\ell A τ = A τ GD + ω ℓ B τ = B τ G D + ω U τ B_\tau=B_\tau^{\mathrm{GD}}+\omega U_\tau B τ = B τ GD + ω U τ □ \square □
C-PEARL-SVRG
Proof. For k = τ p , … , τ ( p + 1 ) − 1 k=\tau p,\ldots,\tau(p+1)-1 k = τ p , … , τ ( p + 1 ) − 1 i ∈ [ n ] i\in[n] i ∈ [ n ] x ~ τ p i = x τ p i \widetilde{\mathbf{x}}_{\tau p}^i=\mathbf{x}_{\tau p}^i x τ p i = x τ p i x ~ k + 1 i = x ~ k i − γ g k i \widetilde{\mathbf{x}}_{k+1}^i=\widetilde{\mathbf{x}}_k^i-\gamma\mathbf{g}_k^i x k + 1 i = x k i − γ g k i g k i = ∇ f i , ξ k i ( x ~ k i ; x τ p i ) − ∇ f i , ξ k i ( x τ p i ; x τ p i ) + ∇ f i ( x τ p i ; x τ p i ) \mathbf{g}_k^i=\nabla f_{i,\xi_k^i}(\widetilde{\mathbf{x}}_k^i;\mathbf{x}_{\tau p}^i)-\nabla f_{i,\xi_k^i}(\mathbf{x}_{\tau p}^i;\mathbf{x}_{\tau p}^i)+\nabla f_i(\mathbf{x}_{\tau p}^i;\mathbf{x}_{\tau p}^i) g k i = ∇ f i , ξ k i ( x k i ; x τ p i ) − ∇ f i , ξ k i ( x τ p i ; x τ p i ) + ∇ f i ( x τ p i ; x τ p i ) τ \tau τ i i i u p i = x ~ τ ( p + 1 ) i − x τ p i \mathbf{u}_p^i=\widetilde{\mathbf{x}}_{\tau(p+1)}^i-\mathbf{x}_{\tau p}^i u p i = x τ ( p + 1 ) i − x τ p i q p i = Q i ( u p i ) q_p^i = Q^i(u_p^i) q p i = Q i ( u p i ) u p = ( u p 1 , … , u p n ) \mathbf{u}_p = (u_p^1,\ldots,u_p^n) u p = ( u p 1 , … , u p n ) q p = ( q p 1 , … , q p n ) \mathbf{q}_p = (q_p^1,\ldots,q_p^n) q p = ( q p 1 , … , q p n ) x ~ τ ( p + 1 ) = ( x ~ τ ( p + 1 ) 1 , … , x ~ τ ( p + 1 ) n ) \widetilde{\mathbf{x}}_{\tau(p+1)} = (\widetilde{x}_{\tau(p+1)}^1,\ldots,\widetilde{x}_{\tau(p+1)}^n) x τ ( p + 1 ) = ( x τ ( p + 1 ) 1 , … , x τ ( p + 1 ) n ) x τ ( p + 1 ) − x ⋆ = ( x ~ τ ( p + 1 ) − x ⋆ ) + ( q p − u p ) \mathbf{x}_{\tau(p+1)}-\mathbf{x}_\star= (\widetilde{\mathbf{x}}_{\tau(p+1)}-\mathbf{x}_\star)+(\mathbf{q}_p-\mathbf{u}_p) x τ ( p + 1 ) − x ⋆ = ( x τ ( p + 1 ) − x ⋆ ) + ( q p − u p ) (14) and (15) as in C-PEARL-SGD.
Here, our x ~ τ ( p + 1 ) \widetilde{\mathbf{x}}_{\tau(p+1)} x τ ( p + 1 ) F p \mathcal{F}_p F p (13) we have
E p [ ∥ x ~ τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 A τ V R ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ . (18) \mathbb{E}_p\left[\left\|\widetilde{\mathbf{x}}_{\tau(p+1)}-\mathbf{x}_\star\right\|^2\right] \leq\left\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\|^2-2\gamma\tau\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle+\gamma^2\tau^2 A_\tau^{\mathrm{VR}}\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle. \tag*{(18)} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 A τ VR ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ . (18) Next, by Lemma B.6 with t = τ t=\tau t = τ L i ≤ L max L_i\leq L_{\max} L i ≤ L m a x
E p [ ∥ u p ∥ 2 ] = E p [ ∑ i = 1 n ∥ x ~ τ ( p + 1 ) i − x τ p i ∥ 2 ] ≤ 4 γ 2 τ 2 ∑ i = 1 n ∥ ∇ f i ( x τ p i ; x τ p i ) ∥ 2 = 4 γ 2 τ 2 ∥ F ( x τ p ) ∥ 2 ≤ (SCO) 4 γ 2 τ 2 ℓ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ . (19) \begin{aligned}
\mathbb{E}_p\left[\left\|\mathbf{u}_p\right\|^2\right]
&=\mathbb{E}_p\left[\sum_{i=1}^n\left\|\widetilde{x}_{\tau(p+1)}^i-x_{\tau p}^i\right\|^2\right]\\
&\leq4\gamma^2\tau^2\sum_{i=1}^n\left\|\nabla f_i\left(x_{\tau p}^i;x_{\tau p}^i\right)\right\|^2\\
&=4\gamma^2\tau^2\left\|F(\mathbf{x}_{\tau p})\right\|^2\\
&\overset{\text{\scriptsize(SCO)}}{\leq}4\gamma^2\tau^2\ell\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle. \tag*{(19)}
\end{aligned} E p [ ∥ u p ∥ 2 ] = E p [ i = 1 ∑ n x τ ( p + 1 ) i − x τ p i 2 ] ≤ 4 γ 2 τ 2 i = 1 ∑ n ∇ f i ( x τ p i ; x τ p i ) 2 = 4 γ 2 τ 2 ∥ F ( x τ p ) ∥ 2 ≤ (SCO) 4 γ 2 τ 2 ℓ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ . (19) Substituting (18) and (19) into (15) , we get
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 A τ V R ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + 4 ω γ 2 τ 2 ℓ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ = ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ V R + 4 ω ℓ ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ . \begin{aligned}
\mathbb{E}_p\left[\left\|\mathbf{x}_{\tau(p+1)}-\mathbf{x}_\star\right\|^2\right]
&\leq\left\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\|^2-2\gamma\tau\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle\\
&\quad+\gamma^2\tau^2 A_\tau^{\mathrm{VR}}\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle\\
&\quad+4\omega\gamma^2\tau^2\ell\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle\\
&=\left\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\|^2-2\gamma\tau\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle\\
&\quad+\gamma^2\tau^2\left(A_\tau^{\mathrm{VR}}+4\omega\ell\right)\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle.
\end{aligned} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 A τ VR ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + 4 ω γ 2 τ 2 ℓ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ = ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ VR + 4 ω ℓ ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ . This is (4) with A τ = A τ V R + 4 ω ℓ A_\tau=A_\tau^{\mathrm{VR}}+4\omega\ell A τ = A τ VR + 4 ω ℓ B τ = 0 B_\tau=0 B τ = 0
Proof of Theorem 4.3
Proof. Starting from Assumption 4.1 and using (QSM),
E p [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ ) = ∥ x τ p − x ⋆ ∥ 2 − γ τ ( 2 − γ τ A τ ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 B τ ≤ (QSM) ∥ x τ p − x ⋆ ∥ 2 − γ τ μ ( 2 − γ τ A τ ) ∥ x τ p − x ⋆ ∥ 2 + γ 2 τ 2 B τ = ( 1 − γ τ μ ζ ) ∥ x τ p − x ⋆ ∥ 2 + γ 2 τ 2 B τ . (20) \begin{aligned}
\mathbb{E}_p\left[\left\|\mathbf{x}_{\tau(p+1)}-\mathbf{x}_\star\right\|^2\right]
&\leq\left\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\|^2-2\gamma\tau\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle\\
&\quad+\gamma^2\tau^2\left(A_\tau\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle+B_\tau\right)\\
&=\left\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\|^2-\gamma\tau(2-\gamma\tau A_\tau)\left\langle F(\mathbf{x}_{\tau p}),\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\rangle+\gamma^2\tau^2B_\tau\\
&\overset{\text{\scriptsize(QSM)}}{\leq}\left\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\|^2-\gamma\tau\mu(2-\gamma\tau A_\tau)\left\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\|^2+\gamma^2\tau^2B_\tau\\
&=(1-\gamma\tau\mu\zeta)\left\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\|^2+\gamma^2\tau^2B_\tau. \tag*{(20)}
\end{aligned} E p [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ∥ x τ p − x ⋆ ∥ 2 − 2 γ τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 ( A τ ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + B τ ) = ∥ x τ p − x ⋆ ∥ 2 − γ τ ( 2 − γ τ A τ ) ⟨ F ( x τ p ) , x τ p − x ⋆ ⟩ + γ 2 τ 2 B τ ≤ (QSM) ∥ x τ p − x ⋆ ∥ 2 − γ τ μ ( 2 − γ τ A τ ) ∥ x τ p − x ⋆ ∥ 2 + γ 2 τ 2 B τ = ( 1 − γ τ μ ζ ) ∥ x τ p − x ⋆ ∥ 2 + γ 2 τ 2 B τ . (20) Since A τ ≥ μ A_\tau\geq\mu A τ ≥ μ 0 < γ τ A τ < 2 0<\gamma\tau A_\tau<2 0 < γ τ A τ < 2 0 < γ τ μ ζ = μ A τ ( γ τ A τ ) ( 2 − γ τ A τ ) ≤ 1 0<\gamma\tau\mu\zeta=\frac{\mu}{A_\tau}(\gamma\tau A_\tau)(2-\gamma\tau A_\tau)\leq1 0 < γ τ μ ζ = A τ μ ( γ τ A τ ) ( 2 − γ τ A τ ) ≤ 1
E [ ∥ x τ ( p + 1 ) − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ ) E [ ∥ x τ p − x ⋆ ∥ 2 ] + γ 2 τ 2 B τ . \mathbb{E}\left[\left\|\mathbf{x}_{\tau(p+1)}-\mathbf{x}_\star\right\|^2\right]\leq(1-\gamma\tau\mu\zeta)\mathbb{E}\left[\left\|\mathbf{x}_{\tau p}-\mathbf{x}_\star\right\|^2\right]+\gamma^2\tau^2B_\tau. E [ x τ ( p + 1 ) − x ⋆ 2 ] ≤ ( 1 − γ τ μ ζ ) E [ ∥ x τ p − x ⋆ ∥ 2 ] + γ 2 τ 2 B τ . Finally, recursive application of the above inequality for p = 0 , … , R − 1 p = 0,\ldots,R-1 p = 0 , … , R − 1
E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ ) R ∥ x 0 − x ⋆ ∥ 2 + γ τ B τ μ ζ . \mathbb{E}\left[\lVert x_{\tau R} - x_\star\rVert^2\right] \le(1-\gamma\tau\mu\zeta)^R\lVert x_0-x_\star\rVert^2+\frac{\gamma\tau B_\tau}{\mu\zeta}. E [ ∥ x τ R − x ⋆ ∥ 2 ] ≤ ( 1 − γ τ μ ζ ) R ∥ x 0 − x ⋆ ∥ 2 + μ ζ γ τ B τ . Comparison with Algorithms in Distributed Optimization
In Section 2, we compared the increment-sharing mechanism with two compression-based methods in distributed minimization: QSGD (Quantized SGD) [2 , 11 ] and DIANA [29 ] . Here, we explain this connection in more detail. Since distributed minimization and MpFL are different settings, we only compare how the methods choose the quantity to compress and how this affects the error due to compression.
Problem Setting
Consider the standard distributed minimization problem
min x ∈ R d f ( x ) : = 1 n ∑ i = 1 n f i ( x ) , \min_{x\in\mathbb{R}^d} f(x) := \frac{1}{n}\sum_{i=1}^{n}f_i(x), x ∈ R d min f ( x ) := n 1 i = 1 ∑ n f i ( x ) , where worker i i i f i f_i f i x x x x ⋆ x_\star x ⋆ ∇ f ( x ⋆ ) = 1 n ∑ i = 1 n ∇ f i ( x ⋆ ) = 0 \nabla f(x_\star)=\frac{1}{n}\sum_{i=1}^{n}\nabla f_i(x_\star)=0 ∇ f ( x ⋆ ) = n 1 ∑ i = 1 n ∇ f i ( x ⋆ ) = 0 ∇ f i ( x ⋆ ) \nabla f_i(x_\star) ∇ f i ( x ⋆ )
Comparison with QSGD and DIANA
Figure 5 compares QSGD [2 , 29 ] , DIANA [29 ] , and C-PEARL-SGD with the algorithms grouped by their problem setting. For QSGD, we follow the distributed formulation in [29 Algorithm 2] , and for DIANA, we use [29 Algorithm 1] without momentum or regularization. In both cases, Q i Q^i Q i g p i = ∇ f i ( x p ) g_p^i=\nabla f_i(x_p) g p i = ∇ f i ( x p ) q p i q_p^i q p i q ˉ p = 1 n ∑ i = 1 n q p i \bar{q}_p=\frac{1}{n}\sum_{i=1}^{n}q_p^i q ˉ p = n 1 ∑ i = 1 n q p i i i i f i ( x i ; x − i ) f_i(x^i;x^{-i}) f i ( x i ; x − i ) x i x^i x i g k i = ∇ f i ( x ~ k i ; x τ p − i ) g_k^i=\nabla f_i(\tilde{x}_k^i;x_{\tau p}^{-i}) g k i = ∇ f i ( x ~ k i ; x τ p − i ) q p i q_p^i q p i q p = ( q p 1 , … , q p n ) q_p=(q_p^1,\ldots,q_p^n) q p = ( q p 1 , … , q p n )
Figure 5. Comparison of the quantities compressed by QSGD and DIANA in distributed minimization (left) and by C-PEARL-SGD in MpFL (right). The input to each compressor is highlighted in red.
Having described the different problem settings and update rules in Figure 5 , we now focus on the quantities that these methods compress and how this choice affects the compression error. In distributed minimization, QSGD [2 , 29 ] directly compresses the local gradient g p i = ∇ f i ( x p ) g_p^i = \nabla f_i(x_p) g p i = ∇ f i ( x p ) x ⋆ x_\star x ⋆ ∇ f i ( x ⋆ ) \nabla f_i(x_\star) ∇ f i ( x ⋆ ) [29 ] addresses this by compressing the difference between the local gradient and a memory vector, rather than the gradient itself. Each worker maintains a memory vector h p i h_p^i h p i Δ p i = g p i − h p i \Delta_p^i = g_p^i - h_p^i Δ p i = g p i − h p i g p i g_p^i g p i h p i h_p^i h p i ∇ f i ( x ⋆ ) \nabla f_i(x_\star) ∇ f i ( x ⋆ ) Δ p i \Delta_p^i Δ p i [29 ] and therefore the compression error also vanishes as the method approaches the solution.
The same idea explains increment sharing in MpFL. C-PEARL-SGD compresses the local strategy increment u p i = x ~ τ ( p + 1 ) i − x τ p i u_p^i = \tilde{x}_{\tau(p+1)}^i - x_{\tau p}^i u p i = x ~ τ ( p + 1 ) i − x τ p i x τ p i x_{\tau p}^i x τ p i u p i u_p^i u p i
