Lattice Representation Learning
Authors: Luis A Lastras
Venue:  (2020)
Keywords: lattices
representation learning
coding theory
lossy source coding
information theory

Abstract: We introduce the notion of \emph{lattice representation learning}, in which the representation for some object of interest (e.g. a sentence or an image) is a lattice point in an Euclidean space. Our main contribution is a result for replacing an objective function which employs lattice quantization with an objective function in which quantization is absent, thus allowing optimization techniques based on gradient descent to apply; we call the resulting algorithms \emph{dithered stochastic gradient descent} algorithms as they are designed explicitly to allow for an optimization procedure where only local information is employed. We also argue that a technique commonly used in Variational Auto-Encoders (Gaussian priors and Gaussian approximate posteriors) is tightly connected with the idea of lattice representations, as the quantization error in good high dimensional lattices can be modeled as a Gaussian distribution. We use a traditional encoder/decoder architecture to explore the idea of latticed valued representations, and provide experimental evidence of the potential of using lattice representations by modifying the \texttt{OpenNMT-py} generic \texttt{seq2seq} architecture  so that it can implement not only Gaussian dithering of representations, but also the well known straight-through estimator and its application to vector quantization. 


Under review as a conference paper at ICLR 2020
LATTICE REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce the notion of lattice representation learning, in which the representa- tion for some object of interest (e.g. a sentence or an image) is a lattice point in an Euclidean space. Our main contribution result for replacing an objective function which employs lattice quantization with an objective function in which quantization is absent, thus allowing optimization techniques based on gradient descent to apply: we call the resulting algorithms dithered stochastic gradient descent algorithms as they are designed explicitly to allow for an optimization procedure where only local information is employed. We also argue that tech- nique commonly used in Variational Auto-Encode Encoders (Gaussian priors and Gaussian approximate posteriors) is tightly connected with the idea of lattice representations, as the quantization error in good high dimensional lattices can be modeled as a Gaussian distribution. We provide experimental evidence of the potential of using lattice representations by implementing a VAE that employs a rectangular lattice and is trained using our results, and contrasting its performance with that of a Gaussian VAE.
PRELIMINARIES
With few notable exceptions, the majority of the practical research representation learning assumes that the representation of the objects of interest (sentences, images, audio signals, etc.) are vectors of real numbers, as this allows us to use powerful optimization algorithms such as variants of gradient descent in the training of computational networks which encode objects into such representations and then use those representations in downstream tasks. Yet, the idea of representing objects using discrete structures (for example, through categorical variables or through the of quantization of otherwise real valued representations) is rather enticing: sometimes we might inherently believe discrete representations use such representations in settings such as reinforcement learning and planning, where discrete actions are important. A classical result by [Lindsay] (1983) for maximum likelihood learning of mixture models tells us that the optimal mixing distribution can be chosen to be discrete (and in fact, the discrete set need not be larger than the amount of training data); this result implies also that the optimal associated "approximate posterior" (when seen as variational inference problem) in fact can be chosen so that it produces discrete representations. The main difficulty associated with discrete representations is that it is not straightforward to train networks that produce and use them because either there no meaningful sense in which differentiation can be used directly (e.g. in the case of categorical variables), almost everywhere. In spite of these difficulties, notable progress has been made. For example, for categorical variables, Jang et al. (2017), and Maddison et al. (2017) proposed essentially the same idea, under the names of Gumbel -Sofmmx and the Concrete Distribution, respectively. This idea, further improved by Tucker al. (011)). uses a continuous approximation "one-hot" encoded categorical distribution which can be learned by appropriately setting parameter controlling the fidelity of the approximation. For the setting where continuous representation quantized obtain the discrete one, an important development is the idea of straight- -through estimation (Bengio et al. 2013), in which quantization is applied in the "forward" direction, but replaces quantization with the identity operator when performing the "backwards" differentiation step- see also recent work attempting to provide theoretical justification of ttraigh-throuuhh estimation (Yin et al. 2017). Of particular relevance to work is VQ-VAE (van den Oord et al.) 2017) in which general vector quantization used, together with brraihh-thhouug estimation, to train the network and the vector quantizers. In fact, the entirety of this paper be seen as type of VQ-VAE where the vector
be the right way to model objects, or may want to
in the case of quantization, the associated gradient is zero
Jangg

---

Under review as a conference paper at ICLR 2020
Po
Figure 1: Two examples of two dimensional lattices. the left, a cubic lattice with basis vectors bi (0, A), b2 = (A,0). In the right, hexagonal lattice with basis vectors b (0, 2).
by = (V33, 1). Also shown for each lattice is the cell Po. containing the origin. The parameter of the cubic lattice A has been set so that the areas both lattice cells are identical.
quantizers are highly structured instead of being free parameters in network; advantages of introducing structure are that we can bring to bear analytical tools that give insight not only how to train these networks with an equivalent continuous version, but also shed light on how we can approximate the performance of continuous Gaussian VAEs in systematic way.
will see, the
In this article, study the possibility of using lattices for object representations by borrowing from theoretical developments information and coding theory (Zamir et al., (0144), in particular they apply lossy source coding problems (Shannon) 1959). see Figure [ for an example of given of basis vectors for an Euclidean space. Lattices have been long studied information theory as they provide powerful means for building structured codes which are analytically tractable and have good space packing and covering properties, which are useful channel coding and lossy source coding applications, respectively (Zamir et al. (014). We note that it has long been known that machine learning and lossy compression are related to each other; for example, we refer the reader to the classical work on the information bottleneck (Tishby et al.) 1999: Tishby & Zaslavsky 2015 Shwartz-ZZv Tishby 2017: Slonim & Weiss 2002), the connection between maximum likelihood estimation and rate distortion explored by Banerjee et al. (2004), Lastras- Montaño (2019). and implicitly, Rose (998),, Neal & Hinton (1998) and a line of research on autoencoders (Giraldo & Principe 2013)] Alemi et al.) 2018 |Higinn et al. 2017). Our work adds this general line of research by adopting more specific structures in this case, lattices from the information theory field and applying them to machine learning problems.
two lattices. In our article, a lattice is defined as the set of all integral linear mixtures
Our primary contribution will be to provide the necessary theory to train computational networks that employ lattices and dithered quantization, leading class of algorithms which call dithered stochastic gradient descent algorithms. Dithering refers to the act of adding random noise to a quantized signal (c.g. an image or time series) for the purposes of diminishing the effect that quantization has on it. The main reason dithering is important to our problem can be traced to fundamental result in the study of lattices information theory called the "Crypto-Lems Lemo-" (see Zamir& & F Feder (1996), G. D. Forney (2004)) which to our knowledge, had not been used before to optimize, with gradient techniques, computational networks that employ quantization in provably correct way. We will additionally connect the task of lattice representation learning with well known technique in generative modeling using variational autoencoders; specifically, Gaussian approximate posteriors (Kingma& & Welling 2014). In experimental section, will demonstrate how can use our results to train a continuous VAE that can re-interpreted, through our main result, as a discrete VAE that uses finite dimensional lattice.
2

---

Under review as a conference paper at ICLR 2020
2 PROBLEM SETUP
To make our work concrete, we will illustrate in the context of a standard encoder/decoder architecture; for a given object d E D (where D is the space of all possible objects), it's representation is produced using an encoder:
e(d)
which is then decoded using decoder:
g(e(d)).
We pause remark that there is subtle difference between the way in which the information theory and machine learning communities use the words "encoder" and "decoder"; the reader needs to be aware of this difference as not get lost in this article. In information theory, an encoder/decoder is almost always a means to represent and retrieve information digitally, in particular, there is a significant emphasis the efficiency of such representations. In machine learning, encoder's output is generally thought of as a continuous vector (of course, as we stated earlier, there are notable exceptions to this); the fact that such continuous vector is represented digitally (in the form of a computer representation of a floating point number) is in a sense an afterthought. Significantly more important in machine learning is the capability of learning parameters for encoder and decoder through training examples, in which case the ussumption of continuity, and more generally, differentiability much more important.
Our work lies in the middle of the two fields. We are interested in a machine learning application, but first class metric to be
want to emphasize the representation cost for the objects being encoded optimized for. In our work, the representations are discrete, this is for any d E DD e(d) belongs to discrete space, which we denote as X. To each element æ E we assign a probability p(x), so that we can talk about a code for the representation space X. In this setting, a code is mechanism for mapping x E X' to ((x) bits (where 1(x) stands for the code bit length) so that x can be recovered, without loss, from the code for of length ((x). It is well known (Cover & Thomas 2006 that for any given code one can construct a probability distribution using the equation p(z)
(xx),
is also known that for a given distribution {p(x)), ), the ideal choice for 7(x) (in units of bits) is log, p(x), in the sense of minimizing the number of expected bits under the assumption that the are being generated with a distribution {x(x)). J. It is also known that such ideal code length in general can only be achieved with block codes which compress multiple elements of X' simultaneously. In our work, we will be indifferent to this we will simply use l(x) = log p(z) for the code length; in fact for our theoretical development we will be using the unit of nats (natural logarithms) as more convenient.
Assume that D a random quantity uniformly distributed over the training data {d1,-.. d. Then the average representation cost for the training data is
EEp log Ple(D))
This is one of the metrics in our work. The other metric is free to be specified by the designer of the architecture. Typically, this will be of the form
ED (((D.g(e(D))
where is some loss function. This covers both unsupervised and supervised settings; in the latter, we assume that the loss function also includes the label for D. It also includes variational autoencoders when they are trained using the Evidence Lower Bound (ELBO).
One way to create discrete representations e(D) is to quantize otherwise continuous representation eg:
e(D) = K (D))
where K denotes a quantization operation; for example, K could use the uniform quantizer with spacing A applied to every one of the m dimensions. The encoder e(), the decoder g() and the representation code - -logp( p() all participate in the end-to-end objective function
Ep ((D((())(((ee( + XED log P(K(ee(D)))
(3)
3

---

Under review as a conference paper at ICLR 2020
where À 0 is a parameter that controls the importance of the representation cost for the overall optimization process.
In nutshell, the problem to be solved is to find theoretically sound basis for the design of good quantizers K that can be trained in an end-to-end computational network. As stated earlier, this can be seen as attempt to bring additional mathematical rigor the VQ-VAE concept.
DITHERED STOCHASTIC GRADIENT DESCENT
3.1 MATHEMATICAL PRELIMINARIES
The principles behind the use of lattices in information theory can be found in the excellent book of Zamir et al. (2014) We borrow from this exposition in here in order to make this work self contained.
Let .1. bn be basis for RR", this is, linearly independent column vectors in R and define B to be the matrix obtained using these basis vectors as its columns: B = [b [b/lb2] [bm]. The lattice A(B) defined as the set of all integral linear combinations of the {61, b:
(
(B 1:Bi::1: i::e Zm)
where Z = -2, -,,0,,,,,,2, jTm When clear from the context, we will use refer to lattice. We define (A) to be the set of all points in Ih" whose closest lattice point is the origin.
Given x E R", we define (A(x) to be the operator (the "quantizer") that takes æ and maps the closest element of the lattice A:
KA = arg min || -pllz
PEA
One of the main reasons we are interested in lattices is because of mathematical tool that can be
used in their analysis, which in information theory is colloquially referred to as the "Crypto-Lemma"
(Zamir & Feder 1996). (G. D. Forney 2004):
Lemma (Crypto-Lemma), For given m dimensional lattice A, let U be uniformly distributed over Po(A). For any E Rm", the distribution of the random vector K Kx(x + U) - U is identical to the distribution of U.
The Crypto-Lemma will give the main mechanism for training computational network using gradient descent algorithms and using such network (during inference) with an explicit quantization step, with firm theoretical guarantee of equivalence.
A few additional mathematical preliminaries are needed. When taking expectations we will explicitly state the probability law being used in the expectation by placing random quantity (most of the time, random vector) as subindex of the expectation. If two random vectors A, B are independent, we will write A IL B. If these random vectors are independent conditional on third random vector C, we will write (A L. B|C).. We will use an upper case P to denote probability measure, this is, function that assigns a probability to an event passed as argument. We will use the notation Pa(a) as summary form of P([A al): ; sometimes will use random vector example, E log (A) can be interpreted as the average cost, in nats, of using a code designed for Å on the random vector A, which is drawn using (generally) different probability law. We will use the notation fA to denote density of a continuous random vector A. We will use the notation PAIB and fAlB to denote conditional versions of the objects described above. In slight overload of notation, recall we use f and e, to denote encoders; the correct usage should be clear from context. Pi and Pg with respect to P₂) for any event A such that (2( = 0 then we have P1 (A) = 0.
argument, thus, for
probability measures, say that P1 < Pg (in words, P1 is absolutely continuous
3.2 THE MAIN RESULT
Our main contribution will be centered on the following new result:
Theorem (representation cost for dithered SGD). Let be any lattice. Let X be a random I vector distributed according to Px, and X be a random R vector distributed according to P where we assume that Px &. Px- Assume U uniformly distributed over Pa. and assume that
4

---

Under review as a conference paper at ICLR 2020
U 11 X and U 11 X. Define
7 = Ka(X +0)
(5)
2 = KA(X +U)
(6)
Then
1
(v(U) log fx-u(X U)
Exu log P220(Z())
= Ex,U
The proof of this result is based on a dual application of the Crypto-Lenme Lemtm, and can be found in the Appendix. In the application of result, Pxx will be associated with the empirical statistics of the encoding of training data (prior to quantization), and Px will be associated with prior belief on the statistics of the encodings of any data, prior to quantization.
Notice that the right hand side of Equation (7) has no quantization involved. Notice also that the expression in the expectation does not use directly any global statistics about X; instead relies on fx-r. which is density that the designer can specify when the statistics of X are specified and when the lattice A is designed. By avoiding the explicit quantization we eliminate the problem resulting from the gradient of quantized signal being zero almost everywhere, and by ensuring that the expression being optimized does not directly depend global statistics about X, ensure that stochastic gradient descent is feasible, since requires that you update parameters based on gradients computed small batches of training data. For these reasons, shall call the machine learning algorithms that one derives from Theorem
D dithered stochastic gradient descent algorithms.
Now examine the left hand side of Equation 7 and notice that it does involve explicitly quantization: in fact, Z will become the discrete lattice representation of our work. Notice the conditioning in P2 P2 on the dither value U. This means that the discrete representation not only depends on the dither U, but also being encoded using a code that depends U as well. Notice also that log P 221 may not be the very best code one could be using which log P2Iu. in fact
Ex,U
log
= ExxU log (ZIU)
+ DKL (21210)
where the former is the "true" best possible representation cost (for given encoder) and the latter term (a conditional KL. divergence which is known to be nonnegative) denotes the excess cost. Thus the representation cost may not be, in certain sense, "optimum"" which is what we pay to make stochastic gradient descent feasible by avoiding having to compute global statistics at every step of the optimization. Having said this, our anecdotal experience that this not a significant problem one allows the parameters of the encoder to also be trained, then the encoder "adapts" so to produce representations that approximate the prior that we have set.
A reader knowledgable in the literature of lattices in lossy compression theory may be wondering what is the connection between Theorem and the information theoretic result linking entropy coded dithered quantization and mutual information (Zamir & Feder 1996). The answer is that Theorem [ generalizes this result to a setting where we aren't 't necessarily using the optimum code, which happens to be particularly useful in stochastic gradient descent algorithms.
We now construct the system that we intend to study. We refer the reader to Figure 2 where we illustrate an encoder/decoder architecture coupled a loss function. In the left hand side, have network that employs pre/post dithered quantization of a representation quantized using a lattice A; in the right, there subtractive dithering but no quantization.
Following Figure 2 define
X x= (D)
With this definition, we can see that in the left hand side of Figure the quantized representation Z matches the definition in Equation (5) of Theorem [
2 KA(X + +U)
5

---

Under review as a conference paper at ICLR 2020
U
U
D
c
A
X
Z
D
(0) log fx-2
Ec
X
log Pa u ((I
((Dlg(-))
((Dlg(-))
Figure 2: Pre/post dithered quantization the context of lattice representation learning. The system in the left is used during inference time, the one in the right during training time.
Now reference the optimization objective in Equation 3 note that one the things we need to do is to define a code that will be used to encode Z. For this purpose, we will use code constructed using a distribution P P22 The way we will construct this conditional distribution is also given by the equations Theorem | In particular, the designer will be free to specify any distribution Px their choice, and then construct the random vectors X, U that they are independent random vectors distributed according to Px and Pv, respectively. Next, as in Equation (6) we define
2 KA + U)
The distribution Pzi0 is the one associated with this definition. Encoding Z, the lattice representation of D, using the code implied by Pziu incurs on the cost
log
PAIU (ZU)
Continuing our analysis of the optimization objective in Equation (3. the designer specified loss function value is
(D,
so that the total objective function is transformed
I(D. gZ U)) Alog
P2 (21U)
The difficulty in optimizing this objective function is that Z is the result of quantization operation; this affects both terms. To deal with the term in the left, we observe that Lemma] implies that
Px.z-u = Px.x-u
Now observe that (Z U DJX) and (x U DJX); and as consequence PD,.- PD.x-U
as well. This means that
ED -(z.((Z)))) ED.x-U (Z E ED, ((()),((e
This demonstrates how we get rid of the quantization by replacing it with subtractive dithering for the first term in 8 For the second term (the representation cost), we use Theorem to obtain
1
(U) EDU log (X-
ED.U
log
(Z
so that the new optimization objective is now
(U
EDJu ((DD.g(e.D)) U)) AED
log fx (f
(9)
As indicated earlier, stochastic gradient descent is possible because fx-u does not use any global information about the training data D. The way we propose this objective function be optimized is sim- ilar the optimization algorithms used in Variational Autoencoders (the called "re- pe-parametrization trick"): :) in particular, we propose to sample for every D, one dither and then performing gradient descent regarding the sampled (/ regarded constant in the computational network.

---

Under review as a conference paper at ICLR 2020
3.3 THE CONNECTION TO VARIATIONAL AUTOENCODERS
Assume that the role of the decoder is to output a distribution over the data space D, this is,
g(Z U' Q--IZ
where Q a distribution over D. Assume that that we choose for the loss function
U)) = - log Q(D
In this setting, the loss function is quantifying the likelihood of the data d given the dithered lattice representation Z - U. From information theoretic coding perspective, this likelihood is the cost in bits needed to represent the data d, given Z U. In information theory, randommess shared between the encoder and decoder, and therefore there is cost in transmitting (in practice, pscudo random numbers with shared seed can be used to implement this, for example). Thus to complete the cost needed to represent the data D, need the cost of representing Z, which in our work is given by - log P Zz (Z . As per our earlier development, we can substitute both of these likelihoods instead with ones which do not employ quantization, arriving to
regarded as common
1 log Q(Dee((D - U) + A Alog (U)((
fu(U)
(10)
Those versed in the literature of variational autoencoders, might recognize the famous Evidence Lower BOund (ELBO) (for À = 1) in the expression above. The term in the right-hand side is associated with the KL term (prior to taking expectation). One way
is by noticing that
fu()) = = fu- (eo(D) - (l))(D)) which is the "approximate posterior" and fx-u is the "prior" (which explains why we are giving the designer full control over the distribution of X). The term on the left, the other hand, is associated with the "decoder" in the VAE.
3.3. THE CONNECTION TO GAUSSIAN VAES
A very common practice in VAEs is to model the prior and the approximate posterior as Gaussians. turns out that there is a sense in which the distribution U approximates that of independently identically distributed (i..d.) Gaussian noise. To see this, we need to introduce additional concepts from the theory of lattices.
The volume, second moment and and normalized second moment of the lattice cell are defined
VA vA=Lo -a-Ja du, Po(
1
{
a
[|u|Edu,
G(A)
VA m Po(A)
2-2/m
respectively. The smallest possible second moment for any lattice on dimension is defined as Gmi we shall call any such lattice optimal. The normalized second moment of an m-dimmeniional hyper-sphere is denoted by G It is known that
Gm > G
lim m--00
G
2Te
2re
A classical result in the theory of lattices is that the normalized second moment of an m dimensional optimal lattice converges to the same quantity
lim Gm
(11)
m-+00
2Te
in other words, there exist lattices whose normalized second order moment approaches that of hyper-sphere as the lattice dimension m grows to infinity. Now denote Z to be an m dimensional Gaussian vector with independent entries each with variance equal to o and let Um denote random vector uniformly distributed over Po(A). Then, it is not difficult to show that (Zamir et al. 2014
(u 12)) = log(2neG(A))
(12)
where DKL denotes the KL divergence and consequence, combining (11) and 13)
that
lim (U 12-) 0.
(13)
00
7

---

Under review as a conference paper at ICLR 2020
One way to interpret this colloquially is that the distribution of the dither of a good lattice approx- imates that of a Gaussian as the dimension grows to infinity. This establishes more firmly the connection between variational autoencoders that employ Gaussian approximate posteriors with lattice representations.
Suppose for now that X is chosen also to be i.i.d Gaussian. In light of (13). let us analyze the performance of good high dimensional lattice by assuming U to be also i.i.d. Gaussian with variance x- Then -x-u is the distribution of another i.i.d. Gaussian. Let us assume that the
parameters of X and U are such that X has unit variance then (5) becomes
+ 1 1 (Iea(D) - - -ee((D)-U1 log Q(Dlea(D) U)
1 JU m mlogoo 0
(14)
At this point, the expression identical to one that one might derive from VAE theory. One important point is to note that in VAEs, the approximate posterior can have general parameters that depend on the encoder output complex forms; for example, in the case of Gaussian approximate posterior both the mean and the correlation matrix in the approximate posterior could depend on the encoder output. the case which we use lattice representations, only the mcan of the approximate posterior can have dependencies the encoder output.
The significance of the observation this subsection is that many of the results (with relatively minor modifications) that the VAE community has obtained likely can be re- re-interpreted as results involving (discrete) lattice quantized representations together with pre/post quantized dithering.
The reader may be wondering: what is new? The point of this section is to suggest that very good lattices approximate the hehavior of Gaussian VAEs which are known to be good. To implement practical system, Theorem 1 can be used implement finite lattices. We will show this in the experimental section.
The reader may also be asking: but why even lattices at all? Why use, say, categorical variables and some variant of the Concrete/Gumbel--Sfftn way answer this question is: consider using lattices if you interested theoretically sound basis obtaining Gaussian VAE-like performance using discrete representations.
trick, or use VQ-VAEs directly? One
4 EXPERIMENTAL RESULTS
For our experiments with finite dimensional lattices, we will be using lattice whose basis is diagonal matrix with positive entrics. This is simple variant of a cubic lattice in which the spacing parameter vary per dimension so we will call it the rectangular lattice. To implement training of VAE using this lattice rely Theorem 1. For this, need to specify prior distribution on X. Note that of the key things will need is fx - the density of X U where U is uniformly distributed over the cell of the lattice we are considering here. Therefore, is highly advantageous to choose a distribution for X so that the distribution of X U has simple form.
Our choice for the distribution of X is for each entry of the vector X to be zero mean Laplacian distribution, this is, an origin centered symmetric distribution that decays exponentially on each side. To simplify, assume = 1 and let A > 0 the width of the uniform distribution so that U is uniformly distributed over (-A 2/2). Let b be the parameter for the Laplacian distribution of X, then
fx fx-v(1)= = {
1 - exp (-1/xp-AA222 (exp(-n/b) exp(n/b) [n] < A/2
2 eexp(=1zl/b) - exp(-A/26))
[m] > A/2
In general assume collection of {A:} and {b:} potentially distinct parameters.
8

---

Under review as a conference paper at ICLR 2020
200
Restangular
Gaussian Lattice VAE
180
valiation performance
140
120
100
20 40
60
80
100
120
140
epoch
Figure 3: Comparison of the performance (negative log likelihood nats) of a rectangular lattice VAE, hypothetical high dimensional lattice (in green), approximated using Gaussian VAE where the variance of the approximate posterior not data dependent, and and a Gaussian VAE (in red) where the variance of the Gaussian of the approximate posterior is allowed be data dependent,
We use static MNIST in our experiments. For both the encoder we use three layer network in which the dimensions of the intermediate layer outputs are 784 + 300 + 300 - 40. The first two layers are gated linear networks with no activation function (the only nonlinearity is the multiplicative gating) and the last layer is simple linear network with no gating or activation. For the decoder the dimensions 40 + 300 - 300 with no activation function but the last layer is an ungated linear network with a sigmoid activation function. We use batch size of 100 and Adam with learning rate 5e-4. We keep track of the model with the best validation set performance and if more than 50 epochs pass without being able to improve this performance, we stop the experiment. Then we compute the improved log likelihood estimate by making use of importance sampling with 1000 samples for each test example Burda et al. (2016). To implement this, we adapted the code made available for the results in Tomezak Welling (2018).
784; as before the first two layers are gated linear networks
When training for the finite dimensional lattice, the training objective for an MNIST image is
log (D) U)
log (e U)}
(15)
where Q is the decoder network, e, denotes the encoder network and [] denotes the ith element of vector.
When train two types of Gaussian VAEs. In one case, the approximate posterior variance is not allowed to depend on the original MNIST image; call this the Lattice Gaussian VAE because denotes the performance an ideal lattice VAE. The other setting is a Gaussian VAE where the approximate posterior variance is allowed to depend the data; this simply term Gaussian VAE.

---

Under review as a conference paper at ICLR 2020
Table 1: Comparison of test negative log likelihood using importance sampling (nats)
Rectangular lattice 94.45
Gaussian lattice VAE
Gaussian VAE
89.35
88.85
The results of our experiments can be seen in Figure where we illustrate the negative log likelihood of the validation set as a function of the number of training epochs. As seen, the performance of the rectangular lattice VAE is not as good as that of either of the two Gaussian VAEs, which is expected; as described in this article, simpler lattices won't perform as well as high dimensional good lattices. Notice however that the performance of the rectangular lattice is quite competitive and furthermore, notice that the performance of the two Gaussian VAEs are rather close each other. This is encouraging for lattice based VAEs because it implies that it is in principle possible to get rather close the performance of Gaussian VAE using higher dimensional lattices.
We then evaluated better upper bound on negative log likelihood through the technique of importance sampling (Burda et al.] 2016); the results are in T We see here that the performance of the rectangular lattice VAE remains quite competitive; for example the numbers reported for Gumbel- Softmax for MNIST in Jang et al. (2017) are above 100 nats.
To get closer to the performance of a Gaussian Lattice VAE, what we need to do is to increase the effective lattice dimension; for example we could use the hexagonal lattice or even higher dimensional lattices. Theorem remains the main tool for training such more complex systems; this is left for future work.
5 CONCLUSIONS
The present work is inspired by belief that information theory, and in particular lossy compression theory can be very effective in serving as theoretical foundation for problems in representation learning, including the design and analysis of highly performant practical algorithms. We have introduced lattices as possible way to create discrete representations, and proved fundamental result which allows us to train computational networks that use lattice quantized dithering using an equivalent (in an expected sense) computational network which replaces quantization with dithering, thus allowing gradient descent to apply. This result also allows us to use only local information during the optimization, thus additionally enabling stochastic gradient descent. We also established fundamental connection between the use of good high dimensional lattices and the idea Gaussian dithering, which is common in generative modeling settings such Variational Autoencoders. Finally, we provided initial experimental evidence of the potential of using lattices an VAH setting, where contrasted the performance of a rectangular lattice based VAE and two types of Gaussian VAEs. The bottom line is that if one is interested in getting close to the performance of Gaussian VAE with discrete representations with a good theoretical basis, we suggest the reader consider lattices and to train them using dithered stochastic gradient descent.
REFERENCES
Alexander A. Alemi, Ben Poole. Ian Fischer, Joshua V. Dillon, Rif A. Saurous, and Kevin Murphy. Fixing broken elbo. In Proceedings of the 35th International Conference on Machine Learning. 2018.
Arindam Banerjee, Inderjit Dhillon, Joydeep Ghosh, and Srujana Merugu, An information theoretic analysis of maximum likelihood mixture estimation for exponential families. In Proceedings of the Twenty-first International Conference on Machine Learning, ICML '04, pp. 8-, New York, NY, USA, 2004. ACM. ISBN 1-58113-838-5.
Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville. Estimating propagating gradients through stochastic neurons for conditional computation. CoRR, abs/130s 0oos/1338.344 33322, 2013. URL http://arxiv. wwtp:/wwwwww..g///////oa/// 3432
10

---

Under review as a conference paper at ICLR 2020
Yuri Burda, Roger B. Grosse, and Ruslan Salakhutdinov. Importance Weighted Autoencoders. In The International Conference on Learning Representations (ICLR). 2016.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder decoder for statistical machine translation. In Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing (EMNLP), pp. 1724-1734 Doha, Qatar, October 2014, Association for Computational Linguistics. doi: 10.3115/w1/D14-111 2xtp/aathoooog/D14-112
URL https: www. ac lweb
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecom- munications and Signal Processing). Wiley-Intersciencee, New York, NY, USA, 2006. ISBN 0471241954.
Jr. G. D. Fomny. Shannon meets wiener ii: On mmse estimation in successive decoding schemes. In In Proceedings of 42st Annual Allerton Conference on Communication, Control, and Computing, 2004.
Luis Gonzalo Sánchez Giraldo and José C. Príncipe. Rate-distortion auto-encoders. CoRR, abs/1312.7381, 2013.
7381
I. Higgins, L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Lerchner. Beta- VAE: Learning Basic Visual Concepts with a Constrained Variational Framework. In The International Conference on Learning Representations (ICLR), Toulon. 2017.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparametrization with gumbel-softmax. In 5th International Conference Learning Representations (ICLR 2017.
2017.
D.P. Kingma and M. Welling. Auto-Encoding Variational Bayes. In The International Conference on Learning Representations (ICLR), Banff. 2014.
Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander Rush. OpenNMT: Open- source toolkit for neural machine translation. Proceedings of ACL 2017, System Demonstrations, pp. 67-72, Vancouver, Canada, July 2017. Association for Computational Linguistics. URL https: www. www.aclweb... www.ac...eb..rrg/ammooooooooooo wttp:/annnhoooooo11/111110
Guillaume Klein, Yoon Kim, Yuntian Deng, Vincent Nguyen, Jean Senellart, and Alexander Rush. OpenNMT: Neural machine translation toolkit. Proceedings of the 13th Conference of the Association for Machine Translation in the Americas (Volume 1: Research Papers), pp. 177- 184, Boston, MA, March 2018. Association for Machine Translation in the Americas. URL https: www. ac wew. ogy #1 8-1817
Luis A. Lostras-Montaño. Information theoretic lower bounds on negative log likelihood. In The International Conference Learning Representutions (ICLR), Toulon. 2019.
Bruce G. Lindsay. The geometry of mixture likelihoods: A general theory. Ann. Statist,, 11(1):86-9) 94, 03 1983.
Chris J. Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relax- ation of discrete random variables. In 5th International Conference on Learning Representations (ICLR 2017). 2017.
Radford M. Neal and Geoffrey Hinton. A View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants, pp. 355-368. Springer Netherlands, Dordrecht, 1998.
Kenneth Rose. Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proceedings of the IEEE, (11):2210-2233) November 1998.
C. E. Shannon. Coding theorems for discrete source with fidelity criterion. In IRE Nat. Com. Rec., pp. 142-163. 1959.
Ravid Shwartz- Ziv and Naftali Tishby. Opening the black box of deep n networks via information. CoRR, abs/1703 703.00810 10, 2017. URL http:h//aaww....r//////////0////
networs

---

Under review as a conference paper at ICLR 2020
Noam Slonim and Yair Weiss. Maximum likelihood and the information bottleneck. In Proceedings of the 15th International Conference on Neural Information Processing Systems, NIPS' 02, pP- 351-358, Cambridge, MA, USA, 2002. MIT Press.
Ilya Sutskever, Oriol Vinyals, and Quoc Le. Sequence sequence learning with neural networks. In NIPS, 2014.
N. Tishby, F. Pereira, and W. Bialek. The information bottleneck method. In Proceedings of the 37-th Annual Allerton Conference on Communication, Control and Computing, pp. 368-377. 1999.
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 IEEE Information Theory Workshop. 2015.
Jakub M. Tomezak and Max Welling. VAE with VampPrior. In The 2nnd International Conference on Artificial Intelligence and Statistics. 2018.
George Tucker, Andriy Mnih, Chris Maddison, John Lawson, and Jascha Sohl-Dickstein. Rebar: Low-variance, unbiased gradient estimates for discrete latent variable models. In Advances in Neural Information Processing Systems 30, pp. 2627-2636. Curran Associates, Inc., 2017.
Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu, Neural discrete representation learning. In Advances Neural Information Processing Systems 30, pp. 6306-6315. 2017.
Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley J. Osher, Yingyong Qi, and Jack Xin. Under- standing thhhugh estimator training activation quantized neural nets. The International Conference on Learning Representations (ICLR), Toulon. 2017.
Ram Zamir and Meir Feder. On lattice quantization noise. IEEE Trans. Inform. Theory, 42:1 155-19999 1996.
Ram Zamir, Bobak Nazer, Yuval Kochman, and llai Bistritz. Lattice Coding for Signals and Networks: Structured Coding Approach to Quantization, Modulation and Multiuser Information Theory. Cambridge University Press, 2014. doi: 10.1017/CB00771119905555
A APPENDIX
A.1 PROOF OF THEOREM 1 CORE RESULT ON DITHERED SGD
For reference purposes, we restate the statement the theorem:
Theorem (representation cost for dithered SGD). Let be any lattice. Let X be a random R vector distributed uccording to Px, X be a random 8 vector distributed according to Px. where assume that Px & Px. Assume U is uniformly distributed over Po, and assume that U IL. X
and U 11 X. Define
Z KA(X +U)
(16)
2 KA(X +U)
(17)
Then
log (z = Exxu log fu(U)
Ex.
(18)
fx-e U)
To prove this result, we will rely on this Lemma:
Lemma 2. Let X, U, Z be R. valued random vectors such that (X 11 U U) and X 11 U, with U continuous and Z discrete. Then
(2)x (z)u(
1z-UIx(=- 2//2))
fz-u -w)
12

---

Under review as a conference paper at ICLR 2020
Proof of Lemma 2 We assume in this proof that X is continuous and has a density; the case where X is discrete can be proved similarly. The proof proceeds as follows:
(2(xu(
(a)
(x
P2i0 (z/u)
(xlu
(x)2,
(
fx(x)
(
f U,U (a/2 u, u)
[x(x)
(d)
Ux u)
fx(x)
fx12 u (x)2 uu u)
fx fx(x)fz-u(( u)
( 12-
fz-u(z-00 u)
where (a) follows from Bayes" rule for mixed continuous/diserete variables, (b) follows from the assumption that X I. U. (c) follows from the fact that these two events are identical
= 2,= = u) 12 U = - u, U, U= = u].
Finally, (d) follows from the assumption that (X TL U|Z UU) and (e) follows from the use of Bayes' rule.
Proof of Theorem I. A fundamental fact in probability theory is that and B are random vectors where B nnC) for some function n, then A and / are independent given C. We now use the classical argument employed in the analysis of lattices in quantization, which is that because by definition U E Po(A).
-U) =
-
and therefore KA KA(Ž-U) -U)- (2 -) U. This shows that U can be obtained as function of 2 U.
Therefore (X 11 Ú U) and since by construction & II U. will be able to apply Lemma
13

---

Under review as a conference paper at ICLR 2020
The proof thus proceeds follows:
1
P2
(K (K(X
x)
Exu
log
Εx.
log
P2i0
(2U
P2 P2 (2)
Ex.u
log
Pap (2IU) (2
f2- (Z U
Εx,
log
f2-u - U)
S2-1Ix (Z UIX)
(d)
Éx.2-U
log
(2 U)
log 12-018 (X U
(c)
Exx--U
12-u UU)
f2 - (X - -U(X)
( Ex,
log
82 (x-u((- -U)
fx-U1& (X - -
@
Ex,U
log
fx fx-u(X - U)
Sv(U)
Ex,u
log
fx_u (X U)
where (a) follows from the definition of 2 which implies that for all x and all u,
P2I,, (Ka(z + u)lu, x) = 1,
(b) follows from the definition of Z, (c) follows from an application of Lemma 2 (d) is change of variables which is feasible since X and Z - U are the only random vectors under the expectation, (e) follows from application of the Crypto Lemma, (J) is another change of variables, (g) follows from another application of the Crypto Lemma, but this time applied to the joint distribution of
X, 2 U.
A.2
ADDITIONAL RESULTS ON AN AUTOENCODING SETTING
In this appendix, we describe some results for the autoencoding setting, where the goal not to estimate densities but rather to create representation that describes with high fidelity the original object interest.
In the autoencoding setting are able to make stronger statement than in the VAE example in the main body of the paper about the benefits of using better lattices.
Let J. denote the x identity matrix. The following Lemma describes how the second moment of lattice whose dither "white" controls the quantization error as observed through an arbitrary function:
Lemma 3 (approximation error due to lattice quantization). For given dimension m 2 1, let 17 : Im - R be twice differentiable function. Assume that U is column vector uniformly distributed over the cell PP((A) of a lattice A. and assume that Eu(UUT] = oi m for some o If tr (r(H, + and if o is sufficiently small, then
o (T)
Evin(a + -)]-n(())
2
where H. denotes the Hessian (the matrix of second order derivatives) of
Proof. It is easy to see that if u E Po(A), then -u E Po(A). Due to this property, the first moment of lattice is zero:
Fu [ 0.
14

---

Under review as a conference paper at ICLR 2020
Let Ascaled 1 A be scaled version of A. Define V U, then clearly Ev [VV]] Im- JΛ. Using Taylor series expansion, assuming A is small, 0a
Eply(o + U)] Evlu( [oV)]
n( + Ev
V
H
2
n(x) + o
Σ
H ye, Ev [[A]]] Ev
2
id
n)x) + x
Tr(H,,).
2
Lattices that achieve Gmm have white dithers. This is result by Poltyrev and can be found in (Zamir & Feder 1996):
Lemma 4. For any m 2 1, if lattice that achieves Gm and U is uniformly distributed over PP((A), then ElUUT) is proportional In.
If one keeps constant the volume VA of the lattice cell then by definition,
22/m
2/m G(A) Z o V
2T
We consider two lattices: a lattice spanned by a matrix proportional to Ims and a lattice with a normalized second moment equal to G... From the previous discussion, it is easy see that both lattices have white dithers, and therefore Lemma GemmaBaapplen appplies. We also note that the normalized second moment of lattice spanned by a matrix proportional to Im G1 1/12 Applying Lemmal ttwice. the difference between the two approximations (one for each lattice) can be estimated by
5 [G - G.)) TT, <
Tr (r) = 0.0124 (x))
12
2Te
The above is an absolute estimate. In relative terms, the size the error by using the best lattice with dimension m relative to the size of the eтror incurred by the cubic lattice. This is then given by
G G1
6
0.7
πE
In the above, 1) was a generic function but in our case, we would like to identify it with E. Thus, we can improve the quantization error in the designer's choice of loss function by up to 30% by using better lattice, all at a constant representation cost.
A.2.1 AUTOENCODING EXPERIMENTS
The purpose of our experiments is to draw comparison between two techniques for quantized representation learning. Both techniques will be using stochastic gradient descent, which implies that we need to guarantee that the "backwards" computational network (the one used to compute the gradient of the objective functional with respect to all parameters) needs be associated with meaningful gradient, this is, one that can be used to iteratively improve the loss function.
The first technique is network trained with scalar or vector quantization in the forward direction. Because quantization has zero derivative almost everywhere, it is not "meaningful" in the sense of the paragraph above. Therefore, the backward direction we use straight-throug estimation in order to create fully differentiable backwards computational network (Bengio et al. 2013 van den Oord et al., (2017). The second technique is an estimate of how a very good lattice in high dimensions will perform, using non-data dependent Gaussian dithering to approximate uniform distribution over this lattice.
For the experimental setting, we have chosen seq2seq (Sutskever al. 2014) autoencoder as implemented in OpenNMT-Py (Klein et al., 2017) 2018). This open source package implements generic seq2seq architecture that encodes variety of input types (text, audio, images) into
15

---

Under review as a conference paper at ICLR 2020
300
N-250, M=16384
quantization straight- Shrough
gausssia dithering
250
N-250. M-4096
200
representation
150
N=250, Ms128
100
N=125, M=4
0.2
0.6
0.8
1.4
average word negative log likelihood (bits)
Figure 4: Comparison of the performance of hypothetical high dimensional lattice, approximated using Gaussian dithering, and several quantizers trained using straight-through estimation. The x-axis is the average word negative log likelihood in bits. The y-axis is the representation cost of the quantized representation vector, averaged per word. Lower better for both. All numbers plotted for the test data.
vector valued representation, and then decodes this representation into text. For our experiments, we have chosen a strict autoencoder experiment where we encode into representation and where we expect that exactly the same text be produced by the decoder from this representation.
We modified this open source package (the source code will released) by intercepting the com- munication between the encoder and decoder in order to apply the various quantization techniques that we are proposing to evaluate. function is the average word negative log likelihood at the output of the decoder. We will maintain the same loss function verbatim. In addition, we computed the representation cost of the quantized vector communicated from the encoder to the decoder, normalized also per word basis. There is a tradeoff between these two quantities the higher the allowed representation cost, in principle the obtain.
seq2 seq setup like the one being described here, the loss
better loss function
For the specifics of the architecture, we chose a layer bidirectional GRU (Cho et al. 2014) recurrent neural network for both the encoder and decoder, with each direction having 250 dimensions in its internal state and in the GRU's output vector (so that the total communication pipe between encoder and decoder is 500 dimensions). The OpenNMT py package implements an optional global attention which creates additional communication paths between encoder and decoder. We disabled this, presents additional complications that are important for the purposes of this article. We use Adam with an initial learning rate of le-4, which decays by factor of 0.75 every 50k steps after an initial 100k steps where kept constant. The total number of training steps is 500k. The parameter À which weights the representation cost in the total objective function is slowly annealed from a value close to 0 to its (asymptotic) value of 1.0; the value 0.5 achieved at 100k steps.
When performing quantization and straight-through estimation, the 250 dimensions of each direction of the bi-directional GRU can be quantized in several ways, depending on how we partition the 250 dimensions. One family of such possibilities is use N 250 scalar quantizers each using M levels, for various values of M. Another example we demonstrate N 125 quantizers, each with M = 4 two dimensional code vectors. In any of the experiments, each quantizer is independent of
16

---

Under review as a conference paper at ICLR 2020
the other quantizer, in the sense that its M levels parameters of the model which optimized using gradient descent. Each of the N codes is associated with a code (a distribution over its M levels), which can also be optimized using gradient descent. The average code length obtain as the representations are encoded with this code is the representation cost.
For the experiments using Gaussian dithering, the output of the encoder is first linearly transformed using a linear operator with free parameters, and then it dithered using an uncorrelated zero mean Gaussian with a diagonal correlation matrix that is also set of free parameters. The dithered signal is then passed through another linear operator. The representation cost for Gaussian dithering is computed using techniques from Variational Autoencoders; essence we assume an isotropic unit variance Gaussian as a prior over the representation space and then estimate the KL divergence between the dithered representation conditional on the encoder output and the Gaussian prior.
The specific data that we use for the text autoencoding experiment is a set of over 4 mil- lion english sentences prepared using scripts that are available in Google's NMT tutorial (https:/ / www. coonm//enooffooo /nmtt in particular the wmtl6 lettt16___eeeeee sh script) for a German/English translation system; as this an autoencoding setup, we only use the English sen- tences. For the test data, we use 3003 sentences also typically used in translation experiments for test- ing (newstest2014) This data set was then processed using OpenNMT-PP -py preprocess.. py tool. We only report results for the test data.
The results can be seen in Figure 4 In the lower left hand side we see the tradeoff between the representation cost and the average word negative log likelihood. We see that the projected performance of a good lattice significantly better than the performance of the specific quantizers, trained with straight-through estimation that we tested. The reader may be wondering whether the high dimensional assumption that we make on the gaussian dithering approximation to good lattices implies that the projected performance may be unrealistic; we do not know with certainty this point however we believe that good lattice in 250 dimensions will likely be very well approximated with Gaussian.
17


Reviews:
[{"review_id": "Sklb0fgSqH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "This paper proposes a framework for gradient descent optimization of latent variable models where the latent code lies on a (n-dimensional) lattice. After a brief overview of relevant results in lattice theory, a method (\"Dithered gradient descent\") is proposed to differentiate through lattice quantization by means of an additive \"dither\" noise variable and a lower bound on the total reconstruction+representation loss using a prior distribution. After elaborating on the relationship between their framework and the VAE literature, the authors go on to give an explanation of the link between the covering property of a lattice and the reconstruction loss. Finally, empirical evidence is given for the better compression and reconstruction properties of a sentence autoencoder with lattice latent codes.\n\nOverall, while the idea presented in this paper is interesting (using lattices as discrete latent variables), I don't think that the paper in its current state is up to standards for ICLR.\n\nFirst, there is little motivation for using lattices over other discrete latent variable models in the first place (eg. straight-through estimator with Gumbel softmax or VQ-VAE).\n\nSecond, while I appreciate the efforts that the authors have gone through to make lattice theory accessible to a profane audience, I think that the presentation (particularly in 2.2) could benefit from significant re-ordering as well as more emphasis on the parallel with the VAE literature. A lot of the concepts introduced there have equivalents in VAE lingo (prior, ELBO) and would benefit from being identified as such as they are introduced (and not just in a following sub-section). I also think that presenting Theorem 1 first is confusing, because we are shown the solution before seeing the problem. I think that it would be much more natural to 1. recall the original objective 2. introduce (and motivate) tithering and the $\\hat X$ and then 3. introduce theorem 3 to explain how to get rid of quantization. In terms of global structure the paper is also rather imbalanced with 3 large sections including a monolithic 3 page long introduction. I would advise splitting up as appropriate to give the reader some space to breathe.\n\nThird, and perhaps most importantly, the experimental section is underwhelming. The description of the method used is too sparse and ridden with inaccuracies and vague descriptions. A reader would be hard-pressed to try to reproduce these results from the paper alone. The task itself is rather arbitrary (sentence autoencoding with GRUs), and from what I understand, there is no direct comparison with the relevant literature (eg. Gumbel straight-through or VQ-VAEs). I think that the authors should have at least illustrated the appeal of lattice representation learning on a toy example. Furthermore as stated by the author in the conclusion, the experiments don't even involve actual finite dimension lattices, making most of the paper seem irrelevant in hindsight. Overall this section feels rushed and it is the biggest point against the paper for me. \n\nFinally, the paper is littered with small typos or unfortunate notation collisions which, if individually benign, make parsing this already dense paper harder than needed. Some specific examples are given in the notes at the end of my review.\n\nNotes (in no specific order):\n\n- Second to last paragraph on page 3: \"one may want to have $\\Delta>0$ be very small [...] but that leads to a larger reconstruction cost\". I assume you meant \"representation cost\".\n- $- \\log p$ instead of $\\log \\frac 1 {p}$ to save space\n- Voronoi cells are introduced but never referenced.\n- Subscripted lowercase f is overloaded, use lowercase p or q for densities. This makes some of the formulas in 2.2 particularly annoying to parse.\n- In 2.4 $G_1$ refers to something different than $G_m$ with $m=1$\n- The term \"dither\" is not defined explicitly. The closest I could find is a reference to \"the dither value U.\". Given the prominence of the term in the paper (and in the name of your proposed method) I think this warrants more attention.\n- In the experimental section you justify the use of Gaussian dithering (instead of the uniform dithering used in all the theorems) by \"The justification for using Gaussian dithers is partly contained in the high resolution analysis done in Subsection 2.4.\". However there is no explicit reference to this fact in 2.4 (in fact the words \"gaussian\" or \"normal\" don't even appear in 2.4). The link should be made more explicit somewhere.\n- Some sentences seemingly don't make sense: \"The representation cost for Gaussian dithering using techniques from Variational Autoencoders; in essence we assume an isotropic unit variance Gaussian as a prior over the representation space and then estimate the KL divergence between the dithered representation conditional on the encoder output and the Gaussian prior.\" in the experimental section.\n- Page 3 codelength: references (eg. the shannon paper). In general a lot of the \"It is well-known\" statements in the paper should be accompanied by a reference.\n- Some references don't have a date (Van den Oord in page 9 for instance)\n- the result figure is very hard to read especially on paper. A bit of color as well as larger font/linewidth would go a long way.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xOGMsctH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "\nThe paper discusses discrete representation learning from a lattice perspective, where one performs a \"reparametrization trick\" during training and quantized learning over inference. This is different from other methods such as Gumbel trick in the sense that the quantization is done on lattices and the noise is uniform over primitive cells. The paper discusses some connections with VAEs, showing how one could interpret the VAE objective with \"Gaussian dithering\". While the theory is interesting and seems to be valid, I am not entirely sure how we could use it well in practice (apart from the proposed Gaussian dithering, which is very similar to what we already have with VAE reparametrization trick).\n\n\nQuestions:\n\t- In sec 2.3 an argument is placed for connection with VAEs. It seems that here U is sampled from Gaussian and therefore unbounded and not \"uniform\" within the primitive cell? It's not critical, but I wonder if the this argument could be more interested if better connected to lattices, ie the optimality of \"hyperspheres\" as a lattice representation.\n\n\t- Experimental-wise, I don't see how the proposed training approach is different from a regular VAE setup (maybe that is the point), and I am confused by the procedure in which you would do quantization for the \"hypothetical lattice\" experiments. Does the \"representation cost\" here mean the loss you get with the Gaussians? How do we obtain useful discrete representations in practice?\n\n\t- It seems helpful to have experiments on popular tasks for VAEs like binarized MNIST; this would make it easier to compare with more existing baselines. \n\n\t- It might be nice to restructure the paper, a lot of the paragraphs are very long and a lot of math uses one entire line while being very short (it seems the numbered equations are most useful). Some details can be put in the appendix to make the paper shorter.\n\nTypos: \n\t- introduction \"a line of research of autoencoders\" \\citep format.\n\t- Description for (3) \"first term\" and \"second term\" order?\n\t- Lemma 1: \"a uniformly distributed over\"\n\t- Grammatical errors across the paper; it would be nice to proof read them carefully for camera-ready version.\n\t\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BJgrBWlmqS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "**After rebuttal**\n\nThanks for the work you put into the rebuttal!\n\nI think the paper now reads better and like the new added experiment! However, I remain unconvinced about the practical usefulness of lattice representations especially in light of missing comparison to other algorithms (as mentioned, I am no expert, but [1] or something similar would have been nice). I will thus leave the “weak reject” score unchanged but will not block the acceptance if other reviewers and/or the AC believe the paper should be accepted.\n\n\n**Original review**\n\nThis paper presents a technique for learning of lattice valued embeddings. The authors propose to learn the embeddings by gradient descent which naturally brings about the challenge of how to obtain non-zero gradients when the embedding space is discrete. To resolve this, they apply the “Crypto-Lemma”, a well-known result from information theory, which allows them to obtain meaningful gradients by using certain uniform perturbation of the embeddings. Since the resulting algorithm is hard to implement in high dimensions, the authors eventually replace the uniform noise with a small Gaussian noise. The paper is concluded with an experiment comparing learned and fixed lattice embeddings in terms of the average code length (“representation cost”) on a dataset of English sentences.\n\nI am currently leaning towards recommending rejection of this paper. The two main reasons are: (i) I am missing concrete examples of where application of lattice embeddings is more beneficial than simple continuous (or binary) valued embeddings; (ii) If the main application of this algorithm is supposed to be compression, then I am missing sufficient background section on alternatives to the presented algorithm and comparison to these within the experiments (I am admittedly no expert on the use of ML algorithms for compression, but a simple search reveals, e.g., [1] as a relevant baseline). Finally, since the paper is 10 pages, I am applying a higher standard then I would to an 8 page paper as instructed by the guidelines.\n\n\nMajor comments:\n\n- As alluded above, can you please clarify whether the main application of your algorithm is compression, or whether there are applications in which lattices have interpretative value or some other advantage not related to compression?\n\n- Can you please explain why is there no comparison to other compression algorithms (e.g., [1])?\n\n- Can you please provide more detail on how exactly you obtain the measurements in fig.3? E.g., how have you selected the reported hyper-parameters? Were the same hyper-parameters used for both yours and the straight-through model, or did each model run with its optimal hyper-parameters? Are the reported numbers an average over a larger number of random seeds? etc.\n\n\nMinor comments:\n\n- On p.1, line 5, “of of” -> “of”\n\n- On p.1, wasn’t the phrase “in another line of thinking” supposed to be connected to the following, instead of appended to the preceding sentence?\n\n- On p.3, you say “We are interested in a machine learning application, but want to emphasize the representation cost for the objects being encoded as a first class metric to be optimized for.”\nI am not entirely sure I understand what you want to say here. Standard variational inference (the type that is among else being employed by the cited VAEs) has a well known Minimum Description Length (MDL) interpretation. Can you please clarify why MDL is not “a first class metric to be optimized for”? \n\n- At times I felt like the paper is burdening the reader with unnecessary definitions. For example, why does the reader have to know what a “fundamental Voronoi cell” is when they already know the definition of a “fundamental cell”?\n\n- I like that you are distinguishing between probability distributions and their density/probability mass functions (PMF) as it generally makes reader’s life easier in a paper like this. However, I would have liked if you have consistently stuck with the notation that you introduce (f for densities, p for probability mass functions) instead of using capital P in some places where density/PMF is appropriate (for example, compare the lower case p in eq.3, with the expressions for entropy and cross-entropy on p.5). On a related note, I find the choice of denoting both the encoder and density functions by f somewhat unfortunate.\n\n- In the second display after eq.8, should S be X? \n\n\nReferences:\n\n[1] James Townsend, Tom Bird, David Barber. Practical Lossless Compression with Latent Variables using Bits Back Coding. https://arxiv.org/abs/1901.04866", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a new view of latent variable learning as learning lattice representations.

Overall, the reviewers thought the underlying ideas were interesting, but both the description and the experimentation in the paper were not quite sufficient at this time. I'd encourage the authors to continue on this path and take into account the extensive review feedback in improving the paper!
Decision: Reject