LASER: Linear Compression in Wireless Distributed Optimization

We thank the reviewer for the constructive feedback and insightful comments. We refer to the common response about the theoretical and algorithmic novelty of LASER.

• Theoretical analysis: As highlighted in the common response, a major difficulty in the theoretical analysis of LASER is handling the communication noise and the power budget. Since the channel noise interacts in a non-linear way with the gradients (Eq. (noisy channel)), we tackle this through introducing channel-influence factor which gives a handle to control the second-moments of the noisy gradients, which are crucial for convergence analysis. On the power front, Lemmas 7 and 8 in Appendix B.1 establish the optimal power allocation scheme among the rank components in order to obtain a tight characterization of the channel influence for various compression schemes. This further facilitates a thorough comparison with baselines such as Z-SGD and showcases the benefits of compression algorithms through convergence rates.

• Intuition behind Eq. (5): As demonstrated in Section 3 of the paper, the underlying intuition here is that under a fixed power budget, if we transmit the full gradient matrix of size $m \times m$, this budget has to be utilized for $m^2$ entries. On the other hand, if we capitalize on its low-rank structure we effectively need to transmit $O(m)$ entries, thus we can allocate more power-per-entry hence resulting in a roughly $O(m)$ boost in the signal-to-noise ratio (SNR). This intuition mathematically translates into the reduction of the gradient variance, as captured by the channel-influence factor in Eq. (4). In view of this, Eq. (5) compares these noise variances for Z-SGD and LASER and confirms the above intuition.

We thank the reviewer for the constructive feedback and encouraging comments and reconsideration of the score!

We thank the reviewer for the constructive feedback and insightful comments. We refer to the common response about the theoretical and algorithmic novelty of LASER, which also illustrates that it's extremely efficient and practical.

We thank the reviewer for the encouraging feedback and insightful comments.

• Power scalars: As highlighted in [1, 2], in each communication round the nodes first transmit the gradient norms $\|\| \boldsymbol{g}_i \|\|$, which are scalars, to the server which then computes their maximum and transmits it back. Since this procedure only involves transmission of real scalars, it has negligible communication overhead as compared to the gradients being transmitted.

• Processing time for PowerSGD and baselines: As highlighted in Section 4.3 of the paper, PowerSGD [3], the low-rank compressor behind LASER, takes significantly smaller processing time as compared to other compressors such as Top-K or Random-K. For example, Table 4 in [3] highlights that PowerSGD achieves a significant 42 % reduction in processing time/batch as compared to Top-K, whereas it’s 55 % compared to Random-K for CIFAR-10. Similar computational gains of PowerSGD over the baselines are demonstrated further in [3] over various challenging datasets.

• Energy budget: Indeed, our current comparison already considers the total energy costs in an implicit manner. Since we fix the power budget per each iteration across various baselines and compare the final accuracy after a specific number of epochs, this is equivalent to the former scenario. We observe similar gains for LASER even when the final number of epochs is increased further.

References:

• [1] Huayan Guo, An Liu, and Vincent KN Lau. Analog gradient aggregation for federated learning over wireless networks: Customized design and convergence analysis. IEEE Internet of Things Journal, 8(1):197–210, 2020.

• [2] Wei-Ting Chang and Ravi Tandon. Mac aware quantization for distributed gradient descent. In GLOBECOM 2020-2020 IEEE Global Communications Conference, pages 1–6. IEEE, 2020.

• [3] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 32, 2019.

We thank the reviewer for the encouraging feedback and valuable suggestions. We will fix the typos in our revised version. We address the individual questions below.

Local error: Following the standard convention in [1], in Line 7 of Algorithm 1 we add the local error $\boldsymbol{e}_i$ to the scaled gradient $\gamma \boldsymbol{g}_i$ to get the new gradient $\boldsymbol{M}_i$. In Line 13, after its low-rank reconstruction through $\boldsymbol{g}$, a normal SGD step is performed on $\boldsymbol{\theta}$. We can see that when there is no compression error, $\boldsymbol{e}_i =0$, this falls back to the classical SGD. As suggested, one could in principle multiply the learning rate $\gamma$ to the local-error but this requires a slight change in the definition of local error and the SGD descent step, so that we could recover the classical SGD in the special-case as above.

Assumption 5: Thanks for your insightful comment. We indeed highlight the interplay between $\lambda_{\mathrm{LASER}}$ and $\delta_r$ in Appendix B.2. Since the channel corruption follows the rank-compression, Assumption 5 roughly ensures that the overall compression is still benign. Mathematically, as derived in B.2, even in the hypothetical scenario where the compressor has access to the channel output, we see that a condition of the form $\lambda_{\mathrm{LASER}} \leq \delta_r$ is needed to ensure that the overall compression factor is still less than $1$. In view of this, Assumption 5 can be roughly treated as $\lambda_{\mathrm{LASER}} \leq O(\delta_r)$ in the general scenario.

On the other hand, while the above assumption is needed only for theoretical analysis, empirically we observe an interesting rank-accuracy tradeoff as demonstrated in Appendix F.5. We observe that either with low-rank or high-rank decomposition, the final accuracy is worse than that of the medium-rank. We believe this phenomenon is perhaps an empirical manifestation of the interplay between $\lambda_{\mathrm{LASER}}$ and $\delta_r$. Given the difficulty in characterizing $\delta_r$ precisely, establishing a clear mathematical justification for the aforementioned phenomena is an interesting topic of future research.

Layer-wise decomposition: We fully agree with your comment. Indeed, we already specify this feature just below Algorithm 1 on page 4 in the paper, but we will further make it clear.

References:

• [1] Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv:1909.05350, 2019.

Dear Authors, thanks a lot for your answer,

• Local error: That makes sense, thanks for your answer (also, this has become clearer for me upon inspection of equation (20) in [1]).
• Assumption 5: Thank you, that makes it clearer for me. Though, regarding the bound on $\delta\_r$, in general, wouldn't $\delta\_r$ be equal to $\frac{r}{d}$ ? (since, assuming the worst case scenario where $\boldsymbol{M}$ has all singular values equal to its largest ($\sigma\_{max}$), we have for the Frobenius norm $\\| \mathcal{C}\_r (\boldsymbol{M}) -\boldsymbol{M} \\|\_{F}^2 = (d-r)\sigma\_{max}^2 = (1 - \frac{r}{d}) d \sigma\_{max}^2 = (1 - \frac{r}{d}) \\| \boldsymbol{M} \\|\_F^2$ (I may be mistaken). With such bound, this means, according to equation (5), that it would be necessary to enforce an SNR large enough to ensure validity of Assumption 5 (e.g. it is not verified if SNR=1) ? However, I guess this bound on $\delta\_r$ is loose in practice since DNNs for instance, are low-rank compressible so $\delta\_r$ will be smaller. But I guess it could be interesting to deepen this aspect: for instance if there are some common assumptions on the "low-rank compressiveness" of DNNs in the literature which would give some tight enough bound on $\delta\_r$, those would in turn result in the necessary value for the SNR; another option could be to just verify experimentally, by computing the maximum $\delta\_r$ over all $\boldsymbol{M}$ encountered during training, and checking whether it verifies Assumption 5. In any case, such analysis does not need to be done (as the remaining time is limited), and so this will not impact my evaluation of the paper, I am just checking whether my understanding of the technique is correct.
• Layer-wise decomposition: Thank you, I had missed the reference on page 4.

I have read the reviews and responses, and I keep my positive impression on the paper and will preserve my score.

1) Please note that the central node does not have to be a base station; the central node could be the edge device, such as a router in a concert hall. As a concrete example, let's consider the following scenario.

Location: a concert hall with a few hundred to several thousands of audience (or more)

Clients: cell phone

Central node: edge device

ML models to be learned: music-related neural network in an app (e.g., Spotify)

Here, several clients - whose data will be most relevant to training a music-related ML model- are physically co–located and thus naturally share the wireless medium. (Cf. The clients here would be anyone willing to share their gradients and need not be chosen beforehand.) Thus in this example, the central node could be the edge device, such as a router in the concert hall.

2) Applying our algorithm to “cellular” communication scenarios (i.e., Base Stations = central node, User Equipment (UE) = clients ) will potentially require more coordination and adjustments. First of all, we agree that not all cells would be suitable to perform LASER-based federated learning. Instead, only some base stations (with sufficiently large clients participating in the federated learning) will allocate some (wireless) resource blocks to the LASER operation. There are several other aspects to coordinate such as resource allocation (data traffic vs. federated learning traffic). These are all interesting potential research problems although they are not within the scope of our work. We would like to briefly mention that supporting ML applications from wireless is of increasing interest.

We thank the reviewer for the engaging and insightful comments.

It is true that in today’s communication systems, the encoders need to follow standards. Related to that, we (1) explain how we could make LASER compatible with the current modulation scheme, (2) discuss potential (minimal) changes in the wireless systems required to implement LASER, and (3) make final remarks on our thoughts on academic research.

1) Digital vs. Analog transmissions: LASER transmission as a high-order QAM. There are ways to adapt LASER to a digital transmission framework if needed. Perhaps one straightforward way would be to quantize the transmitted values of LASER to make it compatible with the modulation schemes used in today’s communication systems (e.g., QAM). The typical range of QAM levels varies from system to system. For WiFi, a very high modulation order (e.g., 4096-QAM) is one of the key enhancements of WiFi 7 (IEEE 802.11be). It is shown in the literature that the quantization of real-valued codewords to 6 bits usually does not affect the reliability much. The quantification of LASER is an interesting future research topic.

2) LASER and Comm. Standards.

Small modification: We would like first to note that using LASER (+ quantization) in today’s wireless systems will only require ‘bypassing’ channel coding/modulation and directly generating modulation symbols, which is not a complicated modification.

LASER as a joint-source channel coding algorithm: regarding the reviewer’s comment that “Wireless communication standards will (not) incorporate a specific physical layer technique only for the sake of computing averages”, on the one hand, we’ll note that given that we do not need major changes to the wireless system as noted above, we do not think LASER is completely ruled out solely for the compatibility reason. On the other hand, we would like to note that LASER belongs to a broad family of joint source-channel coding algorithms from the perspective of which part of the standards needs to change. Communication systems, to date, relied on source-channel separation for several reasons; it’s simple; it’s known to be optimal if we have a lot of (asymptotically many) IID sources; and there are not many good joint source-channel coding algorithms. With the advance of ML, there are several reasons to explore neural joint source-channel codecs, some of which includes that not all part of the data source is equally important; we finally have the capability to design analytically intractable joint source-channel coding algorithms in a data-driven manner, etc. (cf. There are several studies demonstrating the efficacy of data-driven short-blocklength neural codecs and semantic communications such as NECST [1]). Joint source-channel coding, also called semantic communications, for wireless is definitely of interest to industry and academia; the communities as a whole are at the stage of exploring what is feasible and how much gain we can achieve from it.

Recent trends in Wireless: Given the extensive interest from industry and academia in neural-based codecs, joint source-channel coding, ML-driven wireless, wireless for ML applications, end-to-end ML-driven communication blocks, and virtualized RAN, we do not think LASER (and more generally directly mapping data to modulation symbols) is completely ruled out in future. An interesting discussion would be on which communication modes (cellular, wifi, or private networks) can benefit most by deploying LASER.

Final remark: As a final remark, we believe, as academics, we should not bind our research only to what is available with today’s technology. We believe it's an important and exciting area of research to evaluate the capability of aggregation-leveraging communication algorithms.

References:

• [1] NECST: https://arxiv.org/abs/1811.07557

We thank the reviewer for the constructive feedback and insightful comments. We refer to the common response about the novelty of LASER.

• Uplink and downlink noise: In the uplink channel the resource-constrained workers communicate with the server whereas in the downlink communication the server to the clients. The downlink is a broadcast channel which is typically assumed in the literature to be noiseless [1-3]. The underlying intuition here is that the central server (e.g. base station) is not as resource/power-constrained as the individual clients (e.g. mobile phones) and hence it can ensure its transmission error-free relatively speaking. While few works [8, 9] study the impact of downlink noise on the convergence of Z-SGD, it’s an interesting future direction to extend these results for LASER-like compression algorithms.

• Transmission of power scalars: Yes, indeed. As highlighted in [4, 5], the nodes transmit only the gradient norms $\|\| \boldsymbol{g}_i \|\|$, which are scalars, to the server which then computes their maximum and transmits it back. Since this procedure only involves transmission of real scalars, it has negligible communication overhead as compared to the gradients being transmitted.

References:

• [1] H Brendan McMahan and Daniel Ramage. Federated learning: Collaborative machine learning without centralized training data. https://ai.googleblog.com/2017/04/federated-learning-collaborative.html, 2017.

• [2] Jakub Koneˇcn `y, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492, 2016.

• [3] Jakub Koneˇcn `y, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02527, 2016.

• [4] Huayan Guo, An Liu, and Vincent KN Lau. Analog gradient aggregation for federated learning over wireless networks: Customized design and convergence analysis. IEEE Internet of Things Journal, 8(1):197–210, 2020.

• [5] Wei-Ting Chang and Ravi Tandon. Mac aware quantization for distributed gradient descent. In GLOBECOM 2020-2020 IEEE Global Communications Conference, pages 1–6. IEEE, 2020.

We apologize for the delay in our response. Regarding the compatibility with the wireless communication standards and base stations, we responded to your review directly. Here we address the remaining questions:

• Feedback analysis: Here the main idea is to control the influence of the channel via the channel influence factor to leverage the standard error-feedback analysis. To this end, in Appendix B, as highlighted in Eq. (LASER), Appendix B.1 and B.2 obtain characterizations of the channel influence factor. Building upon this, in B.3, we utilize the standard error-feedback techniques taking this new factor into account and incorporating it into the standard lemmas for error bounds and the progress in the descent step (Lemmas 11-13).

• Power budget: Please note that the power budget is fixed across all the baselines for comparison. Then this fixed budget is varied in order to capture the relationship between the final accuracy and the power budget used (accuracy improves with more power). Hence the tables 1 and 3 show that for the baseline Z-SGD to achieve the same accuracy as that of LASER, it needs $16 \times$ more power.

Thanks for the response. Regarding novelty in the analysis, it would be helpful if you could point to specific steps (e.g., equation numbers) where the analysis is different from standard error-feedback analysis.

My following comments remain unaddressed:

• The considered wireless communication system with "over the air" averaging is essentially doing the averaging in the analog domain. This is impractical as all modern wireless systems are digital and data transmission involves channel coding, which is likely incompatible with "over the air" averaging. I am aware that this concept has been presented in many papers published in wireless communications journals and conferences, but it is still impractical. It is unlikely that wireless communication standards will incorporate a specific physical layer technique only for the sake of computing averages, which in any foreseeable future represents only a very small fraction of data transmitted in common wireless systems. Moreover, this mechanism restricts the averaging to clients communicating with a single basestation, while in practice, the coverage of a single basestation is quite small and having all the clients connecting to the same basestation is very unlikely.
• It is not quite clear how power reduction is achieved as shown in the experiments. The power budget is fixed according to Algorithm 1. If there is a fixed power budget, the same budget should apply to both the proposed algorithm and the baselines. The results in Table 1 and Table 3 either do not enforce a fixed power budget, which contradicts with the description in Algorithm 1, or there is something else wrong.