The Effects of Invertibility on the Representational Complexity of Encoders in Variational Autoencoders 
Authors: Divyansh Pareek
Andrej Risteski
Venue: ICLR 2022 Poster (2022)
Keywords: variational autoencoders
encoder
representational complexity
Langevin
invertibility
deep learning theory

Abstract: Training and using modern neural-network based latent-variable generative models (like Variational Autoencoders) often require simultaneously training a generative direction along with an inferential (encoding) direction, which approximates the posterior distribution over the latent variables. Thus, the question arises: how complex does the inferential model need to be, in order to be able to accurately model the posterior distribution of a given generative model?  In this paper, we identify an important property of the generative map impacting the required size of the encoder. We show that if the generative map is ``strongly invertible" (in a sense we suitably formalize), the inferential model need not be much more complex. Conversely, we prove that there exist non-invertible generative maps, for which the encoding direction needs to be exponentially larger (under standard assumptions in computational complexity). Importantly, we do not require the generative model to be layerwise invertible, which a lot of the related literature assumes and isn't satisfied by many architectures used in practice (e.g. convolution and pooling based networks). Thus, we provide theoretical support for the empirical wisdom that learning deep generative models is harder when data lies on a low-dimensional manifold.

Published as a conference paper at ICLR 2022
THE EFFECTS OF INVERTIBILITY ON THE REPRESEN- TATIONAL COMPLEXITY OF ENCODERS IN VAES
Divyansh Pareek
Andrej Risteski
Machine Learning Department
Machine Learning Department
Carnegie Mellon University Pittsurgh, PA, 15213
Carnegie Mellon University
Pittsbrrg,, PA, 15213
dpareekeandrew. cmu cmu. edu
aristeske andrew cmu edu
ABSTRACT
Training and using modern neural-network based fatent-varialle generative models (like Variational Autoencoders) often require simultaneously training a generative direction along with an inferential (encoding) direction, which approximates the posterior distribution over the latent variables. Thus, the question arises: how complex does the inferential model need to be, in order to be able to accurately model the posterior distribution of given generative model? In this paper, we identify an important property of the generative map impacting the required size of the encoder. We show that if the generative map is "strongly invertible" (in a sense we suitably formalize), the inferential model need not be much more complex. Conversely, we prove that there exist non-invertible generative maps, for which the encoding direction needs to be exponentially larger (under standard assumptions computational complexity). Importantly, we do not require the generative model to be layerwise invertible, which lot of the related literature assumes and not satisfied by many architectures used in practice (e.g. convolution and pooling based networks). As non-invertible generator results in distribution supported on a low-dimensional manifold, this provides theoretical support for the empirical wisdom that learning deep generative models is harder when data lies on a sufficiently complex low-dimensional manifold.
INTRODUCTION
Many modern generative models of choice (e.g. Generative Adversarial Networks (Goodfellow
et al. 2014), Variational Autoencoders (Kingma & Welling 2013)) are modeled as non-linear, possibly stochastic transformations of simple latent distribution (e.g. a standard Gaussian). A particularly common task is modeling the inferential (encoder) direction: that is, modeling the posterior distribution on the latents given an observable sample æ. Such task is useful both at train time and test time. At train time, fitting generative models like variational autoencoders via maximum likelihood often relies on variational methods, which require the joint training of generative model (i.e. generator/decoder), as well as inference model (i.e. encoder) which models the posterior distribution of the latent given the observables. At test time, the posterior distribution very often has some practical use, e.g. useful, potentially interpretable feature embeddings for data (Salimans et al. 2016 Berthelot et al. 2018), "intervening" on the latent space to change the sample in some targeted manner (Shen et al. 2020), etc. As such, the question the "complexity" of the inference model (i.e. number of parameters to represent it using neural network-based encoder) as function of the "complexity" of the forward model is of paramount importance. so that training is computationally tractable:
Question: How complex does the inference (encoder) model need to be relative to the complexity of the generative (decoder) model
In this paper we identify an important property of the generative direction governing the complexity of the inference direction for variational autoencoders: bijectivityinwerriiiity of the mean of the generative direction. We prove that when the mean of the generative direction is invertible, the complexity of the inference direction is not much greater than the complexity of the generative

---

Published as a conference paper at ICLR 2022
direction. Conversely, when the mean of the generative direction is not invertible, modulo stan- dard computational complexity conjectures from cryptography, we can exhibit instances where the inference direction has to be much more complex.
On the mathematical level, our techniques involve a neural simulation a Langevin random walk to sample from the posterior of the latent variables and uncover novel connections between Langevin diffusions and (hierarchical) deep latent Gaussians. On the lower bound side, we provide a reduction from the existence of one-way Boolean permutations computational complexity: that is, permuta- tions that are easy to calculate, but hard to invert. We show that the existence of small encoder for non-invertible generators would allow us design an invertor for any Boolean permutation, thus violating the existence a one-way way permutation. This is the first time such ideas have been applied to generative models.
Note that a non-invertible generator results in distribution supported on a lower dimensional manifold. Thus, our results show that learning deep generative models harder when data lies on sufficiently complex low-dimensional manifold. corroborating similarly flavored empirical observations (Dai & Wipf 2019 Arjovsky et al. 2017).
OUR RESULTS
The Variational Autoencoder (VAE) (Kingma & Welling 2013) is one of the most commonly used paradigms in generative models. It's trained by fitting generator which maps latent variables to observables x, denoted by po (z]²),, as well as an encoder which maps the observables to the latent space, denoted by is (z|zr). Here @ and 0 are the encoder parameters and generator parameters respectively. Given n training samples {2(0)p 1 the VAE objective is given by
max 0,0 TI
Σ
E Banga(latin ((
[1oRPO(<"1>)] - KL ([((=))()))<(()))
where p(z) is typically chosen to be a standard Gaussian. This loss can be viewed as a variational relaxation of the maximum likelihood objective, where the encoder qo- in the limit of infinite representational power, is intended to model the posterior distribution (0))
Setup: We will consider setting which the data distribution itself is given by some ground-truth generator G R4 + Rd, and ask how complex (in terms of number of parameters) the encoder needs to be (as a function the number of parameters of G), s.t. it approximates the posterior distribution p(= (x)) of the generator.
We will consider two standard probabilistic models for the generator/encoder respectively.
Definition (Latent Gaussian), A latent Gaussian is the conditional distribution given by stochastic pushforward of Gaussian distribution. That is, for latent variable E RR and observable v E Rd. for a neural network IR -> Rdd and noise parameter 8², we have p(æ|2) = ((G()))BBIA)) and p(z) = (0, Ia.)
In other words, a sample from this distribution can be generated by sampling independently (0, Ia.) and & (0, and outputting x G(z) E. This is standard neural parametrization of a generator with (scaled) identity covariance matrix, a fairly common choice in practical implementations of VAES (Kingma & Welling 2013 Dai & Wipf 2019).
We will also define a probabilistic model which is a composition of latent Gaussians (i.e. consists of multiple stochastic layers), which is also common, particularly when modeling encoders in VAEs, as they can model potentially non-Gaussian posteriors (Burda et al. 2015 Rezende et al. 2014):
Definition 2 (Deep Latent Gaussian). A deep latent Gaussian is the conditional distribution given by sequence of stochastic pushforwards of Gaussian distribution. That is, for observable 2o E R and latent variables {2, E IR J.=,, for neural networks {G; : Rdd-1 - Rd !
and noise parameters (8P) the conditional distribution p(2r.1z0) (z0) is deep latent Gaussian when p(=//==-)== NG (a,)) vi E [L] and p(=0) = A J.,)
In other words, a deep latent Gaussian is distribution, which can be sampled by ancestral sampling, one layer at time. Note that this class of distributions is convenient as choice for encoder
2

---

Published as a conference paper at ICLR 2022
in VAE, since compositions are amenable to the reparametrizzaiion trick of Kingma & Welling
(2013) the randomness for each of the layers can be "presampled" and appropriately transformed (Burda et al.
2013 Rezende et al. 2014). Then, we ask the following:
Question: If VAE generator is modeled as a latent Gaussian (that is, p(æ[2) (G)),, B)),,, s.t. the corresponding G has at most N parameters, and wish to approximate the posterior p(z (r) by a deep latent Gaussian s.t. the total size of the networks in it have at most N' parameters, how large must N' be function of N?
We will work in the setting di = d. = d. and prove a dichotomy based on the invertibil-
ity of G: namely, if G Rd - Rd bijective, and 3 S Aoo. the poste-
rior p(z(z) can be e-approximated in total variation distance by deep latent Gaussian of size N' = ON -poly(d, 1/3, 1/e)). Thus, if the neural network G is invertible, and for a fixed e and small-enough variance term 8 we can approximate the posterior with deep latent Gaussian polynomially larger than G. On the other hand, if G is not bijective, if one-ooy- wwayffunctions exist (a widely believed computational complexity conjecture), we will show there exists VAE generator G CdRdd - Te of size polynomial in d, for which the posterior p(z[2) cannot be approximated in total variation distance for even an inverse polynomial fractiiaaaraaii fraction of inputs x, unless the inferential network
is of size exponential in d.
Remark 1: Note that it is in fact sufficient to investigate only the case where d; = do d. Let us elaborate why:
For Theorem 1 a function G R + Rd can be bijective, Lipschitz and strongly invertible (i.e. satisfies Assumptions 1 and 2) only if di = do. so Theorem (upper bound) would not make any sense unless the dimensions are equal. (Note: there are bijective maps between, say, and I² e.g. fpacc-filling curves, but these cannot be Lipschitz, as Lipschitz maps preserve the Hausdorff dimension, and the Hausdorff dimensions of R and R are 1 and respectively).
Theorem 2 is a lower bound meaning we aim to exhibit an example of hard instance when G is not bijective. Having exhibited hard instance for the di = d, = d case, it is trivially easy to construct hard instance in the theorem where the output dimension is larger- which is the more common setting in practice. To do so, consider a circuit C: [+1) - {+1] 111,,,, which equals to C, the one one-way-cinee wir-cut from Conjecture [n the first di coordinates, and is equal to (i.c. is constant) on the last do - di coordinates. Then C' is one-way too-sinee the last do - di values are just fixed 1, if we can invert we can invert C too. The reduction in the proof of Theorem 2 then can just be performed with è instead, giving a lower bound instance for the di < d, case.
2.1 UPPER BOUNDS FOR BUECTIVE GENERATORS
We first lay out the assumptions on the map G. The first is a quantitative characterization of bijectivity; and the second requires upper bounds the derivatives of G up to order 3. We also have centering assumption. We state these below.
Assumption (Strong invertibility). We will assume that the latent and observable spaces have the same dimension (denoted d), and G Rd + Idd is bijective. Moreover, we will assume there exists a positive constant > 0 such that V21, 22 E Rdd [[G(z1) G(2z)ll 2 m || 1121-22)) 22
This stronger quantitative version of invertibility. Furthermore, the infinitesimal version of this condition (i.e. || -2ll + 0) implies that the smallest magnitude of the singular values of the Jacobian any point is lower bounded by m, that is Vz E Rd, min (Ja( 2 m > iE(d]
Remark 2:
Since m is strictly positive, this in particular means that the Jacobian is full rank everywhere.
Remark 3: Note, we do not require that G is layerwise invertible (i.e. that the each map from one layer to the next is invertible) if that is the case, at least in the limit 3 + 0, the existence of an inference decoder of comparable size to is rather obvious: we simply invert each layer one at a time. This is important, many architectures based the dimension (i.e. map from a lower to a higher dimensional space), followed by pooling (which decrease the dimension). Nevertheless, it has been observed that these architectures invertible in
convolutions perform operations which increase
3

---

Published as a conference paper at ICLR 2022
practice Lipton & Tripathi (2017) manage to get almost 100% success inverting off- fff-the-shell trained model thus justifying this assumption.
Assumption (Smoothness). There exists a finite positive constant M > 0 such that
Y21, 22 R [[G(z1) - G(22)l M ||| z2ll
Moreover, we will assume that G has continuous partial derivatives up to order 3 at every 2 E IRd and the derivatives are bounded by finite positive constants M2 and Mg
A2 E ERR
||> S M2 < co, co.1VvGG221lo, M3 00
This is a mild assumption, stating that the map G is smooth to third order. The infinitesimal version of this means that the largest magnitude of the singular values the Jacobian at any point is upper bounded by M, that is V2 Rd, max (Ja()()
Remark 4:
[|Ja(z)]lop M co.
sE|d]
Remark 5: A neural network with activation function a will satisfy this assumption when or : R Lipschitz, and max, (a(a) & max, (a)) are finite.
Assumption 3 (Centering). The map G : Rd > I satisfies G(0) = 0.
Remark 6: This assumption is for convenience of stating the bounds-we -we effectively need the "range" of majority of the samples under the distribution of the generator. All the results can be easily restated by including a dependence on |G(0))-
Our main result is then stated below. Throughout, the O(.) notation hides dependence the map constants, namely m, M, M2, M3. We will denote by dTv q) the total variation distance between the distributions p. q-
Theorem 1 (Main, invertible generator). Consider a VAE generator given by latent Gaussian with == 0, I, noise parameter 3² and generator G RRd Tkd satisfying Assumptions / and which has N parameters and differentiable activation function a. Then, for
350
dl.s V log d
there exists a deep latent Gaussian with N' = O (N ppolyld, (. b) parameters and activation func- tions {ar, o', ,P} and a neural network & with (N') parameters and activation functions funncionon {a, p) where p(z) = x², such that with probability 1- exp( (d)) over a sample x from the VAE generator, ((z) produces values for the parameters of the deep latent Gaussian such that the distribution q(2(z) specifies satisfies drv (g(2[x), p(z[z)) S.
Remark 7: Having encoder (==(x) with parameters produced by neural network taking a as input is fairly standard practice it is known as amortized variational inference. (Miih & Gregor 2014 Kingma& & Welling 2013 Rezende et al. 2014)
Remark 8: The addition of p in the activation functions for convenience of stating the bound.
Using usual techniques in universal approximation it can be simulated using any other smooth activation, see Appendix G
2.2 LOWER BOUNDS FOR CON-BUECTIVE GENERATORS
We now discuss the case when the generative map G is bijective, showing an instance such that no small encoder corresponding to the posterior exists. The lower bound will be based on a reduction from the existence of one-way functions standard complexity assumption in theoretical computer science (more concretely, cryptography). Precisely, we will start with the following form of the -uuuwat-nnnntion conjecture:
Conjecture (Existence of one-way permutations (Katz & Lindell 2020)). There exists bijection f: 1-1, + [-1,1)d computable by Boolean circuit C: 11
{-1,1] of size poly(d),
but for every T(d)= poly(d) and e(d) polycai and circuit C'
11
(-1,1) of size ((d)
it holdy Pr Pr (C
s c(d).
4

---

Published as a conference paper at ICLR 2022
In other words, there is circuit of size polynomial in the input, s.t. for every polynomially sized invertor circuit (the two polynomials need not be the same the invertor can be much larger, so long as it's polynomial), the invertor circuit succeeds inputs. Assuming this Conjecture, we show that there exist generators that do not have small encoders that accurately represent the posterior for most points x. Namely:
at most an inverse polynomial fraction of the
Theorem (Main, non-invertible generator), If Conjecture I Tholds, there exists a VAE generator G F. - IRd with size poly(d) and activation functions functioon {sgn, min, max), s.t., for every B o(1/ /d). every T(d) -polldd) and every e(d) 1/poly(d), any encoder E thut can be represented by deep latent Gaussian with networks that have total number of parameters bounded by T(d), weights bounded by W, activation functions that are L-Lipschitz, and node outputs bounded by M with probability 1 - exp(- over a sample x from G and L, M, W o(exp(pon (polydd))), we have:
Pra-o dTV(E(2)0))
-
S {()
10
Thus, we show the existence of a generator for which no encoder of polynomial size reasonably approximates the posterior for even an inverse-polynomial fraction of the samples x (under the distribution of the generator).
Remark 9: The generator G, though mapping from IRd - Rd will be highly non-invertible. Perhaps counterintuitively, Conjecture [ applies to tijoch, the point will be that G will be simulating a Boolean circuit, and in the process will give the same output on many inputs (more precisely, it will only depend on the sign of the inputs, rather than their values).
The choice of activation functions {sgn, min, max} is for convenience of stating the theorem. Using standard universal approximation results, similar results can be stated with other activation functions, see Appendix G
Remark 10:
The restrictions on the Lipschitzness of the activations, bounds of the weights and node outputs of E are extremely mild-as they are allowed to be potentially exponential in d co-oosidering that even writing down natural number in binary requires logarithmic number of digits.
Remark 11:
3 RELATED WORK
On the empirical side, the impact of impoverished variational posteriors in VAEs (in particular, modeling the encoder as a Gaussian) has long been conjectured as one of the (several) reasons for the fuzzy nature of samples in trained VAEs. Zhao et al. (2017) provide recent evidence towards this conjecture. Invertibility of generative models in general (VAEs, GANs and normalizing flows), both as it relates to the hardness of fitting the model, and as relates to the usefulness of having an invertible model, has been studied quite a bit: Lipton & Tripathi (2017) show that for off-the- shelf trained GANs, they can invert them with near- 100% success rate, despite the model not being encouraged to be invertible during training: Dai & (019)) propose an alternate training algorithm for VAËS that tries to remedy algorithmic problems during training VAFS when data lies on a lower- dimensional manifold: BBehrmann et al. (2020) show that trained normalizing flows, while being by design invertible, are just barely so- - the learned models are extremely close to being singular.
On the theoretical side, the most closely relevant work is Lei et al. (2019) They provide an algorithm for inverting GAN generators with random weights and expanding layers. Their algorithm is layerwise that is to say, each of the layers in their networks is invertible, and they invert the layers one at a time. This is distinctly not satisfied by architectures used in practice. which expand and shrink a typical example are convolutional architectures based on convolutions and pooling. The same paper also shows NP-hardness of inverting a general GAN, but crucially they assume the network G is part of the input (their proof does not work otherwise). Our lower bound can be viewed as a "non-uniform complexity" (i.e. circuit complexity) analogue of this, since we are looking for small neural network E, as opposed to an efficient algorithm; crucially, however G is not part of the input (i.e. G can be preprocessed for unlimited amount of time). Hand & Voroninski (2018) provide similar guarantees for inverting GAN generators with random weights that satisfy layerwise invertibility, albeit via non-convex optimization of certain objective.
5

---

Published as a conference paper at ICLR 2022
4 PROOF OVERVIEW
Overview of Theorem 1 Recall, given a generator G and noise level 8², we wish to provide a deep latent Gaussian (Definition 2 that approximates sample from the distribution p(z[æ), with high probability over the draws of x from the underlying density. To show Theorem | there are three main ingredients:
1. We show that gradient descent on the function f(z) |1 =112, run for (²) number of steps, recovers a point Zinit close to argmax, logp(z(z)) -i.e. i.e. the mode of the posterior.
2. We show that Langevin diffusion, a Markov process that has pl p(2|2² as it's stationary distribution, started close to the mode of the posterior via Zinst computed by GD above, run for O (log(d/c) amount of time; returns sample from distribution close to p(z[z) in total variation distance.
3. We show that the above two steps can be "simulated" by a deep latent Gaussian of size at most poly(d, 3. 4) larger than the original network, by inductively showing that each next iterate the gradient descent and Markov chain can be represented by neural network of size comparable to the generator G.
Part is formalized in Lemma I The main observation is that the gradient of the loss will have the form (=()) Jc(=)" an invertible matrix-therefiin therefore, any stationary points will necessarily be the (unique) point 2 s.t. G(z) x. This in turn, for small B, will be close to argmax, log logg(z/// (z).
x). By Strong Invertibility (Assumption [}. Ja(2) will be
Part 2 is formalized in Lemma 2 and is technically most involved. As 3 - O, the distribution p(=[ær concentrates more around it's mode, and approaches Gaussian centered at it. More precisely, we show that starting at Pinst. there is region D such that the probability of Langevin diffusion leaving this region is small (Lemma [13 and the distribution restricted to D is log-concave (Lemma 4 As consequence of the latter claim, reflected Langevin diffusion (a "restricted" version of the standard Langevin diffusion) converges rapidly to p(z]ar) restricted to D. As consequence of the former claim, the reflected and standard Langevin diffusion are close in the total variation sense.
Finally, Part based on the observation that we can approximately simulate gradient descent, as well as the Langevin dynamics using a deep latent Gaussian (Definition 2).. Proceeding to gradient descent, the key observation that if we give neural network = as the input, the point n2)= (G(z) I) can be calculated by a network of size comparable to the size of neural network representing Jc: the Jacobian of a neural network. And in turn, the Jacobian network can be represented by neural network at most a factor (dd) bigger than the neural network representing G-th is by noting that each partial derivative of G can be represented by a neural network of size comparable G, essentially by the backpropagation algorithm (Lemma 5).
The idea to simulate Langevin dynamics is similar: the Euler-Mariyama discretization of the corre- sponding stochastic differential equation (with precision h) is discrete-time Markov chain, s.t. the updates take the form
(2) where L the unnormalized log-likelihood of the posterior p(z(z) (equation 3 below). Same as is the case for gradient descent, a sample following the distribution of these updates can be implemented by a latent Gaussian, with a neural net of size at most (d) bigger than the size of G-the randomness being handled by Gaussian noise that the latent Gaussian has its disposal.
オ LV + v2hg., & ~~ (N,
proceeds by reduction to Conjecture | We Overview of Theorem 2 The proof of Theorem 2
consider G(=) = C(sgn( )) where is a circuit satisfying the assumptions of Conjecture
We show that we can use an encoder g(=|ar) that works with good probability over (wrt to the distribution of G) to construct a circuit C' that violates Conjecture The main idea is as follows: the samples will, with high probability, lie near points on the hypercube {=1]d, For such points, the posterior p(z(z) will concentrate around C C-1(2), so taking the sign of a sample from q(2(2) should, with good probability, produce inverse of sgn(x).
Simulating this construction using a Boolean circuit, we can get a "randomized" circuit that inverts C. Producing a deterministic circuit follows ideas from complexity theory, where show that given randomized circuit, there exists a single string of randomness that works for all inputs, the success probability of the algorithm is high enough.

---

Published as a conference paper at ICLR 2022
5 MAIN INGREDIENTS: THEOREM 1
First, we introduce a few pieces of notation that will be used in multiple places in the proofs. We will also omit subscripting quantities with notational convenience, we will denote the unnormalized log-likelihood of p(z|a) as L RR R. s.t.
notation whenever is clear from context. For
1
l(=)== = 2 ||=1|2 +
ga |G(()) ==l??
(3)
Note, by Bayes rule, p(=[æ) & p(z|2) p(2), so p(z|z) e- Note this is a well-defined
probability distribution since V2 E. L(2) 2 _11211? therefore the partition function is finite. Further, we will denote the inverse of x as 2. namely:
2 = arg min |[((z) - =||²
(4)
ZER
Note since G is invertible, is uniquely defined, and it's such that G (2) = 2. Crucially due to this, the function (22) is strongly convex in some region around the point 2 which can be seen by evaluating (2) from equation 3 These properties are convenient - that why we base our analysis on this inverse point.
5.1 PART 1: CONVERGENCE OF GRADIENT DESCENT
First, we show that gradient descent on the function f(=) = [[[(2) x||², started at the origin, converges a point close in bounded number of steps. Precisely:
Lemma (Convergence Gradient Descent to the Inverse). When satisfies Assumptions 7 and
2 with probability 1 exp(-O(d)) over the choice of x, running gradient descent f(2)
[[(()) 212 with the starting point 20)) == 0 and learning rate ò where Q O(d). for
O d xz) steps converges a point 2(5), such that [|=(5) 111 S 8.
As mentioned in Section 4 the idea is that while is non-convex, its unique stationary point is 2, as
ff(=) J=(=)² (G(=) .)) and Ja(=) is an invertible matrix Vz E I from Assumption 1 The
proof essentially proceeds by a slight tweak on the usual descent lemma (Nesterov) 2003). due to the
fact that the Hessian's 's norm is not bounded in all of IRd and is given in Appendix B
5.2 PART 2: FAST MIXING OF LANGEVIN DIFFUSION
We first review some basic definitions and notation. Recall, Langevin diffusion is described by a stochastic differential equation (SDE):
Definition (Langevin Diffusion). Langevin Diffusion is continuous time Markov process {z+ t E IK} defined by the stochastic differential equation
dæ, Vg )dt V2dB
t t2 0
(5)
where g Rd + R, and (B, : E R+} a Brownian motion Rd with covariance matrix Ia- Under mild regularity conditions, the stationary distribution of this process is P Bdd R+ such that P(z) =0==)
For the reader unfamiliar with SDEs, the above process can be interpreted as the limit as + 0 of the Markov chain
(6) The convergence time of the chain stationarity closely tied to the convexity properties of L. through functional-analytic tools like Poincaré inequalities and Log-Sobolev inequalities (Bakry & Emery 1985). We show that the distribution p(2[æz) .r) can be sampled c-approximately in total variation distance by running Langevin dynamics for (log(d/e)) number of steps. Namely:
ヒ 2 (2) + V2hg. E~ C0,
Lemma 2 (Sampling Complexity for general G). Let 3 O
Then, with probability
Vlog over the choice of x, if we initialize Langevin diffusion equation 6 at zo which
1 -
satisfies || 20 21 < Ω B (.. /dlog for some T = 0 d2 log ?) we have drv (Pr.p(z(z) & e/2
where P; is the density corresponding 2t-
7

---

Published as a conference paper at ICLR 2022
Note, the lemma requires the variance of the latent Gaussian to be sufficiently small. This intuitively ensures the posterior p(2[2) 2)) is somewhat concentrated around its mode and we will show that when this happens, in some region around the mode, the posterior is close to Gaussian. The proof of this has two main ingredients:
(1) 2t stays in a region 'D around with high probability; (2) The distribution p(=[ar), when restricted to D is log-concave,
"projected" version of Langevin diffusion (formally called reflected Langevin diffusion, see Definition mixes fast to this restricted version of p(= (z).
The first part is formalized as Lemma 13 in Appendix C The main mathematical tool is a stochastic differential equation characterizing the change the distance from 2. Namely, we show:
áll= a|( If a follows the Langevin SDE corresponding to 2,, then for E D as defined in Lemma 13 and B S Bo as defined above, it holds that
Lemma 3 (Change of distance from 2). Let n==)
m² B2 n=)ddl (1=11 + di 2Vn(z)dB
dn(2) S
This SDE is analyzed through the theory of Cox-Ingersoll-Ross (Cox et al. 2005) processes, which SDEs of the type d.M, (a- (.-, +y M,dB, where a, b, arre positive constants. Intuitively, this SDE includes an "attraction term' dt which becomes stronger as we increase M, (in our case, as we move away from the center of the region 2), and diffusion term ev M,M, due the injection of noise. The term 1| d)dt comes from the heuristic Itó calculus equality dB, = dt.
m The "attraction term" 3" (=)=dt comes from the fact that [==) is approximately strongly convex near 2. (Intuitively, this means the Langevin process attracted towards 2.)
To handle the second part, we show the distribution p(z(x) restricted to D is lon-ccncave: Lemma (Strong convexity of over D). For all = E D, V²
Since the set D is a 12 ball (which is of course convex), which always remains inside D, called the reflected Langevin diffasion mixes fast.
show alternate Markov process
Definition (Reflected Langevin diffusion, (Lions & Sznitman 1984 [Saisho 1987)). For suffi- ciently regular region D C Rd, there exists a measure U supported on ØD, such that the continuous- time diffusion process {yr t E } starting with yo E DD defined by the stochastic differential
equation:
dy Vg(vi)tt + VddB UUU (y:) t 2
has as stationary measure p. D - RR+ such that P(y) x e e Here g : Rd + R. (B. : t E R
is a Brownian motion in IR with covariance matrix la, and is an outer normal unit vector to D.
For readers unfamiliar with SDEs, the above process can be interpreted as the limit as + of
Vk 2 0, M 1lp yx /Vg())) V2hga
EN NOO, Ia)
where 1p is the projection onto the set 2D
For total variationa distance, the mixing time in total variation distance of this diffusion process was characterized by Bubeck et al. (2018):
Theorem (Mixing for log-concave distributions over convex set, Bubeck et al. (2018): Proposition 2). Suppose measure p Rdd R+ of the form p(æ) x e 9l supported over S Rdd of diameter R which is convex, and Vx E S. V2g Z O. Furthermore, let Do E S. Then, if Pr is the distribution after running equation 7 for time t starting with a Dirac distribution at No, we have
TV(p:, p) Se 2R
Since the set D in Lemma 13 an 12 ball (which of course convex), it suffices to show that is convex on DD whihic is straightforward calculation. The details of this are again in Appendix
5.3 PART 3: SIMULATION BY NEURAL NETWORKS
Finally, we show that the operations needed for gradient descent as well as Langevin sampling can be implemented by deep latent Gaussian. Turning the gradient descent first, need to "simulate" by
8

---

Published as a conference paper at ICLR 2022
x) roughly (d)/32) number of times. We prove that there is a neural network that given an input 2, outputs 2 -))a(2) (G(z) z). The main ideas for this are that: (1) If G' is neural network with N parameters, each coordinate of Jz(2) can be represented as neural network with ((N) parameters. (2) If f J are two neural networks with N and M parameters respectively, f + g and fg can be written neural networks with O(M N) parameters.
neural net the operation <- 2 2=)) (G(2)-
The first part essentially follows by implementing backpropagation with a neural network:
Lemma (Backpropagation Lemma, Rumelhart et al. (1986). Given neural network G R - I. of depth and size N, there is neural network of size O(N + +1) which calculates the gradient / for i e [d].
For the second part, addition is trivially implemented by "joining" the two neural networks and adding extra node to calculate the sum of their output. For multiplication, the claim follows by noting that zy = 1 (x + y)² 1 (x y)². Using the square activation function, this can be easily computed by a 2-layer network.
Proceeding to the part about simulating Langevin diffusion, we first proceed create discrete-time random process that closely tracks the diffusion. The intuition for this was already mentioned in Section the SDE describing Langevin can be viewed as the limit + of
ビ z h JJC()) (G(=) (G(z)- - -0)] + V2hE,E~ N(O,
It can be readily seen that the drift part, that is z JG(=)² (G(=) - x)) can be calculated by a neural net via the same token as in the case of the gradient updates. Thus, the only difference is in the injection of Gaussian noise. However, each layer G, in a deep latent Gaussian exactly takes a Gaussian sample & and outputs G2(2) + so each step of the above discretization of Langevin can be exactly implement by a layer in a deep latent Gaussian. The details are in Appendix D
MAIN INGREDIENTS: THEOREM 2
We prove Theorem proceeds by reduction to Conjecture | Namely, C is Boolean circuit satisfy- ing the one-way-function assumptions in Conjecture
consider G(=) = C(sgn(=)). Suppose there
a deep latent Gaussian of size T ('n) with corresponding distribution q(z|zz) ). s.t. with probability at least c(d) over the choice of (wrt the distribution of G), it satisfies drv (p(2)ar (p(2))r),,,))))) (l) {(1==)) 1/10. We will how to construct from the encoder a circuit C' that violates Conjecture Namely, consider a ī constructed by sampling Σ ~ {+1] ja uniformly at random, and outputting C(E). To violate Conjecture D we'd d like to find C- (f), using the encoder E.
We first note that x 5 +, { (O, (aa))) is distributed according the distribution of the generator G. Moreover, we can show that with probability at least e(d)/2, 2, it will be the case that is s.t. both (T q(([=)) s 1/10 and very close to point on the discrete hypercube {=1]d. The reason for this that the samples themselves for small enough 9 with high probability are close to a point on the hypercube. For such points, it will be the case that g(=[ær) is highly concentrated around C C²)( thus returning the sign of a sample will with high probability invert T. By simulating this process using Boolean circuit, we get "randomized" circuit (that is, circuit using randomness) that succeeds at inverting with inverse polynomial success. To finally produce a deterministic Boolean circuit that violates Conjecture [ we a standard trick in complexity theory: boosting the success probability by generating multiple samples together with the assumption on the weights and Lipschitzness of E. For details, refer to Appendix E
7 CONCLUSION
In this paper we initiated the first formal study of the representational complexity of the good encoders in VAEs. We proved the following dichotomy: generators with invertible means give rise to posteriors that can be approximated by encoders not much larger than the generator. On the other hand, for non-invertible generators, the corresponding encoder may need to be exponentially larger. We hope work will stimulate research of other data distribution properties that render inference tractable.

---

Published as a conference paper at ICLR 2022
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Dominique Bakry and Michel Émery. Diffusions hypercontractives. In Séminaire de Probabilités XIX 1983/84, pp. 177-206. Springer, 1985.
Jens Behrmann, Paul Vicol, Kuan-Chieh Wang, Roger Grosse, and Jömn-enrik Jacobsen. Un- derstanding and mitigating exploding inverses in invertible neural networks. arXiv preprint 1:Xiv:2006.09344 2020.
David Berthelot, Colin Raffel, Aurko Roy, and lan Goodfellow. Understanding and improving interpolation in autoencoders via an adversarial regularizer. arXiv preprint arXiv:1801 07543, 2018.
Sébastien Bubeck, Ronen Eldan, and Joseph Lehec. Sampling from a log-concave distribution with projected langevin monte carlo. Discrete & Computational Geometry, 59(4):757-78,, 2018.
Yuri Burda, Roger Grosse, and Ruslan Salakhutdinov. Importance weighted autoencoders. arXiv preprint N.KKv:55590005 2015.
John C Cox, Jonathan E Ingersoll Jr, and Stephen A Ross. A theory of the term structure of interest rates. In Theory of Valuation, pp. 129-164. World Scientific, 2005.
Bin Dai and David Wipf. Diagnosing and enhancing vae models. arXiv preprint arXiv:1903.0578)) 2019.
Arnak S Dalalyan. Theoretical guarantees for approximate sampling from smooth and log-concave densities. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2016.
Arnak Dalalyan. Further and stronger analogy between sampling and optimization: Langevin monte carlo and gradient descent. arXiv preprint arXiv:1704.04755 2017.
Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprins 14X6v:/406.22m 2661, 2014.
Paul Hand and Vladislav Voroninski. Global guarantees for enforeing deep generative priors by empirical risk. In Conference On Learning Theory, pp. 970-978. PMLR, 2018.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
Nobuyuki Ikeda and Shinzo Watanabe. A comparison theorem for solutions of stochastic differential equations and its applications. Osaka Journal of Mathematics, 14(3):619-63,, 1977.
Jonathan Katz and Yehuda Lindell. Introduction to modern cryptography. CRC press, 2020.
Diederik P Kingma and Max Welling. 1rXiv:1312.6114, 2013.
Auto-encoding variational bayes. arXiv preprint
Qi Lei, Ajil Jalal, Inderjit S Dhillon, and Alexandros G Dimakis. Inverting deep generative models, one layer time. arXiv preprint arXiv: (006::90000000 07437, 2019.
Lek-Heng Lim. Singular values and cigenvalues of tensors: a variational approach. In 1st IEEE International Workshop Computational Advances in Multi- Adaptive Processing, 2005., pp. 132, IEEE, 2005.
Pierre- Pierre-Louis Louis Lions and Alain-Sol Sznitman. Stochastic differential equations with reflecting boundary conditions. Communications on Pure and Applied Mathematics, 37(4):511-537, 1984.
Zachary Lipton and Subarna Tripathi. Precise recovery latent vectors from generative adversarial networks. arXiv preprint arXiv: ( 7702004782 2017.
10

---

Published as a conference paper at ICLR 2022
Andriy Mnih and Karol Gregor. Neural variational inference and learning in belief networks. In International Conference on Machine Learning, pp. 1791-1799. PMLR, 2014.
Ankur Moitra and Andrej Risteski. Fast convergence for langevin diffusion with matrix manifold structure. arXiv preprint arXiv:2002.05576. 2020.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2003.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. arXiv preprint 17Xvx3702,03849, 2017.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. In International conference machine learning,
pp. 1278-1286. PMLR, 2014.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. nature, 323(6088):533-536, 1986.
Yasumasa Saisho. Stochastic differential equations for multi-dimensional domain with reflecting boundary. Probability Theory and Related Fields, 74(3):455-477 477, 1987.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. Advances in neural information processing systems, 29: 2234-2242, 2016.
Yujun Shen, Jinjin Gu, Xiaoou Tang, and Bolei Zhou. Interpreting the latent space of gans for semantic face editing. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9243-9252, 2020.
Hava T Siegelmann. Neural networks and analog computation: beyond the Turing limit. Springer Science & Business Media, 2012.
Matus Telgarsky. Neural networks and rational functions. In International Conference Machine Learning, pp. 3387-3393. PMLR, 2017.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Shengjia Zhao, Jiaming Song, and Stefano Ermon. Towards deeper understanding of variational autoencoding models. arXiv preprint arXiv: 2017.

---

Published as a conference paper at ICLR 2022
A TECHNICAL DEFINITIONS
In this section, we state several definitions and standard lemmas, to cover some technical prerequisites for the proof.
We first recall a few definitions and lemmas about two notions of distance between probabilities we will extensively, total variation and x² distance.
Definition (Total variation distance). defined as
The total variation distance between two distributions P, is
dT (P. sup P(A) Q(A)
A
Definition 6 (x2 distance). The x² distance between two distributions P,Q. s.t. Pis absolutely continuous with respect to Q, is defined as
P (6-1)²
xP..Q) == EQ
The following two lemmas about the total variation and x² distance are standard:
Lemma 6 (Coupling Lemma). Let P,Q:9. + IR be two distributions, and c: 2 - be any coupling of P, Q. Then, if (X, X') are random variables following the distribution c, have:
drv(P, Q) S Pr[X & X')
Lemma (Inequality between TV and x²). Let P, P,Q be probability measures, S.I. P is absolutely continuous with respect to Q. We then have:
1 dTv(P,Q) Vx2(P.Q)
We will be heavily using notions from continuous-time time Markov Processes. In particular: Definition 7 (Markov semigroup). We say that family of functions {Pr( v) on a state space Markov semigroup if (x.. :) distribution on and
Pro+o1z8) = / Pi(x, (2,
for all x, y E Ω and s, 0.
Definition 8 (Continuous time Markov processes). A continuous time Markov process (Xt)r20 on state space is defined by a Markov semigroup (P, y) as follows. For any measurable A C Ω
Pr(X++t E A)
P((x, dy Pr A)
Moreover Pt can be thought of as acting on a function as
(z) P.,,
gly) v)
Finally we say that p(x) is a stationary distribution if X, implies that X, ~ p for all f.
With this in place, we can finally define the Langevin diffusion Markov process:
Definition (Langevin Diffuusio,, Definition restated), Langevin Diffusion is continuous-time Markov process { E Rt} defined by the stochastic differential equation
dæ, (2 V2dB
t
(9)
where g Rd + IR, and (B, : t E R+} Brownian motion Rd with covariance matrix la- Under mild regularity conditions, the stationary distribution of this process is P Rd - R such that P(z) e 9
will also be useful to have definition of a diffusion process that only stays within some support D, and thus has stationary distribution supported D. Specifically:
12

---

Published as a conference paper at ICLR 2022
Definition 10 (Reflected Langevin diffusion, (Lions & Sznitman 1984, Saisho 1987). Definition
restated). For a sufficiently regular region S IR, there exists measure U supported on 0D, such that the mantinuous-time diffusion process {yr. : IR} starting with yo D defined by the
stochastic differential equation:
dyt = VVylvd + V2dB, (y))d
120
(10)
R. (B, : R+ has as stationary measure p: D - R+ such that P(y) x e 9(v), Here g -
is a Brownian motion in IR with covariance matrix La, and is an outer normal unit vector to D.
Towards introducing quantities governing the mixing time of continuous-time Markov process, we introduce
Definition 11. The generator of the Markov Process is defined (for appropriately restricted
functionals g)
Pig -9
Lg lim
Moreover if p is the unique stationary distribution, the corresponding Dirichlet form and variance are Es (g. h) = Ep Lh) and (gr Ep Epg)
respectively. We will use the shorthand E(g) gg.
A quantity of particular interest when analyzing the mixing time of Markov processes is the Poincaré constant:
Definition 12 (Poincaré Inequality). A continuous Markov process satisfies Poincaré inequality with constant C if for all functions g such that Exr is defined (finite), it holds that:
Ex(()) 2 C Varp(g)
where P (in the subscript) is the stationary distribution of the Markov process. We will abuse notation, and for such Markov process with stationary distribution P, denote by Cpe(P) (P) the smallest such that above Poincaré inequality is satisfied; and call it the Poincaré constant of P.
The relationship between the Poincaré constant and the mixing time of random walk (in particular, the in Definition 4 is given by the following (standard) lemma:
Lemma 8 (Mixing in x² from Poincaré). Let & follow the stochastic differential equation of reflected Langevin disfusion ( (Definition 4 with stationary measure P. Let Pe be the density of 2 and let Po be absolutely continuous with respect to the Lebesgue measure. Then:
(1) If Po is supported on D. Pe is supported on D, VI >1>0
(2) x2 P) e//Cue (P),
Finally, we will also need a discretized version of the continuous-time Langevin diffusion. Definition 13 (Euler-Mant) MBuler-Mariyama Discretization for the Langevin Diffusion). For a potential g Rd R. the Euler-Mariyann discretization of the continuous Langevin diffusion with discretization level is the discrete- time random walk
Vk 2 0, Zk-1 = 2 hVgg())) + 22h Ex~ (0,
(11)
We will also associate with this discrete-time process stochastic differential equation
dm, = - Vg( + v2dB,
(12)
which has the property that Eus and zμ follow the same distribution for all A: 2 0. if 20 and &o follow the same distribution.
Note the equivalence between equation 11 and equation 12 follows by noting that the drift in the interval [th, (t + 1)h] in equation 12 is constant so we only need to integrate the Brownian motion for time h.
We can also consider the discretized version of the reflected Langevin diffusion, which looks like projected gradient descent with Gaussian noise Bubeck al. 2018).
13

---

Published as a conference paper at ICLR 2022
Definition 14 (Discretization for the Reflected Langevin Diffusion). For potential g R + R, the Euler-Mariyama discretization the reflected Langevin diffusion with discretization level the discrete-time random walk
Vk 2 0, 9k+1 llp yk / (Vg) + 22hx
E ~ (O,
(13)
where TT the projection onto the set D.
We can also associate with this discrete-time process stochastic differential equation
djr Vg(ūLu/jja + Vdd, + v.U (De)
(14)
for measure U supported on 0D, which has the property that O&A and yk follow the same distribution for all & 2 0, if yo and Do follow the same distribution.
B PROOF OF LEMMA I CONVERGENCE OF GRADIENT DESCENT TO 2
First, we state the tweak on the usual descent lemma (Nesterov 2003), due to the fact that the Hessian's 's norm is not bounded in all of IR We only need to identify a region A containing the starting point (0) such that the function's 's value at points outside A are guaranteed to be more than
the function value at 20) Namely:
Lemma (Adjusted Descent Lemma). Let Rd + be twice differentiable function. For region A, let it hold that Vz A, [[)2 I cc. Further, let V2 E TR f(z) 2 f(2(0)
for a known point 20)) A. Then the gradient descent iterates starting with 20)) with the learning
rate = Q satisfy
f(z(0+1)) S (()
8 $20
2Q
We first state the well- descent lemma. Lemma (Descent Lemma, Eq 1.2. 13 in (Nesterov 2003 ) Let f be a twice differentiable function,
and at point the hessian sutisfies [=)](p S the next gradient descent iterate 2+ satisfies
< co. Then with the learning rate == Q'
((tt)s(aa 2Q [V[
Using this, we prove the Adjusted Descent Lemma.
We will prove the Lemma by induction. To that end, let call by I(s), Vs the proposition in the Lemma statement, i.e.
Proof of Lemma 9
((s)
> f(((0)
2Q \1(2()))11
We first write two propositions J(s) and K(s):
J(s): 200) A
K(s):
f(2()) s f(=) Vz E E
We will use induction to show that ((s) A J(s) A ((s) hold true Vs 2 0. ((0) holds true, since 2(0) E A is given in the statement. ((0) is also given in the statement of the lemma.
Since Vz A, [(=)l(p 5 Q: from Lemma 10 conclude that
(15) Hence I(0) also holds true. So the base case of the induction (s = 0) is done, i.e. I(0) A A ((0).
((s)
(s))
Vs 2
Since [(s) implies descent, and ((s) implies that all points outside region A have larger function value, we also have
T(s) K(s) J(s + 1) K(++1)
(16)
14

---

Published as a conference paper at ICLR 2022
Combining implications equation 15 and equation 16 and Lemma 10 get (ss) (s) (s)) (( 1) A ([ls++1)K(s+]))
as 0
(17)
Hence the induction step also goes through.
n
We can now use this prove convergence of gradient descent.
Proof of Lemmal 7 region A.
To the adjusted descent lemma (Lemma 9 let define the appropriate
M
|<||
A
|=|| S
(18)
m
Obviously 20)) = 0 A. We also have V2 E IRd
A. the following holds
f(z) f(=(0)) = f(z) - f(0)
2 (IG(2) z||2 [[ ==1²)
(IG(=) G(3)12 ||G(0) G(
2
2 (0) 1
(m²lI 2112 - 1
2
2 C (mll
21l MI
M
2 mm
|12 21
|2|1
M
2 mC
|||||
+
||=11
201 mC
M
+1
||=|||
M
+ 1)
||
M
|
+1
.mC+
||
M (2)
3 ||| + &l] denotes a non-negative quantity, which does not affect the sign of these inequalities. In the above calculation, (0) follows from Assumptions and 2 (1) uses the
definition of A from equation equation 18 and (2) uses Lemma 23
In A, the norm the Hessian can be bounded as below. The expression of V can be inferred from the expression of 2 L given in equation equation 56 We then get
v f()))lop [1 +
Σ [G,(z) kE(d]
251 ||)
<(0) M + Σ G+(()) xz|
max sEId
iE|d
(11) M + Vd. [IG(2) - x M2
M + VdMM2 1|2- 211
(2) M² + VaMM2 2 M ||>|||| =: Q
1)
2EA
(19)
where (0) follows from Assumption 2 (1) follows since Vi E [d], V> < G op:
which follows from the sup-definition of the & norm (Lim 2005). In (1), we also used the fact that [[l]] v di) ||e||e- And in (2) used the diameter of AA of equation equation 18
15

---

Published as a conference paper at ICLR 2022
With A, Q defined through equations equation 18 and equation 19 the conditions of Lemma 9 are
satisfied, so we can use the descent equation. We can then use the standard argument below
vs e [] | 2a
= f(20)) S f(z - S 1 2Q a
Since f is a non-negative function, it is bounded below by zero. This means that
[Vf(2(()) S 2Q f(2101)
min .E
We note that
|V = [x) (G(z) - x)
min (J [[((2) x||
:E|d]
min [o,(Ja(=)) 22f(2)
sE|d]
m 2f(z))
By Lemma 9 we then have
[in / (z(o)))]
1
[(2(8)
2
m
1 Qf(z(0))
m2
S
Furthermore, by Assumption we have
< 1
| - |||
(8) - x|1
2f(2(8))
m
2Qf(2(01)
1 m²
S
gives us the required number gradient descent steps. We will finally simplify the expression for S. Since f(=(0)) f(0) G[( x|| Assumption 3). we get
Hence, setting 8 m
2 S
| (from
Q |
5
(20)
mnd
82
Plugging in the expression for Q from equation
19 and using ||=||| O(vd) from Lemma 24 we
get S O d desired.
C PROOF OF LEMMA 2 FAST MIXING OF LANGEVIN DIFFUSION
Notation:
We first set up some notation. We denote by 2₁ the time t iterate of Langevin diffusion (Definition (3) with g == L, having as stationary distribution P(z) p(z|z). Further, we denote by
Pt the density of
Similarly, we denote by &, the iterates of the reflected Langevin chain (Definition with g == L, with stationary distribution P(z) x e M[2) supported over E D. We denote by P. the density of ă Lemma 11. rad(D) defined Lemma 13 along with the restriction on 3 from the same lemma satisfies
m²
m
rad(D) < min
6dMM2 22VdMM,
This in particular means that rad(D) < O(1dd).
16

---

Published as a conference paper at ICLR 2022
Proof. Follows by straightforward substitution.
This section will be organized as follows. In Subsection C.1 we prove a lemma quantifying the difference between the distributions of the regular and reflected Langevin Chains To use this lemma, we require a property of the Langevin diffusion for our setting remains in the region D. We tackle this in Subsection C.2 In subsection C.3 we prove Lemma 4 namely that p(z[æ) restricted to D log-concave. Finally, using the above three pieces, we will prove prove the main lemma of this section (Lemma in subsection
Organization:
(Lemma 12
(Lemma 1 namely, that the chain with probability
C.4
We note that some of the techniques here have overlap with techniques used in (Moitra Risteski 2020), but we provide all the proofs in detail for completeness.
C.1 RELATING RESTRICTED AND UNRESTRICTED LANGEVIN CHAINS
The main lemma of this section is as follows:
Lemma 12 (Comparing with reflected Langevin diffusion). Let & follow the reflected Langevin SDE (Definition 4) with := L), with stationary measure P and with domain 'D. Let 24 follow the Langevin diffusion SDE (Definition 3) with ;= L, with stationary measure P. Let Pe be the density of z and let Pt be the density of and let Po be absolutely continuous with respect to the Lebesgue measure.
Then Vt 2 0, Pr Ba E [0, t), Ra $ DJ S a, it holds that:
dTv(P:, P) S
(radP(D)
Vt 2
Proof. Consider the total variation distance between P. and P. Using triangle inequality, we have
dPr P) S dP P.) + dTv P) + dT, P)
(21)
We first bound the second term using Theorem 3. Since D is convex and L is convex over D by Lemma we have
dTv P)
Se 2rad
(22)
For the first term, consider the coupling of 2n and & such that the Brownian motion B, is the same. We then have for any t 2 0
(P) Pr + 3x] Pr/3s E j0, 2 & D
(23)
where the first incquality follows by Lemma 6 and the second inequality follows from a rewrite that uses the fact that if the unrestricted chain 2, stays inside the region D, then the two diffusions won't t differ at all due to the coupling of the Brownian motion. The term a bounds the probability of the unrestricted chain 2, leaving the region D.
For the third term, need to bound dP, P). Note that P Rd + RRt P: D Rt, P(z) xc <M))) This means that V2 E D. P(2) P(z) and Ve Rd (D P()) P(z). So we can write
P(z) ee-
L(x)) and
dPv P) Pr [200 $ D
(24)
where 2 is the follows the stationary distribution of the Langevin diffusion P. From the drift bound in the lemma statement, we can take the limit of t + co to get
lim
VI 2 0, Pr Ba E 00 $ D <
Pr la E [0, 00), $ D <
Pr Exx $ S a
(25)
Using equation equation 24 and equation 25
we get
(P
(26)
The lemma statement follows from equations equation
23
equation
22 and equation 26
n
17

---

Published as a conference paper at ICLR 2022
C.2 EFFECTIVE REGION FOR LANGEVIN DIFFUSION
In this section, we prove Langevin mostly stays in an effective region D, namely:
Lemma 13 (Effective region for Langevin diffusion). Let 'D = {= ||= 2|| S rad(D)) with
4 4(2d+ !=!!-
rad(D)
13 m (2d+ 1=!!" x
log
Let zo satisfy ||z0 Ell S raa((D). Then with
3 S So, we have that VT > O, Pr
E
E [0, T),
xn $ DJ S e/4, where
4
m3
d0
80
min
66M /2MM
s2d++ 1=12)
d
(d
+
||||| me
log
Towards proving Lemma 13 we will first prove Lemma 3
Proof of Lemma Using dæ = (zz)dt + V2dB, along with Itó's Lemma, we can compute
dn(=)) = (Vn(z), VL + (v2) + (Vn(z), v2dB.)
(27)
We will bound each term on the right hand side. First note that Vnς(2) = - ê, and so V (2n(22) for all E Rd. We proceed to the second and third term since they 're straightforward. For the third term, we have (Vn(=), dBB.) [|
=
222(2)) (2n(2)dB3 B,, using slight abuse of notation to denote the I-dimensional Brownian motion (in the RHS) as also B,. For the second term, note that
An(=)= = d since (2) = I. So:
dn(2) - (Vn(2), (t + d. dt + +2Vn(2)dB
(28)
For the first term, from Lemma 26 we get
(Vn(z), v=(2)) (z 2, L2))
1 g Jo())" Jo( (z- + (z 2, Rv)((2))
- 2, + (z 2, I
(2 - 8, 2) + || - 2| + ga [la(() - 2)12 + (z - 2, Rol(z))
(29)
First, we analyze (2 - 2, 2). Using Cauchy- Schwartz we can write (2 - 2, 2) 2 -||2 - -211|
Case 1. [= El ||. We write that (2 2, E) =||
Case 2. = - 8 ||. We can write that (= 2, 2) 2 -1 -1
In either case, it holds that
(2 - 2) 2 - (1|2 2112 2 + ||
(30)
Second, by Assumption 1 we can say that
[]Jo()) })| m 1= =112
(31)
Third, by the expression of the norm of the remainder from Lemma 26 we get (z 2, Rv)(
|| El| [x)]
2 2,32
(3dMM, ||2 - 21l + VdMMs || (1x-211) -11--20 211
For E D we have ||2 - ||| S rad(D) so
(a 2 (z)) 2 2,92
3dM SdMMM2 rDd + VdMM3 : rad(D)?) -|=- 2ED
The inequality on rad(D) from Lemma 11 implies that 3dM rod(DD < m m² rad(D)² < -- and so
and VdMM3
m² ||
(2 2, (x)) 2 2
2112
E
(32)
18

---

Published as a conference paper at ICLR 2022
Plugging in equation equation
30 equation
31 equation 32
in equation equation 29 get
m²
m2
m²
(Vn(z), VL())) 2 -||2||-
2|
-
211
2 E D
ga
2
2,52
Using this in equation equation finishes the proof.
28 and substituting the definition of 17(2), i.e. 12 - 811 2n ())
Next, we prove high probability deviation bounds for Cox- Nox-Ingersoll--R -oss processes. Precisely, we show:
Lemma 14 (Concentration Bounds on Cox-Ingersoll-Ras Process). Consider the SDE
dX,- = wxxdt + NNt + X,d,
for N E N and w > Then for any
4N w
4N )
VT > 0, Pr Vt E [0, s.t. X, S 2Xo
log
2 21-6
Proof. The SDE describes a Cox-Ingersoll-Roc process of dimension Ñ, which equals in distribution the random variable Y; as defined below, and with matching initial condition Yo := Xo-
(1,0)2
Y,
(33)
Here V,(0) follow the Omsstenn-Uhlenbeed equation dV;()) VV dt and Vo Yo/N
for all E [Ñ]. dB(") are (I-d) Brownian motions, and we have referenced them separately because they are independent for each i E [V]. Indeed, applying Itó's Lemma, we recover the same SDE as:
1 . [ 2v/(() (- v2 +
dY. Σ
di + 2V, (9) dB!
N
(v((1) dt + Nel + 2
( (B(()
=-
1=1
-YYdl + Ndl + Σ (v²0)) dB.
wY Not + 2 Y,dB,
Here in the RHS the first expression, the term 1 2 the term 1 o² (v
( from Ito's Lemma.
And in the third expression, notice that we have replaced a sum of brownian motions with a single one of matching variance.
Now we can write an explicit solution for the SDE. Since we know the solution of an Orsstein- Uhlenbeck process, each vz(0) can be solved as (now we drop the indexing i since the solution is same for each [N)
V = Voe 22 7 I' ((()))))
(34)
F(()
Applying the reflection principle F(t), we get
V, >0 0
F() Pr Pr |0, T), F(1) 2 2P) 2 a)
(35)
19

---

Published as a conference paper at ICLR 2022
Further, writing the distribution of F(t), we have
F(1) F(O~~N (1-
From standard Gaussian tail bounds, we have
a²
VT' > 0, Va > O Pr(F(T) 2 al S exp
(1 w
From equation 35 substituting := rV (1 e= we have
0,Vr
Pr 3t E [0,T], 2
(1 - e wT)
S 2e 2r-
Since the quantity F(t) has symmetric density about zero for all t, we can write the two sided bound as
2 _ (1 - e
VT 0. A O
Pr 3 e [0,
[(t)
I 4e
(36)
Choosing such that e/N - in equation 36 and using union bound over the indices i [M] we have
vT w.p. (1-c): At [0 [M), (v:0--V' e =x))
log
4N
2 (1
e-w
w
2
log
4N
w
Plugging in (i))
Yo/N for all i [N] we get
AA > 0 w.p. (1-6): A [ vil S VYoNee -2 #1+ -
2
log
4N
2 log
4N
S Yo/N+
Finally, using (a + 6)² < 2(a + b²) and summing over all indices i [N]. we get
N
V 0 w.p. (1 - c): VI (O,T) Σ (v 2 < 2Y +
4N
4N
log
(37)
Replacing the sum by Y, using equation 33 and replacing X,, X2 in place of Y,, Yo gives the result.
Next, since all of SDEs far have been actually inequalities, will need standard comparison theorem for SDEs:
Lemma 15 (Comparison theorem, (Ikeda & Watanabe 1977)). )) Let Up Xe be two processes following the SDEs
dU, f(U,)dt + h(U,)dB,
dX, g(X,)dt + h(X.)dB,
driven by the same Brownian motion В.. Let at least one of these SDEs have a pathwise unique solution. Vx E Rd, f(x) < g(x), and if Un Xo. then with probability 1,
U X
0
20

---

Published as a conference paper at ICLR 2022
shows domination of stochastic variables based inequality in their respective SDEs. This is almost what we need, since we showed an inequality in SDEs in Lemma] 3 and showed that the upper bound is concentrated in Lemma 14 We need slight adjustment
Lemma 15
top of this though. Note that the inequality between SDEs in Lemma holds only for E 'D however the inequality that the above Lemma requires on all points a, I [(a S g(x). We work through this by simply noting that conditioned on X, (the upper bound SDE) being concentrated in region, Ur will also be concentrated in the region. We state and show this below.
Lemma 16. Let Ub, X₃ be two stochastic processes whose SDES follow
dU, =(UU)dtt + h(U,)dB,
dX, = g(x))dt + h(Xx)dB, driven by the same Brownian motion Br. Let least one of these SDEs have a pathwise unique solution. If (a) S s(xa) for all a S Cug and Up Xo I Oggi then
VT 0, D. < on Pr V 10. U, s x 2 Pr
X S
M
Proof. Consider any T > 0 and X S on-
Pr V [0, T) U. X] > Pr Vt E [0, T), Us & X, and VI E [0, X, S X]
Pr Vt E [0, X₁ S X
Pr Vt E [0, 11, U3 - X₂ Vt [0,1], X, S
Where the last probability is one, because both U, and X, continuous-time processes, and so Ug > X, given X, S X < or is not possible because U/ cannot cross over X, in the f S region (using comparison Lemma 15
Given the above preliminaries, we can finally complete the proof of Lemma
Proof of Lemma 13
Instantiate Lemma 16 with U, := 77(2) and instantiate another SDE on X₃ with
the same Brownian motion U2, as below
m 32
dx,
X,dt + 2| d dt 2 X,dB.
such that Xo == Un = (=0) = 11100 - 211 From Lemma 14 (plugging in N = [[] + d] and m² w WF), ), we can conclude that for any >>
4N w
4N _
VT 0, Pr Vt E [0, X, 2X,
log
21
(38)
c
Using the Lemma 16 on U, and X,, with X : 2X, + log
and with ag = (D))
(since the inequality between SDEs of U, and X, holds in the region U, I (rad(D)² from lemma
3)
get
S a VT 0. Pr Pr (0, U, ool 2 Pr Vt E [0, T) Us s X
> Pr Vt [0, < X
where the last inequality follows from equation 38 Note that U2 < ag z, E DD. This is exactly the event whose probability we need to lower bound.
| 21 rad(D)
We now check that the condition for the above is met, namely:
4N
4N
X < op 2X
log
rad (D)2
w
e
21

---

Published as a conference paper at ICLR 2022
Where Xn = -/1
2
(grad(D)) from the lemma statement. This then becomes
4N
4N
1
log
7
rad(D)), i.c.
w
N
4.N
(D) 2 4
log
Putting in the values N, from above, and using Lemma 23 to bound || (since the RHS above is
an increasing function of N), and bounding the ceiling trivially by [x]] S + d (since d 2 1) means suffices that
2d + 1=1l 4
43 m
(ad
||=112 m²
(D)
log
Using the bound on ,3 the above inequality is indeed satisfied for our choice of rad (D).
C.3 PROOF OF LEMMA
Proof. Using the expression of V from equation equation 56
we get that
L²L(2)
1+ 32
m²
(C.(
xx4) I
(39)
iE
And we have
Σ
(G(())
- xi)
Σ G+(z)) - xd V
iEId
iE|d
op
G.(2) 1/ [+
iE/4
<0)) Vd. |[G(2) x1| V
(1) Vd M|| 21 M2
< VdMM, rad(D)
2 E
In (0), used the fact that Vi [d, V
< || which be derived from the
op
sup-definition of the tensor & norm from (Lim
2005). In (1), we' we've 'e used Assumption Using the
expression of rad(D) from Lemma 11 get
< m
(G)())
xz))
E D
b
iE|d
op
S m 2
2 E D (since d 2 1)
Using this in equation 39 we get V²I(2) 2 for E D.
C.4 PROOF OF LEMMA 2
We can now put together the proof of Lemma
Proof of Lemma 2 Using Lemma 12 with D defined as in Lemma 13 with := =/4 in Lemma 13
and setting T = rad? (D) log we get e T/2rad 4. Using rad(D) = O(1/d) from lemma
11 the result follows.
22

---

Published as a conference paper at ICLR 2022
D PROOF OF THEOREM I BULER-MARIYAME DISCRETIZATION AND NEURAL SIMULATION
In this section, we use the mixing time bounds in the previous sections, along with discretization error analysis when running a disretized (in the simplest manner, via a Maller-arryyama scheme) version of the Langevin diffusion chain. This is done in Subsection D.1 Subsequently, each of these steps can be simulated by a "layer" of a neural network. This is done in Subsection D.2 Finally, we put everything together prove Theorem in Subsection D.3
show that
D.1 BOUNDING THE ERROR IN THE EULER- MARIIAAA DISCRETIZATION
We finally wish to show that with a polynomially small discretization level (i.e. h), the Fuler- Mariyama scheme approximates appropriately for our purposes the Langevin diffusion process. We recall from equation 2 that this Markov process is described by
= -- LV + V2hc. Ç ~ N(,
(40)
There is a rich field in the literature on discretizing Langevin diffusion (Dalalyan 2016 Raginsky et al. 2017| Dalalyan 2017) primarily used for designing efficient sampling algorithms large fraction of them analyzing the above discretization. We will mostly rely on tools from Bubeck et al.
(0018). We show:
Lemma 17 Marie--Mariyama discretization). Let 2, follow the Langevin diffusion dz, -z + V2dB,, and let Pt denote the distribution of 2t.
Let 2 follow the continuous-timg Markov process determined by the Euler-Mariyama discretization scheme with discretization level hs given by equation 12 namely
dê = (=(eN//))a)a + v2dB,
(41)
Let us denote by P, the distribution of 2. Finally, let 20 in D satisfying || 21| S radd (D), with 'D defined as in Lemmal 13
Then, if = (2rad ( log(1/e) and = polypp, 1/d, 1/M, m, m, B), we have (Tv(Pr, Pr) Se
Proof. Let y/ follow the Reflected Langevin SDE (Definition 4). with g := L and region D. and with the initialization y0 = 20- Let dt. follow the continuous- time extension of the discretized reflected Langevin SDE given by equation [4 with g == L and region D), with the initial point do zg. Let Q and Q denote the respective distributions. Let Q denote the stationary distribution of yt-
From triangle inequality, we can decompose our error as
dTV Pr) < dTV (Qr, Pr) + dTv (Qr,Qr) + dTV Qr) We will bound each of the terms in turn.
(42)
For the first term, consider a coupling of y and = that uses the same Brownian motion for both processes, so long as neither has left D. and chooses an arbitrary coupling henceforth. By Lemma 6 we have
dTv(Qr, Pr) < Pr # yr]
< Pr(2T leaves D) + Pr(yr leaves D)
<//2
where the last inequality follows by Lemma
13
For the second term, we can further break it up, again by using the triangle inequality as
drv (Qr, Qr) S dTv (Ộr Q) dTV (Q, QT)
(43)
We will use a result about the discretization of reflected Langevin diffusion from Bubeck et al. 2018). Towards that, let us denote
L max V L(()]
(44)
2 = max RED D
2 L(=)|lop
(45)
23

---

Published as a conference paper at ICLR 2022
Using Theorem 1 from Bubeck al. 2018 if T (2ra log(1/c) and h
poly(e, 1/d,1/L, 1/ )) both terms in equation 43 are upper bounded by e/4. On the other hand, by equations equation 55 and equation 56 have
VV((2 < ||=|| + 32 Ja(z)) (12GG)) x/l
[| + rad(())
M rD)(
2
B²
Using Lemma 23 and the first term of the RHS from Lemma
we get
VL(=)]I v ||=|||
+ (1+
M
m²
2 2ED
36d
M
<o(v +0
+
2 2ED
Which follows using Lemma 24 Lemma we get
For the second order bound, a similar calculation as the proof of
[Mo(3)]lpp + - [IV'GIll(G(()) - zil
S +1+
3a
< 1
(M² + m²)
g2
o
82
Plugging the bounds above, we get that if T
(2rad(D)) log(1/e) and
then dTv (Qr, QT) s E/2.
Finally, for the third term, we will show that
dTV (Pr, Qr) S c/4
(46)
Towards that, by Lemma coupling the Gaussian noise to be the same for (Pthrrm and (Qthem. we have
dT (Pr,QT) Pr[Pr + Qr)
Pr [ & D)
By the definition of total variation distance, and Lemma 6 again, have
Pr[3t [ & DJ s dTv ((&therr) ((ahemt-(x)ettr)) + Pr[at [2], ze $ D)
By Lemma 13 and Lemma we have Pr[ [T], D) < e/4 and drV (L (ztherr) s
e/4 which proves equation 46
D.2 NEURAL SIMULATION OF ARITHMETIC OPERATIONS
The deep latent Gaussian will be an overall map from observables æ E IRd to latents z e Rd such that an approximate sample from the posterior p(=[x:).
In this section, we prove "simulation" lemmas that show how to combine neural networks for two functions f.g create neural network for some arithmetic operation applied to f. g (e.g. 9. f x etc.).
Recall, p: R R denotes the square activation function, i.e. p(x) x
24

---

Published as a conference paper at ICLR 2022
Lemma 18. If Rd R is neural network with M parameters and g R R is neural network with parameters, both with set of activation functions Σ, then wif weg can be represented by a neural network with ((M + N) parameters and set of activation functions funcciion Σ for any wi, W2 E IR.
Proof. We simply note that we can make network with one more layer than the maximum of the depth of and g that adds up the scaled outputs of f. g to produce wif + w2g. No additional nonlinearity is needed.
RR is neural network with M parameters and g: Rd - E is neural network with parameters, both with set of activation functions E, then for any w E RR v = wfg can be represented by neural network with (M N) parameters with set of activations E {p).
Lemma 19. f
functiooo
Proof. Noting zy = + -)= y) for all z, y E R, we can implement the multiplication
of scalars using two-layer neural network with (1) parameters using the p activation function. We
then proceed same for addition, adding one layer to multiply the outputs of f.g.
O
Lemma 20. IfG : T + R&d is represented by neural network with N parameters and differentiable activation function set Σ, given an x E R.d and E Rdd, one can compute for any 01, C2 E R.
2 + c2Ja(z)² (G(z)-2))
via a neural network with ((N))) parameters and activation functions EUN' Up), where y contains the derivatives of the activations in E.
Proof. Each coordinate of JG Rdd Rddd be written neural network with O (N)
parameters by Lemma 5) with activation functions Σ EY Each coordinate of G(z) I can be computed in ((N) parameters using lemma 18
Performing the multiplications needed for Ja(z)² (G(=) a) via Lemma 19 results in a network of size (N))) due to the d2 size of the Jacobian, and together with the addition of ejz (via (d)
parameters) results in the final bound of (NN?) on the parameters.
D.3 PROOF OF THEOREM
Finally, we can put all the ingredients together to prove Theorem
Proof of Theorem ! The deep latent Gaussian we construct will have all latent dimensions d as well as the output dimension d. The input will be e Red, the observable on which we want to carry out the inference. We will first create part for the GD simulation, and then one for the Langevin chain.
Using Lemma with 8 tarad (), if we run Gradient Descent for S O
1²
steps (using the bound rad(D) 2(Bva) from Lemma 13 we can get Dinit with 2i 2l <
(D).
Using Lemma 20, we can construct network Done with O ( (Nd*) parameters that executes single step of gradient descent. In the deep latent Gaussian we construct, we repeat Done with zero variance times to simulate all the steps of gradient descent and construct Zinit- The overall number
of parameters of the deep latent Gaussian so far then O [plly(d, b)) -N). Note, though the first variable 20 has unit variance, first step by multiplying by 0.
casily transform it to zero variance Gaussian simulate the
Starting with the random point zo. if we run the discretized Langevin dynamics given by equation [] for T/ h steps with T and as given by Lemma 17 we get by the error bounds of Lemma 17 and Lemma 2 and the triangle inequality:
drV (Prip(z (()()1)))) Se
which is the required overall bound.
25

---

Published as a conference paper at ICLR 2022
We further note that each step of the discretized Langevin dynamics can be simulated by layer of the deep latent Gaussian: by Lemma 20 we can construct a network Sone with O (Ndf) parameters that computes the next Langevin iterate. Choosing the variance to be 2h, then, accomplishes exactly the distribution of single step of the discretized dynamics. Given the choice of 7 and h, the number of steps we need to run is O (poly(1/e /e, d, 1/8)). Hence, the overall number of parameters required for simulating the discretized dynamics is O (poly(1/e, (1/e,,1/ddd d, N).. Finally, it's clear that the dependence on the layers comes through the (z(z)=(((()) -x) terms in the gradient and Langevin updates- so the weights for the deep latent Gaussian can be produced by network of size O (poly(1/c,, d, 1/5)- N) as well. The multiplication by can be implemented via the square activation p. Thus, the proof is finished
E PROOF OF THEOREM 2 LOWER BOUND
First, we observe the following proposition, which shows that the samples x with high probability lie near vertex of the hypercube [=1]d
Lemma 21 (Closeness to hypercube). A sample from the VAE with G(z) C(sgn(z)) and variance I satisfies, for all e
Pr[l - G(=)ll S 6c3vd 2 - exp((_ed
Proof. Since G(z) is Gaussian with variance 1, the claim follows via standard concentration of the norm of Gaussian.
Furthermore, we also have the following lemma, that shows that when æ is near vertex of the hypercube, the posterior p(z[ær) concentrates near the (sgn(zz)) that is, the pre-image of the nearest point to x on the hypereube.
Lemma 22 (Concentration near pre-image). Let x be such that ||x - sgn(x)]] S 63vd. Then,
Pr (=gg(()))(sgn(3) + C (s((n(())) S exp(-2d)
Proof. By Bayes rule, since p(sgn(=)) is uniform, we have
p(sgn(=)]æ² p(alsgn(2))
Consider then any E {+1]d, b + sgn(z). We have:
p(z(b) c 11/
m<r|sgn(2) 1/33 x- (=)]
S e -10d 10d
where the last inequality follows for 8 = (()/Vd) and small enough constant in the o(-) notation. Hence,
p(sgn(=){>)
=1
Σ p(blz)
bgng)(=
2 c p(x|sgn(2))
2 1 - 2d
Proof of Theorem The proof will proceed by reduction to Conjecture T Namely, C be Boolean circuit satisfying the one one-way-function assumptions in Conjecture C(sgn(=))
Let G be defined as G(2)
26

---

Published as a conference paper at ICLR 2022
Suppose that there is encoder E of size [(n), s.t. with probability at least e(d) over the choice of x (wrt to the distribution of G). we have (V(p(z(z). & 1/10, where g(2[x) is the distribution of the encoder when is supplied as input.
We will first show how to construct a neural sequential Gaussian C" which violates Conjecture in an "average sense": namely, for 1/poly(d) fraction of inputs ø E (+1)², with probability exp( -d) outputs the 2, s.t. 2 = C(2).
Subsequently we will remove the randomness - i.. we will produce from this deterministic and neural network, rather than a circuit - subsequently we will show how to remove both the randomness, and use simulate the neural networks using Boolean circuit.
This deep latent Gaussian C" receives a B E [+1]d and constructs (randomly) multiple samples R2 as
I + Ç ~~ (0,
(47)
Subsequently, it samples (multiple) 2 from E(2(x) and checks whether = C(sgn(=)). yes, 1).
outputs sgn(z). If for none of the samples z and sgn(z) ã, it outputs (1, ,,,,,..,))).
We will show that for 1/poly(d) fraction of inputs ā e [=1]4, with probability 1 - exp(- C" outputs the 2, s.t. I C()).
Note that is distributed according to the distribution of the generator G. (Since T is uniformly distributed on the hypercube.) Let E₁ be the event that dTV(((( (r), E(z)) S 10- E2 the event that
|| sgn || 63vd. By Assumption, Er[
e(d); by Lemma 21 for large enough d,
Pr[Eg] - d Hence, Pr(E, Eg]
<(d) 2 i.e. Pr[E, E2) 2 <(d)
2
2
Consider an x for which both events E₁ and Eg attain. From the the definition of TV distance and Lemma 22 we have
Pr Pro~E(s)o) (sg((2) + C- (=((((())) & Pr Premp(s) Præ-p(el)|(ggn(3) * C (sgn(z))) + 10
1
$ exp( (22(-22)))) + 10
1
5
Hence, we have
Pr. [1 (Pr (Pr (sgn(z) + C- (sgn(x()))) < 1/5)] 2 <(d)
By the tower rule of probability, we can rewrite this as
(0, [Praes(a(s) [1 (Pr (Pr== + C- (sgn( (2)gg(2)) [x) S 1/5)]] 2 c(d)/2
Let us denote the random variable
C A( Przvp(e)s) [1 [(s))((s)))))g((( # (sgn(x)) S 1/5)]
such that we have
Es[A(3)] 2 c(d)/2
By the reverse Markov inequality, it follows that
Pr[A(2)) s a] 1- e(d)/2
1-a
Taking <(d)/2 we get Pr(A(z) < c(d)/2) < 1 - (d)/4. Hence, with probability at least (d)/4 /4 over the choice of 2, we have
Pr Pr Papp(()))) (Pre + C (sgn( s 1 2 e(d)/2
As we indicated, C will repeat sampling x and z|.x multiple times. Let us denote by & the Gaussian
noise sampled in equation 47 and (s the Gaussian samples used in sampling ~ ((2[z).
Consider sampling { i E M.M. where M = 2 ( and (6- ", E [4], E [M]].
27

---

Published as a conference paper at ICLR 2022
where M' Slooo d). and for each i [M].] E [M'] outputs = - {i. and samples from ((2[2) using the randomness in {52 " "/=1. By Chermoff bounds, with probability 1 - exp(- at least one pair of indices (i, is such that the corresponding choice of random vectors results in choice of 2. such that ((sgm(=)) = f. Since the total number of possible strings 2 is 2", taking the constants M' sufficiently large, by union bound, there is pair (i.j), s.t. the corresponding vectors Si 1 " works for all ã. Hard-coding these into the weights of a neural network, we get deterministic neural network of size O(IC) + (d)), that with probability (d)//4 inverts C.
in M, M'
The only leftover issue is that E' is a neural network (hence, a continuous function), whereas we are trying to produce Boolean circuit. Conversions between neural networks applied Boolean inputs and Boolean circuits are fairly standard (see (Siegelmann (2012), Chapter 4, Theorem 6), but we include a proof sketch for completeness nevertheless.
First, we show that having logarithmic in L, W, M precision for the weights and activations in E suffices. For notational convenience, let us denote by N the maximum degree of any node in E. The proof is essentially the same as Lemma 4.2.1 in Siegelmann (2012)- the only difference is that our inputs are close to binary, but not exactly binary. Namely, for some constants ōw,, Sa to chosen, consider a network É I2d + Rdd which has the same architecture as E, and additionally:
The edge weights { } are produced by truncating the weights wayj to log(8..) significant bits, s.t. Vi,j [wa - Way S 8np
If a node in has activation o, the corresponding node E' has activation o' that truncates the value of a to log(5.) significant bits, s.t. Vx, (o(x) - o' (x)x S da.
Then, we claim that for nodes at depth from the input, denoting e(xx) and ((x) the function calculated by the node E and É respectively, we will show by induction:
(o(x) 6(x) - (LLNW))-(LLMMM. + 6a)
Let us denote by e, the maximum of [u(x) ((x) for any nodes v, ê at depth t. Suppose the claim is true for nodes at depth and consider node at depth + 1. Denoting by 2n ......:B0 Un the inputs to v, we have
[u(x) 0(x) = o
Σ (pvr(()
-o'
Σ (20i(())
(48)
$
Σ w.)x(z)
Σ (x))((z)
+ o { () -
Σ t. (x)
(49)
Σ [w:e;(x) (x);(x)) + da
(50)
L Σ (lw,))(1) w,),(z)) + - + 8
(51)
S L Σ (Wer + - + Sn
(52)
< LNW + LN + Ga
(53)
where equation 50 follows by Lipschitzness of a and equation 52 follows from the fact that the weights are bounded by W and the outputs v, are bounded by M.
Unfolding the recursion, we get
6++1 (INW) + +.,) S (INW) + 8,)
Given this estimate, we can choose 8w, 8,, s.t. the values at each output coordinate of E and È match. suffices to have (L M& + 5a) < which obtains when 5, = O [1 (LNW) i.e. it suffices to only keep O (dlog( I.NW) + log(M)) significant bits.
28

---

Published as a conference paper at ICLR 2022
Next, we show how to simulate E by Boolean circuit - this is essentially part of the proof of Lemma 4.2.2 in Siegelmann (2012). Namely, each pre-activation can be computed by a subcircuit of size O N (dlo)(L) + log()))) by the classic carry-lookahead algorithm for addition. Since only require log( 6a) bits of accuracy for the activation function, and each activation is most M (so we need (log M) bits for the integer part), we need Olog M + log(ō,)) nodes for the activation function.
Hence, we can simulate F by a Boolean circuit which is at most a factor of log(M))) log()),,o((W) lo)( Since W, M o(exp(poly(d))). the size of the size of
poly (N, log(T)) the resulting Boolean circuit is still poly(d). Thus, we've constructed polynomial-sized circuit which inverts the one-way- permuttaann,nnnn, thus violating Conjecture
F TECHNICAL LEMMAS
This section contains several equations and calculational lemmas that repeatedly the proofs of Theorem [
F.1 BOUND ON ||
Recall that we defined the inverse point 2 for a given E I24 in equation equation As mentioned earlier, due to bijectivity, on the norm of & using our assumptions, which will be useful in various places in the proof.
unique and satisfied G(2) x. Further, can easily prove bound
Lemma 23. 2 defined as in equation 4 with G that satisfies Assumption
! is such that
|0]||
|||||
m
Proof. Using strong invertibility from Assumption and centering from Assumption 3 we can write
||
G(O) ||G(2) - G(O) 2 m - 2 - O|
-
|
(54)
m
L
F.2 HIGH PROBABILITY BOUND ON ||>|||
Lemma 24 (High-probability bound on | With following the density from Definition 7 witt di = d, = d), s.f. G satisfies Assumption
we have that
| 12(M + B)vd
w.p. 2-xxp((-4d)
Proof: The density of x is defined by the latent Gaussian. Let's denote the error term as ((0,82T) We have
G(z) +e |||||| < [G(= ||e|| | < M||=|| + ||l||
(Where we used assumption 2p. Now and e follow zero eero-mean Gaussian densities, with variances
and 88 respectively. Using standard gaussian tail bounds (similar to lemma 21 with the required claim.
2), we get
Remark: Since we work under the setting 3 < O(1) from equation we can use |||||| < O(Vd) with probability ed)()
29

---

Published as a conference paper at ICLR 2022
F.3 CHARACTERIZING LOSS NEAR 2
We need to understand how and VL behaves near for several claims in the proofs. We will use Taylor expansion, bounding the contribution of higher order terms.
F.3.1
EXPRESSIONS FOR DERIVATIVES
Using equation equation
we first calculate the expressions of the derivatives as
L((z) = B
(G(=))(G()))) -x)
(55)
L') I
B² Je(z)
Ja(z) Jc(z) E (3((()) -x;)
(56)
iE|d
At the inverse point since G(8) = z, we have:
L(#) = ||
( =
(57)
L2) = T+ J 2
Since (²) Ž the function [(2) is strongly convex in the neighbourhood of é.
F.3.2 BOUND ON 3RD DERIVATIVE OF L
To show the behaviour of V L. around é, we will first bound the norm of the 3rd order derivatives of I. below.
Lemma 25 (Bounding the 3rd derivative of L). For all z E RR., it holds that
VdM
[+=))) op S g2
(3vaMz + Mall=- - #1)
Proof. An elementary calculation shows that
1 ,32
V2L(2)
3 Σ
VG.(2) 8T V²G Σ (G(()) 21)
(58)
KE(M
EE|4
Here, the tensor product 8T multiplies elements from Rd and Raxd give elements in Rdxdxd We subscript with to avoid confusion with the kronecker product.
Then, have:
L
5
3
Σ VG+(2) 8T V-G.(2)
(G(()))))(()) - -z:)
(triangle inequality)
32
iE|d
KE(d
op
op
<
3
(G.(z) 8T v'G,(>)
GG((z) zi 1 G
32
op
EE|d]
EE/
3.
[=)(
max ic[4
V² + +[[((=) =/11
max
v (+(()))
13
2E|d
iE[d]
(1)
1
(3 Vd. [|Ja(=)]le
| + Vd. [[G(2) -ll |
82
(2)
1
3d MM + Vd- MM3 || - 2
32
In (1) we use Eiels lasl I Vk. v EiE(h) of the first part of both the terms; and the fact that
Vi [d], [T()) < ||]||op for any tensor T (where T(2) denotes sub-tensor) the second part of both terms. This fact follows from the sup-definition of l, norm on tensors from (Lim) (005). In (2), Assumption 2 well A|] Va || for A being
matrix.
30

---

Published as a conference paper at ICLR 2022
F.3.3 PERTURBATION BOUND OF VL
Using the above, we show the Taylor expansion result for the gradient of L: Lemma 26 (Perturbation of VL). For all IR., it holds that
1 Jo())
VL(z)= [+
(z (z-2) 2) + (x)(2)
where [|
JaM 23
(3vāM2 + Mall= #|l) ||| =
Proof. We Taylor expand VL around a. Using equation equation 57 we get
(L(z) ( L2) (2 2) + Rv((2)
1 (c(3) Jc( (= - 2) + Rx2(2)
+ (
(59)
To bound the norm of the remainder term, we note that
[x)(22)
2 [ amsa
1
||2 2|1
For Zmid = Emidd (1 tmidd 2 for some tmid E [0, 1]. And for the third derivative, we use lemma 25
directly to get
VdM
[ S 2
(3vdM₃ + Mallz - -112
-211
(60)
This finishes the proof.
G REMARK ON ACTIVATION FUNCTIONS
The choice of activation functions in our results is largely a matter of convenience. Using standard techniques from approximation theory, e.g. Hornik (1991): Yarotsky (2017), one can approximate neural network with one choice of nonlinearity via a (comparably sized) neural network with another choice of nonlinearity, under very mild conditions on the nonlinearities. Crucially, this simulation only increases the size by dimension-indeeendeen factor. This result frees us (for purposes of deriving an expressibility result) work with activation functions chosen for mathematical convenience and produce results that hold without loss of generality.
For instance, if we wished use ReLU activations, we can use the following lemma. We note that this proof is almost verbatim the same as the proof of Lemma 1.3 in Telgarsky (2017) and proofs for other activations like sigmoid or tanh can be written completely analogously.
Lemma 27. Let Q S [-M, MJ and let G1 [-M, layers and n parameters, s.I., the weights W for each layer i and node j in G1 are bounded as, i.e. Vi,j Σx [W/2] B. Furthermore, assume that the activation functions used G1 belong to the set E, s.s. all functions o IR R satisfy supze[- B.MBB.BB... of M. Then there exists a neural
IR be neural network with at most (
network G2 with ReLU activation and O (LBY'BM log( (LBYIBM parameters, such that for all MU (z(()) G2(2)) S.
Proof. For any a E, from Theorem in Yarotsky (2017) it follows that there exists neural network R with ReLU activations and O LBM
log(
L.MM
parameters such that SuP.s[[B-M,.-M] [a()
d
R(x)| <'.
We will construct the network G2 by replacing each activation in G2 with the corresponding net- work R as given by the result above with c/l. Note, this network is at most a factor of O (LB) log( (LBY"IBM) )) bigger than G1, as the lemma requires.
We will prove the claim of the lemma by induction on I. More precisely, will show (by induction) that for each node at layer i, the network G2 calculates a function that is LiB) away in to norm from the corresponding node in G1, and the inputs the node are in [- BM, BM).
31

---

Published as a conference paper at ICLR 2022
For the base case since the input [-M, MJ the result follows by Theorem in [Yarotsky (2017)].
We proceed to the inductive claim. Let (x) denote the vector valued mapping computed by the nodes at layer i, and let (z( be the corresponding vector Gz. As inductive hypothesis. assume that (x)) H Hn(œ))>> I (LB)'ic' for all E [-M, Mf and ||H( I M as well as [[ I M. Therefore, for the jth node in layer (& + 1) in network G₁ we have [W7 [x)) S [Willi]|H(=]||>
BM and is bounded by M this interval, so
have ( ( S M. Along with the bound on the activations, the part of the inductive hypothesis about the size of the input is proven. To prove the error bound, we have:
+ Hx)) R(W] HR(2)) & (W)](()) - (W HR(Z)) (w3 Hn(x)) -R(3- HR(z))
S L/W
- - +e' (i
This finishes the proof of the inductive step, and thus the lemma.
32


Reviews:
[{"review_id": "WRzRG2QPD9", "reviewer": "Reviewer_hddw", "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": "This is a purely theoretical paper trying to solve a very interesting and important question, which is generally a good paper.  However, I still have some concerns and questions about it.\n\nPros:\n1. This paper is well-written and intuitive. It's difficult to achieve that for a purely theoretical paper.\n2. The proofs are reasonable. Sorry I only checked the main theorem and some lemmas and didn't find the time to delve into the proofs in the appendix.\n\nConcerns and Questions:\n1. The inference model is assumed to be a deep latent Gaussian model, which is not the case for VAEs. The structure looks similar to some hierarchical VAE but it's not the same. This heavily limits the usage of the conclusion in usual VAEs.\n2. In remark 3, the authors mention that the case for layerwise invertible models is very simple. They argue that some convolutional NN contains operations that increase and then decrease the dimensions, which makes layers not invertible and necessitates the invertible rather than the layerwise invertible assumption. But why not regard the two layers as a single layer, which becomes invertible again? I guess it is not difficult to get a reverse of such a layer.\n3. The paper mentions that Learning deep generative models more generally is harder for data on low-dimensional manifolds. This paper (https://arxiv.org/abs/2106.13746) gives some explanation why deep generations models can deal with some manifolds easily but fail on others. Can we use the method in your paper to analyze the problem as well?", "summary_of_the_paper": "The paper answers the question how complex inference models need to be to accurately estimate posterior distributions. The conclusion is when a latent Gaussian model with N parameters satisfies (1) strong invertibility, (2) 3-th smoothness, the posterior can be approximated by a deep latent Gaussian model with O(N) parameters. A special case is also given to show that strong invertibility is necessary to the conclusion.", "summary_of_the_review": "The paper is well-written and the conclusions are reasonable. But I still have some concerns about the too strong assumptions of the main theorem, which might limit the usage of the conclusion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Po5xzm4TDvC", "reviewer": "Reviewer_agVY", "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": "Unfortunately, the exploration made appears to me mostly about something else. This whole paper doesn’t read like a paper about VAEs, or about DL, but rather about applying a conjecture by Katz & Lindell (2020), having to do with Boolean circuits, to the situation of VAEs.\n\nIn that regard, the situation studied about VAEs feels rather artificial because in practice we never deal with random mappings or with worst-case distributions. The whole edifice of deep learning is predicated upon assumption that patterns in the experimental data will play nicely with the inductive bias of neural networks. This does not invalidate the study of worst-case scenarios, but it makes it less interesting.\n\nIn fact, the whole paper rests upon the aforementioned conjecture coming from the world of cryptography, for which not much background is given. For all the reader can tell, that conjecture cited with reference to a book that came out in 2020, could be false. That would make this very paper completely void.\n\nAfter having said all that, I’ll admit to my lack of familiarity with some of the techniques used by the authors despite being knowledgeable about VAEs.", "summary_of_the_paper": "The authors of the paper start from a great initial question that connects the complexity of the encoder and generator of a VAE. It is reasonable to suspect that the complexity of one mapping would have an effect on the complexity of the other mapping.", "summary_of_the_review": "The paper starts with a good inquiry, but the answer provided is unsatisfying. It relies on a conjecture from another field which, even if proven true, would not make it all that useful.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "HxY8J6IkwB3", "reviewer": "Reviewer_8CZc", "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": "Pros:\n- The idea of using Boolean permutations as a proof method in network analysis context in the presented manner appears novel to me.\n- The said idea might well be useful to prove other network properties.\n- The mathematics, to the extent that I could follow it, seems correct.\n- The paper does seem to prove the claimed complexity properties of inference models in the \"approximately invertible\" and the \"non-invertible\" cases.\n- The paper puts together an impressive amount of math to prove the points, with extensive details in the supplement (the latter of which, however, I did not have time to evaluate in detail)\n\nCons:\n- The paper suffers from confusing structure and sloppy language at critical points. It starts with sweeping questions such as 'How to choose the architecture' and 'When is inference (much) harder than generation', but then actually focuses only on very specific and narrow parts of those wide questions. The wide questions are then followed by a moderately heavy load of math. The paper reads as a string of theorems and remarks, where the reader has to jump around to understand how the theorems relate to the overall points of the paper. The proof is somewhat complicated and it is difficult to confirm the derivation holds at every step (though I admit this final point may be a failure from my side).\n- VAE basics, for example, are given considerable amount of space, but there is no ending summary or Conclusion to draw things together, which adds to the impression that the ultimate significance of the work is not clear.\n- There is no empirical part nor clear indication of empirical usefulness of the results. Both theorem 1 and theorem 2 prove the *existence* of networks that satisfy the conditions. Could the authors help me to understand the connection to empirical significance, or should we simply approach this as a mathematical exercise?\n- The final sweeping claim in the introduction, namely that the paper lends theoretical support to the idea that \"learning deep generative models more generally is harder when data lies in a low-dimensional manifold\" just seems inappropriate to me. I'm not sure the whole notion of 'learning more generally when data lies in a low-dimensional manifold' makes sense as an expression. Being familiar with the cited (Arjovsky, 2017), I believe I understand what the authors mean, but I don't see how their results really lend the said support to that idea. Could the authors explain this, or point to where is this explained?\n- In terms of impact, first, it is not surprising that the complexity requirements of inference and generative subnetworks are similar in the typical case, and in fact, the authors acknowledge this, but present the value in this work for providing theoretical foundation for this \"empirical wisdom\". I find this work somewhat valuable in this regard, but I did not quite understand, do the theorems actually give us a way of telling, for a given network, whether it has the strongly invertible nature or not?\n- Some of the citations are not entirely appropriate. E.g. in the first paragraph, the ideas cited for both (Betherlot,2018) and (Shen,2020) have certainly been presented before those papers came out; e.g., the modification of latent space has been investigated at least since [1] in a similar context.\n- The very place in the text that could illuminate the significance of the results (Sec. 1) reads as \"We identify...an aspect...: a notion of approximate bijectivity of the mean of the generative direction. We prove that under this assumption...\" Forgive me, but what does it mean that one 'identifies an aspect' which turns into 'notion', and then 'proves [things] under this assumption'? This is just unnecessarily fuzzy, in striking contrast with the mathematical precision shown in some other parts of the paper.\n- The results of Lipton & Tripathi (2017) do not show that \"these architectures are invertible in practice\" as the authors state. What they may have shown is that those architectures are *sometimes* invertible in practise. E.g. in GAN context, AFAIK the general inversion of CNNs is an open research problem. If I am wrong, I ask the authors to explain why.\n\n[1] Salimans et al. 2016, Improved Techniques for Training GANs.\n\n", "summary_of_the_paper": "This purely mathematical paper investigates the important question of how does the necessary level of complexity of an inference subnetwork depend on the the complexity of the corresponding generative subnetwork, in a VAE model. The paper introduces a specific measure of invertibility, and uses it to show that a generative subnetwork that is sufficiently strongly invertible only requires an inference model at similar complexity, while some \"non-invertible\" generative subnetworks will require an exponentially more complex inference subnetwork. The paper provides a lengthy and comprehensive proof of both.", "summary_of_the_review": "The proofs in the paper appear correct, and at first glance, they appear relevant to generative models research community.\nHowever, upon closer look, despite the commendable theoretical work, the paper seems to amount to proving the *existence* of a network of certain complexity, in the invertible case, and the *existence* of a generative subnetwork that only allows inference networks with pathological (exponentially growing) complexity. Without any guidance of how one could construct the networks under the said conditions, or measure how far we are from meeting those conditions, I am worried that the paper boils down into a mathematical exercise without considerable impact in this line of research.\n\nI also had concerns about the sloppy wording of the claims in the introductory section, and the structure of the paper in terms of the order of how things are presented, and the lack of clear bottom line.\n\nIn combination, I lean towards rejection, but I may improve my score if the authors can convince me of the significance of the theorems, and if they manage a considerable rewrite of the introduction section. Given the considerable theoretical weight and intellectual import of the paper, I would encourage the authors to do so.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers viewed this paper as marginally above the acceptance threshold (6).

Most of the initial concerns of reviewers were around (a) the applicability of the theory to actual practical use cases and networks, and (b) the presentation and framing of the work, and scope of its results. There were fairly detailed responses from the authors: two of the three reviewers increased their scores after the author response. There's still some lingering questions as to how "real-world" relevant the theory is, but the consensus at this point is to accept the paper.

My primary concern for acceptance would be that the proofs techniques are based on Boolean circuits, and none of the reviewers (nor the AC) are particularly familiar with this, and thus the proofs in the appendix have been only lightly reviewed. The "impression" of all reviewers is of correctness.
Decision: Accept (Poster)