Accelerating Federated Learning with Quick Distributed Mean Estimation

Thank you for the review.

---

Weaknesses

---

The abstract is not informative at all. The reader has no idea about the techniques this work uses to improve DME and the novelty of the techniques after reading it. It should at least mention, for example, one idea QUIC-FL builds on is BSQ which sends exactly a few large coordinates and quantizes the rest small ones.

We will revisit the abstract to make it more informative.

In Introduction, the paragraph starting with “For example, in Suresh et al. 2017 …”, it is mentioned the entropy encoding is “compute-intensive”. How long does the decoding time of this approach take? Table 1 does not include entropy encoding as a baseline.

It is mentioned in Introduction that the decoding procedure of “entropy encoding” from a previous work is “compute-intensive”. What is the time complexity of this decoding procedure? It seems this approach is not included in Table 1 as a baseline for comparison.

In theory, entropy encoding requires $O(d)$ time. However, this operation is not GPU-friendly and is thus much slower in practice. In the paper “DoCoFL: Downlink Compression for Cross-Device Federated Learning” (ICML 2023), the authors performed timing measurements of entropy encoding schemes and found it to be ~ two orders of magnitude slower compared to EDEN, which runs on a GPU (QUIC-FL also runs on a GPU and is faster than EDEN as we show in the paper).

The Lloyd-Max quantizer is a biased quantizer that yields good quantization levels for a given distribution. In some cases, the outcome may be suboptimal (see [A], Example 3.2.1 ). However, the quantizer is known to be optimal for the log-concave distributions (see, e.g., [B]), including the Guassian, which is the focus of our work.

[A] MIT lecture notes https://ocw.mit.edu/courses/6-450-principles-of-digital-communications-i-fall-2006/926689aaa62a0315473fa9b982de1b07_book_3.pdf

[B] Huang, Bormin, and Jing Ma. "On asymptotic solutions of the Lloyd-Max scalar quantization." 2007 6th International Conference on Information, Communications & Signal Processing. IEEE, 2007. https://ieeexplore.ieee.org/document/4449824.

The paragraph “while the above methods suggest …” is abrupt and confusing. It’d be better to move this paragraph before surveying existing quantization techniques in Introduction.

In Section 2 preliminaries, it would be clearer if “unbiased algorithms and independent estimators” can be formally and clearly defined. Minor issue: “we that NMSE …” => “we want that NMSE …”

We will revise these accordingly.

The uniform random rotation appears at several places in the work. What exactly is this rotation? Is it a uniform Gaussian random rotation?

Random Matrix Theory (RMT) was introduced by Wishart [C] in 1928, and includes rotating the vector by multiplying it with a “rotation matrix”, which is a random orthogonal matrix (see e.g., [D] for more details and methods for its generation. We will discuss this in the paper.

[C] Wishart J. The generalised product moment distribution in samples from a normal multivariate population. Biometrika 20A, 32–52 (1928). [D] Martin A Tanner and Ronald A Thisted. Generation of Random Orthogonal Matrices. Journal of the Royal Statistical Society. Series C (Applied Statistics), 31(2):190–192, 1982.

In Section 3.5 “accelerating QUIC-FL with RHT”, “adversarial vectors” are mentioned but not introduced. It is confusing how the proposed approach compares against DRIVE and EDEN in terms of the application to “adversarial vectors”.

We meant that there are inputs for which DRIVE and EDEN fail to give an $O(1/n)$ NMSE when using RHT, as we explain in Appendix A. This is not a distinct application but rather an acknowledgment that DRIVE and EDEN are not suitable for worst-case situations.

In Section 3.5 “accelerating QUIC-FL with RHT”, it states “the result does not have the additive NMSE term is [because] we directly analyze the error for the Hadamard-rotated coordinates”. Can the author be more formal and specific how the analysis here is different from the one in Theorem 3.1?

In Theorem 3.1., we analyze the error that arises from approximating the distribution after a uniform random rotation and show that it is manifested in the $O(\sqrt{\log d / d})$ additive error term. The analysis in Section 3.5 directly analyzes the distribution that results from applying RHT, and thus no additional error term is needed.

Several places in the work states in plain text the performance of QUIC-FL with different values of its hyperparameters. For example, in Section 3.5 “accelerating QUIC-FL with RHT”, it states the NMSE of QUIC-FL is bounded by … with $b=1,2,3,4$. It’d be easier for the readers if those numbers can be turned into figures.

We will add the figures to the paper.

Thank you for the review.

Regarding the first question: Yes! One can use our approach to optimize the quantization for the actual distribution (shifted-Beta, as we explain in the paper - page 6). We knowingly chose to optimize it for the normal distribution instead as (1) it is independent of the dimension of the input vectors, (2) it is a good approximation and the error that arises from it diminishes very quickly with the dimension. This way, we can run the solver once and get a solution that is applicable across a range of vector dimensions and learning tasks. By restricting the number of solver invocations, we can also run the solver to yield a better approximation (e.g., more quantiles and shared randomness values) for the same overall computation/time.

The runtime of the solver is exponential in $b$ (and is largely independent of $p$ and $t_p$), but we only need to run it once (offline) for each value of $b$, and the values of interest are small (e.g., $b\in\{1,2,3,4\}$).

We will clarify these in the paper.

Regarding the requested changes: We will fix the first two. Thank you! With respect to the third, it should indeed be $x$ and not $R(h,x)$, which is the value that the receiver estimates the coordinate at given the shared randomness value $h$ and message $x$.

Thank you for the review.

Indeed, we do not claim that QUIC-FL is generally more accurate than EDEN in practice. Our contribution is in getting a comparable accuracy with asymptotically faster decoding time.

Moreover, our contribution is not just in improving the decoding complexity, but also in providing stronger worst-case guarantees. Namely, EDEN has an NMSE of $O(1/n)$ only when using uniform random rotation (which requires $O(d^3)$ time and is computationally intensive) and $O(1)$ when using RHT (as the quantization is biased; see Appendix A for details). In contrast, QUIC-FL has $O(1/n)$ NMSE even when using RHT.

Regarding the decoding time, as we convey in the paper: According to recent sources (e.g., see the “Federated Learning with Formal Differential Privacy Guarantees” blog post by Google), cross-device FL training procedures can accommodate many thousands of devices per round. Current works (see “Federated Learning with Formal Differential Privacy Guarantees,” SysML 2019) even discuss using tens of thousands of clients per round. In such a setup, if one wishes to use the most accurate available DME techniques, asymptotically faster aggregation time may translate to significant savings in time and/or resources, even if the aggregation is performed on a powerful server.

In light of our consistent findings and the existing evidence that suggests such savings translate to reduced latency (“..devices have significantly higher-latency, lower-throughput connections..”, Federated learning: Collaborative machine learning without centralized training data, Google blog), we believe our approach will indeed lead to improved real-world deployment.

Regarding the overhead of encoding the indices – we do consider $p$ to be a constant (e.g., 1/512). You are correct that if we encode the indices explicitly, this will cost $O(d\log d\cdot p)$ bits ($O(d\log d)$ if $p$ is constant). In theory (and in practice), we can simply use $d$ bits to encode the indices in a 0-1 vector for $d$-bit overhead for all indices combined in all cases. In practice though, as $p$ is considerably smaller than $1/\log d$, it is cheaper to send the indices, and this was the point of our statement.

In summary, the theoretical results can be achieved by sending a bit vector, and thus we achieve the $O(1/n)$ bound with $b=O(1)$. In practice, for reasonable $p$, $d$, explicit encoding of the $p$-fraction of the coordinates is cheaper.

We will clarify these points in the paper.

Thank you for the review.

Unfortunately, QUIC-FL’s faster decoding relies on the quantization itself being unbiased, while EDEN uses an optimized biased quantization of the transformed coordinates. EDEN becomes unbiased for a single sender only after the inverse rotation and scaling are applied; however, this also requires users to use different rotations because otherwise, the senders’ results are not independent. EDEN’s better vNMSE is a direct implication of biased quantizations being capable of lower error rates than unbiased ones. We do not see an approach that allows QUIC-FL to apply different rotations to different senders and maintain its decoding time. In particular, because QUIC-FL uses the same rotation for all senders, the unbiasedness comes from a randomized rounding using the same rotation (unlike EDEN’s deterministic rounding, with different random rotations). We do not see how a hybrid can be achieved.

Regarding 3.1, the term $\mathbb E[(Z-\widehat Z)^2]$ is independent of $d$ and only depends on $b,p$. We present it in this way to allow one to understand how further improvements in the unbiased quantization of normal random variables (e.g., if one has a more powerful solver or is able to solve the continuous variant) translate directly to improvements in the vNMSE bound. We can provide explicit tables that give bounds for meaningful values of $b,p$. One such result is given in Thm G.3 for running QUIC-FL with RHT. Here, we also give the vNMSE results for QUIC-FL with a uniform random rotation, which are closer to the error in practice even when using RHT:

p = 1/128:

b = 1, $\mathbb E[(Z-\widehat Z)^2]$ = 1.408 b = 2, $\mathbb E[(Z-\widehat Z)^2]$ = 0.201 b = 3, $\mathbb E[(Z-\widehat Z)^2]$ = 0.0398 b = 4, $\mathbb E[(Z-\widehat Z)^2]$ = 0.00859

p=1/512:

b = 1, $\mathbb E[(Z-\widehat Z)^2]$ = 1.517 b = 2, $\mathbb E[(Z-\widehat Z)^2]$ = 0.223 b = 3, $\mathbb E[(Z-\widehat Z)^2]$ = 0.0444 b = 4, $\mathbb E[(Z-\widehat Z)^2]$ = 0.00982

In order to get a general formula for uniform random rotations, we can consider uniform quantization (we do at least as good as this). The bound that depends on $b,T_p$ would be $O(T_p^2 \cdot 4^{-b})$. Recall that for $p>0$ we have $T_p = \Phi^{-1}(1-p/2)$, which gives a bound in terms of $p$.

We will add this discussion to the paper.