Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

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

I 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:

+) 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.

+) 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.

+) What are the difficulties of the Gaussian base distribution?

review_title: Official Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: **Summary**

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

**Positives**

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


**Negatives**

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

**Score**

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

**Major comments**

1. 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. 
1. As the main result is Theorem 1, UNFs should be discussed earlier and CNFs should be discussed later. 
3. 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.
1. 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.
2. 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.
4. ** Note that by the initialization, $|w_{r0}|$ and $|b_{r0}$ are O(\sqrt{\log m / m})**
What is the initialization distribution, and why can we not change the initialization distribution?
5. 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).
6.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?  
7. In the top right image of Figure 1, I don't see any benefit of large $m$ --- the training curve is too unstable?


**Minor comments**


1. *Recent work in supervised learning attempts to provide theoretical justification for
why overparameterized neural networks can train and generalize efficiently in the above sense* Add a citation.
2. *We will only train the wr, br, and the ar0 will remain frozen to their initial value*
What about $w_{r0}$ and $b_{r0}$?
3. Some terms are defined but they are not used ever again, for example, $L_G$ for the Gaussian distribution.






review_title: Interesting model but the paper is confusing

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:

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

Pros:

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

2. The experimental methodologies and theoretical computations appear to be correct.

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

Cons:

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

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

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

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

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

Recommendation:

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

Supporting arguments for recommendation:

See "Cons", especially points 1 and 2 there.

Questions for the authors:

1. Please address the cons mentioned above.

2. 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?

3. 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?

Additional feedback:

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

2. Typos: In the abstract, "On the other" -> "On the other hand". In the paragraph just before Section 3, "Lemmas 1" -> "Lemma 1".
review_title: Interesting but somewhat limited problem setting with lack of novelty in proof techniques

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 
 
Here are my detailed comments. 







- The presentation of theoretical results can be further improved. For instance:
-- In Lemma 1, what does $(\phi^{-1}(F’)){\|\delta}$ mean?
-- 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.
-- What is the definition of  $\tilde w_i$ in Lemma 3? 
-- What are the definitions of $M_{\hat L}$ and $m_{\hat L}$ in Lemma 12? Are they related to $n$?
-- Second line in Page 24, eq.() is a typo. 
- 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? 
- 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?
- 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?

[1] Zou, Difan, et al. "Gradient descent optimizes over-parameterized deep ReLU networks." Machine Learning 109.3 (2020): 467-492.

[2] Du, Simon, et al. "Gradient descent finds global minima of deep neural networks." International Conference on Machine Learning. 2019.

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

[4] Allen-Zhu, Zeyuan, and Yuanzhi Li. "What Can ResNet Learn Efficiently, Going Beyond Kernels?." Advances in Neural Information Processing Systems. 2019.

[5] Chen, Zixiang, et al. "How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?." arXiv preprint arXiv:1911.12360 (2019).

[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).

review_title: Review for `'Learning and Generalization in Univariate Overparameterized Normalizing Flows'

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