# Better than Optimal: Improving Adaptive Stochastic Quantization Using Shared Randomness

Ran Ben Basat, Yaniv Ben-Itzhak, Michael Mitzenmacher, Shay Vargaftik

<figure><img src="image_1.png" /></figure>

## To cite this version:

Ran Ben Basat, Yaniv Ben-Itzhak, Michael Mitzenmacher, Shay Vargaftik. Better than Optimal: Improving Adaptive Stochastic Quantization Using Shared Randomness. 2025. hal-05227887

HAL Id: hal-05227887

https://hal.science/hal-05227887v1

Preprint submitted on 28 Aug 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Better than Optimal: Improving Adaptive Stochastic Quantization Using Shared Randomness

RAN BEN BASAT, YANIV BEN-ITZHAK, MICHAEL MITZENMACHER, and SHAY VARGAFTIK

Quantization is used to convert higher-precision data into a lower-precision representation, providing a fundamental technique to reduce memory usage, computational complexity, and communication costs in machine learning tasks. Recently, Adaptive Stochastic Quantization (ASQ) methods, which provide unbiased optimized quantized values for a specific input (i.e., when the input distribution is not known to the dequantizer), have been shown to be efficient for compressing large tensors on the fly.

In this paper, we introduce the Adaptive Unbiased Quantization (AUQ) problem that generalizes ASQ to a setting where shared randomness known to both the quantizer and the dequantizer is allowed. We prove an asymptotic gap between the achievable accuracy of the problems, showing that AUQ can be quadratically more precise. We then introduce Simba, an AUQ technique that improves the accuracy of optimal ASQ methods. Intuitively, Simba uses multiple sets of quantization values, and the set used to quantize a specific value is determined using the shared randomness. Interestingly, we show that Simba improves both the speed and accuracy of optimal ASQ methods by leveraging an approximate ASQ solution as a starting point from which Simba improves. We measure Simba to be up to ≈ 24× more accurate for popular distributions than the state-of-the-art optimal ASQ method, QUIVER, while also being up to two orders of magnitude faster. Finally, we demonstrate that Simba can be used to improve the accuracy of QUIC-FL, a state-of-the-art Distributed Mean Estimation technique, by replacing its solver-based lookup tables with tables computed by Simba.

## 1 Introduction

Quantization is a key technique for reducing the memory, compute, and network bandwidth consumption of machine learning (ML) models during training and inference. By allowing for the approximation of real values using a small number of bits, quantization enables many resource-saving techniques, including gradient compression [1–6], post-training quantization [7–10], quantization aware training [11–13], KV-cache compression [14–17], and dataset compression [18, 19].

We focus on two desired properties of some quantization algorithms: adaptivity and unbiasedness, for the following reasons:

* Adaptivity: Certain quantization algorithms, such as Round-to-Nearest, QSGD [20], and QUIC-FL [21], use predetermined quantization values that are applied to the input or a transformation of the input (e.g., after scaling based on the input's norm and min/max values, or after a random rotation). Conversely, adaptive quantization methods select the set of quantization values based on the specific input. As shown in previous work (e.g., [22–24]), adaptivity can lead to substantial improvements in accuracy, at the cost of additional computation.

* Unbiasedness: Given the input vector $X \in \mathbb{R}^d$, we would like the estimate $\tilde{X}$ to satisfy $\mathbb{E}[\tilde{X}] = X$. Having an unbiased estimate of the input provides diverse benefits in a range of applications. One example is when estimating the average of $n$ vectors located on different nodes, a problem known as Distributed Mean Estimation [1, 2, 4, 21, 25]. The unbiased estimate allows for a decay in the estimate's MSE that is proportional to $1/n$, where $n$ is the number of participants, whereas biased estimators may not have such decay as the errors may be correlated (e.g., when all vectors are identical) [25]. Another example of the benefits of unbiasedness is achieving higher accuracy when compressing LLM parameters, compared to biased approaches such as Round to Nearest [26]. The improvement stems from the fact that when taking the inner product between the model weights and activations, unbiased quantization leads to error cancellation, thereby reducing the resulting noise.

<footnote>Dedicated to our beloved cat, Simba, who had a short but happy life. Simba loved catsicles, traveling, and shared randomness and spent hours staring at the screen while our papers were being written.</footnote>
A fundamental approach to achieving unbiased quantization is Stochastic Quantization (SQ), which is popular across both adaptive [22, 23] and non-adaptive methods [20, 24, 27, 28]. In SQ, a value $x \in \mathbb{R}$ is stochastically rounded between two values $a_x, b_x$ such that $x$'s estimate respects $E[\hat{x}] = x$, i.e., $\hat{x} = b_x$ with probability $(x - a_x)/(b_x - a_x)$ and $\hat{x} = a_x$ otherwise. For encoding the input using $s$ quantization values per entry, SQ uses a set $Q \subset \mathbb{R}$ of size $|Q| = s$ such that each $x \in X$ is stochastically rounded to $\hat{x} \in Q$. In turn, Adaptive SQ (ASQ), e.g., [22–24], determines and uses the optimal set of quantization values $Q$ with respect to the input $X$.

While known optimal ASQ methods such as [22, 24] find the optimal $Q$ for the process described above, the formulation of the ASQ problem does not consider *shared randomness*, which we show can allow improvements in accuracy. In fact, for quantizing scalars, it is known that SQ is only optimal when no Shared Randomness (SR) is allowed, and that SR can improve the accuracy [29].

In this paper, we introduce the Adaptive Unbiased Quantization (AUQ) problem, which extends ASQ to allow SR. In AUQ, we assume that a random SR value $h_x$ is generated for each entry $x \in X$. In general, $h_x$ may be continuous, although we consider discrete integer distributions as we later explain. Importantly, $h_x$ is known to both the encoder and decoder (which is achievable, e.g., using a shared PRNG seed) and is not communicated or stored as part of the encoding. When shared randomness is allowed, the quantization and dequantization can depend on $h_x$. We prove that the accuracy improvement offered by AUQ is asymptotic and can be up to quadratically better compared to optimal ASQ methods.

We then present Simba, a novel AUQ method. Simba employs alternating optimization to iteratively improve subsets of quantization values to decrease the error. It also uses an observation about the structure of optimal quantization methods that use shared randomness to further decrease the search space, which can be intuitively summarized as ‘be deterministic whenever possible and randomize only when you have to’. Namely, for all except one possible realization of $h_x$, Simba’s quantization is deterministic, but randomization is still used on some $h_x$ to ensure unbiasedness. Additionally, Simba has an optimal space complexity of $O(d)$, which improves on known ASQ methods.

We note that the greedy approach used by Simba does not necessarily lead to an optimal solution that uses shared randomness; in fact, we prove that any similar greedy iterative method cannot achieve optimality. Nonetheless, we find that by initializing Simba with an approximately optimal solution (determined by Apx. QUIVER [24]) we obtain results that are more accurate than *optimal* ASQ, while also being markedly faster to compute.

We perform extensive ablation studies to tune Simba’s parameters and demonstrate the resulting benefits in three ways:

* We show Simba consistently yields accuracy and speed that improve over the existing best *optimal* ASQ methods that do not use shared randomness, by testing over different input distributions, bit-budgets, and vector sizes.

* We demonstrate that Simba’s execution time is comparable with that of the fastest *approximate* ASQ methods while being markedly more accurate.

* We show that Simba can be used to improve methods that optimize the *worst-case* MSE by employing preprocessing (e.g., the Randomized Hadamard Transform), such as [1, 3, 4, 21, 25, 30–32]. Specifically, we show that Simba improves the state-of-the-art Distributed Mean Estimation (DME) QUIC-FL [21].
## 2 Background

### 2.1 Preliminaries

**Adaptive Stochastic Quantization (ASQ)** ASQ considers encoding real-valued sorted vectors $X \in \mathbb{R}^d$ using s quantization values per entry and focuses on finding a set $Q \subset \mathbb{R}$ of quantization values of size $|Q| = s$. The goal is to pick $Q$ such that when each entry $x \in X$ is quantized to some $\hat{x} \in Q$<fnref n="1" /> with $\mathbb{E}[\hat{x}] = x$, the MSE, also known as the sum-of-variances $\sum_{x \in X} \mathbb{E}[(x - \hat{x})^2]$ is minimized.

Some key observations that were identified in previous ASQ works (e.g., [22, 24]), are that (1) there exists an optimal solution in which $Q \subseteq X$ (i.e., the set of quantization values is a subset of the input) and (2) for any $x \in X$, the optimal quantization strategy is to stochastically round it to $\hat{x} \in \{a_x, b_x\}$ where $a_x = \max\{q \in Q \mid q \le x\}$ and $b_x = \min\{q \in Q \mid q \ge x\}$ are the quantization values closest to $x$. Using these observations, the above works were able to design efficient algorithms to find the optimal $Q$ using dynamic programming approaches.

**Error Metrics** To measure the error, we use the vector-Normalized MSE ($vNMSE$), a standard metric for compression algorithms (e.g., see [4] and the references therein), which is defined as:

$$vNMSE = \frac{\mathbb{E}\left[\left\|X - \hat{X}\right\|^2\right]}{\|X\|^2}.$$

Note that when $X$ is a unit-vector, namely $\|X\| = 1$, $vNMSE$ is reduced to MSE. Throughout the paper we assume that $X \ne 0$ as otherwise the $vNMSE$ is undefined.

**Shared vs. Private Randomness.** In this paper, we make a distinction between private randomness (known only to the quantizer) and shared randomness (that can be generated by both the quantizer and dequantizer). We note that shared randomness is readily implementable, e.g., by using a shared PRNG seed, and is a standard assumption in quantization works (e.g., see [1, 4, 21]). Importantly, the shared random bits are not stored and thus do not affect the number of bits required for representing the quantized values. As explained, each entry $x$ is associated with a shared randomness value $h_x$. We use $h$ as a shorthand for $h_x$ when clear from context. Throughout the paper, we assume that private randomness is always allowed.

**Notation.** For an integer $i$, we denote $[i] = \{0, \dots, i - 1\}$. We also denote by $U[i]$ the uniform distribution over $[i]$.

**Terminology.** Throughout the paper we use encoder/decoder and quantizer/dequantizer interchangeably to refer to the entity quantizing the data and the one that estimates it.

### 2.2 Motivation

We now motivate the benefits of allowing shared randomness with a simple example. Consider quantizing the vector $X = (+1, -1, 0, \dots, 0) \in \mathbb{R}^d$ with a single bit per entry ($s = 2$). Using ASQ, all entries will be rounded to $\pm 1$, yielding a $vNMSE$ of $(d - 2)/2$.

In contrast, assume that we have a shared random bit $h_x \sim U[2]$ per entry $x \in X$, i.e., $\Pr[h_x = 0] = \Pr[h_x = 1] = 1/2$. Denoting the encoding of the quantized value of $x$ as $e_x \in \{0, 1\}$, we can use the algorithm described in Figure 1. This algorithm has two properties.

(1) The algorithm is unbiased:

$$\mathbb{E}[\hat{x} | x = -1] = \mathbb{E}[\hat{x} | x = -1 \wedge h_x = 0] \cdot \Pr[h_x = 0] + \mathbb{E}[\hat{x} | x = -1 \wedge h_x = 1] \cdot \Pr[h_x = 1] = -1.$$

$$\mathbb{E}[\hat{x} | x = 0] = \mathbb{E}[\hat{x} | x = 0 \wedge h_x = 0] \cdot \Pr[h_x = 0] + \mathbb{E}[\hat{x} | x = 0 \wedge h_x = 1] \cdot \Pr[h_x = 1] = 0.$$

$$\mathbb{E}[\hat{x} | x = 1] = \mathbb{E}[\hat{x} | x = 1 \wedge h_x = 0] \cdot \Pr[h_x = 0] + \mathbb{E}[\hat{x} | x = 1 \wedge h_x = 1] \cdot \Pr[h_x = 1] = 1.$$

<footnote n="1">¹s is usually selected as a power of two, allowing $\hat{x}$ to be represented using $\log_2 s$ bits.</footnote>
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 1. The quantization process.</figcaption></figure>

(2) The variance of the $-1$ entry is $1$, as it has equal chance of being quantized to $-2, 0$, and so is the variance of the entry $+1$. The zero entries are accurately quantized and thus do not contribute to the MSE. Therefore, the $vNMSE$ is $2/\|X\|^2 = 1$.

While the above shows the value of shared randomness for a specific vector, we now prove that this phenomenon is much more general. For example, the theorem below implies that for $s = 2$, the $vNMSE$ of the optimal quantization with shared randomness is $O(\sqrt{d})$ for any input vector, i.e., there is a quadratic gap in accuracy compared to the worse case without shared randomness. The proof of the theorem appears in Appendix A.

**Theorem 2.1.** For any constant $s > 1$ and any $d > 1$, there exists $d > \underline{d}$ and an input $X \in \mathbb{R}^d$, such that the $vNMSE$ of the optimal adaptive SQ techniques is $\Omega(d^{1/(s-1)})$. In contrast, for any input $X \in \mathbb{R}^d$, the $vNMSE$ of the optimal unbiased quantization with shared randomness is $O(d^{1/s})$.

# 3 Adaptive Unbiased Quantization

In this section, we introduce the Adaptive Unbiased Quantization (AUQ) problem, discuss how to extend current approaches (such as ASQ) by utilizing shared randomness, and outline its challenges.

## 3.1 Modeling Shared Randomness

As the above example suggests, quantization methods with shared randomness cannot be represented solely by $s$ quantization values. This is because for each different shared randomness value we may have a different set of $s$ quantization values, and the quantization process itself may not always quantize entries to one of their two closest quantization values.

Instead, we represent shared randomness quantization schemes as follows. For each $x \in X$, we denote by $\ell$ the number of values the shared random variable $h_x$ can take on, and have $h_x \sim U[\ell]$. For example, in the above algorithm, $\ell = 2$. An algorithm that uses a shared random variable that can take on $\ell$ values (per entry) is defined using:

* A set $Q = \{Q_h \in \mathbb{R}^s | h \in [\ell]\}$ that contains $\ell$ vectors of quantization values, each of size $|Q_h| = s$. Observe that, without loss of generality, we may assume that all $Q_h$'s are monotone, i.e., that

$$ \forall h \in [\ell], q \in [s-1] : Q_h(q) \le Q_h(q+1). \quad (1) $$

* A set $\mathcal{F} = \{F_h : X \to \Delta[s] | h \in [\ell]\}$, where $\Delta[s]$ is a distribution over $[s]$, where $F_{h,q}(x) = \text{Pr}[e_x = q | h_x = h]$ is the probability of encoding $x$ as $q \in [s]$ when $h_x = h$. $^2$

The dequantization process then simply takes the encoded value $e_x$ and estimates $\tilde{x} = Q_{h_x}(e_x)$.

Notice that the above model, for each $h \in [\ell]$, allows arbitrary scalar quantizers, while assuming that the dequantizer is deterministic (i.e., can be represented using the $s \times \ell$ values of $Q$). This modeling is general as it is known that one cannot reduce the variance by allowing (private) randomness in the dequantization process [29].

<footnote>$^2$By $F_{h,q}(x)$ we refer to the $q$'th value in the distribution $F_h(x)$, i.e., $(F_h(x))^q$.</footnote>
The connection between the $\ell$ different scalar quantizers is given by the requirement that the overall scheme is unbiased; that is:

$$ \forall x \in X : \mathbb{E}[\hat{x}] = \frac{1}{\ell} \sum_{h=0}^{\ell-1} \mathbb{E}[\hat{x} | h_x = h] = \frac{1}{\ell} \sum_{h=0}^{\ell-1} \sum_{q=0}^{s-1} F_{h,q}(x) \cdot Q_h(q) = x. $$

For example, consider the quantization scheme given by Figure 1. This scheme is represented using the quantization values $Q_0 = (-2, 0)$, $Q_1 = (0, 2)$ and the encoding probabilities $F_0(-1) = F_1(-1) = (1, 0)$, $F_0(0) = (0, 1)$, $F_1(0) = (1, 0)$, and $F_0(1) = F_1(1) = (0, 1)$.

**The representation length.** An important property of shared-randomness quantization schemes is that the actual shared random values need not be stored as part of the encoding. This means that for a sufficiently large $d$, the overheads of sending $Q$ are quite minimal. Assuming that a float requires $f$ bits (e.g., $f = 16$ for half precision), the entire encoding of $X$ requires $f \cdot s \cdot \ell$ bits for $Q$ and additional $d \cdot \log_2 s$ bits for $\{e_x | x \in X\}$. Thus, when the dimension $d$ is sufficiently large,<fnref n="3" /> the overhead from allowing shared randomness is quite minimal. For example, if $d = 2^{20}$ and $s = 16$, any scheme that uses $s$ quantization values (i.e., $e_x \in [s]$) requires at least 0.5MB, while a shared randomness scheme with $\ell = 16$ would require less than 0.5005MB.

Notice that to perform the decoding from the above representation, the decoder must know $\mathcal{F}$. There are two natural approaches to achieve that. First, $\mathcal{F}$ can be explicitly sent. However, generally, the size of $\mathcal{F}$ can be very large (e.g., $\Omega(d)$), defeating the purpose of compression. The second approach is to reconstruct $\mathcal{F}$ by solving a quadratic optimization problem. However, this approach severely degrades the decoding time. Instead, we outline below an alternative approach that is both fast and has no encoding-length overhead.

## 3.2 The AUQ Challenges

**Challenges with the combinatorial approach.** The first observation, as evident by the example given in Section 2.2, is that when designing an algorithm for adaptive unbiased quantization with shared randomness, the $s \times \ell$ quantization values of optimal $Q$ may not be entries of the input $X$. As a result, it is unclear whether a dynamic programming approach (which is used by previous optimal ASQ methods such as [22, 24]) is suitable for this setup, and we need to consider alternatives.

**Challenges with convex methods.** The AUQ problem is known to be intractable using methods such as gradient descent as it is non-convex even without shared randomness (where it simplifies to the ASQ problem) and for any $s \ge 4$ [23].

**Challenges with subset methods.** We now demonstrate that any method that optimizes only a subset of the quantization values at a time may converge to a local optimum that can be significantly worse than the global one. Namely, we consider the input from Section 2.2 and prove that while the optimal $vNMSE$ is $O(1)$, there exists a local optimum with $vNMSE$ of $\Omega(d)$.

More concretely, consider once again the input $X = (+1, -1, 0, \dots, 0)$ and quantizing using one shared random bit per entry ($\ell = 2$). This setting has a local optimum at $Q_0 = (-1.5, 0.5)$, $Q_1 = (-0.5, 1.5)$ and $F_0(-1) = F_1(-1) = (1, 0)$, $F_0(0) = (0, 1)$, $F_1(0) = (1, 0)$, and $F_0(1) = F_1(1) = (0, 1)$, in which the quantizer is the same as in Figure 1 but the quantization values $Q$ are different. Notice that the $vNMSE$ of this solution satisfies $\lim_{d \to \infty} \frac{vNMSE}{d} = 1/8$. In this case, we prove in Appendix B, that optimizing any strict subset of the quantization values $Q$ cannot asymptotically improve the $vNMSE$. This is in direct contrast to the algorithm presented in Section 2.2 that has $vNMSE = 1$ for all $d$.

**Lemma 3.1.** For an input $X = (+1, -1, 0, \dots, 0) \in \mathbb{R}^d$, any unbiased quantization scheme with $\ell = 2$ for which $(\{-1.5, -0.5, 0.5, 1.5\} \cap (Q_0 \cup Q_1)) \neq \emptyset$ must have $\lim_{d \to \infty} \frac{vNMSE}{d} \ge 1/8$.

<footnote n="3">³Specifically, if $s \cdot \ell \ge d$, the encoding is larger than the original vector and we thus assume that $s \cdot \ell < d$.</footnote>
This is because of Equation (1) and that:

* $\frac{1}{\ell} \sum_{h=0}^{\ell-1} Q_h(0)$ must be no larger than $\min X$ as otherwise the algorithm cannot be unbiased for $\min X$.

* If $\frac{1}{\ell} \sum_{h=0}^{\ell-1} Q_h(0) < \min X$ then if we increase $\min_{h \in \{0, \dots, \ell-1\}} Q_h(0)$ (which is smaller than $\min X$) to make the inequality tight, we only decrease the error.

* The second equation holds symmetrically.

Thus, Simba always ensures that the equations in (2) hold by maintaining:

$$Q_0(0) = \ell \cdot \min X - \sum_{h=1}^{\ell-1} Q_h(0) \quad , \quad Q_{\ell-1}(s-1) = \ell \cdot \max X - \sum_{h=0}^{\ell-2} Q_h(s-1) \quad (3)$$

Accordingly, Simba never optimizes the quantization values $Q_0(0)$, $Q_{\ell-1}(s-1)$ directly but rather moves them whenever needed according to Equation (3).

To further restrict the search space, Simba enforces the restriction that

$$\forall h \in \{1, \dots, \ell-2\} \quad \forall q \in \{0, \dots, s-1\} : Q_{h-1}(q) \le Q_h(q) \le Q_{h+1}(q). \quad (4)$$

A similar restriction is applied to the extreme $h$ values, where Simba enforces that

$$\forall q \in \{1, \dots, s-1\} : Q_{\ell-1}(q-1) \le Q_0(q) \quad , \quad \forall q \in \{0, \dots, s-2\} : Q_{\ell-1}(q) \le Q_0(q+1). \quad (5)$$

These restrictions (Equation (4) and Equation (5)) are natural, and have been found to hold for an optimal (non-adaptive) solution for the truncated normal distribution [21].

We now explain the determination of low and high (Line 4 of Algorithm 1) for small $\ell$ values, starting with $\ell = 2$, as illustrated in Figure 2.

(1) When $q \in \{1, \dots, s-2\}$ (Figure 2(a)), we set for $Q_h(q)$: low = $Q_{((h-1) \bmod 2)}(q - \mathbb{I}_{h=0})$ and high = $Q_{((h+1) \bmod 2)}(q + \mathbb{I}_{h=1})$. Note that this case only applies when $s > 2$. Here, $\mathbb{I}_A$ takes the value 1 if $A$ is true.

(2) If $q = 0, h = 1$ (Figure 2(b)) we set (for $Q_1(0)$): low = $\frac{Q_0(0)+Q_1(0)}{2} = \min X$ and high = $Q_0(1)$. This low value is designed to ensure that the $Q_0(0) \le Q_1(0)$ monotonicity (Equation (4)) is preserved as $Q_0(0)$ is moved according to Equation (3). Namely, we have that $Q_0(0) = 2 \cdot \min X - Q_1(0)$, and thus, if we decrease $Q_1(0)$, $Q_0(0)$ will increase, and the above value for low is when the two coincide. Similarly, if $q = s-1, h = 0$ then we set for $Q_0(s-1)$: low = $Q_1(s-2)$ and high = $\frac{Q_0(s-1)+Q_1(s-1)}{2} = \max X$.

Next, we describe the ranges for $\ell = 3$, which is illustrated in Figure 3:

(1) If $q \in \{1, \dots, s-2\}$ (Figure 3(a)) then we set for $Q_h(q)$: low = $Q_{((h-1) \bmod 3)}(q - \mathbb{I}_{h=0})$ and high = low = $Q_{((h+1) \bmod 3)}(q + \mathbb{I}_{h=2})$. This case only applies when $s > 2$ and satisfies both Equation (4) and Equation (5).

(2) (Figure 3(b)) If $q = 0, h = 1$ then we set for $Q_1(0)$: low = $\frac{Q_0(0)+Q_1(0)}{2}$ and high = $Q_2(0)$. If $q = 0, h = 2$ then we set for $Q_2(0)$: low = $\max\{Q_1(0), Q_2(0) - (Q_1(0) - Q_0(0))\}$ and high = $Q_0(1)$. As before, this value for low is designed to maintain $Q_0(0) \le Q_1(0)$ ((Equation (4))) as $Q_0(0) = (3 \cdot \min X - Q_1(0)) - Q_2(0)$ and thus $Q_0(0)$ increases when $Q_2(0)$ decreases. The value low = $Q_2(0) - (Q_1(0) - Q_0(0))$ is when $Q_0(0)$ and $Q_1(0)$ coincide. Similarly, if $q = s-1, h = 0$ then we set for $Q_0(s-1)$: low = $Q_2(s-2)$ and high = $\min\{Q_1(s-1), Q_0(s-1) + (Q_2(s-1) - Q_1(s-1))\}$. Finally, if $q = s-1, h = 1$ then for $Q_1(s-1)$ we set low = $Q_0(s-1)$ and high = $\frac{Q_1(s-1)+Q_2(s-1)}{2}$.

The general case of $\ell \ge 4$ is more technical and is thus deferred to Appendix C.
<figure><img src="image_5.png" /><figcaption>Fig. 2. Illustration of low and high for different $(h, q)$ for $\ell = 2$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 3. Illustration of low and high for different $(h, q)$ for $\ell = 3$.</figcaption></figure>

## 4.2 Picking the quantization value to optimize

As we described above, the search range for a given quantization is determined by a small number of other quantization values. As a result, the algorithm may not make significant progress if we revisit a given $(h, q)$ pair without moving the quantization values that determine its search range first. Accordingly, we propose to iterate over the $(h, q)$ pairs in lexicographic order (although any fixed order is expected to yield similar results.)

## 4.3 Deciding F and calculating the MSE

Heretofore, we have described how Simba optimizes the quantization values, which requires deciding on the encoding probabilities F and computing the MSE.

Given a set of quantization values $Q$, Simba determines $F$ using a partition of the input $X$ into $\ell \cdot (s-1)$ intervals $X_0, \dots, X_{\ell \cdot (s-1)-1}$ (i.e., for all $i \le j$ and $a \in X_i, b \in X_j: a \le b$).

The partitioning is done by computing a set of $\ell \cdot (s-1) - 1$ thresholds $T_0, \dots, T_{\ell \cdot (s-1)-2}$ such that $X_i = X \cap [T_{i-1}, T_i)$ (where we denote $T_{-1} = \min X$ and $T_{\ell \cdot (s-1)-1} = \max X$). Simba sets:

$$T_i = \frac{1}{\ell} \sum_{h=0}^{\ell-1} Q_h \left( \left\lfloor \frac{i + \ell - h}{\ell} \right\rfloor \right) . \qquad (6)$$

As explained above, for any $x \in X$ Simba only uses stochastic quantization at one $h_x$ value while deterministically quantizing at all other values. The choice of the specific $h_x$ value at which Simba
<figure><img src="image_7.png" /><figcaption>Fig. 4. Illustration of the thresholds (dashed vertical lines) and corresponding intervals {$X_i = X \cap [T_{i-1}, T_i)$} for $\ell = 3$. Each threshold is an average of $\ell$ quantization values as defined in Equation (6), and all entries in each $X_i$ are stochastically quantized in the interval with the color matching that of the interval.</figcaption></figure>

stochastically quantizes $x$ depends on the interval $X_i$ that contains $x$, and must be $(i \mod \ell)$ if Equation (4), Equation (5), and unbiasedness are to be maintained. For example, every entry in $x \in X_0$ must be stochastically quantized when $h_x = 0$ as otherwise $\hat{x}$ cannot be an unbiased estimate of $x$. Each $x \in X_i$ is thus quantized as follows:

* Given $h \in \{0, \dots, \ell - 1\} \setminus \{i \mod \ell\}$, Simba deterministically quantizes $x$ to $Q_h(\lfloor \frac{i+\ell-h}{\ell} \rfloor)$.

That is, $\forall h \in [\ell] \setminus \{i \mod \ell\}, q \in [s] : F_{h,q}(x) = \begin{cases} 1 & \text{If } q = \lfloor \frac{i+\ell-h}{\ell} \rfloor \\ 0 & \text{Otherwise} \end{cases}$.

* Given $h = i \mod \ell$, Simba stochastically quantizes $x$ between $L_i \triangleq Q_h(\lfloor \frac{i}{\ell} \rfloor)$ and $R_i \triangleq Q_h(\lfloor \frac{i}{\ell} \rfloor + 1)$. Specifically, to ensure unbiasedness, Simba computes:

$$x' = \ell \cdot (x - T_i) + R_i. \qquad (7)$$

The stochastic quantization then ensures that $\mathbb{E}[\hat{x} | h = i \mod \ell] = x'$. That is, if we denote

$$p_{\uparrow} = \frac{x' - L_i}{R_i - L_i} \text{ and } p_{\downarrow} = 1 - p_{\uparrow} \text{ we have: } \forall q \in [s] : F_{h,q}(x) = \begin{cases} p_{\uparrow} & \text{If } q = \lfloor \frac{i+\ell-h}{\ell} \rfloor \\ p_{\downarrow} & \text{If } q = \lfloor \frac{i+\ell-h}{\ell} \rfloor - 1 \end{cases}.$$

This setup is illustrated in Figure 4. We now prove that Simba is indeed unbiased.

**Lemma 4.1.** For all $x \in X : \mathbb{E}[\hat{x}] = x$.

**PROOF.** Notice that, by the definition of $x'$ (Equation (7)),

$$\mathbb{E}[\hat{x}] = \frac{1}{\ell} \sum_{j=0}^{\ell-1} \mathbb{E}[\hat{x} | h=j] = \frac{1}{\ell} \cdot \left( x' + \sum_{j=0}^{\ell-1} Q_j \left( \lfloor \frac{i+\ell-j}{\ell} \rfloor \right) - R_i \right) = T_i + \frac{x' - R_i}{\ell} = x.$$

We are left with showing that $x' \in [L_i, R_i]$ (and thus $p_{\downarrow}, p_{\uparrow}$ are valid probabilities). The upper bound is simple, since $x \in X_i \subset [T_{i-1}, T_i)$ and thus $x' = \ell \cdot (x - T_i) + R_i \le R_i$.

For the lower bound, when $i > 0$, denote $h' = i \mod \ell$, and notice that $x \ge T_{i-1} = T_i + \frac{L_i - R_i}{\ell}$ and thus (for $i \in \{0, \ell \cdot (s-1) - 1\}$ we use $T_{-1} = \min X, T_{\ell \cdot (s-1)-1} = \max X$ and Equation (2)):

$$x' = \ell \cdot (x - T_i) + R_i \ge \ell \cdot \left( T_i + \frac{L_i - R_i}{\ell} - T_i \right) + R_i = L_i. \quad \square$$
Finally, we explain the MSE through the variance of an arbitrary $x \in X_i$ (as $MSE = \sum_{x \in X_i} \text{Var}[\hat{x}]$):

$$ 
\begin{aligned}
\text{Var}[\hat{x}] &= \frac{1}{\ell} \sum_{j=0}^{\ell-1} \mathbb{E}[(x - \hat{x})^2 | h = j] \\
&= \frac{1}{\ell} \left( p_{\uparrow}(x - R_i)^2 + p_{\downarrow}(x - L_i)^2 + \sum_{\substack{0 \le j \le \ell-1 \\ j \ne (i \mod \ell)}} \left( x - Q_j \left( \lfloor \frac{i+j}{\ell} \rfloor \right) \right)^2 \right). \quad (8)
\end{aligned}
$$

## 4.4 Optimizations and Runtime Analysis

The above description of Equation (8) gives a mathematical formulation of the MSE. In practice, we aim for its computation to be quick, as this is done very frequently.

As described in Line 1 of Algorithm 1, Simba is initialized with a set of quantization values $Q$ (and their corresponding initial MSE, as explained in Section 4.5).

Our approach enables the quick updating of the MSE whenever a quantization value is updated, rather than computing it from scratch, by taking advantage of the fact that for most intervals {$X_i$}, the quantization process and error remain unchanged.

As a first step, we explain how to efficiently compute the MSE of a given interval $X_i$.

To that end, for $j^* = i \mod \ell$, we use $L_i = Q_j^*(\lfloor \frac{i}{\ell} \rfloor)$, $R_i = Q_j^*(\lfloor \frac{i}{\ell} \rfloor + 1)$ as before and denote

$$ \beta_i = \sum_{j \in [\ell]} \left( Q_j \left( \lfloor \frac{i+j}{\ell} \rfloor \right) \right)^2, \quad N_i = |X_i|, \quad S_{X_i} = \sum_{x \in X_i} x, \quad S_{X_i}^2 = \sum_{x \in X_i} x^2. $$

Then the following holds, with the proof deferred to Appendix D. In short, we plug the values of $p_\uparrow, p_\downarrow, x'$ (Section 4.3) into Equation (8), sum over all $x \in X_i$ and simplify the resulting expression.

**Lemma 4.2.**

$$ \text{MSE}_i \triangleq \sum_{x \in X_i} \text{Var}[\hat{x}] = -S_{X_i}^2 + (R_i + L_i) \cdot S_{X_i} + \left( \frac{\beta_i}{\ell} - T_i \cdot (R_i + L_i) \right) \cdot N_i. $$

Next, we use two $d$-sized cumulative-sum auxiliary arrays, that are pre-computed in $O(d)$ time, that allow us to compute the above quantities in constant time: (e.g., $(S_X)_k = \sum_{j=0}^k x_j$)

$$ S_X = \left\{ \sum_{j=0}^{k} x_j \mid k \in [d] \right\}, \quad S_X^2 = \left\{ \sum_{j=0}^{k} x_j^2 \mid k \in [d] \right\}. $$

Then, denoting by $I_\downarrow, I_\uparrow$ the smallest and largest index in the input $X$ that belong to $X_i$, we have:

$$ S_{X_i} = (S_X)_{I_\uparrow} - (S_X)_{I_\downarrow-1}, \quad S_{X_i}^2 = (S_X^2)_{I_\uparrow} - (S_X^2)_{I_\downarrow-1}. \quad 4 $$

Finally, we note that $I_\downarrow, I_\uparrow$ can easily be computed in $O(\log d)$ time using a binary search for $T_i, T_{i-1}$, or in $O(\log d/\log \log d)$ time using the known Static Predecessor Search data structures [33]. In practice, we find that a simple binary search is sufficient for values of $d$ that are of interest.

**Corollary 4.3.** $\sum_{x \in X_i} \text{Var}[x]$ is computable in $O(\log d)$ time.

<footnote n="4">⁴Here, $(S_X)_{-1} = (S_X^2)_{-1} = 0$.</footnote>
Next, we describe how to maintain the MSE when a quantization level changes (lines 8, 10, 16, 18). Throughout the execution, Simba maintains $T_i$, $\beta_i$, $L_i$, $R_i$, and $MSE_i$ for all $i \in [\ell \cdot (s-1) - 1]$. As evident by Equation (6), each change of a quantization level $Q_h(q)$ affects the values of at most $\ell$ thresholds which are consecutive. Accordingly, there are at most $\ell + 1$ intervals $\{X_i\}$ whose $MSE_i$ needs to be updated. Finally, as $MSE = \sum_i MSE_i$, and as each such update requires updating $T_i$ and $\beta_i$, each of which is done in constant time, the MSE can be updated in $O(\ell \cdot \log d)$ time.

We summarize the asymptotic complexities, not including the initialization, of Simba as follows:

**Lemma 4.4.** *The time and space complexities of Simba's optimization method (not including the initialization of $\mathcal{Q}$ in Line 1) are $O(d + \text{iters} \cdot \text{bin\_iters} \cdot s \cdot \ell^2 \cdot \log d)$ and $O(d)$, respectively.*

**Further optimization:** Observe that $MSE = \sum_i MSE_i$ has an additive $-\sum_i S_{X_i}^2 = -\sum_{x \in \mathcal{X}} x^2$ term which is a constant that depends on the input but not on the current solution $\mathcal{Q}$. Accordingly, we avoid using $S_X^2$ altogether, saving time and space.

## 4.5 "Better than optimal" Quantization Scheme

As exemplified by Lemma 3.1, the quality of the solution of any subset method highly depends on the initialization.

To avoid ending up with a bad local optimum, Simba uses existing ASQ methods for initialization. Specifically, we consider two alternatives: QUIVER [24], which computes an optimal ASQ (no shared randomness, i.e., equivalent to $\ell = 1$) set of quantization values in $O(d \cdot s)$ time and space, and Apx. QUIVER that computes an approximation in $O(d + m \cdot s)$ time and space, where $m$ is a tradeoff parameter between run-time and approximation guarantee. As shown by [24], Apx. QUIVER has formal approximation guarantees and in practice achieves near-optimal MSE even for moderate $m$ values.

We prove that despite the fact that Simba stochastically quantizes an entry $x$ at a single shared randomness value, the resulting MSE is identical. Since each subsequent iteration of Simba can only improve the MSE, we are guaranteed that the resulting error can only improve.

**Lemma 4.5.** Let $\mathcal{Q}^*$ be an ASQ solution (i.e., without shared randomness) for which $\mathcal{Q}^*(0) = \min X, \mathcal{Q}^*(s-1) = \max X;$<fnref n="5" /> then it has the same MSE as Simba with $Q_0 = Q_1 = \dots = Q_{\ell-1} = \mathcal{Q}^*$.

*PROOF.* The essence of the proof lies in showing that if for a given $x \in (X \setminus \{\max X\})$ we denote $a_x = \max \{q \in \mathcal{Q}^* | q \le x\}$ and $b_x = \min \{q \in \mathcal{Q}^* | q > x\}$, then Simba would produce an estimate that satisfies $\hat{x} \in \{a_x, b_x\}$, the same as the ASQ method we start from. This directly implies that $\text{Var}[\hat{x}]$ is the same, since $\text{Pr}[\hat{x}] = a_x$ is determined by the unbiasedness constraint.

Notice that, since $Q_0 = Q_1 = \dots = Q_{\ell-1} = \mathcal{Q}^*$, there exists an $z$ for which $T_z = a_x, T_{z+\ell} = b_x$. This implies that $x \in \bigcup_{i=z+1}^{z+1+\ell} X_z$. Notice that, by the definitions given in Section 4.3, $T_i$ is the average of $\ell$ quantization values that include all the values $x$ is deterministically quantized to and also $R_i$, the right endpoint of the interval it is stochastically quantized in. Similarly, $L_i$ is a quantization value that appears in the average of $T_{i-1}$. Therefore, $\hat{x}$ takes values in the $\ell + 1$ quantization values of $T_i, T_{i-1}$. Since the thresholds $T_z = a_x, \dots, T_{z+\ell}$ are different weighted averages of $a_x$ and $b_x$ (namely, $T_i = \frac{a_x \cdot (\ell - i + z) + b_x \cdot (i - z)}{\ell}$), this means that $x$ must be quantized to either $a_x$ or $b_x$.

Finally, for $x = \max X$, the variance is 0 in both cases. □

We conclude with Simba's overall complexity, including its initialization, as outlined below.

**Theorem 4.6.** *Simba initialized with QUIVER requires $O(d \cdot s + \text{iters} \cdot \text{bin\_iters} \cdot s \cdot \ell^2 \cdot \log d)$ time and $O(d \cdot s)$ space, and is always at least as accurate as the optimal ASQ solution.*

<footnote n="5">⁵This constraint is satisfied by all optimal solutions as explained in Section 4.1. It also holds for Apx. QUIVER.</footnote>
**Theorem 4.7.** *Simba initialized with Apx. QUIVER requires $O(d+m \cdot s + \text{iters} \cdot \text{bin\_iters} \cdot s \cdot \ell^2 \cdot \log d)$ time and $O(d+m \cdot s)$ space, and is always at least as accurate as Apx. QUIVER.*

**Setting the values of *iters*, *bin_iters*.* The above runtime expression suggest that as long as $\text{iters} \cdot \text{bin\_iters} < \frac{d}{\ell^2 \cdot \log d}$ the runtime of QUIVER-initialized Simba is dominated by that of QUIVER, and if $\text{iters} \cdot \text{bin\_iters} < \frac{d+m \cdot s}{\ell^2 \cdot s \cdot \log d}$ the runtime of Apx. QUIVER-initialized Simba is dominated by that of Apx. QUIVER. Since we are using finite (e.g., 64-bit) number representations, there is little value in setting *bin\_iters* to more than several dozen. In practice, we observed only slight accuracy degradation even when the value is very small (e.g., *bin\_iters* = 2). Accordingly, even a large value for *iters* would mean that Simba is nearly as fast as QUIVER/Apx. QUIVER. In practice, we terminate the execution of Simba when an iteration does not noticeably improve the MSE.

# 5 Use Case: Improving QUIC-FL

In this section, we explain how Simba can improve QUIC-FL [21], a state-of-the-art unbiased compression algorithm that optimizes for the worst case MSE by transforming all inputs to an “average case”. QUIC-FL works in the following stages. First, it applies the Randomized Hadamard Transform (RHT) to the input vector. The RHT efficiently approximates a random rotation on the sphere, effectively moving the input to a random point with the same norm; it is known that the result’s entries then have a distribution that quickly approaches an i.i.d. normal distribution (as *d* increases) [25]. QUIC-FL then separates the small entries within a range [-*T*, *T*], for a suitable parameter *T*, from the larger ones; larger entries are sent at full (e.g., 16-bit) precision while small entries are quantized. QUIC-FL quantizes small entries using a precomputed (i.e., non-adaptive) set of quantization levels (and making use of shared randomness) that have been optimized specifically for the truncated (within [-*T*, *T*]) normal distribution. The result is dequantized, and the inverse RHT rotation is applied at the receiver to approximate the original input.

We use Simba to improve QUIC-FL by utilizing it to compute an improved precomputed set of quantization levels using shared randomness, with no other changes. We explain how Simba yields better precomputed tables. In [21], the quantization tables for QUIC-FL were computed offline by determining equations for an optimization problem whose solution provides the table information for the truncated normal distribution and then using a general-purpose numerical equation solver to produce a solution. Additionally, [21] approximates the distribution by discretizing it using a small number (e.g., 256) of quantiles to provide a discrete problem suitable for the solver. The exact formulation is given in Appendix E for completeness, but is irrelevant for our purposes. The key issue is that the resulting optimization problem is quite complex, requiring a coarse approximation of the distribution and limiting the number of quantization levels and bits of shared randomness that can be used. (It can take a week or more to solve the problem offline, even with these limitations, and running out of memory is also possible.)

Simba can yield a better drop-in precomputed solution because it does not require a general-purpose equation solver and accordingly has better time and space complexity, allowing us to numerically optimize over much larger instances. In particular, we can use 10 million points chosen independently from the truncated normal distribution to generate a table with Simba; in practice, this gives a better representation of the truncated normal distribution. Also, we can use more shared randomness (e.g., $\ell = 256$ compared to $\ell = 16$ used by [21]) which can lead to better accuracy. Simba can produce a precomputed table in less than an hour with these settings. We quantify the improvement in accuracy from using Simba in the evaluation section.
<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 5. Simba's runtime breakdown for different *s*, *ℓ* and *m* values for the LogNormal(0, 1) distribution. The vNMSE appears above each setup's bars.</figcaption></figure>

# 6 Evaluation

*Setup.* We implemented Simba in C++ and evaluated it on a server with an Intel Core i9-10980XE CPU (18 cores, 3.00 GHz, and 24.75 MB cache) and 128 GB RAM, running Ubuntu 20.04.2 LTS. When error-bars are displayed, all data points are averaged over 10 seeds.
*Baselines.* We compared Simba with C++ implementation of QUIVER [24], Apx. QUIVER [24], ALQ [23], and Zip-ML [22] from the open source repository [34]. To evaluate the improvement for worst-case-optimized algorithms, we also compare our Simba-improved version of QUIC-FL with the original QUIC-FL [21] implementation and the open sourced implementation of EDEN [4].

## 6.1 Hyperparameters Ablation

We begin by an ablation study to demonstrate the effect of Simba's hyperparameters.

*Initialization.* In this experiment, we measure the effect of QUIVER's initialization granularity on Simba's vNMSE and runtime. As illustrated in Figure 5, unless $m$ is too small, there is little sensitivity to $m$ in terms of vNMSE. Namely, $s$ this is done very frequently using $m = 1000$ and $m = 10000$ Apx. QUIVER and the Exact QUIVER solution, Simba converges to roughly the same vNMSE. In contrast, if $m = 100$, the resulting vNMSE is often degraded, especially for large $s$ values.

The choice of initialization parameter $m$ also has a significant impact on the runtime. If $m$ is small, Simba requires more iterations to converge, prolonging the runtime. On the other hand, when using the exact QUIVER solution, the initialization with larger $m$ is long and dominates the runtime. Although the best value of $m$ may vary, across a large set of experiments we have found $m = 1000$ to be a robust choice for all tested distributions and $s$ values. In Appendix F.1, we repeat these experiments for four additional distributions and observe similar trends.

*Time-To-vNMSE.* We turn to measure how the vNMSE decreases with more time given to Simba's optimization. Namely, we calculate the vNMSE and time as we increase the number of *iters*, an experiment we term 'time-to-vNMSE'. The results, shown in Figure 6, for a vector of size $d = 2^{20}$ whose entries are i.i.d. Lognormal(0, 1), show that after the initialization (using Apx. QUIVER) the vNMSE quickly improves, with marginal subsequent benefits for using more *iters* beyond the initial improvement. The results for the Normal(0, 1) distribution (Figure 7) show similar behaviour, and in Appendix F.2 we repeat these experiments for three additional distributions and observe similar results. In line with the previous experiments, we observe that $m = 1000$ is a sweet spot that gives both fast initialization and good vNMSE, and use it hereafter for comparing with alternative solutions.

*The number of quantization sets $\ell$.* In this experiment, we measure the effect of $\ell$ on QUIVER's vNMSE. As illustrated in Figure 8 for the LogNormal(0, 1) and Normal(0, 1) distributions and $d = 2^{20}$, even for $\ell = 2$, the improvement in comparison to optimal ASQ solutions (e.g., ZipML and QUIVER) is significant. As $\ell$ increases, the additional improvement decreases quickly. In Appendix F.3, we repeat these experiments for four additional distributions that show a similar trend. Henceforth, for clarity, we will focus on a subset of $\ell$ values, specifically $\ell \in \{2, 4, 6\}$.

## 6.2 Adaptive Quantization Algorithms

We compare Simba to state-of-the-art optimal ASQ solutions, Zip-ML [22] and QUIVER [24]. As shown in Figure 9, Simba presents a tradeoff where larger $\ell$ results in a more accurate quantization (lower vNMSE) but also requires more time to compute $Q$. Compared to other methods, Simba is consistently more accurate than the optimal ASQ, while being markedly faster. The results are shown for the LogNormal(0, 1) and Normal(0, 1) distributions, and additional distributions, deferred to Appendix G, all show similar behavior. We also measure the benefits in extreme case where $s = 2$. In this setup, ASQ methods (both optimal and approximate) must have $Q = \{\min X, \max X\}$ and cannot adapt to the distribution of other entries. Simba, however, is able to significantly improve the vNMSE, in line with Section 2.2. As shown in Figure 10, Simba's vNMSE improvement significantly grows as a function of $d$ and reaches $\approx 24 \times$ when $\ell = 6$ and $d = 2^{24}$.
<figure><img src="image_10.png" /><figcaption>Fig. 6. Simba's time-to-vNMSE for the a $d = 2^{20}$-sized LogNormal(0, 1)-distributed vector.</figcaption></figure>

## 6.3 Adaptive Quantization Approximation Algorithms

Next, we compare Simba with $ℓ = 4$ to five approximate ASQ solutions:

* Apx. Quiver [24]. Configured with $m = 1000$.
<figure><img src="image_11.png" /><figcaption>Fig. 7. Simba's time-to-vNMSE for the a = 2²⁰-sized Normal(0, 1)-distributed vector.</figcaption></figure>

* ZipML-CP Unif. and ZipML-CP Quant. ([22]) These run ZipML on a subset of 1000 Canda-
date Points (CP) that are picked either uniformly or based on quantiles of the input X.
<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /><figcaption>Fig. 8. Simba's vNMSE for different $\ell$ values for the LogNormal(0, 1) and Normal(0, 1) distributions, for $d = 2^{20}$. Even for $\ell = 2$, the improvement in comparison to optimal ASQ solutions (e.g., ZipML and QUIVER) is significant. As $\ell$ increases, the additional improvement becomes marginal.</figcaption></figure>

* ZipML 2-Apx. [22] An algorithm that computes an approximate solution in $O(d \log d + s^3)$ time. It guarantees that its sum of variances is at most twice that of an optimal solution with $\lfloor s/2 \rfloor$ quantization values.

* ALQ [23]. It fits a Truncated Normal distribution's parameters to model the input vector and optimizes the quantization levels.

As shown in Figure 11 for the Lognormal(0,1) distribution, Simba is consistently more accurate than approximate ASQ methods, while having a speed comparable to the fastest approximations as $d$ increases. As expected (see Section 4.5), Simba's asymptotic runtime behavior is similar to Apx. Quiver, which it uses for initialization. Evaluation of additional distributions is deferred to Appendix H, as all show similar behavior.
<figure><img src="image_14.png" /><figcaption>Fig. 9. Comparing Simba (with varying $ℓ$ values) initialized using Apx. QUIVER with $m = 1000$ to other adaptive solutions on a LogNormal(0, 1)- and Normal(0, 1)-distributed inputs. The time axis is on a log scale.</figcaption></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /><figcaption>Fig. 10. Comparison for $s = 2$. Since ASQ methods must set $Q = \{\min X, \max X\}$, we depict a single 'SQ' curve for the $vNMSE$ and do not report its runtime.</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>Fig. 11. Simba's vNMSE and runtime, both in log-scale, for different s and d values for the LogNormal(0, 1) and Normal(0, 1) distributions. Simba generalizes Apx. QUIVER and trades off some computation for accuracy. Both Simba and Apx. QUIVER are significantly more accurate and faster than other methods for increasing d values. Apx. QUIVER is configured with m = 1000 and the number of candidate points in ZipML-CP is 1000.</figcaption></figure>

## 6.4 Worst-case Algorithms

Here, we quantify the improvement attainable by Simba for worst-case (non-adaptive) algorithms as explained in Section 5. We compare the original QUIC-FL [21] and its Simba-improved variant with the most accurate, but asymptotically slower, EDEN [4] method. As Figure 12 shows, Simba improves the error of QUIC-FL for all values of s. Interestingly, for s = 16, the ratio between its error and EDEN's is below 1, meaning that the Simba-improved QUIC-FL is more accurate than EDEN, while also being asymptotically faster. We note that the input distribution (Lognormal (0,1), $d = 2^{20}$) is irrelevant to the results, since the three methods first apply the Randomized Hadamard Transform, meaning that each has a vNMSE that is nearly independent of the input for large enough d.
<figure><img src="image_18.png" /><figcaption>Fig. 12. Comparing the errors of the original and Simba-improved variants of QUIC-FL to the most accurate (but asymptotically slower) worst-case algorithm, EDEN, for $s \in \{2^1, 2^2, 2^3, 2^4\}$.</figcaption></figure>

# 7 Conclusion and Discussion

We presented the Adaptive Unbiased Quantization (AUQ) problem that extends ASQ by allowing shared randomness, and proved an asymptotic accuracy improvement. We then introduced Simba, a novel AUQ method, and using extensive evaluation, showed its speed and accuracy benefits. While Simba guarantees that it is at least as accurate as current ASQ approaches, it is not guaranteed to find the optimal solution when shared randomness is allowed. We believe that finding the optimal solution requires new techniques (see Section 3.2) and is an interesting future direction. Another promising direction is improving the vNMSE bound attainable by shared randomness algorithms. Theorem 2.1 shows there exists an asymptotic gap between methods that use shared randomness and those that do not. However, the bound only uses $\ell = 2$, while the evaluation results suggest that further improvement might be possible with more shared randomness.

We note that there exist many other types of compression, such as sparsification (e.g., [35, 36]), low-rank decomposition (e.g., [37]), sparse coding (e.g., [38]), in-network compression (e.g., [39]), and variable-length encoding (e.g., [4, 5]). For the most part, these are orthogonal and can work in conjunction with Simba; for example, one can apply entropy encoding on the output of Simba, or run it on a sparsified vector. Compression also naturally appears in other domains such as streaming and network measurements [40, 41].

**Acknowledgments:** We thank Samuel Coward for valuable feedback.

# References

[1] A. T. Suresh, X. Y. Felix, S. Kumar, and H. B. McMahan, "Distributed Mean Estimation With Limited Communication," in *International Conference on Machine Learning*. PMLR, 2017, pp. 3329-3337.

[2] J. Konečný and P. Richtářik, "Randomized Distributed Mean Estimation: Accuracy vs. Communication," *Frontiers in Applied Mathematics and Statistics*, vol. 4, p. 62, 2018.

[3] S. Caldas, J. Konečný, H. B. McMahan, and A. Talwalkar, "Expanding the Reach of Federated Learning by Reducing Client Resource Requirements," *arXiv preprint arXiv:1812.07210*, 2018.
[4] S. Vargaftik, R. B. Basat, A. Portnoy, G. Mendelson, Y. B. Itzhak, and M. Mitzenmacher, "EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning," in *International Conference on Machine Learning*. PMLR, 2022, pp. 21 984-22 014.

[5] R. Dorfman, S. Vargaftik, Y. Ben-Itzhak, and K. Y. Levy, "DoCoFL: downlink compression for cross-device federated learning," in *International Conference on Machine Learning*. PMLR, 2023, pp. 8356-8388.

[6] W. Han, S. Vargaftik, M. Mitzenmacher, B. Karp, and R. Ben Basat, "Beyond Throughput and Compression Ratios: Towards High End-to-end Utility of Gradient Compression," in *HotNets*, 2024.

[7] E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh, "OPTQ: Accurate quantization for generative pre-trained transformers," in *The Eleventh International Conference on Learning Representations*, 2023.

[8] Y. Jeon, C. Lee, K. Park, and H.-y. Kim, "A Frustratingly Easy Post-Training Quantization Scheme for LLMs," in *Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing*, 2023, pp. 14 446-14 461.

[9] J. Kim, S. Lee, and M. Park, "Towards next-level post-training quantization of hyper-scale transformers," in *NeurIPS*, 2024.

[10] J. Kim, A. Gupta, and Y. Tan, "Boa: Attention-aware post-training quantization without backpropagation," in *ICML*, 2025.

[11] P. Micikevicius, S. Narang, J. Alben, G. Diamos, E. Elsen, D. Garcia, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh et al., "Mixed Precision Training," in *International Conference on Learning Representations*, 2018.

[12] S. Shen, Z. Dong, J. Ye, L. Ma, Z. Yao, A. Gholami, M. W. Mahoney, and K. Keutzer, "Q-BERT: Hessian Based Ultra Low Precision Quantization of BERT," in *Proceedings of the AAAI Conference on Artificial Intelligence*, vol. 34, no. 05, 2020, pp. 8815-8821.

[13] J. Doe and L. Smith, "Reshape and adapt for output quantization (raoq): Quantization-aware training for in-memory computing systems," in *ICML*, 2024.

[14] Y. Sheng, L. Zheng, B. Yuan, Z. Li, M. Ryabinin, B. Chen, P. Liang, C. Ré, I. Stoica, and C. Zhang, "Flexgen: High-Throughput Generative Inference of Large Language Models With a Single GPU," in *International Conference on Machine Learning*. PMLR, 2023, pp. 31 094-31 116.

[15] Y. Liu, D. Kim, and J. Park, "Minicache: Kv cache compression in depth dimension for large language models," in *NeurIPS*, 2024.

[16] X. Zhang, Y. Li, and Q. Zhou, "Kv cache is 1 bit per channel: Efficient large language model inference with coupled quantization," in *NeurIPS*, 2024.

[17] Z. Zhang, H. Shen, S. Vargaftik, R. B. Basat, M. Mitzenmacher, and M. Yu, "Hack: Homomorphic acceleration via compression of the key-value cache for disaggregated llm inference," *arXiv preprint arXiv:2502.03589*, 2025.

[18] D. Zhou, K. Wang, J. Gu, X. Peng, D. Lian, Y. Zhang, Y. You, and J. Feng, "Dataset Quantization," in *Proceedings of the IEEE/CVF International Conference on Computer Vision*, 2023, pp. 17 205-17 216.

[19] S. Khaki, A. Sajedi, K. Wang, L. Z. Liu, Y. A. Lawryshyn, and K. N. Plataniotis, "Atom: Attention mixer for efficient dataset distillation," in *CVPR*, 2024.

[20] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, "QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding," *Advances in Neural Information Processing Systems*, vol. 30, pp. 1709-1720, 2017.

[21] R. B. Basat, S. Vargaftik, A. Portnoy, G. Einziger, Y. Ben-Itzhak, and M. Mitzenmacher, "Accelerating Federated Learning with Quick Distributed Mean Estimation," in *International Conference on Machine Learning*, 2024.

[22] H. Zhang, J. Li, K. Kara, D. Alistarh, J. Liu, and C. Zhang, "ZipML: Training Linear Models with End-to-End Low Precision, and a Little Bit of Deep Learning," in *International Conference on Machine Learning*. PMLR, 2017, pp. 4035-4043.

[23] F. Faghri, I. Tabrizian, I. Markov, D. Alistarh, D. M. Roy, and A. Ramezani-Kebrya, "Adaptive Gradient Quantization for Data-parallel SGD," *Advances in neural information processing systems*, vol. 33, pp. 3174-3185, 2020.

[24] R. Ben-Basat, Y. Ben-Itzhak, M. Mitzenmacher, and S. Vargaftik, "Optimal and approximate adaptive stochastic quantization," *Advances in Neural Information Processing Systems*, vol. 37, pp. 94 265-94 291, 2024.

[25] S. Vargaftik, R. Ben-Basat, A. Portnoy, G. Mendelson, Y. Ben-Itzhak, and M. Mitzenmacher, "Drive: One-bit Distributed Mean Estimation," *Advances in Neural Information Processing Systems*, vol. 34, pp. 362-377, 2021.

[26] M. Nagel, R. A. Amjad, M. Van Baalen, C. Louizos, and T. Blankevoort, "Up or Down? Adaptive Rounding for Post-training Quantization," in *International Conference on Machine Learning*. PMLR, 2020, pp. 7197-7206.

[27] S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan, "Deep learning with limited numerical precision," in *International conference on machine learning*. PMLR, 2015, pp. 1737-1746.

[28] A. Ramezani-Kebrya, F. Faghri, I. Markov, V. Aksenov, D. Alistarh, and D. M. Roy, "NUQSGD: Provably Communication-efficient Data-parallel SGD via Nonuniform Quantization," *The Journal of Machine Learning Research*, vol. 22, no. 1, pp. 5074-5116, 2021.

[29] Ben Basat, Ran and Mitzenmacher, Michael and Vargaftik, Shay, "How to Send a Real Number Using a Single Bit (And Some Shared Randomness)," in *48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)*.
vol. 198, 2021, p. 25.

[30] M. Safaryan, E. Shulgin, and P. Richtárik, "Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor," *Information and Inference: A Journal of the IMA*, 2020.

[31] X. Chen, S. Vargaftik, and R. Ben-Basat, "When ML Training Cuts Through Congestion: Just-in-Time Gradient Compression via Packet Trimming," in *Hotnets*, 2024.

[32] M. Li, R. B. Basat, S. Vargaftik, C. Lao, K. Xu, X. Tang, M. Mitzenmacher, and M. Yu, "THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression," in *USENIX Symposium on Networked Systems Design and Implementation*, 2024.

[33] M. L. Fredman and D. E. Willard, "Surpassing the information theoretic bound with fusion trees," *Journal of computer and system sciences*, vol. 47, no. 3, pp. 424-436, 1993.

[34] "QUIVER code," https://github.com/ranbenbasat/QUIVER.

[35] J. Fei, C.-Y. Ho, A. N. Sahu, M. Canini, and A. Sapio, "Efficient Sparse Collective Communication and its Application to Accelerate Distributed Deep Learning," in *Proceedings of the 2021 ACM SIGCOMM 2021 Conference*, 2021, pp. 676-691.

[36] W. Han, S. Vargaftik, M. Mitzenmacher, B. Karp, and R. B. Basat, "Beyond throughput and compression ratios: Towards high end-to-end utility of gradient compression," in *Proceedings of the 23rd ACM Workshop on Hot Topics in Networks*, 2024, pp. 186-194.

[37] T. Vogels, S. P. Karimireddy, and M. Jaggi, "PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization," in *Advances in Neural Information Processing Systems*, vol. 32, 2019.

[38] V. Monga, Y. Li, and Y. C. Eldar, "Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing," *IEEE Signal Processing Magazine*, vol. 38, no. 2, pp. 18-44, 2021.

[39] X. Chen, S. Vargaftik, and R. B. Basat, "When ml training cuts through congestion: Just-in-time gradient compression via packet trimming," in *Proceedings of the 23rd ACM Workshop on Hot Topics in Networks*, 2024, pp. 177-185.

[40] R. B. Basat, G. Einziger, M. Mitzenmacher, and S. Vargaftik, "Faster and more accurate measurement through additive-error counters," in *IEEE INFOCOM 2020-IEEE Conference on Computer Communications*. IEEE, 2020, pp. 1251-1260.

[41] J. Kučera, R. B. Basat, M. Kuka, G. Antichi, M. Yu, and M. Mitzenmacher, "Detecting routing loops in the data plane," in *Proceedings of the 16th International Conference on emerging Networking Experiments and Technologies*, 2020, pp. 466-473.
## A Proof of Theorem 2.1

**Theorem 2.1.** For any constant $s > 1$ and any $\underline{d} > 1$, there exists $d > \underline{d}$ and an input $X \in \mathbb{R}^d$, such that the vNMSE of the optimal adaptive SQ techniques is $\Omega(d^{1/(s-1)})$. In contrast, for any input $X \in \mathbb{R}^d$, the vNMSE of the optimal unbiased quantization with shared randomness is $O(d^{1/s})$.

### PROOF. A.1 Lower bound

We first prove the lower bound when shared randomness is not allowed. Denote $\gamma = \lfloor \underline{d}^{1/(s-1)} \rfloor$ and for all $i \in \{0, \dots, \lfloor(s-1)/2\rfloor\}$, denote $c_i = \gamma^{-i}$. Consider the vector that has $\underline{d}$ zero entries and in addition each of $\{+c_i, -c_i\}$ appears $\gamma^{2i}$ times.

Notice that $\gamma^{2\lfloor(s-1)/2\rfloor} \le 2^{s-1}\underline{d}$ and thus the resulting vector has

$$d = \underline{d} + 2 \sum_{i=0}^{\lfloor(s-1)/2\rfloor} \gamma^{2i} = \underline{d} + 2(-1 + \gamma^{2+2\lfloor(s-1)/2\rfloor})/(-1 + \gamma^2) = \Theta(\underline{d})$$

entries, and a squared norm of $2 \sum_{i=0}^{\lfloor(s-1)/2\rfloor} \gamma^{2i} \cdot c_i^2 = 2 \lfloor(s-1)/2\rfloor + 2 = O(1)$.

We use an observation from previous papers about the optimal adaptive SQ solutions [22, 24] that states that there exists an optimal set of quantization values $Q \subset X$, i.e., a solution where all quantization values appear in the input vector.

Next, we observe that there are at least $s+1$ elements in the support of $X$ (e.g., $\{-1, 0, +1\}$ when $s=2$), and thus either there exists $i \in \{1, \dots, \lfloor(s-1)/2\rfloor\}$ such that either $(c_i \notin Q$ or $-c_i \notin Q)$, or $0 \notin Q$.

* Let us consider the first case and assume without loss of generality that $c_i \notin Q$.

In this case, if $i < \lfloor(s-1)/2\rfloor$, the entries with value $c_i$ are stochastically quantized between $c_{i-1}$ and $c_{i+1}$ and thus the MSE is at least

$$\gamma^{2i} \cdot (\gamma^{-i-1} - \gamma^{-i}) \cdot (\gamma^{-i} - \gamma^{-i+1}) = \Omega(\gamma).$$

Similarly, if $i = \lfloor(s-1)/2\rfloor$, the MSE is lower bounded by (stochastically quantizing between $c_{i-1}$ and 0)

$$\gamma^{2i} \cdot (\gamma^{-i-1} - \gamma^{-i}) \cdot \gamma^{-i} = \Omega(\gamma).$$

Combined with the constant norm (shown above), we conclude that in this case the vNMSE is $\Omega(\gamma) = \Omega(\underline{d}^{1/(s-1)}) = \Omega(d^{1/(s-1)})$.

We note that when $s$ is odd, there are $s+2$ elements in the support of $X$, and thus, there has to be such an $i$ as described.

* Alternatively, let us consider bound the error for the case where $s$ is even and $0 \notin Q$. In this case, the zero entries are stochastically quantized between $-c_{s/2-1}$ and $+c_{s/2-1}$ and thus the quantization MSE is

$$\underline{d} \cdot (\gamma^{-(s/2-1)})^2 = \underline{d} \cdot \gamma^{2-s} = \underline{d} \cdot \lfloor \underline{d}^{1/(s-1)} \rfloor^{2-s} \ge \underline{d}^{1+(2-s)/(s-1)} = \Omega(\underline{d}^{1/(s-1)}) = \Omega(d^{1/(s-1)}).$$

Finally, as the squared norm is constant, the vNMSE is also $\Omega(d^{1/(s-1)})$.

## A.2 Upper bound

We now turn to proving the upper bound. We consider allowing the per-entry shared random variable to take two possible outcomes, i.e., each $x \in X$ has an associated $h_x \sim U[2]$ (i.e., $\Pr[h_x = 0] = \Pr[h_x = 1] = 1/2$).

We show a specific algorithm that has a vNMSE of $O(d^{1/s})$ for any input $X \in \mathbb{R}^d$; clearly, the optimal algorithm with shared randomness is at least as accurate, thus establishing the bound.
Note that the vNMSE metric is scale-free; that is, if one has a set of quantization values for $X$, then multiplying all values by some $\xi > 0$ will yield the same vNMSE for the input $\xi \cdot X$. Consequently, we assume, without loss of generality, that $X$ is a unit vector and thus $x \in [-1, 1]$ for all $x \in X$.

For ease of exposition, we first consider the case of $s = 2$. In this case, we use the same dequantization as in Figure 1(b) and generalize the encoding procedure of Figure 1(a) as follows:

<table><thead><tr><th>$h_x \setminus x$</th><th>$x \in [-1, 0]$</th><th>$x \in (0, 1]$</th></tr></thead><tbody><tr><td>0</td><td>Bernoulli(1 + $x$)</td><td>1</td></tr><tr><td>1</td><td>0</td><td>Bernoulli($x$)</td></tr></tbody></table>

The table shows the values of $e_x$ for different combinations of $x$ and $h_x$. Here, Bernoulli($p$) means that the encoder sets $e_x = 1$ with probability $p$.

First, we prove that the algorithm gives an unbiased estimate for any $x \in [-1, 1]$ : For $x \in (0, 1]$ (the other case follows by symmetry) we have:

$$ 
\begin{aligned}
\mathbb{E}[\hat{x}] &= \frac{1}{2} (\mathbb{E}[\hat{x} | h_x = 0] + \mathbb{E}[\hat{x} | h_x = 1]) \\
&= \frac{1}{2} (\mathbb{E}[\hat{x} | e_x = 1, h_x = 0] + x \cdot \mathbb{E}[\hat{x} | e_x = 1, h_x = 1] + (1-x) \cdot \mathbb{E}[\hat{x} | e_x = 0, h_x = 1]) \\
&= \frac{1}{2} (0 + x \cdot 2 + (1-x) \cdot 0) = x.
\end{aligned}
$$

We now show an $O(\sqrt{d})$ vNMSE bound on any input. Consider the variance of the estimate of a single entry $x$, which we, without loss of generality, assume is positive:

$$ 
\begin{aligned}
\mathbb{E}[(x - \hat{x})^2] &= \frac{1}{2} (\mathbb{E}[(x - \hat{x})^2 | h_x = 0] + \mathbb{E}[(x - \hat{x})^2 | h_x = 1]) \\
&= \frac{1}{2} (\mathbb{E}[(x - \hat{x})^2 | \hat{x} = 0] + x \cdot \mathbb{E}[(x - \hat{x})^2 | e_x = 1, h_x = 1] \\
& \qquad \qquad \qquad + (1-x) \cdot \mathbb{E}[(x - \hat{x})^2 | e_x = 0, h_x = 1]) \\
&= \frac{1}{2} (x^2 + x \cdot (x-2)^2 + (1-x) \cdot x^2) = 2x - x^2.
\end{aligned}
$$

Similarly, if $x < 0$, we have $\mathbb{E}[(x - \hat{x})^2] = -2x - x^2$. Using the fact that $X$ is a unit vector, and thus $\sum_{x \in X} |x| \le \sqrt{d}$ by the Cauchy-Schwarz inequality. Therefore, we have:

$$ \text{vNMSE} = \sum_{x \in X} \mathbb{E}[(x - \hat{x})^2] = \sum_{x \in X} (2|x| - x^2) \le 2\sqrt{d} - 1 = O(\sqrt{d}) = O(d^{1/s}). $$

Next, we turn to prove the bound for $s > 2$. In our algorithm, the receiver estimates $\hat{x}$, for any $x \in X$, based on its encoding $e_x \in \{0, \dots, s-1\}$ and shared randomness $h_x$.

We consider two cases based on the parity of $s$ and denote $\eta = d^{-1/s}$.

### Case I: s is odd.

Namely, for a given $h_x \in \{0, 1\}$, we consider the values

$$ \{4h_x - 2\} \cup \{+\eta^i, -\eta^i \mid i \in \{1, \dots, (s-1)/2\}\}. $$

For example, for $s = 3$, we encode $\{-2, -d^{-1/3}, d^{-1/3}\}$ or $\{-d^{-1/3}, d^{-1/3}, 2\}$, depending on $h_x$. This is formally given by the table below, which shows the values of $\hat{x}$ for different combinations of $e_x$ and $h_x$:

Our algorithm works as follows:
<table><thead><tr><th>$h_x \setminus e_x$</th><th>0</th><th>1</th><th>2</th></tr></thead><tbody><tr><th>0</th><td>-2</td><td>-η</td><td>η</td></tr><tr><th>1</th><td>-η</td><td>η</td><td>2</td></tr></tbody></table>

<figure><img src="image_19.png" /><figcaption>Fig. 13. The quantization process for $s = 3$.</figcaption></figure>

* If $x > 0$, we always round it to the nearest value when $h_x = 0$ and stochastically round it to ensure unbiasedness when $h_x = 1$. We explain it in detail for $s = 3$, whose quantization process is illustrated in Figure 13.

For example, if $h_x = 0, s = 3$ and $x \in (0, \eta]$, we deterministically use $e_x = 2$ and thus $\hat{x} = \eta$; in turn, if $h_x = 1$, we stochastically quantize between $-\eta, +\eta$. Note that to achieve unbiasedness, we need that the expectation of the stochastic quantization will satisfy

$$x = \mathbb{E}[\hat{x}] = \frac{1}{2} \cdot (\mathbb{E}[\hat{x} | h_x = 0] + \mathbb{E}[\hat{x} | h_x = 1]) = \frac{1}{2} \cdot (\eta + \mathbb{E}[\hat{x} | h_x = 1]),$$

and thus $\mathbb{E}[\hat{x} | h_x = 1] = 2x - \eta$. Therefore, when $h_x = 1$,

$$\hat{x} = \begin{cases} +\eta & \text{w.p. } x/\eta \\ -\eta & \text{otherwise} \end{cases}.$$

Indeed, this ensures that $\mathbb{E}[\hat{x}] = x$ for all $x \in (0, \eta]$.

Next, let us look at larger entries, namely, $x \in (\eta, 1]$ (still for $s = 3$). As before, when $h_x = 0$ we deterministically have $e_x = 2$ and thus $\hat{x} = \eta$. However, when $h_x = 1$, we stochastically quantize between $\eta$ and 2. That is, to ensure unbiasedness, we set:

$$\hat{x} = \begin{cases} 2 & \text{w.p. } (2x - 2\eta)/(2 - \eta) \\ \eta & \text{otherwise} \end{cases}.$$

* The case for $x \le 0$ is symmetric and we stochastically round it when $h_x = 0$ while deterministically rounding if $h_x = 1$.

Next, we bound the resulting $vNMSE$ (still for the $s = 3$ example). Let us bound the sum of variances of two subsets of the entries separately:
• $A \triangleq \{x \in X \mid |x| > \eta\}$, i.e., all entries whose absolute value is larger than $\eta$. We have that

$$ \sum_{x \in A} \mathrm{Var}[\hat{x}] = \sum_{x \in A} (2 - |x|)(|x| - \eta) < 2 \sum_{x \in A} (|x| - \eta) \\ \le 2 \sqrt{|A| \sum_{x \in A} (|x| - \eta)^2} \le 2 \sqrt{|A| \sum_{x \in A} x^2} \le 2\sqrt{|A|} \le 2/\eta. $$

Here, the second inequality follows from the Cauchy-Schwarz inequality, and the fourth and fifth from X being a unit vector.

• $\{x \in X \mid |x| \le \eta\}$, all smaller entries. Notice that the variance of each such entry is at most $\eta^2$ and there are at most $d$ such entries, for a sum of variances of $O(d \cdot \eta^2)$.

Putting the two quantities together, we have a $v$NMSE of at most $O(1/\eta + d \cdot \eta^2) = d^{1/3}$, as needed. Generalizing to an arbitrary odd $s$ value, and denoting $A_i \triangleq \{x \in X \mid |x| \in [\eta^{i+1}, \eta^i]\}$ for all $i \in \{1, \dots, (s-1)/2 - 2\}$ and $A_> \triangleq \{x \in X \mid |x| \in [\eta, 1]\}$, we have that:

• If $x \in A_i$, we quantize it to $\hat{x} \in \{\mathrm{sign}(x) \cdot \eta^{i+1}, \mathrm{sign}(x) \cdot \eta^i\}$, stochastically for $h_x = \mathrm{sign}(x)$ and deterministically for $h_x = 1 - \mathrm{sign}(x)$, with the SQ probability set to retain unbiasedness. Similarly to the $s=3$ analysis, we have:

$$ \sum_{x \in A_i} \mathrm{Var}[\hat{x}] = \sum_{x \in A_i} (\eta^i - |x|)(|x| - \eta^{i+1}) < \eta^i \sum_{x \in A_i} (|x| - \eta) \\ \le \eta^i \sqrt{|A_i| \sum_{x \in A_i} (|x| - \eta)^2} \le \eta^i \sqrt{|A_i| \sum_{x \in A_i} x^2} \le \eta^i \sqrt{|A_i|} \le \eta^i / \eta^{i+1} = 1/\eta. $$

Once again, the second inequality follows from the Cauchy-Schwarz inequality, and the fourth and fifth from X being a unit vector.

• If $x \in A_>$ we quantize it to $\hat{x} \in \{\mathrm{sign}(x) \cdot \eta, \mathrm{sign}(x) \cdot 2\}$, stochastically for $h_x = \mathrm{sign}(x)$ and deterministically for $h_x = 1 - \mathrm{sign}(x)$, with the probability that lead to unbiasedness. Note that this is allowed since we can quantize to $-2$ when $h_x = 0$ and to $+2$ if $h_x = 1$. We similarly have:

$$ \sum_{x \in A_>} \mathrm{Var}[\hat{x}] = \sum_{x \in A_>} (2 - |x|)(|x| - \eta) < 2 \sum_{x \in A_>} (|x| - \eta) \\ \le 2 \sqrt{|A_>| \sum_{x \in A_>} (|x| - \eta)^2} \le 2 \sqrt{|A_>| \sum_{x \in A_>} x^2} \le 2\sqrt{|A_>} \le 2/\eta. $$

• If $|x| < \eta^{(s-1)/2}$, we quantize it to $\hat{x} \in \{-\eta^{(s-1)/2}, +\eta^{(s-1)/2}\}$, stochastically for $h_x = \mathrm{sign}(x)$ and deterministically for $h_x = 1 - \mathrm{sign}(x)$, with the probability that lead to unbiasedness. As in the $s=3$ example, each such entry has a variance upper bounded by $\eta^{s-1}$ and there can be at most $d$ such entries.

Combining all of these together we have a $v$NMSE of

$$ \sum_{i=1}^{(s-1)/2-2} \left( \sum_{x \in A_i} \mathrm{Var}[\hat{x}] \right) + \sum_{x \in A_>} \mathrm{Var}[\hat{x}] + \sum_{x \in X \mid |x| < \eta^{(s-1)/2}} \mathrm{Var}[\hat{x}] = \\ \left( (s-1)/2 - 2 \right) \cdot 1/\eta + 2/\eta + d \cdot \eta^{s-1} = (s-1)/2/\eta + d \cdot \eta^{s-1} = O(d^{1/s}) $$

**Case II: $s$ is even.**
When $s$ is even, our quantization values are similar, but we add another at 0; specifically, for a given $h_x \in \{0, 1\}$, we have the values

$$ \{4h_x - 2\} \cup \{0\} \cup \{+\eta^i, -\eta^i \mid i \in \{1, \dots, s/2 - 1\}\}. $$

For example, for $s = 4$, we encode $\{-2, -d^{-1/4}, 0, d^{-1/4}\}$ or $\{-d^{-1/4}, 0, d^{-1/4}, 2\}$, depending on $h_x$. This is formally given by the table below, which shows the values of $\hat{x}$ for different combinations of $e_x$ and $h_x$:

<table><thead><tr><th>$h_x \setminus e_x$</th><th>0</th><th>1</th><th>2</th><th>3</th></tr></thead><tbody><tr><th>0</th><td>-2</td><td>-η</td><td>0</td><td>η</td></tr><tr><th>1</th><td>-η</td><td>0</td><td>η</td><td>2</td></tr></tbody></table>

We analyze the general case, denoting as before: $A_i \triangleq \{x \in X \mid |x| \in [\eta^{i+1}, \eta^i]\}$ for all $i \in \{1, \dots, s/2 - 2\}$ and $A_> \triangleq \{x \in X \mid |x| \in [\eta, 1]\}$. We further denote $A_< \triangleq \{x \in X \mid |x| < \eta^{s/2-1}\}$. As in the odd $s$ case, if $x \in A_i$ for some $i$, we have $\hat{x} \in \{\text{sign}(x) \cdot \eta^{i+1}, \text{sign}(x) \cdot \eta^i\}$. Similarly, for $x \in A_>$ we get $\hat{x} \in \{\text{sign}(x) \cdot \eta, \text{sign}(x) \cdot 2\}$ and for $x \in A_<$ then $\hat{x} \in \{0, \text{sign}(x) \cdot \eta^{s/2-1}\}$. In all cases, we stochastically quantize $x \in X$ if $h_x = \text{sign}(x)$ and deterministically for $h_x = 1 - \text{sign}(x)$, with a probability that ensures unbiasedness.

The analysis showing that $\sum_{x \in A_i} \text{Var}[\hat{x}] < 1/\eta$ and $\sum_{x \in A_>} \text{Var}[\hat{x}] < 2/\eta$ is identical to the above. We provide a similar analysis for $A_<$:

$$ \sum_{x \in A_<} \text{Var}[\hat{x}] = \sum_{x \in A_<} |x|(\eta^{s/2-1} - |x|) < \eta^{s/2-1} \sum_{x \in A_<} |x| \le \eta^{s/2-1} \cdot \sqrt{d}, $$

where the last inequality follows from the Cauchy-Schwarz inequality.

Summing it all up, we have that the $vNMSE$ is upper bounded by:

$$ \sum_{i=1}^{(s-1)/2-2} \left( \sum_{x \in A_i} \text{Var}[\hat{x}] \right) + \sum_{x \in A_>} \text{Var}[\hat{x}] + \sum_{x \in A_<} \text{Var}[\hat{x}] = (s/2 - 2) \cdot 1/\eta + 2/\eta + d \cdot \eta^{s-1} = s/(2\eta) + \eta^{s/2-1} \cdot \sqrt{d} = O(d^{1/s} + d^{-(s/2-1)/s+1/2}) = O(d^{1/s}). $$

We established that in all cases, the $vNMSE$ is upper bounded as stated. $\square$

## B Proof of Lemma 3.1

**Lemma 3.1.** For an input $X = (+1, -1, 0, \dots, 0) \in \mathbb{R}^d$, any unbiased quantization scheme with $\ell = 2$ for which $(\{-1.5, -0.5, 0.5, 1.5\} \cap (Q_0 \cup Q_1)) \neq \emptyset$ must have $\lim_{d \to \infty} \frac{vNMSE}{d} \ge 1/8$.

**PROOF.** By sign symmetry, it is enough, without loss of generality, to show that if $0.5 \in Q_0 \cup Q_1$ or $1.5 \in Q_0 \cup Q_1$ then $\lim_{d \to \infty} \frac{vNMSE}{d} \ge 1/8$.

* **Case** $0.5 \in Q_0 \cup Q_1$. Without loss of generality, we may assume that $0.5 \in Q_0$. Consider two sub-cases: (i) $Q_0(0) = 0.5$ (and $Q_0(1) \ge 0.5$); (ii) $Q_0(1) = 0.5$ (and $Q_0(0) \le 0.5$). In case (i), in order to encode the zero entries in an unbiased manner, we must have $Q_1(1) \le -0.5$, thus the variance of quantizing each zero is at least $1/4$, leading to $\lim_{d \to \infty} \frac{vNMSE}{d} \ge (1/4)/2 = 1/8$.
In case (ii), we write the optimization problem that minimizes $\text{Var}[\hat{x} | x = 0]/\|X\|^2 = \text{Var}[\hat{x} | x = 0]/2 \le \lim_{d \to \infty} \frac{\text{vNMSE}}{d}$:

$$ \min \frac{1}{4} \left( F_{0,0}(0)(Q_0(0))^2 + (1 - F_{0,0}(0)) \cdot 0.5^2 + F_{1,0}(0)(Q_1(0))^2 + (1 - F_{1,0}(0))(Q_1(1))^2 \right) \\ \text{s.t.} $$

$$ -1 = \mathbb{E}[\hat{x} | x = -1] \ge \frac{1}{2}(Q_0(0) + Q_1(0)) $$

$$ \mathbb{E}[\hat{x} | x = 0] = \frac{1}{2} \left( F_{0,0}(0)Q_0(0) + (1 - F_{0,0}(0)) \cdot 0.5 + F_{1,0}(0)Q_1(0) + (1 - F_{1,0}(0))Q_1(1) \right) = 0 $$

$$ \begin{aligned} 1 = \mathbb{E}[\hat{x} | x = 1] &\le \frac{1}{2}(0.5 + Q_1(1)), \\ 0 \le F_{0,0}(0), F_{1,0}(0) &\le 1. \end{aligned} $$

This problem is convex, and its solution is given by $F_{0,0} = 0, F_{0,1} = 1, Q_0(0) = -1.5, Q_1(0) = -0.5, Q_1(1) = 1.5$, where the target value is $1/8$.

* **Case 1** $1.5 \in Q_0 \cup Q_1$. Without loss of generality, we may assume that $1.5 \in Q_1$.

Again, we consider two subcases: (iii) $Q_1(0) = 1.5$ (and $Q_1(1) \ge 1.5$); (iv) $Q_1(1) = 1.5$ (and $Q_1(0) \le 1.5$).

Subcase (iii) is simple, as in order to encode 0 unbiasedly, we must have $Q_0(0) \le -1.5$ and thus $\text{Var}[\hat{x} | x = 0] = 1.5^2 = 2.25$, yielding $\lim_{d \to \infty} \frac{\text{vNMSE}}{d} \ge (9/4)/2 = 9/8$.

Next, consider subcase (iv) (where $Q_1(0) \le Q_1(1) = 1.5$). Once more, we write the optimization problem which minimizes $\text{Var}[\hat{x} | x = 0]/\|X\|^2 = \text{Var}[\hat{x} | x = 0]/2 \le \lim_{d \to \infty} \frac{\text{vNMSE}}{d}$:

$$ \min \frac{1}{4} \left( F_{0,0}(0)(Q_0(0))^2 + (1 - F_{0,0}(0)) \cdot Q_0(1)^2 + F_{1,0}(0)(Q_1(0))^2 + (1 - F_{1,0}(0))(1.5)^2 \right) \\ \text{s.t.} $$

$$ -1 = \mathbb{E}[\hat{x} | x = -1] \ge \frac{1}{2}(Q_0(0) + Q_1(0)) $$

$$ \mathbb{E}[\hat{x} | x = 0] = \frac{1}{2} \left( F_{0,0}(0)Q_0(0) + (1 - F_{0,0}(0)) \cdot 0.5 + F_{1,0}(0)Q_1(0) + (1 - F_{1,0}(0))Q_1(1) \right) = 0 $$

$$ \begin{aligned} 1 = \mathbb{E}[\hat{x} | x = 1] &\le \frac{1}{2}(Q_0(1) + 1.5), \\ 0 \le F_{0,0}(0), F_{1,0}(0) &\le 1. \end{aligned} $$

As before, one can verify that the solution to the optimization problem yields a minimal value of $1/8$.

To conclude, we showed that in all cases, if one starts from the $Q_0 = (-1.5, 0.5)$, $Q_1 = (-0.5, 1.5)$ and $F_0(-1) = F_1(-1) = (1, 0)$, $F_0(0) = (0, 1)$, $F_1(0) = (1, 0)$, and $F_0(1) = F_1(1) = (0, 1)$ solution, they must change **all** quantization values to lower the vNMSE below $d/8$. $\square$

### C Determining the search range for $\ell \ge 4$

Simba sets the search range as follows, starting with the intermediate $q$ values case:

(1) If $q \in \{1, ..., s-2\}$ then low = $Q_{(h-1) \mod l}(q - \mathbb{I}_{h=0})$ and high = $Q_{(h+1) \mod l}(q + \mathbb{I}_{h=l-1})$, as illustrated in Figure 14(a) and Figure 14(b).

We turn to explain the bounds for extreme values of $q$:
<figure><img src="image_20.png" /><figcaption>Fig. 14. Illustration of low and high for different $(h, q)$.</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>Fig. 15. Illustration of low and high for $q = 0$. The cases for $q = s - 1$ are symmetric.</figcaption></figure>

(4) If $h = 1, q = 0$ then $low = \frac{Q_0(0)+Q_1(0)}{2}$ as illustrated in Figure 15(a). This restriction comes from Equation (3) as otherwise it would cause $Q_0(0) > Q_1(0)$, which is not allowed.

(5) If $h \in \{2, \dots, l-2\}, q = 0$, then $low = \max\{Q_{h-1}(0), Q_h(0) - (Q_1(0) - Q_0(0))\}$. Here, the restriction that $low \ge Q_h(0) - (Q_1(0) - Q_0(0))$ enforces that $Q_0(0) \le Q_1(0)$ holds. This is illustrated in Figure 15(b).

(6) If $h = l - 1, q = 0$, then $low = \max\{Q_{l-2}(0), Q_{l-1}(0) - (Q_1(0) - Q_0(0))\}$ and $high = Q_0(1)$, as illustrated in Figure 15(c).

(7) If $h = l - 2, q = s - 1$ then $low = Q_{l-3}(s-1)$ and $high = \frac{Q_{l-2}(s-1)+Q_{l-1}(s-1)}{2}$, symmetrically to Item 4.

(8) If $h \in \{1, \dots, l-2\}, q = s-1$, then $low = Q_{h-1}(s-1)$ and
$$high = \min\{Q_{h+1}(s-1), Q_h(s-1) + (Q_{l-1}(s-1) - Q_{l-2}(s-1))\},$$
symmetrically to Item 5.
(9) If $h = 0, q = s - 1$ then $high = \min \{Q_1(s-1), Q_0(s-1) + (Q_{t-1}(s-1) - Q_{t-2}(s-1))\}$ and
$low = Q_{t-1}(s-2)$, symmetrically to Item 6.

D Proof of Lemma 4.2

**Lemma 4.2.**

$$
MSE_i \triangleq \sum_{x \in X_i} \mathrm{Var}[\hat{x}] = -S_{X_i}^2 + (R_i + L_i) \cdot S_{X_i} + \left(\frac{\beta_i}{\ell} - T_i \cdot (R_i + L_i)\right) \cdot N_i.
$$

PROOF. For ease of notation, throughout the proof we use $Q_j$ as a shorthand for $Q_j(\lfloor \frac{i+j}{\ell} \rfloor)$.

Recall our notations:

$$
j^* = i \mod \ell, R_i = Q_{j^*}, L_i = Q_{j^*-1}, \beta_i = \sum_{j \in [\ell]} (Q_j)^2, N_i = |X_i|, S_{X_i} = \sum_{x \in X_i} x, S_{X_i}^2 = \sum_{x \in X_i} x^2.
$$

Starting from Equation (8), we split

$$
MSE_i = D + S,
$$

where

$$
D = \sum_{x \in X_i} \frac{1}{\ell} \sum_{j \neq j^*} (x - Q_j)^2, \quad S = \sum_{x \in X_i} \frac{1}{\ell} \left[ p_{\uparrow} (x - R_i)^2 + p_{\downarrow} (x - L_i)^2 \right].
$$

Using $\sum_{j \neq j^*} Q_j = \ell T_i - R_i$, and $\sum_{j \neq j^*} Q_j^2 = \beta_i - R_i^2$, we get

$$
\begin{align}
D &= \sum_{x \in X_i} \frac{1}{\ell} \sum_{j \neq j^*} (x - Q_j)^2 = \left( \frac{1}{\ell} \sum_{x \in X_i} x^2 \right) - \frac{2}{\ell} \left( \sum_{x \in X_i} x \right) \left( \sum_{j \neq j^*} Q_j \right) + \frac{1}{\ell} \left( \sum_{j \neq j^*} Q_j^2 \right) \nonumber \\
&= \frac{\ell - 1}{\ell} S_{X_i^2} - \frac{2(\ell T_i - R_i)}{\ell} S_{X_i} + \frac{N_i}{\ell} (\beta_i - R_i^2). \tag{9}
\end{align}
$$

Next, we use $p_\uparrow = \frac{x'-L_i}{R_i-L_i}$ and $p_\downarrow = 1-p_\uparrow$ and expand $S$:

$$
S = \sum_{x \in X_i} \frac{1}{\ell} \frac{(x' - L_i)(x - R_i)^2 + (R_i - x')(x - L_i)^2}{R_i - L_i}. \quad (10)
$$

Expanding each product we get:

$$
\begin{align*}
(x' - L_i)(x - R_i)^2 &= x' (x - R_i)^2 - L_i (x - R_i)^2, \\
(R_i - x')(x - L_i)^2 &= R_i (x - L_i)^2 - x' (x - L_i)^2.
\end{align*}
$$

Grouping the terms involving $x'$ and those not:

$$
\begin{align}
& (x' - L_i)(x - R_i)^2 + (R_i - x')(x - L_i)^2 \nonumber \\
&= x' \left[ (x - R_i)^2 - (x - L_i)^2 \right] + \left[ R_i (x - L_i)^2 - L_i (x - R_i)^2 \right]. \tag{11}
\end{align}
$$

Computing the two brackets, we write:

$$
(x - R_i)^2 - (x - L_i)^2 = -2(R_i - L_i)x + (R_i^2 - L_i^2) = (R_i - L_i)(-2x + R_i + L_i), \quad (12)
$$

$$
R_i (x - L_i)^2 - L_i (x - R_i)^2 = (R_i - L_i) (x^2 - R_i L_i). \quad (13)
$$

Plugging Equation (12) and Equation (13) into Equation (11):

$$
(x' - L_i)(x - R_i)^2 + (R_i - x')(x - L_i)^2 = (R_i - L_i) \left[ x'(-2x + R_i + L_i) + (x^2 - R_i L_i) \right].
$$
Next, since $x' = \ell(x - T_i) + R_i$:

$$ 
\begin{aligned}
\frac{(x' - L_i)(x - R_i)^2 + (R_i - x')(x - L_i)^2}{R_i - L_i} &= x' (-2x + R_i + L_i) + (x^2 - R_i L_i) \\
&= \ell(x - T_i)(-2x + R_i + L_i) + R_i(-2x + R_i + L_i) + x^2 - R_i L_i.
\end{aligned} 
\quad (14) $$

Putting Equation (14) into Equation (10):

$$ S = \sum_{x \in X_i} \frac{1}{\ell} \underbrace{\left[ \ell(x - T_i)(-2x + R_i + L_i) + R_i(-2x + R_i + L_i) + x^2 - R_i L_i \right]}_{(ii)} \quad (15) $$

Simplifying each sum we get:

$$ \frac{1}{\ell} \sum_{x \in X_i} (i) = \sum (x - T_i)(-2x + R_i + L_i) = -2S_{X_i^2} + S_{X_i}(R_i + L_i + 2T_i) - N_i \cdot T_i(R_i + L_i), $$

$$ \frac{1}{\ell} \sum_{x \in X_i} (ii) = \frac{R_i}{\ell} \sum (-2x + R_i + L_i) = \frac{-2R_i}{\ell} S_{X_i} + \frac{N_i}{\ell} (R_i^2 + R_i L_i), $$

$$ \frac{1}{\ell} \sum_{x \in X_i} (iii) = \frac{1}{\ell} \sum (x^2 - R_i L_i) = \frac{1}{\ell} \cdot S_{X_i^2} - \frac{1}{\ell} \cdot R_i L_i N_i. $$

Putting these back into Equation (15) yields:

$$ S = \underbrace{(\frac{1}{\ell} - 2)S_{X_i^2}}_{S_1} + \underbrace{(R_i + L_i + 2T_i - \frac{2R_i}{\ell})S_{X_i}}_{S_2} + \underbrace{N_i(\frac{R_i^2}{\ell} - T_i(R_i + L_i))}_{S_3}. $$

Recall that $MSE_i = D + S$ and by Equation (9):

$$ D = \underbrace{\frac{\ell-1}{\ell} S_{X_i^2}}_{D_1} - \underbrace{\frac{2(\ell T_i - R_i)}{\ell} S_{X_i}}_{D_2} + \underbrace{\frac{N_i}{\ell}(\beta_i - R_i^2)}_{D_3}. $$

Therefore:

$$ \text{Coefficient of } S_{X_i^2}: \quad D_1 + S_1 = \frac{\ell - 1}{\ell} + \left(\frac{1}{\ell} - 2\right) = -1, $$

$$ \text{Coefficient of } S_{X_i}: \quad D_2 + S_2 = -\frac{2(\ell T_i - R_i)}{\ell} + \left(R_i + L_i + 2T_i - \frac{2R_i}{\ell}\right) = R_i + L_i, $$

$$ \text{Constant term:} \quad D_3 + S_3 = N_i \cdot \frac{\beta_i - R_i^2 + R_i^2}{\ell} - N_i \cdot T_i(R_i + L_i) = N_i \cdot \left(\frac{\beta_i}{\ell} - T_i(R_i + L_i)\right). $$

Hence, as required,

$$ MSE_i = -S_{X_i^2} + (R_i + L_i) \cdot S_{X_i} + \left(\frac{\beta_i}{\ell} - T_i \cdot (R_i + L_i)\right) \cdot N_i. \quad \square $$
## E QUIC-FL's Optimization Formulation

We explain the formulation of the problem QUIC-FL [21] uses to derive a near-optimal set of quantization levels for the truncated normal distribution. The notation is adapted to that of the current paper.

As explained above, after applying the Randomized Hadamard Transform, the entries are nearly i.i.d. normally distributed. The next step is to “truncate” the distribution by restricting the quantization only to entries in $[-T, T]$, for a suitable parameter $T$. Intuitively, the larger $T$ is, the fewer entries that might not be quantized (thus increasing the representation length), but also the less accurate the quantization of the small entries. In particular, the authors propose to use $T \approx 3.09$, which corresponds to quantizing a 511/512-fraction of the entries as a good working point.

Then, QUIC-FL uses a finite number $M$ of quantiles of the truncated distribution. Denoting $Z \sim N(0, 1)$, it defines quantiles $\mathcal{A}_M = \{A_M(i) | i \in [M]\}$, where the quantile $A_M(i)$ satisfies

$$ \Pr[Z \le A_M(i) | Z \in [-T, T]] = \frac{i}{M-1}. $$

For a given shared randomness value $h \in [\ell]$, a given $q \in [s]$, and a given entry $x \in X$, QUIC-FL denotes by $S(h, q, x) = \Pr[e_x = q | h, x]$ the probability of encoding the entry as $q$. Similarly, it uses $R(h, q) = (\hat{x} | h, e_x = q)$ to denote the estimate using the encoding $e_x$ and the shared random value $h$. The optimization problem is then given by:

$$ \begin{array}{ll} \underset{S,R}{\text{minimize}} & \displaystyle\sum_{h \in [\ell], i \in [M], q \in [s]} S(h, q, A_M(i)) \cdot (A_M(i) - R(h, q))^2 \quad \text{subject to} \\ (\textit{Unbiasedness}) & \displaystyle\frac{1}{\ell} \cdot \sum_{h \in [\ell], q \in [s]} S(h, q, A_M(i)) \cdot R(h, q) = A_M(i) \quad \forall i \in [M] \\ (\textit{Probability}) & \displaystyle\sum_{q \in [s]} S(h, q, A_M(i)) = 1 \quad \forall h \in [\ell], i \in [M] \end{array} $$

$$ S(h, q, A_M(i)) \ge 0 \quad \forall h \in [\ell], i \in [M], q \in [s]. $$

The output of a solver that is given this problem as input is the sender table $S$ and receiver table $R$, that together form the quantization scheme.

## F Additional Distributions for Hyperparameters Ablation

In this appendix, provide runtime breakdown (Appendix F.1), time-to-$v$NMSE (Appendix F.2), and sensitivity to $\ell$ (Appendix F.3) results for additional distributions.

### F.1 Runtime Breakdown - additional distributions

We provide the runtime breakdown results for the Exponential(1) (Figure 16), Normal(0, 1) (Figure 17), Weibull(1, 1) (Figure 18), and TruncatedNormal(0, 1, $a = -1, b = 1$) (Figure 19) distributions.
<figure><img src="image_22.png" /><figcaption>(a) $s = 4, \ell = 2$.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(b) $s = 16, \ell = 2$.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(c) $s = 64, \ell = 2$.</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>(d) $s = 4, \ell = 4$.</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>(e) $s = 16, \ell = 4$.</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>(f) $s = 64, \ell = 4$.</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>(g) $s = 4, \ell = 6$.</figcaption></figure>

<figure><img src="image_29.png" /><figcaption>(h) $s = 16, \ell = 6$.</figcaption></figure>

<figure><img src="image_30.png" /><figcaption>(i) $s = 64, \ell = 6$.</figcaption></figure>

<figure><img src="image_31.png" /><figcaption>Fig. 16. Simba's runtime breakdown for different $s$, $\ell$ and $m$ values for the Exponential(1) distribution.</figcaption></figure>
<figure><img src="image_32.png" /><figcaption>(a) $s = 4, \ell = 2$.</figcaption></figure>

<figure><img src="image_33.png" /><figcaption>(b) $s = 16, \ell = 2$.</figcaption></figure>

<figure><img src="image_34.png" /><figcaption>(c) $s = 64, \ell = 2$.</figcaption></figure>

<figure><img src="image_35.png" /><figcaption>(d) $s = 4, \ell = 4$.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>(e) $s = 16, \ell = 4$.</figcaption></figure>

<figure><img src="image_37.png" /><figcaption>(f) $s = 64, \ell = 4$.</figcaption></figure>

<figure><img src="image_38.png" /><figcaption>(g) $s = 4, \ell = 6$.</figcaption></figure>

<figure><img src="image_39.png" /><figcaption>(h) $s = 16, \ell = 6$.</figcaption></figure>

<figure><img src="image_40.png" /><figcaption>(i) $s = 64, \ell = 6$.</figcaption></figure>

<figure><img src="image_41.png" /><figcaption>Fig. 17. Simba's runtime breakdown for different $s$, $\ell$ and $m$ values for the Normal(0, 1) distribution.</figcaption></figure>
<figure><img src="image_42.png" /><figcaption>(a) $s = 4, \ell = 2$.</figcaption></figure>

<figure><img src="image_43.png" /><figcaption>(b) $s = 16, \ell = 2$.</figcaption></figure>

<figure><img src="image_44.png" /><figcaption>(c) $s = 64, \ell = 2$.</figcaption></figure>

<figure><img src="image_45.png" /><figcaption>(d) $s = 4, \ell = 4$.</figcaption></figure>

<figure><img src="image_46.png" /><figcaption>(e) $s = 16, \ell = 4$.</figcaption></figure>

<figure><img src="image_47.png" /><figcaption>(f) $s = 64, \ell = 4$.</figcaption></figure>

<figure><img src="image_48.png" /><figcaption>(g) $s = 4, \ell = 6$.</figcaption></figure>

<figure><img src="image_49.png" /><figcaption>(h) $s = 16, \ell = 6$.</figcaption></figure>

<figure><img src="image_50.png" /><figcaption>(i) $s = 64, \ell = 6$.</figcaption></figure>

<figure><img src="image_51.png" /><figcaption>Fig. 18. Simba's runtime breakdown for different $s$, $\ell$ and $m$ values for the Weibull(1, 1) distribution.</figcaption></figure>
<figure><img src="image_52.png" /><figcaption>(a) $s = 4, \ell = 2$.</figcaption></figure>

<figure><img src="image_53.png" /><figcaption>(b) $s = 16, \ell = 2$.</figcaption></figure>

<figure><img src="image_54.png" /><figcaption>(c) $s = 64, \ell = 2$.</figcaption></figure>

<figure><img src="image_55.png" /><figcaption>(d) $s = 4, \ell = 4$.</figcaption></figure>

<figure><img src="image_56.png" /><figcaption>(e) $s = 16, \ell = 4$.</figcaption></figure>

<figure><img src="image_57.png" /><figcaption>(f) $s = 64, \ell = 4$.</figcaption></figure>

<figure><img src="image_58.png" /><figcaption>(g) $s = 4, \ell = 6$.</figcaption></figure>

<figure><img src="image_59.png" /><figcaption>(h) $s = 16, \ell = 6$.</figcaption></figure>

<figure><img src="image_60.png" /><figcaption>(i) $s = 64, \ell = 6$.</figcaption></figure>

<figure><img src="image_61.png" /><figcaption>Fig. 19. Simba's runtime breakdown for the TruncatedNormal(0, 1, $a = -1, b = 1$) distribution.</figcaption></figure>
## F.2 Time To vNMSE - additional distributions

We provide the time to vNMSE results for the Exponential(1) (Figure 20), Normal(0, 1) (Figure 7), Weibull(1, 1) (Figure 21), and TruncatedNormal(0, 1, $a = -1, b = 1$) (Figure 22) distributions.

<figure><img src="image_62.png" /></figure>

<figure><img src="image_63.png" /><figcaption>Fig. 20. Simba's time-to-vnmse for different s, l and m values for the Exponential(1) distribution.</figcaption></figure>
<figure><img src="image_64.png" /><figcaption>(a) s = 4, l = 2.</figcaption></figure>

<figure><img src="image_65.png" /><figcaption>(b) s = 16, l = 2.</figcaption></figure>

<figure><img src="image_66.png" /><figcaption>(c) s = 64, l = 2.</figcaption></figure>

<figure><img src="image_67.png" /><figcaption>(d) s = 4, l = 4.</figcaption></figure>

<figure><img src="image_68.png" /><figcaption>(e) s = 16, l = 4.</figcaption></figure>

<figure><img src="image_69.png" /><figcaption>(f) s = 64, l = 4.</figcaption></figure>

<figure><img src="image_70.png" /><figcaption>(g) s = 4, l = 6.</figcaption></figure>

<figure><img src="image_71.png" /><figcaption>(h) s = 16, l = 6.</figcaption></figure>

<figure><img src="image_72.png" /><figcaption>(i) s = 64, l = 6.</figcaption></figure>

<figure><img src="image_73.png" /><figcaption>Fig. 21. Simba's time-to-vnmse for different s, l and m values for the Weibull(1, 1) distribution.</figcaption></figure>
<figure><img src="image_74.png" /><figcaption>(a) $s = 4, l = 2$.</figcaption></figure>

<caption>(b) $s = 16, l = 2$.</caption>

<figure><img src="image_75.png" /><figcaption>(d) $s = 4, l = 4$.</figcaption></figure>

<caption>(e) $s = 16, l = 4$.</caption>

<figure><img src="image_76.png" /><figcaption>(g) $s = 4, l = 6$.</figcaption></figure>

<caption>(h) $s = 16, l = 6$.</caption>

<figure><img src="image_77.png" /><figcaption>Fig. 22. Simba's time-to-vnmse for different $s$, $l$ and $m$ values for the TruncatedNormal(0, 1, $a = -1, b = 1$) distribution.</figcaption></figure>
<figure><img src="image_78.png" /></figure>

------ Optimal ASQ ------ Simba

<caption>Fig. 25. Simba's vNMSE for different $l$ values for the TruncatedNormal(0, 1, $a = -1, b = 1$) distribution and $d = 2^{20}$. Even for $l = 2$, the improvement in comparison to optimal ASQ solutions (e.g., ZipML and Quiver) is significant. As $l$ increases, the additional improvement becomes marginal.</caption>

## F.3 The Number Of Quantization Sets $l$ - additional distributions

We provide the sensitivity to $l$ results for the Exponential(1) (Figure 23), Weibull(1, 1) (Figure 24), and TruncatedNormal(0, 1, $a = -1, b = 1$) (Figure 25) distributions.

<figure><img src="image_79.png" /></figure>

------ Optimal ASQ ------ Simba

<figure><img src="image_80.png" /><figcaption>Fig. 23. Simba's vNMSE for different $l$ values for the Exponential(1) distribution and $d = 2^{20}$. Even for $l = 2$, the improvement in comparison to optimal ASQ solutions (e.g., ZipML and Quiver) is significant. As $l$ increases, the additional improvement becomes marginal.</figcaption></figure>

------ Optimal ASQ ------ Simba

<caption>Fig. 24. Simba's vNMSE for different $l$ values for the Weibull(1, 1) distribution and $d = 2^{20}$. Even for $l = 2$, the improvement in comparison to optimal ASQ solutions (e.g., ZipML and Quiver) is significant. As $l$ increases, the additional improvement becomes marginal.</caption>
G Additional Distributions for Adaptive Quantization Algorithms Comparison

We compare to optimal ASQ methods for the Exponential(1) (Figure 26), Weibull(1, 1) (Figure 27), and TruncatedNormal(0, 1, a = -1, b = 1) (Figure 28) distributions.

<figure><img src="image_81.png" /><figcaption>Fig. 26. Comparing Simba (with varying $\ell$) to other adaptive solutions on an Exponential(1) distributed input.</figcaption></figure>

<figure><img src="image_82.png" /><figcaption>Fig. 27. Comparing Simba (with varying $\ell$) to other adaptive solutions on a Weibull(1, 1) distributed input.</figcaption></figure>
<figure><img src="image_83.png" /><figcaption>Fig. 28. Comparing Simba (with varying $ℓ$) to other adaptive solutions on a TruncatedNormal(0, 1, $a = -1, b = 1$) distributed input.</figcaption></figure>

## H Additional Distributions for Approximate Algorithms Comparison

We compare to approximate ASQ methods for the Exponential(1) (Figure 29), Weibull(1, 1) (Figure 30), and TruncatedNormal(0, 1, $a = -1, b = 1$) (Figure 31) distributions.

<figure><img src="image_84.png" /><figcaption>Fig. 29. Simba's vNMSE and runtime for different $s$ and $d$ values for the Exponential(1) distribution. Simba generalizes Apx. QUIVER and trades off some computation for accuracy. Both Simba and Apx. QUIVER are significantly more accurate and faster than other methods for increasing $d$ values.</figcaption></figure>
<figure><img src="image_85.png" /></figure>

<figure><img src="image_86.png" /><figcaption>Fig. 30. Simba's vNMSE and runtime for different *s* and *d* values for the Weibull(1, 1) distribution. Simba generalizes Apx. QUIVER and trades off some computation for accuracy. Both Simba and Apx. QUIVER are significantly more accurate and faster than other methods for increasing *d* values.</figcaption></figure>

<figure><img src="image_87.png" /></figure>

<figure><img src="image_88.png" /><figcaption>Fig. 31. Simba's vNMSE and runtime for different *s* and *d* values for the TruncatedNormal(0, 1, *a* = -1, *b* = 1) distribution. Simba generalizes Apx. QUIVER and trades off some computation for accuracy. Both Simba and Apx. QUIVER are significantly more accurate and faster than other methods for increasing *d* values.</figcaption></figure>