arXiv CSopen access

Exploiting Correlations in Federated Learning: Opportunities and Practical Limitations

1

Exploiting Correlations in Federated Learning: Opportunities and Practical Limitations

arXiv:2604.14751v1 [cs.IT] 16 Apr 2026

Adrian Edin, Student Member, IEEE, Michel Kieffer, Senior Member, IEEE, Mikael Johansson, IEEE Fellow, and Zheng Chen, Senior Member, IEEE

Abstract—The communication bottleneck in federated learning (FL) has spurred extensive research into techniques to reduce the volume of data exchanged between client devices and the central parameter server. In this paper, we systematically classify gradient and model compression schemes into three categories based on the type of correlations they exploit: structural, temporal, and spatial. We examine the sources of such correlations, propose quantitative metrics for measuring their magnitude, and reinterpret existing compression methods through this unified correlation-based framework. Our experimental studies demonstrate that the degrees of structural, temporal, and spatial correlations vary significantly depending on task complexity, model architecture, and algorithmic configurations. These findings suggest that algorithm designers should carefully evaluate correlation assumptions under specific deployment scenarios rather than assuming that they are always present. Motivated by these findings, we propose two adaptive compression designs that actively switch between different compression modes based on the measured correlation strength, and we evaluate their performance gains relative to conventional non-adaptive approaches. In summary, our unified taxonomy provides a clean and principled foundation for developing more effective and application-specific compression techniques for FL systems. Index Terms—Federated learning, communication efficiency, compression, correlation.

updates are then sent to a central parameter server (PS), which aggregates them to obtain an updated global model. Compared to centralized learning, FL offers advantages such as improved scalability and enhanced data privacy. However, FL also faces the challenge of a communication bottleneck due to frequent information exchange between local clients and the PS, especially when the exchanged information contains high-dimensional parameter vectors from deep neural networks. To address this communication bottleneck, several strategies for improving the communication efficiency of FL have been proposed based on reducing the number of bits transmitted from clients to the server in each communication round, e.g., through model update compression [1]; • reducing the number of active communication links, e.g., via client selection [2], [3] or event-triggered communication [4], [5]; • reducing the frequency of communication, e.g., by performing multiple gradient steps before aggregation [6]. •

In earlier studies, commonly used compression techniques in FL, such as quantization [7] and random sparsification [8], treat the model updates generated by local clients as independent I. I NTRODUCTION information sources. However, the correlation and redundancy As machine learning (ML) models grow in scale and among local model updates can be exploited to achieve complexity, training them on massive datasets with a single more efficient compression. These correlations may arise machine becomes increasingly demanding. The rise of edge from the model architecture, the learning algorithm, or other computing and data parallelism has driven the emergence of design choices in the FL system [9]–[12]. Classical coding collaborative machine learning, where multiple nodes—each theory shows that correlated sources can be compressed more with access to a portion of the data—collaborate to train efficiently, with greater savings as correlation increases [13]. a shared model without sharing raw samples. This can be For instance, in the lossy compression of parallel Gaussian done in a network with a master–worker architecture, such as sources, correlation enables lower transmission rates for a given federated learning (FL), or in a decentralized topology with distortion level compared to uncorrelated sources. Another local interactions, such as decentralized learning. In server- example is predictive coding, widely used in image and based FL, multiple clients iteratively update their local copy video compression, that exploits redundancy between adjacent of the global model using their own private data. These model pixels or consecutive frames to enhance compression efficiency. Inspired by this principle, recent works in FL [14]–[16] apply This work was supported in part by ELLIIT, the Swedish Research Council predictive techniques to compress temporally correlated model (VR), the Knut and Alice Wallenberg (KAW) Foundation, and the Wallenberg updates. By forecasting future updates from past ones, only the AI, Autonomous Systems and Software Program (WASP) funded by the Knut residuals—representing deviations from the prediction—need to and Alice Wallenberg Foundation. Adrian Edin and Zheng Chen are with the Department of Electrical be transmitted, significantly reducing communication overhead Engineering (ISY), Linköping University, SE-581 83 Linköping, Sweden when consecutive updates are sufficiently correlated. So far, (email: {adrian.edin, zheng.chen}@liu.se). Michel Kieffer is with CentraleSupélec, CNRS, L2S, Uni- predictive coding has mainly been applied to exploit temversité Paris-Saclay, Gif-sur-Yvette, FR-91192, France (email: poral correlations in local model updates, but the underlying [email protected]). principle is not limited to the time domain. In fact, similar Mikael Johansson is with the Division of Decision and Control Systems, School of EECS, KTH Royal Institute of Technology, SE-100 44 Stockholm, strategies could also be applied to capture structural correlations Sweden (email: [email protected]). within the model itself or spatial correlations across clients,

2

for example, using subspace projection methods [17]–[19]. However, whether such correlations are present in practical FL settings and how they might be effectively measured and leveraged for compression remains an open question. Given the growing interest in redundancy-based compression schemes in the FL literature, we find it pertinent to examine whether such correlations are observable in practice, and to what extent they can actually contribute to improving communication efficiency. Our paper makes the following contributions: • We introduce a unified framework for analyzing structural, temporal, and spatial correlations in FL, and propose metrics for measuring each type of correlation. • We reinterpret existing redundancy-based compression techniques through the lens of these correlations, offering a new perspective on their underlying design principles. • The practical limitations of correlation-based subspace projection methods, such as computational complexity and memory overhead, are also discussed to provide a thorough assessment of their advantages and disadvantages. • Based on existing non-adaptive compression schemes, we propose two adaptive designs that measure the strength of correlations on the fly and dynamically switch between different compression modes. • We conduct experiments demonstrating that correlation strength varies with model size, task complexity, and system configuration. These results highlight the importance of adaptive compression designs compared to their static counterparts. Notation: The set of real numbers is denoted by R. Vectors are written in bold lowercase letters, e.g., a, and matrices in uppercase letters, e.g., A. The symbols ∥·∥ and ∥·∥F denote the Euclidean norm and Frobenius norm, respectively. For a set S, |S| denotes its cardinality. For a positive integer N , [N ] denotes the set {1, . . . , N }. II. T HREE S OURCES OF C ORRELATION IN F EDERATED L EARNING In a FL system, a set of K distributed clients collaborates in training a shared ML model under the coordination of a central PS. Each client k ∈ [K] has local access to subset Dk of the complete dataset D = ∪K k=1 Dk . The training objective is to minimize a global loss f (x) =

K X

wk fk (x),

(1)

k=1

where x ∈ Rd is the vector of model parameters, wk = |Dk |/|D| are aggregation weights proportional to the amount P of data held by client k, fk (x) = |D1k | ξ∈Dk ℓ(x; ξ) is the local objective of client k, and ℓ(x; ξ) is the loss for sample ξ. A canonical FL algorithm is federated averaging (FedAvg) [20], which proceeds iteratively as follows: 1) The PS broadcasts the current global model parameters x(t) to all clients. 2) Each client k performs τ local stochastic gradient updates using mini-batches (t,i+1)

xk

(t,i)

= xk

(t,i)

− γ∇fk (xk

(t,i)

, Dk

), i = 0, . . . , τ − 1,

(t,i)

where γ is the learning rate, and Dk is a randomly sampled mini-batch of data from Dk . (t) 3) Each client computes its local model update gk = (t,τ ) xk − x(t) and sends it to the PS.1 4) The PS aggregates all updates to obtain the new global model: x(t+1) = x(t) +

K X

(t)

wk gk .

(2)

k=1

Many variations of FedAvg have been proposed, such as reducing variance by computing and communicating auxiliary correction vectors [21], [22], introducing momentum in local updates [23], or adding a proximal term to improve stability in heterogeneous settings [24]. a) Communication Bottleneck: In each round of the distributed training procedure, FedAvg requires two communication phases: (1) clients upload local updates to the PS; and (2) the PS broadcasts the updated global model. Most existing research on communication-efficient FL focuses on client-to-PS links, since each client requires dedicated resources to transmit its model update to the PS. To reduce the communication cost, data compression is commonly applied (t) before transmitting the local model updates. Let {b gk }k=1,...,K represent the reconstructed local model updates at the PS, a common design principle for compression is to minimize the distortion measured by the empirical mean square error (MSE), given by 1 (t) (t) ∥b g − gk ∥2 . (3) d k Many existing works use this distortion measure implicitly or explicitly, as we will discuss later. Earlier studies on FL with compressed updates focus on simple schemes such as sparsification or masking. Recent studies have adopted different forms of subspace projection methods, motivated by the potential correlation/redundancy in transmitted information [10], [11], [16], [25]–[27]. Nevertheless, current literature lacks a unified taxonomy to describe and interpret how specific compression designs relate to different sources of correlation inherent in FL algorithms. We categorize them into three types: • Structural correlation results from the learning model, e.g., neural network structure. Some components of the gradient vectors may be correlated with other components. • Temporal correlation originates from the iterative nature of the optimization algorithm and is influenced by design features such as momentum and regularization. As a result, gradient vectors generated in consecutive iterations may exhibit significant correlation. • Spatial correlation arises when training datasets across different clients share similar distributions. This can lead to correlated local model updates across clients. In the following sections, we discuss each correlation type in detail and provide illustrative examples. While a complete theoretical understanding of these correlations remains elusive – (t)

(t)

MSE(b gk , gk ) =

1With single-step SGD, i.e., τ = 1, the local model update equals the negative of the local gradient multiplied by the step size.

3

partly due to the black-box nature of deep learning models [28] – we aim to offer practical insight and useful tools for analyzing and exploiting them. III. S TRUCTURAL C ORRELATION We define structural correlation as the dependency among (t) the elements within a client’s local model update gk . Let us consider a simple linear regression example. Given a dataset D containg N pairs of feature-observation points (ξi , yi ) ∈ Rd−1 × R, i ∈ [N ], we form a prediction function ybi using a linear model

update slice. The structural correlation may depend on the organization of the model update matrix, as evidenced in [9], [26], [35], where different choices for the mapping from vector (t) (t) gk to matrix Gk have been considered. The cosine similarity is used to measure the degree of structural correlation between two model update slices:  (t) T (t)  (gk,i ) gk,j , g (t) ̸= 0 and g (t) ̸= 0 (t) (t) (t) (t) k,i k,j CSS(gk,i , gk,j ) = ∥gk,i ∥∥gk,j ∥  0, otherwise

where i and j are slice indices. In FL, if different model update slices of the model update matrix exhibit high pairwise cosine ybi (w, b) = ξTi w + b, (4) similarity, it becomes possible to identify a common subspace where w ∈ Rd−1 is the weight vector and b ∈ R is the bias. to represent these model update slices effectively. This enables The objective is to find the estimate of w and b such that a more efficient, lower-dimensional representation, which is y1 , . . . , ybN )T ∈ RN and the main motivation behind many compression designs using the corresponding elements of yb = (b T N y = (y1 , . . . , yN ) ∈ R are as close as possible for all low-rank approximation. Another way to quantify the degree of structural correlation samples i ∈ D. Using vector notation, we obtain yb(x) = Rx, T T N ×d d is to use singular value decomposition (SVD). A matrix G ∈ where R = [ξ1 , . . . , ξN ; 1N ] ∈ R , and x = [w; b] ∈ R m×n R can be decomposed as collects all tunable parameters. We quantify the quality of the fit using the MSE over all N samples. The objective and its gradient are

G = U ΣV T ,

∥b y (x) − y∥2 xT RT Rx − 2yT Rx + yT y f (x) = = (5) N N and
1 2RT Rx − 2RT y , (6) ∇f (x) = N respectively. These expressions display how the dataset R and the objective function f (x) interact to potentially induce correlations among the components of ∇f (x). For more complex tasks with larger ML models, several existing works have investigated the existence of such structural correlation. For instance, [29] and [30] show that the gradient converges to a very small subspace spanned by a few top eigenvectors of the Hessian. This suggests that dimension reduction can be achieved by projecting the gradients onto a low-dimensional subspace [31]. The impact of the network model and data on the spectrum of the Hessian matrix has been investigated in [32]. The observations can also be related to the intrinsic dimensionality of data and model representations [33], [34], suggesting that high-dimensional models with a large number of parameters may effectively be trained within a lower-dimensional subspace.

where U ∈ Rm×m and V ∈ Rn×n are orthonormal matrices, and Σ ∈ Rm×n contains the singular values σ1 , . . . , σmin{m,n} on its main diagonal, in decreasing order σ1 ≥ · · · ≥ σmin{m,n} ≥ 0. SVD enables the identification of global correlations among multiple vectors, rather than local pairwise correlations, albeit at a higher computational cost than the cosine similarity metric. When applying SVD to the model update matrix, the presence of a few dominant singular values suggests a stronger low-rank structure.

A. How to Evaluate the Degree of Structural Correlation? (t)

First, consider the local model update vector gk ∈ Rd , we introduce the model update matrix generated by client k at iteration t as   (t) (t) (t) Gk = gk,1 (7) . . . gk,n ∈ Rm×n , (t)

(t)

where gk,i ∈ Rm is the i-column of Gk . This matrix contains (t) the elements of gk ∈ Rd , reshaped into an m × n matrix (t) such that mn = d.2 We refer to each column gk,i as a model 2 If d is not divisible by m, zero-padding will be applied.

(8)

B. Exploiting Structural Correlation using Low-Rank Approximation Once a high degree of structural correlation is observed within each local model update, low-rank approximation can be applied to obtain a compressed update of reduced dimension. a) SVD: One example of low-rank approximation is to (t) perform SVD on the model update matrix Gk = U ΣV T , m×m n×n where U ∈ R and V ∈ R are orthogonal matrices and Σ contains the singular values. A lower-dimensional (t) representation of Gk can be formed using Ur ∈ Rm×r and n×r Vr ∈ R , whose columns are the first r columns of U and V respectively, i.e., Ur = [U ]:,1:r and Vr = [V ]:,1:r . Model update compression can use either Ur alone or the combination of Ur and Vr . • When compression uses only Ur , client k transmits the (t) compressed update UrT Gk ∈ Rr×n to the PS. The communication cost is rn in each client-to-PS link. The PS must also know Ur to reconstruct the original update, which requires transmitting rm elements. • When compression uses both Ur and Vr , client k transmits e (t) = UrT G(t) Vr ∈ Rr×r to the diagonal matrix G k k the PS. The communication cost is r (the number of diagonal elements in the matrix) in each client-to-PS link. Additional transmissions of rm elements for Ur and rn

4

Remark III.1. By ranking the singular values in decreasing order, and sending the basis vectors corresponding to the r largest singular values, the compression design effectively minimizes the MSE distortion of the reconstructed model update, under a limited number of transmitted elements. b) PCA: principal component analysis (PCA) [25], [26], [31] is another efficient tool for obtaining an approximate (t) representation of the model update matrix Gk using a set of vectors that capture the largest variations in the columns (t) of Gk . This is achieved by computing a covariance matrix (t) C from the columns of Gk and performing the eigenvalue T decomposition C = QΛQ , where Λ = diag(λ1 , . . . , λm ) is the diagonal matrix of eigenvalues, with λ1 ≥ · · · ≥ λm ≥ 0, and Q ∈ Rm×m is an orthonormal matrix.PGiven the model (t) (t) n update matrix Gk and the mean ḡ = n1 i′ =1 gk,i′ ∈ Rm , the covariance matrix is computed as C=

n 1 X (t) (t) (gk,i′ − ḡ)(gk,i′ − ḡ)T . n−1 ′

(9)

i =1

The principal components are the columns of Q. Consider the matrix Qr = [Q]:,1:r of the first r columns of Q. To exploit the structural correlation, client k can compute a reduceddimensional representation of the i-th model update slice as (t) (t) gek,i = QTr (gk,i − ḡ) ∈ Rr ,

1.0 x2

elements for Vr are required for the PS to reconstruct e (t) V T . Ur G r k An example of using SVD to compress local model updates is the ATOMO framework presented in [9].

1 1 1 8L 4L 2L

x∗

0.8 0.6 −0.75

−0.50

−0.25

0.00

0.25 x1

0.50

0.75

1.00

1.25

Figure 1. A 2D toy example with gradient descent and the quadratic loss function defined in (5). The trajectories marked with different colors correspond 1 1 1 to different values of the learning rate γ ∈ { 2L , 4L , 8L }.

generated by each client k. In general, the degree of temporal correlation may be affected by the following factors: • Properties of the loss function, e.g., convexity, and smoothness. With a convex and smooth global objective function, we expect stronger temporal correlation compared to a non-convex function with many local minima. • Hyperparameter values in the iterative optimization algorithm, e.g., learning rate, batch size, momentum, and regularization factor. Figure 1 shows the trajectory of the parameter vector (with two parameters) in a linear regression problem. We observe that a smaller learning rate yields a smoother trajectory, implying a higher degree of temporal correlation, albeit at the cost of requiring more iterations to converge. A. How to Evaluate the Degree of Temporal Correlation?

The degree of temporal correlation can be quantified using the cosine similarity between two model update vectors, i.e., which is then transmitted to the PS. After the PS receives the CSS(g (t1 ) , g (t2 ) ), where t and t are two time (iteration) 1 2 k compressed model update slice from client k, it can get an indices.k A high degree of similarity suggests that past model estimate of the model update slice by updates can be leveraged to predict the trajectory of future (t) (t) T (t) m gbk,i = Qr ge + ḡ = Qr Qr (gk,i − ḡ) + ḡ ∈ R . (11) updates, which is the main motivation behind prediction-based model update compression schemes. While the communication cost in the client-to-PS link for For the linear regression problem with a quadratic loss each model update slice is reduced to r elements instead of function, we can obtain a closed-form expression for the degree m, ensuring that both parties have knowledge of Qr and ḡ of temporal correlation. Combining the gradient vector in (6) requires additional transmission of m(r + 1) elements for all with the parameter update x(t+1) = x(t) − γ∇f (x(t) ), we get slices.   1  T  (t) ∇f (x(t+1) ) = 2R R x − γ∇f (x(t) ) − 2RT y Remark III.2. The PCA and SVD are closely related [36]. N 2RT R For example, when ḡ = 0m , the squared singular values σi2 =∇f (x(t) ) − γ ∇f (x(t) ) coincide with the eigenvalues of the covariance matrix λi , and N   the left unitary matrix U coincides with the PCA basis Q. 2RT R = I −γ ∇f (x(t) ). (12) N For both PCA and SVD, it is obvious that the choice of r (the number of basis vectors to be communicated) plays a Define A = I − γ 2RT R , and let L = λ ( RT R ), where max N N critical role. Larger values of r capture more information in the λ (·) extracts the maximum eigenvalue. Using a step size max subspace spanned by the model update matrix, while smaller 0 ≤ γ ≤ 1 ensures that ∥A∥ ≤ 1, which in turn implies values of r reduce the communication cost. There is always a ∥∇f (x(t+1)L)∥ ≤ ∥∇f (x(t) )∥ in (12). The cosine similarity trade-off among information loss, computational complexity, between two consecutive gradients is thus lower-bounded by and communication cost. ∇f (x(t+1) )T ∇f (x(t) ) CSS(∇f (x(t+1) ), ∇f (x(t) )) = ∥∇f (x(t+1) )∥∥∇f (x(t) )∥ IV. T EMPORAL C ORRELATION (t) T (t) ∇f (x ) A∇f (x ) In the context of FL, temporal correlation refers to the simil≥ ≥ min λi (A), (13) (t) (t+1) i ∥∇f (x(t) )∥2 arity between consecutive local model updates g , g , . . ., (10)

k

k

5

where λi (A) is the i-th eigenvalue of A. Because λi (A) = A primary source of spatial correlation is the training data T 1 gives mini λi (A) = λmin (A) = available to each client. When clients’ local datasets are drawn 1 − 2γλi ( RNR ), using γ ≤ 2L 1 − 2γL ≥ 0. Naturally, this means that a smaller learning rate from similar distributions, spatial correlation tends to be high. and a smaller L lead to a higher degree of temporal correlation. In FL, local datasets are very often statistically heterogeneous and unbalanced, which affects the degree of spatial correlation that can be observed during the training procedure [40], [41]. B. Exploiting Temporal Correlation using Predictive Coding Predictive coding techniques are widely used in multimedia compression scenarios to reduce redundancy by exploiting A. How to Evaluate the Degree of Spatial Correlation? correlations between adjacent pixels or image frames [13], The degree of spatial correlation between two clients can [37]. In FL, prediction-based encoding has been used to be quantified by the cosine similarity of their local model (t) (t) exploit the temporal correlation between consecutive model updates, i.e., CSS(gk , gl ), where k and l are two client updates [12], [14]–[16], [38], [39]. The key idea is to generate indices. When the model update vectors from multiple clients (t) a prediction gqk of the current model update based on are highly correlated, it is possible to identify a common lower(t−1) (t−2) the knowledge of previous updates {gk , gk , . . .} and dimensional subspace that efficiently represents these updates. (t) (t) transmit only the prediction residual gk − gqk , i.e., the Note that exploiting spatial correlation locally is difficult for difference between the actual update and the prediction. The PS individual clients unless each one has precise knowledge of computes the same prediction using shared information between the common subspace. Therefore, it requires the assistance of the clients, based on which it can reconstruct the original the PS, which has knowledge of all local model updates. model update after receiving the residual. When the prediction Again, we use the linear regression example to illustrate the is accurate, the residual contains much less information than effects of spatial correlation. We consider two clients k and l, the original model update, and can therefore be represented each with Nk and Nl data samples. The local loss functions using fewer bits. Communication efficiency can be further are given by fk (x) = 1 (xT RT Rk x − 2yT Rk x + yT yk ), and k k k Nk improved by omitting residual transmission when the prediction fl (x) = 1 (xT RT Rl x − 2yT Rl x + yT yl ), respectively. The l l l Nl is sufficiently accurate [11], [15]. The predictor can, e.g., cosine similarity between their gradient vectors is • the previous local model update (e.g., gradient vector when CSS(∇fk (x), ∇fl (x)) using single-step SGD) [12], [38], so that the prediction residual becomes the model update difference; (RTk Rk x − RTk yk )T (RTl Rl x − RTl yl ) = • momentum-inspired weighted average of previous local Nk Nl ∥∇fk (x(t) )∥∥∇fl (x(t) )∥ model updates [16], [39]; xT Ax + bT x + c = , (16) • linear combination of previous model updates with com∥∇fk (x(t) )∥∥∇fl (x(t) )∥ bination weights optimized by the least-squares criterion (i.e., minimizing the MSE distortion) [11], [15]. RTk Rk RTl Rl −1 T T T T T where A = N Nl , b = Nk Nl (yk Rk Rl Rl +yl Rl Rk Rk ), k Particularly, in [15], the prediction relies on a window of 1 T T and c = Nk Nl (yk Rk Rl yl ). The gradient of the quadratic ′ previously transmitted model updates {b g (t−t ) }t′ =1,...,h , which loss is invariant under unitary transformations of the column are combined through a linear predictor defined as space. Specifically, if Rl = P Rk and yl = P yk , for any h orthonormal P ∈ RNk ×Nk , then ∇fl (x) = RTl Rl x − RTl yl = X ′ (t) gqlin (a) = at′ gb(t−t ) . (14) RTk P T P Rk x − RTk P T P yk = RTk Rk x − RTk yk = ∇fk (x). t′ =1 Since the cosine similarity between any vector and itself is Here, a = [a1 , . . . , ah ] contains the prediction coefficients and one, it follows that CSS(∇fk (x), ∇fl (x)) = 1 in this case. By examining the row space further, we can identify two h is the memory size. The optimal coefficients a∗(t) ∈ Rh are found by minimizing the reconstruction error between the cases where CSS(∇fk (x), ∇fl (x)) = 0. First, if the row (t) spaces of Rl and Rk are orthogonal, i.e., Rk RTl = 0Nk ×Nl , current model update g (t) and the prediction gqlin (a), i.e., the cosine similarity is zero, which corresponds to the scenario (t) a∗(t) = argmin∥q glin (a) − g (t) ∥2 . (15) of extreme data heterogeneity. Otherwise, we obtain a level a∈Rh hypersurface of the quadratic function at which the cosine (t) The predictor can also be written in a matrix form gqk,lin (a) = similarity is zero. Note that this set of points includes the minimizers of fk (x) and fl (x). In the remaining parameter space, (t−1) (t−h) M a, where M = (gk , . . . , gk ) ∈ Rd×h . When M has the cosine similarity is nonzero, indicating the existence of full column rank, the MSE-optimal prediction coefficients can potential correlations that could be exploited for compression. ∗(t) T −1 T (t) be obtained in closed-form as a = (M M ) M g . This Quantifying spatial correlation between more than two clients (t) corresponds to projecting g onto the subspace spanned by is possible using a SVD-based measure. To facilitate this, we the columns of M . generalize the method in Section III-B by considering the observation matrix Φ ∈ Rp×q . The structure of Φ depends on V. S PATIAL C ORRELATION the type of correlation we aim to measure. To measure spatial (t) We define spatial correlation as the similarity between local correlation in FL, we use Φ = (g1(t) , . . . , gK ) ∈ Rd×K , which (t) model updates gk produced by different clients k ∈ [K]. contains the local gradient vectors from all clients, available at

6

(t)

the PS. To measure structural correlation, we take Φ = Gk ∈ Rm×n , as in Section III-B. Applying SVD to the measurement matrix gives Φ = U ΣV T , where Σ ∈ Rp×q contains the singular values σi , i ∈ [min{p, q}], sorted as σ1 ≥ .. ≥ σmin{p,q} , on its diagonal elements, and U ∈ Rp×p and V ∈ Rq×q are orthonormal matrices. Definition V.1 (Conserved Energy Ratio). Given an observation matrix Φ ∈ Rp×q , and r ∈ [0, min{p, q}], the energy conserved by the first r singular values is defined as αcer =

r X

σi2

.min{p,q} X

i=1

i=1

σi2 = ∥Σ1:r,1:r ∥2F /∥Σ∥2F .

(17)

Using Definition V.1, we define a measurement function MCorrSVD(Φ, βsvd ), where the inputs are: p×q • an observation matrix Φ ∈ R , and • a fraction βsvd ∈ [0, 1], and the output is the conserved energy ratio αcer ∈ [0, 1] for r = ⌈βsvd · min{p, q}⌉. This function quantifies the proportion of energy captured by a low-rank approximation using a fraction βsvd of the leading singular values. As an example, for some energy threshold αsvd ∈ [0, 1], we can consider sufficient correlation to be present if MCorrSVD(Φ, βsvd ) = αcer ≥ αsvd . While this heuristic rule can be applied, other metrics such as the effective rank [42] could provide a more principled way to quantify the extent of low-rank structure. B. Exploiting Spatial Correlation using Subspace Projection In addition to measuring the correlation degree, SVD can also be used to extract a subspace onto which we project the model update, thereby reducing its dimensionality. After collecting local model updates from all clients, the PS performs SVD (t) (t) on the measurement matrix Φ = (g1 , . . . , gK ) ∈ Rd×K as T Φ = U ΣV . Then, we define an operator TruncSVD(Φ, αsvd ), which, given inputs p×q • an observation matrix Φ ∈ R , and • a threshold αsvd ∈ [0, 1], returns the truncated SVD components r×r • Σr = Σ1:r,1:r ∈ R , p×r • Ur = U:,1:r ∈ R , and q×r • Vr = V:,1:r ∈ R , where r is selected as the smallest integer such that the conserved energy ratio (see Definition V.1) is above the target value αsvd . The PS needs to broadcast Ur (and possibly Vr ) to all clients so that they can perform model update compression by subspace projection in subsequent iterations. For example, when using Ur ∈ Rd×r to compress the model update vector (t) gk ∈ Rd , we have the compressed model update as (t)

(t)

gek = UrT gk ,

(18)

which reduces the number of transmitted elements from d to (t) r. After the PS receives gek , it can recover an approximate model update by (t)

(t)

(t)

gbk = Ur gek = Ur UrT gk .

(19)

Table I CLASSIFICATION OF RECENT COMPRESSION SCHEMES USED IN FL.

Structural Temporal Spatial ATOMO [9]

✓

—

—

LAG [4]

—

✓

—

Recycling [11]

—

✓

—

FedSketch [43]

✓

—

—

L-GreCo [44]

✓

—

—

✓

✓1

✓ —

Temporal sparsification mask [45], [46] Gradient difference [12], [38]

✓

✓1

Momentum-style prediction [16], [39]

—

✓1

—

Temporal predictive coding [15]

—

✓

— ✓

SVDFed [10]

—

✓1

GradiVeQ [26]

✓1

✓1

✓2

FedOComp [25]

—

✓1

✓2

PowerSGD [35], [47]

✓

✓

✓2

FedPara [48]

✓

—

—

SVD-resuse [49], [50]

✓

✓1

—

Proposed AdaSVDFed

—

✓

✓

Proposed PCAFed

✓

✓

✓

1 Implicit usage.2 Considers the aggregate.

Remark V.1. The SVD-based low-rank approximation method presented in Section III-B projects the current model update matrix G onto its top-r singular subspace. The subspace projection method presented in this section uses a fixed subspace with previously learned basis from an earlier iteration. The difference is that exploiting spatial correlation among clients requires server-side processing, i.e., the PS collects local updates to extract subspace information for client-side compression in later iterations. VI. B ENEFITS AND L IMITATIONS OF S UBSPACE P ROJECTION M ETHODS While the idea of using subspace projection for model update compression in FL is not new, our correlation-based taxonomy provides a unified lens for understanding the underlying design principles. In this section, we will classify existing studies into different categories, and discuss the benefits and limitations of these methods in terms of communication cost, computational, and memory overhead. A. Classification of Existing Compression Methods Table I gathers and classifies some existing correlation-aware compression methods, depending on the sources of correlation they rely on. Next, we discuss some of them in more detail. 1) Temporal Sparsification Mask : The works in [45], [46] consider sparsification in the standard parameter basis and are therefore classified as exploiting structural correlation. These schemes leverage temporal correlation by retaining part of the sparsification mask across consecutive iterations, implicitly assuming temporal correlation. Moreover, [46] is also classified

7

as exploiting spatial correlation because the portion of the mask preserved between iterations is shared across all clients. 2) GradiVeQ : The work in [26] adopts an alternative transmission protocol, known as ring-all-reduce, which provides all clients with access to the aggregated model update once communication is complete. The update is divided into model update slices, similarly to the approach used in this paper. The method alternates between two phases: a training phase and a compression phase. During the training phase, each client stores model updates, after which a covariance matrix is computed. Temporal correlation is exploited by using PCA, and the basis matrix learned from the first slice is reused for all subsequent slices. We classify this use of structural and temporal correlations as implicit, since a single basis matrix is reused across slices and across multiple iterations. 3) SVDFed : The work in [10] employs server-assisted compression to capture spatial correlation among clients using (t) (t) SVD. It uses Φ = (g1 , . . . , gK ), and performs compression using a truncated left orthonormal matrix Ur . These prior studies typically assume that the sources of correlation they rely on always exist. In practice, algorithm designers should verify the strength of these correlations and adapt the compression scheme accordingly, rather than applying one-size-fits-all compressors. B. Communication Cost Reduction

and g (t−j) can be as large as jθ, giving CSS(g (t) , g (t−j) ) ≥ cos(jθ). To guarantee temporal correlation, we require j ≤ mr 2π θ . If the break-even number of iterations m−r exceeds this limit, reusing the basis matrix for that many iterations is not guaranteed to be useful. C. Implicit Dependence on Temporal Correlation A limitation of server-side computation of basis matrices is that after the PS collects local model updates from all clients in iteration t, the extracted basis matrices can only be used for update compression in the subsequent iterations t + 1, t + 2, . . .. Consequently, such compression methods rely on the implicit assumption of temporal correlation, meaning that the subspace information extracted from earlier iterations can remain useful later. With weak temporal correlation, the basis matrix will fail to capture the model evolution in subsequent iterations, thus resulting in high compression distortion. D. Computational and Memory Overhead Using SVD or PCA for measuring correlation and designing compression schemes requires additional computations. For example, if we want to verify the degree of structural correlation before applying low-rank approximation to compress a model (t) update matrix Gk ∈ Rm×n , we only need to compute its singular values, and not the full SVD. If m ≥ n, computating singular values requiring O(2mn2 +2n3 ) FLOPS, compared to O(6mn2 + 20n3 ) FLOPS for the complete SVD [51, Section 8.6]. Computing PCA, especially for tall matrices with m ≫ n, by explicitly forming the covariance matrix may be inefficient. Instead, one can exploit the close relationship between PCA and SVD to obtain the principal components and singular values of the covariance matrix directly via an SVD [36]. Moreover, since PCA requires mean subtraction—incurring an additional cost of m(n + 1) FLOPS—it typically entails higher computational overhead than SVD. Memory overhead originates from the need to store previous model update information, such as in temporal-correlationaware compression design via predictive coding, which consumes storage resources. When the number of clients grows, this memory overhead may become a significant concern.

The main advantage of subspace projection as a compression method is the reduced communication cost. Instead of transmitting d (entire parameter vector) or m (one slice of the model update matrix) elements, only r elements need to be transmitted. However, the basis matrix is needed for both the clients and the PS to perform compression and decompression. Transmitting the basis matrix incurs additional communication cost, and the amount of extra communicated information depends on whether the clients or PS compute the basis matrices. When using clientside processing, the basis matrices are computed at each client and communicated to the PS, thus the communication cost grows linearly with the number of clients K. When using server-side processing, the basis matrices are computed at the PS and sent back to the clients, which can be done by broadcast. The break-even point in terms of the total number of communicated elements can be easily calculated for VII. A DAPTIVE C OMPRESSION D ESIGNS WITH M ULTIPLE each compression method. Consider an example where S OURCES OF C ORRELATION we use server-side processing and want to compress one (t) The three types of correlation may coexist in an FL system. model update slice of the model update matrix, gk,i , using Thus, an efficient compression design can benefit from jointly (t) (t) TruncSVD((g1,i , . . . , gK,i ), α), for some α. If we reuse Ur considering multiple sources of correlation. In this section, for j consecutive iterations, the total communication cost is we introduce two adaptive and context-aware compression (t) mr +rj, for transmitting Ur and UrT gk,i . Uncompressed model designs: AdaSVDFed in Section VII-A, an augmented version updates for the same number of iterations require transmitting of SVDFed, and PCAFed in Section VII-B, which can exploit mr jm elements. When mr + rj < jm ⇐⇒ j > m−r , reusing all three types of correlation when present and switch between the basis vectors over multiple iterations reduces the total different compression modes depending on the degree of communication cost. Nevertheless, this calculation ignores that measured correlation. compression will introduce distortion into the model updates, potentially affecting training performance. For example, suppose consecutive gradient iterates maintain A. AdaSVDFed a cosine similarity of at least c, so the angle between them is at We introduce AdaSVDFed in Algorithm 1, which switches most θ = arccos(c). After j iterations, the angle between g (t) between SVD-based and predictive-coding-based compression

8

Computed at the PS Measure spatial correlation using (t) MCorrPCA({gk }k∈[K] , βPF ) > αPF . Per agent processing, ∀k ∈ [K]

No

Measure temporal′ correlation using (t−t ) MCorrPCA({gk }t′ ∈[h] , βPF ) > αPF . No

Yes

Yes

Combined processing at PS

Measure temporal′ correlation using (t−t ) MCorrPCA({gk }t′ ∈[h],k∈[K] , βPF ) > αPF . No

Yes

sk = LocalPCA.

Measure structural′ correlation using (t−t ) MCorrPCA({gk,i }i∈[N ],t′ ∈[h] , βPF ) > αPF . No sk = PCA. Individual PCAs per slice.

Yes sk = PCA. One PCA for all slices.

Measure structural′ correlation using (t−t ) MCorrPCA({gk,i }i∈[N ],t′ ∈[h],k∈[K] , βPF ) > αPF . No sk = PCA, ∀k ∈ [K]. Individual PCAs per slice.

Yes sk = PCA, ∀k ∈ [K]. One PCA for all slices.

(t)

Figure 2. The flowchat describing the state selection process in PCAFedStateUpdate({gk }k=1,...,K , αPF , βPF ).

modes depending on the measured spatial correlation. Every Tu iterations, the algorithm enters an update state s = UPDATE, where the PS measures spatial correlation to decide whether SVDFed compression in [10] or predictive-coding compression in [15] will be used for the next Tu − 1 iterations. Specifically, the switching decision is governed by βSF ∈ [0, 1] and αSF ∈ [0, 1]: we set s = SPATIAL and use SVDFed compression (described in Section VI-A3) if no more than ⌈βSF · min{K, d}⌉ basis vectors are needed to capture at least (t) (t) a fraction αSF of the energy in (g1 , . . . , gK ). Otherwise, we set s = PRED to use the predictive-coding mode (described in Section IV-B), in which each client further compresses the prediction residual using C(·) : Rd → Rp (e.g., sparsification) and the PS reconstructs the vector via the reverse operation EXPAND(·) : Rp → Rd . The key advantage of AdaSVDFed is that it avoids transmitting the basis matrix Ur from the PS to the clients when the spatial correlation is low, thereby reducing downlink communication cost when the basis provides little compression benefit. Note that both SVD and predictive coding methods already exist in the literature. With this AdaSVDFed algorithm, our goal is to demonstrate that introducing an adaptive switching mechanism can improve existing compression designs, as shown in Section VIII through simulation results.

P correlations. Compute the mean µ = 1/|G| g′ ∈G g ′ ∈ Rp and the covariance X 1 C= (g ′ − µ)(g ′ − µ)T ∈ Rp×p . (20) |G| − 1 ′ g ∈G

We find the principal values λi , i = 1, . . . , p, from the eigenvalue decomposition C = QΛQT , where Λ = diag(λ1 , . . . , λp ) is the diagonal matrix of eigenvalues, ordered such that λ1 ≥ · · · ≥ λp ≥ 0, and Q ∈ Rp×p is an orthonormal matrix. To measure the degree of correlation using PCA, we consider the approximate energy ratio defined as Pr ∥µ∥22 + i=1 λi Pp αaer = . (21) ∥µ∥22 + i=1 λi

Then, using (21), we define a measurement function MCorrPCA(G, βpca ), where the inputs are: • a set of p-dimensional vectors G, and • a fraction βpca ∈ [0, 1], and the output is the approximate energy ratio αaer ∈ [0, 1] for r = ⌈βpca ·p⌉. This function provides an approximate method for quantifying the energy captured by a low-rank subspace. As an example, for a threshold αpca ∈ [0, 1], we consider correlation to be sufficient if MCorrPCA(G, βpca ) = αaer ≥ αpca . Using (21) also allows us to design a compression block TruncPCA(G, αpca ), which, given inputs B. PCAFed • a set of p-dimensional vectors G, and • a threshold αpca ∈ (0, 1], Until now, SVD has been the primary method considered for returns measuring and exploiting correlations. An alternative option p×r • the truncated Qr = Q:,1:r ∈ R , and is to use PCA, as discussed in Sections III-A and III-B. p • the mean µ ∈ R , Let G ′be a set of p-dimensional vectors, for instance, G = (t−t ) {gk,i }i∈[n],t′ ∈[h] with p = m, which contains all model where r is selected as the smallest integer such that update slices (with lenght m) of client k in multiple iterations. MCorrPCA(G, βpca ) ≥ αpca . Note that r = 0 is possible if In this way, we can jointly measure the temporal and structural the mean value contains enough energy. Using the mean vector

9

Algorithm 1: AdaSVDFed.

Algorithm 2: PCAFed.

1

Global state s ∈ {UPDATE, SPATIAL, PRED} Mk , MPS,k ← 0d×h , ∀k ∈ [K] 3 for t = 1, ..., T do 4 if t mod Tu = 1 then s ← UPDATE. (t) 5 Each client k computes local model update vector gk 6 if s = UPDATE then (t) 7 Each client transmits gk to the PS

1

2

2

Client states sk ∈ {UPDATE, PCA, LocalPCA} for t = 1, ... do 3 if t mod Tu = 1 then Set sk ← UPDATE, ∀k ∈ [K]. (t) 4 Each client k computes local model update vector gk // State: UPDATE

5 6

// Procedure at PS: 8 9 10

11 12 13 14 15 16 17 18 19 20 21

(t)

// Procedure at PS: (t)

G(t) ← (g1 , ..., gK ) if MCorrSVD(G(t) , βSF ) > αSF then PS gets Ur from TruncSVD(G(t) , αSF ) and broadcasts Ur to all clients s ← SPATIAL else (t) Each client stores mk ← gk (t) PS stores mPS,k ← gk , ∀k ∈ [K] s ← PRED (t)

(t)

gbk ← gk

23 24 25

else if s = PRED then for clients k = 1, ..., K do in parallel

27

28

8 9 10 11

13

(t)

15

19

20 21

(t)

(t)

Reconstruct gbk ← Mk ak + EXPAND(e rk )  (t)  Update memory: Mk ← gbk , [Mk ]:,:h−1 ,  (t)  MPS,k ← gbk , [Mk ]:,:h−1 PK (t) PS updates x(t+1) ← x(t) + k=1 wk gbk and transmits x(t+1) to all clients

(t)

(t)

gbk ← gk , ∀k ∈ [K]

else

for clients k where sk = PCA do in parallel for slice i = 1, ..., n do in parallel (t) (t) (t) (t) Client k transmits gek,i ← [Qk,i ]T (gk,i − µk,i ) to PS (t) (t) (t) PS reconstructs gbk,i ← Qk,i gek,i , ∀i ∈ [n] // State: LocalPCA

16

18

(t) (t) ak ← argmina ∥gk − Mk a∥ (t) (t) (t) rk ← gk − Mk ak (t) (t) rek ← C(rk ) (t) (t) Client k transmits ak and rek to PS

PS updates states sk using (t) PCAFedStateUpdate({gk }k=1,...,K , αPF , βPF ) for clients k where sk = PCA do (t) (t) PS transmits µk,i , Qk,i to client k, ∀i ∈ [n]

// State: PCA 12

17

// Both client k and PS: 26

7

14

else if s = SPATIAL then (t) (t) Each client transmits gek ← UrT gk to the PS (t) (t) PS reconstructs gbk ← Ur gek // Client k computes:

22

if sk = UPDATE for all k ∈ [K] then (t) Each client transmits gk to the PS

for clients k where sk = LocalPCA do in parallel (t) if MCorrPCA({gk,i }i∈[n] , βPF ) > αPF then (t) Client k computes Qk,r using (t) TruncPCA({gk,i }i∈[n] , αPF ) (t) (t) Client k transmits Qk,r , µk , and (t) (t) T (t) (t) gek,i ← [Qk,r ] (gk,i − µk ), ∀i ∈ [n] (t) (t) (t) (t) PS reconstructs gbk,i ← Qk,r gek,i + µk , ∀i ∈ [n] else // Insufficient exploitable correlation

22 23

24

(t)

Client k transmits gk to PS (t) (t) gbk ← gk PK (t) PS updates x(t+1) ← x(t) + k=1 wk gbk and transmits x(t+1) to all clients

correlation, the update mechanism sets sk = LocalPCA, which (t) µ and Qr , a client can compress a model update slice gk,i by requires no additional computations at the PS. A client in this applying (10), and the server decompresses it using (11). state applies PCA-based compression to its local model update We introduce PCAFed in Algorithm 2, an adaptive compres- each iteration if sufficient structural correlation is measured sion design that actively measures and exploits the three types within the update. In the presence of temporal correlation, the of correlation. Each client k has a state sk , k = 1, . . . , K, update method can exploit structural and/or spatial correlation, that determines the compression mode it currently uses. Every which correspond to the four cases that use s = PCA in k Tu iterations, the algorithm sets all clients to the update state (t) Figure 2. In all four cases, the PS computes the mean µk,i and sk = UPDATE, k = 1, . . . , K, to measure the degree of (t) correlation and apply the most suitable compression mode for the basis matrix Qk,i , but each case uses different information depending on the present correlation(s): the subsequent Tu − 1 iterations. (t) • Spatial and structural correlation: Let PCAFedStateUpdate({gk }k=1,...,K , αPF , βPF ) be the Collect n model update slices from K clients in h mechanism that the PS uses to update the compression mode for iterations. Compute one PCA to obtain µ(t) , Q(t) = all clients, where αPF ∈ [0, 1] and βPF ∈ [0, 1]. To do so, the (t−t′ ) TruncPCA({gk,i }i∈[n],t′ ∈[h],k∈[K] , αPF ), and assign PS measures correlation according to the flowchart in Figure 2 (t) (t) to decide the next state of each client. In the absence of temporal µk,i = µ(t) , Qk,i = Q(t) , ∀i ∈ [n], ∀k ∈ [K].

10

10 1 m=IO, n=HW m=IHW, n=O m=IH, n=OW

10 2

I=128, O=128, H=3, W=3

10 1 m=IO, n=HW m=IHW, n=O m=IH, n=OW

10 2

0 10000200003000040000 # trans. elem.

0

(a) layer1.1.conv2 (5th)

100

50000 100000 150000 # trans. elem.

(b) layer2.1.conv2 (9th)

I=256, O=256, H=3, W=3

10 1 m=IO, n=HW m=IHW, n=O m=IH, n=OW

10 2 0

200000 400000 600000 # trans. elem.

(c) layer3.1.conv2 (13th)

100 Normalized MSE

100

Normalized MSE

I=64, O=64, H=3, W=3 Normalized MSE

Normalized MSE

100

I=512, O=512, H=3, W=3 m=IO, n=HW m=IHW, n=O m=IH, n=OW

10 1 10 2 0

1 2 # trans. elem.

1e6

(d) layer4.1.conv2 (17th)

1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2

Temporal IID

Structural Non-IID

Correlation

Correlation

b (100) ∈ Rm×n for different ResNet18 layers (total depth: 18), and their depth in the Figure 3. Normalized MSE of the model update matrix approximation G network, as a function of the number of transmitted elements over the client-to-PS link. When min(m, n) is small, the number of possible choices is limited, and we explicitly mark the attainable points in these cases. The vertical gray dotted line marks mn = IOHW transmitted elements (number of elements without compression). τ = 32, γ = 0.001.

0

10

20

30 40 50 Iteration

(a) LeNet.

60

70

1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2

Spatial

mentation, it serves as an example to illustrate how correlationawareness can be incorporated into the compression design. VIII. N UMERICAL E XPERIMENTS

0

50

100 Iteration

150

200

(b) ResNet.

Figure 4. Measured correlation during training across all layers, where each layer’s influence is proportional to its number of parameters. Under the non-IID setting, each client holds at most 4 of 10 labels. We measure (t) structural correlation by MCorrPCA({gk,i }i∈[n] , 0.2), temporal correlation (t−t′ )

by MCorrPCA({gk }t′ =0,...,4 , 0.2), which is averaged over the K = 20 (t) clients. Spatial correlations are measured as MCorrPCA({gk }k∈[K] , 0.2). The results are averaged over 10 runs, and the fill shows ± one standard deviation. τ = 32, γ = 0.001.

Spatial correlation: Collect one model update slice from K clients in h iterations. Compute n PCAs (one for each slice) to obtain (t) (t) (t−t′ ) µi , Qi = TruncPCA({gk,i }t′ ∈[h],k∈[K] , αPF ), ∀i ∈ (t) (t) (t) (t) [n], and assign µk,i = µi , Qk,i = Qi , ∀i ∈ [n], ∀k ∈ [K]. • Structural correlation: Collect n model update slices from one client in h iterations. Compute K PCAs (one ′for each client) to (t) (t) (t−t ) obtain µk , Qk = TruncPCA({gk,i }i∈[n],t′ ∈[h] , αPF ), (t) (t) (t) (t) ∀k ∈ [K], and assign µk,i = µk , Qk,i = Qk , ∀i ∈ [n], ∀k ∈ [K]. • Only temporal correlation: Collect one model update slice from one client in h (t) (t) iterations. Compute nK PCAs to obtain µk,i , Qk,i = •

(t−t′ )

TruncPCA({gk,i

}t′ ∈[h] , αPF ), ∀i ∈ [n], ∀k ∈ [K].

The PS then transmits the corresponding mean vector(s) and basis matrix (matrices) to each client k with sk = PCA. Remark VII.1. One drawback of this algorithm is the high computational complexity. While impractical in any real imple-

In this section, we present simulation results to quantify the degrees of structural, temporal, and spatial correlations, using the metrics discussed in the previous sections.3 We consider three learning tasks with different learning models: • A binary classification task, using a linear model fitted via logistic regression. Each data sample (ξi , yi ) ∈ Rd × {−1, 1} is a feature-label pair, and the sample-wise loss T ℓ(x; (ξi , yi )) = log(1 + e−yi ξi x ). We use the w8a dataset from [52], which contains 49 749 samples with d = 300 features. • An image classification task on the MNIST dataset [53], which has 50 000 training samples, using a small convolutional neural network LeNet [54], with 44 426 trainable parameters. • An image classification task on the CIFAR10 dataset [55], which has 50 000 training samples, using a larger convolutional neural network ResNet18 [56], with 11 181 642 trainable parameters. The training data samples are evenly distributed among the clients in the system. We examine both IID settings, in which each client possesses an equal share of all class labels, and non-IID settings, where clients hold a subset of available classes. Each client applies mini-batch stochastic gradient decent (SGD) (t,i) and adapts the batch size |Dk | based on the number of (t,i) local SGD steps τ such that |Dk | · τ = |Dk |. For the image classification tasks, we apply heavy-ball momentum with parameter 0.9 in the local SGD steps, and a weight decay of factor 10−4 . For learning models whose parameters naturally divide into layers, e.g., the layers of a neural network, we apply compression independently to each such layer. To identify where the largest gains can be achieved by introducing redundancy-based compression, we focus on layers that account for a significant portion of the total parameters. For the LeNet model trained on the MNIST dataset, we consider the fully connected layer 3 The code will be publicly available after the review process.

1

1

250

38

100

25

750 1000

250 500 750 1000 Iteration

Iteration

Iteration

150

1

38

200 300 1

100 200 300 400 Iteration

200 300 400

75 112 150 Iteration

(a) Linear model. Left: τ = 1, γ = 0.01. Right: τ = 32, γ = 0.0025

100

400

112

1

1

25

100 Iteration

1

1

75

50 75 100

1

25

(c) ResNet18, layer: layer4.0.conv1. Left: τ = 1, γ = 0.01. Right: τ = 32, γ = 0.001

100 200 300 400 Iteration

1.0

50

0.8

75 100

1

25

50 75 100 Iteration

(b) LeNet, layer: fc1. Left: τ = 1, γ = 0.05. Right: τ = 32, γ = 0.001

1

0.6

0.4

25

200 300 400

50 75 100 Iteration

1

Iteration

500

Iteration

1 Iteration

1 Iteration

Iteration

11

1

100 200 300 400 Iteration

50

0.2

75 100

1

25

50 75 100 Iteration

0.0

(d) ResNet18, layer: layer4.0.conv2. Left: τ = 1, γ = 0.01. Right: τ = 32, γ = 0.001

Figure 5. Temporal correlation between model updates over time evaluated using |CSS(g (t1 ) , g (t2 ) )|.

fc1, with shape [256, 120], as it contains approximately 70% of the model’s parameters. For the ResNet18 model trained on the CIFAR-10 dataset, we focus on the convolutional layers layer4.0.conv1, with shape [256, 512, 3, 3], and layer4.0.conv2, with shape [512, 512, 3, 3], which account for approximately 11% and 21% of the total parameters, respectively. A. Correlation Evolution Figure 4 shows how the correlation strength evolves during training with K = 20 clients. The results indicate that the correlation varies over time and depends on both the model architecture and the data distribution. In Figure 4a, we see that after an initial phase with high correlation, the IID scenario experiences a substantial decline in spatial correlation and a minor drop in temporal correlation during the later part of training. While initially weaker, the non-IID setting maintains a more stable spatial correlation. Meanwhile, Figure 4b shows that the structural correlation is strong regardless of data distribution, while the degree of temporal and spatial correlation is larger in the non-IID setting. B. Impact of Parameter Reshaping on Structural Correlation The structural correlation measures in Figure 4 are for one specific mapping from convolutional kernel to model update matrix, that is, n = OH and m = IW . In Figure 3, we explore different mappings—choosing m and n as various combinations of O, I, H, and W —and compare b (t) reconstructed how the MSE of the low-rank approximation G at the PS varies with the number of transmitted elements. We present four convolutional layers from different depths in the ResNet18 model: layer1.1.conv2 (5th layer), layer2.1.conv2 (9th layer), layer3.1.conv2 (13th layer), and layer4.1.conv2 (17th layer), in Figures 3a to 3d, respectively. We find that no

single mapping is optimal across all layers, assigning I and O to different axes generally yields a lower MSE for the same number of transmitted elements. C. Impact of Multiple Local Steps on Temporal Correlation We use cosine similarity to measure the strength of temporal correlation at a single client when using different numbers of local SGD steps across three learning tasks. For the linear model in (Figure 5a), a high degree of temporal correlation is observed for both small (τ = 1) and large (τ = 32) numbers of local steps. From Figure 5b, we observe strong temporal correlation during two distinct phases of the LeNet training process. However, for ResNet18 (Figures 5c and 5d), the correlation diminishes as the number of local steps increases. These results suggest that the model update trajectory can be more complex for certain models and datasets, resulting in weaker temporal correlation. D. State Evolution In Figure 6, we illustrate how the system switches between different states and compression modes when implementing Algorithms 1 and 2. When training LeNet under an IID data distribution, we find that in the early iterations, both AdaSVDFed and PCAFed tend to select compression modes that exploit multiple sources of correlation (e.g., spatial+temporal or spatial+temporal+structural). In the non-IID case, both algorithms use compression modes less frequently that rely less on spatial correlation. However, for ResNet18, the state selection is hindered by the weaker temporal correlation seen in Figures 4b and 5, especially for the IID case, which limits how often both algorithms can exploit multiple correlations simultaneously. For AdaSVDFed in Figure 6c, the results reveal heavy use of the predictive coding mode, where a prediction and a compressed

0.6 0.4 0.2 0.0

0

20

40 Iteration

60

0.8 0.6 0.4 0.2 0.0

0

20

40 Iteration

60

Spatial+Temporal Spatial+Temporal+Structural 1.0

0.8 0.6 0.4 0.2 0.0

0.8 0.6 0.4 0.2 0.0

0

25

50

75 100 125 150 Iteration

Update Proportion of parameters

Proportion of parameters

Proportion of parameters

1.0

Prediction 1.0 0.8 0.6 0.4 0.2 0.0

0

25

50

0

20

40 Iteration

60

Structural No compression

Update

20

60

0.8 0.6 0.4 0.2 0.0

0

40 Iteration

(b) LeNet, using PCAFed. IID to the left and non-IID to the right.

(a) LeNet, using AdaSVDFed. IID to the left and non-IID to the right.

Spatial

Temporal Temporal+Structural 1.0

Proportion of parameters

0.8

Update

75 100 125 150 Iteration

(c) Resnet18, using AdaSVDFed. IID to the left and non-IID to the right.

Spatial+Temporal Spatial+Temporal+Structural 1.0

Temporal Temporal+Structural 1.0

0.8 0.6 0.4 0.2 0.0

0

25

50

75 100 125 150 Iteration

Proportion of parameters

1.0

Prediction 1.0

Proportion of parameters

Spatial

Proportion of parameters

Proportion of parameters

12

Structural No compression

Update

0.8 0.6 0.4 0.2 0.0

0

25

50

75 100 125 150 Iteration

(d) Resnet18, using PCAFed. IID to the left and non-IID to the right.

Figure 6. Proportion of parameters operating under each state during training, averaged across K = 20 clients. Under the non-IID setting, each client holds at most 4 of 10 labels. The “No compression” reported for PCAFed is when the system is in LocalPCA, but insufficient structural correlations are found, so the raw update is transmitted. α = 0.8, β = 0.2, τ = 32, γ = 0.001. The results are average over 10 runs.

Baseline

1.0

PCAFed

AdaSVDFed

0.65 0.60 0.55

0.8

Accuracy

Accuracy

0.9

0.7

0.50 0.45 0.40

0.6 0.5

SVDFed

0.35 0

20

40 60 80 100 Transmitted elements (·10 )

(a) LeNet.

120

0.30

0

10

20 30 40 50 Transmitted elements (·10 )

60

(b) ResNet.

Figure 7. Training performance versus total number of transmitted elements for non-IID data distribution. Under the non-IID setting, each client holds at most 4 of 10 labels. The results are average over 10 runs, and the fill shows ± one standard deviation. τ = 32, γ = 0.001.

residual are transmitted. For PCAFed in Figure 6d, the results indicate that LocalPCA is used most frequently, where raw model updates are transmitted due to a lack of correlation. In contrast, the slightly stronger temporal correlation in the nonIID scenario is sufficient to enable joint exploitation of spatial and temporal correlations. In the early iterations in Figure 4b, we see a spike in temporal correlation, which is believed to cause the temporary use of temporal correlation in Figure 6d. E. End-to-End Training Performance of Context-Aware Adaptive Compression Design At last, we compare the training performance of Algorithms 1 and 2 to a baseline without compression and SVDFed.4 We apply per-layer compression, and fix the update frequency Tu = 3. For AdaSVDFed, we use h = 5, αSF = 0.8, βSF = 0.2, and let C(·) be a Top-5% compression operator, i.e., preserving 4 we consider a simplified version of SVDFed with periodic updating of the subspace-defining matrix.

the 5% elements with largest magnitude (rounded up to the nearest integer). For PCAFed, we use h = 5, αPF = 0.8 and βPF = 0.2. We note that the parameters have not been fine-tuned and may not be optimal for performance. Finding optimal parameters for the compression schemes is outside the scope of this paper and is left for future work. Generally, we see in Table II that all compression schemes reduce the number of elements in the client-to-PS links, at the cost of transmitting more elements in the PS-to-client direction. In some cases, the PS-to-client transmission accounts for the majority of the total communication cost. The PCAFed scheme shows strong performance on the tasks at hand, and its savings relative to other schemes can be attributed to its ability to adapt to changing correlations during training. In the scenario with stronger correlations (i.e., when training LeNet), we observe comparable iteration complexity. For the larger model (i.e., ResNet18), the iteration complexity increases slightly, but the increase is less pronounced than for the other schemes. Comparing the number of transmitted elements between SVDFed and AdaSVDFed demonstrates the potential benefit of adaptive designs: in all cases where spatial correlation is weak, we observe a significant reduction in the number of communicated elements in the PS-to-client link. We also observe a significant increase in iteration complexity for SVDFed when temporal correlation is weak, e.g., when training ResNet18. IX. C ONCLUSION AND F UTURE W ORK We categorize three types of correlation: structural, temporal, and spatial, which are inherent in FL algorithms. Using unified terminology and notations, we also describe several correlationexploiting schemes for compressing local model updates in the literature and clarify their underlying design principles.

13

Table II T RAINING PERFORMANCE OF A LGORITHMS 1 AND 2 COMPARED TO SVDF ED WITH FIXED UPDATE INTERVAL Tu , AND A BASELINE WITHOUT COMPRESSION . U NDER THE NON -IID SETTING , EACH CLIENT HOLDS AT MOST 4 OF 10 LABELS . T HE REPORTED VALUES ARE AVERAGED OVER 10 RUNS . τ = 32, γ = 0.001, K = 20. Model

LeNet LeNet

# Trans. Elem. (PS → Agents)

50 52 53 67

44.07 · 106 17.74 · 106 16.67 · 106 19.78 · 106

44.07 · 106 32.91 · 106 42.39 · 106 39.55 · 106

88.14 · 106 50.65 · 106 59.05 · 106 59.33 · 106

— TS = 3 TS = 3 TS = 3

43 47 43 86

38.30 · 106 15.08 · 106 13.95 · 106 25.89 · 106

38.30 · 106 35.33 · 106 48.98 · 106 53.04 · 106

76.59 · 106 50.42 · 106 62.93 · 106 78.93 · 106

None PCAFed AdaSVDFed SVDFed

— TS = 3 TS = 3 TS = 3

87 105 122 185

19.41 · 109 10.74 · 109 10.07 · 109 13.90 · 109

19.41 · 109 23.52 · 109 27.19 · 109 67.52 · 109

38.81 · 109 34.26 · 109 37.27 · 109 81.42 · 109

None PCAFed AdaSVDFed SVDFed

— TS = 3 TS = 3 TS = 3

81 104 111 202

18.20 · 109 9.85 · 109 9.16 · 109 15.11 · 109

18.20 · 109 23.28 · 109 24.80 · 109 54.72 · 109

36.39 · 109 33.13 · 109 33.97 · 109 69.83 · 109

Compression Method

Update Freq.

# Iter.

MNIST, IID

None PCAFed AdaSVDFed SVDFed

— TS = 3 TS = 3 TS = 3

None PCAFed AdaSVDFed SVDFed

Until reaching 95% validation accuracy

MNIST, non-IID Until reaching 90% validation accuracy

CIFAR10, IID ResNet18

# Trans. Elem. (Agents → PS)

Dataset, Distr.

Until reaching 65% validation accuracy

CIFAR10, non-IID Until reaching 55% validation accuracy

We present numerical examples demonstrating that significant correlations can emerge in certain scenarios and can be leveraged to develop more efficient compression designs. These correlations vary across learning tasks and among different components (e.g., layers of a neural network) of the learned model. Therefore, it is necessary to measure the degree of correlation (either locally or centrally) and adapt compression strategies to the correlation structures of the model components. We design two adaptive compression algorithms that dynamically switch between different correlation-exploiting modes: one that augments an existing design with a dynamic switching mechanism, and another that can jointly exploit structural, temporal, and spatial correlations when present. Through numerical experiments, we demonstrate that these adaptive algorithms outperform their non-adaptive counterparts in terms of communication cost. We leave the search for optimal hyperparameters and the further development of optimized, scalable, and correlation-centric designs for future work. Several other aspects remain to be investigated further, such as considering compression optimized for metrics other than MSE, exploring connections between commonly used bounds and our correlation measurement, and examining the effects of additional algorithmic add-ons (e.g., error compensation). R EFERENCES [1] [2] [3]

[4]

J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh and D. Bacon, “Federated learning: Strategies for improving communication efficiency”, arXiv preprint arXiv:1610.05492, 2016. Y. J. Cho, J. Wang and G. Joshi, “Towards understanding biased client selection in federated learning”, in International Conference on Artificial Intelligence and Statistics, 2022, pp. 10 351–10 375. H. Ko, J. Lee, S. Seo, S. Pack and V. C. M. Leung, “Joint client selection and bandwidth allocation algorithm for federated learning”, IEEE Transactions on Mobile Computing, vol. 22, no. 6, pp. 3380–3390, 2023. T. Chen, G. Giannakis, T. Sun and W. Yin, “LAG: Lazily aggregated gradient for communication-efficient distributed learning”, in Advances in Neural Information Processing Systems, vol. 31, 2018, pp. 5050– 5060.

[5]

[6] [7]

[8] [9]

[10]

[11] [12] [13] [14] [15]

[16] [17]

[18]

# Total Trans. Elem.

Y. Xu, Z. Jiang, H. Xu, Z. Wang, C. Qian and C. Qiao, “Federated learning with client selection and gradient compression in heterogeneous edge systems”, IEEE Transactions on Mobile Computing, vol. 23, no. 5, pp. 5446–5461, 2024. S. U. Stich, “Local SGD converges fast and communicates little”, in International Conference on Learning Representations, 2019, pp. 3514– 3530. D. Alistarh, D. Grubic, J. Li, R. Tomioka and M. Vojnovic, “QSGD: Communication-efficient SGD via gradient quantization and encoding”, in Advances in Neural Information Processing Systems, vol. 30, 2017, pp. 1709–1720. J. Wangni, J. Wang, J. Liu and T. Zhang, “Gradient sparsification for communication-efficient distributed optimization”, in Advances in Neural Information Processing Systems, vol. 31, 2018, pp. 1299–1309. H. Wang, S. Sievert, S. Liu, Z. Charles, D. Papailiopoulos and S. Wright, “ATOMO: Communication-efficient learning via atomic sparsification”, in Advances in Neural Information Processing Systems, vol. 31, 2018, pp. 9850–9861. H. Wang, X. Liu, J. Niu and S. Tang, “SVDFed: Enabling communication-efficient federated learning via singular-valuedecomposition”, in IEEE International Conference on Computer Communications, May 2023, pp. 1–10. S. S. Azam, S. Hosseinalipour, Q. Qiu and C. Brinton, “Recycling model updates in federated learning: Are gradient subspaces low-rank?”, in International Conference on Learning Representations, 2022. P. Richtarik, I. Sokolov and I. Fatkhullin, “EF21: A new, simpler, theoretically better, and practically faster error feedback”, in Advances in Neural Information Processing Systems, vol. 34, 2021, pp. 4384–4396. K. Sayood, Introduction to Data Compression. Morgan Kaufmann, 2018. K. Yue, R. Jin, C.-W. Wong and H. Dai, “Communication-efficient federated learning via predictive coding”, IEEE Journal of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 369–380, Apr. 2022. A. Edin, Z. Chen, M. Kieffer and M. Johansson, “Temporal predictive coding for gradient compression in distributed learning”, in 60th Annual Allerton Conference on Communication, Control, and Computing, Sep. 2024. T. B. Adikari and S. C. Draper, “Compressing gradients by exploiting temporal correlation in momentum-SGD”, IEEE Journal on Selected Areas in Information Theory, vol. 2, no. 3, pp. 970–986, Sep. 2021. S. Park and W. Choi, “Regulated subspace projection based local model update compression for communication-efficient federated learning”, IEEE Journal on Selected Areas in Communications, vol. 41, no. 4, pp. 964–976, 2023. J. Zhang, Y. Xu and K. Yuan, “An efficient subspace algorithm for federated learning on heterogeneous data”, arXiv preprint arXiv:2509.05213, 2025.

14

[19]

[20]

[21]

[22]

[23]

[24] [25] [26]

[27]

[28] [29] [30] [31]

[32] [33] [34] [35]

[36] [37] [38] [39] [40] [41]

Y. Han, X. Li, S. Lin and Z. Zhang, “A random projection approach to personalized federated learning: Enhancing communication efficiency, robustness, and fairness”, Journal of Machine Learning Research, vol. 25, no. 380, pp. 1–88, 2024. B. McMahan, E. Moore, D. Ramage, S. Hampson and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data”, in International Conference on Artificial Intelligence and Statistics, PMLR, Apr. 2017, pp. 1273–1282. S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich and A. T. Suresh, “SCAFFOLD: Stochastic controlled averaging for federated learning”, in Proceedings of the 37th International Conference on Machine Learning, 2020, pp. 5132–5143. H. Zhao, K. Burlachenko, Z. Li and P. Richtárik, “Faster rates for compressed federated learning with client-variance reduction”, SIAM Journal on Mathematics of Data Science, vol. 6, no. 1, pp. 154–175, 2024. W. Liu, L. Chen, Y. Chen and W. Zhang, “Accelerating federated learning via momentum gradient descent”, IEEE Transactions on Parallel and Distributed Systems, vol. 31, no. 8, pp. 1754–1766, Aug. 2020. T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar and V. Smith, “Federated optimization in heterogeneous networks”, Proceedings of Machine learning and systems, vol. 2, pp. 429–450, 2020. Y. Xue, L. Su and V. K. N. Lau, “FedOComp: Two-timescale online gradient compression for over-the-air federated learning”, IEEE Internet of Things Journal, vol. 9, no. 19, pp. 19 330–19 345, Oct. 2022. M. Yu, Z. Lin, K. Narra et al., “GradiVeQ: Vector quantization for bandwidth-efficient gradient aggregation in distributed CNN training”, in Advances in Neural Information Processing Systems, vol. 31, 2018, pp. 5123–5133. L. Abrahamyan, Y. Chen, G. Bekoulis and N. Deligiannis, “Learned Gradient Compression for Distributed Deep Learning”, IEEE Transactions on Neural Networks and Learning Systems, vol. 33, no. 12, pp. 7330–7344, Dec. 2022. C. Zhang, S. Bengio, M. Hardt, B. Recht and O. Vinyals, “Understanding deep learning requires rethinking generalization”, in International Conference on Learning Representations, 2017, pp. 3001–3015. G. Gur-Ari, D. A. Roberts and E. Dyer, “Gradient descent happens in a tiny subspace”, arXiv preprint arXiv:1812.04754, 2018. R. Cosson, A. Jadbabaie, A. Makur, A. Reisizadeh and D. Shah, “Lowrank gradient descent”, IEEE Open Journal of Control Systems, vol. 2, pp. 380–395, 2023. T. Li, L. Tan, Z. Huang, Q. Tao, Y. Liu and X. Huang, “Low dimensional trajectory hypothesis is true: DNNs can be trained in tiny subspaces”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 45, no. 3, pp. 3411–3420, Mar. 2023. L. Sagun, U. Evci, V. U. Guney, Y. Dauphin and L. Bottou, “Empirical analysis of the hessian of over-parametrized neural networks”, arXiv preprint arXiv:1706.04454, 2017. A. Ansuini, A. Laio, J. H. Macke and D. Zoccolan, “Intrinsic dimension of data representations in deep neural networks”, in Advances in Neural Information Processing Systems, vol. 32, 2019, pp. 6111–6122. C. Li, H. Farkhoor, R. Liu and J. Yosinski, “Measuring the intrinsic dimension of objective landscapes”, in International Conference on Learning Representations, 2018, pp. 1764–1787. T. Vogels, S. P. Karimireddy and M. Jaggi, “PowerSGD: Practical lowrank gradient compression for distributed optimization”, in Advances in Neural Information Processing Systems, vol. 32, 2019, pp. 14 259– 14 268. J. J. Gerbrands, “On the relationships between SVD, KLT and PCA”, Pattern recognition, vol. 14, no. 1-6, pp. 375–381, 1981. D. Salomon and G. Motta, Handbook of data compression. Springer Science & Business Media, 2010. K. Mishchenko, E. Gorbunov, M. Takáč and P. Richtárik, “Distributed learning with compressed gradient differences”, Optimization Methods and Software, pp. 1–16, Sep. 2024. Y. Chen, R. S. Blum, M. Takáč and B. M. Sadler, “Distributed learning with sparsified gradient differences”, IEEE Journal of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 585–600, Apr. 2022. T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar and V. Smith, “Federated optimization in heterogeneous networks”, in Proceedings of Machine Learning and Systems, vol. 2, 2020, pp. 429–450. X. Li, K. Huang, W. Yang, S. Wang and Z. Zhang, “On the convergence of FedAvg on non-IID data”, in International Conference on Learning Representations, 2020, pp. 13 431–13 456.

[42] [43] [44] [45] [46]

[47]

[48] [49] [50]

[51] [52] [53] [54] [55] [56]

O. Roy and M. Vetterli, “The effective rank: A measure of effective dimensionality”, in 15th European Signal Processing Conference, Sep. 2007, pp. 606–610. D. Rothchild, A. Panda, E. Ullah et al., “FetchSGD: Communicationefficient federated learning with sketching”, in Proceedings of the 37th International Conference on Machine Learning, 2020, pp. 8253–8265. M. Alimohammadi, I. Markov, E. Frantar and D. Alistarh, L-GreCo: Layerwise-adaptive gradient compression for efficient and accurate deep learning, 2023. arXiv: 2210.17357 [cs.LG]. E. Ozfatura, K. Ozfatura and D. Gündüz, “Time-correlated sparsification for communication-efficient federated learning”, in 2021 IEEE International Symposium on Information Theory (ISIT), 2021, pp. 461–466. Y. Sun, S. Zhou, Z. Niu and D. Gündüz, “Time-correlated sparsification for efficient over-the-air model aggregation in wireless federated learning”, in IEEE International Conference on Communications (ICC), 2022, pp. 3388–3393. A. V. Makkuva, M. Bondaschi, T. Vogels, M. Jaggi, H. Kim and M. Gastpar, “LASER: Linear compression in wireless distributed optimization”, in Proceedings of the 41st International Conference on Machine Learning, 2024, pp. 34 383–34 416. N. Hyeon-Woo, M. Ye-Bin and T.-H. Oh, “Fedpara: Low-rank hadamard product for communication-efficient federated learning”, arXiv preprint arXiv:2108.06098, 2021. Y. Hao, Y. Cao and L. Mou, “Flora: Low-rank adapters are secretly gradient compressors”, in Proceedings of the 41st International Conference on Machine Learning, 2024, pp. 17 554–17 571. J. Zhao, Z. Zhang, B. Chen, Z. Wang, A. Anandkumar and Y. Tian, “GaLore: Memory-efficient LLM training by gradient low-rank projection”, in Proceedings of the 41st International Conference on Machine Learning, 2024, pp. 61 121–61 143. G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed. Johns Hopkins University Press, 2013. C.-C. Chang and C.-J. Lin, “LIBSVM: A library for support vector machines”, ACM Transactions on Intelligent Systems and Technology, 2011. Y. LeCun, C. Cortes and C. Burges, “MNIST handwritten digit database”, ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist, vol. 2, 2010. Y. LeCun, L. Bottou, Y. Bengio and P. Haffner, “Gradient-based learning applied to document recognition”, Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, Nov. 1998. A. Krizhevsky, G. Hinton et al., “Learning multiple layers of features from tiny images”, 2009. K. He, X. Zhang, S. Ren and J. Sun, “Deep residual learning for image recognition”, in IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.