Year: 2020

Abstract:
In supervised learning, it is known that overparameterized neural networks with one hidden layer provably and efficiently learn and generalize, when trained using Stochastic Gradient Descent (SGD). In contrast, the benefit of overparameterization in unsupervised learning is not well understood. Normalizing flows (NFs) learn to map complex real-world distributions into simple base distributions and constitute an important class of models in unsupervised learning for sampling and density estimation. In this paper, we theoretically and empirically analyze these models when the underlying neural network is one hidden layer overparametrized network. On the one hand, we provide evidence that for a class of NFs, overparametrization hurts training. On the other hand, we prove that another class of NFs, with similar underlying networks, can efficiently learn any reasonable data distribution under minimal assumptions. We extend theoretical ideas on learning and generalization from overparameterized neural networks in supervised learning to overparameterized normalizing flows in unsupervised learning. We also provide experimental validation to support our theoretical analysis in practice.

heading: 1 INTRODUCTION
text: Neural network models trained using simple first-order iterative algorithms have been very effective in both supervised and unsupervised learning. Theoretical reasoning of this phenomenon requires one to consider simple but quintessential formulations, where this can be demonstrated by mathematical proof, along with experimental evidence for the underlying intuition. First, the minimization of training loss is typically a non-smooth and non-convex optimization over the parameters of neural networks, so it is surprising that neural networks can be trained efficiently by first-order iterative algorithms. Second, even large neural networks whose number parameters are more than the size of training data often generalize well with a small loss on the unseen test data, instead of overfitting the seen training data. Recent work in supervised learning attempts to provide theoretical justification for why overparameterized neural networks can train and generalize efficiently in the above sense.
In supervised learning, the empirical risk minimization with quadratic loss is a non-convex optimization problem even for a fully connected neural network with one hidden layer of neurons with ReLU activations. Around 2018, it was realized that when the hidden layer size is large compared to the dataset size or compared to some measure of complexity of the data, one can provably show efficient training and generalization for these networks, e.g. Jacot et al. (2018); Li & Liang (2018); Du et al. (2018); Allen-Zhu et al. (2019); Arora et al. (2019). Of these, Allen-Zhu et al. (2019) is directly relevant to our paper and will be discussed later.
The role of overparameterization, and provable training and generalization guarantees for neural networks are less well understood in unsupervised learning. Generative models or learning a data distribution from given samples is an important problem in unsupervised learning. Popular generative models based on neural networks include Generative Adversarial Networks (GANs) (e.g., Goodfellow et al. (2014)), Variational AutoEncoders (VAEs) (e.g., Kingma & Welling (2014)), and Normalizing Flows (e.g., Rezende & Mohamed (2015)). GANs and VAEs have shown impressive capability to generate samples of photo-realistic images but they cannot give probability density estimates for new data points. Training of GANs and VAEs has various additional challenges such as mode collapse, posterior collapse, vanishing gradients, training instability, etc. as shown in e.g. Bowman et al. (2016); Salimans et al. (2016); Arora et al. (2018); Lucic et al. (2018).
In contrast to the generative models such as GANs and VAEs, when normalizing flows learn distributions, they can do both sampling and density estimation, leading to wide-ranging applications as mentioned in the surveys by Kobyzev et al. (2020) and Papamakarios et al. (2019). Theoretical understanding of learning and generalization in normalizing flows (more generally, generative models and unsupervised learning) is a natural and important open question, and our main technical contribution is to extend known techniques from supervised learning to make progress towards answering this question. In this paper, we study learning and generalization in the case of univariate overparameterized normalizing flows. Restriction to the univariate case is technically non-trivial and interesting in its own right: univariate ReLU networks have been studied in recent supervised learning literature (e.g., Savarese et al. (2019), Williams et al. (2019), Sahs et al. (2020) and Daubechies et al. (2019)). Multidimensional flows are qualitatively more complex and our 1D analysis sheds some light on them (see Sec. 4). Before stating our contributions, we briefly introduce normalizing flows; details appear in Section 2.
Normalizing Flows. We work with one-dimensional probability distributions with continuous density. The general idea behind normalizing flows (NFs), restricted to 1D can be summarized as follows: Let X ∈ R be a random variable denoting the data distribution. We also fix a base distribution with associated random variable Z which is typically standard Gaussian, though in this paper we will work with the exponential distribution as well. Given i.i.d. samples of X , the goal is to learn a continuous strictly monotone increasing map fX : R→ R that transports the distribution of X to the distribution of Z: in other words, the distribution of f−1X (Z) is that of X . The learning of fX is done by representing it by a neural network and setting up an appropriate loss function.
The monotonicity requirement on f which makes f invertible, while not essential, greatly simplifies the problem and is present in all the works we are aware of. It is not clear how to set up a tractable optimization problem without this requirement. Since the function represented by standard neural networks are not necessarily monotone, the design of the neural net is altered to make it monotone. For our 1D situation, one-hidden layer networks are of the form N(x) = ∑m i=1 aiσ(wix+ bi), where m is the size of the hidden layer and the ai, wi, bi are the parameters of the network.
We will assume that the activation functions used are monotone. Here we distinguish between two such alterations: (1) Changing the parametrization of the neural network. This can be done in multiple ways: instead of ai, wi we use a2i , w 2 i (or other functions, such as the exponential function, of ai, wi that take on only positive values) (Huang et al., 2018; Cao et al., 2019). This approach appears to be the most popular. In this paper, we also suggest another related alteration: we simply restrict the parameters ai, wi to be positive. This is achieved by enforcing this constraint during training. (2) Instead of using N(x) for f(x) we use φ(N(x)) for f ′(x) = dfdx , where φ : R→ R
+ takes on only positive values. Positivity of f ′ implies monotonicity of f . Note that no restrictions on the parameters are required; however, because we parametrize f ′, the function f needs to be reconstructed using numerical quadrature. This approach is used by Wehenkel & Louppe (2019).
We will refer to the models in the first class as constrained normalizing flows (CNFs) and those in the second class as unconstrained normalizing flows (UNFs).
Our Contributions. In this paper, we study both constrained and unconstrained univariate NFs theoretically as well as empirically. The existing analyses for overparametrized neural networks in the supervised setting work with a linear approximation of the neural network, termed pseudo network in Allen-Zhu et al. (2019). They show that (1) there is a pseudo network with weights close to the initial ones approximating the target function, (2) the loss surfaces of the neural network and the pseudo network are close and moreover the latter is convex for convex loss functions. This allows for proof of the convergence of the training of neural network to global optima. One can try to adapt the approach of using a linear approximation of the neural network to analyze training of NFs. However, one immediately encounters some new roadblocks: the loss surface of the pseudo networks is non-convex in both CNFs and UNFs.
In both cases, we identify novel variations that make the optimization problem for associated pseudo network convex: For CNFs, instead of using a2i , w 2 i as parameters, we simply impose the constraints ai ≥ and wi ≥ for some small constant . The optimization algorithm now is projected SGD, which in this case incurs essentially no extra cost over SGD due to the simplicity of the positivity constraints. Apart from making the optimization problem convex, in experiments this variation
slightly improves the training of NFs compared to the reparametrization approaches, and may be useful in practical settings.
Similarly, for UNFs we identify two changes from the model of Wehenkel & Louppe (2019) that make the associated optimization problem convex, while still retaining empirical effectiveness: (1) Instead of Clenshaw–Curtis quadrature employed in Wehenkel & Louppe (2019) which uses positive and negative coefficients, we use the simple rectangle quadrature which uses only positive coefficients. This change makes the model somewhat slow (it uses twice as many samples and time to get similar performance on the examples we tried). (2) Instead of the standard Gaussian distribution as the base distribution, we use the exponential distribution. In experiments, this does not cause much change.
Our results point to a dichotomy between these two classes of NFs: our variant of UNFs can be theoretically analyzed when the networks are overparametrized to prove that the UNF indeed learns the data distribution. To our knowledge, this is the first “end-to-end” analysis of an NF model, and a neural generative model using gradient-based algorithms used in practice. This proof, while following the high-level scheme of Allen-Zhu et al. (2019) proof, has a number of differences, conceptual as well as technical, due to different settings. E.g., our loss function involves a function and its integral estimated by quadrature.
On the other hand, for CNFs, our empirical and theoretical findings provide evidence that overparametrization makes training slower to the extent that models of similar size which learn the data distribution well for UNFs, fail to do so for CNFs. We also analyze CNFs theoretically in the overparametrized setting and point to potential sources of the difficulty. The case of moderatesized networks, where training and generalization do take place empirically, is likely to be difficult to analyze theoretically as presently this setting is open for the simpler supervised learning case. We hope that our results will pave the way for further progress. We make some remarks on the multidimensional case in Sec. 4. In summary, our contributions include:
• To our knowledge, first efficient training and generalization proof for NFs (in 1D). • Identification of architectural variants of UNFs that admit analysis via overparametrization. • Identification of “barriers” to the analysis of CNFs.
Related Work. Previous work on normalizing flows has studied different variants such as planar and radial flows in Rezende & Mohamed (2015), Sylvester flow in van den Berg et al. (2018), Householder flow in Tomczak & Welling (2016), masked autoregressive flow in Papamakarios et al. (2017). Most variants of normalizing flows are specific to certain applications, and the expressive power (i.e., which base and data distributions they can map between) and complexity of normalizing flow models have been studied recently, e.g. Kong & Chaudhuri (2020) and Teshima et al. (2020). Invertible transformations defined by monotonic neural networks can be combined into autoregressive flows that are universal density approximators of continuous probability distributions; see Masked Autoregressive Flows (MAF) Papamakarios et al. (2017), UNMM-MAF by Wehenkel & Louppe (2019), Neural Autoregressive Flows (NAF) by Huang et al. (2018), Block Neural Autoregressive Flow (B-NAF) by Cao et al. (2019). Unconstrained Monotonic Neural Network (UMNN) models proposed by Wehenkel & Louppe (2019) are particularly relevant to the technical part of our paper.
Lei et al. (2020) show that when the generator is a two-layer tanh, sigmoid or leaky ReLU network, Wasserstein GAN trained with stochastic gradient descent-ascent converges to a global solution with polynomial time and sample complexity. Using the moments method and a learning algorithm motivated by tensor decomposition, Li & Dou (2020) show that GANs can efficiently learn a large class of distributions including those generated by two-layer networks. Nguyen et al. (2019b) show that two-layer autoencoders with ReLU or threshold activations can be trained with normalized gradient descent over the reconstruction loss to provably learn the parameters of any generative bilinear model (e.g., mixture of Gaussians, sparse coding model). Nguyen et al. (2019a) extend the work of Du et al. (2018) on supervised learning mentioned earlier to study weakly-trained (i.e., only encoder is trained) and jointly-trained (i.e., both encoder and decoder are trained) two-layer autoencoders, and show joint training requires less overparameterization and converges to a global optimum. The effect of overparameterization in unsupervised learning has also been of recent interest. Buhai et al. (2020) do an empirical study to show that across a variety of latent variable models and training algorithms, overparameterization can significantly increase the number of recovered ground truth latent variables. Radhakrishnan et al. (2020) show that overparameterized autoencoders
and sequence encoders essentially implement associative memory by storing training samples as attractors in a dynamical system.
Outline. A brief outline of our paper is as follows. Section 2 contains preliminaries and an overview of our results about constrained and unconstrained normalizing flows. Appendix B shows the existence of a pseudo network whose loss closely approximates the loss of the target function. Appendix C shows the coupling or closeness of their gradients over random initialization. Appendices D and E contain complete proofs of our optimization and generalization results, respectively. Section 3 and Appendix G contain our empirical studies towards validating our theoretical results.

heading: 2 PRELIMINARIES AND OVERVIEW OF RESULTS
text: We confine our discussion to the 1D case which is the focus of the present paper. The goal of NF is to learn a probability distribution given via i.i.d. samples data. We will work with distributions whose densities have finite support, and assumed to be [−1, 1], without loss of generality. Let X be the random variable corresponding to the data distribution we want to learn. We denote the probability density (we often just say density) of X at u ∈ R by pX(u). Let Z be a random variable with either standard Gaussian or the exponential distribution with λ = 1 (which we call standard exponential). Recall that the density of the standard exponential distribution at u ∈ R is given by e−u for u ≥ 0 and 0 for u < 0.
Let f : R→ R be a strictly increasing continuous function. Thus, f is invertible. We use f ′(x) = dfdx to denote the derivative. Let pf,Z(·) be the density of the random variable f−1(Z). Let x = f−1(z), for z ∈ R. Then by the standard change of density formula using the monotonicity of f gives
pf,Z(x) = pZ(z)f ′(x). (2.1)
We would like to choose f so that pf,Z = pX , the true data density. It is known that such an f always exists and is unique; see e.g. Chapter 2 of Santambrogio (2015). We will refer to the distribution of Z as the base distribution. Note that if we can find f , then we can generate samples of X using f−1(Z) since generating the samples of Z is easy. Similarly, we can evaluate pX(x) = pZ(f−1(z))f ′(x) using (2.1). To find f from the data, we set up the maximum log-likelihood objective:
max f
1
n n∑ i=1 log pf,Z(xi) = max f 1 n [ n∑ i=1 log pZ(f(xi)) + n∑ i=1 log f ′(xi) ] , (2.2)
where S = {x1, . . . , xn} ⊂ R contains i.i.d. samples of X , and the maximum is over continuous strictly increasing functions. WhenZ is standard exponential, the optimization problem (2.2) becomes
min f L(f, S), where L(f, S) =
1
n ∑ x∈S L(f, x) and L(f, x) = f(x)− log f ′(x). (2.3)
A similar expression, with f(x)2/2 replacing f(x), holds for the standard Gaussian. We denote the loss for standard Gaussian as LG(f, x).
Informally, one would expect that as n→∞, for the optimum f in the above optimization problems pf,Z → pX . To make the above optimization problem tractable, instead of f we use a neural network N . We consider one-hidden layer neural networks with the following basic form which will then be modified according to whether we are constraining the parameters or the output.
N(x) = m∑ r=1 ar0 ρ ((wr0 + wr)x+ (br + br0)) . (2.4)
Here m is the size of the hidden layer, ρ : R→ R is a monotonically increasing activation function, the weights ar0, wr0, br0 are the initial weights chosen at random according to some distribution, and wr, br are offsets from the initial weights. We will only train the wr, br and the ar0 will remain frozen to their initial values.
Let θ = (W,B) ∈ R2m denote the parameters W = (w1, w2, ..., wm) ∈ Rm and B = (b1, b2, ..., bm) ∈ Rm of the neural network. We use Stochastic Gradient Descent (SGD) to update the parameters of neural networks. Denote by θt = (W t, Bt) with W t = (wt1, w t 2, ..., w t m) and
Bt = (bt1, b t 2, ..., b t m) the parameters at time step t = 1, 2, . . ., and the corresponding network by Nt(x). The SGD updates are given by θt+1 = θt − η∇θLs(Nt, xt) where η > 0 is learning rate, and Ls(Nt, xt) is a loss function, and xt ∈ S is chosen uniformly randomly at each time step. For supervised learning where we are given labeled data {(x1, y1), . . . , (xn, yn)}, one often works with the mean square loss Ls(Nt) = 1n ∑n i=1 Ls(Nt, xi) with Ls(Nt, xi) = (Nt(xi)− yi)2.
We now very briefly outline the proof technique of Allen-Zhu et al. (2019) for analyzing training and generalization for one-hidden layer neural networks for supervised learning. (While they work in a general agnostic learning setting, for simplicity, we restrict the discussion to the realizable setting.) In their setting, the data x ∈ Rd is generated by some distribution D and the labels y = h(x) are generated by some unknown function h : Rd → R. The function h is assumed to have small “complexity” Ch which in this case measures the required size of neural network with smooth activations to approximate h.
The problem of optimizing the square loss is non-convex even for one-hidden layer networks. AllenZhu et al. (2019) instead work with pseudo network, P (x) which is the linear approximation of N(x) given by the first-order Taylor expansion of the activation:
P (x) = m∑ r=1 ar0 (σ(wr0x+ br0) + σ ′(wr0x+ br0) (wrx+ br)) . (2.5)
Similarly to Nt we can also define Pt with parameters θt. They observe that when the network is highly overparameterized, i.e. the network size m is sufficiently large compared to Ch, and the learning rate is small, i.e. η = O(1/m), SGD iterates when applied to L(Nt) and L(Pt) remain close throughout. Moreover, the problem of optimizing L(P ) is a convex problem in θ and thus can be analyzed with existing methods. They also show an approximation theorem stating that with high probability there are neural network parameters θ∗ close to the initial parameters θ0 such that the pseudo network with parameters θ∗ is close to the target function. This together with the analysis of SGD shows that the pseudo network, and hence the neural network too, achieves small training loss. Then by a Rademacher complexity argument they show that the neural network after T = O(Ch/ 2) time steps has population loss within of the optimal loss, thus obtaining a generalization result.
We will now describe how to obtain neural networks representing monotonically increasing functions using the two different methods mentioned earlier, namely CNFs and UNFs.

heading: 2.1 CONSTRAINED NORMALIZING FLOW
text: Note that if we have ar0 ≥ 0, wr0 + wr ≥ 0 for all r, then the function represented by the neural network is monotonically increasing. We can ensure this positivity constraint by replacing ar0 and wr0+wr by their functions that take on only positive values. For example, the function x 7→ x2 would give us the neural network N(x) = ∑m r=1 a 2 r0 ρ((wr0 +wr)
2x+ br0 + br). Note that ar0, wr0 +wr and br0 + br have no constraints, and so this network can be trained using standard gradient-based algorithms. But first we need to specify the (monotone) activation ρ. Let σ(x) = x I [x ≥ 0] denote the ReLU activation. If we choose ρ = σ, then note that in (2.3) we have
log f ′(x) = log ∂N(x)
∂x = log ( m∑ r=1 a2r0 (wr0 + wr) 2I [ (wr0 + wr) 2x+ br0 + br ≥ 0 ]) .
This is a discontinuous function in x as well as in wr and br. Gradient-based optimization algorithms are not applicable to problems with discontinuous objectives, and indeed this is reflected in experimental failure of such models in learning the distribution. By the same argument, any activation that has a discontinuous derivative is not admissible. Activations which have continuous derivative but are convex (e.g. ELU(x) given by ex − 1 for x < 0 and x for x ≥ 0)) also cannot be used because then N(x) is also a convex function of x, which need not be the case for the optimal f . The oft-used activation tanh does not suffer from either of these defects. Pseudo network with activation tanh is given by
P (x) = m∑ r=1 a2r0 ( tanh(w2r0x+ br0) + tanh ′(w2r0x+ br0) (( w2r + 2wr0wr ) x+ br )) .
Note that P (x) is not linear in the parameters θ. Hence, it is not obvious that the loss function for the pseudo network will remain convex in parameters; indeed, non-convexity can be confirmed in experiments. A similar situation arises for exponential parameterization instead of square.
To overcome the non-convexity issue, we propose another formulation for constrained normalizing flows. Here we retain the form of the neural network as in (2.4), but ensure the constraints ar0 ≥ 0 and wr0 ≥ 0 by the choice of the initialization distribution and wr0 + wr ≥ 0 by using projected gradient descent for optimization.
N(x) = m∑ r=1 ar0 tanh ((wr0 + wr)x+ (br + br0)) , with constraints wr0 + wr ≥ , for all r.
Here, > 0 is a small constant ensuring strict monotonicity of N(x). Note that constraints in the formulation are simple and easy to use in practice. The pseudo network in this formulation will be
P (x) = m∑ r=1 ar0 ( tanh(wr0x+ br0) + tanh ′(wr0x+ br0) (wrx+ br) ) ,
with constraints wr0 + wr ≥ , for all r. P (x) is linear in θ, therefore the objective function is also convex in θ. Note that P (x) need not be forced to remain monotone using constraints: if N(x) and P (x) are sufficiently close and N(x) is strictly monotone with not too small minx ∂N(x) ∂x , then we will get monotonicity of P (x). Next, we point out that this formulation has a problem in approximation of any target function by a pseudo network. We decompose P (x) into two parts: P (x) = Pc(x) + P`(x), where
Pc(x) = m∑ r=1 ar0 (tanh(wr0x+ br0)) and P`(x) = m∑ r=1 ar0 ( tanh′(wr0x+ br0) (wrx+ br) ) .
Note that Pc(x) only depends upon initialization and does not depend on wr and br. Hence, it can not approximate the target function after the training, therefore P`(x) needs to approximate target function with Pc(x) subtracted. Now, we will show that P`(x) can not approximate “sufficiently non-linear” functions. The initialization distribution for wr0 is half-normal distribution with zeromean and variance= 1m of normal distribution, i.e. wr0 = |X| where X has normal distribution with the same parameters. The bias term br0 follows normal distribution with 0 mean and 1m variance. Using the initialization, we can say that wr0 and |br0| areO (√ logm√ m ) with high probability;
therefore, |wr0x+ br0| is O (√ logm√ m ) . Using the fact that tanh′(y) ≈ 1 for small y, we get that tanh′ (wr0x+ br0) ≈ 1 for sufficient large m. In such cases, P` (x) becomes linear function in x and won’t be able to approximate sufficiently non-linear function.
Note that this issue does not arise in pseudo network with ReLU activation because the derivative of ReLU is discontinuous at 0 but as described earlier, for CNFs activations need to have continuous derivative. The same issue in approximation arises for all activations with continuous derivative. Using other variance of initializations leads to problem in other parts of the proof. This problem remains if we use normal distribution initialization of wr0 and br0 with variance o ( 1
logm
) . For
normal distribution initialization of wr0 and br0 with variance Ω ( 1 logm ) and O(1), successfully
training of CNFs to small training error can lose coupling between neural network N(x) and pseudo network P (x). Please see Appendix F for more details. A generalization argument for activations with continuous derivatives is not known even in the supervised case, therefore we do not work with constrained normalizing flow. However, we show the effect of overparameterization for constrained normalizing flow with tanh activation in experiments (Section 3).

heading: 2.2 UNCONSTRAINED NORMALIZING FLOW
text: Unlike the constrained case, where we modeled f(x) using a neural network N(x), here we model f ′(x) using a neural network. Then we have f(x) = ∫ x −1 f
′(u) du. While this cannot be computed exactly, good approximation can be obtained via numerical integration also known as numerical quadrature of f ′(x). The strict monotonicity of f is achieved by ensuring that f ′(x) is always
positive. To this end a suitable nonlinearity is applied on top of the neural network: f ′(x) = φ(N(x)), where N(x) is as in (2.4) with ρ = σ = ReLU, and φ is the function ELU + 1 given by φ(x) = ex I [x < 0] + (x+ 1) I [x ≥ 0]. Thus φ(x) > 0, for all x ∈ R, which means that f ′(x) > 0 for all x. Although this was the only property of ELU + 1 mentioned by Wehenkel & Louppe (2019), it turns out to have several other properties which we will exploit in our proof: it is 1-Lipschitz monotone increasing; its derivative is bounded from above by 1.
We denote by f̃ (x) the estimate of f(x) = ∫ x −1 f ′(u) du obtained from f ′(x) via quadrature
f̃(x) = ∑Q i=1 qif
′(τi (x)). Here Q is the number of quadrature points τ1 (x) , . . . , τQ (x), and the q1, . . . , qQ ∈ R are the corresponding coefficients. Wehenkel & Louppe (2019) use Clenshaw–Curtis quadrature where the coefficients qi can be negative.
We will use simple rectangle quadrature, which arises in Riemann integration, and uses only positive coefficients: f̃(x) = ∆x [ f ′(−1 + ∆x) +f ′(−1 + 2∆x) . . .+f ′(x) ] , where ∆x = x+1Q . It is known (see e.g. Chapter 5 in Atkinson (1989) for related results) that∣∣∣f̃(x)− f(x)∣∣∣ ≤ M ′′(x+ 1)2 2Q , where M ′′ = max u∈[−1,x] |f ′′(u)|.
Compared to Clenshaw–Curtis quadrature, the rectangle quadrature requires more points for similar accuracy (in our experiments this was about double). However, we use it because all the coefficients are positive which helps make the problem of minimizing the loss a convex optimization problem.
Instead of using f , to which we do not have access, we use f̃ in the loss function, denoting it L̂(f ′, x) for the standard exponential as the base distribution to write L̂(f ′, x) = f̃(x) − log f ′(x) and L̂(f ′, S) = 1n ∑ x∈S L̂(f
′, x). The loss L̂G(f ′, x) for the standard Gaussian as the base distribution is defined similarly.
Let X be a random variable with density supported on [−1, 1]. Let the base distribution be the standard exponential, and so Z will be a random variable with the standard exponential distribution. And let F ∗ : R→ R be continuous monotone increasing such that F ∗−1(Z) has the same distribution as X . Let S = {x1, . . . , xn} be a set of i.i.d. samples of X . Following Allen-Zhu et al. (2019), we initialize ar0 ∼ N (0, 2a), wr0 ∼ N ( 0, 1m ) and br0 ∼ N ( 0, 1m ) , where a > 0 is a small constant to be set later. The SGD updates are given by θt+1 = θt − η∇θL̂(f ′t , xt) where f ′t(x) = φ(Nt(x)), and xt ∈ S is chosen uniformly at random at each step. We can now state our main result. Theorem 2.1 (informal statement of Theorem E.1). (loss function is close to optimal) For any > 0 and for any target function F ∗ with finite second order derivative, hidden layer size m ≥ C1(F ∗′) 2 , the number of samples n ≥ C2(F ∗′) 2 and the number of quadrature points Q ≥ C3(F ∗′) , where C1(·), C2(·), C3(·) are complexity measures, with probability at least 0.9, we have
Esgd
[ 1
T T−1∑ t=0 Ex∼DL(ft, x)
] − Ex∼D [L(F ∗, x)] = O( ).
The complexity functions in the above statement have natural interpretations in terms of how fast the function oscillates. Now recall that KL (pF∗,Z ||pft,Z) = EX log pF∗,Z(X)
pft,Z(X) , which gives Esgd [ 1 T ∑T−1 t=0 KL (pF∗,Z ||pft,Z) ] = O( ).Recall that pf,Z(x) is the probability density of f−1(Z). Using Pinsker’s inequality, we can also bound the total variation distance between the learned and data distributions pft,Z and pF∗,Z .
Define pseudo network g′(x), which acts as proxy for f ′(x), as g′(x) = φ(P (x)). Note that our definition of pseudo network is not the most straightforward version: g′(x) is not a linear approximation of f ′(x). As in Allen-Zhu et al. (2019), we begin by showing the existence of a pseudo network close to the target function. However, for this we cannot use the approximation lemma in Allen-Zhu et al. (2019) as it seems to require dimension at least 2. We use the recent result of Ji et al. (2020) instead (Lemma B.1). The presence of both f ′ and f̃ and other differences in the loss function leads to new difficulties in the analysis compared to the supervised case. We refer to the full proof due to the lack of space.

heading: 3 EXPERIMENTS
text: Full details of experimental setup and additional results on constrained normalizing flow as well as results on unconstrained normalizing flow are given in appendix G.

heading: 3.1 RESULTS FOR CONSTRAINED NORMALIZING FLOW
text: In Sec. 2.1, we suggested that high overparameterization may adversely affect training for constrained normalizing flows. We now give experimental evidence for this. In Figs. 1, we see that as we increase the learning rate, training becomes more stable for larger m. Note that for learning rate 0.025, constrained normalizing flow with m = 1600 doesn’t learn anything due to small learning rate. We observe that the L2-norms ofW t andBt form = 6400 are at least as large as those ofm = 1600. On both datasets, as we increase the learning rate, L2-norm of Bt increases and learning of constrained normalizing flow becomes more stable. These observations support our claim in Sec.2.1 that for learning and approximation of overparameterized constrained normalizing flow, neural networks need large L2-norms of W t and Bt.

heading: 4 CONCLUSION
text: In this paper, we gave the first theoretical analysis of normalizing flows in the simple but instructive univariate case. We gave empirical and theoretical evidence that overparametrized networks are unlikely to be useful for CNFs. By contrast, for UNFs, overparametrization does not hurt and we can adapt techniques from supervised learning to analyze two-layer (or one hidden layer) networks. Our technical adaptations and NF variants may find use in future work.
Our work raises a number of open problems: (1) We made two changes to the unconstrained flow architecture of Wehenkel & Louppe (2019). An obvious open problem is an analysis of the original architecture or with at most one change. While the exponential distribution works well as the base distribution, can we also analyze the Gaussian distribution? Similarly, Clenshaw-Curtis quadrature instead of simple rectangle quadrature? These problems seem tractable but also likely
to require interesting new techniques as the optimization becomes non-convex. That would get us one step closer to the architectures used in practice. (2) Analysis of constrained normalizing flows. It is likely to be difficult because, as our results suggest, one needs networks that are not highly overparametrized—this regime is not well-understood even in the supervised case. (3) Finally, analysis of normalizing flows for the multidimensional case. Our 1D result brings into focus potential difficulties: All unconstrained architectures seem to require more than one hidden layer, which poses difficult challenges even in the supervised case. For CNFs, it is possible to design an architecture with one hidden layer, but as we have seen in our analysis of CNFs, that is challenging too.

heading: A NOTATIONS
text: We denote (α,β) as a concatenation of 2 vectors α and β . For any 2 vectors α and β , α β denotes element wise multiplication of α and β vector. We denote the parameters of neural network θ ∈ R2m is concatenation of W = (w1, w2, ..., wm) ∈ Rm and B = (b1, b2, ..., bm) ∈ Rm (i.e. θ = (W,B)). Similarly, θt = (W t, Bt) where W t = (wt1, w t 2, ..., w t m) and B t = (bt1, b t 2, ..., b t m). Similarly, A0 = (a10, a20, . . . , ar0, . . . , am0). We denote 1 = (1, 1, . . . , 1) ∈ Rm. We use Big-O notation to hide constants. We use log to denote natural logarithm. [n] denotes set {1, 2, . . . , n}

heading: B EXISTENCE
text: This section contains a proof that shows existence of a pseudo network whose loss closely approximates the loss of the target function. Lemma B.1. For every positive function F ∗′, for every x in the radius of 1 (i.e. |x| ≤ 1), there exist a function h(wr0, br0) : R2 → [−Uh, Uh] such that∣∣φ−1 (F ∗′(x))− Ewr0,br0∼N (0,1) [h(wr0, br0)I [wr0x+ br0 ≥ 0]]∣∣ ≤ ωφ−1(F∗′)(δ) where Uh is given by
Uh = Õ
( ‖ ( φ−1 (F ∗′) ) |δ ‖ 5 L1
δ10(ωφ−1(F∗′)(δ))4
) (B.1)
Proof. We use a result from Ji et al. (2020) to prove the lemma.
Result B.1. (One-dimensional version of Theorem 4.3 from Ji et al. (2020)) Let ψ : R → R and δ > 0 be given, and define
ωψ(δ) = sup{ψ(x)− ψ(x′) : max{|x| , |x′|} ≤ 1 + δ, |x− x′| ≤ δ} ψ|δ(x) :=ψ(x)I [|x| ≤ 1 + δ] ψ|δ,α :=ψ|δ ∗Gα
α := δ 1 + √ 2 log (2M/ωψ(δ)) = Õ(δ)
M := sup |x|≤1+δ
|ψ(x)|
β := 1
2πα2 Tr(wr0, br0) :=2 [ ψ|δ,α(0) + ∫ ∣∣∣ψ̂|δ,α(v)∣∣∣ cos (2π (θψ|δ,α(v)− ‖v‖)) dv] + 2π ( 2πβ2
) ∣∣∣ψ̂|δ(βwr0)∣∣∣ e (br0)22 sin (2π (θψ|δ,α(βwr0)− br0)) I [|br0| ≤ ‖wr0‖ ≤ r] where ∗ denotes convolution operation, Gα denotes Gaussian with mean 0 and variance α2. Note that Õ hides logarithmic dependency of complexity measure of function ψ.
∣∣∣ψ̂|δ,α∣∣∣ denotes magnitude of fourier transform of ψ|δ,α and θψ|δ,α denotes phase of fourier transform. Then,
sup |x|≤1 ∣∣ψ(x)− Ewr0,br0∼N (0,1) [Tr(wr0, br0)I [wr0x+ br0 ≥ 0]]∣∣ ≤ ωψ(δ) (B.2) The upper bound of Tr(wr0, br0) is given by
sup wr0,br0 ‖Tr(wr0, br0)‖ = Õ ( ‖ψ|δ‖5L1 δ10(ωψ(δ))4 ) = UT (B.3)
Using Result B.1 for φ−1(F ∗′(x)) function, denoting Tr(wr0, br0) for φ−1(F ∗′(x)) function as h(wr0, br0), we get∣∣φ−1(F ∗′(x))− Ewr0,br0∼N (0,1) [h(wr0, br0)I [wr0x+ br0 ≥ 0]]∣∣ ≤ ωφ−1(F∗′) (δ)
with following upper bound on h(wr0, br0).
sup wr0,br0
h(wr0, br0) ≤ Õ
( ‖ ( φ−1 (F ∗′) ) |δ ‖ 5 L1
δ10(ωφ−1(F∗′)(δ))4
) = Uh
Divide pseudo network P (x) into 2 parts: Pc(x), first part of pseudo network is constant and time-independent and P`(x), second part of pseudo network is linear in wr and br
P (x) = Pc(x) + P`(x)
where
Pc(x) = m∑ r=1 ar0 (wr0x+ br0) I [wr0x+ br0 ≥ 0]
P`(x) = m∑ r=1 ar0 (wrx+ br) I [wr0x+ br0 ≥ 0]
Lemma B.2. (Approximating target function using P`(x)) For every positive function F ∗′ and for every ∈ (0, 1), with at least 1− 1c1 − exp ( − 2m 128c21U 2 h logm ) probability over random initialization, there exist θ∗ such that we get following inequality for all x ∈ [−1, 1] and some fixed positive constant c1 > 1.
|φ(P ∗` (x))− F ∗′(x)| ≤ ωφ−1(F∗′) (δ) +
and upper bound L∞ norm of parameters is given by
‖θ∗‖∞ ≤ Uh √ π√
2m a
Proof. Define w∗r and b ∗ r as
w∗r = 0
b∗r = sign (ar0)
√ π
m a √ 2 h( √ mwr0, √ mbr0)
(B.4)
Using w∗r and b ∗ r ,
Ear0∼N (0, 2a),wr0∼N(0, 1m ),br0∼N(0, 1m ) [P ∗ ` (x)]
= Ear0∼N (0, 2a),wr0∼N(0, 1m ),br0∼N(0, 1m ) [ m∑ r=1 ar0(w ∗ rx+ b ∗ r)I [wr0x+ br0 ≥ 0] ]
= Ear0∼N (0, 2a),wr0∼N(0, 1m ),br0∼N(0, 1m )
[ ar0sign (ar0) √ π
a √ 2 h( √ mwr0, √ mbr0)I [wr0x+ br0 ≥ 0] ] (i) = Ewr0∼N(0, 1m ),br0∼N(0, 1m ) [ h( √ mwr0, √ mbr0)I [√ m (wr0x+ br0) ≥ 0
]] where equality (i) follows from Fact H.2 and homogeneity of indicator function. Using Lemma B.1,∣∣∣Ear0∼N (0, 2a),wr0∼N(0, 1m ),br0∼N(0, 1m ) [P ∗` (x)]− φ−1 (F ∗′(x))∣∣∣
= ∣∣∣Ewr0∼N(0, 1m ),br0∼N(0, 1m ) [h(√mwr0,√mbr0)I [√m (wr0x+ br0) ≥ 0]]− φ−1 (F ∗′(x))∣∣∣
≤ ωφ−1(F∗′) (δ) (B.5)
Using technique from Yehudai & Shamir (2019), we define
h = h ((a10, w10, b10) , . . . , (ar0, wr0, br0) , . . . , (a10, wm0, bm0)) = sup x∈[−1,1]
|P ∗` (x)− Ear0,wr0,br0 [P ∗` (x)]|
We will use McDiarmid’s inequality to bound h.∣∣∣h ((a10, w10, b10) , . . . , (ar0, wr0, br0) , . . . , (a10, wm0, bm0))− h((a10, w10, b10) , . . . , (a′r0, w′r0, br0)′ , . . . , (a10, wm0, bm0))∣∣∣ ≤ 4c1Uh √ 2 logm m Using Lemma 26.2 from Shalev-Shwartz & Ben-David (2014), we get
E [h] = 2
m Ear0,wr0,br0,ξr [ sup x m ∣∣∣∣∣ m∑ r=1 ξi (w ∗ rx+ b ∗ r) I [wr0x+ br0 ≥ 0] ∣∣∣∣∣ ]
where ξ1, ξ2, . . . , ξm are independent Rademacher random variables.
Ear0,wr0,br0 [h] ≤ 2
m Ear0,wr0,br0,ξr [ sup x m ∣∣∣∣∣ m∑ r=1 ξiar0 (w ∗ rx+ b ∗ r) I [wr0x+ br0 ≥ 0] ∣∣∣∣∣ ]
≤ 2 m Ear0,wr0,br0,ξr [ sup x m ∣∣∣∣∣ m∑ r=1 ξiar0 (w ∗ rx+ b ∗ r) I [wr0x+ br0 ≥ 0] ∣∣∣∣∣ ] ≤ 8c1 √
logmUh m Ear0,wr0,br0,ξr [ sup x ∣∣∣∣∣ m∑ r=1 ξiI [wr0x+ br0 ≥ 0] ∣∣∣∣∣ ]
One can show that
1 m Ear0,wr0,br0,ξr [ sup x ∣∣∣∣∣ m∑ r=1 ξiI [wr0x+ br0 ≥ 0] ∣∣∣∣∣ ] ≤ 2 √ logm m
Using this relation, we get
Ear0,wr0,br0 [h] ≤ 16c1Uh logm√
m Using Mcdiarmid’s inequality, with at least 1− 1c1 − exp ( − 2m 128c21U 2 h logm ) , we have
|P ∗` (x)− Ear0,wr0,br0 [P ∗` (x)]| = h =≤
2 + 16c1Uh logm√ m (i) ≤ (B.6)
where inequality (i) follows from our choice of m in lemma D.2. Using eq.(B.5), we get∣∣P ∗` (x)− φ−1 (F ∗′(x))∣∣ ≤ ωφ−1(F∗′) (δ) + (B.7) Using 1-Lipschitzness of φ, we get
|φ(P ∗` (x))− F ∗′(x)| = ∣∣φ(P ∗` (x))− φ (φ−1 (F ∗′(x)))∣∣
≤ ∣∣P ∗` (x)− φ−1 (F ∗′(x))∣∣
≤ ωφ−1(F∗′) (δ) + The upper bound on norm of ‖θ∗‖∞ is given by the following equation.
‖θ∗‖∞ ≤ Uh √ π√
2m a
Corollary B.1. (Approximating target network using P (x)) For every positive function F ∗′ and for every ∈ (0, 1), with at least 0.99− 1c1 − 1 c6 − 1c7 − exp ( − 2m 128c21U 2 h logm ) probability over random initialization, there exists θ∗ such that we have following inequality for all x ∈ [−1, 1] and some fixed positive constants c1 > 1, c6 > 1 and c7 > 1. |φ (P ∗(x))− F ∗′(x)| ≤ 16c1 (c6 + c7) a logm+ ωφ−1(F∗′) (δ) + and upper bound on L∞ norm of parameters θ∗ is given by
‖θ∗‖∞ ≤ Uh √ π√
2m a
Proof. Using Lipschitz continuity of φ function, we get
|φ (P ∗` (x))− φ(P ∗(x))| ≤ |P ∗` (x)− P ∗(x)|
≤ ∣∣∣∣∣ m∑ r=1 ar0 (wr0x+ br0) I [wr0x+ br0 ≥ 0] ∣∣∣∣∣ Now, there are at most m break points of indicator I [wr0x+ br0 ≥ 0] where value of I [wr0x+ br0 ≥ 0] changes. We can divide range of x into at most m + 1 subsets where in each subset, value of indicators I [wr0x+ br0 ≥ 0] is fixed for all r. Suppose there are m′ indicators with value 1 in a given subset. Without loss of generality, we can assume that indicators from r = 1 to r = m′ is 1. Then,∣∣∣∣∣ m∑ r=1 ar0 (wr0x+ br0) I [wr0x+ br0 ≥ 0] ∣∣∣∣∣ = ∣∣∣∣∣∣ m′∑ r=1 ar0 (wr0x+ br0)
∣∣∣∣∣∣ ≤
∣∣∣∣∣∣x m′∑ r=1 ar0wr0 + m′∑ r=1 ar0br0 ∣∣∣∣∣∣ Now, applying Hoeffding’s inequality for the sum in above equation, we get
Pr ∣∣∣∣∣∣ m′∑ r=1 ar0wr0 ∣∣∣∣∣∣ ≥ t  ≤ exp(− 2t2m m′ ( 2c1 a √ 2 logm )2 ( 2c6 √ 2 logm )2 )
= exp ( − t 2
32c21c 2 6 2 a (logm)
2
)
Taking t = 16c1c6 a (logm), with at least probability 0.999− 1c1 − 1 c6 , we have∣∣∣∣∣∣ m′∑ r=1 ar0wr0 ∣∣∣∣∣∣ ≤ 16c1c6 a (logm) and similarly, we will get that with at least 0.999− 1c1 − 1 c7
probability,∣∣∣∣∣∣ m′∑ r=1 ar0wr0 ∣∣∣∣∣∣ ≤ 16c1c7 a (logm) we will get that at least 0.999− 1c1 −
1 c6 − 1c7 probability, we have∣∣∣∣∣ m∑ r=1 ar0wr0I [wr0x+ br0 ≥ 0] ∣∣∣∣∣ ≤ 16c1c6 a (logm) (B.8)∣∣∣∣∣ m∑ r=1 ar0br0I [wr0x+ br0 ≥ 0]
∣∣∣∣∣ ≤ 16c1c7 a (logm) Using these relations, we get that with at least 0.99− 1c1 −
1 c6 − 1c7 probability,∣∣∣∣∣ m∑ r=1 ar0 (wr0x+ br0) I [wr0x+ br0 ≥ 0] ∣∣∣∣∣ ≤ 16c1 (c6 + c7) a logm (B.9) Using above inequality, we get
|φ (P ∗` (x))− φ(P ∗(x))| ≤ |P ∗` (x)− P ∗(x)| ≤ 16c1 (c6 + c7) a logm
Using lemma B.2, with at least 0.99− 1c1 − 1 c6 − 1c7 − exp
( −
2m 128c21U 2 h logm
) probability,
|φ (P ∗(x))− F ∗′(x)| ≤ |φ (P ∗(x))− φ(P ∗` (x))|+ |φ(P ∗` (x))− F ∗′(x)| ≤ 16c1 (c6 + c7) a logm+ ωφ−1(F∗′) (δ) +
Lemma B.3. (Optimal loss) For every positive function F ∗′ and for every ∈ (0, 1), with at least 0.99− 1c1 − 1 c6 − 1c7 − exp ( − 2m 128c21U 2 h logm ) probability over random initialization, there exist θ∗ such that loss of pseudo network with θ∗ parameters is close to that of the target function for all x ∈ [−1, 1] and for some fixed positive constants c1 > 1, c6 > 1 and c7 > 1.∣∣∣L̂ (φ (P ∗) , x)− L̂ (F ∗′, x)∣∣∣ ≤ 3 (16c1 (c6 + c7) a logm+ ωφ−1(F∗′) (δ) + ) Proof. ∣∣∣L̂ (φ (P ∗) , x)− L̂ (F ∗′, x)∣∣∣ ≤ ∣∣∣∣∣ Q∑ i=1 ∆xφ (P ∗(τi (x)))− Q∑ i=1 ∆xF ∗′ (τi (x))
∣∣∣∣∣ + |log (φ (P ∗(x)))− log (F ∗′(x))|
(i) ≤ 2 ( 16c1 (c6 + c7) a logm+ ωφ−1(F∗′) (δ) + ) + ∣∣P ∗(x)− φ−1 (F ∗′ (x))∣∣
≤ 2 ( 16c1 (c6 + c7) a logm+ ωφ−1(F∗′) (δ) + ) + |P ∗c (x)|+
∣∣P ∗` (x)− φ−1 (F ∗′ (x))∣∣ (ii) ≤ 3 ( 16c1 (c6 + c7) a logm+ ωφ−1(F∗′) (δ) +
) where inequality (i) follows from Corollary B.1 with at least 0.99 − 1c1 − 1 c6 − 1c7 −
exp ( −
2m 128c21U 2 h logm
) probability. Inequality (ii) uses Eq.(B.7) and Eq.(B.9).

heading: C COUPLING
text: In this section, we prove that, for random initialization, the gradients of the loss of pseudo network closely approximate the gradients of the loss of the target function. In other words, we show coupling of their gradient-based optimizations. Define λ1 as
λ1 = sup t∈[T ],r∈[m],wtr,btr,|x|≤1
φ′(Nt(x)) φ(Nt(x)) (C.1)
We get following find upper bound on λ1.
λ1 = sup t∈[T ],r∈[m],wtr,btr,|x|≤1
φ′(Nt(x))
φ(Nt(x))
= sup t∈[T ],r∈[m],wtr,btr,|x|≤1 exp (Nt(x)) I [Nt(x) < 0] + I [Nt(x) ≥ 0] exp (Nt(x)) I [Nt(x) < 0] + (Nt(x) + 1) I [Nt(x) ≥ 0]
= sup t∈[T ],r∈[m],wtr,btr,|x|≤1 I [Nt(x) < 0] + I [Nt(x) ≥ 0] Nt(x) + 1
= 1 (C.2)
Define ∆̄ as
∆̄ = 6c1 a √ 2 logm (C.3)
for some positive constant c1 > 1.
Lemma C.1. (Bound in change in patterns) For every x in 1 radius (|x| ≤ 1) and for every time step t ≥ 1, with probability at least 1− 1c1 − exp ( − 64(c2−1) 2η2m2∆̄2t2 π ) over random initialization, for at most c2 4 √ 2η √ m∆̄t√ π fraction of r ∈ [m]
I [ (wr0 + w t r)x+ br0 + b t r ≥ 0 ] 6= I [wr0x+ br0 ≥ 0]
for some positive constant c1 > 1 and c2 ≥ 1.
Proof. Taking derivative of L̂(f ′, x) wrt wr,∣∣∣∣∣∂L̂(f ′t , x)∂wr ∣∣∣∣∣ = ∣∣∣∣∣ ( Q∑ i=1 ∆xφ ′(Nt (τi (x)) )ar0σ′ ((wr0 + wtr)τi (x) + br0 + btr) τi (x) )∣∣∣∣∣ +
∣∣∣∣ 1φ(Nt(x)) (φ′(Nt(x))ar0σ′ ((wr0 + wtr)x+ br0 + btr)x) ∣∣∣∣
≤ Q∑ i=1 ∣∣∆xφ′(Nt (τi (x)) )ar0σ′ ((wr0 + wtr)τi (x) + br0 + btr) τi (x)∣∣ +
∣∣∣∣φ′(Nt(x))φ(Nt(x)) ∣∣∣∣ ∣∣(ar0σ′ ((wr0 + wtr)x+ br0 + btr)x)∣∣
Using Eq.(C.2), ∆x ≤ 2Q , |x| ≤ 1 and |φ ′ (N(x))| ≤ 1 for all x ∈ [−1, 1], we get∣∣∣∣∣∂L̂(f ′t , x)∂wr ∣∣∣∣∣ ≤ 3 |ar0| Using Lemma H.2, with at least 1− 1c1 probability, we get∣∣∣∣∣∂L̂(f ′t , x)∂wr
∣∣∣∣∣ ≤ ∆̄ (C.4) where ∆̄ is defined in Eq.(C.3). Using same procedure for br, we get∣∣∣∣∣∂L̂(f ′t , x)∂br ∣∣∣∣∣ = ∣∣∣∣∣ Q∑ i=1 ∆xφ ′ (Nt (τi (x))) ar0σ ′ ((wr0 + wtr)τi (x) + br0 + btr) ∣∣∣∣∣
+ ∣∣∣∣ 1φ(Nt(x)) (φ′(Nt(x))ar0σ′ ((wr0 + wtr)x+ br0 + btr)) ∣∣∣∣
≤ 3 |ar0| =∆̄ (C.5)
Using Eq.(C.4) and Eq.(C.5), we get ∣∣wtr∣∣ ≤ η∆̄t∣∣btr∣∣ ≤ η∆̄t (C.6) Define
Ht = {r ∈ [m]| |wr0x+ br0| ≥ 4η∆̄t} (C.7)
For every x with |x| ≤ 1 and for all r ∈ [m], |wtrx+ btr| ≤ 2η∆̄t. For all r ∈ Ht, we get I [(wr0 + wtr)x+ br0 + btr ≥ 0] = I [wr0x+ br0 ≥ 0]. Now, we need to bound the size of Ht. We know that for all x ∈ [−1, 1], wr0x + br0 is Gaussian with E [wr0x+ br0] = 0 and Var [wr0x+ br0] ≥ 1m . Using Lemma H.3, we get
Pr ( |wr0x+ br0| ≤ 4η∆̄t ) ≤ 4 √ 2η √ m∆̄t√ π
Using Fact H.1 forHct (whereHct = [m]/Ht) for some positive constant c2 ≥ 1, we get
Pr ( |Hct | ≥ c2m 4 √ 2η √ m∆̄t√ π ) ≤ exp −2m((c2 − 1)(4√2η√m∆̄t√ π ))2 ≤ exp ( −64(c2 − 1) 2η2m2∆̄2t2
π ) Pr ( |Hct | ≤ c2m 4 √ 2η √ m∆̄t√ π ) ≥ 1− exp ( −64(1− c2) 2η2m2∆̄2t2 π )
Pr ( |Ht| ≥ m ( 1− c2 4 √ 2η √ m∆̄t√ π )) ≥ 1− exp ( −64(1− c2) 2η2m2∆̄2t2 π )
where |Ht| denotes the cardinality of setHt and similarly for |Hct |.
Lemma C.2. (Bound on difference of f ′ and g′) For every x in 1 radius (|x| ≤ 1) and for every time step t ≥ 1, with at least 1− 1c1 probability, function with neural network and function with pseudo network are close for some positive constants c1 > 1.
|φ(Nt(x))− φ(Pt(x))| ≤ 24c1 aη∆̄t ∣∣Htc∣∣√2 logm
Proof. We know that φ is 1-Lipschitz continuous. Using Lipschitz continuity of φ, we get
|φ(Nt(x))− φ(Pt(x))| ≤ |Nt(x)− Pt(x)|
We bound |Nt(x)− Pt(x)| as following.
|Nt(x)− Pt(x)| ≤ ∣∣∣∣∣ ∑ r∈[m] ar0 ( (wr0 + w t r)x+ br0 + b t r ) I [ (wr0 + w t r)x+ br0 + b t r ≥ 0 ] − ∑ r∈[m] ar0 ( (wr0 + w t r)x+ br0 + b t r ) I [wr0x+ br0 ≥ 0]
∣∣∣∣∣ ≤
∣∣∣∣∣∣ ∑ r/∈Ht ar0 ( (wr0 + w t r)x+ br0 + b t r ) ( I [ (wr0 + w t r)x+ br0 + b t r ≥ 0 ] − I [wr0x+ br0 ≥ 0] )∣∣∣∣∣∣ (i) ≤ ∣∣Htc∣∣ (2c1 a√2 logm) (4η∆̄t+ 2η∆̄t) (2) ≤24c1 aη∆̄t
∣∣Htc∣∣√2 logm (C.8) where inequality (i) uses Lemma H.2 with at least 1− 1c1 probability.
Corollary C.1. (Final bound on difference of f ′ and g′) For every x in 1 radius (|x| ≤ 1) and for every time step t ≥ 1, with at least 1− 1c1 − exp ( − 64(c2−1) 2η2m2∆̄2t2 π ) probability over random initialization, function with neural network and function with pseudo network are close for some positive constants c1 > 1 and c2 ≥ 1.
|φ(Nt(x))− φ(Pt(x))| ≤ 192η2m1.5∆̄2c1c2 at
2 √
logm√ π
(C.9)
Proof. Using Lemma C.1 and Lemma C.2, we get |φ(Nt(x))− φ(Pt(x))| ≤24c1 aη∆̄t ∣∣Htc∣∣√2 logm
(i) ≤24c1 aη∆̄t ( c2m 4 √ 2η √ m∆̄t√ π )√ 2 logm
≤ ( 192ηm1.5∆̄c1c2 at √
logm√ π
)( η∆̄t ) = 192η2m1.5∆̄2c1c2 at 2 √
logm√ π
(C.10)
≤ O(η2m1.5∆̄2 at2 √ logm)
where inequality (i) uses Lemma C.1 and the inequality follows with at least 1 − 1c1 − exp ( − 64(c2−1) 2η2m2∆̄2t2
π
) probability. Define ∆tnp as
∆tnp = 192η2m1.5∆̄2c1c2 at
2 √
logm√ π
(C.11)
Lemma C.3. (Coupling of loss functions) For all x in 1 radius (|x| ≤ 1) and for every time step t ≥ 1, with probability at least 1− 1c1 − exp ( − 64(c2−1) 2η2m2∆̄2t2 π ) over random initialization, loss function of neural network and pseudo network are close for some positive constant c1 > 1 and c2 ≥ 1. ∣∣∣L̂ (f ′t , x)− L̂ (g′t, x)∣∣∣ ≤ 3∆tnp Proof.∣∣∣L̂ (f ′t , x)− L̂ (g′t, x)∣∣∣ ≤ ∣∣∣∣∣ Q∑ i=1 ∆xf ′ t(τi (x))− Q∑ i=1 ∆xg ′ t (τi (x))
∣∣∣∣∣+ |log (f ′t(x))− log (g′t(x))| (i) ≤2 ( sup i∈[Q] |f ′t (τi (x))− g′t (τi (x))| ) + |Nt(x)− Pt(x)|
(ii) ≤ 3∆tnp
where inequality (i) follows from 1-Lipschitz continuity of log (φ(N(x))) with respect to N(x). Inequality (ii) uses Eq.(C.8) and Lemma C.2.
Lemma C.4. (Coupling of gradient of functions) For all x in 1 radius (|x| ≤ 1) and for every time step t ≥ 1, with at least 1− 1c1 probability over random initialization, gradient of derivative of neural network function and derivative of pseudo network function with respect to parameters are close for some positive constant c1 > 1.∥∥∥∇θf ′t(x)−∇θg′t(x)∥∥∥
1 ≤ 4c1 a
( m∆tnp + 2 |Hct | )√ 2 logm
Proof.∥∥∥∇θf ′t(x)−∇θg′t(x)∥∥∥ 1 ≤ ∥∥∥φ′(Nt(x))∇θNt(x)− φ′(Pt(x))∇θPt(x)∥∥∥ 1
≤ ∥∥∥φ′(Nt(x))∇θNt(x)− φ′(Pt(x))∇θNt(x)∥∥∥ 1 + ∥∥∥φ′(Pt(x))∇θNt(x)− φ′(Pt(x))∇θPt(x)∥∥∥ 1
≤ |φ′(Nt(x))− φ′(Pt(x))| ∥∥∥∇θNt(x)∥∥∥
1 + |φ′(Pt(x))| ∥∥∥∇θNt(x)−∇θPt(x)∥∥∥ 1
≤ |Nt(x)− Pt(x)| ∥∥∥∇θNt(x)∥∥∥ 1 + ∥∥∥∇θNt(x)−∇θPt(x)∥∥∥ 1
where last inequality follows from 1-Lipschitzness of φ′ function and φ′(x) ≤ 1 for all x such that |x| ≤ 1, t ∈ [T ]. To upper bound ∥∥∥∇θNt(x)−∇θPt(x)∥∥∥ 1 ,∥∥∥∇θNt(x)−∇θPt(x)∥∥∥
1 ≤ ∥∥∥(A0, A0) (1x,1) (I [(W0 +W t)x+B0 +Bt ≥ 0]− I [W0x+B0 ≥ 0] , I [ (W0 +W t)x+B0 +B t ≥ 0 ] − I [W0x+B0 ≥ 0]) ∥∥∥ 1
(i) ≤ ( 8c1 a √ 2 logm ) |Hct |
≤ 8c1 a |Hct | √ 2 logm (C.12)
The inequality (i) uses property of Ht that for all r ∈ Ht, I [(wr0 + wtr)x+ br0 + btr ≥ 0] = I [wr0x+ br0 ≥ 0]. Using Eq.(C.11) and Eq.(C.12), we get∥∥∥∇θf ′t(x)−∇θg′t(x)∥∥∥
1 ≤ |Nt(x)− Pt(x)| ∥∥∥(A0, A0) (1x,1) (I [(W0 +W t)x+B0 +Bt ≥ 0] , I [ (W0 +W t)x+B0 +B t ≥ 0 ] ) ∥∥∥ 1 + ∥∥∥∇θNt(x)−∇θPt(x)∥∥∥ 1
≤ 4c1 am∆tnp √ 2 logm+ 8c1 a |Hct | √ 2 logm
= 4c1 a ( m∆tnp + 2 |Hct | )√ 2 logm
Lemma C.5. (Coupling of gradient of loss) For all x in 1 radius (|x| ≤ 1) and for every time step t ≥ 1, with probability at least 1 − 1c1 − exp ( − 64(c2−1) 2η2m2∆̄2t2 π ) over random initialization, gradient of loss function with neural network and loss function with pseudo network are close for some positive constant c1 > 1 and c2 ≥ 1.∥∥∇θL̂(f ′t , x)−∇θL̂(g′t, x)∥∥1 ≤ 192ηm1.5∆̄c1c2 at√logm√π + 16c1 am∆tnp√2 logm Proof.
∥∥∇θL̂(f ′t , x)−∇θL̂(g′t, x)∥∥1 ≤ ∥∥∥∥∥ Q∑ i=1 ∆x∇θf ′t(τi (x))− ∇θf ′t(x) f ′t(x)
− Q∑ i=1 ∆x∇θg′t(τi (x)) + ∇θg′t(x) g′t(x) ∥∥∥∥∥ 1
≤ ∥∥∥∥∥ Q∑ i=1 ∆x∇θf ′t(τi (x))− Q∑ i=1 ∆x∇θg′t(τi (x)) ∥∥∥∥∥ 1︸ ︷︷ ︸
I
+ ∥∥∥∥∥∇θg′t(x)g′t(x) − ∇θf ′ t(x) f ′t(x) ∥∥∥∥∥ 1︸ ︷︷ ︸
II
Proving bound on I,
I = ∥∥∥∥∥ Q∑ i=1 ∆x∇θf ′t(τi (x))− Q∑ i=1 ∆x∇θg′t(τi (x)) ∥∥∥∥∥ 1
≤ Q∑ i=1 ∆x ∥∥∥∇θf ′t(τi (x))−∇θg′t(τi (x))∥∥∥ 1
(i) ≤ 8c1 a ( m∆tnp + 2 |Hct | )√ 2 logm
where inequality (i) follows from Lemma C.4. Now, we will bound II,
II = ∥∥∥∥∥∇θg′t(x)g′t(x) − ∇θf ′ t(x) f ′t(x) ∥∥∥∥∥ 1
= ∥∥∥∥∥ exp (Pt(x)) I [Pt(x) < 0] + I [Pt(x) ≥ 0]exp (Pt(x)) I [Pt(x) < 0] + (Pt(x) + 1) I [Pt(x) ≥ 0]∇θPt(x) − exp (Nt(x)) I [Nt(x) < 0] + I [Nt(x) ≥ 0]
exp (Nt(x)) I [Nt(x) < 0] + (Nt(x) + 1) I [Nt(x) ≥ 0] ∇θNt(x) ∥∥∥∥∥ 1
= ∥∥∥∥∥ ( I [Pt(x) < 0] + I [Pt(x) ≥ 0] (Pt(x) + 1) ) ∇θPt(x)− ( I [Nt(x) < 0] + I [Nt(x) ≥ 0] (Nt(x) + 1) ) ∇θNt(x) ∥∥∥∥∥ 1
= ∥∥∥∥∇θPt(x)−∇θNt(x)∥∥∥∥ 1
I [Pt(x) < 0, Nt(x) < 0]︸ ︷︷ ︸ II1
+ ∥∥∥∥∥∇θPt(x)− ∇θNt(x)Nt(x) + 1 ∥∥∥∥∥
1 I [Pt(x) < 0, Nt(x) ≥ 0]︸ ︷︷ ︸ II2
+ ∥∥∥∥∥ ∇θPt(x)Pt(x) + 1 −∇θNt(x) ∥∥∥∥∥
1 I [Pt(x) ≥ 0, Nt(x) < 0]︸ ︷︷ ︸ II3
+ ∥∥∥∥∥ ∇θPt(x)Pt(x) + 1 − ∇θNt(x)Nt(x) + 1 ∥∥∥∥∥
1 I [Pt(x) ≥ 0, Nt(x) ≥ 0]︸ ︷︷ ︸ II4
On simplifying II2, we get
II2 ≤ (∣∣∣∣ 1Nt(x) + 1 ∣∣∣∣ ∥∥∥∥∇θPt(x)−∇θNt(x)∥∥∥∥ 1 + ∣∣∣∣ Nt(x)1 +Nt(x) ∣∣∣∣ ∥∥∥∥∇θPt(x)∥∥∥∥ 1 ) I [Pt(x) < 0, Nt(x) ≥ 0]
≤ (∥∥∥∥∇θPt(x)−∇θNt(x)∥∥∥∥
1
+ ∆tnp ∥∥∥∥∇θPt(x)∥∥∥∥ 1 ) I [Pt(x) < 0, Nt(x) ≥ 0] (C.13)
Similarly, on simplifying II3, we get
II3 ≤ (∣∣∣∣ 1Pt(x) + 1 ∣∣∣∣ ∥∥∥∥∇θPt(x)−∇θNt(x)∥∥∥∥ 1 + ∣∣∣∣ Pt(x)1 + Pt(x) ∣∣∣∣ ∥∥∥∥∇θNt(x)∥∥∥∥ 1 ) I [Pt(x) ≥ 0, Nt(x) < 0]
≤ (∥∥∥∥∇θPt(x)−∇θNt(x)∥∥∥∥
1
+ ∆tnp ∥∥∥∥∇θNt(x)∥∥∥∥ 1 ) I [Pt(x) ≥ 0, Nt(x) < 0] (C.14)
On simplifying II4, we get
II4 ≤ (∥∥∥∥∥ ∇θPt(x)Pt(x) + 1 − ∇θNt(x)Pt(x) + 1 ∥∥∥∥∥
1
+ ∥∥∥∥∥ ∇θNt(x)Pt(x) + 1 − ∇θNt(x)Nt(x) + 1 ∥∥∥∥∥
1
) I [Pt(x) ≥ 0, Nt(x) ≥ 0]
≤
( 1
Pt(x) + 1 ∥∥∥∥∇θPt(x)−∇θNt(x)∥∥∥∥ 1 + ∥∥∇θNt(x)∥∥1∆tnp (Pt(x) + 1) (Nt(x) + 1) ) I [Pt(x) ≥ 0, Nt(x) ≥ 0]
≤ (∥∥∥∇θPt(x)−∇θNt(x)∥∥∥ 1 + ∥∥∥∇θNt(x)∥∥∥ 1 ∆tnp ) I [Pt(x) ≥ 0, Nt(x) ≥ 0] (C.15)
Using Eq.(C.13), Eq.(C.14) and Eq.(C.15), we get
II = ∥∥∥∥∥∇θg′t(x)g′t(x) − ∇θf ′ t(x) f ′t(x) ∥∥∥∥∥ 1
≤ ∥∥∥∇θPt(x)−∇θNt(x)∥∥∥ 1 + ∥∥∥∇θNt(x)∥∥∥ 1 ∆tnpI [Pt(x) ≥ 0]
+ ∆tnp ∥∥∥∇θPt(x)∥∥∥ 1 I [Pt(x) < 0, Nt(x) ≥ 0]
Using Eq.(C.12), we get II ≤ 8c1 a |Hct | √ 2 logm+ ∆tnp (∥∥∥∇θNt(x)∥∥∥ 1 + ∥∥∥∇θPt(x)∥∥∥ 1 ) ≤ 8c1 a |Hct | √ 2 logm+ ∆tnp (∥∥∥ (A0, A0) (1x,1) (I [W0x+B0 ≥ 0] , I [W0x+B0 ≥ 0])∥∥∥ 1
+ ∥∥∥ (A0, A0) (1x,1) (I [(W0 +W t)x+B0 +Bt ≥ 0] , I [(W0 +W t)x+B0 +Bt ≥ 0]) ∥∥∥
1 ) ≤ 8c1 a |Hct | √ 2 logm+ ∆tnp ( 8c1 am √ 2 logm
) = 8c1 a ( |Hct |+m∆tnp )√ 2 logm (C.16)
Combining bounds on I and II, we get∥∥∇θL̂(f ′t , x)−∇θL̂(g′t, x)∥∥1 ≤ 8c1 a (m∆tnp + 2 |Hct |)√2 logm + 8c1 a ( |Hct |+m∆tnp )√ 2 logm
≤ 8c1 a ( 2m∆tnp + 3 |Hct | )√ 2 logm
Using Lemma C.1, with at least 1− 1c1 − exp ( − 64(c2−1) 2η2m2∆̄2t2 π ) probability, we get ∥∥∇θL̂(f ′t , x)−∇θL̂(g′t, x)∥∥1 ≤ 192ηm1.5∆̄c1c2 at√logm√π + 16c1 am∆tnp√2 logm Define Γ as the upper bound on
∥∥∇θL̂(f ′t , x)−∇θL̂(g′t, x)∥∥1. Γ = 192ηm1.5∆̄c1c2 at √
logm√ π + 16c1 am∆ t np
√ 2 logm (C.17)

heading: D OPTIMIZATION PROOF
text: This section shows that gradient-based optimization of the loss for the target function can be closely approximated by the gradient-based optimization of the pseudo network. Since the loss function of the pseudo network is convex in its parameters, we get global optimization. Lemma D.1. (Convexity of loss function of pseudo network) The loss function for pseudo network is convex with respect to parameters of neural network.
Proof. The loss function for pseudo network is
L̂(g′t, x) = Q∑ i=1 ∆xg ′ t(τi (x))− log (g′t(x))
Dividing the loss function in 2 parts,
L̂(g′t, x) = L̂1(g ′ t, x) + L̂2(g ′ t, x)
where
L̂1(g ′ t, x) = Q∑ i=1 ∆xg ′ t(τi (x))
L̂2(g ′ t, x) = − log (g′t(x))
We will prove convexity of both L̂1(g′t, x) and L̂2(g ′ t, x). To prove convexity of L̂1(g ′ t, x) as a function of parameters θ, we will prove that Hessian of L̂1(g′t, x) is positive semidefinite.
∇θL̂1(g′t, x) = Q∑ i=1 ∆x∇θg′t(τi (x)) = Q∑ i=1 ∆xφ ′ (Pt (τi (x)))∇θPt (τi (x))
∇2θL̂1(g′t, x) = Q∑ i=1 ∆x∇2θg′t(τi (x))
= Q∑ i=1 ∆xφ ′′(Pt(τi (x)))∇θPt(τi (x))∇θPt(τi (x))T
+ Q∑ i=1 ∆xφ ′(Pt(τi (x)))∇2θPt(τi (x))
= Q∑ i=1 ∆xφ ′′(Pt(τi (x)))∇θPt(τi (x))∇θPt(τi (x))T
The first term of the Hessian matrix is sum of Gram matrix and the second term of the Hessian matrix is Gram matrix. Hence, the Hessian of L̂1(g′t, x) is positive semidefinite. For second term,
L̂2(g ′ t, x) = − log (exp (Pt(x)) I [Pt(x) ≤ 0] + (Pt(x) + 1) I [Pt(x) > 0])
= −Pt(x)I [Pt(x) ≤ 0]− log (Pt(x) + 1) I [Pt(x) > 0]
Note that L̂2(g′t, x) is convex in Pt(x) and Pt(x) is linear in θ. Composition of convex and linear function is convex therefore, L̂2(g′t, x) is convex in θ. As sum of 2 convex functions is convex, L̂(g′t, x) is convex.
Remark D.1. If we use base distribution as standard Gaussian distribution, then loss function will have following term.
L̂1 (g ′ t, x) = ( Q∑ i=1 ∆xg ′ t(τi (x)) )2 If we find Hessian of L̂1, then we get
∇θL̂1 (g′t, x) = ( Q∑ i=1 ∆xg ′ t(τi (x)) )( Q∑ i=1 ∆xφ ′ (Pt (τi (x)))∇θPt (τi (x)) )
∇2θL̂1 (g′t, x) = ( Q∑ i=1 ∆xg ′ t(τi (x)) )( Q∑ i=1 ∆xφ ′′(Pt(τi (x)))∇θPt(τi (x))∇θPt(τi (x))T )
+ ( Q∑ i=1 ∆x∇θg′t(τi (x)) )( Q∑ i=1 ∆x∇θg′t(τi (x)) )T If base distribution is standard Gaussian distribution, then ′t has to be negative for some points therefore the first term in the Hessian won’t remain positive semi-definite therefore, the loss function won’t remain convex in parameters of neural network θ if we use standard Gaussian distribution as base distribution. At points with negative values of g̃, Hessian of L̂1(g′t, x) with respect to θ can be negative semidefinie and L̂1(g′t, x) can be non-convex in θ.
Lemma D.2. (Approximated loss is close to optimal loss) For every ∈ (0, 1), there exist m > poly ( Uh, 1 ) , η = Õ ( 1 m ) and T = O ( U2h logm 2 ) such that, with at least 0.95 −
exp ( −
2m 128c21U 2 h logm
) probability, we get
1
T T−1∑ t=0 Esgd[L̂(f ′t ,X )]− L̂(F ∗′,X ) ≤ O( ′)
Proof. For set of examples X , define
L̂(f ′t ,X ) = 1 |X | ∑ x∈X L̂(f ′t , x)
From Lemma D.1, we know that L̂(g′t,X ) is convex in parameters θ. Using convexity of L̂(g′t,X ) wrt θ,
L̂(g′t,X )− L̂(g∗′,X ) ≤ 〈∇θL̂(g′t,X ), θt − θ∗〉 ≤ ‖∇θL̂(g′t,X )−∇θL̂(f ′t ,X )‖1‖θt − θ∗‖∞
+ 〈∇θL̂(f ′t ,X ), θt − θ∗〉 (D.1)
where ‖.‖1 and ‖.‖∞ denotes l1 and l∞ norm respectively. The stochastic gradient descent updates the parameters using xt at time t. g∗′ is defined as following.
g∗′(x) = m∑ r=1 ar0σ (wr0x+ br0) + m∑ r=1 ar0σ (wr0x+ br0) (w ∗ rx+ b ∗ r)
For stochastic gradient descent, we get
‖θt+1 − θ∗‖22 = ‖θt − η∇θL̂(f ′t , xt)− θ∗‖22 = ‖θt − θ∗‖22 + η2‖∇θL̂(f ′t , xt)‖22 − 2η〈θt − θ∗,∇θL̂(f ′t , xt)〉
Taking expectation wrt xt, Ext [ ‖θt+1 − θ∗‖22 ] = ‖θt − θ∗‖22 + η2Ext [ ‖∇θL̂(f ′t , xt)‖22 ] − 2η〈∇θL̂(f ′t ,X ), θt − θ∗〉 (D.2)
Using Eq.(D.2) and Eq.(D.1), L̂(g′t,X )− L̂(g′∗,X ) ≤ ∥∥∇θL̂(g′t,X )−∇θL̂(f ′t , x)∥∥1‖θt − θ∗‖∞ + ‖θt − θ∗‖22 − Ext [ ‖θt+1 − θ∗‖22 ] 2η
+ η
2 Ext
[ ‖∇θL̂(f ′t , xt)‖22 ] Using Eq.(C.4) and Eq.(C.5), we get∥∥∥∇θL̂(f ′t , xt)∥∥∥2
2 ≤ 2m∆̄2
Averaging from t = 0 to T − 1, we get
1
T T−1∑ t=0 Esgd[L̂(g′t,X )]− L̂(g′∗,X ) ≤ Γ ( sup t∈[T ] ‖θt‖∞ + ‖θ∗‖∞ ) + ‖θ0 − θ∗‖22 2ηT + ηm∆̄2
(i) = Γ ( sup t∈[T ] ‖θt‖∞ + ‖θ∗‖∞ ) + ‖θ∗‖22 2ηT + ηm∆̄2 (D.3)
Note that ∆̄ and Γ are defined in Eq.(C.3) and Eq.(C.17). Inequality (i) follows from the fact that θ0 = (0, 0, . . . , 0) ∈ R2m. Using Lemma B.3 and Lemma C.3, with at least 0.99 − 1c1 −
∑T t=1 exp ( − 64(c2−1) 2η2m2∆̄2t2 π ) − 1c6 − 1 c7 − exp ( − 2m 128c21U 2 h logm ) probability, we get
1
T T−1∑ t=0 Esgd[L̂(g′t,X )]− L̂(g′∗,X ) ≤ Γ ( sup t∈[T ] ‖θt‖∞ + ‖θ∗‖∞ ) + ‖θ∗‖22 2ηT + ηm∆̄2
1
T T−1∑ t=0 Esgd[L̂(f ′t ,X )]− L̂(g′∗,X ) (i) ≤ Γ ( sup t∈[T ] ‖θt‖∞ + ‖θ∗‖∞ ) + ‖θ∗‖22 2ηT + ηm∆̄2 + 3∆tnp
1
T T−1∑ t=0 Esgd[L̂(f ′t ,X )]− L̂(F ∗′,X ) (ii) ≤ Γ ( sup t∈[T ] ‖θt‖∞ + ‖θ∗‖∞ ) + ‖θ∗‖22 2ηT + ηm∆̄2
+ 3∆tnp + 3 ( 16c1 (c6 + c7) a logm+ ωφ−1(F∗′) (δ) + )
Note that inequality (i) and inequality (ii) uses Lemma B.3 and Lemma C.3 respectively. We choose following values/relations of η, T .
η =
m∆̄2
= m ( 6c1 a √ 2 logm )2 =
72c21m 2 a logm
T = ‖θ∗‖22 2η
= U2hπ
2m 2a
72c21m 2 a logm
2 2
= 18πc21 logm U 2 h
2
(D.4)
We can choose δ such that ωφ−1(F∗′) (δ) = . Using above inequalities, we get following equalities.
‖θ∗‖22 2ηT = ‖θ∗‖22 2η 2η ‖θ∗‖22 =
ηm∆̄2 = m∆̄2 m∆̄2 = 3 ( 16c1 (c6 + c7) a logm+ ωφ−1(F∗′) (δ) + ) ≤ 3 (16c1 (c6 + c7) a logm+ 2 )
Using Corollary B.1, we get
‖θ∗‖∞ ≤ Uh √ π√
2m a
‖θ∗‖2 ≤ √ m‖θ∗‖∞ ≤ Uh √ π√
2 √ m a
To get value of m,
sup t∈[T ] ‖θt‖∞ = sup t∈[T ]
η∆̄t = η∆̄T = ‖θ∗‖22∆̄
2 ≤ U
2 hπ 2m 2a
( 6c1 a √ 2 logm ) 2
= 3πU2hc1 √ logm√
2m a
sup t∈[T ]
‖θt‖∞ + ‖θ∗‖∞ ≤ πU2h (1 + 3c1) √ logm√
2m a
Γ = 192ηm1.5∆̄c1c2 at √ logm√
π + 16c1 am∆
t np
√ 2 logm
≤ 192ηm 1.5∆̄c1c2 at √ logm√
π + 16c1 am
√ 2 logm ( 192η2m1.5∆̄2c1c2 at 2 √
logm√ π ) ≤192ηm 1.5∆̄c1c2 at √
logm√ π
+ 3072 √ 2c21c2 2 aη
2t2m2.5 logm∆̄2√ π
≤ 192m 1.5c1c2 a √ logm√
π
( U2hπ
4m 2a
)( 6c1 a √ 2 logm ) + 3072 √ 2c21c2 2 am
2.5 logm√ π
( U2hπ
4m 2a
)2 ( 6c1 a √ 2 logm )2 ≤ 288 √ 2π √ m logmc21c2U 2 h + 13824 √ 2π3c41c2 √ m (logm) 2 U4h
2
≤ 14112 √ 2π3c41c2 √ m (logm) 2 U4h
2 Multiplication of Γ and ( supt∈[T ] ‖θt‖∞ + ‖θ∗‖∞ ) will be
Γ ( sup t∈[T ] ‖θt‖∞ + ‖θ∗‖∞ ) ≤ 14112 √ 2π3c41c2 √ m (logm) 2 U4h 2 ( πU2h (1 + 3c1) √ logm√ 2m a )
= 14112π2.5c41c2 (1 + 3c1) (logm) 2.5 U6h√
m a 3
Taking m as
m ≥ Ω
( c81c 2 2 (1 + 3c1) 2 U12h
2a 8
) (D.5)
Choosing m which satisfies above inequality will give us the following inequality.
Γ ( sup t∈[T ] ‖θt‖∞ + ‖θ∗‖∞ ) ≤
Using Eq.(C.11), we get
∆tnp =
( 192η2m1.5∆̄2c1c2 at 2 √
logm√ π ) ≤ ( 192m1.5c1c2 a √
logm√ π
)( U2hπ
4m 2a
)2 ( 6c1 a √ 2 logm )2 = ( 864π1.5c31c2 (logm) 1.5 U4h√
m 2 a
) (D.6)
Using sufficiently high m, we get
∆tnp ≤
( 864π1.5c31c2 (logm)
1.5 U4h√
m 2 a
)
≤ O
( c31c2 (logm) 1.5 U4h a 4
2 ac41c2 (1 + 3c1)U 6 h
)
= O
( 2 (logm) 1.5
c1 (1 + 3c1)U2h ) ≤ O ( )
Using Eq.(D.4) and Eq.(D.5), with at least 0.99− 1c1 − 1 c6 − 1c7 − ∑T t=1 exp ( − 64(c2−1) 2η2m2∆̄2t2 π ) −
exp ( −
2m 128c21U 2 h logm
) probability, we get
1
T T−1∑ t=0 Esgd[L̂(f ′t ,X )]− L̂(F ∗′,X ) ≤ Γ ( sup t∈[T ] ‖θt‖∞ + ‖θ∗‖∞ ) + ‖θ∗‖22 2ηT + ηm∆̄2
+ 2592π1.5c31c2 (logm) 1.5 U4h√
m 2 a + 3 (16c1 (c6 + c7) a logm+ 2 )
≤ 3 + 2592π 1.5c31c2 (logm) 1.5 U4h√
m 2 a + 3 (16c1 (c6 + c7) a logm+ 2 )
Taking c1 = 100, c2 = 2, c5 = 1000, c6 = 100, c7 = 100, a = 6000 logm ≤ , with at least 0.95− ∑T t=1 exp ( − 64η 2m2∆̄2t2 π ) − exp ( − 2m 128c21U 2 h logm ) probability,
1
T T−1∑ t=0 Esgd[L̂(f ′t ,X )]− L̂(F ∗′,X ) ≤ 3 + 2592π1.5c31c2 (logm) 1.5 U4h√ m 2 a +O ( )
≤ 3 +O ( 2
U2h
) +O ( )
For any ∈ [0, 1], with probability at least 0.96− ∑T t=1 exp ( − 64η 2m2∆̄2t2 π ) −exp ( − 2m 128c21U 2 h logm ) probability,
1
T T−1∑ t=0 Esgd[L̂(f ′t ,X )]− L̂(F ∗′,X ) ≤ O( )
To find lower bound on probability, we use ∑T t=1 1 t2 ≤ ∑∞ t=1 1 t2 ≤ 2.
T∑ t=1 exp ( −64η 2m2∆̄2t2 π ) (i) ≤ T∑ t=1
π
64η2m2∆̄2t2 ≤ π ( m∆̄2 )2 32 2m2∆̄2 ≤ π∆̄ 2
32 2 ≤ π 3200 ≤ 0.01
where inequality (i) follows from exp (−x) ≤ 1x for all x ≥ 0. Finally, with at least 0.95 − exp ( −
2m 128c21U 2 h logm
) probability,
1
T T−1∑ t=0 Esgd[L̂(f ′t ,X )]− L̂(F ∗′,X ) ≤ O( )

heading: E GENERALIZATION
text: In this section, we prove generalization guarantees to complement our optimization result, and complete the proof of our main theorem (Theorem E.1) about efficiently learning distributions using univariate normalizing flows. The proof in this section can be divided broadly in two parts. First, we prove that empirical average of L̂ (f ′t , x) and L̂ (F
∗′, x) on training examples are close to expectation of L̂ (f ′t , x) and L̂ (F
∗′, x) with respect to underlying data distribution, respectively. The similar argument is also used in Allen-Zhu et al. (2019). Second, we prove that L̂ (f ′t , x) and L̂ (F
∗′, x) are close to L (ft, x) and L (F ∗, x), respectively.
Recall that the approximate loss function L̂ is given by
L̂ (f ′t , x) = Q∑ i=1 ∆xφ (Nt (τi (x)))− log(φ (Nt (x)))
where
Nt(x) = m∑ r=1 ar0σ ( (wr0 + w t r)x+ br0 + b t r ) Lemma E.1. (Empirical Rademacher complexity for two-layer neural network) For every B > 0, for every n ≥ 1, with at least 1− 1c1 probability over random initialization, the empirical Rademacher complexity is bounded by
1 n Eξ∈{±1}n
[ sup
maxr∈[m]|wr|,|br|≤B n∑ i=1 ξiN(xi)
] ≤ 8c1 aBm √ 2 logm√
n
Proof. Using part a of Lemma H.5, we get that {x 7→ wrx + br | |wr| ≤ B, |br| ≤ B} has Rademacher complexity 2B√
n . Using part b of Lemma H.5, we get that {x 7→ ((wr0 + wr)x+ (br0 + br)) | |wr| ≤ B, |br| ≤ B,wr0, br0 ∼ N ( 0, 1m ) } has Rademacher complexity 2B√ n
. Using part c of Lemma H.5, we get that class of functions in F = {x 7→ N(x) | maxr∈[m] |wr| ≤ B,maxr∈[m] |br| ≤ B} has Rademacher complexity
R̂ (X ;F) ≤ 2‖a‖1 2B√ n (i) ≤ 8c1 aBm
√ 2 logm√
n
where inequality (i) follows from Lemma H.2 with at least 1− 1c1 probability over random initialization.
Define upper bound on maximum and lower bound on minimum value of loss function L̂ is given by
sup x L̂ (F ∗′, x) = sup x Q∑ i=1 ∆xF ∗′(τi (x))− log(F ∗′(x)) ≤ 2MF∗′ − log (mF∗′) := ML̂ (E.1)
inf x L̂ (F ∗′, x) = inf x Q∑ i=1 ∆xF ∗′(τi (x))− log(F ∗′(x)) ≥ 2mF∗′ − log (MF∗′) := mL̂ (E.2)
Lemma E.2. Suppose n is sufficiently high such that it satisfies following condition.
n ≥ O
(( ML̂ −mL̂ )2 (Q+ 1) 2 U4h (logm) 2
2
)
If n satisfies above condition, then with at least 0.98 probability over random initialization, population loss of any functions of set {x 7→ N(x) | |wr| ≤ η∆̄T, |br| ≤ η∆̄T ∀r ∈ [m]} is close to empirical loss i.e.
sup N∈F ∣∣∣∣∣Ex∈D [L̂ (f ′t , x)]− 1n n∑ i=1 L̂ (f ′t , x) ∣∣∣∣∣ ≤
Proof. Note that L̂ (f ′t , x) depends on neural network Nt(x) through (Nt (τ1 (x)) , Nt (τ2 (x)) , . . . , Nt (τQ (x)) , Nt(x)) vector. Using Fact H.8, with at least 1 − δ probability, we get
sup N∈F ∣∣∣∣∣Ex∼D [L̂ (f ′t , x)]− 1n n∑ i=1 L̂ (f ′t , x) ∣∣∣∣∣ ≤ 2√2Ls (Q+ 1) R̂ (X ;F) + b √ log 1δ 2n
(E.3)
where F = {x 7→ N(x) | |wr| ≤ η∆̄T, |br| ≤ η∆̄T ∀r ∈ [m]}. We get coordinate wise Lipschitz continuity of loss L̂ function as following.
Lj ≤ sup N∈F,|x|≤1 |∆xφ′ (N (τj (x)))|
≤ sup N∈F,|x|≤1
1 Q |φ′ (N (τj (x)))|
≤ 2 Q ∀i ∈ [Q]
LQ+1 ≤ sup N∈F,|x|≤1
φ′(N(x)) φ(N(x)) = sup N∈F,|x|≤1 exp (N(x)) I [N(x) ≤ 0] + I [Nt(x) ≥ 0] exp (N(x)) I [N(x) ≤ 0] + (N(x) + 1) I [N(x) ≥ 0]
≤ sup N∈F,|x|≤1 I [N(x) ≤ 0] + 1 N(x) + 1 I [N(x) ≥ 0]
≤ 1
Using Lemma H.4, standard Lipschitz constant of L̂ is
Ls ≤ √√√√Q+1∑ i=1 L2i ≤ √ 4 Q + 1 ≤ 2 (E.4)
To get upper bound on L̂, we use Lipschitz property of L̂.
∣∣∣L̂ (f ′t , x)− L̂(f̃ ′t , x)∣∣∣ ≤ Q∑ i=1 ∆x |N(τi (x))|+ |N(x)| (E.5)
Note that L̂ (f ′t , x) depends upon (N (τ1 (x)) , N (τ2 (x)) , . . . , N (τQ (x)) , N(x)) vector and similarly, L̂ ( f̃ ′t , x ) depends upon (0, 0, 0, . . . , 0, 0) Finding upper bound N(x) for all x ∈ [−1, 1],
sup N∈F,x∈[−1,1] N(x) ≤ sup |wr|≤η∆̄T,|br|≤η∆̄T,x∈[−1,1] Pt(x) + ∆ T np
≤ sup |wr|≤η∆̄T,|br|≤η∆̄T,x∈[−1,1] m∑ r=1 ar0σ (wr0x+ br0) + m∑ r=1 ar0 (wrx+ br)σ (wr0x+ br0) + ∆ T np
(i) ≤ 16c1 (c6 + c7) a logm+m ( 2c1 a √ 2 logm ) ( 2η∆̄T ) + ∆Tnp
≤ 16c1 (c6 + c7) a logm+m ( 2c1 a √ 2 logm ) ( 2η∆̄T ) + ∆Tnp
(ii) ≤ 16c1 (c6 + c7) a logm+m ( 48c21 2 a logm ( U2hπ
4m 2a
)) + ∆Tnp
≤ O ( U2h logm ) where inequality (i) uses Eq. (B.9), Lemma H.2 and Eq.(C.6). The inequality (ii) uses our choices of η and T from Eq.(D.4) and lower bound on m from Eq.(D.5). Define K as upper bound on supN∈F,x∈[−1,1]N(x).
K := O
( U2h logm ) (E.6)
Using upper bound on supN∈F,x∈[−1,1]N(x) and Eq.(E.5), we get upper bound on L̂(b).
b = K +K + L̂ (0, 0, ..., 0, 0) ≤ 2K + 2
Using value of b in Eq.(E.3) and Lemma E.1, with at least 1− δ − 1c1 probability, we get
sup N∈F ∣∣∣∣∣Ex∈D [L̂ (f ′t , x)]− 1n n∑ i=1 L̂ (f ′t , xi) ∣∣∣∣∣ ≤ 4 √ 2 (Q+ 1) 8c1 aη∆̄Tm √ 2 logm√
n + (2K + 2) √ log 1δ 2n
We use δ = 0.01 and choose n which satisfies following condition.
n ≥ O
(( ML̂ −mL̂ )2 (Q+ 1) 2 U4h (logm) 2
2
) (E.7)
Using above n, with at least 0.98 probability, we get
sup N∈F ∣∣∣∣∣Ex∈D [L̂ (f ′t , x)]− 1n n∑ i=1 L̂ (f ′t , xi) ∣∣∣∣∣ ≤ Lemma E.3. (Concentration on approximated loss of target function) Suppose n is sufficiently high such that it satisfies following condition.
n ≥ O
(( ML̂ −mL̂ )2 (Q+ 1) 2 U4h (logm) 2
2 ) If n satisfies above condition, then with at least 0.9999 probability, population loss of target function F ∗′ is close to empirical loss i.e.∣∣∣Ex∼D [L̂ (F ∗′, x)]− L̂ (F ∗′,X )∣∣∣ ≤
Proof. Finding minimum value (mL̂) and maximum value (ML̂) of loss function L̂,
sup x L̂ (F ∗′, x) = sup x Q∑ i=1 ∆xF ∗′(τi (x))− log(F ∗′(x)) ≤ 2MF∗′ − log (mF∗′) = ML̂
inf x L̂ (F ∗′, x) = inf x Q∑ i=1 ∆xF ∗′(τi (x))− log(F ∗′(x)) ≤ 2mF∗′ − log (MF∗′) = mL̂
where MF∗′ = maxx∈[−1,1] F ∗′ (x) and mF∗′ = maxx∈[−1,1] F ∗′ (x). Using Hoeffding’s inequality,
Pr (∣∣∣Ex∼D [L̂ (F ∗′,X )]− L̂ (F ∗′,X )∣∣∣ ≥ ) ≤ exp(− 2n 2( ML̂ −mL̂ )2 )
Taking n as
n ≥ O
(( ML̂ −mL̂ )2 (Q+ 1) 2 U4h (logm) 2
2
)
With at least probability 1− exp ( − 2n 2
(ML̂−mL̂) 2 ) ,∣∣∣Ex∼D [L̂ (F ∗′, x)]− L̂ (F ∗′,X )∣∣∣ ≤ (E.8)
Corollary E.1. Under same setting as Lemma D.2 and
n ≥ O
(( ML̂ −mL̂ )2 (Q+ 1) 2 U4h (logm) 2
2
)
then with at least 0.92− 2 exp ( − m8 2a ) − exp ( − 2m 128c21U 2 h logm ) − exp ( − 2n 2 (ML̂−mL̂) 2 ) probability, we get
Esgd
[ 1
T T−1∑ t=0 Ex∼D [ L̂(f ′t , x) ]] − Ex∼D [ L̂(F ∗′, x) ] ≤ O( )
Proof. Using Lemma D.2, Lemma E.2 and Lemma E.3, with at least 0.92 − 2 exp ( − m8 2a ) −
exp ( −
2m 128c21U 2 h logm
) − exp ( − 2n 2
(ML̂−mL̂) 2
) probability, we get
Esgd
[ 1
T T−1∑ t=0 Ex∼D [ L̂(f ′t , x) ]] − Ex∼D [ L̂(F ∗′, x) ] ≤ O( )
Theorem E.1. (loss function is close to optimal) For every ∈ (0, 1), there exist m > poly ( Uh, 1 ) , η = Õ ( 1 m ) and T = O ( U2h logm 2 ) , for any target function F ∗′ with finite second order derivative and number of quadrature points Q ≥ 4MF∗′′+4K2 and number of training points
n ≥ O ( (ML̂−mL̂) 2 (Q+1)2U4h(logm) 2
2
) , with at least 0.92−2 exp ( − m8 2a ) −exp ( − 2m 128c21U 2 h logm ) −
exp ( − 2n 2
(ML̂−mL̂) 2
) probability, we have
Esgd
[ 1
T T−1∑ t=0 Ex∼D [L(ft, x)]
] − Ex∼D [L(F ∗, x)] ≤ O( )
where Uh is the complexity of target function defined in B.1 and
MF∗′′ = sup x∈[−1,1]
F ∗′′ (x)
MF∗′ = sup x∈[−1,1]
F ∗′ (x)
mF∗′ = inf x∈[−1,1]
F ∗′ (x)
ML̂ = 2MF∗′ − log (mF∗′) mL̂ = 2mF∗′ − log (MF∗′)
K2 = O
( U2h (logm) 1.5 )
Proof. First, we will try to bound
∣∣∣L̂(F ∗′, x)− L(F ∗, x)∣∣∣ ≤ ∣∣∣∣∣ Q∑ i=1 ∆xF ∗′ (τi (x))− F ∗(x) ∣∣∣∣∣ ≤2MF ∗′′
Q
Similarly, bounding error for f ′t , we will get
∣∣∣L̂(f ′t , x)− L(ft, x)∣∣∣ ≤ ∣∣∣∣∣ Q∑ i=1 ∆xf ′ t (τi (x))− ft(x) ∣∣∣∣∣ ≤ 2 (supx f ′′ t (x))
Q
To get supx f ′′ t (x), we will use Eq.(E.6). sup x f ′′t (x) ≤ sup x |N ′t(x)|
≤ sup x m∑ r=1 ar0σ ′ ((wr0 + wtr)x+ br0 + btr) (wr0 + wtr)
≤ sup x m∑ r=1 ar0 ( wr0 + w t r ) I [ (wr0 + w t r)x+ br0 + b t r ≥ 0 ] ≤ sup
x ∑ r∈H ar0 ( wr0 + w t r ) I [wr0x+ br0 ≥ 0] + ∑ r/∈H ar0 ( wr0 + w t r ) I [ (wr0 + w t r)x+ br0 + b t r ≥ 0 ] ≤ sup
x ∑ r∈H ar0wr0I [wr0x+ br0 ≥ 0] + ∑ r∈H ar0w t rI [wr0x+ br0 ≥ 0]
+ ∑ r/∈H ar0wr0I [ (wr0 + w t r)x+ br0 + b t r ≥ 0 ] + ∑ r/∈H ar0w t rI [ (wr0 + w t r)x+ br0 + b t r ≥ 0 ] (i) ≤ 16c1c6 a (logm) +m ( 2c1 a √ 2 logm ) ( η∆̄T
) + ( c2 4 √ 2ηm √ m∆̄t√
π
)( 2c1 a √ 2 logm )(2c6√2 logm√ m )
+ ( c2 4 √ 2ηm √ m∆̄t√
π
)( 2c1 a √ 2 logm ) ( η∆̄T
) ≤ O ( ) +m ( 2c1 a √ 2 logm )( ∆̄ U2hπ
4m 2a ) + ( c2 4 √ 2m √ m∆̄√
π
)( 2c1 a √ 2 logm )(2c6√2 logm√ m ) U2hπ
4m 2a
+ ( c2 4 √ 2m √ m∆̄√
π
)( 2c1 a √ 2 logm )( ∆̄ ( U2hπ
4m 2a
)2)
≤ O ( ) +O ( U2h logm ) +O ( U2h (logm) 1.5 ) +O ( )
≤ O
( U2h (logm) 1.5 ) Define K2 as upper bound on supx f ′′ t (x),
K2 = O
( U2h (logm) 1.5 ) Taking Q as
Q ≥ 2MF ∗′′ + 2K2
(E.9)
Using given value of Q, we get that∣∣∣L̂(F ∗′, x)− L(F ∗, x)∣∣∣ ≤ (E.10)∣∣∣L̂(f ′t , x)− L(ft, x)∣∣∣ ≤ (E.11) Using these relations, we get
Esgd
[ 1
T T−1∑ t=0 Ex∼D [L(ft, x)]
] − Ex∼D [L(F ∗, x)] ≤ O( )
By definition of KL divergence, we get
Esgd
[ 1
T T−1∑ t=0 KL (pF∗,Z ||pft,Z)
] ≤ O( )

heading: F PROBLEM IN TRAINING OF CONSTRAINED NORMALIZING FLOW
text: In this section, we provide reasons and details why changing initialization will not solve the problem (described in section 2.1 ) in the training of Constrained Normalizing Flow. The neural network in Constrained Normalizing Flow (CNF) is defined as
N(x) = τ m∑ r=1 ar0 tanh ((wr0 + wr)x+ (br + br0)) , with constraints wr0 + wr ≥ , for all r.
Here, > 0 is a small constant and τ is a normalization constant which only depends on m. The pseudo network for this neural network will be
P (x) = τ m∑ r=1 ar0 ( tanh(wr0x+ br0) + tanh ′(wr0x+ br0) (wrx+ br) ) ,
with constraints wr0 +wr ≥ , for all r. We decompose P (x) into two parts: P (x) = Pc(x)+P`(x), where
Pc(x) = τ m∑ r=1 ar0 (tanh(wr0x+ br0)) and P`(x) = τ m∑ r=1 ar0 ( tanh′(wr0x+ br0) (wrx+ br) ) .
Note that Pc(x) only depends upon initialization and does not depend on wr and br. Hence, it can not approximate the target function after the training, therefore P`(x) needs to approximate target function with Pc(x) subtracted. Note that normalization constant τ is necessary to keep P`(x) as same order of F ∗′(x) with Pc(x) subtracted. Note that Now, we will show that P`(x) can not approximate “sufficiently non-linear” functions. Using half-normal distribution initialization of wr0 with (mean, variance) of normal distribution as ( 0, 1m ) and normal distribution initialization of br0 with (mean,
variance) as ( 0, 1m ) , wr0 and |br0| are O (√ logm√ m ) with high probability; therefore, |wr0x+ br0|
is O (√
logm√ m ) . Using the fact that tanh′(y) ≈ 1 for small y, we get that tanh′ (wr0x+ br0) ≈ 1
for sufficient large m. In such cases, P` (x) becomes linear function in x and won’t be able to approximate sufficiently non-linear function. Using other variance of initializations leads to problem in other parts of the proof. Remark F.1. Using different variance in initialization of wr0 and br0 will not solve the problem in the training of CNFs (mentioned in section 2.1).
Informal Proof: As described above, if we use variance of initialization of wr0 and br0 as 1m , then P`(x) cannot approximate “sufficiently non-linear” target function. The same problem will remain if variance of initialization of wr0 and br0 is o ( 1
logm
) . For variance of initialization of wr0 and br0 is
Ω (
1 logm
) and O(1), we will prove by contradiction that there doesn’t exist any pseudo network with
sufficiently small norm on ‖θ∗‖2 for which the pseudo network can approximate the target function and for bigger norm on ‖θ∗‖2, pseudo network P (x) during the training does not stay close to N(x).
Remark F.2. There doesn’t exist any pseudo network with sufficiently small norm on ‖θ∗‖2 for which the pseudo network can approximate the target function and for bigger norm on ‖θ∗‖2, pseudo network P (x) during the training does not stay close to N(x).
Informal Proof: Suppose there exist P ∗(x) function which approximates the target function F ∗′ (x). As described earlier, P ∗c (x) only depends upon initialization and does not depend onwr and br. Hence,
it can not approximate the target function after the training, therefore P ∗` (x) needs to approximate target function with P ∗c (x) subtracted. Hence, P ∗ c (x), P ∗ ` (x) and F ∗′(x) should be Θ(1). From the
condition that P ∗c (x) needs to be O(1), we get that τ will be o ( 1 σwbm ) for the considered range of variance of wr0 and br0 where σwb is variance of wr0 and br0. We denote variance of ar0 as σa. From the condition that P ∗` (x) needs to be Θ(1), we need
τ m∑ r=1 ar0 ( tanh′(wr0x+ br0) (w ∗ rx+ b ∗ r) ) = Θ (1)
=⇒ τmσa √ logm‖θ∗‖∞ = Θ (1) =⇒ ‖θ∗‖∞ = Θ (
1
τmσa √ logm ) Using norm equivalance, we need
‖θ∗‖2 = Θ (
1
τ √ mσa √ logm ) Doing similar calculation as in Lemma D.2 for the loss of normalizing flow LG, we will get Eq.(D.3) and from Eq.(D.3), to get small training error, we need
‖θ∗‖22 ηT = O ( )
=⇒ ηT = O ( ‖θ∗‖22 ) =⇒ ηT = O ( 1
mτ2σ2a logm
) (F.1)
Now, to find coupling of function N(x) and P (x) as well as derivative of function N ′(x) and P ′(x), we find upper bound on the derivative of loss function and wr and br.
∂LG(f t, x)
∂wr =τNt(x)(ar0σ
′((wr0 + w t r)x+ br0 + b t r))
− τ N ′(x) (ar0(σ ′((wr0 + w t r)x+ br0 + b t r) + (wr0 + w t r)xσ ′′((wr0 + w t r)x+ br0 + b t r)))
We assume that LG(ft, x) is L̃1-lipschitz continuous wrt N and L̃2-lipschitz continuous wrt N ′. Assuming |σ′(.)| ≤ 1 and |x| ≤ 1,∣∣∣∣∂LG(ft, x)∂wr ∣∣∣∣ ≤ τL̃1ar0 + τL̃2ar0 (1 + |wtr + wr0||σ′′((wr0 + wtr)x+ br0 + btr)|) Assuming |σ′′(.)| ≤ C,∣∣∣∣∂LG(ft, x)∂wr
∣∣∣∣ ≤ τL̃1ar0 + τL̃2ar0 (1 + C(|wtr|+ wr0)) Using Lemma H.2 for ar0 and wr0, with at least 1− 1c1 − 1 c2
probability,∣∣∣∣∂LG(ft, x)∂wr ∣∣∣∣ ≤ (2c1σaτ√2 logm)(L̃1 + L̃2 (1 + C (|wtr|+ 2c2σwb√2 logm))) (F.2)
For projected gradient descent, |wtr| ≤ η t−1∑ i=0 ∣∣∣∣∂LG(ft, xi)∂wr ∣∣∣∣
≤ η t−1∑ i=0 (( 2c1σaτ √ 2 logm )( L̃1 + L̃2 + 2c2CσwbL̃2 √ 2 logm ) + ( 2c1σaτ √ 2 logm ) L̃2C|wir| ) ≤ ( 2ηc1σaτ √ 2 logm )( L̃1 + L̃2 + 2c2CL̃2σwb √ 2 logm ) t+ ( 2ηc1σaτ √ 2 logmL̃2C )(t−1∑
i=0
|wir|
)
Define α and β as α = ( 2ηc1τσa √ 2 logm )( L̃1 + L̃2 + 2c2CL̃2σwb √ 2 logm )
β = ( 2ηc1σaτ √ 2 logmL̃2C )
Using α and β,
|wtr| ≤ αt+ β ( t−1∑ i=0 |wir| )
where t−1∑ i=0 |wir| ≤ α(t− 1) + (1 + β) ( t−2∑ i=0 |wir| )
≤ α ((t− 1) + (1 + β)(t− 2)) + (1 + β)2 ( t−3∑ i=0 |wir| ) ≤ α ( (t− 1) + (1 + β)(t− 2) + (1 + β)2(t− 3) ) + (1 + β)3
( t−4∑ i=0 |wir| )
In general, we can write
t−1∑ i=0 |wir| ≤ α t−t′−1∑ i=1 (1 + β)i−1(t− i) + (1 + β)(t−t′−1)  t′∑ i=0 |wir|  Taking t′ = 0,
t−1∑ i=0 |wir| ≤ α ( t−1∑ i=1 (1 + β)i−1(t− i) ) ∑t−1 i=1(1 + β)
(i−1)(t− i) is sum of an arithmetic-geometric progression (AGP). Using Fact H.6, t−1∑ i=0 |wir| ≤ α ( t−1∑ i=1 (1 + β)i−1(t− i) )
= α
( (t− 1)− (1 + β)t−1
−β −
(1 + β) ( 1− (1 + β)t−2 ) β2 )
= α
( β(1 + β)t−1 − β(t− 1)− (1 + β) + (1 + β)t−1
β2 ) = α ( (1 + β)t − (1 + βt)
β2
) (F.3)
Using Eq.(F.3) to bound |wtr|, |wtr| ≤ α ( t+ β ( (1 + β)t − (1 + βt)
β2 )) = α ( (1 + β)t − 1
β ) = ( L̃1 + L̃2 + 2c2CL̃2σwb √ 2 logm
L̃2C
)(( 1 + 2ηc1σaτ √ 2 logmL̃2C )t − 1 ) = ∆tw
Similarly, we
∂LG(ft, x)
∂br = Nt(x)τ
( ar0σ ′((wr0 + w t r)x+ br0 + b t r) ) − τ N ′t(x) ( ar0(wr0 + w t r)σ ′′((wr0 + w t r)x+ br0 + b t r) )
We assume that LG(ft, x) is L̃1-lipschitz wrt Nt(x) and L̃2-lipschitz wrt N ′t(x). Additionaly, assuming that |σ′(.)| ≤ 1 and |σ′′(.)| ≤ C,
∣∣∣∣∂LG(ft, x)∂br ∣∣∣∣ ≤ L̃1ar0τ + L̃2ar0Cτ (wr0 + |wtr|)
Using Lemma H.2 for ar0 and wr0, with at least 1− 1c1 − 1 c2 probability,
∣∣∣∣∂LG(ft, x)∂br ∣∣∣∣ ≤ (2c1σa√2 logm) τ (L̃1 + L̃2C|wr|+ 2c2CL̃2σwb√2 logm) (F.4)
For projected gradient descent,
|btr| ≤ η t−1∑ i=0 ∣∣∣∣∂LG(ft, xi)∂br ∣∣∣∣
= 2ηc1σaτ √ 2 logm ( L̃1 + 2c2L̃2Cσwb √ 2 logm ) t+ 2ηc1σaτL̃2C √ 2 logm ( t−1∑ i=0 |wir| )
Using Eq.(F.3), |btr| ≤ 2ηc1σaτ √ 2 logm ( L̃1 + 2c2L̃2Cσwb √ 2 logm ) t
+ 2ηc1σaL̃2C √ 2 logm
( L̃1 + L̃2 + 2c2CL̃2σwb √ 2 logm
2ηc1σa √ 2 logmL̃22C 2
)(( 1 + 2ηc1τσa √ 2 logmL̃2C )t − 1 )
= 2ηc1σaτ √ 2 logm ( L̃1 + 2c2L̃2Cσwb √ 2 logm ) t
+
( L̃1 + L̃2 + 2c2CL̃2σwb √ 2 logm
L̃2C
)(( 1 + 2ηc1σaτ √ 2 logmL̃2C )t − 1 ) = ∆tb
Finding lower bound on ∆tb, we get
∆tb ≥ 2ηc1σaτ √ 2 logm ( L̃1 + 2c2L̃2Cσwb √ 2 logm ) t
+
( L̃1 + L̃2 + 2c2CL̃2σwb √ 2 logm
L̃2C
)(( 1 + 2ηtc1σaτ √ 2 logmL̃2C ) − 1 )
= 2ηc1σaτ √ 2 logm ( L̃1 + 2c2L̃2Cσwb √ 2 logm ) t
+
( L̃1 + L̃2 + 2c2CL̃2σwb √ 2 logm
L̃2C
)( 2ηtc1σaτ √ 2 logmL̃2C ) = Ω (ηtσaτσwb logm)
We get similar lower bound on ∆tw.
∆tw = Ω (ηtσaτσwb logm)
Now, we show coupling between N ′t(x) and P ′ t (x). Assuming that σ ′ is C-lipschitz continuous,
|N ′t(x)− P ′t (x)| = ∣∣∣∣∣τ m∑ r=1 ar0 ( (wtr + wr0) ( σ′((wr0 + w t r)x+ br0 + b t r)− σ′(wr0x+ br0) ) − σ′′(wr0x+ br0) ( wr0(w t rx+ b t r) )) ∣∣∣∣∣
≤ Cτ m∑ r=1 2ar0|wtr + wr0|+ Cτ m∑ r=1 ar0wr0|wtrx+ btr|
= Cτ m∑ r=1 ar0 ( 2|wtr + wr0|+ wr0|wtrx+ btr| ) (i)
≤ Cτ ( 2c1σa √ 2 logm )( ‖W t‖1 + ‖W0‖1 + 2c2σwb √ 2 logm ( ‖W t‖1 + ‖Bt‖1 )) = O ( τσaσwbm logm ( ∆tw + ∆ t b
)) where inequality (i) follows from Fact H.2. Now, using t = T to find upper bound on |N ′T (x)− P ′T (x)|, we get
|N ′T (x)− P ′T (x)| = O ( τσaσwbm logm ( ∆Tw + ∆ T b )) = O ( τσaσwbm logm ( ∆Tw + ∆ T b
)) = O ( τσaσwbm logm ( ∆Tw + ∆ T b
)) = O (τσaσwbm logm (ηTσaτσwb logm))
= O ( ηTτ2σ2aσ 2 wbm (logm) 2 )
= O
( τ2σ2aσ 2 wbm (logm) 2
mτ2σ2a logm
)
= O
( σ2wb (logm) ) For σwb in range Ω ( 1
logm ) and O(1), |N ′T (x)− P ′T (x)| can become very high and in those cases,
N ′T (x) and P ′ T (x) willnot remain close.

heading: G ADDITIONAL EXPERIMENTS
text: In this section, we show experimental results on synthetic 1D data to support our theoretical findings. We use the same architecture and initialization as described in Sec. 2 for both constrained and unconstrained normalizing flows. In all our experiments, we fix the weights of the output layer and train the weights and biases of the hidden layer. For training, we use mini-batch SGD with batch size 32. We use 2 datasets each with 10,000 data points. One of the dataset is mixture of 2 Gaussians and other one is mixture of 3 beta distributions. All results are averaged over 3 different iterations.
G.1 RESULTS FOR UNCONSTRAINED NORMALIZING FLOW
In Fig. 2, we show comparison of data distribution and generated data distribution for unconstrained normalizing flow. Unconstrained normalizing flow with exponential distribution as a base distribution learns the data distribution well. We study the effect of overparameterization on L2-norm of W t and Bt and convergence speed. To reproduce situation similar to the theoretical analyses for unconstrained normalizing flow, we choose learning rate as cm where c is a constant. The first row of Figure 3 contains results for mixture of Gaussians dataset and the second row contains results for mixtures of beta distributions dataset. From Fig. 3, we see that L2-norm of W t and Bt decreases with increasing m. Moreover, the change is proportional to 1/ √ m which is similar to the bound in theoretical result. From the last column of Fig. 3, we see that the training speed for different values of m remains almost constant. Our choice of T in theoretical analysis also poly-logarithmically depends upon m. We obtained similar results for Gaussian distribution as well.
G.2 RESULTS FOR CONSTRAINED NORMALIZING FLOW
In Sec. 2.1, we suggested that high overparameterization may adversely affect training for constrained normalizing flows. We now give experimental evidence for this in Figs 4, 5 and 6. We use Gaussian distribution as a base distribution for all our experiments of constrained normalizing flow. In Fig.4, we see that for neural network with m = 100 and m = 400, the training loss decreases stably. In Figs. 5 and 6, we see that as we increase the learning rate, training becomes more stable for larger m. Note that for learning rate equal to 0.025 and 0.0125, constrained normalizing flow with m = 1600 doesn’t learn anything due to small learning rate. We observe that the L2-norms of W t and Bt for m = 6400 are at least at large as those of m = 1600. On both datasets, as we increase the learning rate, L2-norm of Bt increases (except for learning rate=0.05 of mixture of beta distribution) and learning of constrained normalizing flow becomes more and more stable. We also experimented with more number of epochs (1000 epochs) for mixture of Gaussian dataset for number of hidden layers m = 1600, 6400 (see Fig.7). These observations support our claim in Sec.2.1 that for learning and approximation of overparameterized constrained normalizing flow, neural networks need large L2-norms of W t and Bt.

heading: H USEFUL FACTS
text: Lemma H.1. Suppose Zk ∼ N (0, σ2) and Y = ∑n k=1 Z 2 k is chi-squared distribution with following property for all t ∈ (0, 1).
Pr [∣∣∣∣∣ 1n n∑ k=1 Z2k − σ2 ∣∣∣∣∣ ≥ t ] ≤ 2 exp ( − nt 2 8σ4 )
Proof. From example 2.11 from Wainwright (2019), for Z ′k ∼ N (0, 1) and Y = ∑n k=1 Z ′2 k is chi-squared distribution with following property for all t ∈ (0, 1).
Pr [∣∣∣∣∣ 1n n∑ k=1 Z ′2k − 1 ∣∣∣∣∣ ≥ t ] ≤ 2 exp ( −nt 2 8 ) Using above equation for Zkσ ,
Pr [∣∣∣∣∣ 1n n∑ k=1 Z2k σ2 − 1 ∣∣∣∣∣ ≥ tσ2 ] ≤ 2 exp ( − nt 2 8σ4 )
Pr [∣∣∣∣∣ 1n n∑ k=1 Z2k − σ2 ∣∣∣∣∣ ≥ t ] ≤ 2 exp ( − nt 2 8σ4 )
Lemma H.2. Let X1, X2, ..., Xn be independent random variables fromN (0, σ2), then with at least 1− 1c1 probability, following holds.
max i∈{1,2,...,n}
|Xi| ≤ 2c1σ √ 2 log n
Proof. From Romberg (2012), E [
max i∈{1,2,...,n}
|Xi| ] ≤ σ (√ 2 log n+ 1 ) ≤ 2σ (√ 2 log n ) Assuming n ≥ 2, the last inequality follows. Using Markov’s inequality,
Pr (
max i∈{1,2,...,n}
|Xi| ≥ 2c1σ (√ 2 log n )) ≤ 1 c1
Pr (
max i∈{1,2,...,n}
|Xi| ≤ 2c1σ (√ 2 log n )) ≥ 1− 1
c1
s
Lemma H.3. For standard Gaussian random variable X from N (0, σ2), following anticoncentration inequality holds.
Pr (|X| ≤ R) ≤ 2R σ √ 2π
Proof. (From Du et al. (2018)) For standard Gaussian random variable Xσ ,
Pr (∣∣∣∣Xσ ∣∣∣∣ ≤ R) ≤ 2R√2π
Using R = R ′
σ , we get the required result.
Lemma H.4. Suppose function f : Rd → R is Lg-Lipschitz continuous and Li-coordinate wise Lipschitz continuous i.e.
|f(a)− f(b)| ≤Lg‖a− b‖ ∀a,b ∈ Rd (Standard Lipschitz continuity)
|f(a1, a2, ..., ai, ..., ad)− f(a1, a2, ..., bi, ..., ad)| ≤Li|ai − bi| ∀a1, a2, ..., ai, ..., ad, bi ∈ R and ∀i ∈ [d] (Coordinate-wise Lipschitz continuity)
If a function f satisfies Li-coordinate wise Lipschitz continuity for all i, then function f follows following inequality.
|f(a1, a2, ..., ad)− f(b1, b2, ..., bd)| ≤ n∑ i=1 Li |ai − bi|
Moreover, the function f also satisfies standard Lipschitz continuity with Lg Lipschitz constant where inequality between Lg and Li is as follows.
Lg ≤ √√√√ d∑ i=1 L2i
Proof. Define a = (a1, a2, ..., ad) and b = (b1, b2, ..., bd).
|f(a1, a2, ..., ad)− f(b1, b2, ..., bd)| ≤ |f(a1, a2, ..., ad)− f(b1, a2, ..., ad)| + |f(b1, a2, a3, ..., ad)− f(b1, b2, a3, ..., ad)| + |f(b1, b2, a3, ..., ad)− f(b1, b2, b3, ..., ad)| + ...+ |f(b1, b2, ..., bd−1, ad)− f(b1, b2, b3, ..., bd)|
≤L1 |a1 − b1|+ L2 |a2 − b2|+ ...+ Ld |ad − bd|
≤ √√√√ d∑ i=1 L2i ‖a− b‖2
where last inequality follows from Cauchy-Schwarz inequality.
Fact H.1. (Hoeffding’s inequality on Binomial random variable) If we have a binomial random variable with parameters n (total number of trials) and p (probability of success). For number successful trial k ≥ np, following inequality holds.
Pr (X ≥ k) ≤ exp ( −2n ( k n − p )2)
Fact H.2. (Half-normal distribution) If X follows a normal distribution with with mean 0 and variance σ2, N ( 0, σ2 ) , then Y = |X| = Xsign (X) follows a half-normal distribution with mean E [Y ] = σ √
2√ π .
Fact H.3. For a gaussian random variable X ∼ N (0, σ2), ∀t ∈ (0, σ), we have
Pr(|X| ≥ t) ≥ 1− 4t 5σ
Fact H.4. The sum of reciprocals of the squares of the natural numbers is given by ∞∑ n=1 1 n2 = π2 6 ≤ 2
Fact H.5. (Theorem 3.1(r ′ 5) of Li & Yeh (2013)) For any α > 1 and x ∈ [ 0, 1α−1 ) ,
(1 + x) α ≤ 1
1− αx1+x = 1 +
αx
1− (α− 1)x
Fact H.6. If Arithmetic-Geometric Progression(AGP) is as follows.
a, (a+ d)r, (a+ 2d)r2, (a+ 3d)r3, ...., [a+ (n− 1)d] rn−1
where a is the initial term, d is the common difference and r is the common ratio. The sum of the first n terms of the AGP (Sn) is given by
Sn = a− [a+ (n− 1)d] rn 1− r + dr ( 1− rn−1 ) (1− r)2
Fact H.7. ( Lemma A.3 from Ji et al. (2020) ) The Fourier transform of f is defined as
f̂(w) = ∫ f(x)e2πiwxdx
The polar decomposition of the Fourier transform f̂ is f̂(w) = ∣∣∣f̂(w)∣∣∣ e2πiθf (w) with |θf (w)| ≤ 1.
The Fourier transform f̂ follows below properties. 1. ∣∣∣f̂(w)∣∣∣ ≤ ‖f‖L1 for any real number w.
2. Let α > 0 be given and define β := 12πα . Gα is Gaussian with coordinate-wise variance α2. Then ∣∣∣Ĝα∣∣∣ = Ĝα (meaning Ĝα has no radial component) and
Ĝα(w) = 1√
2πα2 Gβ(w) =
√ 2πβ2Gβ(w) = √ 2πG (w/β)
Definition H.1. Let F be a set of functions Rd → R and X = (x1, x2, ..., xn) be a finite set of samples. The empirical Rademacher complexity of F with respect to X is defined by
R̂ (X ;F) = Eξ∼{±1}n [
sup f∈F
1
n n∑ i=1 ξif(xi) ] Lemma H.5. The Rademacher complexity have following properties.
a. Suppose |x| ≤ 1 for allX . The classF = {x→ wx+b | |w| ≤ B, |b| ≤ B} has Rademacher complexity R̂ (X ,F) ≤ 2B√
n
b. Given F1,F2 classes of functions, then R̂ (X ;F1 + F2) = R̂ (X ;F1) + R̂ (X ;F2)
c. Given F1,F2, ...,Fm classes of functions from X → R and suppose w ∈ Rm is a fixed vector, then F ′ = {x → ∑m r=1 wrσ (fr(x)) | fr ∈ Fr} satisfies R̂ (X ;F ′) ≤
2‖w‖1 maxr∈[m] R̂ (X ;Fr) where σ is 1-Lipschitz continuous function.
Proof. The b and c parts of the proposition are from Allen-Zhu et al. (2019) . Proof of the a part is as following.
R̂ (X ,F) = 1 n Eξ∼{±1}n [ sup f∈F w ( n∑ i=1 ξixi ) + b ( n∑ i=1 ξi )]
= B
n Eξ∼{±1}n [∣∣∣∣∣ n∑ i=1 ξixi ∣∣∣∣∣+ ∣∣∣∣∣ n∑ i=1 ξi ∣∣∣∣∣ ]
Using Jensen’s inequality, we get
Eξ∼{±1}n [∣∣∣∣∣ n∑ i=1 ξixi ∣∣∣∣∣ ] = Eξ  ∣∣∣∣∣ n∑ i=1 ξixi ∣∣∣∣∣ 2 0.5  ≤ Eξ ∣∣∣∣∣ n∑ i=1 ξixi ∣∣∣∣∣ 2 0.5
Using independence of ξi for all i ∈ [n], we get
Eξ ( n∑ i=1 ξixi )2 = Eξ ∑ i,j ξiξjxixj  =
n∑ i=1 |xi|2 ≤ n
Using same technique, we will get same bound for Eξ [| ∑n i=1 ξi|].
R̂ (X ,F) ≤ 2B√ n
Fact H.8. (Rademacher Complexity) If F1,F2, ...,Fk are k classes of functions Rd → R and Lx : Rd → [−b, b] is Lg-Lipschitz continuous function for any x ∼ D, then
sup f1∈F1,...,fk∈Fk ∣∣∣∣∣Ex∈D [Lx (f1(x), ..., fk(x))]− 1n n∑ i=1 Lx (f1(xi), ..., fk(xi)) ∣∣∣∣∣ ≤ 2R̂ (X ;L) + b √ log 1δ 2n
where L is set of all functions Lx. Using vector contraction inequality from Maurer (2016), we get
sup f1∈F1,...,fk∈Fk ∣∣∣∣∣Ex∈D [Lx (f1(x), ..., fk(x))]− 1n n∑ i=1 Lx (f1(xi), ..., fk(xi)) ∣∣∣∣∣ ≤ 2 √
2Lg ( k∑ i=1 R̂ (X ;Fi) ) + b √ log 1δ 2n

Review summaries:
This paper proved that for a certain modified version of sufficiently-overparametrized univariate normalizing flows where the underlying neural network has only one hidden layer, with high probability it can learn a distribution that is close enough to the target distribution where the distance can be measured in, e.g., KL divergence. The width of the network, number of samples, and the number of quadrature points are required to be at least polynomial in inverse of error rate and complexity measure of the target distribution. The authors also provided theoretical evidence and did experiments on synthetic Gaussian mixture datasets to show that another variation of the normalizing flow model does not benefit from overparametrization under this one-hidden-layer univariate setting.

This paper studies overparameterization over unsupervised learning. In detail, it uses constrained normalizing flows (CNF) and unconstrained normalizing flows (UNF) to learn the underlying unknown one-dimensional distribution, which can be parameterized by a two-layer neural network. The authors propose theoretical results for UNF and suggest that by selecting wide enough neural networks, a great number of random samples and number of quadrature points, a two-layer neural network is able to learn the true UNF up to small error. Experiment results are presented for both CNF and UNF, which back up their claim. 

The paper studies the role of overparameterization in learning normalizing flow models. More specifically, the authors analyze the optimization and generalization of such a model when the transport map f is parameterized by a two-layer neural network with potentially many hidden units (or highly over-parameterized). Importantly, the focus is on univariate data distributions.