New Bounds For Distributed Mean Estimation and Variance Reduction
Authors: Peter Davies
Vijaykrishna Gurunanthan
Niusha Moshrefi
Saleh Ashkboos
Dan Alistarh
Venue: ICLR 2021 Poster (2021)
Keywords: distributed machine learning
mean estimation
variance reduction
lattices

Abstract:  We consider the problem of distributed mean estimation (DME), in which $n$ machines are each given a local $d$-dimensional vector $\mathbf x_v \in \mathbb R^d$, and must cooperate to estimate the mean of their inputs $\mathbf \mu = \frac 1n\sum_{v = 1}^n \mathbf x_v$, while minimizing total communication cost. DME is a fundamental construct in distributed machine learning, and there has been considerable work on variants of this problem, especially in the context of distributed variance reduction for stochastic gradients in parallel SGD. Previous work typically assumes an upper bound on the norm of the input vectors, and achieves an error bound in terms of this norm. However, in many real applications, the input vectors are concentrated around the correct output $\mathbf \mu$, but $\mathbf \mu$ itself has large norm. In such cases, previous output error bounds perform poorly. 
            In this paper, we show that output error bounds need not depend on input norm. We provide a method of quantization which allows distributed mean estimation to be performed with solution quality dependent only on the distance between inputs, not on input norm, and show an analogous result for distributed variance reduction. The technique is based on a new connection with lattice theory. We also provide lower bounds showing that the communication to error trade-off of our algorithms is asymptotically optimal. As the lattices achieving optimal bounds under $\ell_2$-norm can be computationally impractical, we also present an extension which leverages  easy-to-use cubic lattices, and is loose only up to a logarithmic factor in $d$. We show experimentally that our method yields practical improvements for common applications, relative to prior approaches.  

Published as a conference paper at ICLR 2021
NEW BOUNDS FOR DISTRIBUTED MEAN ESTIMATION AND VARIANCE REDUCTION
Peter Davies
Vijaykrishna Gurunathan ITT Bombay
IST Austria peter. davies@ist.ac.dt at
1assmavijay19999@mma1.....
Niusha Moshrefi
Saleh Ashkboos
IST Austria
IST Austria saleh. ashkboosCist. ac
niusha. wwwaaaaosssessssoeoeoooe at
Dan Alistarh
IST Austria NauralMagic dan. alistarh@ist.an ac at
ABSTRACT
We consider the problem of distributed mean estimation (DME), in which n machines are each given a local d-dimensional vector Iy E Rd and must cooperate to estimate the mean of their inputs μ μ= n E Ty while min- imizing total communication cost. DME is fundamental construct in dis- tributed machine learning, and there has been considerable work on variants of this problem, especially in the context of distributed variance reduction for stochastic gradients in parallel SGD. Previous work typically assumes an upper bound on the norm of the input voctors, and achieves an error bound in terms of this norm. However, in many real applications, the input vectors are concentrated around the correct output μe, but μu itself has large norm. In such cases, previous output error bounds perform poorly.
In this paper, we show that output error bounds need not depend on in- put norm. We provide a method of quantization which allows distributed mean estimation to be performed with solution quality dependent only on the distance between inputs, not on input norm, and show an analogous new
result for distributed variance reduction. The technique is based connection with lattice thcory. We also provide lower bounds showing that the communication to error trade-off of our algorithms is asymptotically optimal. As the lattices achieving optimal bounds under fz-norm can be computationally impractical, we also present an extension which leverages easy-Lo-use cubie lattices, and loose only up to a logarithmic factor d. We show experimentally that our method yields practical improvements for common applications, relative prior approaches.
INTRODUCTION
Several problems in distributed machine learning and optimization can be reduced to vari- ants distributed mean estimation problem, in which n machines must cooperate to jointly estimate the mean of their d-dimensional inputs μ + >n F, as closcly as possible, while minimizing communication. In particular, this construct is often used for distributed vari- ance reduction: here, each machine reccives as input an independent probabilistic estimate of a d-dimensional vector V, and the aim is for all machines to output a common estimate of V with lower variance than the individual inputs, minimizing communication. Without any communicatio restrictions, the ideal output would be the mean of all machines' inputs.
While variants of these fundamental problems have been considered since seminal work by Tsitsiklis & Luo 1987), the task has seen renewed attention recently in the context.

---

Published as a conference paper at ICLR 2021
of distributed machine learning. In particular, variance reduction is key component in data-parallel distributed stochastic gradient descent. (SGD), ; the slandard way to parallelize the training of deep neural networks, e.g. [Bottou (2010); Abadi et al. (2016), where it is used to estimate the average of gradient updates obtained in parallel at the nodes. Thus, several prior works proposed efficientt compression schemes to solve variance reduction or
mean estimation, see e.g. Suresh et al.] (2017); Alistarh et al. (2017) : [Raezani-Kebrya et al. (2019); Gandikota et al. (2019), and Ben--Nu & Hoefler (2019) for a general survey
of practical distribution schemes. These schemes seek to quanfize nodes' inputs coordinate-
wise to one of a limited collection of values, in order to then efficiently encode and transmit
these quantized values. A trade-off then arises between the number of bits sent, and the
added variance due of quantization.
Since the measure of output quality is variance, it appears most natural to evaluate this with respect to input variance, in order to show that variance reduction is indeed achieved. Surprssingy, however, we aware of no previous works which do so; all existing methods give bounds on output variance in terms of the squared input norm. This clearly subopti- mal when the squared norm is higher than the variance, i.e, when inputs are not centered around the origin. In some practical scenarios this causes output variance to be higher than input variance, as we demonstrate in Section
Contributions. In this paper, we provide the first bounds for distributed mean estima- tion and variance reduction which are still tight when inputs are not centered around the origin. Our results are based on new lattice-based quantization techniques, which may be of independent interest, and come with matching lower bounds, and practical extensions. More procisely, our contributions are as follows:
For distributed mean estimation, we show that, to achieve a reduction of a factor q in the imput 'variance' (which we define to be the maximum squared distance between inputs), it is necessary and sufficient for machines to communicate log q) bits.
For variance reduction, show tight Odd n) bounds the worst-case commu- nication bits required to achieve optimal ((n)-factor variance reduction by n nodes over d-dimensional input, and indeed to achieve any variance reduction at all. We then show how incorporating error detection into our quantization scheme, we can also obtain tight bounds on the bits required in expectation.
We show how to efficiently instantiate our lattice-based quantization framework in practice, with guarantees. In particular, we devise a variant of the scheme which ensures close-to-on doseeto-optimal communication-varian bic lattice, and use it to obtain improvements relative to the best. known previous methods for distributed mean estimation, both on synthetic and real-world lasks.
bounds even for the standard cu-
1.1 PROBLEM DEFINITIONS AND DISCUSSION
MEANESTIMATION is defined as follows: we have n machines u, and each receives as input a vector C, E IRd, We also assume that all machines receive a common value y, with the guarantee that for any machines u, U, || - æ, S y. Our goal is for all machines to output the same value EST E Rd, which is an unbiased estimator of the mean f == EveM Bes Le. E [ESTT] = μe, with variance as low possible. Notice that the input specification is entirely deterministic; any randomness in the output ariscs only from the algorithm used.
In the variant of VARIANCEREDUCTION, we again have a set of n machines, and now an unknown true vector V. Each machine v receives as input an independent unbiased estima- tor Ie of V (i.e., E [x,] = V) with variance E || v| I o². Machines are assumed to have knowledge of a. Our goal is for all machines to output the same value EST E Rd which is an unbiasod estimator of V, i.c., E EST V, with low variance. Since the input is random, output randomness now stems from this input randomness as well as any randomness in the algorithm.
DERIANCEREDUCTUUS is common for instance in the context of gradient-based optimization of machine learning models, where we assume that each machine v processes local samples in order to obtain a slochastic gradient ge. which is an unbiased estimator of the true gradient V, with variance bound o². If we directly averaged the local stochastic gradients Go, we
2

---

Published as a conference paper at ICLR 2021
could obtain unbiased estimator of the true gradient G with variance bound o² //n, which can lead to laster convergence.
Input Variance Assumption. The parameter y replaces the usual MEANESTIMATION assumption of a known bound MI on the norms of inpul vectors. Note that, in the worst case, we can always set y = 2M and obtain the same asymptolic upper bounds as in e.g. Suresh et al. (2017); our results are therefore al least as good as previous approaches in all cases, but provide significant improvement. when inputs are not centered around the origin.
The reason for this change is to allow stronger bounds in scenarios where we expect inputs to be closer to each other than to the origin. In particular, it allows MEANESTIMATION problem to more effectively generalize VARIANCEREDUCTIONN Parameter y is a determinis- tic analogue of the parameter for VARIANCEREDUCTTONS both y and a provide bound on the distance of inputs from their mean, rather than from the origin. Accordingly, input instance corresponds (up to constant factors) to
variance o² for VARIANCEREDU y² for MEANESTIMATION instance. For consistency of terminology, we therefore refer to y² as the imput variance of the instance (despite such inputs being deterministic).
It is common in machine learning applications of VARIANCFREDUCTTON to assume that an estimate of the variance o² is known (Alistrrh et al., 2017; Gandikota et al., 2019). To study both problems in common framework, MRANESTIMATION, and assume knowledge of the input variance y² Even the relevant. bounds y or are not known priori, they can usually be estimated in practice.
make the analogous assumption about
Relationship Between Problems. If one allows unrestricted communication, the natural solution to both problems is to average the inputs. This is an exact solution to MEANES- TIMATION with variance 0, and is also an asymptotically optimal solution to VARIANCERE- DUCTION, of variance at most, a²
However, doing so would require the exchange of infi- nile precision real numbers. So, it. is common to instead communicate quanlized values of bounded bit-length (Alistarh et al. 2017), which will engender additional variance caused by random choices within the quantization method. The resulting estimates will therefore
have variance Varguant for MEANESTIMATION and o² + Var quant for VARIANCEREDUC-- TION. We will show tradc-off between bits of communication and output variance for both problems; in the case of VARLANGEREDUCTION though, there is an 'upper limit" to this trade-off, since we cannot go below Q( ) total output variance.
The other major difference between the two problems is that in MeaN distances between inputs are bounded by y with certainty, whereas in VARIANCEREDUCTION they are instcad bounded by O(a) only in expectation. This causes extra complications for quantization, and introduces a gap between average and worst-casc communication cost.
Distributed Model. We aim to provide a widely applicable method for distributed mcan estimation, and therefore we avoid relying on the specifics of particular distributed models. Instead, we assume that the basic communication structures we use (stars and binary trees) can be constructed without significant, overhead. This setting is supported by machine learning applications. which have very high input dimension (i.e., > n), and the costs of sy synchronization or const ruction of an overlay (which do not depend on d, and are generally poly-logarithmic in n), will be heavily dominated by the communication costs incurred subsequently during mean estimation. They also need only be incurred once, even if mean estimation or variance reduction is to be performed many times (e.g. during distributed SGD). For these reasons, we do not include these model-specific setup costs in our stated complexities; any implementation should take them into separate consideration.
For simplicity, we will present our algorithms within a basic synchronous fault-free message- passing model, in which machines can send arbitrary messages to any other machine, but they could naturally be extended to asynchronous and thared--emory models of communi- cation. Our aim will be to minimize the number of bits sent and received by any machine during the algorithm; we do not consider other mcasures such as round complexity.
Vector Norms. When dealing with vectors in Rd, will use names in bold, e.g. x, y. We will state most of our results in such a way that they will apply to any of the three
1 FFor specific classes of input distribution, and for non-asymptotic concentration results, however, better estimators of V are known; see e.g. Joly al. (017))
3

---

Published as a conference paper at ICLR 2021
most commonly-use used norms on Rd in applications: l norm | Ei= loals lz norm ||]|| == v Vi =f, and & norm || == max ||z:||- Throughout the paper we will therefore use the general notation ||- which should be considered to be fixed as one of these norms, other than for statements specific to particular norms. Definitions which depend on norms, such as variance Var [x] : E [| E [ax] [1 are therefore assumed to also be under the appropriate norm.
1.2 RELATED WORK
Several recent works consider efficient compression schemes for stochastic gradients, e.g. Seide et al. (2014): Wang et al. 20188) ; Alistarh et al. 2017 2018:: Stich et al. (2018) ;
Wen et al. [017]] Wangni et al. 2018 Lu & Sa 2220)) We emphasize that these works
consider a related, but diflerent problem: they usually rely on assumptions on the input structure such as second-moment bounds on the gradients-and are evaluated primarily on the practical performance of SGD, rather than isolating the varianco-reduction step. (In some cases, these schemes also rely on history /error-corroetionn (Aji & Heafield 2017 Dry- den ct al., 2016 Alistarh ct al. 2018 Stich et al. 2018).) As a result, they do not provide thcoretical bounds on the problems we consider. In this sense, our work is closer to Suresh (2018); Gandikota al. (2019), which focus primarily on the distribuled mean estimation problem, with SGD as only one potential application.
et a.. (2017); Konečný & Richtárik
For example, QSGD (Alistarh et. al. 2017) considers similar problem to VARIANCERE- DUCTION; the major difference is that coordinates of the imput vectors are assumed to be specified by 3i- floats, rather than arbitrary real values. Hence, transmitting imput vectors exactly already requires only O(d) bits. They therefore focus on reducing the con- stant factor (and thereby improving practical performance for SGD), rather than providing asymptotic results on communication cost. They show that the expected number of bits per entry can be reduced from 32 to 2.8, at the expense of having an output variance bound in terms of input norm rather than imput variance.
This is a common issue with existing quantization schemes, which Icads to non-trivial com- plications when applying quantization to gradient descent and variance-reduced SGD (Kün- stner 2017) or to model-averaging SGD (Lu & Sa 2020), since in this case the imputs are clearly not centered around the origin. The standard way to circumvent this issue, adopted by the latter two references, but also by other work on quantization (Mishchenko el al., 2019), is to carefully adapt the quantization scheme and the algorithm to remove this issue, for instance by quantizing differences with respect to the last quantization point. These approaches, however, do not provide improvement 'one-shot' quantization methods, and instead rely on historical information and propertics of SGD or the function to optimize (such smoothness). They are therefore inherently application-specife contrast, does not require "manual" centering of the iterates, and does not require storage of previous iterates, or any properties thereof. Konečný & Richtárik] (2018) study MEANESTE. MATION under similar assumptions, and are the only prior work to use quantization centered around points other than the origin. However, again prior knowledge about the input dis- tribution must be assumed for their scheme to provide any improvements.
Our method, by
Suresh et al. (2017) study the MEANESTIMATION problem defined on real-valued input vec- tors. They present a series of quantization methods, providing an 0 Even
| (2) upper bound, and corresponding lower bounds. Recent work by Gandikota et al. (2019) studies VARIANCEREDUCTION and uses multi-dimeensioall quantization techniques. However, their locus is on protocols using o(d)-bit messages per machine (which we show connol reduce input variance). They do give two quantization methods using O(d)-bit messages. Of these, one gives an O L max.s ||xx,11)) bound on output variance, similar to the bound of Suresh et al. (2017) for MEANESTIMATION (the other is much less efficient since it is designed to achiove a privacy guarantce). Mayckar & Tyagi (2020) obtain a similar error bound but with slightly longer Odd log log(log dj)-bit messages.
All of the above works provide output. error bounds based on the norms of input vectors. This is only optimal under the implicit assumption that inputs are centered around the origin. In Section we provide evidence that this assumption does not hold in some practical
4

---

Published as a conference paper at ICLR 2021
scenarios, where the imput (gradient) variance can be much lower than the input (gradient) norm: intuitively, for SGD, input variance is only close to squared norm when true gradients are close to O, i.e, the optimization process is already almost complete.
OUR RESULTS
In this work, we argue that it is both stronger and more natural to bound output variance in terms of input variance, rather than squared norm. We devise optimal quantization schemes for MEANESTIMATION and CADIANCEREDUCTION, and prove matching lower bounds, re- gardless of input norms. We summarize the main idcas that lead to these results.
2.1 LATTICE-BASEL QUANTIZATION
The reason that all prior works obtain output variance bounds in terms of input norm rather than variance that they employ sets of quantization points which are centered around the origin O. We instead cover the entire space Rd with quantization points that are in some sense uniformly spaced, using lattices.
Lattices are subgroups of IRd consisting of the integer combinations of set of basis vectors. well-known (Minkowski 1911) that certain lattices have desirable properties for cov- ering and packing Euclidean space, and lattices have been previously used for some other applications of quantization (soe, c.g., Gibson & Sayood (1988)). ), though mostly only in low dimension. By choosing an appropriate family of lattices, we show that any vector in Rd can be rounded (in a randomized, unbiased fashion) to a nearby latlice point, but also that there are not too many nearby lattice points, they can be specified using few bits.
Lattices contain an infinite number points, and therefore any encoding using a finite number of bits must use bit-strings to refer to an infinite amount of lattice points. To allow the receiver in our quantization method to correctly decode the intended point, we utilize the fact that we have bound on the distance between any two machines' inputs (y for MrANESTIMATION, and (n) (probabilistically, by Chobyshev's inequality) for VARI- ANCEREDUCTION). Therefore, if all points that map to the same bit-string are sufficiently far apart, a machine can correctly decode based on proximity its own input.
The simplest version of our lattice quantization algorithm can be described as follows
To encode Fu. randomly map to one of a set of nearby lattice points forming a convex hull around Fa. Denote this point by
Send # mod under the lattice basis: q is the quantization precision parameter.
To decode with respect to Φe, output the closest lattice point to Ea matching z mod q
By showing that V. is contained within convex hull of nearby lattice points, we can round to one of these points randomly to obtain z such that the expectation of z is æ itself, thereby ensuring unbiasedness. This is because point within convex hull be expressed as a linear combination of its vertices with coefficients in [0, 1]. which we can use as rounding probabilities.
Our reason for using mod with respect to the lattice basis in order to encode lattice points into bit-strings is that by exploiting properties of the particular lattices we employ, can show a lower bound on the distance between points encoded with the same bit-string, while also controlling the number of bits we use. Then, since points encoded with the same string are sufficiently far apart, our proximity-based dccoding procedure can determine the correct. point. We also have paramcter e which controls the granularity of the lattice used. This mothod of settice-based quantization gives the following guarantce for communicating vector between two parties:
Theorem 1. For any q = 2(1), any e > O, and any two parties v holding input vectors Lu, K., E IRd respectively, there is a quantization method in which u sends ( log q) bits to 0, and if || æx.Il O(ge), can recover unbiased estimate of a. with || x., O(e)-
5

---

Published as a conference paper at ICLR 2021
Details and proofs are deferred to the full version of this paper due to space constraints. This result is very general, and can be applied not only to distributed mean estimation but. to any application in which high-dimensional vectors are communicated, in order to reduce communication.
2.2 UPPER BOUNDS
Next, we show how apply our quantization procedure to NEANESTIMATION and VARI- ANCEREDUCTION. We wish to gather (quantized estimates of) machines' inputs to single machine, which computes the average, and broadcasts quantized estimate of this average to all other machines. For simplicity of analysis we do so using a star and a binary tree as our communications structures, but any connected communication topology would admit such an approach. The basic star topology algorithm can be described as follows:
All machines u send Tu, quantized with precision parameter and = (yy/)), the leader machine v.
Machine v decodes all received vectors, averages them, and broadcasts the result, using the same quantization parameters.
By choosing the leader randomly we can obtain tight bounds in expectation on the number of communication bits used per machine, and by using more balanced communication structure such binary tree we can extend these bounds in expectation to hold with certainly (at the expense of requiring more communication rounds).
Theorem 2. For any q = 2(1), MEANESTIMATION can be performed with each machine using strictly O(dlog 4) communication bits, with O ( output variance.
Theorem 3. VARIANCEREDDUCTIO can be performed using strielly O(dlogn) bils, with O output variance, succeeding with high probability.
These results give optimal commmicationn-aarinn make this bounds practical, we address two main challenges.
bounds for these problems. However, to
Challenge Input Variance. One difficulty with our approach that we assume known estimate of input variance (y² for MEANESTIMATION, o² for VARIANCEREDUCTION) Furthermore, in VARIANCEREDDUCTION even if our input variance estimate is correct, some pairs of inputs can be further apart, since the bound is probabilistic.
To address this problem, we develop mechanism for error delection, which allows the receiver to detect if the encode and decode vectors (æ, and æ, respectively) are too far apart for successful decoding. In this way, if our estimate of input variance proved too low, we can increase either it or the number of bits used for quantization until we succeed. The main idea is that rather than using mod q to encode lattice points, use more sophisticated coloring of the lattice and a new encoding procedure to ensure va and a, are far apart, with high probability the encoder chooses color which is not used by any nearby point to Va. and therefore u can tell that C, was not nearby.
As an application, we obtain an algorithm for VARIANCEREDUCTION which uses an optimal expected number of bits per machine (except for an additive log n, which in our applications is assumed to be far smaller than dlogg q):
Theorem 4. For any = 2(1), VARIANCEREDDUTTION can be performed using (d log + logn) n) commanication bits per machine in expectation, with O + a) output variance, succeeding with high probabilily.
Challenge 2: Computational Tractability. Another issuc is that known lattices which are optimal for & and fz-nosms can be computationally prohibitive to generate and use for problems in high dimension. We show that if we instead use the standard cubic lattice, which is optimal under -orm and admits straight.orward O(d)-computation encoding and decoding algorithms, in combination with structured random rotation using the Walsh- Hadamard transform as proposed by Suresh et. al. (2017) we can come within a log-factor variance of the optimal bounds of Theorems
3 and

---

Published as a conference paper at ICLR 2021
Thcorem 5. Using the cubic lattice with random rotation, achieve the following output
variances under nn-norm (succeediigg with high probubility):
0
q log nd for MEANESTIMATION, using striclly Old log q) bils;
0 loRd for VARIANCEREDUCTION, using strictly O(dlogn) bits;
= for VARIANCEREDUCTIOON using O(d g + log bits in expec- O 00 lognd
lation.
Furthermore, each machine need perform only O(d) computation in ezpectation.
Under the cubic lattice, our quantization method particularly simple and efficient in practice. Since the lattice basis is orthogonal, vector encoding and decoding by finding ap- propriate nearby lattice points boils down to simple coordinate- wise rounding procedure.
LOWER BOUNDS
We next show matching lower bounds on the communication required for MEANESTIMATION and VARIANCEREDUCTOON (from any source) to output an estimate of sufficient accuracy, via an information- thhorrttic argument, and therefore apply to almost any model of communication. Our proofs essentially argue that, if machine receives only a small amount of bits during the course of an algorithm, it has only a small mumber of possible (expected) outputs. We can therefore find instances such that our desired output (μ or V) is far from any of these possible outputs. This argument is complicated, however, by the probabilistic nature of outputs (and, in the case of the VARIANGKREDUUCTIOO problem, inputs).
These results bound the number of bits a machine must receive
Theorem 6. For any MEANESTIMATION algorithm in which any machine receives most b bits in expectation,
E [ISS [=] = 122222 #/2
To achieve an output variance of O( we that machines must receive Q(d log q) bits in expectation, matching the upper bound of Theorem 2 Similarly, we have the following tight bounds for VARIANCEREDUCTION
Theorem 7. For any VARIANCEREDUCTION algorithm in which all machines receive (strictly) most bils,
E EST v Q(o2n2-
This bound matches Theorem since to reduce the variance expression to o (and, in fact, even to O(a²), i.., to achieve any reduction of output variance compared to input variance), we require = ((dlog) bits.
Theorem 8. For any VARIANCEREDUCTTION algorithm in which any machine receives at most b bits in expectation,
EST VI = 22(022
Here we match the leading terms of Theorem to reduce variance to O(e"), we require ((dlogg) bits in expectation. Note that it is well known (and implied by e.g. Braverman el. al. (2016)) that output variance cannot. be reduced below o(²) even with unlimited commumcation, so Theorem implies that the full variance expression in Theorem is tight.

---

Published as a conference paper at ICLR 2021
4 EXPERIMENTAL VALIDATION
We investigate three distinct applications for our scheme: compressing gradients and models in variants of data-paral paralle SGD, and distributed power iteration for eigenvalue computa- tion (Suresh et al. 2017). We implement the practical version of our algorithm (using the cubic latlice), which lor simplicity we call RLQSGD (or LQSGD for the version without Hadamard rotation). The implemented variant ensures optimal variance, up to a log d fac- tor (Theorem 5). We compare against QSGD (Alistarh et al.) 2017), the Hadamard- based scheme of Suresh et al. (2017). , as well as uncompressed baselines.
Example 1: Compressing Gradients. We first apply compression to a parallel solver for least-squares regression, which is given as input matrix A, partitioned among the nodes; and a target vector b, with the goal of finding w" = argmin |Aww - b b12. In this example, we generate w² E Rd and entries of A E RSxd by sampling from NN 1), and we set b = Aw". Note that the input data (and gradients) are thus naturally normalized. We then run distributed gradient descent with our quantization scheme, using 3 bits per coordinate for all methods, and examine the characteristics of the gradients sent, as well as the convergence and variance of the overall process. Figure [ (left) shows the gradient norms and distances for the case of two nodes executing gradient descent for d = 100 and 8K samples, while the center and right panels show the variance of the gradient estimate for each mot and convergence, respectively.
Regression norms: S 8192, a = 100, batch size 4036
Regressice Varience
6192. d= 100, Ir 0.ft batch mn 4096, glevel B
Regression
= 92, = 2. m 180, hatch sirw 4096
10-211
50
2001 Jokc)
mill
25-
20-
12
33-
12//200
Figure 1: Gradient quantization results for the regression example.
Figure (left) shows that, even in this simple normalized example, the distance between the two gradients throughout training is much smaller than the norm of the gradients them- selves. Figure [ (center) shows that both variants of our scheme (RLQSGD and LQSGD, with and without rotation) have significantly lower variance relative to Hadamard and stan- dard QSGD, and in fact are the only schemes to get below input variance in this setting. Figure 1 (right) shows that this leads to better convergence using our method. The exper- imental report in the full version of this paper contains experiments on other datasets, and node counts, as well as a larger-scale application of our scheme to train neural works... This application shows that our scheme matches or slightly improves the performance of specialized gradient compression schemes, at the same bit budget.
Local SGD Sonvergence: 8192. 100, 0.1, batch 4096, 6, rep 10
Local SGD quantization error: 8192, 100, 0.1, batch 4096,
1L0500 1
RLOSSE (xss)
0500
0530
-10-
3
-10
35-
12.
12.3
15.0
13.3
Ieeition
Figure 2: Local SGD: convergence for different quantizers (left) and quantization error (right).
8

---

Published as a conference paper at ICLR 2021
Example 2: Local SGD. A related example is that of compressing models in Lo- calSGD (Stich 2018), where each node lakes several SGD steps on its local model, followed by global model averaging step, among all nodes. (Similar algorithums are popular in Feder- ated Learning (Kairouz el al. 2019).) We use RLQSGD to quantize the models transmitted by each node as part of the averaging: to avoid artificially improving our performance, we compress the model difference A; between averaging steps, at each node i. RQSGD is a good fit. since neither the models nor the A; are zero-centered. We consider the same setup as for the previous example, averaging every 10 local SGD iterations. We illustrate the con- vergence behavior and the quantization error in Figure 2 which shows better convergence and higher accuracy for antice--ased quantization.
Example 3: Distributed Power Iteration. The power iteration method estimates the principal eigenvector of an input matrix X, whose rows are partitioned across machines, to form input matrices X; at the nodes. Each row of the input matrix X is generated from a multivariate gaussian with first two cigenvalues large and comparable. In each itcration, each machine updates their estimate relative to its input matrix as u, =x >xxx X,æ, and nodes average these estimates. We apply 8-bit quantization following Suresh et al.] (2017). Notice that our method is a good candidate here since these estimates clearly need not be gero-centered, a fact that is evident in Figure 3 (left). Figure
communicate these vectors U;
3 (center) shows convergence under different quantization schemes, while Figure 3 (right) Shows that our method provides significantly lower quanlization error across iterationn.
iteration Norms
Power Peration Convergen.e
Power tteratton Quantization Error Mahhorrraaaaay
-15
-23-
US500 2000
-30
24
10
20
33
20
45
15
Figure 3: Input norms (left), convergence (center) and quantization error (right) when executing distributed power iteration on parallel workers.
Overall, the results suggest that our method can leverage its support of arbitrary centering to provide consistent improvements in these three different settings.
5 CONCLUSIONS
We have argued in this work that for the problems of distributed mean estimation and variance reduction, one should measure the output variance in terms of the input variance, rather than the input norm as used by previous works. Through this change in perspective, we have shown optimal algorithms, and matching lower bounds, for both problems, inde- pendently of the norms of the input vectors. This improves over the theoretical guarantees provided by previous work whenever the imputs are not known to be concentrated around the origin. Our experiments suggest that this also brings about improvements in terms of practical performance. In future work, we plan to explore practical applications for variants of our schemes, for instance in the context of federated or decentralized distributed learning.
ACKNOWLEDGMENTS
Peter Davies is supported by the European Union's Horizon 2020 research and innovation programine under the Marie Skdodowska--urre grant agreement No. 754411. This project has also received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement No. 805223 ScaleMT.).
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Martin Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large-scale machine learning. 12th { {USENLX] Symposium on Operating Systems Design and Implementation. (LOSDI) 16), pp. 265 283, 2016.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradi- ent. descent. In Proceedings of the 2017 Conference on Empirical Methods in Nul-
wral Language Processing, pp. 440-445, Copenhagen, Denmark, September 2017. As- sociation for Computational Linguistics. doi: 10.18638/v1/D17-1000 //www.aclweb. aclweb. org/ hagg/annthllogy/D7-1044
URL https:
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Commmnicalionn-lllcieett sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709 1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, pp. 5973-5983, 2018.
Tal Ben-Nun and Torsten Hoefler. Demystifying parallel and distributed deep learning: An in-depth concurrency analysis. ACM Computing Surveys (CSUR), 52(4): 43, 2019.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT pp. 177-186. Springer, 2010.
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff. Commu- nication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the 48th Annual ACM sympossum on Theory of Computing (STOC 2016), pp. 1011-1020, 2016.
Nikoli Dryden, Tim Moon, Sam Ade Jacobs, and Brian Van Essen, Communication quan- tization for data-parallel training of deep neural networks. In 2016 2nd Workshop on Machine Learning in HPC Environments (MLHPC), pp. 1 8. IEEE, 2016.
Venkata Gandikota, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector quantized stochastic gradient descent. arXiv preprint arXiv:1911.070 2019.
Jerry D. Gibson and Khalid Sayood. Lattice quantization. In Advances in Electronics and Électron Physics, volume 72, pp. 259 330. Academic Press, 1988. doi: hitps:
//doi.org/ watrrgg/1.111////1 (506000055000)))))6)))
Emilien Joly, Gábor Lugosi, Roberto Imbuzeiro Oliveira, et al. On the estimation of the mcan of a random vector. Electronic Journal of Statistics, 11(1):440 451, 2017.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cum- mings, et al. Advances and open problems in federated learning. arXiv preprint (rXto:1912.04977 2019.
Frederik Künstner. Fully quantized distributed gradient descent. http://infoscience. 2017. URL htttp://infosciencee epfl ch/ ch/recordd224549
Jakub Koncčný and Peter Richtárik. Randomized distributed mcan estimation: Accuracy vs. communication. Frontiers in Applied Mathematies and Statistics, 4:62, 2018. ISSN 2297- 4687. doi: 10.3389 fams.2201 2018.0006.. $389/fams
URL
Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decen- tralized SGD. In Proc. International Conference on Machine Learning (ICML), 2020.
Prathamesh Mayekar and Himanshu Tyagi. Ratq: A universal fixed-length quantizer for stochastic optimization. In Proceedings of the 29rd Internalional Conference on Arlificial Intelligence and Statistics (AISTATS), 2020.
10

---

Published as a conference paper at ICLR 2021
Hermann Minkowski. Gesammelte Abhandlungen. Teubner, 1911.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09300 2019.
Ali HamezanniKebrraa Fartash Faghri, and Daniel Roy. Nuqsgd: Improved commu- nication efficiency for data-paralle sgd via nonuniform quantization. arXiv preprint arXiv: 06077, 2019.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and application to data-parallel distributed training of speech dnns. In Interspeech 2014, September 2014.
Sebastian U Stich. Local sgd converges fast and communicates little. arXic:1805. 1805.097777 2018.
arXiv preprint
Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, pp. 4447 4458, 2018.
Ananda Theertha Suresh, Felix X Yu, Sanjiv Kumar, and H Brendan McMahan. Distributed mean estimation with limited communication. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3329 3337, 2017.
John N Tsitsiklis and Zhi-Quan Luo. Communication complexity convex optimization. Journal of Complexity, 3(3):231-245) 1987.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication-effcieene learning via atomic sparsification. In Advances in Neural Information Processing Systems, pp. 9850 9861, 2018.
Jiançiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for eonmmicatioon-efeeient distributed optimization. In Advances in Neural Information Processing Systems, pp. 1299 1309, 2018.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Proceedings of the 31st International Conference Neural Information Processing Sys- tems, NIPS'17, pp. 1508 1518, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
11


Reviews:
[{"review_id": "T-b-dTEcdmv", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers distributed mean estimation in two variations (mean estimation and variance reduction), applicable for instance in distributed learning where several machines needs to figure out the mean of their locally computed gradients.\n\nThe paper measures the quality of an estimator in terms of the input variance, where earlier work has implicitly assumed that the input across the machines had mean zero, and instead measured quality in terms of the inputs\nIn that sense the approach takes in this paper generalizes previous work. \n\nThe authors provide matching upper and lower bounds for the the two problems considered, as well as a practical implementation of the general form of algorithms presented. Finally, experiments back up the quality of the approach considered.\n\nPros:\n- I think the definition of the problems is natural and clean and the right one to consider (instead of assuming zero centered inputs).\n- The approach makes application of these algorithms much simpler as the zero mean assumption is removed and does not need to be handled separately\n- The general latticed based algorithms are natural and very reasonable.\n- The efficient algorithm instantiation of the general approach is nice.\n- It is great that the authors provide matching upper and lower bounds and in general the works seems very thorough.\n- The experiments show the applicability of the general approach.\n\nCons:\n- The actual algorithm used does not match the optimal bounds given.\n- Given the nature of the problem the constants may be relevant instead of using O notation in particular in the actual algorithm presented and used in experiments.\n\nThe cons i have listed i think are all small and overall i think this is a good paper as it provides a clean practically applicable version of the problem, the bounds shown are tight and an actual new algorithm is provided and shown to have good practical qualities.\n\nQuestion.\nDefinition 9, the packing radius. Maybe i misunderstand. Is it supposed to be the smallest r such that  two balls of radius r centered around any two different lattices points do not intersect? Because that is not what i read from the definition, but that is used in the proofs.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "PQduCKMT62Q", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper studies the problem of mean estimation of n vectors in R^d in a distributed setting. There are n machines. Each has one data point, a vector x_v. The goal is to compute the mean of x_v’s for v = 1, …, n with as few bits of communication as possible. \nTheir main contribution is using a new quantization method by exploiting the structure of Lattices. The idea is that each machine randomly assigns its point to a nearby lattice point. Then, the lattice point can be expressed by a few bits. While two points might be assigned to the same bit strings (since the lattice has infinitely many points), the hope is that these points are far apart from each other.\nFurthermore, we need to ensure that other machines could decode the bit string and obtain the same lattice point again and use this point to compute the average. Thus, another machine would interpret the bit string as a close-by lattice point. Note that since we assume some guarantees that all the x_v's are close to each, it suffices that a machine selects the closest lattice point that its description would match the bit string. \nExperimental evaluation is also provided.\n\nOverall evaluation: The authors consider an essential problem and use an interesting idea to solve it. Adding more discussion and literature review might help improve the paper. The writeup could be improved as well.\n\nMajor comments:\n- It would be beneficial if the authors discuss and compare the following straightforward approach: We can use a previously known algorithm and allow the machines to obtain a potentially inaccurate estimate of the mean, say \\hat \\mu. Then, we can run the algorithm again. This time vectors being x_v - \\hat \\mu. In this step, we bring down the points closer to the center. Thus, the accuracy increases over time. We can repeat this process several times until we achieve the desired accuracy.\n\n- It might be worth looking at a series of papers that studied the mean estimation of random vectors in a non-distributed setting. They mainly focus on the tail behavior of the estimate. They use different estimates other than average, such as the median of means. See “On the estimation of the mean of a random vector” and more recent papers that cited this one.\n\nMinor comments:\n- It is unclear from the main text which convex hull is picked. Maybe it worth discussing some high-level explanations in the main text as well.  \n- Bottom of page 4: Using Chebyshev’s inequality would only guarantee that a constant fraction of points is within distance O(\\sigma \\sqrt{n}).\n- Abstract, Line 3: where \\mu is defined, “\\n” is missing.\n- Page 2, last paragraph: “thanto” -> other than the\n- Page 7, Line 1: O(\\sigma^2) -> Shouldn’t be O(\\sigma^2/n)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "My5vf08l9U5", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the distributed mean estimation problem where $N$ machines (each holding 1 value $x_u$) wish to compute the mean of all $N$ values.\nAlong with values $x_u$, each machine receives a common value $y$. This value $y$ upper-bounds $\\|x_u - x_v\\|$ over all machines $v$. The parameter $y^2$ is called the input variance.\nThe authors propose a lattice-based algorithm whose quantization parameter allows a trade-off between numbers of bits needed to be communicated and the output variance of the estimated mean. One crucial contribution of the paper is that it provides guarantees with respect to input variance instead of input norm (which can be large if the inputs do not have 0 mean).\n\n\nThe paper is well-written. It has a clear description of the problem and provides a natural motivation. It also gives a great overview of prior work. The main idea of the algorithm is also explained in a clear way.\n\nThis work studies a basic and important problem in distributed computation. It combines and proposes several interesting ideas. I especially like the idea of lattice-based quantization and using local information, i.e., $x_v$, together with y to perform decoding.\n\nThe paper says:\n-- \"By choosing the leader randomly we can obtain tight bounds in expectation on the number of communication bits used per machine, and by using a more balanced communication structure such as a binary tree we can extend these bounds in expectation to hold with certainty.\"\nAlthough not very crucial for this work, one should note here that using a binary tree structure would increase the number of rounds (or the communication time) by a $\\log n$ factor until the final result is obtained.\n\nAlgorithms 3 and 4 perform communication setup, i.e., electing a leader or making a binary-tree like communication network. What is the communication cost of these? Is it accounted for anywhere?\n\n\nPage 17, Lemma 20:\nLemma 20 implies that there EXISTS a good coloring. But why is it easy to obtain one for us to use in Algorithm 5?\n\n--- Experiments ---\nThe fonts in plots are too small.\nThe experiments are performed only for $n=2$. It seems to be a very limiting setup. It would be nice to show experiments for larger $n$. Given that this is mainly a theoretical work, having such experiments is not a major downside, but they are also not very expressive.\nAmong Figures 1, 2 and 3, in only one plot the x-axis starts from 10, but in the rest from 0. Would be nice to be consistent.\n\n\n\n--- Other comments ---\n\nPage 1, Line 3: Should $\\mu = \\sum_v x_v$ be $\\mu = 1/n \\cdot \\sum_v x_v$?\n\nPage 2: \"thanto the origin\" -> \"than to the origin\"\n\nPage 4, Line 5 of 2nd paragraph of Section 2.1: Is there a typo in \"By choosing an appropriate of lattices\"?\n\nPage 5, first line: Would be nice to emphasize that this is a probabilistic process as $z$ is actually sampled from the linear representation of $x_u$. \n\nPage 5, last line of statement of Theorem 1:\nShould $\\| z - x_u \\| = O(\\varepsilon)$ be $\\| z - x_v \\| = O(\\varepsilon)$?\n\nPage 12, 3rd line of 2nd paragraph of section A.1: Should $c_i(\\lambda) = \\alpha_i mod q$ be $(c_q(\\lambda))_i = \\alpha_i mod q$?\n\nPage 12, 4th and 5th lines of 2nd paragraph of section A.1: $c(\\lambda)$ should be $c_q(\\lambda)$?\n\nAppendix F:\nThere is a sentence saying:\n-- \"In this section we show an extension to the quantization scheme (and thereby also Algorithm 3) allowing us to use a sublinear (in d)\"\nBut in Theorem 27, the bound is O(d log(1+q)). I do not understand why this is sublinear in d. Why does it make sense to make q=o(1)? Shouldn't q be at least a constant?", "extra_scores": {}, "extra_text": {}}, {"review_id": "JSvCgGlsPzS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers a particular setting of distributed mean estimation problem, where each party has a vector of potentially large $l_2$ norm, yet this vectors are fairly close to each other. The goal is to communicate as few bits as possible and estimate the mean of the vectors. Previous approaches had the dependence on the size of the ball containing all the vectors, which gives bad bounds if vectors are long (but close to each other).\n\nThe idea is to decompose each vectors into a convex hull of points in some lattice, then probabilistically round to one of these points, hash lattice points down to a short string and communicate this string. This allows to recover the points we rounded to for each party and thus estimate the mean.\n\nIn order for the communication to be efficient, the cover radius and packing radius should be within $O(1)$ from each other. For $\\ell_2$ norm, this is achievable for random lattices, however such lattices are computationally intractable. The authors notice that we can reduce the original mean estimation problem to the $\\ell_\\infty$ case (incurring the logarithmic loss in the accuracy) and then simply use the cubic lattice.\n\nOverall, I think the result is fairly interesting. None of the techniques are amazingly new (lattice quantization was used before in various context, e.g., locality-sensitive hashing, quantization + hashing down to a short string is a fairly standard idea as well, reduction from $\\ell_2$ to $\\ell_\\infty$ for mean estimation was also used before as well, for, e.g., statistical queries), but I like the clean end result.\n\nOne particular request I have is to describe the computationally simple algorithm via the reduction to $\\ell_\\infty$ directly, not using lattices, since it's much simpler this way (it would be random rotation followed by rounding and hashing).", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new algorithm for distributed multivariate mean estimation. This method performs significantly better than previous approaches when the input vectors have large norm but are relatively close to each other. The approach relies on lattices and randomized rounding. The approach is evaluated experimentally as well. Overall, there is consensus among the reviewers that this work solves a clean problem using non-trivial ideas. I recommend accepting the paper.
Decision: Accept (Poster)