Optimal and Approximate Adaptive Stochastic Quantization

Authors: ben  ran
  basat
yaniv  ben-itzhak
michael  mitzenmacher
shay  vargaftik
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-07 12:47:06

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.

Main paper: 
 introduction: 
 Quantization is central to optimizing a large range of machine learning (ML) applications. It is often used for compressing gradients to reduce network requirements in distributed and federated learning (e.g., [1, 2, 3, 4, 5, 6] ); for quantization of datasets for faster training and inference (e.g., [7] ); and for reducing the memory footprint while accelerating the computation for large models' inference via post-training quantization (e.g., [8, 9] ) and quantization-aware training (e.g., [10, 11] ) of model weights, activations and key-value (KV) caches [12] .A fundamental quantization method is stochastic quantization, where one quantizes an input vector X ∈ R d to X ∈ Q d using a set Q ⊂ R of |Q| = s quantization values so that each entry is unbiased [13] . That is, each x ∈ X is (randomly) quantized to a value x ∈ Q such that E [ x] = x.Previous unbiased quantization works considered different approaches. Some are distributionagnostic, i.e., design the quantization without optimizing it for the specific input. For example, [1, 14, 15] set quantization values with respect to global properties such as the vector's norm, or minimum and maximum values.Other works, e.g., [1, 3, 4, 16, 17, 18, 19] , optimize for the worst case X by applying a reversible transformation (e.g., the randomized Hadamard transform) before quantization that converts it into a vector X ′ with a controlled distribution (e.g., with max(X ′ ) -min(X ′ ) = Õ(∥X∥ 2 / √ d)). The decoder then applies the inverse transformation on the quantized X ′ to obtain an estimate of X.In contrast, some solutions use the fact that, in many cases, the inputs to be quantized have a significant structure that can be leveraged to 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 LogNormal-like [22] or Normal-like [23, 24] distributions. As another example, the distribution of deep activation layers appears to follow a sub-Weibull distribution [25] .To alleviate the need to assume an input distribution, the Adaptive Stochastic Quantization (ASQ) problem (e.g., [26, 27, 28] ) considers selecting Q adaptively, i.e., with respect to the specific input X, that minimizes the mean squared error (MSE, also known as the sum of variances) given byE X -X 2 2 = x∈X Var[ x] ,where X = { x | x ∈ X} is the vector of quantized values.Unfortunately, known ASQ solutions are not practical for the large-size vectors that commonly appear in ML applications. One aspect of the problem's difficulty is that it is known to be non-convex even for s = 4 (two-bit quantization) [28] , which excludes many natural solution methods such as gradient descent. ZipML [26] approaches the challenge using a dynamic programming approach that allows one to optimize Q in polynomial time. However, this solution has a 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 on the fly".As another evidence of the problem's hardness, previous work [27] solves the problem only for a given (Weibull) distribution, writing that "The empirical distribution is usually non-differentiable, 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 to have lower MSE than advanced distribution-agnostic methods such Non-Uniform QSGD (NUQSGD) [29] . ASQ methods can also improve more complex schemes (e.g., including the aforementioned that utilize worst-case to average-case transformations) by replacing distribution-agnostic 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, we introduce QUIVER, an algorithm that features novel acceleration methods and leverages the structure of the underlying problem to reduce the runtime complexity from O(s • d This improvement arises from the observation that the optimal solution, for given input parameters s, d, can be efficiently derived from the solutions for {s -1, d ′ | d ′ ∈ {2, 3, . . . , 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 1 ≤ k ≤ j ≤ d, the sum of variances of points {x k , . . . , x j } can be computed in constant time when quantized to {x k , x j }, a property that is achieved by our new preprocessing method.We then further accelerate 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 a 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 our algorithms in C++ and demonstrate their efficiency. For example, on a commodity PC, QUIVER can compute the optimal 4-bit quantization values (s = 16) for a vector with d = 1M entries in under a second and compute an accurate approximation in just six milliseconds. We evaluate our solutions compared to state-of-the-art ASQ methods on a variety of distributions considering different vector sizes and number of quantization values and demonstrate a 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 [31] ), sparsification (e.g., [32] ), sparse coding (e.g., [33] ), low-rank decomposition (e.g., PowerSGD [34] ), variable-length coding (e.g., EDEN [4] ) and more. Many of these are orthogonal to our work and can be used in conjunction with it. For example, one can use ASQ to quantize a sparsified or transformed vector or apply variable-length encoding to further reduce the size of the quantized vector. shows the empirical MSE of quantizing a single vector with i.i.d. LogNormal(0, σ 2 ) 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, as shown in Figure 1 (b), for distributed mean estimation, the bias may not cancel out when averaging quantized inputs (here, we used a standard setup where all vectors are identical, e.g., see [17] , with i.i.d. LogNormal(0, 1/2) distributed entries) and the advantage of unbiased methods accordingly increases with the number of inputs. Each data point is averaged over ten runs with the standard deviation reported.2 Background 
motivation: 
 We now briefly explain the benefits of ASQ compared to alternative methods.The benefits of adaptivity Unbiased solutions such as QSGD [14] and NUQSGD [29] rely only on global properties (e.g., the input's norm) when selecting Q. Figure 1 (a) shows the benefit of adaptivity by illustrating the potential MSE reduction from selecting Q optimally for the specific input. A similar behavior is observed for biased methods where the non-adaptive Round-To-Nearest (RTN) has a higher error than the optimal adaptive biased scalar quantizer, 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, it is beneficial for the quantization to be unbiased. For example, when there are n senders (e.g., when doing distributed mean estimation [1, 2, 4, 17, 18] ), having unbiased and independent estimates of the vectors allows the mean estimation's MSE to decay proportionally to 1 n ; 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 is demonstrated in Figure 1 (b), which shows that while biased adaptive solutions have lower error for a small number of vectors (1-2), having unbiased quantization is critical to lowering the error for a 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.Given two quantization values a, b and a number x ∈ [a, b], Stochastic Quantization (SQ) is a procedure that rounds x to x where x ∈ {a, b}. Specifically, x obtains the value a with probability p a = b-x b-a and the value b otherwise, i.e., with probability p b = 1-p a = x-a b-a . An important property of SQ is that the expected rounded value is unbiased, i.e., E [ x] = a•p a +b•p b = x. The variance of stochastically quantizing x is then given by E(x -x) 2 = (x -a) 2 • p a + (x -b) 2 • p b = (b -x)(x -a).Given a vector X ∈ R d and an integer s ≥ 2, the Adaptive Stochastic Quantization (ASQ) problem [26, 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 ∈ Q d by stochastically quantizing each entry x ∈ X with valuesa x = max {q ∈ Q | q ≤ x} and b x = min {q ∈ Q | q ≥ x}.Formally, ASQ seeks to minimize the MSE, given by E[∥X -X∥ 2 2 ] = x∈X (b x -x)(x -a x ), where E[ X] = X holds by construction.Leveraging the fact that there exists an optimal solution in which Q ⊆ X [26] (i.e., the quantization values are a subset of the input), one can naively solve the problem in d Θ(s) time by going over all choices for the quantization values. Instead, the following dynamic program (DP) allows us to solve it optimally and in polynomial time for any s [26] . Given a sorted vector X = ⟨x 1 , . . . , x d ⟩, we denote by MSE [i, j] the optimal MSE of quantizing the prefix vector X j = ⟨x 1 , . . . , x j ⟩ using i quantization values that include x j , that is:MSE [i, j] = min Q:|Q|≤i,xj ∈Q x∈Xj (b x -x)(x -a x ).Our MSE [i -1, k] + C[k, j] .Here, the index k denotes the entry in X, x k , of the rightmost quantization value to the left of x j . A naive solution for the above DP is first to compute the matrix C (which takes O(d  
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] in constant time, at the cost of only O(d) additional space. We define the following arrays, β, γ ∈ R d , that store the cumulative sums of the vector and its squared entries:β j = x∈Xj x , γ j = x∈Xj x 2 ∀j ∈ {1, . . . , d} .Denoting β 0 = γ 0 = 0, both are computable in O(d) time as β j = β j-1 + x j and γ j = γ j-1 + x 2 j . We can then express C[k, j] as follows:C[k, j] = x∈[x k ,xj ] (x j -x)(x -x k ) = x∈(x k ,xj ] (x j -x)(x -x k ) = -x j • x k • x∈(x k ,xj ] 1 + (x j + x k ) • x∈(x k ,xj ] x - x∈(x k ,xj ] x 2 = -x j • x k • (j -k) + (x j + x k ) • (β j -β k ) -(γ j -γ k ).With this optimization, we can evaluate C[k, j] in constant time, yielding a solution that uses O(s • d) memory instead of O(d 2 ). Next, we show how to improve the runtime. 
the quiver algorithm: 
 To derive a faster algorithm, we observe that C satisfies the quadrangle inequality, defined below: Proof. We first observe that for any x ∈ [x a , x b ] :EQUATIONFor any x ∈ [x c , x d ], we similarly get:EQUATIONSimilarly, for x ∈ [x b , x c ], we have that:EQUATIONTherefore, we get:C[a, c] + C[b, d] = x∈[xa,xc] (x c -x)(x -x a ) + x∈[xb,xd] (x d -x)(x -x b ) = x∈[xa,xb] (x c -x)(x-x a )+ x∈[xc,xd] (x d -x)(x-x b )+ x∈[xb,xc] (x c -x)(x-x a )+(x d -x)(x-x b ) ≤ x∈[xa,xb] (x d -x)(x-x a )+ x∈[xc,xd] (x d -x)(x-x a )+ x∈[xb,xc] (x c -x)(x-x b )+(x d -x)(x-x a ). = x∈[xa,xd] (x d -x)(x -x a ) + x∈[xb,xc] (x c -x)(x -x b ) = C[a, d] + C[b, c].Here, the inequality follows from equations (1)-(3).Next, let us implicitly define a matrix A ∈ R {1,...,d}×{1,...,d} such thatA[k, j] = MSE [i -1, k] + C[k, j]. Importantly, A is not stored in memory but admits constant time lookups as MSE [i -1, •] is 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 < b and c < d:(A[a, c] > A[b, c]) =⇒ (A[a, d] > A[b, d]). By applying the SMAWK algorithm [37] , which finds the row minimas of an implicitly defined totally monotone matrix, on A T , we obtain in O(d) time and space the indices k j = argmin k∈{1,...,d} A[k, j] for all j ∈ {1, . . . , d}. This immediately gives the next row of the dynamic program, asMSE [i, j] = MSE [i -1, k j ] + C[k j , j].The resulting solution, which we call QUIVER, is given in Algorithm 1 and requires just O(s • d) time and space to compute the optimal quantization values. 
the accelerated quiver algorithm: 
 To accelerate QUIVER, we rely on the observation that while the problem is non-convex for s > 3, it admits a closed-form solution when s = 3.Denoting by C 2 [k, j] = min b∈{k,...,j} (C[k, b] + C[b, j]) the optimal MSE of quantizing the range [x k , x j ] using three quantization values (at x k , x b , x j ), we show how to compute C 2 in constant time.Namely, consider adding a quantization value q ∈ [x k , x j ] (not necessarily in X) between two existing quantization values x k and x j . Let us define the sum of variances of all input entries in [x k , x j ] as a function of q:Q(q) = x∈[x k ,q] (q -x)(x -x k ) + x∈(q,xj ] (x j -x)(x -q). This function is differentiable in [x k , x j ]\ X, and we get:dQ(q) dq = x∈[x k ,q] (x -x k ) -x∈(q,xj ] (x j -x). Algorithm 1 QUIVER 1: Input: X ∈ R d , s ∈ N. ▷ X is sorted. 2: Preprocess(X) ▷ Enables computing C[k, j] in constant time (Section 3). 3: for j = 2 to d do 4: MSE [2, j] = C[1, j] 5: for i = 3 to s do 6: K[i, •] = SMAWK(A) ▷ Where A[k, j] ≜ MSE [i -1, k] + C[k, j] ∀k, j.7:MSE [i, j] = MSE [i -1, K[i, j]] + C[K[i, j], j] for all j ∈ {i, . . . , d}. 8: Q = {x 1 , x d } 9: j = d 10: for i = s down to 3 do 11: j = K[i, j] 12: Q = Q ∪ {x j } 13: return Q Algorithm 2 Accelerated QUIVER 1: Input: X ∈ R d , s ∈ N. ▷ X is sorted. 2: Preprocess(X) ▷ Enables computing C[k, j] and C 2 [k, j] in constant time. 3: s ′ = (s mod 2) 4: if s ′ = 0 then 5: for j = 2 to d do 6: MSE [2, j] = C[1, j] 7: else 8: for j = 3 to d do 9: MSE [3, j] = C 2 [1, j] 10: for i = 2 to ⌊s/2⌋ do 11: K[i, •] = SMAWK(B) ▷ Where B[k, j] ≜ MSE [2 • (i -1) + s ′ , k] + C 2 [k, j] ∀k, j.12:MSE [2 • i + s ′ , j] = MSE [2 • (i -1) + s ′ , K[i, j]] + C 2 [K[i, j], j] ∀j ∈ {i, . . . , d}. 13: Q = {x 1 , x d } 14: j = d 15: for i = ⌊s/2⌋ down to 2 do 16: b * = argmin b∈{K[i,j],...,j} (C[K[i, j], b] + C[b, j])▷ Takes O(1) time. 17:j = K[i, j] 18: Q = Q ∪ {x j , x b * } 19: if s ′ = 1 then 20: b * = argmin b∈{0,...,j} (C[0, b] + C[b, j])▷ Takes O(1) time.21:Q = Q ∪ {x b * } 22: return QNotice that the derivative is monotonically non-decreasing and for any ℓ ∈ {k, k + 1, . . . , j -1} the derivative is fixed (independent of q) over any interval (x ℓ , x ℓ+1 ). This means that Q(q) is minimized at u = inf q ( dQ(q) dq ≥ 0), where u ∈ X. Denote by b * k,j ∈ {k, . . . , j} the value such that x b * k,j = u. Notice that while dQ(u) dq may not be defined, we have that lim h→0 + dQ(u+h) dq ≥ 0 is well-defined.b * k,j i=k+1 (x i -x k ) - j i=b * k,j +1 (x j -x i ) ≥ 0. With some simplifications, this is equivalent to: j i=k+1 x i -(b * k,j -k)x k -(j -b * k,j )x j ≥ 0, yielding b * k,j ≥ jxj -kx k -j i=k+1 xi xj -x k .As b * k,j is an integer, we get a formula for C 2 [k, j] that can be computed in constant time using:b * k,j = jx j -kx k - j i=k+1 x i x j -x k = jx j -kx k -(β j -β k ) x j -x k . That is, for any 1 ≤ k ≤ j ≤ d we have that C 2 [k, j] = C[k, b * k,j ] + C[b * k,j , j]is the sum of the variances in quantizing the entries in [x k , x j ] using the quantization values x k , x b * k,j , x j .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:MSE [i, j] =      min k∈{i,...,j} MSE [i -2, k] + C 2 [k, j] i > 3 C 2 [1, j] i = 3 C[1, j] i = 2, and the resulting pseudo-code for Accelerated QUIVER is given by Algorithm 2. Similarly to QUIVER, we start by initializing the first row of MSE . Importantly, we now separate the even s case (lines 5-6), in which we initialize the row using C, and the odd case, where we use C 2 (lines 8-9). That is, the odd s case 'skips' a 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 matrixB[k, j] ≜ MSE [2 • (i -1) + s ′ , K[i, j]] + C 2 [K[i, j], j].The output yields the minimizers of MSE [2 • i + s ′ , j] used for reconstruction. In the reconstruction step (lines 15-21), 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 at most half of the memory to store K and MSE .To establish correctness, we state the following lemma, whose proof appears in Appendix C.Lemma 5.1. C 2 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 a , x c ]. 
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 on a uniform grid of controllable size m + 1 ≥ s (for some m ∈ N + ), we can accelerate the computation at the cost of a small additional error. Importantly, while the quantization values are from a discretized set of possibilities, we compute the optimal subset of discretized values for the original input vector.To that end, consider the discrete setS = x 1 + ℓ • x d -x1 m | ℓ ∈ {0, .. . , m} . Our goal is then to find Q ∈ S s that minimizes the sum of variances for the original input. Denotings ℓ = x 1 +ℓ• x d -x1m , we modify our preprocessing scheme to consider the discretization:α ℓ = x∈[s0,s ℓ ] 1 , β ℓ = x∈[s0,s ℓ ] x , γ ℓ = x∈[s0,s ℓ ]x 2 ∀ℓ ∈ {1, . . . , m} .As we explain in Appendix E, we can compute these values in O(d) time and space.Using these arrays, we can express the sum of variances of all input entries between two quantization values s k , s j as follows:C m [k, j] = x∈[s k ,sj ] (s j -x)(x -s k ) = x∈(s k ,sj ] (s j -x)(x -s k ) = -s j • s k • x∈(s k ,sj ] 1 + (s j + s k ) • x∈(s k ,sj ] x - x∈(s k ,sj ] x 2 = -s j • s k • (α j -α k ) + (s j + s k ) • (β j -β k ) -(γ j -γ k ).Note that the quadrangle inequality trivially holds for this extension. The resulting algorithm, termed Approximate QUIVER (or in short, Apx. QUIVER), proceeds as QUIVER with C m instead of C, except for the reconstruction stage where we pick Q from S instead of the input X. Apx. QUIVER, whose pseudo-code is given in Appendix F, runs in space and time complexities of O(d + m • s).We next analyze the approximation guarantee of Apx. QUIVER. Denote by opt X,s the optimal MSE attainable for X using s quantization values, and by AQ X,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, s, m we have AQ X,2s-2 ≤ opt X,s+ d•(x d -x1) 2 4m 2 ≤ opt X,s + d•∥X∥ 2 2 2m 2 .Proof. Let Q * ⊆ X be the optimal solution with |Q * | ≤ s. For any q ∈ Q * , denote by q = max {s ℓ ∈ S | s ℓ ≤ q} and q = min {s ℓ ∈ S | s ℓ ≥ q}. Consider the solutionQ = q, q | q ∈ Q * . Note that | Q| ≤ 2s -2 as x 1 , x d ∈ Q * and x 1 = x 1 and x d = x d . Also, Q ⊆ Sand is thus a valid solution of Apx. QUIVER. Thus, AQ X,2s-2 is upper bounded by the MSE when using Q.Next, consider x ∈ X and leta x = max {q ∈ Q * | q ≤ x} and b x = min {q ∈ Q * | q ≥ x}be the values between which x is stochastically quantized in Q * . We consider two cases:• x ∈ [a x , a x ) ∪ (b x , b x ].In this case, when using Q, we have that x is quantized in an interval of size (x d -x 1 )/m and thus its variance is bounded by(x d -x 1 ) 2 /4m 2 . • x ∈ [a x , b x ], in this case, using Q, x is quantized between a x and b x , yielding a variance of (b x -x)(x -a x ) ≤ (b x -x)(x -a x ), i.e., lower than the variance under Q * .As the two cases capture all options, summing the variances over all x ∈ X yields the result.In terms of the vector normalized MSE (vNMSE), 1 which is a normalized MSE measure given byE ∥X-X∥ 2 2 ∥X∥ 2 2, Apx. QUIVER with 2s -2 quantization values achieves an additive d 2m 2 term to the optimal vNMSE when using s quantization values.However, the first inequality of Lemma 6.1 is generally much tighter than the second that uses the squared norm. For example, if the entries of X were i.i.d. U [a, b] random variables, for some constants a < b then (x d -x 1 ) 2 = O(1) while ∥X∥  
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 a 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.4× speedup.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 1). Acc. QUIVER Baselines. We evaluate Accelerated QUIVER and compare its runtime to ZipML [26] . For the approximate variants, we evaluate Apx. QUIVER and compare it with three approximation variants of ZipML proposed in [26] ) time. It guarantees that its sum of variances is at most twice that of an optimal solution with ⌊s/2⌋ quantization values. We also compare with the recently proposed ALQ [28] , which is an algorithm that finds good quantization values for a truncated normal distribution. 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 exact mean, variance, and support parameters for the input vector. This then runs for several (we used 10, as in their released code) iterations, so in total, they compute ≈ 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. We further discuss these approximation algorithms in Appendix I.Exact algorithms experiments. The results are presented in Figure 2 . 16 . As shown, the vNMSE decays linearly with s 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 3 . It is evident in Figure 3 (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 3(c), Apx. QUIVER offers these advantages for different s, m values.Notably, on a commodity PC, Apx. QUIVER can compute near-optimal 4-bit quantization values (s = 16) for a vector with d = 2 20 entries in just six milliseconds, and about 70ms for d = 2 24 , potentially enabling quantizing vectors on the fly for many applications. 
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 of 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 GPUfriendly ASQ algorithms. Also, similarly to previous works (e.g., [26] ), our exact solution assumes that the input vector is sorted. Otherwise, the runtime is increased to O(d • log d + s • d). We note that Apx. QUIVER does not require the vector to be sorted and the time complexity remains O(d + s • m) even for non-sorted inputs, making it even more appealing compared to the exact solutions.Offloading Computation to a GPU: For exact algorithms, one can sort the input vector on a 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 J 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 a 1M -sized vector sums up to only 4ms where the runtime of Accelerated QUIVER is about one second.Generalizing the algorithms for weighted inputs: An interesting generalization of the ASQ problem is the weighted variant, where each entry x i ∈ X is associated with a weight w i ∈ R and the goal is to minimize the weighted sum of variancesd i=1 (x i -x i ) 2 • w i .This variant is useful when, instead of getting an input vector, one wishes to solve ASQ for an empirical distribution. In Appendix K we explain how our algorithms and their analyses generalize to the weighted case, while maintaining the O(d • 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 is open sourced [30] .Algorithm 3 Basic Dynamic Programming Algorithm 1: Input: X ∈ R d , s ∈ N. 2: Compute C : [d] × [d] → R + using X. 3: for j = 2 to d do 4: MSE [2, j] = C[1, j] 5: for i = 3 to s do 6:for j = i to d do 7:MSE [i, j] = min k∈{i,...,j} MSE [i -1, k] + C[k, j] 8: j = d 9: Q = {x 1 , x d } 10: for i = s down to 3 do 11: j = argmin k∈{i,...,j} MSE [i -1, k] + C[k, j] 12: Q = Q ∪ {x j } 13: return Q A Basic AlgorithmWe now describe a simple algorithm that finds the optimal quantization values using the dynamic program, with pseudo-code given by Algorithm 3. After initialization (lines 2-4), the algorithm iteratively computes MSE [i, •] given MSE [i-1, •] (lines 5-7) and traces back the optimal quantization values given the solution (lines 8-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:• Pruning Phase: Remove columns that cannot possibly contain a row maximum. This is done by comparing each column with its neighbors and discarding those that cannot be maxima based on the totally monotone property. At the end of this phase, the number of columns can be no larger than the number of rows.• Recursive Reduction: The algorithm reduces the problem size by considering a subset of the rows and columns. It 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 O(d) for a d × d matrix. This efficiency is due to the recursive reduction of the 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 a 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) + 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.1Lemma 5.1. C 2 satisfies the quadrangle inequality.Proof. The lemma claims that, for any a ≤ b ≤ c ≤ d:C 2 [a, c] + C 2 [b, d] ≤ C 2 [a, d] + C 2 [b, c].Recall that for any a ≤ c ∈ {1, . . . , d}, we denote b * a,c = argmin b∈{a,...,c}C[a, b] + C[b, c].We prove the lemma by a case analysis:• Case b * b,c ≤ b * a,d . In this case, we have that: C 2 (a, c) + C 2 (b, d) = C(a, b * a,c ) + C(b * a,c , c) + C(b, b * b,d ) + C(b * b,d , d) ≤ (i) C(a, b * b,c ) + C(b * b,c , c) + C(b, b * a,d ) + C(b * a,d , d) ≤ (ii) C(b, b * b,c ) + C(b * b,c , c) + C(a, b * a,d ) + C(b * a,d , d) = C 2 (b, c) + C 2 (a, d).,c ) + C(b, b * a,d ) ≤ C(b, b * b,c ) + C(a, b * a,d ). • Case b * b,c > b * a,d .In this case, we have that: C 2 (a, c) + C 2 (b, d) = C(a, b * a,c ) + C(b * a,c , c) + C(b, b * b,d ) + C(b * b,d , d) ≤ (i) C(a, b * a,d ) + C(b * a,d , c) + C(b, b * b,c ) + C(b * b,c , d) ≤ (ii) C(b, b * b,c ) + C(b * b,c , c) + C(a, b * a,d ) + C(b * a,d , d) = C 2 (b, c) + C 2 (a, d).We explain why our acceleration method from Section 4 fails for s > 3. Consider computing the location of two additional quantization values b ≤ u between x a and x c . Similarly to the above analysis, we define by Q(b, u) the resulting sum of variances for all entries in [x a , x c ]. Then:Q(b, u) = x∈[xa,b] (b -x)(x -x a ) + x∈(b,u] (u -x)(x -b) + x∈(u,xc] (x c -x)(x -u).Computing the partial derivatives, we then get:∂Q(b, u) ∂b = x∈[xa,b] (x -x a ) - x∈(b,u] (u -x). ∂Q(b, u) ∂u = x∈(b,u] (x -b) - x∈(u,xc] (x c -x).The challenge now is that both derivatives are non-continuous, and there are multiple indices i, j such that Q(x i , x j ) < 0 but Q(x i+1 , x j ) ≥ 0 or Q(x i , x j+1 ) ≥ 0. Accordingly, it seems unlikely that a closed-form solution that is computable in constant time follows from this approach.Algorithm 4 Apx. QUIVER 1: Input: X ∈ R d , s, m ∈ N. 2: S = x 1 + ℓ • x d -x1 m | ℓ ∈ {0, . . . , m} 3: Preprocess(X, m) ▷ Enables computing C m [k, j] in constant time (Appendix E). 4: for j = 2 to m do 5: MSE [2, j] = C m [1, j] 6: for i = 3 to s do 7: K[i, •] = SMAWK(Z) ▷ Where Z[k, j] ≜ MSE [i -1, k] + Cm[k, j] ∀k, j.8:MSE [i, j] = MSE [i -1, K[i, j]] + C m [K[i, j], j] for all j ∈ {i, . . . , m}. 9: Q = {s 0 , s m } 10: j = m 11: for i = s down to 3 do 12:j = K[i, j] 13: Q = Q ∪ {s j } 14: return Q E Preprosessing for Apx. QUIVER Recall that, for S = x 1 + ℓ • x d -x1 m | ℓ ∈ {0, . . . , m} and s ℓ = x 1 + ℓ • x d -x1m , our goal is to compute the following arrays in O(d) time:α ℓ = x∈[s0,s ℓ ] 1 , β ℓ = x∈[s0,s ℓ ] x , γ ℓ = x∈[s0,s ℓ ]x 2 ∀ℓ ∈ {1, . . . , m} .Denoting δ = x d -x1m , the first step is to make a pass over the input and for each x ∈ X calculate ℓ x = x-x1 δ and setA ℓ = x|ℓx=ℓ 1 , B ℓ = x|ℓx=ℓ x , Γ ℓ = x|ℓx=ℓ x 2∀ℓ ∈ {1, . . . , m} .Next, we make an O(m) time pass to compute the cumulative sums:α ℓ = ℓ i=1 A i , β ℓ = ℓ i=1 B i , γ ℓ = ℓ i=1 Γ i ∀ℓ ∈ {1, . . . , m} .We note that an optimization that proved useful for improving the runtime in practice is to remove empty intervals after the first step. That is, we retain only intervals for which A ℓ > 0, thus reducing the number of intervals from m to m ′ ≤ m, which can be markedly smaller in practice.We describe the pseudo-code of Apx. QUIVER, which is given by Algorithm 4. We start by preprocessing the input to obtain the α, β, γ arrays ( Line 3). Next, we initialize the first row of the matrix, which only has m columns, using C m (Line 4). Follows are s -2 invocations of the SMAWK algorithm, each yielding the next row in MSE and its minimizers K[i, •] (Line 6). Finally, we compute the resulting quantization value set Q from K and S (Line 11).Here, we evaluate by how much Accelerated QUIVER is faster than QUIVER. The results, depicted in Figure 4 , show that Accelerated QUIVER is up to 5.4× faster for s = 3 and is consistently faster throughout. Interestingly, the speedup is more significant in odd values of s. This is because the number of SMAWK invocations is ⌊s/2⌋ -1 in Accelerated QUIVER (e.g., it does not invoke SMAWK at all for s = 3, only once for s = 5, etc.), compared to s -2 invocations in QUIVER.Additional evaluation results of exact solutions. We provide results for additional input vectors distributions: Normal (Figure 5 ), Exponential (Figure 6 ), Truncated Normal (Figure 7 ), and Weibull (Figure 8 ). As shown, all follow the same trends in terms of vNMSE, while the runtime is largely independent of the input distribution.In the ZipML paper [26] , the authors propose two heuristic methods for improving the runtime. The first heuristic includes calculating the optimal solution on a subset of X called candidate points (CP); they further present an analysis that bounds the error with respect to the maximal difference between consecutive CPs and the maximal number of entries in X between consecutive CPs; however, as they do not provide a way to select the CPs, we consider two natural choices: using Uniform CPs, i.e., 2 This variant is termed 'ZipML-CP Unif.' in our evaluation. The second choice of CP is Quantiles, which uses the set x ⌊1+ℓ•(d-1)/m⌋ | ℓ ∈ {0, . . . , m} . This variant is termed 'ZipML-CP Quant.' in our evaluation.x 1 + ℓ • x d -x1 m | ℓ ∈ {0, . . . , m} .The second heuristic has a 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 is termed 'ZipML 2-Apx' in our evaluation. 2 We note that this is different our histogram approach in two aspects: (i) we stochastically quantize X into the set S and (ii) we use weights to consider the number of entries in each histogram bin. LogNormal(0,1)2 20 2 21 2 22 2 23 2 24 Input Dimension (d) Acc. QUIVER Acc. QUIVER We also compare against ALQ [28] , 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 to approximate the optimal quantization values of the fitted distribution up to 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 of approximate solutions. Similarly, we show the approximation algorithms evaluation results for the various distributions and s values: Normal (Figure 9 ), Exponential (Figure 10 ), Truncated Normal (Figure 11 ), and Weibull (Figure 12 ). Again, the runtime of all algorithms is weakly affected by the input distribution. Apx. QUIVER is always the most accurate for increasing d values and has a near-optimal vNMSE when using a sufficient value for m (e.g., m ≥ 400) while being markedly faster than all alternatives. Acc. QUIVER 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 are fast even for large vectors, despite the usage of a somewhat weak GPU. This specific measurement was done over the LogNormal(0,1) distribution, but the sorting and quantization times are largely independent of the specific distribution and were similar to other tested distributions as well.We generalize our algorithms for processing sorted weighted inputs X, W ∈ R d (where each entry has value y ℓ and weight w ℓ and x 1 ≤ x 2 ≤ . . . , x d ). 3Most 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.Pre-processing. To allow constant time computation of weighted C, denoted C w , for weighted inputs we need another auxiliary array. Namely, we define the following: Then, we can then write:C w [k, j] x ℓ ∈[x k ,xj ] w • (x j -x ℓ )(x ℓ -x k ) = x ℓ ∈(x k ,xj ] w • (x j -x ℓ )(x ℓ -x k ) = x j • x k • x ℓ ∈(x k ,xj ] w ℓ + (x j -x k ) • x ℓ ∈(x k ,xj ] w ℓ • x ℓ - x ℓ ∈(x k ,xj ] w ℓ • x 2 ℓ = x j • x k • (α j -α k ) + (x j -x k ) • (β j -β k ) -(γ j -γ k ).Observe that C w clearly satisfies the quadrangle inequality, and thus, the correctness follows. The approximation variant also follows similarly. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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 societal 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 an implementation of the SMAWK algorithm by Daniel Steinberg, 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 or dataset.• The authors should state which version of the asset is used and, if 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 of use in the 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 a dataset.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.Similarly to the unweighted case, the sorted vector requirement is only needed for the exact solutions. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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). 
2. 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). 
3. 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.
questions: questions: 1. Are there alternatives to SMAWK that can be implemented (with some small modifications) that still allow QUIVER to work?
2. 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?
3. Are there any other results in the literature that you can compare with Apx. QUIVER results (such as line 223 - 224)?
4.  The asymptotic difference among the approximate algorithms are not clear to me in Figure 3, can the author elaborate further?
limitations: limitations: Yes
paper_summary: paper_summary: This paper studies the Adaptive Stochastic Quantization (ASQ) problem and presents a dynamic programming based algorithm that improves time and space complexities.
strength_weakness: strength_weakness: 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:

ln. 29, $X’$

on ln37,   $\hat{X}$ concatenation of  $\hat{x}$’s ?  define all  parameters before using them.

same for $\theta(s)$ on ln 107. 

-ln. 106   is Q in X ?

- Many abbreviations are undefined: ALQ,QSGD,RTN .
- ln. 56-57, It is  ambiguous  to which algorithms you are comparing  the  time and space  complexity of your algorithm.
- what does  “on a commodity PC” mean? provide specifications  of your processor.
- ln. 80 "orders of magnitude lower error" , compared to which algorithm?
- The definition of MSE[i,j] in 109 is not clear. please write it mathematically.

- 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.
questions: 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: limitations: The proposed Algorithm is not implemented for ML model and  gradient compression.
paper_summary: paper_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.

I have read the authors' responses to my comments and made changed the overall score.
strength_weakness: strength_weakness: 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.
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)?

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. 

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.  

Other comments:
Line 106: the inclusion of Q in X seems a typo.
questions: questions: Please state the problem much earlier.
limitations: limitations: The paper addresses the limitations appropriately.
paper_summary: paper_summary: The paper is concerned with quantization,
that is encoding the components of a vector $X\in \mathbb{R}^{d}$ in a finite
alphabet $Q$ of given size $s$. The goal is unbiased,
stochastic quantization, where for a given component $x$ the encoding value $%
\hat{x}$ are chosen at random such that $E\left[ \hat{x}\right] =E\left[ x%
\right] $. Given $Q$ this fixes the encoding procedure, so that the
principal problem is the choice of the alphabet $Q$, which should minimize
the mean squared error (MSE) $E\left[ \left\Vert X-\hat{X}\right\Vert \right]
$, for fixed size $s$. It is important to realize that the optimal alphabet
is a subset of the set of components of $X$, so $s\leq d$. An optimal
solution has been found by Zhang et al [24] and the same paper already
offers an improved algorithm called ZipML of $O\left( sd^{2}\right) $
runtime and $O\left( d^{2}\right) $ memory requirement.

The paper at hand builds on the analysis of the latter paper, and gives an
improved algorithm  of $O\left( sd\right) $ both runtime and memory
complexity. Using a closed form solution for $s=3$ runtime and memory
requirements are halved in another improvement of the algorithm. Just as the
previous algorithm this version also returns the optimal solution.

To further accelerate the method the authors discretize the quantization
values on a grid of fixed size $m+1>s$ and seek a subset of this grid to
minimize the MSE for resulting set. The algorithm they present then has
space and time complexity of $O\left( d+ms\right) $. Because of this
improvement on can afford a larger cardinality of the set of quantization
values. The excess error of this approximate algorithm for $2s-2$
quantization values over the previous algorithm with $s$ quantization values
is bounded.

The paper then gives results of numerical experiments with various
distributions.
strength_weakness: strength_weakness: 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.
questions: 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: 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.

Comments: title: Reviewer Response
Relating to the Weaknesses
comment: Thanks for the reference!
We will study it and discuss it in the paper.
Thank you for correcting the terms. Although the presentation of the paper should be clear enough to not raise these concerns, I will defer to the other reviewers' comments and area chair.
Thank you for addressing my comments. 

I have changed my mind about the fit to NeurIPS.

Concerning the discussion about the source of redundancy, perhaps there are similarities with the unfolding/unrolling optimization concept. For example, see:
Monga, Vishal, Yuelong Li, and Yonina C. Eldar. "Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing." IEEE Signal Processing Magazine 38.2 (2021): 18-44.
Please read the submission text (lines 109-110), which is comprehensive and correct:

``we denote by $MSE[i,j]$ the optimal MSE of quantizing the prefix vector $X_j=\langle{x_1,\ldots,x_j}\rangle$ **using $i$ quantization values** *that include* $x_j$''.

That is, the corresponding mathematical formulation is:
$$
MSE[i,j] = \min_{Q: |Q|\le {i}, x_j\in Q} \sum_{x\in X_j} (b_x-x)(x-a_x).
$$

We are puzzled by your low score, which is due to minor typos and presentation issues, without any evaluation of the contribution of the proposed methods.
Thank you for clarification of some of my points. Some are unaddressed in your rebuttal.  Please add clear definition of  MSE[i,j] to the paper. The one I see in your rebuttal comments does not show  dependency on i. You can add a notation definition subsection to avoid confusions, for instance \hat{x} \in \{a_x,b_x\}  is your notation for ASQ, please don't assume the readers know it already. The ASQ is the main definition in your paper, yet you defined it only inline on ln. 94-97. It better be a numbered equation to  be clear.  I see other reviewers commenting on some notations as well. I still think the presentation of the paper needs much further improvement, therefore I will keep my score.
Thank you for the clarification provided. I will keep my score, modulo potential insights in the discussion phase with the other reviewers.
I really appreciate the detailed answers and the responses the author made regarding my reviews. Most of my points are addressed properly, and I believe the revised version with the additional details will be quite solid. While I will have to see further discussion with AC and other reviewers to improve the score I have given, I am certainly in support of this paper acceptance.
**W1** Thank you for the suggestion. We agree that explaining the SMAWK algorithm in detail and providing more intuition about it will improve the paper, and we will add these for the camera-ready version. 

We provide the high-level details here:

*SMAWK Algorithm Steps* 

* Pruning Phase:
> Remove columns that cannot possibly contain a row maximum. This is done by comparing each column with its neighbors and discarding those that cannot be maxima based on the totally monotone property. At the end of this phase, the number of columns can be no larger than the number of rows.

* Recursive Reduction:
> The algorithm reduces the problem size by considering a subset of the rows and columns. It 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.

---

**Efficiency:**
The SMAWK algorithm achieves a time complexity of $O(d)$ for a $d×d$ matrix. This efficiency is due to the recursive reduction of the 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 a 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) + O(n) = O(n)$.
A simple example Python (by David Eppstein) implementation appears here: https://github.com/pombredanne/code-5/blob/master/recipes/Python/117244_SMAWK_totally_monotone_matrix_searching/recipe-117244.py. 
Our implementation is in optimized C++ and we will release it as open source with the publication of the paper.

**W2**  The novelty of QUIVER is the identification that producing MSE[i,·] from MSE[i-1,·] can be expressed as the problem of finding the maximas in an *implicitly defined* matrix. This requires several steps, including our pre-processing (to enable matrix queries in constant time) and proving the quadrangle inequality. Further, finding MSE[i,·] from MSE[i-1,·] is only a subroutine in the algorithm which invokes it several times and also reconstructs the resulting solution.

Further novelty is in our Accelerated QUIVER algorithm which provides a faster solution to the same problem, and the Approx. QUIVER that provides further speedup at the cost of a small error. 

We will further clarify our contribution in the paper.

**W3** Accelerated QUIVER works and is faster than QUIVER for all $s$. When $s>3$, it also requires invoking the SMAWK algorithm as a subroutine, but the number of invocations reduces significantly.  We will further clarify this in the text.

Namely, we provide a closed-form, computable in constant time, solution for the $s=3$ problem, and then reformulate the dynamic program (see lines 171-182) to allow fewer recursive steps, thereby improving both the speed and space requirements both theoretically and in practice.

If our understanding of this weakness is incorrect, we would appreciate if the reviewer could clarify.