Optimal and Approximate Adaptive Stochastic Quantization
Authors: Ran Ben-Basat
Yaniv Ben-Itzhak
Michael Mitzenmacher
shay vargaftik
Venue: NeurIPS 2024 poster (2024)
Keywords: adaptive quantization
quantization
compression
algorithms
dynamic programming
Primary area: optimization
TL;DR: Optimal and near-optimal methods for unbiasedly quantizing large vectors on the fly while minimizing the mean squared error for the particular input

Abstract: Quantization is a fundamental optimization for many machine learning (ML) use cases, including compressing gradients, model weights and activations, and datasets. The most accurate form of quantization is adaptive, where the error is minimized with respect to a given input rather than optimizing for the worst case. However, optimal adaptive quantization methods are considered infeasible in terms of both their runtime and memory requirements.

We revisit the Adaptive Stochastic Quantization (ASQ) problem and present algorithms that find optimal solutions with asymptotically improved time and space complexities. Our experiments indicate that our algorithms may open the door to using ASQ more extensively in a variety of ML applications. We also present an even faster approximation algorithm for quantizing large inputs on the fly.

Optimal and Approximate Adaptive Stochastic Quantization
Ran Ben Basat
Yaniv Ben-Itzhak VMware Research
Michael Mitzenmacher Harvard University
Shay Vargaftik VMware Research
UCL
Abstract
Quantization fundamental optimization for many machine learning (ML) use cases, including compressing gradients, model weights and activations, and datasets. The most accurate form of quantization is adaptive, where the error is minimized with respect to given input rather than optimizing for the worst case. However, optimal adaptive quantization methods are considered infeasible in terms of both their runtime and memory requirements.
We revisit the Adaptive Stochastic Quantization (ASQ) problem and present algo- rithms that find optimal solutions with asymptotically improved time and space complexities. Our experiments indicate that our algorithms may open the door to using ASQ more extensively in variety of MI applications. We also present even faster approximation algorithm for quantizing large inputs on the fly.
Introduction
Quantization is central to optimizing large range machine learning (ML) applications. is often used for compressing gradients to reduce network requirements in distributed and federated learning
4 5 6); for quantization of datasets for faster training and inference (c.g., [7]:: and for reducing the memory footprint while accelerating the computation for large models' inference via post-training quantization (e.g., ()) and quantization-awan training (e.g., [10] of model weights, activations and key-value (KV) caches [12].
(c.g., [ 2
3
fundamental quantization method is stochastic quantization, where one quantizes an input vector X E d to X E Q" using set Q C. IR of [Q] = 5 quantization values so that each entry is unbiased [33. That is, each x E X is (randomly) quantized to a value â E Q such that E [
Previous unbiased quantization works considered different approaches. Some are distribution- agnostic, i.e., design the quantization without optimizing it for the specific input. For example, [4] 15] set quantization values with respect global properties such as the vector's norm, or minimum and maximum values.
T9 optimize for the worst X by applying a reversible transformation (e.g., the randomized Hadamard transform) before quantization that converts it into a vector X' with controlled distribution (e.g., with max(X') min(X') (X'') = O( / /Vd). The decoder then applies the inverse transformation the quantized X' to obtain estimate of X.
Other works, e.g.,
18
In contrast, some solutions use the fact that, in many cases, the inputs to be quantized have a significant structure that can be leveraged reduce the quantization error. For example, DNN gradients (which are often compressed in distributed and federated learning applications to reduce bandwidth [20 21)
were observed to follow LogNormalllike [22 Normal-like 23 24 distributions. As another example, the distribution of deep activation layers appears to follow a nub-Weibull distribution 25
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

To alleviate the need to assume an input distribution, the Adaptive Stochastic Quantization (ASQ)
problem (e.g., 26 27 2 considers selecting Q adaptively, ie., with respect to the specific input X, that minimizes the mean squared error (MSF, also known as the sum of variances) given by
x - x x
E
Σ mEX
Var(a]
where X = { x E X3 is the vector of quantized values.
Unfortunately, known ASQ solutions are practical for the large-size vectors that commonly appear in MI applicatinss One aspect of the problem's 's difficulty is that is known to be non-convex even for (two-bit quantization)
[23]. which excludes many natural solution methods such as gradient descent. ZipMI. [26] approaches the challenge using a dynamic programming approach that allows one to optimize Q in polynomial time. However, this solution has significant overhead and solving the problem optimally is often considered to be impractical; for example, (28) states
"To find the optimal sequence of quantization values, a dynamic program is solved whose computational and memory cost is quadratic.... For this reason, ZipML is impractical for quantizing the fly".
As another evidence of the problem's 's hardness, previous work 27 solves the problem only for given (Weibull) distribution, writing that
"The empirical distribution is usually non-differentaable making the searching of Q infeasible".
Nevertheless, there is significant interest in advancing ASQ solutions towards wider adoption as even approximate adaptive solutions like ALQ (28) have been shown have lower MSE than advanced distribution-ggnose
methods such Non- Non-Uniform QSGD (NUQSGD) [29]. ASQ methods can also improve more complex schemes (e.g.. including the aforementioned that utilize worst-case to average-cass case transformations) by replacing distribution-agnosiic quantization with an adaptive one.
In this paper, we show that one can, in fact, solve the ASQ problem optimally and efficiently. To this end, introduce QUIVER, an algorithm that features novel acceleration methods and leverages the structure of the underlying problem to reduce the runtime complexity from (s dd) to ( d) and the space complexity from O(P) (s d).
This improvement arises from the observation that the optimal solution, for given input parameters 8, d, can efficiently derived from the solutions for {s 1, d' E (2,, d}} by a reduction to the problem of finding the row maximas in an implicitly defined totally monotone matrix. This problem is known to have fast algorithms assuming that, for any S j S d, the sum of variances of points {Ik..... 2,} can be computed in constant time when quantized to {Ik: 2y property that is achieved by our new preprocessing method.
We then further accelcrate QUIVER by deriving a closed-form solution for s 3. In turn, this yields a faster solution for any s, by a variant of QUIVER that places two quantization values at a time instead of one. Finally, by discretizing the search space for Q. we show fast approximation variant of QUIVER. This variant introduces an appealing tradeoff between accuracy and speed, making it suitable for quantizing large vectors on the fly.
We implement algorithms in C++ and demonstrate their efficiency. For example, commodity PC, QUIVER can compute the optimal 4-bit quantization values (s = 16) for a vector with d = 1M entries in under second and compute accurate approximation in just six milliseconds. We evaluate our solutions compared to state-of-the-an ASQ methods on a variety of distributions considering different vector sizes and number of quantization values and demonstrate speedup of up to four orders of magnitude. We open source the code of the paper [30]
We note that there are many works that investigate different forms of compression, including non-adaptive quantization (e.g., QSGD [14), biased quantization (e.g., top-k (3I)), sparsification (e.g., (2)., sparse coding (e.g., (33). low-rank decomposition (c.g., PowerSGD (34] variable-length coding (e.g., EDEN 44) and more. Many of these orthogonal conjunction with it. For example, one can use ASQ to quantize a sparsified or transformed vector or apply variable-length encoding further reduce the size of the quantized vector.
work and can be used in

---

10
10a
Mean Eztmatin
MSE
10a
20
10
10-t
1.0
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
2
2
2
2
2
2
Number of vectors
(a) Single vector estimation.
(b) Distributed mean estimation.
QSGD (Unbiased, Non-adaptive)
E
NUQSGD (Unbiased, Non-adaptive)
RTN (Biased, Non-adaptive)
Optimal Adaptive Blased
+ Optimal Adaptive Unblased
Figure An experiment with dimension d = 10M and 10 quantization values. Figure (()) shows the empirical MSE of quantizing single vector with i.idd LogNormal o²) entries. It shows that adaptive methods are more accurate than non-adaptive and that the optimal biased method is more accurate than the optimal unbiased one. However, shown in Figure [(b] for distributed mean estimation, the bias may not cancel out when averaging quantized inputs (here, we used a standard setup where all vectors and the advantage of unbiased methods accordingly increases with the number of inputs. Each data point is averaged over runs with the standard deviation reported.
identical, e.g., see [17), with i.i.d. LogNormal 1 1/2) distributed entries)
2 Background
2.1 Motivation
We now briefly explain the benefits of ASQ compared to alternative methods.
The benefits of adaptivity Unbiased solutions such as QSGD [1] and NUQSGD 29
rely only on global properties (e.g., the input's norm) when selecting Q. Figure I(a) shows the benefit of adaptivity by illustrating the potential MSE reduction from selecting Q optimally for the specific input. A similar behavior observed for biased methods where the non-adaptive Hound-To-Nearte (RTN) has higher error than the optimal adaptive biased scalar quantizer, k- k-means. As shown, this can translate to orders of magnitude lower error, depending on the data's skew.
The benefits of unbiasedness In many cases, is beneficial for the quantization be unbiased. For example, when there are senders (e.g., when doing distributed mean estimation 2 4 17 18] 18). having unbiased and independent estimates of the vectors allows the mean estimation's 's MSE to decay proportionally to 1; with biased quantization, the MSE may not decay with respect to n since the errors may be correlated [17 (e.g.. when all clients have the same vector). This benefit demonstrated in Figure [(b) which shows that while biased adaptive solutions have lower error for small number of vectors (1-2), having unbiased quantization critical lowering the error for large n.
As another example, it was recently shown that compressing large language model parameters with biased techniques such as RTN may result in inferior performance than uniform stochastic quantization [35]. This outcome arises because the LLM layers' parameters are used to compute inner products with their inputs. Having these inner products themselves be unbiased leads to smaller errors in layers' outputs, which in turn leads to better performance.
2.2 Preliminaries
Given two quantization values a, b and number E [a, b), Stochastic Quantization (SQ) a proce- dure that rounds to T. where 전 E (a, Specifically, E obtains the value with probability Pa b-z b-a and the value otherwise, i.e., with probability ps = 1 Pa b-a
r-a An important property of SQ
that the expected rounded value is unbiased, i.c., E [ a. + +b.pb
The variance of stochasti-
cally quantizing æ is then given by E (I 2) (x a²² + (x-b)² b)2 Ps = (b x) a). Given a vector X R and an integer 2 2, the Adaptive Stochastic Quantization (ASQ) prob- lem 266 27 28 looks for a set of quantization values Q where |Q| < s and Q minimizes the mean squared error (MSE) that results from rounding X to X E Q' by stochastically quantizing each entry X with values a max {q Q g ] and b min {q E Q q 2 x).
Formally, ASQ seeks to minimize the MSE, given by E X
Σ (br x)(x ax),
where [ X holds by construction.
3

---

2.3 Existing ASQ methods
Leveraging the fact that there exists an optimal solution in which Q S X [26 (i.e., the quantization values a subset of the input), can naively solve the problem in d8(s) time by going over all choices for the quantization values. Instead, the following dynamic program (DP) allows us to solve optimally and in polynomial time for any s [26]. Given sorted vector X (Fi,.... Td). we denote by MSE(i,) j] the optimal MSE of quantizing the prefix vector Xj = (Z1,..., 2z) using i quantization values that include Ij, that is:
min MSE QUQ
Σ (bz 2) az). x
Our goal is to compute a set of quantization values Q that results in an optimal MSE of MSF[s, d]. Accordingly, we express the dynamic program as follows. We first define Clk, as the sum of variances of all vector entries in the range [xx, Iz} where Tk, Iy E Q are two consecutive quantization values, i.c., Cik, ExElex. (zg x) Ik). Here and when clear from context, to simplify notation, we write Σn to denote Exex.
ior (2....,st,3 {i....,}, we set MSE[2, C[I, Vj and use the recurrence
MSE
MSE 1, [ C[k.]]. ke (E...)))
min
Here, the index is denotes the entry in X, Fk. of the rightmost quantization value to the left of zy. A naive solution for the above DP is first to compute the matrix C' (which takes O(d3) time and (dd) space) and then calculate (s for all i, and thus Q in O(s d2) time and O d) space. In Appendix A we describe simple algorithm that implements this dynamic program.
An improved solution, ZipML (26], uses ((s d)) time and Odd) space, but it remains infeasible even for moderate (e.g.. d = 10a) dimensions. Accordingly, we next design novel techniques to asymptotically improve both the space and time complexities.
Optimization Using Pre-processing
The first ingredient in our solution is the usage of preprocessed arrays that allow us to efficiently compute C[k.j] j] in constant time, at the cost of only O(d) additional space. We define the following arrays, 8,7 7 E Rdd. that store the cumulative sums of the vector and its squared entries:
3, 3,= R
73 Σ 2 x
Vj E (1.....d)
Denoting 30 7oo 0, both are computable in O(d) time By By-1 + I, and 7 Y--1 + 27.
We can then express Clk, ji as follows:
C[k, = Σ
(xy x= - -rt)=
Σ
(xj 2:)(1 xK)
x
=E(re.ry)
1 (xy + xx) Σ I Σ ?
= -- Ik
xE(zE.m,)
=E(
zzz Fx
k) + (z) + xx) (8, Bk) (7p 7K).
With this optimization, we can evaluate Clk jl in constant time, yielding solution that uses ((s- memory instead of (d.). .. Next, we show how to improve the runtime.

---

The QUIVER Algorithm
To derive faster algorithm, observe that C' satisfies the quadrangle inequality, defined below:
Definition 4.1. A function w: (l...., df x {1..... d} + satisfies the quadrangle inequality if for any aSbScSd: w|a, c| + w(b, d] I wfa, d] + wlb, c].
Lemma 4.2. satisfies the quadrangle inequality.
Proof. We first observe that for any x E [Ta, Tbl:
(oe (2 xa) (za 2x vaa) (ore xa)( 22)) (aa x)(x v2).
(1)
For any x E ma). we similarly get:
(es (x u.) (ea <x - x.) (dra x2) anh) I (ua xx 2.).
(2)
Similarly, for x E [xn, vel, we have that:
(ms- - =x va) + (Ia - (x - mn) = (Ie - x) - 1b) + (xa 2)(x Ha) + (aa - 2x) - Ie)
< (xc x)(x - -x)) + (ea 2) xa).
(3)
Therefore, get:
+
Σ
(Ie 2) xza +
Σ
(Ia - 2) - Ib)
xE(Turza)
=Ea We-z)((a) Na)
(wa- vo)
Σ
(xe- 2x vsa) + (Ja 2x) (x))
#E REm
Σ (It 2x) (xaaaa) +
Σ
(It ()) (x-
Σ
(xe=x)(1-u) +Ia - x) xa))
#E mm)
xE me
#E mE
(xa- - (x Ta)
(Ie x) Ib)
Cla + Clb, c).
Here, the inequality follows from equations -13
Next, let us implicitly define matrix A E (I.....)) (I......) such that A[k. MSE k C]k, Importantly, A is not stored in memory but admits constant time lookups as MSE 1, stored and C' is efficiently computable (Section 3 Also, C satisfies the quadrangle inequality and thus A is a totally monotone matrix (36). i.e., for any a and c < d: (A(a, > A[b, c])
(A(a, d] >> Alb, d)). By applying the SMAWK algorithm [37] which finds the row minimas of an implicitly defined totally monotone matrix, on AT, we obtain in O(d) time and space the indices kj argmink Alk, j] for all {1...., d). This immediately gives the next row of the dynamic program, MSE j] MSE - 1, ky] + C[ky.j].
The resulting solution, which we call QUIVER, is given in Algorithm and requires just O(s d) time and space to compute the optimal quantization values.
5 The Accelerated QUIVER Algorithm
To accelerate QUIVER, we rely on the observation that while the problem is non-convex for >> 3, admits flosed-fomm solution when = 3.
Denoting by [k. = minge (C b) + C(b,j)) the optimal MSE of quantizing the range [y), using three quantization values (at Øks Tb, IT)), we show how to compute C in constant time.
Namely, consider adding a quantization value E [5k, 2y] (not necessarily in X) between two existing quantization values 24 and zy. Let us define the sum of variances of all input entries in [æg, æy as a function of Q(q) Exele
<x Ix) + Exe(n,,) (z, - Ix - 4). This function is differentiable in [zk 2, \ X, and get: dQ(a) Ene(nan (x zx) Exe(g,e, 2).
dg
5

---

Algorithm QUIVER
1: Input: X RRd, N.
X is sorted. Enables computing C] in constant time (Section 3)
2: Preprocess( (X)
3: for jor
do
4: M C[L.j]
5: for iori=: 3o do
6:
D. Where Alk. è MSE 1, + C(A.] Vk.j. [S = MSR 1, K [r,]]] ((K))))) for all j E (l.....d).
Kli,
SMAWK( A)
7:
8: Q- (21,
9: d
10: for = down to 3 do K[i,j]
11:
12: Q = QU {zy}
13: return Q
Algorithm 2 Accelerated QUIVER
1: Input: X RR E N.
b X is sorted.
2: Preprocess XX)
Enables computing Clk: j] and [R: in constant time.
3: s' = (s mod 2)
4: if
then
5: for = 2 to d do
6:
MSE C[1,
7: else
8:
for
j to d do
9:
[3 = [²
= to [s/2] do Kii, SMAWK( B) 12: MSE it + s' %'] MSE (i + + c9IKi..5,. Vj dd. d].
10: for
Where B[k,j] & MSB +,,,) Wk,j.
Q {21,2a}
14: d
for = [s/2] down to do
16: b" = arrgmn b (K(K))...)) () C(b.j))
>> Takes O(1) time.
17:
18:
Q QU (Tis Tb
19: if s' 1 then
20:
b* argming (f. of [C[0,b)+CC
> Takes O(1) time.
21:
Q = U (28.}
22:
return Q
Notice that the derivative is monotonically non-decreasing and for any é. E {k. + 1,....j 1} the derivative fixed (independent of q) over any interval (Ize x1+1). This means that Q(q) is minimized at = inf, dy 2 0). where u X. Denote by big E {k......} the value such that Zbg = u.
dQig)
4Q(u+h) 2 0 is well-defined. Notice that while dQ(w) may not be defined, we have that lim dg
dg
We thus require equivalent to: El k+1 2; (bh K)II - (j -bb,) bz 2 0, yielding 6i jaz kzre Elart
Σ bi
1ink4 (#: Ixk) Ei 1 ( (Ir xT)) 0. With some simplifications, this is
2--02
As big is integer, we get formula for C² j] that can be computed in constant time using: b j2.- 2
E -1- pe (0, ( 1. That is, for any 1 < k < j < d we have that 5.- = Ca = Clk, b Clb il is the sum the variances in quantizing the entries in [ak æ,] using the quantization values {Ix, 2bt 2.).

---

We can then use this method to halve the required number of invocations of SMAWK by always using it to pick the second-next quantization value and computing the optimal quantization value in between directly. Our accelerated dynamic program is then given by:
min ke(
MSE - 2, [k i> 3
MS
[1
i= 3
C[1.5]
==2
and the resulting pseudo-code for Accelerated QUIVER given by Algorithm Similarly to QUIVER, start by initializing the first row of MSE. Importantly, now separate the even
(lines 5 6). in which we initialize the row using C, and the odd case, where we use C2 (lines 9 That
is, the odd case 'skips' quantization value that we later determine separately (lines 19 21. Next.
denoting s' = (s mod 2), we proceed with [s/2] -1 invocations of the SMAWK algorithm (lines 10
12). applied on the implicitly defined matrix B B] _ MSE (i-1)+ [i [*K(i,
The output yields the minimizers of MSE i+''', used for reconstruction. In the reconstruction
step (lines T5 2T). we fill in the missing quantization values by finding the optimal value between every two outputs from the dynamic program minimizers K.
Overall, the Accelerated QUIVER algorithm requires at most half of the number of SMAWK invocations compared to QUIVER and most half of the memory to store K and MSE.
To establish correctness, we state the following lemma, whose proof appears in Appendix
Lemma 5.1. C² satisfies the quadrangle inequality.
In Appendix D we discuss why this approach is not suitable for further acceleration by placing more than one quantization value in [x,,
6 The Approximate QUIVER Algorithm
We now show how the usage of quantization value discretization gives a controllable tradeoff between accuracy and speed. Intuitively, by allowing the quantization values to be placed only uniform grid of controllable size m + 1 2 s (for some m E N we can accelerate the computation at the cost of small additional error. Importantly, while the quantization values are from discretized set of possibilities, we compute the optimal subset of discretized values for the original input vector.
To that end, consider the discrete set S = {x1 + l Zg-01 | E {O....,m)) mm.} Our goal is then to find Q (5) that minimizes the sum of variances for the original input. Denoting st 21 + Fa we modify our preprocessing scheme to consider the discretization:
0i =
Σ xr [
Σ
x
76
Σ
2
vl (1....,m)
xE [x)
2E(50.51]
As we explain in Appendix we can compute these values in ((d) time and space.
Using these arrays, we can express the sum of variances all input entries between two quantization values 8k, 8j as follows:
Cmlki
Σ (sj - 2x - sk)= = Σ
(8j - x) - sk)
zE|su.ayl
zE(su.8z)
1 (3) sp) Σ
Σ x²
= Skk
zE(SL
*E(Sk.8,]
xE(*
=-8j (aj - 0..) + (sj + +x) (3, - Bx) - (13 -
7

---

Note that the quadrangle inequality trivially holds for this extension. The resulting algorithm, termed Approximate QUIVER (or short, Apx. QUIVER), proceeds as QUIVER with C. instead of C, except for the reconstruction stage where we pick Q from S instead of the input X. Apx. QUIVER, whose pseudo-code given Appendix F. runs in space and time complexities of O + m 8).
We next analyze the approximation guarantee of Apx. QUIVER. Denote by opt the optimal 2--2 MSE attainable for X using quantization values, and by AQx-2s-2 the MSE of Apx. QUIVER with
2s 2 values. We prove that the MSE of Apx. QUIVER with 2s 2 quantization values is close to the optimal algorithm with s values. In practice, we generally find Apx. QUIVER does better than the bound below, and for moderate m, it is nearly optimal.
Lemma 6.1. For any X, 8, have AQx 25 optx,s x,s + d-(2--11) 4m
4II 2m
x, +
Proof. Let Q" S X be the optimal solution with |Q"| S 8. For any E Q", denote by g
max {ss E S 8, S q) and 7 = min {8r E S 8t 2 4). Consider the solution Q {g. T q E Q*)
Note that I@| < 2s as 21, E Q" and .ं 21 and Fz- = Id. Also, Q C S and is thus
valid solution of Apx. QUIVER. Thus, 2 is upper bounded by the MSE when using Q
Next, consider X and let a₂ = max {q E Q" q S x} and b, min {q e Q" g 2 x} be the values between which is stochastically quantized in Q* We consider two cases:
x E (ag a (ba, bn]. In this case, when using Q, we have that is quantized in an interval of size (ra - x1)/ mm and thus its variance is bounded by (xa - x1)² /4m².
x E (a,, by]. in this case, using Q is quantized between a, and bz yielding a variance of (62 - ()) a I (by- (x az), i..., lower than the variance under Q*
As the two capture all options, summing the variances over all X yields the result.
In terms of the vector normalized MSE (vNMSE) !
which is a normalized MSE measure given by
X- Apx. QUIVER with 2s 2 2 quantization values achieves an additive 2m
term to the
[ optimal vNMSE when using quantization values.
However, the first inequality of Lemma 6. is generally much tighter than the second that uses the squared norm. For example, if the entries of X were i.i.d. Ula, b) random variables, for some
constants a < b then (Iaa x²)² (1)) while || = (d)). Similarly, for i.i.d ((1, o?) entries for constants μl a we have (Ia xx1)² Ollog d) while || = (dd) (both with high probability).
7 Evaluation
We evaluate our algorithms' empirical vNMSE and runtime against SOTA ASQ solutions.
Setup. We implement all algorithms in C++. Unless stated otherwise, we use g4dn 4xlarge AWS EC2 server with custom Intel Cascade Lake CPUs with 64 GB RAM and Ubuntu 22.04 OS and average all results over 5 seeds.
Acceleration Speedup Appendix G shows the speedup attainable by Accelerated QUIVER, As we show, Accelerated QUIVER is consistently faster than QUIVER, providing up to 5.4x speedup.
Distributions. All experiments are done with vectors whose entries are independent and identically distributed. We present results for the LogNormal distribution and defer to Appendix H results for Normal, Exponential, TruncNorm, and Weibull distributions. As mentioned, these distributions are of interest as they are reported to capture gradients, model weights and activations (see Section
'This metric is standard in quantization works (e.g., see 17 and the references therein). It enables us to reason about the results among different dimensions and distributions.

---

Time (ms)
10a
VNISSE
10 1
VNMSE
10
10a
10-1
10-1
10
2
2
21
2
2
2
2
24
2
2
2'
2
2
2
Time [ms]
10a
Time (ms)
10
Time [ms]
10f
10a
10a
10a
10
10-1
2
2
2
2
22c
2
2
2
2
2
2
2
2
2
Dimension (d)
# #Quantization values (5)
#Quantization values (s)
(a) 8 (upper), = 16 (lower).
(b)
2
(c) = 2
ZipML
Acc. QUIVER
Figure 2: Comparing exact solutions with LogNormal(0, 1) distributed input.
VNMSE
10
VIIMSE
10
10a
VNMSE
101
10-1
10-1
20
10-3
2
25
2
2
22
2
2
2
2
2
400
Time [ms]
103
Time [ms]
Time [ms]
10
10
102
10-1
22
2
2
2
2
2
2
24
2
2
200
400
600
800
1000
Dimension (a)
#Quantization values (s)
m
(a) 16 and m 400 bins.
(b) d 2 and m 1000 bins.
(c)
222 and 32.
ZiPML-CP Unif.
ZipML-CP Quant.
ZipML 2-Apx Optimal
ALQ
Apx. QUIVER
Figure 3: Comparing approximate solutions with LogNormal(0, 1) distributed input.
Baselines. We evaluate Accelerated QUIVER and compare its runtime ZipML 26)]. For the approximate variants, we evaluate Apx. QUIVER and compare it with three approximation variants of ZipML proposed in [26]. namely ZipML-CP Quantiles. ZipML-CP Uniform, and ZipML 2- Approximation. ZipML-CP is an algorithm that runs the exact ZipML algorithm on subset of the points called 'Candidate Points'. Since ZipML runs (dd)s time, here we use candidate points to get O(d + M2s) time. ZipML 2-Apx is an algorithm that computes an approximate solution in (d + 5²) time. It guarantees that its sum of variances at most twice that of an optimal solution with [s/2] quantization values. We also compare with the recently proposed ALQ (28), which an algorithm that finds good quantization values for truncated normal distribution. samples several gradients (by computing the gradient of several random batches) to fit the truncated normal parameters. To be fair to ALQ, since we evaluate a single-shot quantization scenario, we calculate the exact mean, variance, and support parameters for the input vector. This then runs for several (we used 10, as their released code) iterations, so in total, they compute zs 10s integrals. While theoretically requiring (dd) time, in model where such integral calculation takes constant with low- low-precision integral caleulations, may improve the runtime, but the error (which is already not competitive) will degrade further. We further discuss these approximation algorithms in Appendix
time, this is markedly slower than other approaches. We note that it possible that
Exact algorithms experiments. The results are presented in Figure 2 Figure 2(a) shows the runtime for optimally solving the ASQ problem for different dimensions and s. As shown, our solutions are markedly faster than ZipMI. which we are unable to run for dimensions d > 217 due to its prohibitively large memory requirements. The asymptotic difference (O(s d²) for 7ipMI. and O(s d) for Accelerated QUIVER) is clearly visible in the different slopes on the log-log plot. As

---

result, Accelerated QUIVER can efficiently quantize vectors. For example, Acc. QUIVER can compute the optimal 4-bit (s 16) quantization values for 1M-sized vector in under a second.
Next, Figure 2(b) and Figure 2 show the vNMSE and runtime with respect to the number of quantization values for d = 2 and d 2 As shown, the vNMSE decays linearly with while the runtime increases linearly. Even for these small dimensions, our algorithms are orders of magnitude faster than ZipML.
Approximate algorithms experiments. The comparison results are presented in Figure It is evident in Figure ((a) that approximate solutions are significantly faster than exact ones. Also, Apx. QUIVER offers both near-optimal vNMSE and the fastest runtime as the dimension increases. As shown in Figures 3(b) and Apx. QUIVER offers these advantages for different 8, values.
Notably, on commodity PC, Apx. QUIVER can compute near-optimal 4-bit quantization values (s = 16) for vector with d = 2 entries in just six milliseconds, and about 70ms for d = 224, potentialll enabling quantizing vectors on the fly for many applications.
8 Discussion
In this paper, we presented algorithms for the Adaptive Stochastic Quantization (ASQ) problem with improved space and time complexities compared to the state of the art. For parameters of interest, our exact algorithms are up to four orders magnitude faster compared to the alternatives while using markedly less memory. To potentially enable on-the-fly adaptive quantization of vectors, we also introduce an approximate algorithm with strong guarantees that runs faster while being significantly more accurate than other approximate solutions.
Limitations: QUIVER is not GPU friendly, and it remains an interesting future work to design GPU- friendly ASQ algorithms. Also, similarly to previous works (c.g., (26)), our exact solution assumes that the input vector is sorted. Otherwise, the runtime is increased to Old log + s.d). We note that
Apx. QUIVER does not require the vector to be sorted and the time complexity remains O(d + s s.m)
for non-sorted imputs, making it even more appealing compared to the exact solutions.
For exact algorithms, one sort the input vector on GPU, bringing the CPU solution complexity to O(s d) which is faster for large vectors. In practice, GPU sorting is rarely the bottleneck; indeed, in Appendix we measure the time it takes to sort the vector on a T4 GPU, and also to quantize the vector after an ASQ outputs the optimal quantization values. For example, the sorting and quantization time for LM-sized vector sums up only 4ms where the runtime of Accelerated QUIVER is about one second.
Offloading Computation to GPU:
Generalizing the algorithms for weighted inputs: An interesting generalization of the ASQ problem is the weighted variant, where each entry F; X is associated with a weight w; and the goal is to minimize the weighted sum of variances Σi= (z; - f2)² w; This variant is useful when, instead of getting an input vector, one wishes to solve ASQ for empirical distribution. In Appendix we explain how our algorithms and their analyses generalize to the weighted case, while maintaining the Old s) and O(d + M s) runtime and space complexities for QUIVER and Apx. QUIVER accordingly. Our measurements indicate that the weighted variants are only 10-20% slower than their unweighted counterparts.
Reproducability: All our results are reproducible and our code open sourced (30
Acknowledgments and Disclosure of Funding
We thank Wenchen Han for his insightful comments and suggestions. Michael Mitzenmacher was supported in part by NSF grants CCF-2101140, CNS-2107078, and DMS-2023522
10

---

References
[1] A. T. Suresh, X. Y. Felix, S. Kumar, and H. B. McMahan, "Distributed Mean Estimation With Limited Communication," in International Conference Machine Learning. pp. 3329-3337.
PMLR, 2017,
[2] J. Konečný and P. Richtárik, "Randomized Distributed Mean Estimation: Accuracy vs. Commu- nication," Frontiers in Applied Mathematics and Statistics, vol. 4, p. 62, 2018.
[3] S. Caldas, J. Konečný, 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-Effiiii 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. $356-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," HotNets, 2024.
[7] D. Zhou, K. Wang, Gu, Peng, D. Lian, Y. Zhang, Y. You, and Feng, "Dataset Quantiza- tion," in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2023, pp. 17205-17216
[8] E. Frantar, S. Ashkboos, Hoefler, and Alistarh, "OPTQ: Accurate quantization for genera- tive pre-trained transformers," in The Eleventh International Conference on Learning Represen- tations, 2023.
[9] 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-14461.
[10] Micikevicius, S. Narang, Alben, G. Diamos, E. Elsen, D. Garcia, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh al., "Mixed Precision Training." in International Conference on Learning Representations, 2018.
[11] 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.
[12] Y. Sheng, L. Zheng, B. Yuan, Z. Li, M. Ryabinin, B. Chen, P. Liang, C. Ré, I. Stoica, and
C. Zhang. "Flexgen: High- Throughutth Generative Inference of Large Language Models With Single GPU," in International Conference Machine Learning. PMLR, 2023, pp. 31 094- 31 116.
[13] 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 Automata, Languages, and Programming (ICALP 2021), vol. 198, 2021, p. 25.
[14] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic, "QSGD: Coamuunication-Effiicee SGD via Gradient Quantization and Encoding." Advances in Neural Information Processing Systems, vol. 30, pp. 1709-1720, 2017.
[15] S. Horvóth, C.-Y. Ho, L. Horvath, A. N. Sahu, M. Canini, and P. Richtárik, "Natural Com- pression for Distributed Deep Learning," Mathematical and Scientific Machine Learning. PMLR, 2022, pp. 141-
[16] M. Safaryan, F. Shulgin, and P. Richtárik, "Uncertainty Principle for Communication Com- pression Distributed and Federated Learning and the Search for an Optimal Compressor," Information and Inference: A Journal of the IMA, 2020.

---

[17] S. Vargaftik, R. Ben-Basat, A. Portnoy, G. Mendelson, Y. Ben-ltzhak, and M. Mitzenmacher, "Drive: One-bit Distributed Mean Estimation," Advances in Neural Information Processing Systems, vol. 34, pp. 362-377, 2021.
[18] R. B. Basat, S. Vargaftik, A. Portnoy, G. Einziger, Y. Ben-ltzhak, and M. Mitzenmacher, "Accelerating Federated Learning with Quick Distributed Mean Estimation," in International Conference Machine Learning, 2024.
[19] X. Chen, S. Vargaftik, and R. Ben-Basat, "When ML Training Cuts Through Congestion: Just-in- Time Gradient Compression via Packet Trimming," in Homnets, 2024.
[20] Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, T. Suresh, and D. Bacon, "Fed- erated Learning: Strategies for Improving Communication Efficiency," arXiv preprint 1eXvv:611.00492 2017.
[21] 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.
[22] B. Chmiel, L. Ben-Uri, M. Shkolnik, E. Hoffer, R. Banner, and D. Soudry, "Neural Gradients are Near-Lognormal: Improved Quantized and Sparse Training." in International Conference Learning Representations. OpenReview.net, 2021. [Online]. Available: Networks for https//opeeeeviiiveeccoooomrr/l/
[23] R. Banner, Y. Nahshan, and D. Soudry, "Post Training 4-Bit Quantization of Convolutional
in NeurlPS, 2019.
[24] X. Ye, P. Dai, J. Luo, X. Guo, Y. Qi, J. Yang, and Y. Chen, "Accelerating CNN Training by Pruning Activation Gradients," in European Conference on Computer Vision. Springer, 2020, pp. 322-338.
[25] M. Vladimirova, J. Arbel, and P. Mesejo, "Bayesian Neural Networks Become Heavier-Tailed With Depth," in NeurIPS 2018-hhinty-second Conference on Neural Information Processing Systems, 2018, pp. 1-7.
[26] H. Zhang, J. Li, K. Kara, D. Alistarh, 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.
[27] F. Fu, Y. Hu, Y. He, J. Jiang, Y. Shao, C. Zhang, and B. Cui, "Don't waste your bits! squeeze activations and gradients for deep neural networks via tinyscript," in International Conference on Machine Learning. PMLR, 2020, pp. 3304-3314.
[28] F. Faghri, I. Tabrizian, I. Markov, D. Alistarh, D. M. Roy, and A. Binezznni-Kebras "Adaptive Gradient Quantization for Data-parallel SGD," Advances in neural information processing systems, vol. 33, pp. 31 3174-3185, 2020.
[29] A. Ramezani-Kebbya, F. Faghri, I. Markov, V. Aksenov, D. Alistarh, and D. M. Roy, "NUQSGD: Provably Communication-effiiienn Data-parallel SGD via Nonuniform Quantization," The Journal of Machine Learning Rexearch, vol. 22, no. 1, pp. 5074-5116, 2021.
[30] "QUIVER code," hutpss//eiibbbcco////mbabaaau/uu
[31] S. U. Stich, J.-B. Cordonnier, and M. Jaggi. "Sparsified sgd with memory," Advances in neural information processing systems, vol. 31, 2018.
[32] J. Fei, C.-Y. Ho, A. N. Sahu, M. Canini, and A. Sapio, "Efficient Sparse Collective Communica- tion and its Application to Accelerate Distributed Deep Learning." in Proceedings of the 2021 I ACM SIGCOMM 202/ Conference, 2021, pp. 676-691.
[33] V. Monga, Y. Li, and Y. C. Eldar, "Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing," IEFE Signal Processing Magazine, vol. 38, no. 2, pp. 18 44, 2021.
12

---

[34] T. Vogels, S. P. Karimireddy, and M. Jaggi, "PowerSGD: Practical Low-Rank Gradient Com- pression for Distributed Optimization." in Advances Neural Information Processing Systems, vol. 32, 2019.
[35] M. Nagel, R. A. Amjad, M. Van Baalen, C. Louizos, and T. Blankevoort, "Up Down? Adaptive Rounding for Post-training Quantization," in International Conference on Machine Learning. PMLR, 2020, pp. 7197-7206.
[36] Z. Galil and K. Park, "A Linear-time Algorithm for Concave One-dimensional Dynamic Programming." Information Processing Letters, vol. 33, no. 6, pp. 309-311, 1990.
[37] A. Aggarwal, M. Klawe, S. Moran, P. Shor, and R. Wilber, "Geometric applications of matrix searching algorithm," in Proceedings of the second annual symposium on Computational geometry, 1986, pp. 285- 292.
[38] "Example SMAWK code," http::/wwww..ooooooccccccccccce/ 117244_SMAWK SMAWK, K_totllllll____t_ monotone _aatri_maatt_____ mat_mmmaatatttttaaa seauching/recipe-111244pp accessed -M-MM...
13

---

Algorithm 3 Basic Dynamic Programming Algorithm
Input: X Rd N.
2: Compute C': [d] x [d] + Rt using X.
3: for j to d do
4: MS = C[L.j]
5: for 3 do
6:
for jarj= ji to do MSF [1.
7:
min MSR 1, + C[k,
ke (b...))
8: = d
9: Q (#1, Fd)
10: for = s down to 3 do
argmin argmin kE
MSE 1, C[
12: Q = Qu{
13: return Q
A Basic Algorithm
We describe simple algorithm that finds the optimal quantization values using the dynamic program, with pseudo-code given by Algorithm 3 After initialization (lines 4 the algorithm iteratively computes MSE(i, given iS (Ines and traces back the optimal quantization
values given the solution (lines 12
B The SMAWK Algorithm
[37
Here, we provide some intuition into how SMAWK operates and achieves its efficiency. The SMAWK algorithm has four main steps:
Remove columns that cannot possibly contain maximum. This is done by comparing each column with its neighbors and discarding those that cannot be maxima based the totally monotone property. At the end of this phase, the number of columns can be no larger than the number of rows.
Pruning Phase:
Recursive Reduction: The algorithm reduces the problem size by considering subset of the rows and columns. selects every other row and recursively solves the reduced problem.
Candidate Set: After solving the smaller problem, the solution provides candidate columns for the original problem. The algorithm only needs to consider these columns to find the maxima for the skipped rows.
Merge Phase: Combine the results from the reduced problem with the candidate set to find the maximum for each original row.
Regarding efficiency, the SMAWK algorithm achieves a time complexity of (d) for d d matrix. This efficiency is due to recursive reduction of problem size and the properties of totally monotone matrices that limit the number of comparisons needed. Namely, the pruning step takes O(#cols). where #cols is the number of columns still being considered. The crux is that the recursive step happens after the pruning, which means that the recursive invocation happens with number of columns that is, at most, double the number of rows (as the number of rows is halved). This means that the overall complexity of each recursive step is proportional to the number of rows, yielding the recursion: T(n) = T(n/2) 2) + O(n) = O(n). A simple example Python implementation
(by David Eppstein) appears here 38 Our implementation is in optimized C++ [30]
C Proof of Lemma 5.1
Lemma 5.1. C satisfies the quadrangle inequality.
14

---

Proof. The lemma claims that, for any a scsc d:
Ca c| + C dl s Ca
Recall that for any S c (1......dd d), we denote
ba. argmin Cla, bj + Cbb... be(a....ct
We prove the lemma by case analysis:
Case b5,c I ba . In this case, have that:
(² (b, = b2,) + C(b c) + C(b, (.a) + Cb d)
C(a, C(b c) C(b, aa + C(b
C(b, C(bb,c: c) + C(a, (2 + C(b d)
(b, ((a
c)
Here, the Inequality (i) follows from the definition of bg that minimizes the MSE over the interval [e] and by that minimizes it over [Tb zal. Inequality (it) follows from the quadrangle inequality of C' (Lemma 4.2h, as b I bb s b and thus
C(a, 1b,c) + C(b, (,,a) S C(b, (,,) + C(a, (a,))
Case 6, > b2 In this case, we have that:
(a (b, = C(a, 12,c) + C(b c) + C(b, (ga)) + C(b d) C(a, baa) + C(ba c) + C(b, (5,)) + C(b,, d)
((,bb,cc C(b..: c) + C(a. ((,)) + C(ba d)
= Cb (a,
Here, the Inequality (i) follows again from bú,c and 1% being optimal for [ xt] and
[Te val. Inequality (ii) follows from the quadrangle inequality of C, as ba, I 66.c S I d and, therefore,
C(bia: c) + C(by,c d) S C(b d) + C(bb,: c).
Together, this concludes the proof.
D No apparent closed-form solution for 3
We explain why our acceleration method from Section 4 fails for 8 > 3. Consider computing the location of two additional quantization values b between v, and
Similarly the above analysis, we define by Q(b, u) the resulting sum of variances for all entries in [Ea F.). Then:
Q(b.u)= Σ (b- (x xo)
Σ
(u - (u-x)(x (x - b)
Σ
(ac 2) u).
xE(x..0]
2E(b.u)
xE(u.ec
Computing the partial derivatives, then get:
aQ(b,u) u)
Σ (x- (x-xa)
Σ
(u - x))
xE|x,.b]
zE(b,u]
aQ(b, u)
(x b)
(Tee I)).
du xE(h,u)
xE(U
The challenge now is that both derivatives are non-continuous, and there are multiple indices i, such that Q(x,, RTy) < 0 but Q(a++1, mry) Q( x)+1) 2 0. Accordingly, it seems unlikely that closed-form solution that is computable in constant time follows from this approach.
15

---

Algorithm 4 Apx. QUIVER
Input: X Rd 9,m E.N
2: S = { = + l. I1-11
IeE (O..... m
3: (reprocess(X,1)
> Enables computing C. [] in constant time (Appendix
4: for = to m do
5:
[1,7] 6: io 3 do
7:
Kli, SMAWK(Z)
Where Zlk, j & MSE + Cm(kkj] Wk ji = MSE 1, [ū,j]]] + C (K jl for all j E m.
8:
9: Q- {s0: 8m)
10:
m
for = down to 3 do
12:
K
13: Q Q 88)
14: return
E
Preprosessing for Apx. QUIVER
Recall that, for {ar + 8- Za l {0, ( m}} and 8p
31 E. 24-21 m
our goal is to
compute the following arrays in (dd) time:
82
vl (1,.......
[50
JE [
xE sc
Denoting 8 = ma
the first step is to make a over the input and for each x E X calculate
lg and set
A Σ B
x
T
Σ
Wl E (1....,m)
=l4==
al,==
z|t.=t
Next, make an O(m) time pass compute the cumulative sums:
Or = Σ A 1=1
B
vl E (l....,m
i=1
We note that optimization that proved useful for improving the runtime in practice is remove empty intervals after the first step. That is, we retain only intervals for which A > 0, thus reducing the number of intervals from to m' < m, which can be markedly smaller in practice.
F Apx. QUIVER Pseudo-code
We describe the pscudo-code of Apx. QUIVER, which is given by Algorithm 4 We start by preprocessing the input to obtain the a, 3,7 arrays Line 3). Next, we initialize the first row of the matrix, which only has columns, using Cm (Line 4 Follows SMAWK algorithm, each yielding the next row in MSE and its minimizers K[i, -| (Line 6). Finally, compute the resulting quantization value set from K and S (Line I1
2 invocations of the
G QUIVER Acceleration Evaluation
Here, we evaluate by how much Accelerated QUIVER is faster than QUIVER. The results, depicted Figure 4 show that Accelerated QUIVER up to 5.4x faster for = 3 and consistently faster throughout. Interestingly. the speedup is more significant in odd values of This is because the number of SMAWK invocations is [s/2] in Accelerated QUIVER (e.g., does not invoke SMAWK all for
3, only once for 5, etc.), compared to 2 invocations in QUIVER.
16

---

H Additional evaluation results
Additional evaluation results of exact solutions. We provide results for additional input vectors distributions: Normal (Figure(), Exponential (Figurefó). Truncated Normal (Figure 7) and Weibull (Figure [8) As shown, all follow the same trends in terms of vNMSE, while the runtime largely independent of the input distribution.
I ASQ Approximation Baselines
In the ZipML paper [26]. the authors propose two heuristic methods for improving the runtime. The first heuristic includes calculating the optimal solution subset of X called candidate points (CP); they further present an analysis that bounds the error with respect the maximal difference between consecutive CPs and the maximal number of entries in X between consecutive CPs; however, as they do not provide way to select the CPs. we consider two natural choices: using Uniform CPs, i.e., (21 + 8
E (O...., m3] This variant is termed 'ZipML-CP Unif." in our evaluation. The second choice of CP is Quantiles, which variant is termed ZipMLL-CP Quant.' in our evaluation.
the set {#(1+c(d-1)mm)
m)]...,]]. This
The second heuristic has bicretira MSE guarantee: using 2s quantization values, it ensures that the MSE is at most twice that of the optimal solution with s quantization values. This variant termed 'ZipML 2-Apx" in our evaluation.
We note that this different our histogram approach two aspects: (i) we stochastically quantize into the set S and (ii) we use weights to consider the number entries in each histogram bin.
104
LogNormal(0.1)
Time [ms]
103
104
Normal(0,) 1)
Time [ms]
103
10a
20
2
22
23
2
4
6
8
10
12
14
16
Input Dimension (d)
# #Quantization Values (s)
QUIVER
F
Acc. QUIVER
Figure The speedup attainable by Accelerated QUIVER, as function of (for fixed 223) and d (for fixed = 8), on the Normal and LogNormal distributions.
17

---

Time (ms)
10a
VNISSE
VNMSE
10a
10
10
10-1
10-3
10-3
21
2
21
2
224
2
2
24
2
2
2'
24
2
2
Time [ms]
10a
Time (ms)
Time [ms]
10c
10a
10a
10a
10-1
2
2
2
2
2
2
2
2
2
2
2
21
2
2
Dimension (d)
# #Quantization values (5)
#Quantization values (s)
(a) 8
(upper), 16 (lower).
(b)
2
(c)
2
ZipML
Acc. QUIVER
Figure 5: Comparing exact solutions with Normal(O, 1) distributed input.
Time (ms)
10a
vNMSE
10-1
VNMSE
10
10
10-3
10
10-1
22
218
2
24
2
2
21
2
Time [ms]
103
Time [ms)]
10
Time [ms]
10
10a
10a
10a
10a
10-1
2
2
2
2.
2
2
2
Dimension
#Quantization values
#Quantization values
(a)
(upper), 16 (lower).
(b) d 2
(c)
2
ZipML
Acc. QUIVER
Figure 6: Comparing exact solutions with Exponential(1) distributed input.
We also compare against ALQ 223] which fits the parameters of a truncated normal distribution to approximate the distribution of the input vector after normalizing it by its norm. It then uses an iterative solution approximate the optimal quantization values of the fitted distribution up the desired precision. As suggested by the authors, we use ten iterations, which were shown to converge to the optimal quantization values for the resulting (truncated normal) distribution.
Additional evaluation results approximate solutions. Similarly, we show the approximation algorithms evaluation results for the various distributions and values: Normal (Figure Exponen- tial (Figure [0). Truncated Normal (Figure TT}, and Weibull (Figure 12p. Again, the runtime of algorithms is weakly affected by the input distribution. Apx. QUIVER always the most accurate for increasing values and has a ncar-optimal vNMSE when using a sufficient value for m (e.g.. 2 400) while being markedly faster than all alternatives.
Time [ms]
10a
WNMSE
10-1
VNMSE
10
10a
10-3
10-1
10-1
212
2
218
2
224
22
23
24
2
2
22
2
24
2
2
Time [ms]
10a
Time [ms]
103
Time [ms]
10
10a
10a
101
10-1
2
255
218
2
22
2
2
2
2
2
2
24
2
2
Dimension (d)
# #Quantization values (s)
#Quantization values (s)
(a) s (upper), 16 (lower).
(b) 212
(c) 2G
ZipML
Acc. QUIVER
Figure 7: Exact solutions with TruncNorm(p: = 0, = 1, 1,b = 1) distributed input.
18

---

Time (ms)
10a
VNISEE
10
VNMSE
10
10a
10-3
10-3
10-1
2
2
218
2
224
2
2
24
2
2
2'
24
2
2
Time (ms)
10a
Time [ms]
10a
Time [ms]
10c
10a
10a
10
10-1
2
2
2
2
22
2
2
2
2
2
2
24
2
2
Dimension (d)
# #Quantization values (5)
#Quantization values (s)
(a) 8
(upper), 16 (lower).
(b)
2
(c)
2
ZipML
Acc. QUIVER
Figure 8: Comparing exact solutions with Weibull(1, 1) distributed input.
10a
10-1
VAMSE
10-1
vNMSE
10
VNMSSE
10-1
3x:10
10-2
2x10-
10-3
212
25
216
221
224
2
200
400
600
800
1000
Time [ms)]
10a
Time [ms]
Time [ms]
10a
10a
10-1
212
2
2
2
2
200
400
600
800
1000
Dimension (d)
#Quantization values (s)
(a)
16 and 400 bins.
(b) d 22 and 1000 bins.
(c) d
222 and 32.
ZipML-CP Unif.
ZipML-CP Quant.
ZipML 2-Apx
ALQ
Apx. QUIVER
Optimal
Figure 9: Comparing approximate solutions with Normal(0, 1) distributed input.
Additional Overheads
We measure the sort and quantize operations using the same EC2 server that is also equipped with an NVIDIA T4 GPU, PyTorch v2.1.2, and CUDA tool kit v12.3. As shown in Figure 13] both operations fast even for large vectors, despite the usage of a somewhat weak GPU. This specific measurement was done over the LogNormal(O,) I) distribution, but the sorting and quantization times are largely independent of the specific distribution and were similar to other tested distributions as well.
K Generalizing Our Algorithms to Weighted Inputs
We generalize our algorithms for processing sorted weighted inputs X, W e RR (where each entry has value y/ and weight wy and 21 & 222 ..... ..)
Most of the algorithmic parts only require a revised method for computing C' in constant time, which is achieved through the modified pre-processing procedure below.
For simplicity, we only discuss the basic QUIVER variant and leave the acceleration as future work.
To allow constant time computation of weighted C, denoted C.y, for weighted inputs we need another auxiliary array. Namely, we define the following:
Pre-processing.
Similarly the unweighted case, the sorted vector requirement is only needed for the exact solutions.
19

---

VNMSE
10-1
VAIMSE
10a
101
VNMSE
10
10 1
10-2
10
10-3
22
215
28
2
2
2
2'
2
2
2
400
800
Time [ms]
10a
Time (ms)
Time [ms]]
10
10
10a
10-1
24
215
21
2
224
2
2
24
200
400
600
800
1000
Dimension (d)
#Quantization values (6)
m
(a)
16 and m bins.
d n and m 1000 bins.
(c) d 2
$
ZIPML-CP Unif.
ZipML-CP Quant.
ZipML 2-Apx Optimal
ALQ
Apx. QUIVER
Figure 10: Comparing approximate solutions with Exponential(1) distributed input.
10"
10"4
vNMSEE
VNMSE
VNMSE
10
10
10-2
10
2
255
2
2
22
2
2
24
2
2
200
400
600
800
1000
Time [ms]
Time [ms]
Time [ms]
101
10
10a
10-1
215
2
2
200
400
600
800
1000
Dimension (d)
#Quantization values (s)
(a) 16 and m 400 bins
(b) d 2 and m 1000 bins.
(c) d 22 and à = 32.
ZipML-CP Unif.
ZipML-CP Quant.
ZipML 2-Apx
ALQ
Apx. QUIVER
I Optimal
Figure 11: Approx. solutions with TruncNorm(4 0, = 1,a 1, = 1) distributed input.
0j Σ
w
jE [l....,dd
(2,w)EX,
B3 Σ w x
jE (1, {I.....d].
(z,w)ex,
7j
Σ
xt
jE (1.......
(0,w)EX;
Then, we can then write:
Culkij]= =
E
w w.(x - I2) - -kk)
# #
Σ
w (xg xx) - FK)
x, [(
Σ
(xz Fk)
Tt.
Σ
Wi x
By Fk (a,, 0g) + (x, xx) (3, - 3a) (Ng - (x)
Observe that Cip clearly satisfies the quadrangle inequality, and thus, the correctness follows. The approximation variant also follows similarly.
20

---

vNMSE
VNMSE
WNMSE
10-1
10"1
10-2
10-2
10-3
2
215
28
2
22
22
2
24
23
2
200
400
600
800
1000
Time (ms]
Time [ms]
Time [ms]
10
102
10
2
2
2
24
200
400
600
800
1000
Dimension (d)
#Quantization values (s)
(a)
16 and m 400 bins
(b) d
2 and m 1000 bins.
(c) d 2 and à 32.
ZiPML-CP Unif.
ZipML-CP Quant.
ZipML 2-Apx Optimal
ALQ
Apx. QUIVER
Figure 12: Comparing approximate solutions with Weibull(1, 1) distributed input.
102
Sort
Quantize
Time [ms]
101
I
100
211
23
25
17
29
2
23
Dimension (d)
Figure 13: Sort and quantization times (s = 16) vs. d on a T4 GPU.
21

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide theoretical guarantees and supporting evaluation results. All our results are reproducible, and we plan to open-source our code upon publication.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We elaborate on the limitations in the Discussion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Each claim is formulated to include all assumptions and is accompanied by complete proof.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All our results are reproducible and we provide the entire set parameters, datasets, and algorithm details. We further plan to open-source our code upon publication.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
23

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We do not use any proprietary data and the synthetic data can reproduced by anyone. The code will be released as open source anyone can easily reproduce our results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/
sooololiccii for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, all the details are documented in detail.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We repeat the experiments with different seeds and report bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes)
Justification:
We measure execution time and document the used hardware.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Yes, it follows it fully.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We only used implementation of the SMAWK algorithm by Daniel Stein- berg, which is released under the MIT license.
We acknowledge this in the code where appropriate.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
26

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We plan to release the code upon publication with the appropriate license.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moddl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "cBMihCXJnG", "reviewer": "Reviewer_HN3u", "summary": "The paper proposes the QUIVER algorithm, Accelerate QUIVER (an accelerated variant when s = 3), and Apx QUIVER (a variant that utilizes approximations for better speed) to solve the Adaptive Stochastic Quantization (ASQ) problem. The paper also provides theoretical guarantees to their algorithm, improving the current SOTA time complexity from $O(s d^2)$ to $O(s d)$ and space complexity from $O(d^2)$ to $O(s d)$. Practical experiments are also run to show the improvement of the current SOTA.", "questions": "1. Are there alternatives to SMAWK that can be implemented (with some small modifications) that still allow QUIVER to work?\n2. The author states that Apx. QUIVER does better in practice than the bound in Lemma 6.1, just out of curiosity, what do you think is the reason?\n3. Are there any other results in the literature that you can compare with Apx. QUIVER results (such as line 223 - 224)?\n4.  The asymptotic difference among the approximate algorithms are not clear to me in Figure 3, can the author elaborate further?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Technically solid: The technical aspects of the paper such as formulations and proofs are clear and correct.\n2. Clear motivations: The benefits of adaptivity and unbiasedness are explained clearly with practical illustrations of the MSE reduction of different methods.\n3. Theoretically and practically outperform SOTA: The paper makes it clear in the contributions and experiments sections how the proposed algorithms outperform past methods practically and with better theoretical complexities. \n4. Weaknesses acknowledgements: The authors clearly state and discuss the drawbacks of their algorithms.", "weaknesses": "1. SMAWK algorithm seems to be an important subroutine in QUIVER, I think it should be elaborated a bit more for those who are not aware of SMAWK and how the process takes O(d) time and space (calls of SMAWK are referred plentifully in the paper). \n2. Following up on that, I also wonder if the authors can elaborate for me on the key novelty of QUIVER since the key update step in this algorithm comes from SMAWK (is it the preprocess?). I do see more clearly the novelty of Accelerated QUIVER with the important observation when s = 3 (also related to question number 1 below). \n3. While Accelerated QUIVER offers some interesting ideas, it does not work for s > 3. I believe the section can be stronger if the authors can maybe elaborate some (common) situations or (useful) applications for s = 3 to contextualize the “practicality” of this algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review. We first address the questions in detail and *relate to the weaknesses in the comment that follows*.\n\n\n\n**Q1** While SMAWK has the optimal $O(d)$ time complexity for the problem, there are simpler approaches. For example, by leveraging the fact that if MSE[i,j] is minimized at k, then for all j’>j, MSE[i,j] must be maximized for some k’>k. This allows a `binary search approach’ that solves the problem with a slower $O(d \\log d)$ time complexity. (This approach is standard and well-known.) \nWe implemented this approach and empirically verified that the resulting solution is slower than using SMAWK.\n\n**Q2** The analysis is (asymptotically) tight only for the worst-case but is far from tight for non-adversarial inputs. Namely, we prove the theoretical claim by constructing a specific solution with $2s-2$ quantization values that is derived from the optimal solution with $s$ quantization values. This solution is generally far from the optimal solution when using $2s-2$ quantization values, even when restricted to grid entries.    \n\nThe intuition is as follows: we placed ($2s-4$) of the quantization values in consecutive pairs on the grid (e.g., $\\ell=17$ and $\\ell=18$). In practice, Approx. QUIVER finds the optimal solution with quantization values that are on the grid, and such a solution is unlikely to contain many pairs of consecutive quantization values (for realistic input vectors). A secondary reason is that the worst-case analysis considers that all coordinates might be in the middle of two grid points, which is unlikely in non-adversarial inputs.\n\n**Q3** Are you referring to [16]? As we discuss in lines 26-29, this is an example of a line of work that optimizes the quantization error for the worst-case inputs by applying a transformation on the input vector. Also, as we explain in lines 67-71, such works are orthogonal to ASQ since one can apply it after the transformation, whereas [1, 3, 4, 15, 16, 17] use pre-computed quantization values instead of the ones that are optimal for the transformed vector. That is, by applying adaptive quantization to select the quantization values after the transformation, we can get a solution with improved accuracy at the cost of additional computation.\n\nWe further note that comparing worst-case solutions to adaptive ones (without applying the transformations) is not an apples-to-apples comparison. Namely, if the input has structure, ASQ can provide a significantly more accurate solution. On the other hand, if the input is distributed adversarially, no benefit can be attained by adaptive algorithms.\n\nTo see the benefit of adaptive solutions over worst-case solutions, consider a trivial example where the input vector has $d/2$ (+1) entries and $d/2$ (-1) entries. ASQ trivially solves this with zero error even for $s=2$. In contrast, all the above algorithms will apply a transformation after which the structure is gone, and any quantization will have a significant error.\n\n**Q4** Thanks for pointing out that this is not explained. We will clarify this in the paper.\nNamely, we compare with several approximate algorithms:\n\n*ZipML-CP* [24] is an algorithm that runs the exact ZipML algorithm on a subset of the points called `Candidate Points’. Since ZipML runs in $O(d^2 s)$ time, here we use M candidate points to get  $O(d + M^2 s)$ time.\n\n*ZipML 2-Apx* [24] is an algorithm that computes an approximate solution in $O(d \\log d + s^3)$ time. \n\n*ALQ* [26] is an algorithm that finds good quantization values for a truncated normal distribution. To use it, it samples several gradients (by computing the gradient of several random batches) to fit the truncated normal parameters. To be fair to ALQ, since we evaluate a single-shot quantization scenario, we calculate the input vector's exact mean, variance, and support parameters. Yet, its algorithm for finding the quantization values for the distribution, which uses an alternating coordinate descent method, underperforms for two main reasons: (1) the distribution, generally, is not truncated-normal. (2) In each iteration of the coordinate, they optimize the location of each quantization value i by fixing the locations of the (i-1)’th and (i+1)’th values and calculating the optimal location by integrating over the distribution truncated to this range. \n\nThis then runs for several (we used 10, as in their released code) iterations, so in total, they compute $\\approx 10s$ integrals. While theoretically requiring $O(d)$ time, in a model where such integral calculation takes constant time, this is markedly slower than other approaches. We note that it is possible that with low-precision integral calculations, one may improve the runtime, but the error (which is already not competitive) will degrade further.\n\n**We will relate to the weaknesses in the following comment.**", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Wcgaqy54pR", "reviewer": "Reviewer_QWUX", "summary": "This paper studies the Adaptive Stochastic Quantization (ASQ) problem and presents a dynamic programming based algorithm that improves time and space complexities.", "questions": "you begin your paper by the assumption of  1-bit quantization  i.e.  $x \\in \\{a,b\\} $(another typo in the paper). However the results are implemented for   more number of bits such as s=16. Is there any reason  you made 1-bit assumption on ln 94?", "limitations": "The proposed Algorithm is not implemented for ML model and  gradient compression.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The algorithm is compared with peer dynamic programming based algorithm called ZIPML. Quiver Algorithm introduced in this paper is showing great  potential to be used for  compression of ML models. The algorithm has the advantage of controllable tradeoff between\naccuracy and speed.", "weaknesses": "The presentation of the paper needs  further improvement. please proofread the paper for  grammatical errors and  typos, some of  which I point out  to here:\n\nln. 29, $X’$\n\non ln37,   $\\hat{X}$ concatenation of  $\\hat{x}$’s ?  define all  parameters before using them.\n\nsame for $\\theta(s)$ on ln 107. \n\n-ln. 106   is Q in X ?\n\n- Many abbreviations are undefined: ALQ,QSGD,RTN .\n- ln. 56-57, It is  ambiguous  to which algorithms you are comparing  the  time and space  complexity of your algorithm.\n- what does  “on a commodity PC” mean? provide specifications  of your processor.\n- ln. 80 \"orders of magnitude lower error\" , compared to which algorithm?\n- The definition of MSE[i,j] in 109 is not clear. please write it mathematically.\n\n- The main problem  of the paper which is defined in on ln.116 is not very clear. No description or references are provided. The authors are leaving many foundational definitions of dynamic programing and its application to quantization up to the reader. The paper better be inclusive of essential  concepts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. \n\nThanks for pointing out the typos, we will fix these.\n\n> In 106 is Q in X ?\n\nWe write that there exists an optimal solution for which $Q\\subseteq X$ (and credit [24] for this observation). That is, there exists an optimal solution where all quantization values are entries in the input vector $X$.\n\n> Many abbreviations are undefined: ALQ,QSGD,RTN .\n\nALQ and QSGD are the names of the algorithms. They were coined by the respective authors of [26] and [13]. The full name of the acronym RTN is given in line 78.\n\n> ln. 56-57, It is ambiguous to which algorithms you are comparing the time and space complexity of your algorithm.\n\nThis is compared to the state of the art. As explained later (line 121), this is compared to ZipML [24]. We will make that clearer in the introduction.\n\n> what does “on a commodity PC” mean? provide specifications of your processor.\n\nPlease see lines 231-233.\n\n> ln. 80 \"orders of magnitude lower error\" , compared to which algorithm?\n\nCompared to the non-adaptive algorithms, as we point out the benefits of adaptivity.\n\n> The definition of MSE[i,j] in 109 is not clear. please write it mathematically.\n\nRecall that $a_x = \\max \\set{q\\in Q\\mid q\\le x}$, $b_x = \\min \\set{q\\in Q\\mid q\\ge x}$, and that $X_j$ is the vector with the first $j$ entries of $X$. \n\nThe mathematical formulation is:\n$$\nMSE[i,j] = \\min_{Q: |Q|\\le j, x_j\\in Q} \\sum_{x\\in X_j} (b_x-x)(x-a_x).\n$$\n\nWe will add this to the paper.\n\n> The main problem of the paper which is defined in on ln.116 is not very clear. No description or references are provided. The authors are leaving many foundational definitions of dynamic programing and its application to quantization up to the reader. The paper better be inclusive of essential concepts.\n\nWe kindly disagree. Dynamic programming is a basic tool in computer science and the specific problem is explained (lines 117-120 give the semantic meaning of the parameter $k$ and MSE[i,j] was defined above).\n\n\n> **Q1:** you begin your paper by the assumption of 1-bit quantization i.e. $x\\in a,b$\n(another typo in the paper). However the results are implemented for more number of bits such as s=16. Is there any reason you made 1-bit assumption on ln 94? \n\nWe do not assume that $x\\in\\{a,b\\}$. \n\nIn stochastic quantization, for some $a,b\\in\\mathbb R$, the input value $x\\in[a,b]$ is quantized to $\\widehat x\\in \\{a,b\\}$. That is, the input is a real value between $a$ and $b$, and the quantized value is one of $a,b$.\nWhen quantizing a vector $X$ using $s>2$ quantization levels, each entry $x\\in X$ is stochastically quantized between the two encompassing values $a_x,b_x$ as explained in lines 101-102.\n\n> **L1:** The proposed Algorithm is not implemented for ML model and gradient compression.\n\nSince QUIVER solves the same problem as previous solutions such as ZipML, there is no gain in recreating experiments that would yield the exact same results. As you can observe from vNMSE subfigures of Figure 2, both QUIVER and ZipML have identical error, as they provide the optimal solution for the ASQ problem. The benefit of QUIVER is in its faster runtime and lower space requirements, as we evaluate in the remaining figures.\n\nMoreover, our paper's focus is not on model or gradient compression but on improving the state of the art for the well-established ASQ problem, which is of high interest to the ML community and NeurIPS in particular, as the line of related works we cite indicates (e.g., [24] and [26], that we compare with, were published in ICML and NeurIPS).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FooydTYBbQ", "reviewer": "Reviewer_KyKu", "summary": "The paper presents an algorithm to solve the Adaptive Stochastic Quantization (ASQ) problem that is claimed to be more computationally efficient than existing solutions. The paper also presents simulations showing the improved efficiency.\n\nI have read the authors' responses to my comments and made changed the overall score.", "questions": "Please state the problem much earlier.", "limitations": "The paper addresses the limitations appropriately.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written. \nThere is sufficient background material on previous works on the topic. \nThe simulation study is clear, appears comprehensive, and there is informative discussion.", "weaknesses": "The motivation for ASQ is unclear to me. In a discussion about quantization in the form of lossy compression in the context of NeurIPS, I’d expect to learn at minimum: (1) what is the source of redundancy that makes quantization possible without affecting too much the performance. (2) How the method exploits this redundancy. The statements in lines 67-71 appear to say that the authors do not care about these aspects.\nSpecifically to ASQ:\nIn the background, the authors nicely explain the benefit of adaptivity and unbiasedness, but do not explain the benefit of stochasticity. For example, what is the benefit of introducing randomness of the proposed type compared to the classical Lloyd algorithm (Lloyd 1982 https://ieeexplore.ieee.org/document/1056489)?\n\nI understand that ASQ has been studied before, which might be interesting, and thus the contribution of the paper might be significant. However, in my opinion, it is not a good fit for NeurIPS since the contribution is only associated with computations/implementation of a known quantization method. \n\nAnother weakness is that the ASQ problem is formally stated only in lines 103-104. The problem appears simple enough to be presented in the first few lines of the paper.  \n\nOther comments:\nLine 106: the inclusion of Q in X seems a typo.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n> What is the source of redundancy that makes quantization possible without affecting too much the performance?\n\nThe source of redundancy depends on the ASQ use case. Here are two specific examples, while other use cases may have a different motivation. \n\n*Example 1: Gradient compression (GC).* (Lines 81-87 in our submission)\n\nGC is a common building block for distributed and federated learning where multiple workers (clients) participate in the learning process. At each round, workers compute their gradients and then aggregate them in order to update the model. Since the process has inherent variance (each such stochastic gradient is computed with respect to a random subset of the data), one can leverage compression to alleviate communication bottlenecks without a significant impact on the accuracy of the aggregated (global) gradient if the variance of the compression is small compared with this inherent variance. \nMoreover, as recent works show, it is important for the compression to be unbiased. Intuitively, when the compression is unbiased (and independent among workers) some workers round up and some round down, allowing the error of the average to decrease proportionally to the number of workers (in expectation).\n\n*Example 2: Model compression (MC).* (Lines 88-92 in our submission)\nIn MC, one quantizes the weights of a model in order to decrease its space requirements and improve the inference time. In this use case as well, it has been demonstrated that applying biased methods like Round-To-Nearest to compress parameters of large language models can lead to worse results compared to stochastic quantization. This is due to the reliance on the parameters of LLM layers for calculating inner products with their inputs. Ensuring these inner products remain unbiased results in less error in the outputs of the layers and less bias accumulation among layers, thereby enhancing overall accuracy.\n\nFor both examples, we cite works that substantiate these claims.\n\n> How the method exploits this redundancy. The statements in lines 67-71 appear to say that the authors do not care about these aspects. Specifically to ASQ: In the background, the authors nicely explain the benefit of adaptivity and unbiasedness, but do not explain the benefit of stochasticity. For example, what is the benefit of introducing randomness of the proposed type compared to the classical Lloyd algorithm (Lloyd 1982 https://ieeexplore.ieee.org/document/1056489)?\n\nLloyd’s algorithm is a great solution for **when the quantization is allowed to be biased**. In fact, *it is impossible to be unbiased without stochasticity* when quantizing since multiple inputs can be quantized to the same value. \n\nMoreover, while Lloyd’s algorithm may not yield the optimal solution, we compare with the **optimal** biased algorithm (for 1D, there is an algorithm that finds the optimal solution, see https://arxiv.org/abs/1701.07204).\n\nThat is, the optimal biased algorithm shown in Figure 1 is at least as accurate as Lloyd’s. When estimating a single vector, it is indeed more accurate than unbiased methods, but as we explain, it is unsuitable for cases when unbiasedness is desired, e.g., when averaging the sum of multiple independently compressed vectors as in federated learning settings.\n\n> I understand that ASQ has been studied before, which might be interesting, and thus the contribution of the paper might be significant. However, in my opinion, it is not a good fit for NeurIPS since the contribution is only associated with computations/implementation of a known quantization method.\n\nWe politely disagree. The known quantization method is considered impractical for many use cases (see lines 43-48), and this work enables the use of ASQ for multiple ML applications, as shown in these previous works.\n\nMoreover, the ASQ problem is well-established and of high interest to the ML community and NeurIPS in particular, as the line of related works we cite indicates (e.g., [24] and [26], which we compare with, were published in ICML and NeurIPS).\n\n> Another weakness is that the ASQ problem is formally stated only in lines 103-104. The problem appears simple enough to be presented in the first few lines of the paper.\n\nThank you for the suggestion. We will expand in lines 19-21 to explain that the goal is to find such a set of quantization values $Q$.\n\n> Other comments: Line 106: the inclusion of $Q$ in $X$ seems a typo.\n\nThis is not a typo. The meaning of $Q\\subseteq X$ is that there exists an optimal solution in which all quantization values are a subset of the input entries. This is a known observation that was mentioned, e.g., in [24]  (as we mention in Line 106).\nWe will explain this further in the text.\n\n> Please state the problem much earlier.\n\nWill do!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8Ze5xB0aOL", "reviewer": "Reviewer_SB91", "summary": "The paper is concerned with quantization,\nthat is encoding the components of a vector $X\\in \\mathbb{R}^{d}$ in a finite\nalphabet $Q$ of given size $s$. The goal is unbiased,\nstochastic quantization, where for a given component $x$ the encoding value $%\n\\hat{x}$ are chosen at random such that $E\\left[ \\hat{x}\\right] =E\\left[ x%\n\\right] $. Given $Q$ this fixes the encoding procedure, so that the\nprincipal problem is the choice of the alphabet $Q$, which should minimize\nthe mean squared error (MSE) $E\\left[ \\left\\Vert X-\\hat{X}\\right\\Vert \\right]\n$, for fixed size $s$. It is important to realize that the optimal alphabet\nis a subset of the set of components of $X$, so $s\\leq d$. An optimal\nsolution has been found by Zhang et al [24] and the same paper already\noffers an improved algorithm called ZipML of $O\\left( sd^{2}\\right) $\nruntime and $O\\left( d^{2}\\right) $ memory requirement.\n\nThe paper at hand builds on the analysis of the latter paper, and gives an\nimproved algorithm  of $O\\left( sd\\right) $ both runtime and memory\ncomplexity. Using a closed form solution for $s=3$ runtime and memory\nrequirements are halved in another improvement of the algorithm. Just as the\nprevious algorithm this version also returns the optimal solution.\n\nTo further accelerate the method the authors discretize the quantization\nvalues on a grid of fixed size $m+1>s$ and seek a subset of this grid to\nminimize the MSE for resulting set. The algorithm they present then has\nspace and time complexity of $O\\left( d+ms\\right) $. Because of this\nimprovement on can afford a larger cardinality of the set of quantization\nvalues. The excess error of this approximate algorithm for $2s-2$\nquantization values over the previous algorithm with $s$ quantization values\nis bounded.\n\nThe paper then gives results of numerical experiments with various\ndistributions.", "questions": "I am a bit bewildered about calling $X$ a vector, since the ordering is appearantly irrelevant. Also multiple values do not change anything. \"Set of real numbers\" seems more appropriate to me.", "limitations": "In a subsection \"limitations\" the authors admit that their algorithm is not GPU-friendly. They also remind the reader that the algorithm requires initial sorting of the data.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper considers a problem of obvious practical relevance.\n\nThe background and the various solutions are presented in a clear way,\neasily understandable even to me, who has never very much considered the\nquantization problem in this form.\n\nI checked most of the analysis which appeared correct.", "weaknesses": "I cannot identify any major weaknesses. I must admit, however,\nthat, not being an expert in this field, I cannot judge if any other relevant\nliterature on unbiased, minimum-variance quantization beyond [24] is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.\n\n> I am a bit bewildered about calling $X$ a vector, since the ordering is appearantly irrelevant. Also multiple values do not change anything. \"Set of real numbers\" seems more appropriate to me.\n\nWe agree that the input can be considered as a multiset (and not a set - a counter-example is given below) of entries we wish to quantize. Our solution, however, is based on a dynamic program that looks at prefixes of the vector one gets by looking at the sorted version of this multiset.\n\nWhy $X$ cannot be modeled as a (simple) set:\n\nFor example, if the entry `5’ appears twice, it carries double the weight when considering the sum of variances. \n\nMore concretely, consider the input $X=(0, 3, 5, 5, 7)$ and $s=3$. The optimal solution in this case is $Q=\\set{0,5,7}$. In contrast, for the input $X=(0, 3, 5, 7)$, the optimal solution is $Q=\\set{0, 3, 7}$, giving a sum of variances of $4$, compared to a sum of variances of 6 if using $Q=\\set{0, 5, 7}$ instead.\n\n\n> I cannot identify any major weaknesses. I must admit, however, that, not being an expert in this field, I cannot judge if any other relevant literature on unbiased, minimum-variance quantization beyond [24] is missing.\n\nPlease note that we also compare our approach with ALQ [26]. We also cite other works (e.g., [25]) that look at special cases (a specific distribution) of the ASQ problem, but are not addressing the general formulation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The authors have studied quantization as a map from a multi-dimensional real space to a finite alphabet of a given size. The authors focus on unbiased quantization and the mean squared error loss and improved the solution by Zhang et al [24] in terms of runtime and memory complexity.

The paper was thoroughly discussed and the reviews are mixed. The reviewers are positive about this work in general, and they have found concerns such as a thorough literature review beyond [24]  and the key novelty of QUIVER considering SMAWK. I think the presentation of the paper should be improved significantly, but these can be improved for the revised manuscript. I would recommend that for the revised version, the authors take into account the comments raised by reviewers and improve the paper as they have promised in the rebuttals.
Decision: Accept (poster)