{'fraction_non_alphanumeric': 0.038514012847478823, 'fraction_numerical': 0.00972087999545222, 'mean_word_length': 4.310641509433962, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
FedVQCS: Federated Learning via Vector Quantized Compressed Sensing

In this paper, a new communication-efficient federated learning (FL) framework is proposed, inspired by vector quantized compressed sensing. The basic strategy of the proposed framework is to compress the local model update at each device by applying dimensionality reduction followed by vector quantization. Subsequently, the global model update is reconstructed at a parameter server by applying a sparse signal recovery algorithm to the aggregation of the compressed local model updates. By harnessing the benefits of both dimensionality reduction and vector quantization, the proposed framework effectively reduces the communication overhead of local update transmissions. Both the design of the vector quantizer and the key parameters for the compression are optimized so as to minimize the reconstruction error of the global model update under the constraint of wireless link capacity. By considering the reconstruction error, the convergence rate of the proposed framework is also analyzed for a non-convex loss function. Simulation results on the MNIST and CIFAR-10 datasets demonstrate that the proposed framework provides more than a 2.5% increase in classification accuracy compared to state-of-the-art FL frameworks when the communication overhead of the local model update transmission is less than 0.1 bit per local model entry.

• We present a communication-efficient FL framework via vector quantized compressed sensing (VQCS), dubbed FedVQCS. In this framework, we compress each local model update by reducing its dimensionality based on CS and, then, quantizing a low-dimensional local model update by using a vector quantizer. For accurate but efficient reconstruction of the global model update at the PS, we aggregate a group of the compressed local model updates and, then, estimate the aggregated model update by applying a sparse signal recovery algorithm. By harnessing the benefits of both dimensionality reduction and vector quantization, FedVQCS significantly reduces the communication overhead required for transmitting the local model updates at the wireless devices. • We optimize the design of the vector quantizer used for the local update compression strategy of FedVQCS. A key feature of our compression strategy is that the local model update after the CS-based dimensionality reduction can be modeled as an independent and identically distributed (IID) Gaussian random vector by the central limit theorem. By utilizing this feature, we derive the optimal shape and gain quantizers for an IID Gaussian random vector based on the Lloyd-Max algorithm [25] and Grassmanian codebook [26], respectively. We also derive the optimal bit allocation between the shape and gain quantizers by characterizing the mean-squared-error (MSE) performance of these quantizers. • We optimize the key design parameters of the local update compression strategy of Fed-VQCS, that include: (i) the number of quantization bits, (ii) sparsity level, and (iii) dimensionality reduction ratio. In particular, we determine the best set of these parameters for minimizing reconstruction error of the global model update at the PS under a capacity constraint. A prominent feature of our parameter optimization is that it can be performed locally at each device without information exchange among the devices. Our analysis also shows that the upper bound of the convergence rate decreases as the MSE of the global model update reconstructed at the PS reduces, implying that our parameter optimization contributes to improving the convergence rate of FL.
• Using simulations, we demonstrate the superiority of FedVQCS over state-of-the-art FL frameworks for an image classification task using the MNIST dataset [27] and the CIFAR-10 dataset [28]. Our simulation results demonstrate that FedVQCS provides more than a 2.5% increase in classification accuracy compared to the state-of-the-art FL frameworks when the communication overhead of the local model update transmission is less than 0.1 bit per local model entry. Meanwhile, the results on the MNIST dataset demonstrate that FedVQCS with a 0.1-bit overhead per local model entry yields only a 2% decrease in classification accuracy when compared with the case that performs no local update compression. The effectiveness of the parameter optimization of FedVQCS is also verified in terms of classification accuracy.

II. SYSTEM MODEL
Consider a wireless FL system in which a PS trains a global model by collaborating with a set K of K wireless devices over wireless links with limited capacity. The data samples for training the global model are assumed to be distributed over the wireless devices only, while the PS does not have direct access to them. Let D k be the local training dataset available at device k ∈ K. The global model at the PS is assumed to be represented by a parameter vector w ∈ RN , whereN is the number of global model parameters. The goal of FL is to find the best parameter vector that minimizes the global loss function, defined as where f (w; u) is a loss function that measures how well the global model with the parameter vector w fits one particular data sample u ∈ D k , and D = ∪ k D k . The global loss function in (1) can be rewritten as where F k (w) = 1 is a local loss function at device k.

A. A Typical FL Framework
A typical FL approach for minimizing the global loss function in (2) involves alternating between local model update at wireless devices and global model update at the PS in each communication round, as explained in [2]. Assume that every device employs a mini-batch SGD algorithm with E ≥ 1 local iterations for updating the parameter vector w (t) . Then the updated parameter vector at device k after E ≥ 1 local iterations is given by where w and D (t,e) k is a mini-batch randomly drawn from D k at the e-th local iteration of round t. As a result, the local model update sent by device k in round t is determined as is invariant in each communication round. If the PS employs the SGD algorithm for updating the parameter vector w (t) , then the updated parameter vector in round t will be given by where γ (t) is a global learning rate. Then the PS broadcasts w (t+1) to the wireless devices, which triggers the start of the local model update process in round t + 1.

A. Overview of FedVQCS
The basic strategy of FedVQCS is to compress the local model updates at the wireless devices by leveraging both vector quantization and CS-based dimensionality reduction while reconstructing the global model update at the PS via sparse signal recovery. The high-level procedure of FedVQCS is illustrated in Fig. 1 and described below.

1) Compression of the local model updates:
In each communication round, each device divides its local model update into B blocks, each of which has a length of N =N B . Let g k , and we refer to this vector as the b-th local block update of device k in round t. Each device compresses these B local block updates in parallel by applying a local block compression process denoted by a function BlkComp(·). The motivation behind this block-wise compression is to reduce the computational complexity for reconstructing the global model update at the PS, as considered in [18]. The compressed local block updates are encoded into digital bits and then transmitted to the PS through wireless links.
determined by the global block reconstruction process.

3) Summary:
The overall procedures of FedVQCS are summarized in Procedure 1, while the local block compression and global block reconstruction processes are summarized in Procedure 2 and Procedure 3, respectively. In the remainder of this section, we elaborate more on the local block compression process (see Sec. III-B) and the global block reconstruction process (see Sec. III-C). In the subsequent section, we will explain how to design a vector quantizer for the local block compression process (see Sec. IV-A) and how to optimize the design parameters of this compression process (see Sec. IV-B). We will also analyze the convergence rate of FedVQCS in Sec. IV-C. Finally, we will demonstrate the superiority of FedVQCS over the existing FL frameworks in Sec. V.

Procedure 1 Federated Learning via Vector
Quantized Compressed Sensing (FedVQCS) Output: w T 1: for t = 1 to T do 2: At the wireless devices: 3: for Each device k ∈ K do in parallel 4: for Each block b ∈ B do in parallel 6: to the PS.

9:
end 10: At the parameter server: 11: for Each block b ∈ B do in parallel

B. Compression of Local Block Update
The local block compression process of FedVQCS consists of three steps: (i) sparsification, (ii) dimensionality reduction, and (iii) vector quantization, as summarized in Procedure 2. The details of each step performed by device k for block b in round t are elaborated below.

1) Sparsification:
In the sparsification step, each local block update is sparsified by nullifying all but the most significant S k entries in terms of their magnitudes, where S k < N is a sparsity level chosen by device k. To compensate for the information loss during the sparsification, the nullified entries are added to the local block update in the next communication round, as done in [22] and [23]. With this compensation strategy, the local block update that needs to be sparsified at device k is expressed asḡ where ∆ (t,b) k ∈ R N is a residual vector stored by device k for block b in round t. As a result, the local block update after the sparsification is denoted byg k ) which has only S k nonzero entries. Then, the residual vector is updated as Our sparsification step is summarized in Steps 1-3 of Procedure 2.
2) Dimensionality reduction: In the dimensionality reduction step, each local block update after the sparsification is projected onto a low-dimensional space as in CS [29]. Let R k = N M k ≥ 1 be a dimensionality reduction ratio chosen by device k, where M k ≤ N is the dimension after projection. Then, the compressed local block update x where α We set the scaling factor as α and the projection matrix as an IID Gaussian random matrix with zero mean and unit variance, i.e., (A R k ) m,n ∼ N (0, 1), ∀m, n. We assume 1 that the devices with the same dimensionality reduction ratio adopt the same projection matrix. Our dimensionality reduction step is summarized in Step 4 of Procedure 2.

3) Vector quantization:
In the vector quantization step, each compressed local block update is quantized using a Q k M k -bit vector quantizer, where Q k is the number of quantization bits per entry chosen by device k. To avoid the computational complexity for quantizing a highdimensional vector, the compressed local block update x k,P k ) T T , as in [15]. Then, these subvectors are quantized in parallel using a Q k L-bit vector quantizer. The resulting quantized subvector is given byv where Q C : R L → C is a vector quantizer with a codebook C such that |C| ≤ 2 Q k L . The optimal design of the vector quantizer will be discussed in Sec. IV-A. Our vector quantization step is summarized in Steps 5-6 of Procedure 2. After vector quantization, the quantized subvectors k,p } P k p=1 and the scaling factor α Owing to this feature, FedVQCS allows each device to not only reduce the communication overhead for transmitting its local model update but also control this overhead by adjusting the values of Q k and R k based on the capacity of the wireless link. Therefore, FedVQCS is a powerful framework for enabling wireless FL with limited link capacity. The optimization of Q k and R k for a given link capacity will be elucidated in Sec. IV-B.

C. Reconstruction of Global Block Update
The global block reconstruction process of FedVQCS consists of two steps: (i) group-wise aggregation, and (ii) sparse signal recovery, as summarized in Procedure 3. The details of each step performed by the PS for block b in round t are elaborated below.

1) Group-wise aggregation:
In the group-wise aggregation step, the PS groups the compressed local block updates with the same dimension and, then, aggregates only the compressed updates in the same group. Meanwhile, to facilitate an accurate reconstruction of the aggregated block update, the PS limits the number of the compressed updates in each group to be less than or equal to K ′ . By adjusting K ′ , the PS can control the tradeoff between the complexity and accuracy of the global block reconstruction, as will be justified later.
Let K g be the indices of the compressed local block updates in group g ∈ {1, . . . , G}, where G is the number of groups, and K 1 , . . . , K G are mutually exclusive subsets of K such that For ease of exposition, we assume that |K g | = K ′ , ∀g. Under error-free reception of the transmitted data {Ω k,p be a quantization error vector. Then, fromv where d k,P ) T T . Because R k = R g , ∀k ∈ K g , the PS can aggregate the compressed local block updates in group g as 2) Sparse signal recovery: In the sparse signal recovery step, the PS estimates the aggregated block updateg Kg from its noisy linear observation y Kg in (13) for every group g. As can be seen in (13), the estimation ofg Kg is a well-known sparse signal recovery problem [29]. Motivated by this fact, the PS employs a sparse signal recovery algorithm (e.g., [30], [31]) to estimateg Kg for every group g. The sparse signal recovery algorithm considered in our work will be elucidated in Sec. V. If the sparsity level ofg Kg is sufficiently smaller than the dimension of y Kg , which will be justified in Sec. IV-B, the PS is able to attain an accurate estimate ofg Kg . After the recovery of the aggregated block updates for all groups, the PS reconstructs the global block update asĝ Kg . Finally, the PS obtains the global model updateĝ Remark 2 (Comparison with existing FL frameworks): The existing FL frameworks in [13]- [15] consider vector quantization for compressing the local model updates, but without applying any dimensionality reduction technique. Unlike these frameworks, FedVQCS applies the CS-based dimensionality reduction before the vector quantization, which reduces the dimension of the local model update by allowing the transmission of its most significant entries only. In [19]- [23], it has been reported that the accuracy of FL does not severely degrade when sending a sufficient number of the significant entries. Therefore, FedVQCS achieves further compression of the local model updates compared with the frameworks in [13]- [15], without significantly sacrificing the learning accuracy. The existing FL framework in [18], which is our prior work, also leverages the CS-based dimensionality reduction, but considers only scalar quantization. In general, the scalar quantization is inferior to the vector quantization considered in FedVQCS in terms of the quantization error. Moreover, FedVQCS optimizes the dimensionality reduction ratio to further minimize the reconstruction error at the PS, which was not explored in [18].
Therefore, FedVQCS enables a more accurate reconstruction of the global model update when compared with the framework in [18].

IV. OPTIMIZATION AND CONVERGENCE ANALYSIS OF FEDVQCS
Here, we first optimize the design of a vector quantizer for the local block compression process of FedVQCS and then optimize the key design parameters of this compression process for minimizing the reconstruction error of the global model update at the PS. We also characterize the convergence rate of FedVQCS, while considering the reconstruction error at the PS.

A. Optimal Design of Vector Quantizer
In FedVQCS, a proper design of the vector quantizer in (11)  can be modeled as an IID random vector whose entry follows a Bernoulli Gaussian-mixture distribution. Hence, for a large N, the projected local model update x can be modeled as an M k -dimensional IID Gaussian random vector with zero mean and unit variance by the central limit theorem, can also be modeled as an L-dimensional IID Gaussian random vector whose distribution is same for all partitions, blocks, devices, and communication rounds, i.e.,

1) Quantizer design problem:
To determine the optimal vector quantizer for the distribution of v ∼ N (0 L , I L ), we consider a shape-gain quantizer, which is effective in quantizing an IID Gaussian random vector while enabling the efficient construction of the optimal codebook [32].
When employing this quantizer, the shape of v, defined as s = v/ v , and its gain defined as h = v are independently quantized. Let Q Cs (s) = argmin s∈Cs s −ŝ 2 and Q C h (h) = argmin h∈C h |h −ĥ| 2 be the shape and gain quantizers using the minimum Euclidean distance criterion, respectively.
Then, the output of the shape-gain quantizer will bev =ĥŝ, whereŝ = Q Cs (s) andĥ = Q C h (h).
As such, the MSE of the shape-gain quantizer can be approximated by [32] E where By utilizing this approximation, we formulate the shape-gain quantizer design problem for a given number of quantization bits QL as follows: argmin This problem is solved using the following strategy: First, we separately determine the MSEoptimal shape and gain quantizers for a fixed bit allocation (Q s , Q h ) and, then, we derive the optimal bit allocation (Q ⋆ s , Q ⋆ h ) for the optimal shape and gain quantizers. 2) Design of shape quantizer: When the number of shape quantization bits is given by Q s , the MSE-optimal shape quantizer is obtained by solving the following problem: . Unfortunately, it is hard to characterize the exact solution of this problem; thus, as an alternative, we consider an approximate solution by replacing the Euclidean distance with the squared chordal distance, as in [15]. Then the approximate solution of (16) is obtained as an even Grassmannian codebook C ⋆ s that can be constructed as follows [15]: • Solve the Grassmannian line packing problem formulated as [26]: where d(ŝ,ŝ ′ ) = 1 − |ŝ Tŝ′ | 2 .
• Construct the even Grassmannian codebook as C ⋆ s = C + s C − s where C − s = {s : −s ∈ C + s }. We determine the optimal shape quantizer by using the even Grassmannian codebook C ⋆ s constructed above. The MSE of the above shape quantizer is characterized, as given in the following lemma: Lemma 1: For large L, the MSE of the even Grassmannian codebook C ⋆ s with size 2 Qs is bounded as Proof: See Appendix A.

3) Design of gain quantizer:
When the number of gain quantization bits is given by Q h , the MSE-optimal gain quantizer is obtained by solving the following problem: where h = v . From v ∼ N (0 L , I L ), the probability density function of the gain h = v is given by where Γ(r) = ∞ 0 t r−1 e −t dt. Because this distribution is strictly log-concave, the Lloyd-Max algorithm in [25] converges to a globally optimal quantizer in terms of minimizing the MSE [33]. Hence, when Q h > 0, we determine the optimal gain quantizerby applying the Lloyd-Max algorithm for the distribution in (20). When Q h = 0, our strategy is to approximate the based on its distribution. Considering these two cases, the MSE of the above gain quantizer is characterized, as given in the following lemma: Lemma 2: The MSE of the optimal gain quantizer is approximated by where Proof: The MSE of the Lloyd-Max codebook with size Q h ≫ 1, namely C ⋆ h , is approximated by [34] We use the above expression for approximating the MSE of the Lloyd-Max quantizer for Q h > 0.

4) Optimal bit allocation:
Now, we derive the optimal bit allocation for the optimal shape and gain quantizers based on the MSE characterizations in (18) and (21). This result is given in the following theorem: Theorem 1: If both the upper bound in (18) and the approximation in (21) hold with equality, the optimal bit allocation Q ⋆ s , Q ⋆ h in (15) is given by where H L,Q = L−1 2L log 2 Proof: From Lemma 1 and Lemma 2, the bit allocation problem with Q h > 0 is Because (P 1 ) is convex [15], the optimal solution is readily derived by leveraging Karush-Kuhn-Tucker (KKT) conditions: where F L,1 (Q s , Q h ) is the objective function of (P 1 ), and λ ⋆ is a Lagrange multiplier. From the KKT conditions, the solution of (P 1 ) is given by Q s , Q h = (QL − H L,Q , H L,Q ), where From Lemma 1 and Lemma 2, the bit allocation problem with Q h = 0 is formulated as Because the objective function of (P 2 ) is a decreasing function of Q s , the solution is given by Q s = QL. The optimal bit allocation in (24) can be obtained by comparing F L,1 (QL − H L,Q , H L,Q ) and F L,2 (QL, 0). This completes the proof.
From Theorem 1, the MSE of the optimal shape-gain quantizer adopted in FedVQCS is approximated by The MSE in (30) clearly demonstrates that the increase in the number of quantization bits reduces the vector quantization error during the local block compression. Therefore, any increase in the capacity of wireless links will lead to a reduction in the reconstruction error of the global block update at the PS in FedVQCS.

B. Parameter Optimization for Local Block Compression
The local block compression process of FedVQCS has three design parameters: (i) the number of quantization bits per entry, Q, (ii) a sparsity level, S, and (iii) a dimensionality reduction ratio, R. These parameters are closely related to the wireless link capacity as well as the reconstruction error of the global model update at the PS. Motivated by this fact, we optimize the above parameters for minimizing the reconstruction error at the PS under the constraint of the wireless link capacity. In this optimization, we assume that the maximum number of digital bits that can be reliably transmitted from device k to the PS in each communication round is given by C kN > 0. We also assume that C k is known at both the PS and device k. Our strategy for parameter optimization is as follows: We first characterize the best choice of Q ⋆ k (R k ) and S ⋆ k (R k ) as a function of R k . We then determine the best dimensionality reduction ratio R ⋆ k when Q k = Q ⋆ k (R k ) and S k = S ⋆ k (R k ). In the remainder of this subsection, we omit the indices t and b for ease of exposition.
1) Characterization of Q ⋆ k (R k ) and S ⋆ k (R k ): As discussed in Remark 1, the communication overhead of FedVQCS for device k is Q k R kN bits. This overhead needs to be less than or equal to C kN for error-free transmission of the compressed local block updates from device k to the PS. Therefore, the optimal number of quantization bits to minimize the quantization error for a fixed R k is To determine the proper sparsity level, we consider the fact that the PS estimates the aggregated block updateg Kg = k∈Kg ρ kgk from its noisy linear observation y Kg = A RggK g + d Kg during the global block reconstruction, where (A Rg ) m,n ∼ N (0, 1). LetS g be the sparsity level of the aggregated block updateg Kg . According to the CS theory [29], a well-established sparse signal recovery algorithm can find a unique solution of the above sparse signal recovery problem with high probability, if for a large N, moderately largeS g , and large N/S g . Inspired by this result, we shall use the inequality (32) to check the feasibility of the accurate reconstruction of g Kg from y Kg . Recall that during the global block reconstruction process of FedVQCS, the PS groups the local model updates with the same dimensionality reduction ratio (i.e., R k = R g , ∀k ∈ K g ), as explained in Sec. III-C. Hence, the local block updates that belong to the same group have the same sparsity level (i.e., S ⋆ k (R k ) = S ⋆ g , ∀k ∈ K g ). From this fact, one can easily show that the condition in (32) always holds for all possibleg Kg if R k < N 2K ′ S k log(N/(K ′ S k )) . Therefore, we determine the best sparsity level for a fixed R k as 2) Optimization of R k : To facilitate the group-wise aggregation strategy explained in Sec. III-C, the dimensionality reduction ratio is assumed to be chosen among a candidate set R c = {R c 1 , . . . , R c C : R c i ≥ 1, ∀i}, shared by all the devices. Under this assumption, we aim to find the optimal choice of R k ∈ R c that can minimize the MSE of the global block reconstruction at the PS.
This optimization problem can be formulated as whereḡ Kg = k∈Kg ρ kḡ k , and the expectation is taken with respect to vector quantization error.
It is generally challenging for the devices to locally solve the problem in (34) because of a lack of knowledge of the local block updates sent by other devices in the same group. In addition, the estimate of the aggregated block update,ĝ Kg , depends on the sparse signal recovery algorithm chosen at the PS. To overcome these challenges, we consider the ideal scenario in which the PS perfectly finds the support set 2 ofg Kg by employing a powerful CS recovery algorithm, and, then, it minimizes the squared error g Kg −ĝ Kg 2 by solving the sparse signal recovery problem in (13). Under this consideration, we characterize the upper bound of the objective function in (34), as given in the following theorem: Theorem 2: Letĝ Kg be the least squares solution of the sparse recovery problem in (13) obtained with the knowledge of the support set of g Kg . If E[ d k 2 ] = σ 2 L,Q k , ∀k ∈ K g , for a large N R k ≫ 1 andS g ≫ 1, the MSE ofĝ Kg is upper bounded as follows: Proof: See Appendix B.
Theorem 2 shows that the upper bound of the global block reconstruction error at the PS can be minimized even if device k ∈ K g locally minimizes E k (R k ). Based on this result, instead of solving (34), we formulate a local optimization problem for device k ∈ K g as Because device k knows the input local block updateḡ k defined in (8), the objective function of (36) can be computed for every R k ∈ R c under the assumptions of Q k = Q ⋆ k (R k ) and S k = S ⋆ k (R k ). Then, by comparing the objective values, device k can determine its best dimensionality reduction ratio R ⋆ k . There exists a tradeoff between the first and second terms of the objective function in (36) which can be interpreted as sparsification and reconstruction errors, respectively. The reconstruction error decreases with R k because the number of vector quantization bits Q ⋆ k (R k ) is an increasing function of R k , as can be seen in (31). In contrast, the sparsification error increases with R k because the sparsity level S ⋆ k (R k ) is a decreasing function of R k , as can be seen in (33). Therefore, the optimization problem in (36) allows each device to determine the best parameters for optimizing the tradeoff between the sparsification and reconstruction errors in FedVQCS.

C. Convergence Rate Analysis
In this analysis, we characterize the convergence rate of FedVQCS when the SGD algorithm with E = 1 is employed for updating the parameter vector at the PS. In our analysis, we make the following assumptions not only for mathematical tractability but also for connecting our analysis with the parameter optimization in Sec. IV-B.
Assumption 1: The loss function F (w) is β-smooth and is lower bounded by a constant Assumption 2: For every w, the stochastic gradient is unbiased, i.e., E ∇F (t) k (w) = ∇F k (w), ∀k, t. Also, the expected squared norm of stochastic gradients is uniformly bounded, Assumption 3: The squared reconstruction error is upper bounded by the squared norm of the true gradient vector with some constant δ < 1, i.e.,

Assumption 3 is particularly relevant to FedVQCS because the parameter optimization of
FedVQCS aims at reducing the MSE of the global block update by opportunistically determining the parameters (Q, S, R) of the local block compression under the constraint of the wireless link capacity. Note that Assumption 1 and Assumption 2 are commonly adopted for analyzing the convergence rate of FL operating with a family of gradient descent algorithms, as in [13] and [35].
Under Assumptions 1-3, we characterize the convergence rate of FedVQCS with the SGD algorithm. This result is given in the following theorem: Theorem 3: Under Assumptions 1-3 with E = 1, ρ k = 1 K , and γ (t) = η (t) = 1−δ 2β(1+δ) √ T , FedVQCS with the SGD algorithm satisfies the following bound: where κ min = N/S min ≥ 1 and S min = min k,t,b S T , which is the same as that of a classical FL framework for a non-convex loss function [35]. Furthermore, the convergence speed of FedVQCS is shown to improve as both δ and κ min decreases. This result implies that our parameter optimization in Sec. IV-B is effective for improving the convergence speed.

V. SIMULATION RESULTS AND ANALYSIS
In this section, we demonstrate the superiority of FedVQCS over existing FL frameworks, using simulations. We assume that the communication overhead allowed for transmitting the local model update at device k is given by C k bits per local model entry. Under this assumption, we consider two communication scenarios: (i) homogeneous and (ii) heterogeneous. In the homogeneous scenario, we set C k =C, ∀k ∈ K, to model the wireless links with the same capacity; whereas, in the heterogeneous scenario, we uniformly draw C k from a pre-defined set C to model the wireless links with different capacities.
In this simulation, we consider FL for an image classification task using the publicly accessible MNIST [27] and CIFAR-10 [28] datasets. Details of the learning scenarios for each dataset are described below. For performance comparisons, we consider the following FL baselines: • Perfect reconstruction: This framework assumes lossless transmission of the local model updates from the wireless devices to the PS without compression, as described in Sec. II-A. that L2 Q ⋆ s ≤ 2 15 , where Q ⋆ s is the optimal number of shape quantization bits. • ScalarQCS: ScalarQCS is the communication-efficient FL framework developed in [18] when Q k = 1, R k = 1/C k , and S k = S ⋆ k (R k ). The aggregate-and-estimate strategy in [18] is adopted for the global block update reconstruction.
• HighVQ: HighVQ is the communication-efficient FL framework developed in [15] when Q k = C k . The dimension of each partition for vector quantization is set to be the largest integer, L, such that L2 C k L ≤ 2 15 for device k.
• D-DSGD: D-DSGD is the communication-efficient FL framework developed in [22]. The number of the nonzero entries for device k is set to be S k such that C kN = log 2 N S k + 33. For FedVQCS and ScalarQCS, we set (G, B) = (25, 10) for the MNIST dataset and (G, B) = (15, 75) for the CIFAR-10 dataset. Except for D-DSGD, we normalize the input data values of the training and test data samples using the mean and standard deviation of each dataset [37], [38]. For D-DSGD, we adjust the input data values of the training and test data samples so that these values are between 0 and 1.
In Fig. 2, we compare the classification accuracy of different FL frameworks in the homogeneous scenario. Fig. 2 shows that for both the MNIST and CIFAR-10 datasets, FedVQCS provides more than a 2.5% increase in classification accuracy compared to the existing communicationefficient FL frameworks when the communication overhead of the local model update transmis-  FedVQCS is more robust against the decrease in the communication overhead allowed for the devices, when compared with the existing FL frameworks.
In Fig. 3, we compare the classification accuracy of different FL frameworks in the heterogeneous scenario with various average communication overheads. In this simulation, we set  In Fig. 4, we compare the classification accuracies of FedVQCS with and without the parameter optimization in Sec. IV-B for the MNIST dataset in the homogeneous scenario with C k = 0.07. Without parameter optimization, we set R k = R, Q k = Q ⋆ k (R), and S k = S ⋆ k (R), ∀k ∈ K. Fig. 4 shows that FedVQCS with the optimized parameters provides a 1.8% increase in classification accuracy compared to FedVQCS with the worst-case parameters (i.e., R = 3 case). This result demonstrates that our parameter optimization effectively improves the accuracy of global model reconstruction at the PS in FedVQCS. This result is also consistent with the convergence rate analysis in Theorem 3 which demonstrated that the convergence rate improves as the reconstruction error of the global model update at the PS decreases.
In Fig. 5, we compare the classification accuracy of FedVQCS with that of ScalarQCS for different numbers of groups for the MNIST dataset in the homogeneous scenario with C k = 0.1. Fig. 5 shows that FedVQCS outperforms ScalarQCS regardless of the number of the groups. Because these two frameworks have a similar global model reconstruction process, the performance gain of FedVQCS over ScalarQCS is attributed to the use of vector quantization instead of scalar quantization. From Fig. 5, we can also observe that the classification accuracies of both frameworks decrease as G decreases. Because the computational complexity of the global model reconstruction process also decreases with G, the result in Fig. 5 shows that the performance-complexity tradeoff associated with these frameworks can be controlled by adjusting the number of groups.

VI. CONCLUSION
In this paper, we have presented a novel framework for communication-efficient wireless FL.
We have shown that our framework significantly reduces the communication overhead of FL by leveraging both vector quantization and CS-based dimensionality reduction for compressing the local model updates at the wireless devices. Another key feature of our framework is that the devices can locally optimize the compression parameters in order to minimize the reconstruction error of a global model update at the PS under the constraint of the wireless link capacity.
We have also demonstrated both analytically and numerically that our compression parameter optimization improves the convergence rate of FL. An important direction of future research is to optimize the learning rate of a training algorithm employed at the PS by taking into account the reconstruction error at the PS. Another promising research direction is to develop dynamic device scheduling and resource allocation strategies for the presented framework by considering the real-world radio resources available in a wireless network. APPENDIX A PROOF OF LEMMA 1 For any even codebook, the following equality holds s −ŝ 2 = 2 − 2 1 − d 2 (s,ŝ).
Combining the inequalities in (40) and (41) for a large L yields the bounds in (18).

APPENDIX B PROOF OF THEOREM 2
In this proof, we assume that K g = {1, . . . , K ′ } without loss of generality. Let T = {i : (g Kg ) i = 0} be the support set ofg Kg . Also, let R g be the dimensionality reduction ratio of the devices in group g. With the knowledge of T , the objective function in (34) can be rewritten as The first term of the right-hand-side (RHS) of (42) is rewritten as where (a) follows from the Cauchy-Schwarz inequality. Letg T be a subvector ofg Kg , which consists of the entries ofg Kg whose indices belong to T . Similarly, let A T be a submatrix of A Rg , which consists of the columns of A Rg whose column indices belong to T . Then, with the knowledge of T , the sparse signal recovery problem in (13) reduces to the estimation of g Kg,T from its linear observation y Kg = A RggK g + d Kg = A TgT + d Kg . The least squares solution of this problem is given byĝ