SpaFL: Communication-Efficient Federated Learning with Sparse Models and Low Computational Overhead

We appreciate the constructive comments. We provide our response to each comment below.

Q1 See weakness 1, During local training with e < E, does the thresholds not be updated? Equation (5) and (6) only work for the e=E? And how the equation (6) is derived?

A1: Yes, when $e < E$, only model parameters are updated while thresholds are frozen. In the last epoch, i.e., $e = E$, we freeze model parameters and update thresholds using eq. (5) and (6). Hence, during $E-1$ epochs, model parameters can adapt to newly generated masks by recovering from pruning-induce noise. Then, in the last epoch, we give the thresholds performance feedback on the current sparse model. We believe that the explanation of the algorithm was not clear enough in the manuscript, and we will clarify it in the revised version.

For the derivation of eq. (6), we define $S(\cdot)$ as a unit step function and $Q\_{k, ij}^{E-1, l} (t)) = |w\_{k, ij}^{E-1, l} (t)| - \tau_i^l(t)$. Then, we can derive eq. (6) as follows:

$\frac{\partial F\_k (\tilde{w}\_k^{E-1}(t), \tau(t) )}{\partial \tau_i^l(t)} = \sum\_{j=1}^{n} \frac{ \partial \tilde{w}\_{k, ij}^{E-1} (t) } { \partial \tau\_i^l (t) } \frac{\partial F\_k (\tilde{w}\_k^{E-1} (t), \tau(t)) }{\partial \tilde{w}\_{k, ij}^{E-1} (t) } = \sum\_{j=1}^{n\_{in}^l} \frac{ \partial \tilde{w}\_{k, ij}^{E-1} (t) } { \partial Q\_{k, ij}^{E-1, l} (t) } \frac{ \partial Q\_{k, ij}^{E-1, l} (t) } { \partial \tau\_i^l (t) } g\_k( \tilde{w}\_k^{E-1}(t))\_{ij}^l$ $= \sum\_{j=1}^{n\_{in}^l} w\_{k, ij}^{E-1, l} (t) \frac{ \partial S(Q\_{k, ij}^{E-1, l} (t)) } { \partial Q\_{k, ij}^{E-1, l} (t) } (-1) g\_k( \tilde{w}\_k^{E-1}(t))\_{ij}^l = -\sum\_{j=1}^{n\_{in}^l} w\_{k, ij}^{E-1, l} (t) g\_k( \tilde{w}\_k^{E-1}(t))\_{ij}^l ,$ where the last equation results from the fact that we used the identity straight-through estimator for $\frac{ \partial S(Q\_{k, ij}^{E-1, l} (t)) } { \partial Q\_{k, ij}^{E-1, l} (t) }$ and $w$ and $\tau$ are constrained to be within $[−1, 1]$ and $[0, 1]$ as described in Section. 3.2.1.

Q2. Comparing equation (10) and (11), authors concludes the relationship between the gradient direction and $\Delta \tau$ when $w >0$ or $w<0$. However, Equation (9) is about the global $\tau$, while equation (10) is talking about local $\tau$. Could authors explain this in more details?

A2: We would like to note that the thresholds in eq. (9) and (10) are both global thresholds. Specifically, in eq. (9) $\tau(t+1) = \sum\_{k \in S\_t} \tau\_k(t)$, $\tau(t+1)$ represents global thresholds and $\tau\_k(t)$ represents local thresholds updated by client $k$ at the last epoch. Eq. (10) is about the gradients of the loss with respect to the current global thresholds $\tau(t)$ as shown in eq. (5). Hence, the clients can obtain $\tau\_k(t)$ by updating $\tau(t)$ using eq. (10).

The main purpose of Section 3.2.4 is to identify how to update model parameters for given $\Delta \tau(t) = \tau(t+1) - \tau(t)$. The update in Section 3.2.4 occurs after receiving the global thresholds $\tau(t+1)$, which is generated from eq. (9). If $\Delta \tau\_i^l < 0$, then the parameters connected to threshold $\tau\_i^l$ are globally important. Otherwise, those parameters are less globally important. Hence, a client can deduce how to update its parameters for given $\Delta \tau(t)$. To this end, we used eq. (10) and (11) to explain the relationship between the sign of parameters, the sign of $\Delta \tau(t)$, and the gradient direction of the parameters.

We appreciate the reviewer for the constructive comments. We provide our response to each comment below.

Q1: What happens if clients do not receive the server update due to unavailability? It is specifically important as the solutions is designed for resource-constrained cross-device FL, where clients are only sometimes available.

A1: We agree with the reviewer that clients may not always be able to receive global thresholds due to their constrained resources. To demonstrate that SpaFL is also compatible with intermittent availability, we did comparison between SpaFL and a baseline where only a small subset of clients can receive the server update. This baseline can capture the unavailability of some clients who cannot participate in the training at a given time. Below, we provide an empirical comparison between SpaFL and the baseline with the scheduling size of 10.

For SpaFL, the communications costs are $1.0208$ Gbit, $2.4956$ Gbit, and $0.7674$ Gbit, for FMNIST, CIFAR-10, and CIFAR-100, respectively. For the baseline, the communications costs are $0.1856$ Gbit, $0.4537$ Gbit, and $0.1395$ Gbit, for FMNIST, CIFAR-10, and CIFAR-100, respectively. We can see that the performance loss of the baseline is very small. Moreover, the baseline used only $20$% of the communication costs used by SpaFL. Therefore, this result demonstrates the compatibility of SpaFL with a scenario where only a subset of clients is available and receives the server update.

Q2. How do non-participant clients update their model?

A2: As demonstrated by response A1, intermittently non-participating clients can update their model when they become available and receive server update. If a client is not participating in the training at a given time, then we can proceed with the SpaFL algorithm with a subset of participating clients. However, if some clients do not participate in the training permanently, then they cannot update their model in SpaFL. However, we believe this is the case for most of FL algorithms and not unique to SpaFL.

Q3: Is there any global model available?

A3: Since SpaFL personalizes clients' models, it does not have a global model. Instead, clients share global thresholds. Since global thresholds are aggregated parameter importance, clients can know which neuron/filter is globally important, thereby learning how to prune their model.

However, SpaFL can also be extended to share some model parameters between clients. Clients can transmit their unpruned parameters to the server as done in [8,9,22,24,25,26] (references are from the manuscript) along with their thresholds. Then, the server can generate a global model by aggregating the received parameters and thresholds. Hence, we extend SpaFL to enable clients to share both global model and thresholds.

We appreciate the reviewer for the constructive feedback. We provide our response to each comment below.

Q1. During the local training for parameters and thresholds, if the gradients are calculated for every weight and applied with the binary mask, then how does it help save the computation overhead? Or if the gradients are calculated w.r.t. the sparse weights, how is it achieved in practice?

A1: During the backpropagation, for each layer, we calculate the gradients for the input activations and the gradients for the weights. In SpaFL, we are able to reduce the number of FLOPs to calculate the gradients for input activations by convolving sparse weight tensors with the gradients of the output activations. In particular, we sparsified the weight tensors before performing convolutions by detaching them from the computation graph. Below, we provide a detailed explanation about how we reduce the computation overhead of the backpropagation.

Consider a convolutional layer with an input tensor $𝑋 ∈ R^{𝑁×𝐶×𝑋×𝑌},$ parameter tensor $𝑊 ∈ R^{𝐹 ×𝐶×𝑅×𝑆}$, and output tensor $𝑂 ∈ R^{𝑁×𝐹 ×𝐻×𝑊}$. Here, the input tensor $X$ consists of $N$ number of samples, each of which has $X×Y$ dimension. The parameter tensor $W$ has $F$ filters of $C$ channels with kernel size $R × S$. Assume that $𝑊$ is pruned, and $𝜌$% of the parameters are active. The output tensor $O$ will have $F$ output channels with dimension $H × W$ for $N$ samples. We can calculate the number of FLOPs for the gradients of input activations by convolving the gradient of output activations with the parameter matrix $W$. Hence, it can be approximated to $𝜌 × 𝑁 × (𝐹 × 𝑅 × 𝑆) × 𝐶 × 𝑋 × 𝑌$. Since we used a sparse tensor $𝑊$ during the forward propagation, we can reduce the number of FLOPs for calculating the gradients of input activations by $𝜌$. Then, we can calculate the gradients of the weights by convolving the input activation with the output gradient. This can be approximately given by $(N × X × Y ) × F × C× R × S$. Since we did not sparsify the activations, there is no reduction of FLOPs in this calculation. Therefore, the total number of FLOPs for the backpropagation in SpaFL can be given by $(1 + 𝜌) × 𝑁 × 𝐹 × 𝑅 × 𝑆 × 𝐶 × 𝑋 × 𝑌$. Meanwhile, without sparsity, the number of FLOPs for the backpropagation will be $2 × 𝑁 × 𝐹 × 𝑅 × 𝑆 × 𝐶 × 𝑋 × 𝑌$. Hence, we can reduce the computing overhead by $\frac{1+𝜌}{2}$ in the backpropagation compared to a baseline that does not use sparse weights. As shown in Fig. 2 in the manuscript, model densities in SpaFL usually go below $10$% after 200 rounds. Hence, we can reduce the computation overhead in the backpropagation around $30$% compared to dense baselines during the training.

Thank you for the constructive comments. We provide our response to each comment below.

Q1: In addition to an intuitive justification for the regularizer in (4) and the second update in 3.2.4 can you also provide an empirical comparison with alternate regularizers?

A1: The main reason for choosing the regularizer $R=\exp(-||\tau||)$ in (4) is that the exponential function goes to zero asymptotically as thresholds increase. This is reasonable because it can penalize low thresholds without making them become extremely large. We can also use a similar regularizer that can give penalty for low thresholds without encouraging them to become a too large value. For example, a regularizer $R' = \frac{1}{||\tau|| + 0.1}$ satisfies such property. Below, we provide an empirical comparison between SpaFL and the baseline that uses $R'$ as below.

For the regularizer $R$, the achieved model densities are $5.36$%, $7.57$% and $7.38$% for FMNIST, CIFAR-10, and CIFAR-100, respectively. Meanwhile, with $R'$, the model densities are $4.85$%, $5.60$%, and $8.01$% for FMNIST, CIFAR-10, and CIFAR-100, respectively. We can see that both regularizers work well with SpaFL. Hence, SpaFL is compatible with any regularizers that can penalize the magnitude of thresholds asymptotically.

Q2: Likewise can you also provide a comparison with a baseline which does not use the update in 3.2.4 but instead just directly continues training the model with the new global thresholds?

A2: The main purpose of Section 3.2.4 is to update the model parameters by extracting the aggregated importance from global thresholds. By investigating the difference between two consecutive global thresholds and parameters, clients can deduce which parameters are globally important. Although clients perform their training using the received global thresholds as described in Section 3.2.2, this additional update provides meaningful performance gains. We provide an empirical comparison between SpaFL and the baseline that does not use the update in 3.2.4 as below

We can see that the update in Section 3.2.4. can provide a clear improvement compared to the baseline by utilizing the aggregated parameter importance from global thresholds.

Q3: Can you provide a derivation for (6) and (11)?

A3: To derive (6), we start from the gradient of the loss with respect to a threshold, as follows:

$\frac{\partial F\_k (\tilde{w}\_k^{E-1}(t), \tau(t) )}{\partial \tau_i^l(t)} = \sum\_{j=1}^{n} \frac{ \partial \tilde{w}\_{k, ij}^{E-1} (t) } { \partial \tau\_i^l (t) } \frac{\partial F\_k (\tilde{w}\_k^{E-1} (t), \tau(t)) }{\partial \tilde{w}\_{k, ij}^{E-1} (t) }= \sum\_{j=1}^{n\_{in}^l} \frac{ \partial \tilde{w}\_{k, ij}^{E-1} (t) } { \partial Q\_{k, ij}^{E-1, l} (t) } \frac{ \partial Q\_{k, ij}^{E-1, l} (t) } { \partial \tau\_i^l (t) } g\_k( \tilde{w}\_k^{E-1}(t))\_{ij}^l$ $= \sum\_{j=1}^{n\_{in}^l} w\_{k, ij}^{E-1, l} (t) \frac{ \partial S(Q\_{k, ij}^{E-1, l} (t)) } { \partial Q\_{k, ij}^{E-1, l} (t) } (-1) g\_k( \tilde{w}\_k^{E-1}(t))\_{ij}^l = -\sum\_{j=1}^{n\_{in}^l} w\_{k, ij}^{E-1, l} (t) g\_k( \tilde{w}\_k^{E-1}(t))\_{ij}^l ,$ where $Q\_{k, ij}^{E-1, l} (t)) = |w\_{k, ij}^{E-1, l} (t)| - \tau_i^l(t)$, $S(\cdot)$ is a unit step function, $\tilde{w} = w \cdot S(Q(w))$. The last equation results from the fact that we used the identity straight-through estimator and $w$ and $\tau$ is constrained to be within $[−1, 1]$ and $[0, 1]$ as described in Section 3.2.1 and 3.2.2.

The derivation of eq. (11) is similar to the above. We start from the gradient of the loss with respect to a parameter $w$ as follows $\frac{\partial F\_k (\tilde{w}\_k(t), \tau(t) )} {\partial w\_k(t)} = \frac{\partial \tilde{w}\_k(t)}{\partial w\_k(t)} \frac{ F\_k (\tilde{w}\_k(t), \tau(t) ) } {\partial \tilde{w}\_k(t) }= \frac{\partial \tilde{w}\_k(t) }{ \partial Q\_k(t) } \frac{\partial Q\_k(t)}{\partial w\_k(t)} g\_k( \tilde{w}\_k(t) )$ $= w\_k(t) \frac{\partial S(Q\_k(t))}{\partial Q\_k(t)} \frac{\partial |w\_k(t)|}{\partial w\_k(t)} g\_k( \tilde{w}\_k(t) ) = |w\_k(t)| g\_k( \tilde{w}\_k(t) ).$ This completes the derivation of eq. (11).