Learning and Generalization in Univariate Overparameterized Normalizing Flows
Authors: Kulin Shah
Amit Deshpande
Navin Goyal
Venue:  (2021)

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, 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.

Under review as a conference paper at ICLR 2021
LEARNING AND GENERALIZATION IN UNIVARIATE OVERPARAMETERIZED NORMALIZING FLOWS
Anonymous authors Paper under double-blind review
ABSTRACT
In supervised learning, it is known that overparameterizee 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 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, provide evidence that for class of NFs, overparametrriation 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 overparameter- ized normalizing flows in unsupervised learning. We also provide experimental validation to support our theoretical analysis in practice.
INTRODUCTION
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 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 typically 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 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 optimiza- tion problem for fully connected neural network with one hidden layer of neurons with ReL.U activations. Around 2018, 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): [i Li& & Liang (2018): Du et al.
(0018 Allen-Zhu et al. (2019; Arora al. (2019). Of these, Allen al. (2019) directly relevant to our paper and will be discussed later.
The role of overparameterizztion, and provable training and generalization guarantees for neural networks are less well understood in unsupervised learning. Generative models or learning 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.. Gooofoooellloow
ct al. 2014)), Variational AutoEncoders (VAEs) (e.g., Kingma & Welling (2014)), and Normalizing Flows (e.g., Rezende & Mohamed ). GANs and VAΣs 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. [owman et al. (2016); Salimans al. (2016); Arora et al. (2018: Lucic al. (2018).

---

Under review as a conference paper at ICLR 2021
In contrast to the generative models such as GANs and VAEs, when normalizing flows lear dis- tributions, they can do both sampling and density estimation, leading to wide-ranging applications as mentioned in the surveys by Koobyze et al. (2020) and Papamakarios et al. (2019). Theoreti- cal understanding of learning and generalization in normalizing flows (more generally, generative models and unsupervised learning) is 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 overparameterrzzed normalizing flows. Restriction to the univariate case is technically non-trivial and interesting 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 ID analysis sheds some light on them (see Sec. 4). Before stating our contributions, we briefly introduce normalizing flows; details appear in Section
Normalizing Flows. We work with one-dimensional probability distributions with continuous density. The general idea behind normalizing flows (NFs), restricted to ID can be summarized as follows: Let X E R be a random variable denoting the data distribution. We also fix 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 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 fx (Z) that of X. The learning of fx is done by representing it by neural network and setting up 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 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 ID situation, one-hidden layer networks are of the form (xx) = m is the size of the hidden layer and the 0z, Wt; b, are the parameters of the network.
= >>= a (w,r + b;), where
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 ag W; we use af w, (or other functions, such as the exponential function, of a; W; that take on only positive values) (Huang 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 a,, We to be positive. This is achieved by enforcing this constraint during training. (2) df
Instead of using (xx) for f(x) we use ((N(x)) for f'(x) dx where & : 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 the second class as unconstrained normalizing flows (UNFs).
Our Contributions. In this paper, we study both constrained and unconstrained univariate NFs theoretically as well 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 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 pscudo network convex: For CNFs, instead of using af wf as parameters, we simply impose the constraints a, and w; 2 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
2

---

Under review as a conference paper at ICLR 2021
slightly improves the training of NFs compared to the reparametrization approaches, and may be useful in practical settings.
Similarly, for UNFs 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 (019) 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 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-hhhh et al. (2019) proof, has number of differences, conceptual as well as technical, due to different settings. E.g., our loss function involves function and its integral estimated by quadrature.
On the other hand, for CNFs, our empirical and theoretical findings provide evidence that over- parametrization 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 moderate- sized 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. In summary, our contributions include:
To our knowledge, first efficient training and generalization proof for NFs (in ID).
Identification of architectural variants of UNFs that admit analysis via overparamettizaatoon
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 Tomezak & Welling (0116). masked autoregressive flow in Paaamakarioss 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.) (020). 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- B-NAF) by Cao et al. (2019). Unconstrained Monotonic Neural Network (UMNN) models proposed by Wehenkel & (2019) are particularly relevant 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 bescent-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 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 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 global optimum. The effect of overparameterizztion in unsupervised learning has also been of recent interest. Buhai et al. (2020) do empirical study to show that across variety of latent variable models and training algorithms, overparameterization can significantly increase the number of recovered ground truth latent variables. RRahaakrishnan et 2020 show that overparameterized autoencoders
3

---

Under review as a conference paper at ICLR 2021
and sequence encoders essentially implement associative memory by storing training samples as attractors in a dynamical system.
Outline. A brief outline of paper is as follows. Section contains preliminaries and an overview our results about constrained and unconstrained normalizing flows. Appendix BaaddixxBshag shows the existence of pseudo network whose loss closely approximates the loss of the target function. Appendix shows the coupling or closeness of their gradients over random initialization. Appendices D and conttain complete proofs of our optimization and generalization results, respectively. Section
3 and Appendix Coontaii our empirical studies towards validating our theoretical results.
2
PRELIMINARIES AND OVERVIEW OF RESULTS
We confine our discussion to the 1D case which is the focus of the present paper. The goal of NF is to learn probability distribution given via i.i.d. samples data. We will work with distributions whose densities have finite support, and assumed to be [-1, IJ, without loss of generality. Let X be the random variable corresponding to the data distribution we want learn. We denote the probability density (we often just say density) of X at E IN by Px Px(u) (u). Let 2 be random variable with either standard Gaussian or the exponential distribution with Recall that the density of the standard exponential distribution at u E IR is given by e em for 2 0 and for u < 0.
(which we call standard exponential).
Let f: IR + T. be strictly increasing continuous function. Thus, f is invertible. We use f'(x) df to denote the derivative. Let p5,z (-) be the density of the random variable (Z) Let x = f=), for 2 E R. Then by the standard change of density formula using the monotonicity of f gives
dz
(z,2 (2)
(2.1)
We would like choose f so that Ps.z px. the true data density. It is known that such an f always
exists and is unique; see e.g. Chapter of Santambrogio (013)). We will refer to the distribution of 2 the base distribution. Note that if we can find f. then
generate samples of X using f- (Z)
since generating the samples of Z is easy. Similarly, we can evaluate px (z) (f (=)))())
using 2.1). To find f from the data, we set up the maximum log-likelihood objective:
max-
log (z,) = max I
Σ log logp2(f(x.)) + Σ log log fz;))
(2.2)
where S (.i,.... ,nn strictly increasing functions. When Z is standard exponential, the optimization problem (2.2) becomes
R contains i.i.d. samples of X, and the maximum is over continuous
minL(f, L(f, where L(F,S) 1 Σ L(F,z) and L(f. x) = f(x) - log (z).
(2.3)
ZES
A similar expression, with /(p)angrrnl loss for standard Gaussian as Lf(f.z). x))
replacing f(x), holds for the standard Gaussian. We denote the
Informally, one would expect that -> for the optimum / 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.
m
N(x)
Σ oro ((w, + w.) x + (b, + bro))-
(2.4)
Here m is the size of the hidden layer, p: I + R is monotonically increasing activation function, the weights aro, Wro, byo are the initial weights chosen at random according to some distribution, and wr, b, offsets from the initial weights. We will only train the wr, b, and the a,o will remain frozen to their initial values.
Let e B) 2 denote the parameters W (Wi, W2, ..., Wm) R and B (b,, by.... bm) E RM of the neural network. We use Stochastic Gradient Descent (SGD) to up- date the parameters of neural networks. Denote by 0f = (W1, B³) with W (wf, wob, w and
4

---

Under review as a conference paper at ICLR 2021
B' = (b4, lb.....,ba bmm) the parameters time step t 1,2,... and the corresponding network by N((x). The SGD updates are given by g 8 17 (NV. where > 0 is learning rate, and (NV,, x²) is loss function, and r' E S is chosen uniformly randomly each time step. For supervised learning where we are given labeled data ((11,3)) (1), (in)........ (In, yn)), ). one often works with the mean square loss (N,) = - (r) with T, (N) (Na( y:)
We now very briefly outline the proof technique of Afllen-ZZu et al. (0119) 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 E F is generated by some distribution D and the labels h(x) are generated by some unknown function h R + R. The function h is assumed to have small "complexity" C₁ 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, Allen Zhu et al. (2019) instead work with pseudo network, P(x) which is the linear approximation of Nax) given by the first-order Taylor expansion of the activation:
m
P(z)= = Σ aro (a(W,oz + bro) + a o'(woo + bro) (w,I - b,)).
(2.5)
Similarly to No also define P. with parameters 0', They observe that when the network is highly overparameterized, i.e. the network size m is sufficiently large compared to Cs. and the learning rate is small, i.e. 17 O(1 (1/mm), SGD iterates when applied to I.(N,) and T.(P.) remain close throughout. Moreover, the problem of optimizing L(P) is a convex problem in 0 and thus can be analyzed with existing methods. They also show an approximation theorem stating that with high probability there are neural network parameters 8" close to the initial parameters 6 such that the pseudo network with parameters 6* 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 = OC,p/e" time steps has population loss within of the optimal loss, thus obtaining generalization result.
We will now describe how to obtain neural networks representing monotonically increasing functions using the two different methods mentioned carlier, namely CNFs and UNFs.
2.1 CONSTRAINED NORMALIZING FLOW
Note that if we have a,o 2 0, w/o + w, 2 for all r, then the function represented by the neural network is monotonically increasing. We can ensure this positivity constraint by replacing a,o and woo+wr w,, by their functions that take on only positive values. For example, the function x + x² would give us the neural network N(x)=
2x + byo + b,,). Note that aro. W/o + w, and byo + b, have no constraints, and so this network can be trained using standard gradient- based algorithms. But first need to specify the (monotone) activation p. Let (x) = x I [x 0) denote the ReLU activation. If we choose p = a, then note that in (23) we have
m Σx= 0,p p((w,o
@N(x) Ox
log Σ a (w,n + wr [wro wr byo + b, 2 0j
log (xxx) = log
This is discontinuous function in as well as in wr and b,. Gradient-based optimization algorithms are not applicable to problems with discontinuous objectives, and indeed this is reflected in experi- mental failure of such models in learning the distribution. By the same argument, any activation that has discontinuous derivative is not admissible. Activations which have continuous derivative but are convex (e.g. ELU(x)) given by ex for & < and for x 2 0)) also cannot be used because then N (a:) is also convex function of ær, 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
m
P(x)
Σ do (tanh(wfor + byo) + tanh' (w,, bro) (ww) + 2w,uw,) + br))
5

---

Under review as a conference paper at ICLR 2021
Note that P(z) is not linear in the parameters 8. 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 retain the form of the neural network as in (2.4). but ensure the constraints 0,a and W/0 2 by the choice of the initialization distribution and wyy + W 2 0 by using projected gradient descent for optimization.
Σ aro tanh ((wro + w,) x (b, bro)), with constraints w/0 + wr 2 c, for all 17
(x))
Here, > 0 is small constant ensuring strict monotonicity of [x)). Note that constraints in the formulation are simple and easy to use in practice. The pseudo network this formulation will be
P(x) - Σ aro (tanh(w,az + b,o) + tanh' (W,,0 + bro) (w,x + b,))
with constraints Wro + Wr- 2 c, for all r. P(æ) is linear in 8, therefore the objective function is also convex in 0. Note that P(x) need not be forced to remain monotone using constraints: if (x)) and P(x) are sufficiently close and N(x) is strictly monotone with not too small min, @N(x)) then we will get monotonicity of P(x). Next, we point out that this formulation has problem in approximation of any target function by pseudo network. We decompose P(x) into two parts:
8x
P(x) Pe(x) + P.(x), where m
m
Pa(x) = Σ aro (tanh(w,or + byo)) and P₂(x)= = Σ aro (tanh' + bro) (w,x b,))
Note that Pc(x) only depends upon initialization and does not depend on w, and b, Hence, it can not approximate the target function after the training, therefore Pe(x) needs to approximate target function with Pa(x)) subtracted. Now, will show that Pe(x)) non-linear" functions. The initialization distribution for wro is half-normal distribution with zero- mean and variance=_ m of normal distribution, i.e. Wyo = |X] where X has normal distribution with the same parameters. The bias term b,o follows normal distribution with 0 mean and 1 m with high probability;
not approximate "sufficiently
variance. Using the initialization, we can say that wro and |bro| are O [/log m v/n
Using the fact that tanh (y) = for small y, we get that tanh' (wmn + byo) Rs 1 for sufficient large m. In such cases, P: (r) becomes linear function in x and won't ton't be able approximate sufficiently non-linear function.
therefore, W + byol is O
(y [yog 17
Note that this issue does not arise in pseudo network with ReLU activation because the derivative of ReLU is discontinuous 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 wro and b,o with variance
ing For
normal distribution initialization of wyo and b,o with variance Ω
log m and 0(1), successfully
training of CNFs to small training network P(x). Please see Appendix [ 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 overparameterivztion for constrained normalizing flow with tanh activation in experiments (Section 3)
lose coupling between neural network ((z) and pscudo
2.2 UNCONSTRAINED NORMALIZING FLOW
Unlike the constrained case, where we modeled f(x) using neural network N (z), here we model f'(x) using a neural network. Then we have f(xx = _S, f'(w) du. While this cannot be computed exactly, good approximation can be obtained via numerical integration also known as numerical quadrature of (x)) The striet monotonicity of f is achieved by ensuring that f'(x) is always

---

Under review as a conference paper at ICLR 2021
positive. To this end suitable nonlinearity is applied on top of the neural network: f()x
((N())), where (z) is as in (2.4) with p = σ = ReLU, and 6 is the function ELU + given by <(x) = e" [[ < 0] + (a 1) I 0j. Thus o(x) > 0, for all R. which means that (z) 0
for all æ. Although this was the only property of ELU + mentioned by Wehenkel & Louppe 2019).
it turns out have several other properties which we will exploit in our proof: it is ipssicc monotone increasing; its derivative is bounded from above by 1.
We denote by I (x) the estimate of [(x) = ("( du obtained from f'(x) via quadrature
f(æ) - & (T, (z)). Here Q is the number of quadrature points T₁ (x) ..... TQ (z), and the Q1..... 94 E R are the corresponding coefficients. /Wehenkel& & Louppe 2019) use (lenshaw-Curti quadrature where the coefficients di can be negative.
We will use simple rectangle quadrature, which arises in Riemann integration, and uses only positive coefficients: f(z) A. [- A.) + f" (0(1--++,))--. +f f())]] where A Q It known
(see e.g. Chapter 5 in Atkinson 1989) for related results) that
Mr + 1)2
f(x) f(x) v
where M" max (f"( wE|-1,a)
2Q
Compared to Clenshaw-Curtis quadrature, the rectangle quadrature requires more points for similar accuracy (in our experiments this was about double). However, we because all the coefficients are positive which helps make the problem of minimizing the loss a convex optimization problem.
Instead of using J. to which we do not have access, we use f in the loss function, denoting it L(J", x)) for the standard exponential as the base distribution to write i(f',z) = f(z) log f'(x) and L) Epes L(f",,)) The loss La(f', .r) for the standard Gaussian the base distribution defined similarly.
Let X be random variable with density supported on [-1, 1]. Let the base distribution be the standard exponential, and so Z will be random variable with the standard exponential distribution. And let F R + IR be continuous monotone increasing such that F (Z) has the same distribution as X. Let S = {......, In be a set of i.i.d. samples of X. Following Allen-Zhu et al. (2019), we initialize aro ~ NO, 2. Wro ~ ~ (o, 1 and byo ~ N (0, m). where ca > 0 is a small constant to be set later. The SGD updates are given by g++1 f 17 V VoL(f, x²) where fz(2) (x))
and x' E S is chosen uniformly at random at each step. We can now state our main result.
Theorem 2.1 (informal statement of Theorem E. (loss function is close to optimal) For any e > 0
and for any target function F* with second order derivative, hidden layer size > G((F")
2²
the number of samples 2 Ca(F") and the number of quadrature points Q > Ca(F")) where C1 (2), are complexity measures, with probability at least 0.9, we have
T-1 Σ t=
Euged
B P. - BEND (T((F" = O(e).
The complexity functions in the above statement have natural interpretations in terms of how fast the function oscillates. Now recall that KL. (pr- <IIpp..)) Ex log Pp- (XX)
(x)) which gives
Engd + ET- KL (pF- .2 2l)p).2) O(e). Recall that p/.2 is the probability density of (Z). Using Pinsker's 's inequality, we can also bound the total variation distance between the learned and data distributions Pf.,z and .r-
Define pseudo network g (z:, which acts as proxy for (z),, as g'(x) ((P(x)) Note that our definition of pseudo network is not the most straightforward version: g'(x) not a linear approximation of fz))). As in Allen-Zu et al. 2019), we begin by showing the existence of a pscudo network close to the target function. However, for this we cannot use the approximation lemma in Allen-Zhu al. (2019) as it seems to require dimension at least 2. We use the recent result of et al. (2000) instead (Lemma B. 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.
7

---

Under review as a conference paper at ICLR 2021
m=2000
122rmm di dstrgeenn
(6-0400
Mamber of spachs
Mumber spochs
Number spocns
Misture of Gaussian Distributions (lus-0..00
Micture of Gaussian Distibbtiinss (1:.-0.00
Mixture Gouss on Distrratiittttttttiii L.5.0
camm of chanto F12
mamm chongeingg
vaning W9G
mi-1000
m--6000
Mi 1970
m. 6400
m=1620
10000000
m1-0200
ror chrrgees
nerm chargge
1ktriber spoche
Mambbe of spoche
Number of appcres
Figure I: Effect of over-parameeerizzaton training of constrained normalizing flow mixture of Gaussian dataset for number hidden layers m 1600, 6400
3 EXPERIMENTS
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
3.1 RESULTS FOR CONSTRAINED NORMALIZING FLOW
In Sec. 2.1 suggested that high overparameterizattio may adversely affect training for constrained normalizing flows. We now give experimental evidence for this. In Figs. [ we see that as we increase the learning rate, training becomes more stable for larger constrained normalizing flow with m = 1600 doesn't 't learn anything due to small learning rate. We 1600. On
Note that for learning rate 0.025,
observe that the Le-norms of W and B for m 6400 are least large those both datasets, as we increase the learning rate, L2-norm of B increases and learning of constrained normalizing flow becomes more stable. These observations support our claim in Sec that for learning and approximation of overparameterized constrained normalizing flow, neural networks need large L2 norms 4 and B*
CONCLUSION
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 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 number of open problems: (1) We made two changes to the unconstrained flow architecture of Wehenkel Louppe (019).. An obvious open problem is an analysis of the original architecture with at most change. While the exponential distribution works well as the base distribution, can we also analyze the Gaussian distribution? Similarly, Clenshaw-Cune quadrature instead of simple rectangle quadrature? These problems tractable but also likely
8

---

Under review as a conference paper at ICLR 2021
to require interesting new techniques 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 results suggest, one needs networks that are not regime 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 possible design an architecture with one hidden layer, but as we have seen in our analysis of CNFs, that is challenging too.
highly overparametrized
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in neural information processing systems, pp. 6158-6169, 2019.
Sanjeev Arora, Andrej Risteski, and Yi Zhang. Do GANs learn the distribution? some theory and empirics, In International Conference on Learning Representations, 2018. URL https
//openreview n E
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97
of Proceedings of Machine Learning Research, pp. 322-332. PMLR, 2019. URL http:// proceedings wwr.mmm...... press / vv7 /aaooaaaaaaa..a html
Kendall Atkinson. An Introduction to Numerical Analysis. John Wiley and Sons, 1989.
Samuel R. Bowman, Luke Vilnis, Oriol Vinyals, Andrew Dai, Rafal Jozefowicz, and Samy Bengio. Generating sentences from a continuous space. In Proceedings The 20th SIGNLL. Conference on Computational Natural Language Learning, pp. 10-21, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/v1/K/ 1002. URL https: / /www///wwww...// aclweb
org/antholoogyKKe 1002
Rares- Buhai, Andrej Risteski, Yoni Halpern, and David Sontag. Empirical study of benefits of overparameteriizatoo in single-layer latent variable generative models. In Proceedings of the 37th International Conference Machine Learning, 2020. URL httptt:::///cceeeee
icml
stc/statiic/appr____. Files/ cml cmtpcc2lccccccccccccc 0t1///2222/5555--2 5645-Paper pdd
Nicola De Cao, Wilker Aziz, and Ivan Titov. Block neural autoregressive flow. In Proceedings of the Thirty-Fifthh Conference on Uncertainty in Artificial Intelligence, UA/ 2019, Tel Avi; Israel, July 22- 25, 2019, pp. 511. AUAI Press, 2019, URL httthtt:/// /aw///aaaa../////////a papers 511 f
I. Daubechies, R. Verere, S. Foucart, B. Hanin, and G. Petrova. Nonlinear approximation and (deep) relu networks. ArXiy, htss/1955.021999 2019.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. Proceedings of the 35th International Conference on Learning Representations, 2018. URL /ttps://arxiv.. www.rr/////////o..e//oooo/eeaeee
abs/ / 810 .
Ian J. Goodfellow, Jean Pouget-Abadia Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27: Annual Conference Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 2672-2688 2014. URL http: /ttp:://pppr.... wwwapess.ips... nips.ippp............. cc wttpss/ppppppppppeeeeeeeeeeeeeee (tw.:a233-neeettttie adversarial-nett
Chin-Wei Huang, David Krueger, Alexandre Lacoste, and Aaron C. Courville. Neural autoregressive flows. In Jennifer G. Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. ICML 2018, volume 80 of Proceedings of Machine Learning Research, pp. 2083-2092. PMLR, 2018 URL TRLptt:: htttt::/pproceedin.t mlr. www.ppresssvve.. http:///ww.......e///ssssaeee
huang 8d. html

---

Under review as a conference paper at ICLR 2021
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Con- vergence and generalization in neural networks. In Samy Bengio, Hanna M. Wal- lach, Hugo Larochelle, Kristen Grauman, Nicolò (eds.), Advances in Neural Information Processing Systems 31: Anmual Conference
and Roman Gamett
on Neural Information Processing Systems 2018, NeurlPS 2018, 3-8 December 2018 Montréal, Canada, pp. 8580-8589, 2018. URL httpp://apprss.att nwws. cctpssccp.sccccceee// 8076 neural- -ta.gattttnggtttaaa kernel convergence and senddgggeraazzation
nww.al networks
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kernels, transportation mappings, and universal approximation. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020. URL
1910. 06956
Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference on Learning Representations, ICLR 20/4 Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014. URL http:
//axxiv.orgl abs/ 1112. 6114
I. Kobyzev, S. Prince, and M. Brubaker. Normalizing flows: An introduction and review of current methods. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2020.
Zhifeng Kong and Kamalika Chaudhuri. The expressive power of a class of normalizing flow models. volume 108 of Proceedings of Machine Learning Research, pp. 3599 3609, Online, 26-28 Aug 2020. PMLR, URL
m www.rrpress/eee /v08 hww.1/00///og2aaaaoomm
Qi Lei, Jason D. Lee, Alexandros G. Dimakis, and Constantinos Daskalakis. SGD learns one-layer networks in WGANs. In In Proceedings of the 37th Internationaal COnference on Machine Learning. 2020. htts::t::: httptt:::s//ppccccccigggee 4998-Paper pdf
Yuan-Chuan Li and Cheh-Chih Yeh. Some equivalent forms of bernoulli's inequality: A survey, Applied Mathematics, 4(07): 2013.
Yuanzhi Li and Zehao Dou. Making method of moments great again? how can GANs learn the abs 2003. 04033.
target distribution, 2020. URL
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochas- tic gradient descent on structured data. In Advances in Neural Information Process- URL http:::/paprrs.npppatt wwtp:iitpp..ccpp......cppp ing Systems 31, pp. 8157-8166. 2018
8038 pdf
Mario Lucic, Karol Kurach, Marcin Michalski, Olivier Bousquet, and Sylvain Gelly. Are gans created equal? large-scale study. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 698-707, 2018
Andreas Maurer. A vector-comtraction inequality for rademacher complexities. In International Conference on Algorithmic Learning Theory, pp. 3-17. Springer, 2016.
Thanh V. Nguyen, Raymond K. W. Wong, and Chinmay Hegde. Benefits of jointly training au- toencoders: An improved neural tangent kernel analysis. CoRR, abs/1911. 1. 1983, 2019a. URL attp::/aaxiin org/ abs 1911. 11983
Thanh V. Nguyen, Raymond K. W. Wong, and Chinmay Hegde. On the dynamics of gradient descent for autoencoders. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pp. 2858-288 22687 PMLR, 2019b. URL http:t///////re/dngggs mlr. prress/v99 www.wnnw...............
George Papamakarios, Theo Pavlakou, and Lain Murray. Masked autoregressive flow for density estimation. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS 17, pp. 2335-2344 2017. ISBN 97815 10860964.
10

---

Under review as a conference paper at ICLR 2021
George Papamakarios, Eric T. Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Bal- aji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. ArXiv, abs/1912.02762, 2019. 2019
Adityanarayanan Radhakrishnan, Mikhail Belkin, and Caroline Uhler. Overparameterizee neural networks can implement associative memory, 2020. URL httpss//arrav..o/////a/ 12362
Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. volume 37 of Proceedings of Machine Learning Research, pp. 1530-1538, Lille, France. 07-09 Jul 2015. PMLR. URL http://ppeeeeeerngg...eerree///r
Justin Romberg. Maximum of sequence of gaussian random variables. 2012. URL http:
Justin Sahs, Ryan Pyle, Aneel Damaraju, Josue Ortega Caro, Onur Tavaslioglu, Andy Lu, and Ankit Patel. Shallow univariate relu networks as splines: Initialization, loss surface, hessian, gradient flow dynamics, 2020.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen. Improved techniques for training gans. In Advances in Neural Informa- fion Processing Systems, pp. 2234-2242. 2016. http:httppp:peeeee wwt.ssiips.cccpppeeeeeeee ccpparrr///paa 6125- - www.-iindoeveeeennttteeee www.eechhhiiiueeeoo htwp::atteccccooo---------aaaaaa
Filippo Santambrogio. Optimal Transport for Applied Mathematicians. Calculus of Variations, PDES and Modeling. Birkhäuser, 2015.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Alina Beygelzimer and Daniel Hsu (eds.), Conference on Learning Theorr, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, volume 99 of Proceedings of Machine Learning Research, pp. 2667-2690. PMLR, 2019, URL [ httt:: htttt:://prcceedangg 9a. html
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Takeshi Teshima, I. Ishikawa, Koichi Tojo, Kenta Oono, M. Ikeda, and M. Sugiyama. Coupling- invertible neural networks universal diffeomorphism approximators. ArXiv, abs/2006. 14469, 2020.
Jakub M Tomezak and Max Welling. Improving variational auto-encoders using householder flow. arXiv preprint arXiv: 161 1.09630, 2016.
Rianne van den Berg, Leonard Hasenelever, Jakub Tomezak, and Max Welling. Sylvester normalizing flows for variational inference. In proceedings of the Conference Uncertainty in Artificial Intelligence ( (UAI), 2018
Martin Wainwright. Digee-Dimmsionall Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi:
010017/978110862777
Antoine Wehenkel and Gilles Louppe. Unconstrained monotonic neural networks. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence A'ccé-BBuc, Emily B. Fox, and Ro- man Gamett (eds.), Advances in Neural Information Processing Systems 32: Annual Confer- ence on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 1543-1553, 2019. URL http::htpp::pppeee
Francis Williams, Matthew Trager, Daniele Panozzo, Claudio Silva, Denis Zorin, and Joan Bruna. Gradient dynamics of shallow univariate relu networks. In Advances in Neural Information Processing Systems 32, pp. 8378-8387, 2019. URL wel sha -ww-uni
nips. ccpppper
904 1004--gradient-dyneee
Gilad Yehudai and Ohad Shamir. On the power and limitations random features for understanding neural networks. In Advances in Neural Information Processing Systems, pp. 2019.

---

Under review as a conference paper at ICLR 2021
A
NOTATIONS
We denote (a, as a concatenation of vectors a and B. For any 2 vectors a and B, a @ B denotes element wise multiplication of a and ß vector. We denote the parameters of neural network
E IR 2m is concatenation of W = [W'1 W2,..., Wm E R and B (b1, b2 be.... bm) E I (i.e. 0 (W, B)). Similarly, 0 (W B³) where W = [wf. wy.... ...y wm) and B (bf bb. ",y,.. k. Similarly, Ag = (010, 420,-... aro,- 0mo). We denote = (1,1,..., 1) E IR We use Big-O notation to hide constants. We use log denote natural logarithm. [n] denotes set {1, 2,...,n) n..
B EXISTENCE
This section contains proof that shows existence of a pseudo network whose loss closely approxi- mates the loss of the target function.
Lemma B.1. For every posifive function F" every x in the radius of I (i.e. |ar| S 1), there exist a function ((ro, bro) IR² + -Un,, Un) such that
-0-1 (F* E Nvo....)) [h(wro: [wr + 6 2 0]] S wa ((F-))(0)
where Un is given by
(F*1)) (P)) Un = (10 ((Fr))
16 112,
(B.1)
((Fr) (6))
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. (020 Let th R R and
5 > 0 be given, and define
(0) (z)) +xz') max[[=] |211 < 1 + 8, x x' 80
( (x)) [|x]] 51+8)
1/ = Go
8
1 22 (2M/ Ō())
M == sup
(x)x
|+|51+
1
B 2Ta
T.(wo, bro) ==2 v 8.a (0) + / Viii (v) cos (2x (O (v) [[=ll)) de
+ 2T (2m ( (hrp? sin (2tr (Dmj. (Bwrn) - byo)) [lbool & || S r]
where * denotes convolution operation, Ga denotes Gaussian with mean O and variance a?. Note that Ô hides logarithmic dependency of complexity measure of function vb. |1i... denotes magnitude of fourier transform of vb 8.a and O2 denotes phase of fourier transform. Then,
(x) b....ba [Tr ( + 6yo 2 O]] S (6) 1=|$1
sup
(B.2)
The upper bound T, T.(wro. bro) is given by
[ bro)l =ō 11 (8))4)
sup
[w0 (0))+
= UT
(B.3)
Using Result B.I for Φ (-'(F((x)) function, denoting T, (wrro bro) for &- (=I(F(((z) function as Iu bro), we get
1 (FF((x)) E Eu.,,troo [h(woo, by (o)l [ bro O]] wo 1(F-1) (8)
12

---

Under review as a conference paper at ICLR 2021
with following upper bound on h(wro, bro).
|| (0 (0 (F 112,
sup h(wro, bro) 50 myo.00o
Un
(10 (F-r) (6))
Divide pseudo network P(x) into 2 parts: Po(x), first part of pseudo network is constant and time-independent and (x)),, second part pscudo network is linear in wa and
P(x) Pa(x) + P(())
where
Pa(x) =
Σ
aro (Wig + bro) II w + bro 2 0]
r=1
T
Pt(x) =
Σ
oro (w, + b,) [urox + bro 0]
Lemma B.2. (Approximating target function using Pt(x)) For every positive function F and for 2m
every e (0, 1), with least 1 1- exp (- there exist 6 such that get following inequality for all [-1, and some fixed positive constant C > 1.
128c (-188qU0; log m probability over random initialization,
6 ( S (a-1(F))) (0) +
-
and upper bound Los norm of parameters is given
UnVT
110 10
/2me
Proof. Define w. and by
- 0
6" sign (aro) VT h( Vnnwoo, Vinbaa)
(B.4)
mea /2
Using Wt and 6,,
(.0 [P7 (z)]
=E Buo.-Ko00hhwoooooOOoH)oooooo
aro aro + 6,]1 ( + 6y0 2 20]
arosign (aro) V ii (l/mmooo / [wro2 + byo 2 0]
=E +o
v22
E (O: ( Vmw,,o vmbb,) [vm (wyor byo) 0]]
where equality (i) follows from Fact H.2 and homogeneity of indicator function. Using Lemma B.I
E
(f(x)) - 0-' (I))
(e h(mmwro mlb [ym (wrox byo) 2 20] - (F*(())))
I (g-)(F-)) (0)
(B.5)
Using technique from Yehudai & Shamir 2019)) we define
((a10, 1io, b10) ...., (aro, Wro, bro) (a10, Wmos bmo)) = sup
PP Eg 20 Brn (x))
xE[-1,1]
13

---

Under review as a conference paper at ICLR 2021
We will use McDiarmid's inequality to bound h. h ((a10, w10, b10) ..... (aro, wro, bro) .... (a10, wmos bmo)) h ((alo: w1o, b10),....... ..... (dro: who, bro) ..... (a10, Wmo, Omo
4cq 4c1Uny2log m
m
Using Lemma 26.2 from Shalev- Shwarzz Ben-David (2014), we get
E [b] = - En,o. Ma..o.
sup m
Σ & (wef + 6,) [wrow + 6r0 2 0)
where E ........ Sm are independent Rademacher random variables.
2
Ea bro [1] -
E Ea.o. Wro.boo.
sup
Saro (wft + b,) II [woox + b,u 2 0
2
E wro.bbo
supm
Searo (w + b,) II (w0ox + bya 2
801 Aog mgg,
sup B Wro
E w + bro 2 20
x
One can show that
m
log m m
E
Earo
braisr
sup
& [2rox + bro 2 0]
S 2
778
Using this relation, we get
16c, Un logm
E wao [b]
vm
Using Mediarmid's inequality, with at least
1 exp
128cfU m
we have
16c; Un log m (i)
IP] (z) Eu Dro
[PT(
2 +
S
(B.6)
mm
where inequality (i) follows from our choice of m in lemma D.2
Using eq.
B.5
we get
(1)x)) (F" w ((Fr)) (6) te
(B.7)
Using 1-Lipschitzness of Φ, we get
(())) |0(P) (1)) o (0 (F (x))) Φ- (F)()))
Wa-1(F-))) (6) te
The upper bound on norm of ||0'| is given by the following equation.
UnVT /2mea
110 1lo0 <
Corollary B.1. (Approximating target network using P(x)) For every positive function Fsr and for every 10, with least 0.99 - cs initialization. there exists 0* such that have following inequality for all [-1, and some fixed positive constants C1 > 1, Cg > and C7 1. - F=) (x)
exp
1280 log probability over random
2m
I 16c, (cs + c7) en log m + wy (g-1(F=1) (8) +
and upper bound on Lae norm of parameters 6" is given by
1100 < UnVT
/2mca
14

---

Under review as a conference paper at ICLR 2021
Proof. Using Lipschitz continuity of & function, get o (PT (z)) (x))) - (x) (x))
Σ 4r (w,oz + bro) Il 1000 + 6,0 2 0)
Now, there are at most m break points of indicator 1 [w + 6,0 2 0J where value of Il [w,oz + 6yo 2 changes. We can divide range of into most m + subsets where in each subset, value of indicators I [wroz + b 2 0] is fixed for all r. Suppose there are m' indicators with value 1 in given subset. Without loss generality, we can assume that indicators from r to m' is 1. Then,
m
0ro (Wrgæ + bro) [wvor + 6,o 2 0]
Σ aro (wrow + bro)
m
arobro
Now, applying Hoeffding's inequality for the sum in above equation, we get
m
21
Pr
Σ
w0o
a
2t
S exp
(Tme m/ (201ca (onicv2loog 2og m)
(2c6v 2 log m
2
2
= exp
32c (log m)
Taking = 16c1 (log m), with at least probability 0.999
og we have
C6C (log m)
and similarly, we will get that with least 0.999
probability,
m'
ooo
16c107ea (log m)
will get that at least 0.999
probability, have
wow (wrox + byo 2 0]
< 16c1 (log
(B.8)
Σ arobrall [Wrox + 6no 2 0]
< 16c 076a (log m)
Using these relations, we get that with at least 0.99
1 probability,
aro (Wroz + bro) I [Wroxr bro 2 0]
$ 16c, (cs + 07) c, log m
(B.9)
Using above inequality, we get (P) -(P) (p) (*)x)) 16c1 (ce 07) ca log
15

---

Under review as a conference paper at ICLR 2021
m 1 1 - -exp (- 128c; log m
Using lemma B.2
with at least 0.99
probability,
(P)()))) - - 1 (P
(( + 10 ( (2)) - (a))
I 16c, (ce + c7) log + Wp (FF1) (6) +
Lemma B.3. (Optimal loss) For every positive function F and for every 6 E (0,1), with at least probability over random initialization, there exist 0 such that loss of pseudo network with 0" parameters is close to that of the target function for all a E [-11, 1] and for some fixed positive constants e₁ > 1, cB > and 07 > 1.
0.99
1 exp 128c5U7 log
2m
65 67
(PP) (F", .x) 5 (16cr (co + 07) en log m + ug ((Fo) (6) +
Proof.
Q Σ Es
((((P"),x) - ((M)))))))))
F (T(())
+ llog (log( log (F*
3 (16a1 (cs + ca logm + WF- (6) + +c)
+ P*(x)) o- (F*) (z))
< 2 (16e) (cs + 07) cu log m (F-1(F-)) (0) + t)
+ [P]())) + (f(x)) x- (F* (z))
3 (16c1 (os + c7) ca log m + (F-)(F-)) (6) + c)
where inequality (i) follows from Corollary 2' exp
B.1 with at least 0.99
1
1
1
c6
128 UR mo probability. Inequality (ii) uses Eq.
B.7 and Eq. B.9 B.9
C COUPLING
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 a
o' (x))
sup \ (.
(C.1)
(x))
We get following find upper bound on d1
(x))
A1
sup
(xN(
of
exp (M) 2
sup
re] &E IuIS exp +
[[N(2>) < 0 [[N( 0 N₂(x) +1
sup rel
=
(C.2)
Define A as
A 6c16a / m
(C.3)
for some positive constant C > 1.
16

---

Under review as a conference paper at ICLR 2021
Lemma C.1. (Bound in change in patterns) For every x in I radius (|2] S 1) and for every time step t t 1, with probability at least 1 - exp (- 66(e2211) A2,2
over random initialization, for
at most 02
m V
fraction of [m]
1 [[ + w + bro + 6, 2 0] & [[woz + 6/0 0]
for some positive constant e₁ > 1 and 02 2 1.
Proof. Taking derivative of L(f x)) wrt wy.
o)(s(,²) Ow.
-
A (Ne (Ti (x)) Jarao' ((w,o + + (2)) + 0io + 1b) vi (xr)
(d'(N((z)))aood ((w,o + ) + 0 + bτ: 2²)
(xN)
Aagss (Ne (Ti (I)) (z))) ((wro + wx)T (x) bro + by) Ts (a))
+ o'(N((a))
(aroo' ((wro + wt)x x + 0ro + bb)) x)
((N((z))
Using Eq. C.2
A2 S 3. |o| I and V (N(x))) S 1 for all æ [-1, 1}, we get
ai x) Ow,
< 3 a.oo
Using Lemma H.2 with least 1 probability, we get
oi(s(, x)
< A
(C.4)
Ow,
where À is defined in Eq.
Using same procedure for b,, we get
oils(,
A o (Ne (Ti (z))) aroo' (wwro + wF)T (x) + 6,o + 1%))
Ob,
x=1
1
Φ (N,( (d((N())) (wwro + wtfx bwo 11,))
S 3 Ja,ol
(C.5)
Using Eq.(C.4.
and Eq. C.5 we get
loff n
(C.6)
by $ n
Define
H₂ = {r E [m]] [yyo
+ brol 2 An
(C.7)
For every with [x]] < 1 and for all E [m]] Iwf. + b.l < 27jAt. For all E Hr, we
get [[wo + wf)x + b,o + b, 2 0] = [wyoar - byo 2 0). Now, we need to bound the size of
H.. We know that for all
[-1.1]. wyoz + bro is Gaussian with E [w + byo] 0 and
Var [wrox + byo] 2 1. Using Lemma H.3 we get
4 4
Pr (wwrox bral I Andt) <
17

---

Under review as a conference paper at ICLR 2021
Using Fact H.l for Hi (where Hi [mi] /Hi) for some positive constant Co 2 1, we get
4v 4/21//mr
4v 4
[H 2 cym
S exp
-2m
(02 - 1)
VT
64((22 1)² 2212
- exp
π
21/1// / mi
64(1 - 22) 2212
[Hi S c2m
2 1 exp
V
4v2n//mSt
64(1 - c2) m 224
Hel 2 m
1 C2
2 21-cxp exp
where [H& denotes the cardinality of set He and similarly for [766)-
Lemma C.2. (Bound difference of f and g') For every in radius (22l S 1) and for every time step t 2 1, with at least 1 probability, function with neural network and function with pseudo network are close for some positive constants 01 > 1.
- ((V((=)))<(((C)))) S 2tcianAA HC lo m
Proof. We know that 1-Lipschitz continuous. Using Lipschitz continuity of é, we get
- P.(x:)
We bound (x) - Px(x)) following.
(N,(x) P.(x)] <
Σ
aro ((w,o + wt)x + b,o + 85) II [[w,o + =,)x + bro + by 2 0]
nE [m]]
Σ ono ((w,o + wi.rr r + b.o + b,) [wrox + bro 2 0]
r[(m]
Σ aro ((w+o + wa + 600 + bt)) (u [(wro + wt)x 6ro 6, 2 0]
1| + bro 2 01)
MgH.
HC' (2016a /2 m)
(4nj31 + 2n) (2)
<2AciennAt HL / logm
(C.8)
where inequality (i) uses Lemma H.2 with at least 1 - probability.
Corollary C.1. (Final bound on difference of f' and g') For every x radius (|x) S 1) and for every time step 2 1, with least 1 cxp (- 1_G4es-1)9n 322 probability over random initialization, function with neural network and function with pseudo network are close for some positive constants e₁ > 1 and C2 Z
192n 1.5 1. 2 C2 Aogm
-(P()))))(((())))
(C.9)
18

---

Under review as a conference paper at ICLR 2021
Proof. Using Lemma
C.I and Lemma C.2 get
[o(N((z) ((P(2))) 224c1 At H
1og m
4V20VmA
24cc c. 22m
log m
VT
192mm 1.5 Ac1eeatt
(nÂt)
V 192n/² m 1. 2101022tt Vlogm
(C.10)
VT
$ O m
1.5 Eal Vlogm)
where inequality (i) uses Lemma C.1 and the inequality follows with least 1
64(e2 1) 119m2322 32,2
exp
probability. Define A as
A hp = 192n/2m2 A e ozea 12 Vlg m
(C.11)
V
Lemma C.3. (Coupling of loss functions) For all x in 1 radius ((x) S 1) and for every time step over random initialization, loss function of neural network and pseudo network are close for some positive constant > 1 and
t L, with probability at least 1 exp (espp-Slcc -AAle--1) (((sg-1)'/) vj" t
22 21 1.
(f(.2)) - L (sb, S $3
Proof.
-
<
Σ
Axf((T( Σ
A.d (T (x)) + flog (f/(x)) - log (o((x))
i=1
1=1
52
sup 1S (T. - de (n (c)))) kE(
+NN((x) Px())
3A mp
where inequality (i) follows from I-Lipschitz continuity of log (z(N()))) with respect to (x).. Inequality (ii) uses (C8) and Lemma C.2
Lemma C.4. (Coupling of gradient of functions) For all in radius (|x) < 1) and for every time step t 2 1, with at least 1 1 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 1.
Vof((=) - Ves((=)]| < 4c1e, (mAip + +2(H()) 22
Proof.
Vof((a) Vosh
< (
s ((Pp))))))(( +1)()))))
+ $ <1N(()) - PI(x)) V | -VoN()))VVPP(.))) voP.(a)
19

---

Under review as a conference paper at ICLR 2021
where last inequality follows from 1- 1-Lipschitzness of o' function and d' $ 1 for all x such that |x|| S 1, (T]. To upper bound VoN((z) VoP((z))
VoN((1)) voP.(=) s (AA0 @ (1v, 1) o (I [(W Wt + Bo + B 2 0] - II Wor BB 2 0]
T[ - HoWo-W")ar + Bo + B 2 0] Wor + BB 2 /)}1
801Fa / log m |Hil
Sciea |74|| v 2 logm m
(C.12)
The inequality (i) uses property of Hi that for all r E H4, I [(w,o + +f)x
0,o + bú, 0]
I [wrox + 6,o 2 0j. Using (C.1l and Eq. C.12 we get
-Vod(())) - [lN(()) Pi(z)) (Au. Au) @ (1z, 1) o (I (W6 + W')x + Bo + B' B²20) 2/
1 [(Wo + w')x Bo B²
+ VoNi(z) - -
I 4c1camA up 2 m + Sc [H4]] /2lgm m
= 4crea (mdmp +2 2H(5) /2lgg m
Lemma C.5. (Coupling of gradient loss) For all x in 1 radius (xx) S 1) and for every time step
t 2 1, with probability at least 1 - 2 -exp (- (-alles- GA(ee-1))' M²t
over random initialization, gradient of loss function with neural network and loss function with pseudo network are close for some positive constant 0₁ > 1 and C2 1.
192mm 1.5 AcIc2eat
VoL(f(. voL(o(, S
+ 16c C, m. mp V log m
Proof.
Voli(r) A (of((T(
VoL(f(.2) VoL((l. S
f((x)
Vogi(z)
A2 (eo((((
(((z)
1=1
Q
A Vo (T)
A (T
Vogi(z)
Vof((=)
(((x)
f((x)
Proving bound on I,
Q
==
Σ
A (f)((((())) - Σ A Vegi(T
Vofi(T (x)) - Vegi(T, (z))
<
1=1
5 Sc1ca (m + 2((gg) 2lggm m
20

---

Under review as a conference paper at ICLR 2021
where inequality (i) follows from Lemma C.4 Now, will bound II,
Vogi(a)
Vol((z)
g((x) f((x))
exp (00)(())))(((()))))110))) 20 VoP.(x)
exp (0077)))))
exp (M(N))))IIMMMM))>)))+00000000000
20 VoN((2)
exp (MM
[[R(()) < < (z) 20 VoP((x) - (TINACO) < + [[N( 2 20) (P((2) 1)
VoNi(e))
(N, +1)
VoP.(o) VoN
(PP(3)<0,N(())) <o
In
(x) VoP((=) (.(x)
[[P((z) < <,))))) 20
VoP((x) (oN( P1(x+1
(1P(2)200, <0)
VoP((x) V.N.(r)
T(P((t) 2 0, N(()) 20
p+ N((x) +
On simplifying I1,, we get
N((x) +1 VoP((z) - + +1 Na(x)
1
| ) < (,)) 2 0]
11,- -
1
(VPP((s)-VoN))) + (oOPoo) 111(() (,,))) (C.13)
Similarly, simplifying I13, get
1 Pr(x)) +1 VaP((x) VoNi(a))
Px(x)
(omccco)) ([P:()) 2,, <0]
lla <
+
1+ Pi(a))
(oP((x)- - VoNo(1E)
| (1)())
A /ON/CC)
(C.14)
On simplifying 1I, we get
(pP((z) VoN((r)
+ VoN.(x) VoN((x)
(IRRG))2 20) 0]
I1, 5
P((z) +1 P((x) +1
+1
N((x) +1
VoPP(Go) - VoNi(1))
+ (P.(T) 1) (N,(
([P(())20,,)))) 2 0
P((x) +1
[oP((x)- VoNo(a))), -VoN(a)))ooN(()))) +
VoN.
AiD)) 11P((T) > 0,N((x))0
(C.15)
21

---

Under review as a conference paper at ICLR 2021
Using C.13)
131, Eq. C.14 and Eq.(C.13) get
Vogi(z) Voli(o)
92(x) f((
VoP((x) - voN((()) + / (P((() 20]
Amp VoP((=) [
Using Eq. C.12 we get
21ogm m + A (/VoN\(e))) \ooP(()))))
S 8c [651
2 log m + Amp [| o (1z, 1) 0 (1 [o + Bo 2 0].1[W62 + Bo 2 01) ||
S 8c [i
+ +1 (Ao. Ao) 2 (1x 1) O (T [(W W*) By + B 2 0) I [[w + w + Bo + B 2 01) 11,
S Ec Ea [7ii] 2 log m + A 8c1cam logm
Sc ([H6) mA hp)
2 loggm m
(C.16)
Combining bounds on and II, we get
[[ooL(((.>) - vol(gb/ x)]1, S Sc16a (m 2 2 22g
8a ( (Hil mm 2llgm
8c1c (2 +3 Hill) 22 2lgo
61(c2-1) m
Using Lemma C.I with least 1 61 exxp
exp
probability, we get
192mm 1.5 Aogg
VoL((. VoL(si, +)] S
16e1 / m
V
Define I as the upper bound on |[voL(f(, - -
192mm 1.5 AArccc.tvloomm + 16 16crea
/2ggg
(C.17)
VT
D OPTIMIZATION PROOF
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 convex its parameters, we get global optimization.
Lemma D.I. (Convexity 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(gh,
Σ
Angi(Ts (x)) - log (ol (x))
i=1
Dividing the loss function in 2 parts,
L(gh, (g(. + L2(g(,
22

---

Under review as a conference paper at ICLR 2021
where
Q Aogi(T (x))
L1(g),)) x)) Σ i=1
12(5hx)= log (d6(xx)
We will prove convexity of both Libe/, x) and L2 .)). To prove convexity of L, (g/ x) as function of parameters 0, we will prove that Hessian of L, (ge x) is positive semidefinite.
Voli
A Vosh(T(()))
2m1
Q
A Vi (z))
Q
A (
Q Σ (P (
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 L1 (g's x) is positive semidefinite. For second term,
La(g.. x)) log (exp (x)()) (x) s (P.(x) ()) > 0]) = - P (x) < 0] log (P((x) ()) 0]
Note that 22(56,x) is convex in (a( and Pa(x) linear in 0. Composition of convex and linear function convex therefore, (g) is convex in 0, As sum of 2 convex functions convex, L(g', Z) is convex.
Remark D.1. If we use base distribution as standard Gaussian distribution, then loss function will have following term.
in x)) =
Σ A (T (x))
we find Hessian of i,, then we gel
VoLn (g), Σ A
Σ
V2Li (9/, =
Σ (e
A. A.Voo (o))
L
A. Voovo (01)
4
T
If base distribution is standard Gaussian distribution, then 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 't remain convex in parameters of neural network 0 if we use standard Gaussian distribution as base distribution. At points with negative values of g. Hessian of LA x) with respect to O can be negative semidefinie and To (g6,,2) 2) can be non-convex in O.
23

---

Under review as a conference paper at ICLR 2021
Lemma D.2. (Approximated loss is close optimal loss) For every (0, 1), there exist > poly (Uh: .)
( and T O U log such that, with at least 0.95
m
e²
exp
1286 log m
2mm
probability, get
T
Egd L(F,, =(())
T
Proof. For set of examples X, define
1 2(f
i(f(.x)
[
From Lemma D.1 know that L(g X)) convex in parameters 8. Using convexity of L X)
wrt 0,
- < X), -0"
(oL X) VoL(fi, 20 110 11
+ VV (Vo -)
(D.1)
where I1-IIı and ol denotes 1 and to norm respectively. The stochastic gradient descent updates the parameters using xf at time t. 9" is defined as following.
g (x) (z)
Σ a (w + bro) +
a (w + byo) (w + b,)
For stochastic gradient descent, we get
|10 0311 110 VoL(((, -0
||0e 11 + 172 Vo 27 0", Vol(ff,
Taking expectation wrt Te.
Eg [1 8" [|
100 8-112 112 + Ex |Vo[(((, 2 0*) (D.2)
Using Eq. (.2) and Eq. Eq.D..I).
L('', x) - i(g" x)) < Vo Voi vo 10
+ 100- 0 0-113 - EFt [||o+1] 00
27
+ R.
Using [q.4 and Eq.CC.. we get
vol(((x'') 1 S 2m
12
Averaging from t to T - 1, we get
T-1
|180 -A"133
E Eagd [g]. .x) s r
||0 /le + 110"1100 (E(?"
sup
+
1ym
2TyI
@
|10112
r
sup (E[7]
|00 b1o 1100 100
mmm
(D.3)
2n/T
Note that and I' are defined in Eq.
C.3) and Eq.CC.1. Inequality (i) follows from the fact
that 0 (0, O, 0,...,0) 0) R2m. Using Lemma B.3 and Lemma C.3 with least 0.99
24

---

Under review as a conference paper at ICLR 2021
E/=1 exp (- [B4(02g-11 -1
1
exp
128c U. log
2
probability, we get
10
Bagd (L -(0 ST
sup [E[T]
|10||l + -100"1000
+
+
mm
2n/
(1
|10-
Baga BagalL(f L(g",,")
r
sup (E[2)
||0: loc + 11001100
+ 1ym² + +3
2x/l'
(1)
110-11
Bega ( x)) - ,(F
S
sup 1E|T]
|10.1lo + 1100
+
+ 1pmm²
2ny
+ 3A hp + (16c1 (cs + 07) ca logm m + wD-1(F-1)) (6) + +c)
Note that inequality (i) and inequality (ii) uses Lemma B.3 and Lemma following values/relations of 7,
C.3
respectively. We choose
17 mA²
m mnee cn v log m)
m2 log m 10-
(D.4)
T
2T
UR 72c me log
2me2
2ea
18Tcf log U2
We can choose 8 such that WG-1(F.1) (8) = c. Using above inequalities, we get following equalities.
|
||0'13
27
2n/T
2n
| 1|
e
mA² m =
3 (16c) (Ca + 07) log m + ws ((=r) (8) + +e) 3 (16c, (Ca (7) ca log m + 2c)
Using Corollary B. we get
100 < UnVT
/2me,
U
| 5 /mlll* 100 5 V2
25

---

Under review as a conference paper at ICLR 2021
To get value of m,
10-1222
UR 2m
(6c) v log ml
110|1 sup nāt nÂT <E[T] 17,7]
sup
S
2e
2c
3nU C1 Vlogm
V2me,e
10'1 + 10 v U (1 321) Vlogm m
sup (E[T]
V2mE,E
192mm 1.5 Acacgcaty
1661 m,, 2 logm
V
192mm 1.5 "Acooiattylogm
192n m 15A2c102ea Vlog m
1601c, v log m
V
V
192mm 1.5 Acio2eatvlogm
3072/20fc2e 2 P
log m²²
VT 192m C1026a
V
logm
U Amege
(601Ea 2 21gg
3072 2 02
02 2 m logm
UR 4meze
(6116
2 2log
288 2 2T / m log UC
13824v C
f22ym (log m)² Uh
14112 c102 m (log (logm)² U
Multiplication of I and (supremm |10 + 1100 will
14112/ 2n 2ee (logm (lom)²2U; (xUR (1 + 3c1) Vlog m
r sup |10' + 110 110 1l (ET]]
2
/2meat
of2 14112 25c (1 3c,) (logm) 255 Uh
v e3
Taking as
c (1 + 3c1) U12
m 2 Ω
(D.5)
Choosing m which satisfies above inequality will give us the following inequality.
sup
||0' - 110" S
(E(T]
Using C.II
C.III
we get
192n' m 1.b 2 ci C2e, 12 Vlog m
A ap
Vogm 192m 5 C1122.
U 4mege
(BeIea
log
V
864m 1.5 15fez (log m)
155 Ud
(D.6)
Vme2ca
26

---

Under review as a conference paper at ICLR 2021
Using sufficiently high we get
664m11.cce (logm) US cm
Uh
Amp 1
Go2 (log m) m) 1.5 EEE
e2act (1 + 301))) UR
c² (log m) m)2.5 C1 (1 + 3c1) Uh
s (c)
Using Eq.
D.4 and D.5 with least 0.99
Σ1- exp
64(e 61(e)-1)9n 3262
exp
128c U7 log probability, we get
T-1 1 Eagd [i(((, - 1(F") ,2 x) S r
10
sup LE[T
0001 + 11001l000 + 2n/T
+ mm
1=0
2592 62902 (log m) 1.5 U
+ 3 (16c; (cs + c7) ca logm m + 2c)
VmE²ca
2592 1.5 1occc2 (log (ogm)=1 155 Un
< 3c +
+ 3 (166) (es + 07) ca log m + 2c)
Vmme
Taking C1 100, C2
c, 1000, C6
100, C7
100, ca 6000 log m
S c, with at least
0.95
T exp
m,
exp
2m 12887U log m
probability,
2592m 1.5 def02 (log m) 1.5 U
Σ
Engal (L,,
Esgel
I(F=IX)) s 3 (02
+ (c)
T
em
2
$ 3E + 0
(c)
U2
For any e E [0, 1]. with probability least 0.96 0 exp (- 66n''m=2p probability,
7
exp
128c Ug log m
Engd - (x) (ce)
To find lower bound on probability,
ΣT
00 1 22 #
T
64 2222
T
Σ
π
exp
64
π
1=1
(mA
A2
A
32c²
3200
0.01
27

---

Under review as a conference paper at ICLR 2021
where inequality (i) follows from exp (-x) I for all 0. Finally, with least 0.95
exp
e'm 128cfU U. log T
probability,
Eugd [T) - i( x)) - 0())
T
E GENERALIZATION
In this section, we prove generalization guarantees to complement our optimization result, and complete the proof of our main theorem (Theorem E.11) about efficiently learning distributions using univariate normalizing flows. The proof in this section can be divided broadly two parts. First, we prove that empirical average of x)) and L (F*1,z) .)) on training examples are close to expectation of L (fi, x) and L (F*1, with respect to underlying data distribution, respectively. The similar argument is also used in Allen- et al. (2019). Second, we prove that L (fi, x) and (F*, x) are close to (ft, x) and I. (F", v), respectively.
Recall that the approximate loss function Ż is given by
(((,))== Σ A (N (No (x))) log(d (N₂ (z)))
i=1
where
m
N.(1) = Σ
0,00 ((wro + wtya + bro + by.)
Lemma E.1. (Empirical Rademacher complexity for two-layer neural network) For every B for
every n 2 1, with at least 1 - 1 probability over random initialization, the empirical Rademacher
complexity is bounded by
n (.N(as))
8cy Ca 22mm2llogg m
Bee(+11" n
sup
Vn
max /en. 15.1 S
Proof. Using part a of Lemma H.5 B} has Rademacher complexity
we get that for +
W. + by
l,,| S B, 16, S
v Using part b of Lemma H.5 we get that {x +
((wra + w,) x + (bro + by)) complexity 2B
+) has Rademacher vn Using part of Lemma H.5 we get that class of functions
|wm|
B, 1,,
B, Wyo bya N N
= fo +
N(x) maxre(m) |uy| I B, max,e(m) |b,| B has Rademacher complexity
2B ( SciEa Bmn log m
R ( < |||a|||
Vn
nn.
where inequality (i) follows from Lemma tion.
H.2 with at least 1 1
probability over random initializa-
Define upper bound on maximum and lower bound on minimum value of loss function Î is given by
sup ( .x) sup
A pT (x)) (x) 2M log (mF.:)= == -M (E.1)
Q
inf (F , xx) = inf
A FT (x)) log(F 2 2m log (Mp = mi (E.2)
28

---

Under review as a conference paper at ICLR 2021
Lemma E.2. Suppose is sufficiently high such that it satisfies following condition.
2 O (M₁ (M.-m)) m;) (Q (Q+ 1) U (log m))
2
If n. satisfies above condition, then with at least 0.98 probability over random initialization, population
loss of any functions of set fx (x) empirical loss i.e.
|urr
nAT, |br| S nÂT Vr [m]] is close to
sup NEF
EGED
L (f(,x))
Σ
i (fr: x)
Se
Proof. Note that
x) depends
neural
network Using Fact H.8 with at least -
Nx(x)
through
(N, (Ti (I)), No (72 (z)),.. No (rq (x)) Nx))) probability, we get
vector.
sup NET
E. EYED [[]]
(. x)
+bV
log
(E.3)
n
2n
where F = +
N
w S AT, [6,| S nÂ Vr E [m]]. We get coordinate wise
Lipschitz continuity of loss function as following.
b S sup NEFIEIE1
And (N (Tp (x)))
< sup
10' (N (T (z)))
Q
NeF.
2 Vi E [Q]
(x)( sup
exp 1NN
LQ+1 < sup
NEF ((N(x))
NeF exp
1
sup [[N(x) 5 N(x) [N(()) 2 oj
31
Using Lemma H.4 standard Lipschitz constant of i. is
Q+1
Lg S
Σ 1 + +1
(E.4)
Q
To get upper bound on L, we use Lipschitz property of L.
[(bx)) - (Fo.x) <
A (N(T (x)) (N(x))
(E.5)
1=1
29

---

Under review as a conference paper at ICLR 2021
Note that L (ft, 2) depends upon (NV (n (a)) NN (re (..). larly, L (fis depends upon (0, 0,,0,0,.... ..... 0,0) 0) Finding upper bound ((x) for all z E [-1,1].
vector and simi-
sup NEF,2E1-1,11
((x) S
sup I.
(x(x) + A up
aro0 (Wrow + b,o) + Σ
a,a (w,z + b,) (wrox + bro) + A
sup ww..5y/dT....5mmA..ee---
r=1
16c1 (cs + C7) co log m + m
2016a v 222loggm
(2n
+ A np
x 16cl (cs + 07) cn log m m 201 ca 22lg m
(21)AT)
A np
UÍ Ameze + T
166, (cg + 67) ca log + m 48c log m
up
0 U log
where inequality (i) uses Eq. [.9), Lemma H.2 and Eq. C.6 The inequality (ii) uses our choices
of n and T from (D.4) and lower bound on from Eq. (.5).. Define K as upper bound on SuPNEF (z).
U log m
(E.6)
Using upper bound supNeF (ee_F,,__1-111 (x) and Eq. B.5 we get upper bound on (()).
b = K + K L (0,0
0,0) s 2K +
Using value of b Eq. E.3 and Lemma E.1 with at least
8 t
+
probability, we get
sup NEF
E ExED
[ (f(.z)
1=1
<v2((++1) 84 Tmmy 2 log m (2K +2)
log 1
V
vn
2n
We use 5 = 0.01 and choose n which satisfies following condition.
n 1 0 (ML (ML-- -m)=² (Q 1)2 U m)²
(E.7)
22
Using above n, with at least 0.98 probability, we get
i. (f(.)))) 1 M
1
sup
FXED
Se
NEF
n
such that it satisfies following condition. Lemma E.3. (Concentration approximated loss of target function) Suppose is sufficiently high
n 3 (MLL- m)) (1² UØ (log m)
22
n satisfies above condition, then with least 0.9999 probability, population loss of target function F is close to empirical loss i.e.
ERND [F(F"')) - L. (F (F',, Se
30

---

Under review as a conference paper at ICLR 2021
Proof. Finding minimum value (mi) and maximum value (M₂) of loss function L,
sup (F x xz) ssu
A (T. (I)) log(F"((x)) - 2M log (mp-)) = M
x
x
i=1
inf L (F x) inl
A Pd (T: (x)) (og(F"(((z)) 2m log (M m
where Mp. max F* (x) and mp- 11,xx FM (x). Using Hoeffding's inequal- ity,
i (F= L (F x (F= 2c) I cxx (-
2nc
Pr BEND
(M, mi))
Taking n as
(M₁ - (My-m (Q+) 1)a URt (log m)²
n 120 0
2
With least probability 1 exp
exp
2nd²
(Mz-me)'
EAND
[L [ (1it)
(1(1),))) .x]] - L (101, ,2 Se
(E.8)
Corollary E.1. Under same setting as Lemma D.2 and
(M m²) (Q (Q+1) UR m)²
n n20
22
then with at least 0.92 - 2exp
-cxp
128 H. Tog m
exp
(M,- (M,-
2nd
probability,
get
T-1
ENnD [[FE:
ELND [E(F .0] 0((c
E Ezgd
T
Proof. Using Lemma
D.2
Lemma
E.2
and Lemma E.3 with at least 0.92 2 exp
(- m 8c2
exp
1286 log
Am
exp
(Mz 2nc² mz))²
probability, we get
1
EEnD [
ELND [110 .00] s (())
E Eegd
T
Theorem E.1. (loss function is close to optimal) For every (0, 1), there exist m poly (Un, 2) = Ō (- and T' = log for any target function F with finite second
order derivative and number of quadrature points Q 4Mpan44K2 and number of training points
0
m)² ). with at least 1.92-2oxp (- 862
-exp (-
2m
128c log
exp
2nc (Me-me))²
probability, we have
E Eggd
BLnD [[ff,
ELND IL(F",,)) O(c)
T t=0l
31

---

Under review as a conference paper at ICLR 2021
where Uy is the complexity of target function defined in B.1 and
Mp."
sup F (x)
aE[-1,1]
MF
sup F (x)
ac[-1,1]
inf Fd (x)
mp.
=E|-1,1]
M2 = 2M p- - log (mp-r)
m 2m log (Mp..)
U/ (logm) 1.5
K2 0
Proof. First, will try bound
[(FF)x)) - L(F",
Σ F. (
2M p..
Q
Similarly, bounding error for f/. we will get
Q
[(f(,)) L(ft, <
Σ
A. (T)
- f(x))
(sup, (x)
32

---

Under review as a conference paper at ICLR 2021
To get sup, (z), will use (q.
sup (a) S sup [x)
Groo' ((wro + wx)x + bro + by) (wro + w;)
sup
sup
aro (wro + wx) [w + wt)r + byo + by 2 0]
b,o + b 2 20 aro (w,o wx) I1 [wrow + 6ro 2 0J Σ aro (wro + +wf) I [(w,o + wx)r
sup
rEH
sup
aroWnol [Wroxr + bro 2 0. + Σ
arow [urox 6,o
0]
rEH
drow,oll [(w,o + w + 0ro + b4, 2 0] +
arow [(uoro + wr) + Uro + bg 2 0j
TEN
r
166 (log m) + (20rea 22 (nAT)
4/2mmm mm
22cy 226v22og m
(20
VT
vm
4v 2
(2015a 2 (nÂT)
VT
A UR Ameze
I O (E) + (201Ea V 220g
4v 4/2mmmA
(201EV 2lgmm
2co 2cav2loge 2oog m Vm
U 4meee
4/2mvmA
URzT AmeZe
(201ea SineaV2logg /20gm
A
V
U 17 +
UR (logm)).
< 00
+0
+ +c)
0 U2 (log m)
Define K₂ upper bound on sup, J:" (x),
Uh (logm) m)) 1.5
K₂ 0 0
Taking Q as
Q 2 2M + +K2
(F.9)
Using given value of Q, we get that
-(F"))))L(FF) L(F", .x) Sc
(E.10)
[i(b)x)) L(Se,2)) xt)
Se
(E.11)
Using these relations, we get
Eggd
E
E [[ft,
EIND IL(F",,)) O(c)
T
t=0
33

---

Under review as a conference paper at ICLR 2021
By definition of KL divergence, get
T-1
Eg agd
KL (pF 2l1))))
s ((e))
T t=0
F PROBLEM IN TRAINING OF CONSTRAINED NORMALIZING FLOW
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
_ aro tanh ((w-u wy) x + (b, + byo)). with constraints wro w, 2 for all r. (x)
Here, > O is small constant and T is normalization constant which only depends on m. The pseudo network for this neural network will be
P(x) = Σ aro (tanh(w-oz + byo) + tanh' (wo'' + byo) (w,x + b,)) r=1
with constraints Wha + wr 2 e, for all r. We decompose P(x) into two parts: -(x)= = where
Pc(x))+
Po(x) = Σ aro (tanh(w,ol + bro)) and Pe(x) Σ aro (tanh' + bro) (w,x + b,))
Note that Pa(x)) only depends upon initialization and does not depend on w,, and b, Hence, it can not approximate the target function after the training, therefore Pa(x) needs to approximate target function with Px(x) subtracted. Note that normalization constant is necessary to keep Pr(x)) as same order of F*xx) with Pa(xr) subtracted. Note that Now, we will show that (a() can not approximate "sufficiently non-linee non-linear" functions. Using half-norma distribution initialization of wPo with (mean, variance) of normal distribution as (o, m and normal distribution initialization of byo with (mean,
variance) as (0, 1),, and |b,o| are O [Vlo m Vm
with high probability; therefore, |w,00 + byol
is O [Vlg v'm
Using the fact that tanh' (v) ~ 1 for small we get that tanh' (w,oæ + byo) = 1
for sufficient large m. In such cases, Pa (x) becomes linear function in 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 initialization of wro and byo 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 wHo and byo as J. then Pz(x)) cannot approximate "sufficiently non-linear" target function. The same problem will remain if variance of initialization of w,o and byo is log 778
For variance of initialization of w,o and b,o is
Ω log and (l)), we will prove by contradiction that there doesn't 't exist any pseudo network with sufficiently small norm ||0||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 F2. There doesn't 't exist any pseudo network with sufficiently small norm on |10 for which the pseudo network can approximate the target function and for bigger norm on ( l| pseudo network P(x) during the training does not stay close to Nz)).
Informal Proof: Suppose there exist Pa (x) function which approximates the target function F* (z)). As described earlier, P. (xx) only depends upon initialization and does not depend w, and b,. Hence,
34

---

Under review as a conference paper at ICLR 2021
it not approximate the target function after the training, therefore (x) needs to approximate target function with (a (z) subtracted. Hence, P. (2), (z), (2) and (x)x) should be @(1). From the condition that Pa (ar) needs to O(1, we get that T will be o (-)_)) for the considered range of variance of wyo and byo where ab is variance of wro and byo- We denote variance of a,o a From the condition that P7 (x) needs to be (1), we need
a (tanh'(w,oz (wror + byo) (w,r b;)) (1)
( (Tmo v /log
ama v log 10 = (1)
100 =0
Using norm equivalance, we need
110 2| 0
T /log m
Doing similar calculation as in Lemma D.2 for the loss of normalizing flow La, we will get Eq. D.3 D.3 and from Eq. (D33), to get small training error, we need
10" O (E)
7/''
10 11
O T/T
TʃT o
(F.I)
emr2a? log
Now, to find coupling of function (xx) and P(x) as well as derivative function (2 and P'(x), find upper bound the derivative of loss function and w. and by.
OLa Owr
(e(x) ((wro + x + byo + bt))
('()) (arolo'((uun) + wx)x b + bt) + (w,o + wf)xo" + wt)x bro b()))
We assume that (o( x.) is Ln-lipschitz continuous wrt and Lz-lipschitz continuous wrt N'. Assuming [a'()) 1 and |æ|| $
aLa(fr,)) x) < TLiano + +Izano (1 |w + wrollo"((u,) + + + bro + b()))
Ow,
Assuming (o"())
(L
S siipa + riza,o (1 + C(waf1 wroo)
Ow,
Using Lemma H.2 for a,a and Wro, with least 1 6i ca probability,
OLo(fi.a) x)
< (eioaT/2lognn (in + Lg (I + C (lwř) 2020 / logm) ))
(F2)
Owr For projected gradient descent,
aLo(fi,"))
|
5n
Owr
(2010.T/2logg) (In + Ln 2c 20g + (2010a7 m
T2C/wot)
1=0
(In in 20, 20200 2lggm) t (2ncraar /2 < <2nc11aa / (2lggm)
Σ
|oof|
35

---

Under review as a conference paper at ICLR 2021
Define and |
a (2 m)
(I + Ly + 20,0L22wu / 2lggm)
Using and B,
| S at + 3
Σ 1=0
|
2
where
|ufl S a(l 11 1)+ + (1 (1+B) B)
Σ
i=0
1-3
<a - 1) + (1+ B) 2)) +1+ +1+ 33
Σ |wui
S a aa - + (1+ 2) +)+ 3)) +1 33
|
In general, we can write
1'
Σ w sa a
Σ (1 (1+ (t- + (1+ (1+
Σ
|
Taking t' 0,
1-1 10++0-1001) Σ W Sa
E1 + (t - 1) is sum of an arithmetic-geometrc progression (AGP). Using Fact H.6
4-1
| K a
Σ (1 3)- 1)
(1-1) - (1+ 33
(1+ 3) (1 (1 + 3)(-2)
-B 3(1 + 3)--1 - 3(t 1) (1+ 8) + (1+ 3)
88
82
(1+ 3) (1 + 3t)
(FF3)
B2
Using Eq. R3 to bound |w
(1 + 3)) - (1 + -B))
| S
t+
B2
(1+ 83 -1
8
i. + i.z 202 Cingo 2 logm)
(11+200000 2nteo (2logmisc))) -1) A
i.C
Similarly, we
0Lo(fu,z No(1)7 (a.00' (wwr + wa)x bro + bb))
(aro(wro + w,)o"((uro wf)x bro 65))
Öb,
Ni(x))
36

---

Under review as a conference paper at ICLR 2021
We assume that Lf(ft is L, lipschic wrt Ni(z) and Ly-lipschitz wrt N((x). Additionaly, assuming that (o)( $ and lo"()] SC
(L, bb,
S Lnaror + LearoCT (wro + |wt1)
Using Lemma H.2 for a,g and wro, with at least
1 probability,
[Lo(f(,3)
s 221oav2lloga 2log m) 7 (Is + L2O|ur1 202 logm)
(F.4)
bb,
For projected gradient descent,
ÖLa(fe, )*)
16,1 S 11
2. loggm m (Tn 202 Co 2 m) t + 2m010ar L2O 2og
Using (.3)
16,1 < T logm
[i, + 202 2
ï + L2 20 C L20 Vlog
)
+ 2:
2nc, v 2 log m2
= [1, 20gLyCoaub 2
[n + Ln 2020II20 2lggm
21+t)0000//22og -1) 4
Finding lower bound on AJ, we get
A 2 2nc10.T 22logm [i, + 20g 2oggm
(
Ż, + Ln + 20, Cos
((1 (1+2ttoioaT 2llg.aar772llgggg -1)
+
isC
21c10aT V2logg (ī, + 202 2ow t
+ L, + in + 20, 20, log
(2ntoioat 2 mLaC)
LgC
= Ω (1ttaTTous logm)
We get similar lower bound on A
A Ω To log m)
37

---

Under review as a conference paper at ICLR 2021
Now, show coupling between (1) and P((x)) Assuming that of is C-lipschitz continuous, [x](2)) - -(()))
m
aro (ww + wro) (o ((1)o + wx)x + byo + bb)) o' (' + b,a)) Σ
o" + bro) (wro(wfr + b,)))
m
S Ct 2arolut + wrol + CT Σ
arowrol 6,
Cr Σ aro (2/u² + whol + w + 6,,
CT (2010 v 2lo m
(IIW")) + [|oll + 2020 2 m (I]W')
|IB*)1a)
O Twtt log m (A + A)))
where inequality (i) follows from Fact
H.2 Now, using = T to find upper bound on
[N)(x) (=()), we get
(x) Pf = O (To
(A A7)
O O m (AT
A?)
(ro log m (A + Ab))
= (To log m a logm)
= o2 m (log m)²)
T T2 (logm)²
emr log m
22h (log
=0
For owh in range Ω log m
and 0(1), (7 - (x) can become very high and in those cases,
N2 (x)) and Pf (x) willnot remain close.
G ADDITIONAL EXPERIMENTS
In this section, we show experimental results on synthetic ID 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 Gaussians and other one is mixture beta distributions. All results are averaged over different iterations.
G.1 RESULTS FOR UNCONSTRAINED NORMALIZING FLOW
In F 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 and Bt and convergence speed. To reproduce situation similar the theoretical analyses for unconstrained normalizing flow, we choose learning rate as where is constant. The first row of Figure 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* and B' decreases with increasing m. Moreover, the change is proportional to 1/ /mm which is similar to the bound in theoretical result. From the last column of Fig. 3 we that the training speed for different values of remains almost constant. Our choice of I in theoretical analysis also poly-logarthmmicaly depends upon m. We obtained similar results for Gaussian distribution well.
38

---

Under review as a conference paper at ICLR 2021
(a) Mixture of Gaussian data distribution
(b) Mixture of Gaussian generated data
(c) Mixture of Beta data distribution
(d) Mixture of Beta gener- ated data
Figure Comparison of data distribution and generated data for mixture of Gaussian beta distributions
Ditributions
Gaussan
355
m--250
1235
m-2000
TH40000 8mh
aw-9350
mi 14t0
Mixture Distibbboons
10-
am--3
m--10
1000
sw-1300
me 2000
m--4433
Number
Number
Turr bor apadct
Figure 3: Effect of over- parameterizzatin training of unconstrained normalizing flow mixture of Gaussian and mixture of beta distributions
39

---

Under review as a conference paper at ICLR 2021
100000
m=200
122rmm di dstrgg- in
400
f0-403
Mamber of spachs
Mumber of spoch
Number of spocns
rixture Bata D ontiibutions (1.:=0.2)
Hixture of Bata onstibutionn (1.2002))
Nisture Eeza Distrr Intiibuutinn 0.6.-32)
changge. 5 4
varm of change F1
16
2
Figure 4: Effect of over-parameterrizaion on training of small sized constrained normalizing flow
G.2 RESULTS FOR CONSTRAINED NORMALIZING FLOW
In Sec. 2.1 suggested that high overparameterizatioo may adversely affect training for constrained normalizing flows. We now give experimental evidence for this in Figs 4 and We use Gaussian distribution
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. [igs.5aand] and 6 we see that 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 1.2-norms of W and B for m 6400 are at least at large as those of m 1600. On both datasets, as we increase the learning rate, I.2-norm of Ba 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 Gaussian dataset for number of hidden layers 1600, 6400 (see 7i These observations support our claim in See 2.1 that for learning and approximation of overparameterized constrained normalizing flow, neural networks need large L2-norms of W and Ba
H USEFUL FACTS
Lemma H.1. Suppose Z ~ N(0, 0²) and Y = Ek=ı Z is chi-squared distribution with following property for all E (0.
n
(-
nt² (-mt²
Pr
z
0²
2t < 2exp
804
Proof. From example 2.11 from Wainwright 2019), for Z/ ~ NN 1) and Y = >k=
z is
chi-squared distribution with following property for all E (0, 1).
(-m²²
nt²
Pr
z
2
< 2 2xx
(-8
71
k=
Using above equation for
Ze
22
1
nt²
Pr
2
$ 2 exp
8
k=1
nt²
Pr
Z
02
>
< 2 exxp
80
k=1
40

---

Under review as a conference paper at ICLR 2021
Modiur of Gissssion Dsttribfiim (1.-000012))
Modiune of Getasiinn Indriiuttonn (12-0.0112))
Misture Counsenn Desir buttes (ur 0125)
12 charge
cam of Shange
LoG0
10-2000
som of dergee
14-0400
Iaa0 805
momm
Manther of apoche
Manter aporhh
Maxture of Gisseston ien (Ir--0t
Moxiure of Gauesson Ded atutatit (In-wDl (1.-0..15)
Misture Contee Eistributionns T.N
13 ram caorge
namm chartee
m=1000
meb420
m=18000 munith
m-1600
1.000
com diergee
nome
Martber of spoche
Marther of appohh
Bumberr aports
Figure 5: Effect of ver-parraettriizatonn training of constrained normalizing flow mixture of Gaussian dataset for number hidden layers m 1600, 6400
41

---

Under review as a conference paper at ICLR 2021
Middure of bwin Bnstr Butiebuters ri 21
Misture Bein Disttr Inttribitiosss 11 01225
Micture of tetl D Wh Vm 0.00255
n=1000
m-0020
1Peemm chargein
1000 (ABS
m-1600
nim4400
som dherge
momm
Monther spoche
Marterr of aporhh
Mistore of Dett Dreinbations (1--wo.o us1
Misture Data Eleembttions (Ixww..1
Meciure of Dwwrrri Destribationn L. ONO
11-04000
com dheroe dhargeens 5
nam shargee
m=1000
meb420
m-1800 muitth
[1
14-6600
Manther of spoche
Marther of apoohh
Bunbhrr sporns
Figure 6: Effect of ver-parramterizzation training of constrained normalizing flow mixture of beta distribution dataset for number hidden layers m = 1600, 6400
42

---

Under review as a conference paper at ICLR 2021
Modium of Giuusion Detrib.eem (1r-0.0122))
Modiure of Gatasion Indributien (12-6.0112))
Misture Counsenn Disir buttees (ix 0125)
1Phemm chargee
var
W-1000 kott
L0G0
100
20
108
500
m=-100
m1-0400
12 mom of dergee
Mamteer of spochh
Marther of aporth
Maxture of Gissesenn Dist iens -in-wit
Moxiure of Gaueszon Und (1r
Misture Cinrecan Sistributtinn 7.
thargeen
namn charter
m=1000
meb420
m-10000
109
10
20
m-1600
m=1100
m=-5400
com dierge
nomm chargee
Manther of apoche
Marther of apprch
Bumberr aporrs
Figure 7: Effect of over-parraeetriizationn training of constrained normalizing flow mixture of Gaussian dataset for epochs=1000 and number of hidden layers m = 1600, 6400
43

---

Under review as a conference paper at ICLR 2021
Lemma H.2. Let X1, X2,,,... Xn be independent random variables from No, o²), then with at least 2i probability, following holds.
max (1........
Xil S 2010 2010 2
Proof. From Romberg 2012),
[xi| S (V22 +1) s 20 (V2log
max (1,2..2....)))
Assuming n 2 2, the last inequality follows. Using Markov's inequality,
[xil 2 2010 (Vllog S
Pr
max iE
21 - 1
Pr
max iE
X S 2010
2logn
Lemma H.3. For standard Gaussian random variable concentration inequality holds.
X from N(0,, following anti-
2R
( S R)
<
Proof. (From Du et al. 2018) For standard Gaussian random variable X
2R
Pr
S
R
2m
Using R R', o. we get the required result.
Lemma H.4. Suppose function f RRd + I is Lg Lipschitz continuous and L--corrdinate wise Lipschitz continuous i.e.
(s(a) - /(b) st, a bll
Va, b E Rd
(Standard Lipschitz continuity)
[a(1,, "..
(d) s(a,, 02, by, da)l SLila; bil Va,, a2,..., ai ad b, E and vi E [d]
(Coordinate-wise Lipschitz continuity)
a function I satisfies La-coordinate wise Lipschitz continuity for all then function I follows following inequality.
If a2, ad) - f(b, b2, ..., ba)l <
Σ Lg la; bil
i=1
Moreover, the function f also satisfies standard Lipschitz continuity with Lg Lipschitz constant where inequality between Ly and Lg as follows.
Tgg S
Σ
L
1=1
44

---

Under review as a conference paper at ICLR 2021
Proof. Define (a1, 02 ad) and b (b,, b2. bd)-
[f(1 02,,.., 0d) f(b,, b2, b.. ba)l - f(11, d2,,.., ad) f(b,, 022 02,,..,00 ad)
+ (bi,, 02 03 03.-....) - [b1, b2, az, aa)
+ (b 02, ag,... Q.) f(b,, b2, Dg,... ad)l
+ + [f(b) b2 .
bd az) f(b,, b2, bs, ba)l
< 1 la bil + Lo2 l02 b2l + Ted lad bal
d
Σ
-
where last inequality follows from Cauchy-Schwarz inequality.
Fact H.I. (Hooeffingg' inequality Binomial random variable) If we have binomial random variable with parameters n (toral number of trials) and p (probability of success). For number successfil trial k np. following inequality holds.
k
2
Pr 2 S exp
-2n
P
Fact H.2. (Half-normal distribution) X follows a normal distribution with with mean and variance o², (0, (²), then Y = | Xsign (X) follows hulf-normal distribution with mean av2 E [Y]
Fact H.3. For gaussian random variable X ~ N(0, o²), Vt E (0, we have
4t
Pr[[X] 2 t)
50
Fact H.4. The sum of reciprocals of the squares of the natural numbers is given by
6
Fact H.5. (Theorem 3.1(y') Li Li & Yeh (013)) For any a > 1 and x E 0, a-T))
(1+x) <
1 (a: 1)
Fact H.6. If AArilhmeii--eomeelee Progression(AGP) is as follows.
a, (a + d)r, (a - 2d)r2 (a + 3d)r ....., . [a + (n - 1)d] n-
where a the initial term, is the common difference and is the common ratio. The sum of the first terms of the AGP (S,) is given by
S, a la (n 1)d r" dr (1 - 1m=
--r
(1 r1-
Fact H.7. (Lemma A.3 from Ji et al. (2020) The Fourier transform of f is defined as
/
f(w)
2 dx
The polar decomposition of the Fourier transform f is f(w) [f(w) (2100 with ( < 1.
The Fourier transform i follows below properties.
1. [(()] < [| for any real number w.
45

---

Under review as a conference paper at ICLR 2021
2. Let 0 be given and define == Go is Gaussian with coordinate wise variance a². Then Ga G.. (meaning G. has radial component) and
Ga(w)= = V2T02
Ga(w) =
= 2 (w/B)
Definition H.1. Let F be set of functions Rdd - lK and X ,
22, ...3 Fn) be finite set of
samples. The empirical Rademacher complexity of F with respect to X' is defined by
sup E (.(())) SEF n
=
Lemma H.5. The Rademacher complexity have following properties.
Suppose [x] S for all X. The class FF = fx - wx+b complexity R (X,F) v
|w| S B, |6| S B) has Rademacher
2B
Vn
b. Given F1. classes of functions, then R (2: F2) = R (X:F) (x:F2))
Given F2,, classes of functions from X _ I and suppose E R is fixed vector, then F = fx E (fr()) | J. E F.} satisfies R (xFF)) s 2||w||1 m R (x)F,) where a is 1-Lipschitz continuous function.
Proof. bld of the proposition are from Allen et al. (019). Proof of the part is as following.
n
n
R (X.
sup fEF
Σ
Eitz
+
B
n2
E Bc-(11)
+
n
Using Jensen's inequality, get
0.5
E
Es
Σ
Eg
Σ f
Using independence of Es for all E [ns]. we get
27
Ex
Σ
Eg
Σ
1=1
Σ
i=1
Using same technique, will get same bound for Eg Ed|l
[
2B
R(
Vni
Fact H.8. (Rademacher Complexity) If F2, Fx are l classes of functions R2d + R and L Rd (-b, b) is Lipschhi, continuous function for any D, then
1 Σ Tax (1,
log
sup heF
EZED [Te (f(()),-.,
5 22 (x;22) + +bl
n
2n
46

---

Under review as a conference paper at ICLR 2021
where C is set of all functions Lg. Using vector contraction inequality from Maurer 2016), we ger
1
sup h h
BEED (Tz ((1(())).,,((())))
Σ
To (fi [x()))
==1
Σ R((:F))
log g
< 2222Lg
+ +b4
2n
47


Reviews:
[{"review_id": "zF84QKnepqX", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n \nHere are my detailed comments. \n\n\n\n\n\n\n\n- The presentation of theoretical results can be further improved. For instance:\n-- In Lemma 1, what does $(\\phi^{-1}(F’)){\\|\\delta}$ mean?\n-- In Theorem 2, it seems that to derive a finite-sample analysis, the second-order derivative of $F^*$ should be finite. The authors may want to add such a claim in the statement of Theorem 1.\n-- What is the definition of  $\\tilde w_i$ in Lemma 3? \n-- What are the definitions of $M_{\\hat L}$ and $m_{\\hat L}$ in Lemma 12? Are they related to $n$?\n-- Second line in Page 24, eq.() is a typo. \n- My main concern is the scalability issue. The main theorem suggests that it is possible to use a neural network to approximate the first-order derivative of the unknown distribution transformation $f$, and to use the neural network to construct the original function $f$ with sufficient quadrature points. However, just as Theorem 1 suggests, the number of quadrature points is of the order $O(1/\\epsilon)$, where $\\epsilon$ is the approximation error. Thus, it seems that for a $d$-dimension case, the number of quadrature points may be the order of $O(1/\\epsilon^d)$. Such an exponential dependence is unacceptable in terms of the scalability. Can the authors explain more about the high-dimension case? \n- In Section 2.1, the authors suggest that overparameterization may hurt the overall performance of CNF by showing experiment results of tanh activation function. Is it true that the failure is actually due to the gradient explosion caused by tanh activation function rather than overparameterization? Meanwhile, it seems that the reason for the authors to use tanh is because they want activations with continuous derivatives and convexity for loss function. Why do we need such a convexity? Is it due to some theoretical concerns (like to make the derivation go through) or concerns from practice?\n- The authors may want to discuss existing results about optimization and generalization of overparameterized deep neural networks [1-3], which are related to this work. Besides, this work relies on the idea of the existence of a pseudo network which approximates the target function well, which may be related to [4-6]. Can the authors discuss and show the relations between these works?\n\n[1] Zou, Difan, et al. \"Gradient descent optimizes over-parameterized deep ReLU networks.\" Machine Learning 109.3 (2020): 467-492.\n\n[2] Du, Simon, et al. \"Gradient descent finds global minima of deep neural networks.\" International Conference on Machine Learning. 2019.\n\n[3] Allen-Zhu, Zeyuan, Yuanzhi Li, and Zhao Song. \"A convergence theory for deep learning via over-parameterization.\" International Conference on Machine Learning. PMLR, 2019.\n\n[4] Allen-Zhu, Zeyuan, and Yuanzhi Li. \"What Can ResNet Learn Efficiently, Going Beyond Kernels?.\" Advances in Neural Information Processing Systems. 2019.\n\n[5] Chen, Zixiang, et al. \"How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?.\" arXiv preprint arXiv:1911.12360 (2019).\n\n[6] Ji, Ziwei, and Matus Telgarsky. \"Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.\" arXiv preprint arXiv:1909.12292 (2019).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "nrtPqwNFnlE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\n\nThe paper studies the problem of learning univariate normalizing flows with single-layer neural networks. The paper studies two models of normalizing flows: constrained normalizing flows (CNFs) and unconstrained normalizing flows(UNFs). For UNFs, the paper gives finite-sample results for UNFs in Theorem 1.\n\n**Positives**\n\nThe paper studies two models of using neural networks for learning normalizing flows. For CNFs, paper identifies issues with the Taylor expansion in the parameter space. For UNFs, Theorem 1 shows that running SGD with a suitable learning rate leads to a neural network with small error. A theoretical study of normalizing flows looks like a promising research direction.\n\n\n**Negatives**\n\nThe paper is very difficult to follow because of numerous grammatical issues and lax notations. In particular, parenthetical commas are incorrectly used throughout the paper.The paper should also be reorganized: Theorem 1, which is the main result, appears on Page 7. Please see the comments below for more details.\n\n**Score**\n\nI recommend rejection of this paper. The paper is not well-written and difficult to follow. The results on CNF are unsatisfactory (Section 2.1) and it is difficult to parse  the results in UNFs (Theorem 1).  The paper should go through major revisions for clarity. Please see the comments below for more details.\n\n**Major comments**\n\n1. I am confused by the term \"constrained normalizing flows (CNFs)\" for $a^2, w^2$ instead of $a$ and $w$. After this re-parameterization, the parameters are no longer constrained. \n1. As the main result is Theorem 1, UNFs should be discussed earlier and CNFs should be discussed later. \n3. Theorem 1 is too informal, and the statement of Theorem 2 should be explained better. The complexity measures $C_1, C_2,$ and  $C_3$ should be mentioned in theorem statements and discussed in the main text.\n1. Should $\\rho$ be a monotonically strictly increasing function or simply non-decreasing? (See the line after Eq. (4)) If so, why are ReLU networks considered throughout the paper. The first line in Section 2.1 should also be clarified.\n2. The notation $L(f,x)$ is over-loaded in different sections: sometimes it is used with $f$ and sometimes with $f_t'$. This is extremely confusing.\n4. ** Note that by the initialization, $|w_{r0}|$ and $|b_{r0}$ are O(\\sqrt{\\log m / m})**\nWhat is the initialization distribution, and why can we not change the initialization distribution?\n5. On page 5, the last line of the first paragraph: $L(N_t,x_t)$ is defined as the squared loss, but it was defined earlier in Eq. (2).\n6.Please provide more details for experiments in Section 3. What were the base distribution, target distribution, and training set size? Since 1D distributions are easy to visualize, how does the estimated distribution compare with the target distribution?  \n7. In the top right image of Figure 1, I don't see any benefit of large $m$ --- the training curve is too unstable?\n\n\n**Minor comments**\n\n\n1. *Recent work in supervised learning attempts to provide theoretical justification for\nwhy overparameterized neural networks can train and generalize efficiently in the above sense* Add a citation.\n2. *We will only train the wr, br, and the ar0 will remain frozen to their initial value*\nWhat about $w_{r0}$ and $b_{r0}$?\n3. Some terms are defined but they are not used ever again, for example, $L_G$ for the Gaussian distribution.\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6UvrYpaoWWq", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis 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.\n\nPros:\n\n1. Understanding why normalizing flow works and the learning process of the underlying neural networks is an important problem, and the idea of using overparametrization to explain this is interesting.\n\n2. The experimental methodologies and theoretical computations appear to be correct.\n\n3. The intuitions behind the problem setting (including the modifications to the algorithm) and the ideas behind the proof are explained in detail and easy to understand. The limitations of this paper are also discussed.\n\nCons:\n\n1. This particular setting of normalizing flow models used in this paper might be a bit limited. The authors only analyzed the univariate case, which is far from the high-dimensional case in practice. It is possible that these two cases work in very different regimes due to the differences between high-dimensional and low-dimensional probabilities. The authors also made two important modifications to the unconstrained normalizing flow: changing the base distribution to standard exponential distribution and changing the quadrature to simple rectangle quadrature. These modifications can also make the model work in very different ways from practice, and the authors did not provide enough theoretical or experimental justifications for the modifications.\n\n2. The techniques used in this paper mainly come from [1], and the proof framework and results are roughly the same. The authors made modifications to the setting so that the optimization becomes convex, and this seems to be the only justification for these modifications. The proof lies in the NTK/lazy training regime, which is hard to generalize to non-convex settings such as moderate width or large learning rate.\n\n3. The structure of this paper may need some improvements. The introduction section is a bit too long with perhaps too much background knowledge for normalizing flows. The contribution and related work parts can also be shortened. Section 2 is also a bit too long, and it may be better to re-organize this section and separate it into preliminaries/main results/proof sketch/discussions to make it easier for the readers to understand.\n\n4. The experiments in this paper are a bit simple, i.e., the authors only did experiments on synthetic datasets like Gaussian mixture with models whose underlying neural networks have only one hidden layer. This setting is far from empirical settings, which makes the conclusions of the experiments not so convincing.\n\n[1] Allen-Zhu, Zeyuan, Yuanzhi Li, and Yingyu Liang. \"Learning and generalization in overparameterized neural networks, going beyond two layers.\" Advances in neural information processing systems. 2019.\n\nRecommendation:\n\nI vote for rejecting this paper. As mentioned in \"Cons\", my major concern is the limitations of the problem setting in this paper and the novelty of the proof. The setting for normalizing flows in this paper is a bit far from practice, and the theoretical proof highly depends on the convexity of the optimization process, making the theoretical claims hard to generalize to more practical settings.\n\nSupporting arguments for recommendation:\n\nSee \"Cons\", especially points 1 and 2 there.\n\nQuestions for the authors:\n\n1. Please address the cons mentioned above.\n\n2. The authors use \"generalization\" in the title, but I am a bit confused because I do not know what generalization means in this normalizing flow setting. Does this mean something like the KL divergence between the learned distribution and the target distribution?\n\n3. In the last paragraph of page 5, the authors said that convex activations \"cannot be used\" because then N(x) would also be convex. Does N(x) have to be non-convex?\n\nAdditional feedback:\n\n1. It may be better to explain \"quadrature\" by figures or examples in the introduction because this seems to be an important difference between normalizing flow models and normal neural networks but it is not explained in detail in the introduction. Explaining this earlier and clearer can help the readers better understand this paper.\n\n2. Typos: In the abstract, \"On the other\" -> \"On the other hand\". In the paragraph just before Section 3, \"Lemmas 1\" -> \"Lemma 1\".", "extra_scores": {}, "extra_text": {}}, {"review_id": "2K-q-chykAZ", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper 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.\n\nFirst, the authors argue that overparameterization hurts the learning of constrained normalizing flows (CNFs) that impose positivity of weights though either projected gradient descent (PGD) or quadratic parameterization. Second, the authors prove that unconstrained NFs (UNFs) by modeling the gradient function f’ rather than f itself can learn the data distribution.\n\nI definitely think this work makes some interesting contributions in terms of provable results for learning over-parameterized NFs. This is given by the fact that the problem is less well-understood compared to supervised learning. However, I am not sure about the impacts of the contribution to the general multivariate/high dimensional setting. Also, I have some other questions:\n\n+) The first result on the failure of PGD/quadratic parameterization in the constrained case is interesting, theoretically. But I wonder if there is any artifact in the proof framework using pseudo networks or linear approximation.\n\n+) Would you see the same observation in Figure 1 with more number of epochs and other activations, says ReLU. Please clarify “Gradient-based optimization algorithms are not applicable to problems with discontinuous objectives” around the end of page 5.\n\n+) What are the difficulties of the Gaussian base distribution?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Motivated by the fact that the benefit of overparameterization in unsupervised learning is not well understood than supervised learning, this paper analyzes normalized flow (NF) when the underlying neural network is one hidden layer overparameterized network and proves that for a certain class of NFs, one can efficiently learn any reasonable data distribution under minimal assumptions. The paper is very well motivated. However, the main concerns from the reviewers include (1) the writing quality and presentation are poor, even after revision during the author’s response; and (2) the analysis is limited in the neural tangent kernel (NTK) regime, which makes the results less significant. I agree with the reviewers’ evaluation and I think the first concern can be addressed by a careful revision, while the second concern needs additional nontrivial effort. Thus, I recommend rejection.
Decision: Reject