QUIC-FL: : Quick Unbiased Compression for Federated Learning
Authors: Ran Ben-Basat
Shay Vargaftik
Amit Portnoy
Gil Einziger
Yaniv Ben-Itzhak
Michael Mitzenmacher
Venue: Submitted to ICLR 2023 (2023)
Keywords: Distirubted
Mean Estimation
Federate Learning
Quantization
Unbiased
Communication Efficient
Bandwidth Reduction
Compression

Abstract: Distributed Mean Estimation (DME) is a fundamental building block in communication efficient federated learning. In DME, clients communicate their lossily compressed gradients to the parameter server, which estimates the average and updates the model. 
State of the art DME techniques apply either unbiased quantization methods, resulting in large estimation errors, or biased quantization methods, where unbiasing the result requires that the server decodes each gradient individually, which markedly slows the aggregation time.
In this paper, we propose QUIC-FL, a DME algorithm that achieves the best of all worlds. QUIC-FL is unbiased, offers fast aggregation time, and is competitive with the most accurate (slow aggregation) DME techniques. To achieve this, we formalize the problem in a novel way that allows us to use standard solvers to design near-optimal unbiased quantization schemes.

Under review as a conference paper at ICLR 2023
QUIC-FL: QUICK UNBIASED COMPRESSION FOR FED- ERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Distributed Mean Estimation (DME) is fundamental building block in communi- cation efficient federated learning. In DME, clients communicate their lossily com- pressed gradients to the parameter server, which estimates the average and updates the model. State of the art DME techniques apply either unbiased quantization meth- ods, resulting in large estimation errors, or biased quantization methods, where un- biasing the result requires that the server decodes each gradient individually, which markedly slows the aggregation time. In this paper, we propose QUIC-FL, a DME algorithm that achieves the best of all worlds. QUIC-FL is unbiased, offers fast ag- gregation time, and is competitive with the most accurate (slow aggregation) DME techniques. To achieve this, we formalize the problem in a novel way that allows us to use standard solvers to design near-optimal unbiased quantization schemes.
INTRODUCTION
In federated learning McMahan et al. (2017): Kairouz et al. (2019). clients periodically send their gradients to the parameter server, which calculates their means. This communication is often network bottleneck, and methods to approximate the mean using small communication are desirable. The Distributed Mean Estimation problem (DME) Suresh et al. (2017) formalizes this fundamental building block as follows: each of n clients communicate representation of a d-dimensional vector to parameter server which estimates the vectors' mean.
Various DME methods have been studied (e.g., Suresh et al. (2017): Konečný & Richtárik (2018);
Vargaftik et al. (202T): Davies al. (202)) Vargaftik et al. (2022)). examining tradeoffs between the required bandwidth and performance metrics such as the estimation accuracy, learning speed, and the eventual accuracy the model.
These works utilize lossy compression techniques, using only a small number of bits per coordinate, which is shown to accelerate the training process [Bai et al. (202T): Zhong et al., (202T). For example, in Suresh et al. (2017), each client randomly rotates its vector before applying stochastic quantization. When receiving the messages from the clients, the server sums up the estimates of the rotated vectors and applies the inverse rotation. As the largest coordinates are asymptotically larger than the mean, their Normalized Mean Squared Error (NMSE) is bounded by Ô (log d n). They also propose an entropy encoding method that reduces the NMSE to ((1/n) but is slow and not GPU-friendly, A different approach to DME computes the Kashin's ' representation Lyubarskii & Vershynin (2010) of a client's vector before applying quantization Caldas al. (2018) Safaryan al. (2020). Intuitively, this replaces the input d-dimensional vector by À . coefficients, for some >> 1, each bounded by O /d) Applying quantization to the coefficients instead of the original vectors allows the
server to estimate the mean using À > bits per coordinate with an NMSE of O (VV-1)²<> How- ever, it requires applying multiple randomized Hadamard transforms, slowing down its encoding.
The recently introduced DRIVE Vargaftik et al. 2021) (which uses b = 1 bits per coordinate) and its generalization EDEN Vargaftik et al. (2022) (that works with any 6 > 0) also randomly rotate the input vector, but unlike Suresh et al. (0117) use biased (deterministic) quantization on the rotated coordinates. Interestingly, both yield unbiased estimates of the input vector after multiplying the esti- mated vector by real-valued "scale" that is sent by each client together with the quantization. Both solutions have an NMSE of (1/n)) and are empirically more accurate than Kashin's representation. However, achieve unbiasedness, each client must generate distinct rotation matrix independently

---

Under review as a conference paper at ICLR 2023
Algorithm
Enc. complexity O(d)
Dec. complexity
NMSE
Alistarb al.
2017
Onn-d d)
O(d/n)
Hadamard Suresh
2017
O(d log d)
O(n-d dlgg
Oilog d/))
Kashin Caldas et al. (2018 Salaryan et al. 2020
O(d log d log(n-d) d)
O(n + log
O[1/n)
EDEN Vargaltnk ct al. 2022
O(d log d)
O(n d (.llogd)
O(1/n)
QUIC-FL (New)
O(d log d)
O(n d + log d)
O(1/n)
Table 1:
The asymptotic guarantees of algorithms with b (1)) bits per coordinate and using the Hadamard transform for rotation based algorithms. The table does not consider variable length encodings (see Appendix
from other clients. In turn, the server must invert the rotation for each vector before aggregating them, resulting in (n) rotations instead of one, asymptotically increasing the decoding time.
Here we attempt to resolve the decoding time slowdown from these recent state of the art DME techniques Vargaftik et al. [2021] 2022). Again, this slowdown arises because unbiasing the estimates requires each client must use its own independent random rotation, and accordingly the server must invert the rotation for each quantized gradient.
In this work we present Quick Unbiased Compression for Federated Learning (QUIC-FL); DME algorithm that produces unbiased estimates, with a fast estimation procedure and an NMSE of O (1/n). QUIC-FL also leverages random rotations, and uses the observation that after rotation the coordinates' distribution approaches d i.i.d. normal variables, / (0. |0:|| Vargaftik et al. (022I). The goal of QUIC-FL is to unbiasedly quantize each coordinate while minimizing the error. Compared with Suresh et al. (2017), we present two key improvements: (1) Instead of quantizing all coordinates, allow the algorithm to send an expected p-fraction of the rotated coordinates exactly (up to precision) for some small (e.g.. P 1/512). This limits the range of the other coordinates to [-T,, where T2 O(1) for any constant p O, thus reducing the possible quantization error significantly. (2) We study how to leverage client-specific shared randomness |Ben Basat et al. (2021) to reduce the error further. Specifically, we model the problem of transmitting a "bounded -supoortt normal random variable Z ~ (0, 1) Z [-Tp, TpJ. using b E N+ bits, with the goal of obtaining an unbiased estimate at the server. Our model considers both a client's private randomness and shared randomness between the clients and server, allowing us to derive an input to optimization problem solver, whose output yields algorithms with a near-optimal accuracy to bandwidth tradeoff.
We implement QUIC-FL in PyTorch Paszke et al. (2019) and TensorFlow Abaai et al. (2015), showing that it can com- press vectors with over 33 million coordinates within 44 mil- liseconds and is markedly more accurate than existing fast- estimate approaches such as QSGD Alistarh et al. (2017).
Hadamard Kashin-TF
NMSE
10-3
Kashin QSGD
Better
EDEN
Hadamard Suresh et al. (211)). and Kashin Caldas et al. 2018);
QUIC-FL
10-4
Safaryan et al. (2020). Compared with DRIVE Vargaftik et (2021) and EDEN Vargaftik et al. (002),, QUIC-FL has only slightly worse NMSE (e.g., less than 1% for dimension) while asymptotically improving the estimation time, as shown on the right. The figure illustrates the cycle (encode plus decode) times vs. NMSE for b 4 bits per coordinate, d 22 dimensions, and n 256 clients. (see $4 for the algorithms' description.) We summarize the asymptotic guarantees of the discussed DME techniques in Table !
100 200 300 400 600 700 Enc. + Dec. time (ms)
4 bits per
We note that our algorithm is based on deriving near-optimal stochastic quantizations for specific dis- tribution by determining a mathematical program (a set of constraints) fed to an optimization program solver. We believe this approach will prove useful for other problems that use stochastic quantization.
While we have surveyed the most relevant related work above, we review other techniques in Appendix A (All appendices appear in the supplementary material.)
2 PRELIMINARIES
Problems and Metrics. Given a non-zero vector x E RR,, vector compression protocol consists of a client that computes a message X and a server that given the message estimates E Rdd The vector
=| x-22
Normalized Mean Squared Error (vNMSE) of the protocol is defined as
Vargaftik et al.
|
22021 2022
2

---

Under review as a conference paper at ICLR 2023
This problem generalizes to the Distributed Mean Estimation (DME) problem, where clients have vectors [ E R that they communicate to centeralized server. We are interested in minimizing the
=| Σ. 1e
Normalized Mean Squared Error (NMSE), defined as
Suresh et al. (2017) 7) Var
Ee 1
gaftik et al. (2021 2022), where T Fang is our estimate of the average - Le.. Note that for unbiased algorithms and independent estimates, we have that NMSE e uNMSE/ n Vargaftik et al. (0211)
Shared randomness. We use both global (common all clients and the server) and client-specific shared randomness (one client and the server). Client-only randomness is termed private randomness.
3 THE QUIC-FL ALGORITHM
3.1
Our first contribution is the introduction of bounded-snpport--unnizae (BSQ). For parameter p E (0. 1]. we pick a threshold Tр such that at most d coordinates can fall outside [-Tp. Tp BSQ separates the vector into two parts: the large coordinates whose absolute value is least Tp. and the small ones. The large values are sent exactly (matching the precision of the input gradient), whereas the small values are quantized and transmitted using a small number of bits each.
This simple approach decreases the еπтоr of every quantized coordinate by bounding the quantized coordinates' support the cost of transmitting some entries accurately. As stated Appendix G we formally show that BSQ, without further assumptions, admits a worst-case vNMSE of p-(2"- 1)
In particular, when p and b are constants, we get an NMSE of O(1/n) with encoding and decoding times of ((d) and ((nd), respectively. However, the linear dependence p means that the hidden constant in the (1/n) NMSE is too large to be practical. For example, if = 2-5 and = 1, we for sending the exact values (assuming coordinates single precision floats) and another for stochastically quantizing the remaining coordinates. In turn, we get a vSN bound of 2-5.(21-1)
need two bits per coordinate on average:
32. In the following section, we show that combining BSQ
with random rotation allows us to get ((/nn) NMSE even with a low constant for low values of p. For example, p = 2-9 and an additional one bit per coordinate for the quantization, we reach a uN of 1.52, 21 improvement despite using less bandwidth.
3.2 ROTATIONS WITH BOUNDED SUPPORT QUANTIZATION
Similarly previous works Suresh al. 2017); Vargaftik al. 2022 2022), our algorithm QUIC-
FL begins by randomly rotating the input vector, after which the coordinates' distribution approaches independent normal random variables for high dimensions Vargaftik al. (2021). This effectively
turns every input into the average case. We note that, unlike Vargattik et al. (2021 2022) all clients use the same rotation, generated with global shared randomness. QUIC-FL then utilizes near-optimal unbiased quantization for the normal distribution for each coordinate. We emphasize that QUIC-FL unbiased for any input; the quantization is tuned for the normal distribution, as after rotation each Unlike previous algorithms, we combine
coordinate it is well-approximated by a normal distribution! [ the rotation with bounded support quantization. QUIC-FL achieves unbiasedness using both private randomness at the client and client-specific shared randomness (shared between it and the server).
As another comparison point, Suresh et al. (0117), given a bit budget of 6(1 + o()) bits per packet, stochastically quantizes each rotated coordinate into one of 2" levels. The algorithm uses max-min normalization, and the levels are uniformly spaced between the minimal and maximal coordinates. Their algorithm then communicates the max and min, together with b bits per coordinate indicating its quantized level, and is shown to have a NMSE of O (log d/n) for any b 0(1).
We begin by analyzing the value of rotation with BSQ. Let Z /O, 1) be normal random variable, modeling a rotated (and scaled) coordinate. Given a defr-de parameter p. we can compute a
For any fixed dimension. we can optimize the quantization (using the solver) for its exact rotated coordinate distribution (known to be a shifted-heta). However, this would require different quantization for each dimension. The difference using normal distribution is negligible, even with dimensions in the hundreds.
3

---

Under review as a conference paper at ICLR 2023
threshold Tp such that Pr I-Tp. T, p 0.2%) we get a threshold of 7 3.097
p. For example, by picking 2-9 (i.e., less than
In general, for any constant p O, have Tр is constant, and using b bits for each coordinate
in -TppTp) we get a NMSE of (1/n) for any constant b (due to unbiased and independent
quantization among clients). For example, consider sending each coordinate in [-Tp, p: TpI using b = 1 bit per coordinate. One solution would be to use stochastic quantization, i.e., given a coordinate Z+T₂ Z E [-Tp, Tpl send the bit for which - = Tp with probability 27, and the bit for å = -Tp otherwise. This quantization results in an unbiased estimate with expected squared error of
E (z - 2)²|
T
2 + Tp
(= - (z-T))²
Tp - (2 (++ 2I,
dz.
2m -Tp
2I,
With p-2- as above, we get E 2)- 88.58. We can view the algorithm expressed so far as a special case of QUIC-FL without shared randomness.
As shown in Appendix B for QUIC-FL (with or without shared randomness) on any d- dimensional input vector (and any quantization scheme for Z [-Tp, TpD) wNMSE
[<-2)² +0 mize for the normal distribution" Again, this holds for any initial vector because QUIC- FL starts with random rotation. Thus, using the above quantization for each coordi- nate for large gradients results in NMSE x 8.58/n. We next show that additionally using client-specific shared randomness can decrease E[ 2 and thus the NMSE.
(v logd
(Vorg))
The additional additive term occurs because we chose to opti-
3.3 LEVERAGING CLIENT-SPECIHE SHARED RANDOMNESS
We now provide an example to show how shared randomness can improve the uNMSE, leading to $3.4 where we formalize our approach to finding near-optimal unbiased compression schemes for bounded-support. (0, variables. Using single shared random bit (i.e., H E {0, 1)). we can
the following algorithm, where X is the sent message and 0.8, B 5.4 are constants:
if H 0 and Z 3 0
B
if I1 X =
x
0
Bernoulli( 27 04.
if H 1 and Z < and Z >
2
a
if H = 1 and X =0
If = 0 and X =
Bernoulli 22
and Z <
3 If = =1
For example, if Z 1, then with probability 1/2 we have that H 0 and thus X 1. and otherwise - the client sends X with probability o-B (and otherwise X 0). Similarly, the reconstruction
would be 2 with probability 1/2 (when H 0), 2 3 with probability 1/2 a+ 0.16, and Ż with probability 1/2
a+8-2 0.84. Indeed, we have that the estimate is unbiased since:
a+3
E 2 Z = 1] = a 1/2 3 1/2 a 8 + (-a) 1/2. a a 3-2
a.
1.
a+
We calculate the quantization's expected squared error, conditioned on E [-Tp; (From symmetry, we integrate over positive (.)
E (z 2) 222
To 2 (1'1
(1= a))=
(z 15-33 3) a 3-22 (z (z+ a)²)
-c -
Using the same = parameter (I, 2 3.097), we get an error of E (Z 2) ~ 3.29, 61% lower than without shared randomness. This algorithm is derived from the solver, which numerically approximates the optimal unbiased algorithm with a single shared random bit, in terms of expected squared error, for this p. We present our general approach for using the solver in the following sections.
Note that, as we begin with normal random variable Z, bounding its support is effective removing the long, proallprobability tails. Additionally, as the learning process typically uses 16-64 bit floats, and we further need to send the coordinate indices, sending each coordinate is expensive, and thus we focus on small values.
If instead we were quantizing shifted-heta random variable B, we would get uNMSE = E. B 9
4

---

Under review as a conference paper at ICLR 2023
3.4 DESIGNING NEAR-OPTIMAL UNBIASED COMPRESSION SCHEMES
In order to design post-rotation compression scheme, first model the problem follows:
We first choose parameter p > 0, the expected fraction of coordinates allowed to be sent exactly. The input, known to the client, a coordinate Z ~ (0, 1). The parameter restricts further the distribution to Z [p Tp]-
The client-specific shared randomness H is known to both the client and server, and without loss of generality, we assume that H U|O 1J. We denote by H [0. 1J the domain of H.
We use bit budget of b E N bits per coordinate, and accordingly assume that the messages in the set Xr = {0..... .,. 2 - 1 Again, coordinates outside the range [-Tp. Tpl are sent exactly,
The client is modeled as S H x R A(K)). That is, the client observes the shared randomness H and input Z, and chooses a distribution over the messages. We further denote by 5 (h, 2) the probability that the client sends E X2 given h and (i.e., vh, Σx Sz
1). For
example, may choose (0, 1//2
If E {0, 1] That is, given
0
0, the client shall
Otherwise
use private randomness to decide whether to send r = or a = 1, each with probability 1/2.
The server is modeled as function H x Ar, - IR, such that if the shared randomness is h H. and the server receives the message E Xg. it produces an estimate 2 2),,
We require that the estimates unbiased, i.e., E[ Z] Z, where the expectation is taken over both the client-specific shared randomness H and the private randomness of the client.
We ready formally define the optimal unbiased quantization problem:
Tr
minimize S,
(h,
R(h, x:)) - dh dz
2T
-Tp 30
S Sch,2) R( dh
subject to
Ve E I-Tp,,
We are unaware methods for solving the above problem analytically. Instead, we propose a discrete relaxation of the problem, allowing us to approach it with solver Namely, we model the algorithm as an optimization problem and the solver output the optimal algorithm. To that end, we need to discretize the problem. Specifically, we make the following relaxations:
The shared randomness is selected uniformly at random from a finite set of values Hy 20 1}. i.e., using shared random bits.
The bounded-support distribution of rotated and scaled Z (0, 1) coordinate is approximated using a finite set of quantiles 2m = the quantile qi the point on the CDF of the bounded-support normal distribution (restricted to [-Tp, TxI) such that the Pr[Z &
4m-1) for a parameter m e N+. In particular,
E [.T.p. = m-1 Notice that we have m such quantiles, corresponding the probabilities {0. m-II m
For example, p 2- and 4 we get the quantile set Q4 {-3.097, -0.4998 0.4298, 3.097].
The client is now modeled S He Qm A(X)) That is, for each shared randomness h E He and quantile E Qm. values, the client has a probability distribution on the messages from which samples, using private randomness, at encoding time.
The server modeled as function R H, X, R, such that the shared randomness H and the server receives the message it produces an estimate 2 R TR,HH X).
Given this modeling, we use the following variables:
'We note that using entropy encoding, one may resulting entropy bounded by (e.g..Suresh
than 2 messages (and thereby reduce the error) the
Suresh al. (201) Vargaftik et al. (2022 Alistarh et al. (2017). As aim to design quick and GPÜ-friendly compression scheme, we not investigate entropy encoding further. 'We used the Gekko Beal et al. (2018) software package that provides a Python wrapper to the APMoni- tor Hedengren al. 2014) environment, running the solvers IPOPT APOPTAPO.
5

---

Under review as a conference paper at ICLR 2023
(sh.g.z h He, qe Qm: 2 X,,, where Sh.q.z denotes the probability of sending message 2, given the quantile and shared randomness value h. We note that the solver's solution will only instruct what to do if all our coordinates were quantiles in Qm In what follows, show how to interpolate the result and get practical algorithm for any E [-Tp:Tp)
r r= frh, h E He, E ), where Th,z denotes the server's estimate value given the shared randomness and the received message x.
Accordingly, the discretized unbiased quantization problem is defined as:
minimize subject to (Unbiasedness)
1
Σ
Sh.ga (q Th,x)
2
hig.a
2
Σ
Shugae Thi q
1/
b,
(Probability)
Σ
Shiq.z
vh.
$0.ga
2 0,
vh. q.
As mentioned, the solver's 's output does not directly yield an implementable algorithm, as it only associates probabilities each (h, q, .)) tuple. natural option is to first stochastically quantize Z to quantile. For example, when Z = 1 and using the Q4 described above, before applying the algorithm, we quantize q 0.4298 with probability > 0.786 q² 3.097 with probability 0.214.
This approach gives algorithm whose pseudo-code is given in Algorithm algorithm is near-optimal in the sense that as the number of quantiles and shared random bits tend to infinity, we converge to an optimal algorithm. In practice, the solver is only able to produce an output for finite m, values; this means that the algorithm would be optimal if coordinates are uniformly distributed over Qm. and not in (0, 1).
The resulting
In words, in Algorithm D each client e uses shared randomness to compute global random rotation R (note that all clients use the same rotation). Next, computes the rotated vector R (I:e); for sufficiently large dimensions, the distribution of each entry in Ze converges to N (0, | The
client then normalizes it, Z = Vd Te
R (xt), to have the coordinates roughly distributed (o 1).
Next, it stochastically quantizes the vector to 2m. Namely, for given coordinate Z, let q q= Qm denote the largest quantile smaller equal to Z. and the smallest quantile larger than respectively. Then we denote by (2) the stochastic quantization operation that returns q* with probability Z-o and q otherwise. The stochastic quantization of the vector applies coordinate-we wise, i.e., 6 -T-9-
(Z.) = (Q.. [0], Q. [d 1])). The next step is to generate a client- -peeenfc shared randomness vector H. in which each entry is drawn uniformly and independently from He. Finally, client follows the client algorithm produced by the solver. That is, for each coordinate Z, the client takes the mapped quantile 2m (Z) Qm. considers the set of probabilities (sh.g.z E X,,, and samples message accordingly. We denote applying this operation coordinate-wise by X. a with prob. 2....... E X It then sends the resulting vector X. to the server, together with the norm | In turn, for each client c, the server estimates its rotated vector by looking up the shared randomness and message for each coordinate. That is, given H. = [H] Hald 1J) and X_ = (X.[0)..... X [ddd11) we denote 'H.,x. = (' ('H..o)_... [o] [
The server then estimates
Rxxx) as (IlEel/ /Vd TH..x.) and averages across all clients before performing the inverse rotation. In the next section, we analyze the solver's output and show how to improve this method.
Further optimization different approach to yield an implementable algorithm from the optimal solution to the discrete problem is to calculate the message distribution directly from the rotated values without stochastically quantizing as we do in Line Indeed, we have found this approach to be somewhat faster and more accurate. Due space constraints, defer the details Appendix C

---

Under review as a conference paper at ICLR 2023
Algorithm 1
Client
Server:
1: Compute Z. ||
vi
(xa).
1: Ve Compute Ze MaiX=
2: Stochastically quantize Z. (Z,) (Za)
2: Compute Zary = 1 - ||oell2 Zo.
3: Sample X {o with prob. 20.2 x N6.
3: Estimate Fuvg R- (Z (Zay)
4: Send (11zell2 Xe) to server
eMMSD
10
10
NMSE
0.5
0.6
10
10-1
10-2
5
2
2
Bit Budget (b)
Accuratly sent coordiantes (p)
Shared random bits (E)
Figure 1: The uNMSE of QUIC-FL function of the bit budget, fraction p, and shared random bits
3.5 HADAMARD
Similarly to previous rotation-based compression algorithms (Suresh al. (2017); Vargaftik al. (2021, 2022) we propose to use the Randomized Hadamard Transform (RHT) (Ailon & Chazelle 2009) instead of uniform random rotations. Although RHT does not induce uniform distribution on the sphere (and the coordinates are not exactly normally distributed), it is considerably more efficient to compute and, under mild assumptions, the resulting distribution is sufficiently close the normal distribution Vargaftik et al. (2021). Here, we are interested in how using RHT affects the guarantees of our algorithm. We analyze how using RHT affects our guarantees, starting by noting that our algorithm remains unbiased for any inpul vector. However, adversarial inputs may (1) increase the probability that a rotated coordinate falls outside [-Tp. Tp] and (2) increase the vNMSE as the coordinates' distribution deviates from the normal distribution. We show in Appendix D that QUIC-FL with RHT has similar guarantees as with random rotations, albeit somewhat weaker (constant factor increases still
in the fraction of accurately sent coordinates and vNMSE). We note that these guarantees stronger than those of DRIVE Vargaftik et al. (202T) and EDEN Vargaftik et al. (2022), which only prove RHT bounds for input vectors whose coordinates are sampled i.i.d. from a distribution with finite moments, and are not applicable to adversarial vectors. In practice, as shown in the evaluation, the actual performance is close to the theoretical results for uniform rotations; improving the bounds left as future work. In our evaluation, we use QUIC-FL (Algorithm 2 with RHT-based vector rotation.
4 EVALUATION
4.1 THEORETICAL EVALUATION: NMSE AND SPEED MEASUREMENTS
Parameter Selection. We experiment with how the different parameters (number of quantiles m, the fraction of coordinates sent exactly p, the number of shared random bits E, etc.) affect the performance of our algorithm. As shown Figure introducing shared randomness decreases the =NMSE significantly compared with & 0. Additionally, the benefit from adding each additional shared is negligible, especially for large b. Accordingly, for 1, l 5 for b 2. and
random bit diminishes, and the gain beyond we hereafter use determined 512 as a good balance between the eNMSE and bandwidth overhead.
for E {3. 4]. With respect to p,
Comparison to state of the art DME techniques. Next, compare the performance of QUIC-FL to the baseline algorithms in terms of NMSE, encoding speed, and decoding speed, using an NVIDIA com-
3080 RTX GPU machine with 32GB RAM and 17-10700K CPU @ 3.80GHz. Specifically, pare with Hadamard Sureehh et al. 2017). Kashin's 's representation Caldas et al. (2018); Safaryan et al. (2020), QSGD Alistarh al. 2017), and EDEN Vargaftik et al. 2022). We evaluate variants of
7

---

Under review as a conference paper at ICLR 2023
10
Dec (ms)
10
Dec. (ms)
10
10
NMSE
10"2
NIASE
10
10
10
10
10-3
10"
100
10-4
10
20
2
2
20 2222222222232222
222 2
Bit budget (b)
Num. Clients (n)
Num. Clients (n)
Dimension (d)
Dimension (d)
*
Hadamard
Kashin-TF
Kashin
QSGD
EDEN
QUIC-FL
Figure 2: Comparison to alternatives with n clients that have the same Log LogNorrun LogNormal(O, 1) input vector Vargaftik
al. 2021 2022 The default values 256 clients, 4 bit budget, and d = 2 dimensions.
Kashin's 's representation: (1) The TensorFlow (TF) implementation AAthhrss that. by default, limits the decomposition to three iterations, and (2) the theoretical algorithm that requires (log(nd iterations. As shown in Figure 2 QUIC-FL has the second-lowest NMSE, slightly higher than EDEN's, which has a far slower decode time. Further, QUIC-FL is significantly more accurate than approaches with similar speeds. We observed that the default TF configuration of Kashin's representation suffers from a bias, and therefore its NMSE' does not decrease inversely proportional to n. In contrast, the theoretical algorithm unbiased but has a markedly higher encoding time. We observed similar trends for different n, b, and d values. We consider the algorithms' bandwidth over all coordinates (e.g.. with bits for QUIC-FL). Overall, the empirical measurements fall in line with the bounds in Table
b 512
bit
2 bits
bits
bits
2.6
0.6
0.6
0.6
Accuracy
0.5
0.3
0.4
0.4
0.4
0.3
0.3
250
500
750
1000
1250
250
500
750
1000
1250
250
500
750
1000
1250
250
500
750
1000
1250
Accuracy (coom)
0.00
0.600
0.000
0.595
0.598
0.58
0.590
0.596
0.56
0.585
0.94
Float32
Hadamard
Kashin-TF
QSGD
EDEN
QUIC-FL
Figure 3: FedAvg over the Shakespeare next-word prediction task at various bit budgets (rows). We report training accuracy per round with rolling window of 200 rounds. The second row zooms in the last 100 rounds (QSGD not included in the zoom since it performed poorly).
4.2 FEDERATED LEARNING EXPERIMENTS
Next-word prediction. We evaluate QUIC-FL the Shakespeare next-word prediction task Shakespeare McMahan et al. (2017) using an LSTM recurrent model. We run FedAvg McMahan al. (017)) with the Adam server optimizer Kingma Ba 2015) and sample round. We use the setup from the federated learning benchmark of Reddi et al. (202T). restated for convenience
10 clients per
Appendix E Figure 3 shows how QUIC-FL compares with other compression schemes at various bit budgets. As shown, QUIC-FL is competitive with EDEN and nearly matches the accuracy of the uncompressed baseline for >
Image classification. We evaluate QUIC-FL against other schemes with 10 persistent clients over
uniformly distributed CIFAR-10 and CIFAR-100 datasets Krizhevsky et al. (2009). We also evaluate Count- Sketch Charikar al. (2002) (CS), often used for federated compression schemes (c.g.. Ivkin ctt al. (2019)). For CIFAR-I0 10 and CIFAR- 100, we use ResNet-9 He et al. (2016) and ResNet- 18 He al. 2016), with learning rates of 0.1 and 0.05, respectively. For both datasets, the clients perform a single optimization step at each round. Our setting includes an SGD optimizer with a cross entropy loss criterion, batch size of 128, and bit budget
The results are shown in Figure with a rolling mean average window of 500 rounds. As shown, QUIC-FL. is competitive with EDEN and the Float32 baseline and is more accurate than other methods.
8

---

Under review as a conference paper at ICLR 2023
CIFAR-10- Zoom-In
CIFAR-100
CIFAR-10 Zoom-In
.85
653
0.6
Tes:
0.8
0.7
0.4
.96
.61 -8
3500
7000
6500
6750
7000
3000
6000
8000
8000
8500
CIFAR-10 10
CIFAR-IB 10 Zoomn-l In
CIEAR 100
CIEAR: 100 Zoom- In
1.0
1.0
Town
0.8
986
9985
0.5
9975
3500
7000
6500
6750
7000
3000
6000
9000
6000
8500
9000
Float32
Hadamard
Keshin-TP
EDEN
CS
QUIC-FL
Figure 4: Train and test accuracy for CIFAR-IO and CIFAR-100 with 10 persistent clients (i.e., silos) and & 1.
MNIST
MNIST Zoom-In
CIFAR-10
CIFAR-10- Zaoe=In
0.9
Tes:
Acenvay
0.3
0.8
0.8
965
.89
0.7
.88
2001
400
530
330
460
650
1000
2000
3000
4000
3000
3500
4000
MNIST
MNIST Zooon-In
CIEAR-10
CIFAR-10 Zooe-Io
1.100
Thain Aveunay
0.975
00
5075
0.960
0.75
985
985
200
400
$50
350
460
550
1000
2000
3000
4000
9000
3500
4000
Floxt32
Hadamard
Kashin-TT TF
EDEN
CS
QUIC-FL
Figure 5: Cross-device federated learning of MNIST and CIFAR- 10 with 50 clients (b = 1).
Next, we consider highly heterogeneous cross-device setup with 50 clients over MNIST and CIFAR- 10 datasets Krizhevsky et al. (2009); LeCun et al. [1988] 2010). For MNIST, each client stores only a single class of the dataset and trains LeNet-5 CIFAR- 10, all clients have the same data distribution, and each trains ResNet-9 He et al. 2016) with learning rate of 0.1. At each training round, 10 clients are randomly selected and perform training over 5 local steps. We use an SGD optimizer with a cross entropy loss criterion, batch size of 128, and bit budget
et al. 1998) with a learning rate of 0.05. For
Figure shows the results with rolling mean window of 200 rounds. Again, QUIC-FL is competitive with EDEN and the uncompressed baseline. Kashin-TF is less accurate followed by Hadamard.
Additional evaluation Due to lack of space, we defer additional evaluation results to Appendix
5 DISCUSSION
In this work, we presented QUIC-FI, quick unbiased compression algorithm for federated learning. Both theoretically and empirically, QUIC-FL achieves an NMSE that is comparable with the most accurate DME techniques, while allowing an asymptotically faster decode time.
We point out a few challenging directions for future work. QUIC-FL optimizes the worst-case error, and while it is compatible with orthogonal directions such sparsification Konečný & Richtárik (2018); Vargaftik et al. (2022): Konečný et al. (2017); Fei et al. (2021). it is unclear how would leverage potential correlations between coordinates Mitchell et al. (2022) or client vectors Davies ctt al. (20TT). Another direction for future research is understanding how to incorporate non-lincer aggregation functions, such approximate geometric median, that have shown to improve the training robustness [Pillutla et al. (2022).
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Advanced Process OPTimizer (APOPT) Solver. http::/s//gtttu..ccoco/oooooo/op
Interior Point Optimizer (IPOPT) Solver. httpo://ecainoo.gggttt...oo/////
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals. Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large-Scale Machine Learning Heterogeneous Systems, 2015. URL https: /www www.orflww...o.......... org/ from tensorflow.org.
Software available
Nir Ailon and Bernard Chazelle. The Fast Johnson-Lindenstraan Transform and Approximate Nearest Neighbors. SIAM Journal on computing. (0(1):302-322, 2009.
Alham Fikri Aji and Kenneth Heafield. Sparse Communication for Distributed Gradient Descent. In Proceedings of the 2017 Conference on Empirical Methods Natural Language Processing, pp. 440 445, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- Efficient SGD via Gradient Quantization and Encoding. Advances in Neural Information Process- ing Systems, 30:1 700-11777, 2017.
Dan-Adrian Alistarh, Torsten Hoefler, Mikael Johansson, Nikola H Konstantinov, Sarit Khirirat, and Cedric Renggli. The Convergence of Sparsified Gradient Methods. Advances in Neural Information Processing Systems, 31, 2018.
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and Optimal LSH for Angular Distance. In Proceedings of the 28th International Conference on Neural Information Processing Systems, pp. 1225-1233. 2015.
The TensorFlow Authors. TensorFlow Federated: Compression via Kashin's representatiio from zation/
Hadamard transform. httpps////ttthsccce//////rrrrrrr
model httpp//o....taaaaaa//oc/ooooo/aa tesearch/kashin.pyyt
wwc.rrrrnncnnnnneeeeeeeeeee.eeee stages/
accessed 19-May-22.
Youhui Bai, Cheng Li, Quan Zhou, Jun Yi, Ping Gong, Feng Yan, Ruichuan Chen, and Yinlong Xu. Gradient compression supercharged high-performance data parallel dnn training. In The 28th ACM Symposium on Operating Systems Principles (SOSP 2021), 2021.
Logan Beal, Daniel Hill, R Martin, and John Hedengren. Gekko optimization suite. Processes, 6(8): 106, 2018. doi: 10.3390/p66080106
Ran Ben Basat, Michael Mitzenmacher, and Shay Vargaftik. How to send a real number using single bit (and some shared randomness). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 2021.
Vidmantas Kastytis Bentkus and Dainius Dzindzalieta. A tight gaussian bound for weighted sums of rademacher random variables. Bernoulli, 21(2):1231 2015.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On Biased Compression For Distributed Learning. arXiv preprint arXiv:2002. 12410 2020.
Sebastian Caldas, Jakub Konečný, H Brendan McMahan, and Ameet Talwalkar. Expanding the Reach of Federated Learning by Reducing Client Resource Requirements. arXiv preprint 1812. 10, 2018.
10

---

Under review as a conference paper at ICLR 2023
Moses Charikar, Kevin Chen, and Martin Farach- Colton. Finding frequeet items in data streams. In International Colloquium on Automata, Languages, and Programming, pp. 693-703. Springer, 2002.
Peter Davies, Vijaykrishna Gurunanthan, Niusha Moshrefi, Saleh Ashkboos, and Dan Alistarh. New Bounds For Distributed Mean Estimation and Variance Reduction. In International Confer- ence on Learning Representations, 2021. URL https:://operreeeee t E86MwoUCCNe:
net www.:neetfforree forum?id
Jiawei Fei, Chen- Yu Ho, Atal N Sahu, Marco Canini, and Amedeo Sapio. Efficient Sparse Collective Communication and its Application to Accelerate Distributed Deep Learning. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference, pp. 576-691, 2021.
Eduard Gorbunov, Konstantin P. Burlachenko, Zhize Li, and Peter Richtarik. MARINA: Faster Non-Convex Distributed Learning with Compression. In Proceedings of the 38th International Conference Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. PMLR, 18-24 Jul 2021. URL https: http::///pprcceednggg.
gorbunov2 html
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
John D. Hedengren, Reza Asgharzadeh Shishavan, Kody M. Powell, and Thomas F. Edgar. Nonlinear modeling, estimation and predictive control in APMonitor. Computers & Chemical Engineer- ing. 70:133 148, 2014. ISSN 0098- 1354. doi: com//sciienn///rrriile//iiiiiii
2014.04.013. URL http: /wwww seciencediree rect. com/
S0C981 3541400114355
Manfred Morari Special Issue.
S. Hochreiter and J. Schmidhuber. Long Short-Term Memory. Neural Computation, 9:1735-1780, 1997.
Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Vladimir Braverman, Ion Stoica, and Raman Arora. Cammuunicaaion-.fffieeee Distributed SGD With Sketching. Advances in neural information processing systems, 2019.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafacl G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh. Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song. Weikang Song. Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma,, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang. Felix X. Yu, Han Yu, and Sen Zhao. Advances and Open Problems in Federated Learning, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In International Conference on Learning Representations, 2015.
Jakub Konečný and Peter Richtárik. Randomized Distributed Mean Estimation: Accuracy vs. Communication. Frontiers in Applied Mathematics and Statistics, 4:62, 2018.
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and
Dave Bacon. Federated Learning: Strategies for Improving Communication Efficiency, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning Multiple Layers of Features From Tiny Images. Master's 's thesis, University of Toronto, 2009.
ChonLam Lao, Yanfang Le, Kshiteej Mahajan, Yixi Chen, Wenfei Wu, Aditya Akella, and Michael Swift. ATP: In-network Aggregation for Multi-tenant Learning. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2/), pp. 741-761, 2021.

---

Under review as a conference paper at ICLR 2023
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Sradient-Basedd Learning Applied to Document Recognition. Proceedings of the IEEE, 86(11):227-223 23244, 1998.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://ynn.leccm lecun. www.:/wwwwnu....m..m.. www.exdb////iiit.....mmmmmm. 2, 2010.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training. In International Conference on Learning Representations, 2018.
Yurii Lyubarskii and Roman Vershynin. Uncertainty Principles and Vector Quantization. IEEE Transactions on Information Theory, 56(7):349-33011 2010.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication Efficient Learning of Deep Networks from Decentralized Data. In Artificial Intelligence and Statistics, pp. 1282, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed Learning With Compressed Gradient Differences. arXiv preprint arXiv:1901.09200 2019.
Nicole Mitchell, Johannes Ballé, Zachary Charles, and Jakub Konečný. Optimizing the communication-accurayy trade-off in federated learning with rate-distortion theory. arXiv preprint arXiv:2201.02664, 2022.
Mervin E Muller. A Note Method for Generating Points Uniformly on N-Dimensional Spheres. Communications of the ACM, 2(4):19-22) 20, 1959.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An Imperative Style, PeghoPerformance Deep Learning Library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gamett (eds.), Advances in Newral Information Processing Systems 32, pp. 8026-8037. Curran Associates, Inc., 2019. URLhttp: http::::pppapp...peeeee wwwaapers.iiigs nips cc/paper 9015 pytorch an. aan.-immpratiiie style high www.frrrfrncce.eee deep learning library. pdf
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 70:1 10:1142-1154, 2022.
Ali Kamezani-Kebrya Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M Roy. Nuqsgd: Provably communication-efficeen data-parallel sgd via nonuniform quantization. Journal of Machine Learning Research, 22(1 14):1-43, 2021.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive Federated Optimization. In International Conference Learning Representations, 2021. httpt:::t//ppeeeeeeeeee wtt.oo/wwwwtetetemtnmmmm forum?
id [dd=LFF33B113S
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A New, Simpler, Theoreti- cally Better, and Practically Faster Error Feedback. In Advances in Neural Information Processing Systems, 2021. URL ltttps://paperss nips .ys.co cc//paper//22//Eilee
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication compres- sion in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA, 2020.
Amedeo Sapio, Marco Canini, Chen- Yu Ho. Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan Ports, and Peter Richtarik. Scaling Distributed Machine Learning with In-Network Aggregation. Design and Implementation (NSDI 2/), pp. 785-808, 2021.
18th USENIX Symposium on Networked Systems
12

---

Under review as a conference paper at ICLR 2023
Raz Segal, Chen Avin, and Gabriel Scalosub. SOAR: Minimizing Network Utilization with Bounded In-network Computing. In Proceedings of the 17th International Conference on emerging Net- working EXperiments and Technologies, pp. 16-29, 2021.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-Bit Stochastic Gradient Descent and Its Application to Data-Parallel Distributed Training of Speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
William Shakespeare. The Complete Works of William Shakespeare, httteespeare.tttsss....
org/ebooks/100
Sebastian U Stich, lean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with Mem- ory. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Asso- ciates, Inc., 2018a. URL httptts:////oteeetttteeeeeeeeeee mewreddiiiinnnnnnnssneee.eee.irr neurips....... htt.iiss.cccppeeeee httppp/pppp///////eeeeeeee b350599900TT003eea///caaaaaaaaa2 Paper, pdf
Sebastian U Stich, Jean- Sanntttt Cordonnier, and Martin Jaggi. Sparsified sgd with memory. Advances in Neural Information Processing Systems, 31, 2018b.
Ananda Theertha Suresh, X Yu Felix. Sanjiv Kumar, and H Brendan McMahan. Distributed Mean Estimation With Limited Communication. In International Conference on Machine Learning, pp- 3329-3337. PMLR, 2017
Ananda Theertha Suresh, Ziteng Sun, Jae Hun Ro, and Felix Yu. Correlated quantization for distributed mean estimation and optimization. In International Conference on Machine Learning, 2022.
Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben-Itzhak, and Michael Mitzenmacher. DRIVE: One-bit Distributed Mean Estimation. In NeurIPS, 2021.
Shay Vargaftik, Ran Ben Basat, Amit Portnoy, Gal Mendelson, Yaniv Ben- Biz-kk and Michael Mitzenmacher. EDEN: Communication Effmuuiiation-EEfiiient and Robust Distributed Mean Estimation for Federated Learning. In International Conference Machine Learning, 2022.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivar, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A Field Guide to Federated Optimization. arXiv preprint 107.022007.0691,, 2021.
Felix Xinnan X Yu, Ananda Theertha Suresh, Krzysztof Choromanski, Daniel N Holtmann-Rice and Sanjiv Kumar. Orthogonal Random Features. Advances in neural information processing systems, 29:1975-1983 2016.
Yuchen Zhong, Cong Xie, Shuai Zheng, and Haibin Lin. Compressed communication for distributed training: Adaptive methods and system, arXiv preprint arXiv:2105.07822 2021.
13

---

federated learning, where there Under review as a conference paper at ICLR 2023
A ALTERNATIVE COMPRESSION METHODS
This paper focused the Distributed Mean Estimation (DMB) problem where clients send lossily compressed gradients to a centralized server for averaging. While this problem is worthy of study on its own merits, we particularly interested in applications are many variations and practical considerations, which have led to many alternative compression methods to be considered. For example, when the encoding and decoding time is less important, different approaches suggest to use entropy encodings such as Huffman or arithmetic encoding to improve the accuracy (e.g.. Suresh et al. (2017); Vargaftik et al. (2022): Aliisarr et al. (2017)) Intuitively, such encodings allow to losslessly compress the lossily compressed vector to reduce its representation size, thereby allowing less aggressive quantization. However, we are unaware of available GPU- Pfrreddeyyly entropy encoding implementation and thus such methods incur significant time overhead.
Critically, for the basic DME problem, the assumption is that this is a one-shot process where the goal is to optimize the accuracy without relying on client-side memory. This model naturally fits cross-device federated learning, where different clients are sampled in each round. We fo- cused on unbiased compression, which is standard in prior works [Suresh et al. (2017); Konečný & Richtárik (2018); Vargaftik et al.] (2021); Davies et al. (2021); Mitchell et al. (2022). How- ever, if the compression error is low enough, and under some assumptions, SGD can be proven to converge even with biased compression Beznosikov et al. (2020).
In other settings, such as distributed learning or cross-silo federated learning, we may assume that clients are persistent and have memory that keeps states between rounds. prominent option to leverage such a state is to use Error Feedback (EF). In EF, clients can track the compression error and add it to the gradient computed in the consecutive round. This scheme often shown to recover the model's 's convergence rate and resulting accuracy [Seide et al. (2014); Alistarh et al. (2018): Richtárik
ct al. (02T) and enables biased compressors such as Top- Stich Stich et al. (2018)).
An orthogonal proposal that works with persistent clients, which is also applicable with QUIC-FL, to encode the difference between the current gradient and the previous one, instead of directly compressing the gradient Mishchenko et al. 2209);; Gorbunov et al. (202I). Broadly speaking, this allows a compression error that is proportional to the size of the difference and not the gradient, and can decrease the error if consecutive gradients are similar each other.
When running distributed learning in cluster settings, recent works show how in in-network aggregation can accelerate the learning process Sapio et al. 12021: Lao et al. (202 :[Segal et al. (202I). Intuitively, as switches are designed to move data at high speeds and recent advances in switch programmability
enable it easily perform simple aggregation operations like summation while processing the data.
Another line of work focuses on sparsifying the gradients before compressing them Fei et al. (2021 : Stich al. (2018): Aji & Heafield (2017). Intuitively, in some learning settings, many of the coordinates are small. and we can improve the accuracy to bandwidth tradeoff by removing all small coordinates prior compression. Another form of sparsification random sampling, which allows us to avoid sending the coordinate indices Vargaftik et al. (2022); Konečný et al. (2017). We note that combining such approaches with QUIC-FL is straightlorward, as we can compress the non-zero entries of the sparsified vectors.
Combining several techniques, including warm-up training, gradient clipping, momentum factor masking, momentum correction, and deep gradient compression Lin et al. (2018), reports savings of two orders of magnitude in the bandwidth required for distributed learning. Another promising orthogonal approach is to leverage shared randomness to get the clients' compression to yield errors in opposite directions, thus making them cancel out and lowering the overall NMSE Suresh et al. (2022).
The QUIC-FL algorithm, based on the output of the solver (see $3). uses non-uniform quantization, i.c., has quantization levels that are not uniformly spaced. Indeed, recent works observed that non-uniform quantization improves the estimation accuracy and accelerates the learning convergence Vargaftik
et al. 2022);;
Beinezani-Kebbyae et al. (2021)
We refer the reader to Kairouz et al. (2019) Konečný et al. (2017): Wang et al. 2021 for an extensive review of the current state of the art and challenges.
14

---

Under review as a conference paper at ICLR 2023
B QUIC-FL'S uNMSE PROOF
In this appendix, analyze how the expected squared quantization error for bounded support normal random variables relates to the uNMSE of our algorithm. Namely, let X = E z 2)
denote the error of the quantization of normal random variable Z No, 1). Our analysis is but is applicable any unbiased method that used following a uniform random rotation. We show that QUIC-FL's vNMSE is essentially X plus a small additional additive error term (arising because the rotation does not yield exactly normally distributed coordinates, as we have explained) that goes to quickly as the dimension increases. We bound the additional error caused by using the Randomized Hadamard Transform in Section 3.5 and Appendix D
general, covers the quantization methods presented in sections B.2 3.3
Theorem 1. It holds that:
log d
UMME & E
Proof. The proof follows similar lines to that Vargaftik et al. (2021) 2022). However, here the uNMSE expression is different and is somewhat simpler it takes advantage of our unbiased quantization technique.
A rotation preserves a vector's euclidean norm. Thus, according to Algorithms 1 and 2 it holds that
|| 212 || (x
1) 7
R (x)
R
(2)
||0|||2
||0||2
Ž
|
2
2 2
7
7
vd
vd 2
d
Taking expectation and dividing by ||01| yields
|
$
2
Ž11
NMSE + E
E
Z
||
(2)
7111 2
Σ E 7 [11 2
E
=
d
Let 2 = (2,,..., -a) be vector of independent (NO, 1) random variables. Then, the distribution of 2 (e.g., see Vargaftik et al. 2021) y Muller 1959)).
each coordinate Z[i] is given by ž|:] vd-
This means that all coordinates of Z and thus all coordinates of follow the same distribution. Thus, without loss of generality, obtain
NMMS + E
| 2
E
22110)-2101)
[Z|0]
'|
Vd
2
2/111 3711
(3)
||0]| 1
For some 0 < 2, denote the event
A = d. < [=]
d (1 (1+a))
Let A be the complementary event of A. By Lemma D.2 in Vargaftik al. (2022) holds that 2 Also, by the law of total expectation
P P(Ac) s 2 22.d
15

---

Under review as a conference paper at ICLR 2023
27
vd
E
[00
_[0]
[
2
2
vd
Vd
E
[10]
- - 2[01
A
P(A) +E
1101 [101
A" PP(A)) & (4)
1
vd
E
2
- [
A
P(A) M ((A))
where M- (uNMSEmaz) and vNMSE maz is the maximal value at the server's reconstruction table (i.e., max(r)) which is a constant that is independent of the vector's 's dimension. Next,
2
((200)- ((01)
2
vd
E
vd
210]
2[01
A
210]
7
| 1/
=
( Vd
[000]
2101)
2
E
(210) 2011
[
1 -10
A
+
1
vd
E
1
2101
A
(5)
Also,
[ - 7(0)
vd
E
-1
1 310 A .P(()) E
| 2
E
(210) {00) |00
A|
PP(A) $
VI
(6)
(2101) - 210
1 -P(A)
E
210
<
V1
(v-
1)
1
1+
< 2xx
V1 V1-a
vi-
v1
1-
2 (210))
{(110)
Here, we used that E
1A1
P(()) & E
= 1 and that 1
%[0] ž[0] A P((A)
E
[ 2[0]| 4, 2
(P(A) =
| (2]0) A4
(P(A) & -عا -F. (210))
21
Next, we similarly obtain
2 2TT]
vd (
1 (vi-a-1) + (1- vI+a
E
P((A) &
2a. (7)
2
Thus,
uNMSE & E (210) 2210) /
+ 4a + 2.e - M
(8)
yields WNMSE & E. [210] - -210)² 21
+ +0 (VVies Jogd
Setting a
Blog d
16

---

Under review as a conference paper at ICLR 2023
Finally, since Z[0] ~ NN(0, 1), write
eMMSE < & (2- +0 logd
(
C INTERPOLATING THE SOLVER'S SOLUTION
C.I EXAMPLES, INTUITION AND PSEUDOCODE
Based on our examination of solver outputs, we determined an alternative approach that does not stochastically quantize each coordinate to quantile as above and empirically performs better.
We explain the process first considering an example. We consider the setting of 5T2 (Tp 3.097).
m 512 quantiles, b bits per coordinate, and l 2 bits of shared randomness. One optimal
solution for the server is given below
x
2
3
h = 0
-5.48
-1.23
0.164
1.68
h = 1
-3.04
-0.831
0.490
2.18
h = 2
22.18
-0.490
0.831
3.04
h = 3
-1.68
-0.164
1.23
5.48
Table 2: Optimal server values (rr.,)) for æ X2, H H2 when p
1/512 and 512, rounded to
significant digits. For example, when 0, the server will estimate one of values bold based shared randomness and the message received from the client.
Given this table, by symmetry, if Z 0 we can send X [1 If $ which is formally 12 Otherwise
written as (x,,0 { If (x IA
(r 2 2 Indeed, we have that E
2
Otherwise
ΣE Th,x = O. Now, suppose that Z > O (the negative case is symmetric); the client can increase the server estimate's expected value (compared with the above choice of X) by moving probability mass to larger z values for some (or all) of the options for H. For any E (-T,, Tp). there are infinitely many client alternatives that would yield an unbiased estimate. For example, if 0.1, below are two client options (rounded to one significant digit):
If (s If = 2 H 3)
H 2)
If = H
0.6
0.3
If [f 2)
H =)
(.H,0.
0.4 If 3 3 3) (H,00.)))
0.7
0
Otherwise
Otherwise
Note that while both S' and S" produce unbiased estimates, their expected squared errors differ. Further, since 0.1 $ 2m, the solver's output does not directly indicate what is the optimal client's 's algo- rithm, even the server table is fixed. Unlike Algorithm [ which stochastically quantizes Z either or at, we studied the solver's 's output (sh.q.z)h.p to interpolate the client to non-quantile values.
The approach we take corresponds to the following process. We move probability mass from the leftmost, then uppermost entry with mass its right neighbor in the server table. So, for example, in Table 2 as Z increases from 0 we first move mass from the entry = h = 2 to the entry 2, 2. That is, the client, based on its private randomness, increases the probability of message 2 and decreases the probability of message
1 when h 2. The amount of mass moved is always chosen to maintain unbiasedness. At some point, as Z increases, all of the probability mass will have moved, and then we start moving mass from
1, 3 similarly.
'A crucial ingredient in getting a human-readale solution from the solver is that we. without loss of generality, force monotonicity in both & and ie.. (x > x') (/s / R²) = Th.z 3 r. Further, note that Table 2 symmetric. We found tables reduce model size for larger values. We use this symmetry in interpolation.
symmetric for small E, m, and then forced symmetry in order to
17

---

Under review as a conference paper at ICLR 2023
Algorithm 2 QUIC-FL
Client
Server:
1: Compute Z.
vi
(x.).
1: Ve Compute Ze Mai
||ze|1
2: Compute S.H., Z.) as in equation given in Ap-
2: Compute Zay = 1 -
||oell2 Zo
pendix C.2
3: Sample X S(H,, Ze)
3: Estimate Favg R (Zar)
Send (1l Xe) to server
(And subsequently, from x 2, h = 0 and so on.) This process is visualized in Figure 6 Note that (,, 2) values are piecewise linear as a function of 2, and further, these values either go from to 1, 1 to 0, or 0 to I and back again (all of which follow from our description). We can turn this description into formulae, and we defer this mathematical interpretation to Appendix C The final algorithm, named QUIC-FL, is given by Algorithm 2 (based the formula given in the appendix).
1.0
1.0
2 h)
0.8
0.8
0.6
0.6
S00
0.4
S110
0.4
S1
0.2
0.2
0.0
0.0
-2
-1
0
1
2 Encoded Coordinate (z)
-2
Encoded Coordinate (z)
1.0
1.0
(
0.8
h
0.8
0.6
0.6
575
155
0.4
0.4
0.2
0.2
0.0
0.0
-2
-1
0 1
-3
2 Encoded Coordinate (z)
-2
Encoded Coordinate (z)
h=0
h=1
h= 2
h=3
Figure 6: The solver's client algorithm (for l 2, 512, 512 for the quantiles (sh.axhhaa- Markers correspond to quantiles in Qm, and the lines illustrate our interpolation.
C.2 DERIVATION EQUATIONS FOR ALGORITHM
As we described in | through an example, and as illustrated by Figure 6 we have found through examining the solver's solutions, for parameter range, that the optimal approach for the client has a structure that we can generalize. This allows us to readily interpolate the algorithm to non-quantile values Z Qm without stochastically quantizing the coordinate to quantile.
Recall the example from with = b 2. There, we had the server table:
0
r=
2
3
h 0
-5,48
-1.23
0.164
1.68
h 1
-3.04
-0.831
0.490
2.18
h = 2
-2.18
-0.490
0.831
3.04
h 3
-1.68
-0.164
1.23
5.48
18

---

Under review as a conference paper at ICLR 2023
When 2 = 0, the client would send X = 2f & and X = 1 otherwise, leading to E 2 0.
Now consider Z 0.1; the client increase the expected server's estimate by changing its behaviour for the leftmost and then uppermost cell, namely X = 1. = 2. Specifically, by following
1
If - 2 H و
0.3
1 = 2)
(H,
0.7
(I= H
0 Otherwise
In general, by applying the monotonicity constraint we observed a common pattern in the optimal solution found by the solver for any b and é (in the range we tested). Namely, when the server table is monotone, the optimal solution deterministically selects the message to send in all but (at most) one shared randomness value. For example, S" above deterministically selects the message H * 2 (sending if H = 3 and 2 H E {0, 1/) and stochastically selects between * = 1 and 2 when H = 2. Furthermore, the shared randomness value in which should stochastically select the message is easy to calculate. Specifically, let z(Z) E X denote the maximal value such that sending z( for all II would result in not overestimating Z in expectation (that is: 24 EKEn, Th, & ZJ). We note that there must exists such a g because,
I () = max {I E X, |
by design, the solver's output for the optimal solution would always satisfy that # -- Tho -T and 2
T. (Otherwise, the solution would either be infeasible or suboptimal.) In particular, this means that we get z(2) E 2,) {2 - 1} for all Z E (-T,T))
Next, let h(Z) E Hy denote the maximal value for which sending z(Z) for all H and x z(Z) for > h would underestimate Z expectation (for convenience, we consider rh,2* = 00, for all h E Hz). Formally:
1(Z) max h H
2
Σ k'=0
nhy g(2)+++11
Σ Th 2() M=h
Z
For example, consider Z 0.1 in the b l 2 example above. We have that z00.1) 1
since 1 2 Th,1 & 0.1 and 2 Ehet, th2 > 0.1. We also have that 2( = 2 as T 2
(0.164 + 0.49 0.44) + (-0.164)) 0.1 and 1 (0.164 + + (-0.164) > 0.1. Similarly, for = 3 we get z(3) = 2 and h(3) = 3.
The interpolated algorithm works as follows: If H < h. it detemmnnistically sends z(2) 1, i.e.,
(H, 2) = (1 (=r = =(Z)+ + 1) If 4. sends z(Z), i.e. (H,
(x
otherwise Finally, for H = 4. it stochastically selects between z(2) and z(Z) + 1. However, notice that the expected value of this quantization (given that H h) may not be exactly Z. Namely, as the algorithm needs to satisfy _
0 otherwise
Z] z EREMe E
H h] = Z, we require that
21-11
# +
3
H
h] = 2 Z
Σ h=0
(h))(2)11
Σ
Tha(ZZ)
-=
Knowing the desired expectation, the overall client's 's algorithm is then defined as:
If (z z(Z) ^ H > 1) (a (===
M M-Th
If (- (7) + H = h)
S. 2)
(hig(2)+1 -0 2h.
(9)
11-
If (a z(Z) ^ H h)
(hig(2)+1 -"hgg(2
Otherwise
Indeed, by our choice of μ. the algorithm is guaranteed to be unbiased for all 2 l-T,T This gives the final algorithm, whose pseudo-code appears in Algorithm 2 As in Algorithm each client rotates its vector and scales it by |=elly to get vectors whose coordinates' distribution approach i.i.d. (V(0, 1). Next, for each entry Z.Lt] the client computes b(Z.ii)), and then it computes S(He, Z=[i)) shown in Eq equation Finally, it samples a message for each coordinate X_ S H,, [e] that it sends to the server together with the norm ||alll2
vd
19

---

Under review as a conference paper at ICLR 2023
D PERFORMANCE OF QUIC-FL WITH THE RANDOMIZED HADAMARD TRANSFORM
As described earlier, while ideally we would like to use a fully random rotation on the d-dimensional sphere as the first step to our algorithms, this is computationally expensive. Instead, we suggest using randomized Hadamard transform (RHT), which is computationally more efficient. We formally show below that we maintain some performance bounds using a single RHT.
We note that some works suggest using two or three successive randomized Hadamard transforms to obtain something that should be closer to uniform random rotation Yu et al. (2016); Andoni et al. (2015). This naturally takes more computation time. In our casc, and in line with previous works Vargaltik et al. (202T] 2022), we find empirically that one RHT appears to suffice. Unlike these works, our algorithm remains provably unbiased and maintains strong NMSE guarantees in this case. Determining better provable bounds using two or more RHTs is left as an open problem.
Theorem 2. Let x E R4, let RRHT(E) be its randomized Hadamard transform, and let 3 vd 1 [RHT(>)[i] be coordinate in the transformed vector. For any p. Pr L-T,p Tyll 3.2p.
Proof. Follows from the following theorem.
Theorem 3 (Bentkus & Dzindzalietal (0155).. Let el....,,d be iid. Radamacher random vari-
ables and let Rd such that |a]| <1. For any Le R. Pr
Σ a aa.
2
Pt[Za1]
4 Zav?
3.1787 Pr IZ > t). (),
Theorem 4. Fix 512 let x E TR., let RnHT(() be its randomized Hadamard transform, and let |<| (RRT(<(][L be a coordinate in the transformed vector. Denoting by Es (3 - 3%)²
3 = Va Vd
the mean squared error using b bits per coordinate, we have EĄ 4.831, F. 0.692, F3 0.131, E1 0.0272.
b
b=2
MAE Eir 891
10"
10
Encoded Coorldnats (2)
Figure 7: Expected squared function of the value of 3 (for
512).
Proof. We present an approach bound the MSE of encoding the coordinate 3. leveraging Theorem 3
Since we believe that it provides only loose bound, we do not optimize the argument beyond showing the technique. Since the MSE, as a function of 3. is symmetric around 0 (as illustrated in Figure 7),
analyze the 3 > 0 case.
The first option is to split [0, 7 into intervals, e.g., I = (15, (2.22,
Using Theorem we get that P1 + Pr[3 & [0, 1.5]] & 3.2 & [0. 1.5]] & 0.427 and similarly, P2 Pr[3 & [0. 2.2]] & 3.2 Pr|Z & [0, 2.2] & 0.089. Next, we provide the maximal error for each bit budget i and such interval:
20

---

Under review as a conference paper at ICLR 2023
b
4
0, 1.5]
2.063
0.267
0.056
0.0134
1.5, 2.2
6.39
0.67
0.128
0.0285
2.2, T
16.73
3.51
0.617
0.11
Table For each interval 7 bit budget b the maximal MSF, i.c., maxzel R (2= - =
Note that for any b E (1,2,3,4) 4]. the MSEs in 13 are strictly larger than those in 12 which are strictly larger than those in /t. This allows us to derive formal bounds on the error. For example, for 1, have that the error is bounded by
E1 < (1 0.427) 2.063 (0.427 - 0.089) 6.39 0.089 16.73 < 4.831.
Repeating this argument, we also obtain:
Di < (1 0.427) 0.267 + (0.427 0.089) 0.67 0.089 3.51 & 0.692
Fg & 0.427) 0.056 + (0.427 0.089) 0.128 + 0.089 0.617 & 0.131
E4 < (1 0.427) 0..014 + (0.427 0.089) -0.0285 + 0.089 0.11 & 0.0272.
E SHAKESPEARE EXPERIMENTS DETAILS
The Shakespeare next-word prediction task was first suggested in McMahan et (2017) to naturally simulate realistic heterogencous federated learning setting. Its dataset consists of 18,424 lines of text from Shakespeare plays (Shaksspeare paartioee among the respective 715 speakers (i.e., clients). We train a standard LSTM recurrent model Hochreiter & Schmidhuber ( (1997) with = 820K parameters and follow precisely the setup described in Reddi et (2021) for the Adam server optimizer case. We restate the hyperparameters for convenience in Table
Task
Clients per round
Rounds
Batch size
Client
Server
Adam's 10-3
Shakespeare
10
1200
10-2
Table Hyperparameters for the Shakespeare next-word prediction experiments.
F ADDITIONAL EVALUATION
Our code appears in the supplementary material and will be released as open source upon publication.
F.1 DISTRIBUTED POWER ITERATION
MNIST
CIFAR-10
CIFAR-10
elimts
100 alients
elients
100 elients
10A
11f
109
hits per coardinate
hits per conrdinate
bits per coordinate (6)
bits per coordinate
Hadamerd
Kashin-TV TF
QSGD
EDEN
QUIC-FL
Figure 8: Distributed power iteration of MNIST and CIFAR-10 with 10 and 100 clients.
We simulate 10 clients that distributively compute the top eigenvector in a matrix (i.e., the matrix rows are distributed among the clients). Particularly, each client executes a power iteration, compresses its top cigenvector, and sends it to the server. The server updates the next estimated eigenvector by the av- eraged diffs (of each client to the eigenvector from the previous round) and scales it by a learning rate of 0.1. Then, the estimated eigenvector is sent by the server the clients and the next round can begin.
21

---

Under review as a conference paper at ICLR 2023
Figure 8 presents the L2 error of the obtained eigenvector by each compression scheme when compared to the cigenvector that is achieved without compression. The results cover bit budget from one bit to four bits for both MNIST and CIFAR- 10 Krizhevsky et al. (2009); LeCun et al. (1998) 2010) datasets. Each distributed power iteration simulation executed for 50 rounds for the MNIST dataset and for 200 rounds for the CIFAR-10 10 dataset.
As shown, QUIC-FL has an accuracy that is competitive with that of EDEN (especially for 3 2), and considerably better than other algorithms that offer fast decoding time. Also, Kashin-TF is not unbiased (as illustrated by Figure and is therefore less competitive for a larger number of clients.
F.2 FEDERATED LEARNING: EXTENDED COMPARISON WITH QSGD
We repeat the experiments from Figure and Figure 5 adding another curve for QSGD, which uses twice the bandwidth of the other a algorithms (one bit for sign, and another for the stochastic quantization). As shown in figures /9 and 10 even with the additional bandwidth, QSGD's accuracy lower than all algorithms except CS. We note that QSGD also has a more accurate variant that uses variable length encoding Alistarh et al. (2017). However, it is not GPU-friendly, and therefore, as with other variable length encoding schemes as we have discussed previously, we do not include it in the experiment.
CIFAR-10
CIFAR-10 10 Zoom-In
CIFAR-100
CIFAR-I00 10000-0000-000000 Zooon-
.88
663
Test Acentayy
0.6
0.8
623
0.7
0.4
.8G
.613
3500
7000
6500
0750
7000
3000
8000
9000
8000
8500
9000
CIFAR-10 10
CIFAR-10 Zoom-I1
CIFAR-100
CIFAR-100
Zoonn-l
1.0
998
1.0
.993
Thwin
Accussey
0.8
986
9985
3500
7000
6500
6750
7000
3000
6000
1000
8000
8500
8000
Plouti22
Hodemardd
Kashin
QSGD
EDEN
QUIC-FL
Figure 9: Train and test accuracy for CIFAR- 10 and CIFAR- 100 with 10 persistent clients (i.., silos) and b 1.
MNIST
NNIST Zoom-In
CIFAR-10
CIFAR-10 Zaor=In
0.0
Assuney
0.0
The
0.8
.955
.89
0.7-
94
.88
2001
400
550
330
450
550
1000
2000
3000
J000
3000
3500
1000
MNIST
MNIST Zoom-In
CIFAR-10
CIFAR- Zoors-In
.810
1.131
Accuruy
Troin
0.975
.00
9075
0L960
0.75
985
985
2001
8X0
500
331
45il
660
10011
2000
2000
4000
2000
3508
4000
Flouti32
Hadlmaard
Kushin- TF
QSCD
CS
EDEN
QUIC-FL
Figure 10: Cross-device federated learning of MNIST and CIFAR-10 10 with 50 clients and = 1.
G ANALYSIS OF THE BOUNDED STOCHASTIC QUANTIZATION TECHNIQUE
In this appendix, we analyze the Bounded Stochastic Quantization (BSQ) approach that sends all coor- dinates outside range [-T,7] 7] exactly and performs a standard stochastic quantization for the rest.
Let p (0,1) and denote Tр [-Tp, Tp]] Using b bits, we split this range into 2 intervals of size 2- meaning that each
|alka notice that there can be at most p coordinates outside 27,
va.
2
coordinate's 's expected squared error is at most
/4. The MSE of the algorithm is therefore
2h
22

---

Under review as a conference paper at ICLR 2023
bounded by
E | 212
d.
2T
2
/4= p.
| 2 (2) 1)2
26
This gives a result of
ONMSE & p- (26 1)²
Let be the representation length of each coordinate in the input vector (e.g., 32 for single- precision floats, r = 16 for half- half-precisson. or 64 for double precision), we get that BSQ sends a message with less than p- r bits per coordinate. Further, this method has O(d) time for encoding and decoding and is GPU-friendly.
23


Reviews:
[{"review_id": "tcRu-qTYNi", "reviewer": "Reviewer_GcFN", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an unbiased stochastic quantization method called QUIC-FL for rotation-based mean estimation, in order to reduce the communication by transmitting full-precision vectors. The method uses a 'shared randomness' approach which reduces the computation cost at the server to recover the compressed signals. The theoretical foundation is based on a Gaussian approximation argument, and the algorithm is realized by relaxing a continuous problem to a discrete problem. Detailed algorithm design and error analysis are presented. Experiments on simulated and real FL datasets shows the effectiveness of the proposed QUIC-FL.", "summary_of_the_review": "The paper presents meaningful results on unbiased stochastic quantization. However, the analytical assumption on the Gaussian approximation, which is the building block of the paper, might be problematic. Thus, this issue needs to be addressed properly. Besides, the empirical gain is not very significant. ", "strength_and_weaknesses": "1. In general, the paper studies a meaningful problem of design unbiased stochastic compression for a vector. However, I have some concerns about the theoretical development. For a vector $x$, after rotation, the norm of the rotated vector $x^TR$ is fixed (equal to $||x||$). Thus, the argument that $x^TR$ is treated as iid Gaussian for designing the quantizer is not very promising. What's the convergence rate of the iid Gaussian approxmiation? I think this could be a serious issue regarding the correctness of the paper.\n\n2. The performance of QUIC-FL only has marginal improvement over prior methods, which is not very impressive.\n\n3. The presentation can be improved. The text on pages 3-6 is too dense. It might be helpful to add some definitions, claims, or theorems to highlight the key results. \n\n4. In Figure 4, why there is a huge sudden drop of the test accuracy curves, including the baseline full-precision model? This seems strange and needs to be re-implemented.\n\n5. Quantization for Gaussian distribution is a classical topic in literature. There should be a related work section on quantization of Gaussian (and other) random variables. The novelty of the proposed quantization method is not very clear.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jNTTziil-VU", "reviewer": "Reviewer_V1XF", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study Distributed Mean Estimation problem (DME) where $n$ clients communicate a representation of a $d$-dimensional vector\nto a parameter server which estimates the vectors’ mean.\n\nThis paper aimes to resolve the decoding time slowdown from these recent state of the art DME\ntechniques Vargaftik et al. (2021; 2022). To control quantization erorr, tthe authors send an expected $p$-fraction of the rotated coordinates exactly for some small $p$ and apply client-specific shared randomness. ", "summary_of_the_review": "Unfortunately, I think there are major technical issues in the paper. So this paper is not ready for publication. ", "strength_and_weaknesses": "Strength: The paper is relatively well-written. It also interesting that the authors provide simple examples such as those in Sections 3.3 and 3.4 to help the readers understand the method. \n\nWeaknesses: Unfortunately, I think the main weakness is that there are major technical issues in the paper, which will be discussed in the following: \n\n\n------\n\n1- \"transmitting a “bounded-support” normal random variable $Z$, $Z\\in[-T_p, T_p]$ using $b$ bits\"\n\nGiven the bounded support, the distrubution will not be normal anymore. It will be \"truncated normal\" with different probability distribution function and moments. I am not sure about the correctness of the analyses in this paper since the authors assume normal distribution for coordinates after the rotation.  \n\nFor example, the expected squared error in page 4 and optimal unbiased quantization problem in page 5 are not correct because the distribution of $Z$ is truncated normal distribution. \n\n------\n\n2- Regarding, the dimension-indpendent upper bounds on the normalized mean square error in this paper, how can these upper bounds be explained based on the known lower bounds (Mayekar 2020, Ramezani-Kebrya 2021, Acharya 2021)? \n\nPrathamesh Mayekar and Himanshu Tyagi. Limits on gradient compression for stochastic optimization. In IEEE International Symposium on Information Theory (ISIT), 2020.\n\nAli Ramezani-Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M\nRoy. Nuqsgd: Provably communication-efficient data-parallel sgd via nonuniform quantization.\nJournal of Machine Learning Research, 22(114):1–43, 2021.\n\nJayadev Acharya, Clement Canonne, Prathamesh Mayekar, and Himanshu Tyagi. \"Information-constrained optimization: can adaptive processing of gradients help?\" Advances in Neural Information Processing Systems (NeurIPS), 2021.\n\n\n\n------\n\nSeveral closely related work have not been cited/compared:\n\nHantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In International Conference on Machine Learning (ICML), 2017.\n\nWei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. TernGrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems (NeurIPS), 2017.\n\nFartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel M. Roy, and Ali RamezaniKebrya. Adaptive gradient quantization for data-parallel SGD. In Advances in Neural Information Processing Systems (NeurIPS), 2020.\n\nPrathamesh Mayekar and Himanshu Tyagi. Limits on gradient compression for stochastic optimization. In IEEE International Symposium on Information Theory (ISIT), 2020.\n\n\n------\n\nThe expected number of bits to transmit should be added to Table 1. For example, for the same $b$, the expected number of bits to transmit for QSGD is much less than QUIC-FL since only one real value for the norm is sent precisely. \n\n\n------\n \nWhen $b$ and $p$ very small,  QUIC-FL becomes essentially rand-$K$ sparsification method.  \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "N9NLmdrz2p", "reviewer": "Reviewer_Whkw", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work introduces an unbiased compression pipeline for Distributed Mean Estimation (DME) and achieves good performance over several typical datasets compared with competitive baselines. ", "summary_of_the_review": "I'm highly confused with the writing and structure of this paper—also have some doubts about the results. The details are provided above. \n\nI would like to receive some comments from other reviewers and feedback from the author(s).", "strength_and_weaknesses": "Strength:\n1. Comprehensive experiments over different datasets are conducted, and QUIC-FL outperforms conventional baselines and is comparable with EDEN. Different ablation studies are provided, such as different bit budgets, number of clients, and dimensions. \n\nConcerns:\n1. This paper is hard to follow. Besides, the math symbols should be highly reduced and unified. In this case, I can not understand exactly what the algorithm is doing and why it works. Moreover, I would suggest Alg. 1 be better described with more details, then more extended descriptions to be given based on Alg. 1. It gives me a feeling of the current Alg. 1 is only an unreadable sketch. This work should also be more centralized and have a better structure.  \n2. In some figures, such as CIFAR-10 in Fig. 5, both the training accuracy and the testing accuracy for Float32 is lower than EDEN and the proposed QUIC-FL. I doubt the results here. More analysis should be provided as well. \n3. It's unclear what is the convergence speed of QUIC-FL. Only the vNMSE upper bound is provided, but I assume it's insufficient. This paper is called \\textit{Quick} compression; I'm not quite sure whether the convergence speed of QUIC-FL is promising. Besides, are the operators of QUIC-FL computationally heavy?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject