Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: A purely theoretical contribution in which the authors present a series of approximation results describing which densities can be well-approximated by DBNs.  Additionally, they provide quantitative error bounds for both Lp based norms and the KL divergence.
strength_and_weaknesses: Strengths:  Fills gaps in the theoretical literature on what densities can be approximated by DBNs.

Weaknesses:  Proofs are a bit terse (as is necessitated by space).  Doesn't contain any experimental evaluation, but I don't think that is necessary for papers of this type.
clarity,_quality,_novelty_and_reproducibility: Clarity:  Overall, I found the motivation and the presentation of the theorems clear (though I had more difficulty following the proof details due to lack of expertise).  Still, I have a few comments:

(1) L^q(R^d) is used in the intro before being defined.
(2) At the beginning of section 1, RBMs are described as both planar and fully connected (these statements are antithetical).
(3) The notation in Theorem 3 isn't consistent with Proposition 1 -- don't you need to sum over the hidden variables?

Quality:  I'm not able to assess overall quality as I am not able to validate all of the proof details (and the proofs are a bit terse for a non-expert like me to follow completely).

Novelty:  The work does appear to make novel contributions over existing works, and the authors are careful to point out exactly where those contributions are.

Reproducibility: n/a
summary_of_the_review: An interesting theoretical contribution that precisely describes classes of probability densities that can be well approximated by DBNs.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper looks at the approximation capabilities of a DBN with 2 layers in which the first layer is a has binary states (both hidden and visible) and the second layer has continuous visible state. Further, it is assumed that the conditional distributions for the last layer all come from the same parental distribution (that is, they are just shifts and rescalings of each other). Under such an assumption, we can think of the DBN as mixture model (such as a Gaussian Mixture model with $\sigma I$ as the covariances when the parental distribution is Gaussian). 

In this set up the paper shows that as the number of hidden nodes goes to infinity, the model can approximate arbitrarily well any measure that is absolutely continuous with respect to Lebesgue measure (i.e. measures that have distributions with respect to the Lebesgue measure.) That is, as the number of mixtures factors increases we can approximately any density. 

In some cases the paper provides error rates. 


strength_and_weaknesses: **Strengths**
---

1) I think the major strength of the paper are the error rates that it presents. In particular, I think even for Gaussian Mixture I dont the optimal error rate is known. 

2) I think writing is clear and proofs are easy to follow and use mostly standard analysis tools. 

**Weaknesses**
---

1) I think a discussion to prior theoretical work on approximations by mixture models is missing. Specifically in the case when we think of the special cases of mixtures of Gaussians and mixtures of exponential families. Significant prior work has been done. In this regard, I think the universality is known (please correct me if I am wrong). However, the strength of the this paper are the error rates. 
clarity,_quality,_novelty_and_reproducibility: **Clarity**

The paper is well written and is easy to read and understand. 

**Novelty and Significance**

I think the error rates presented are new and are of theoretical significance. 

summary_of_the_review: In summary, I think this is a well written paper and with interesting and new results.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors consider approximation of probability density functions by deep belief networks with binary hidden units. Convergence and rates of approximation are provided with respect to the L_q norm and K-L divergence. 
strength_and_weaknesses: The topic of approximation by deep belief networks is interesting. Rates of convergence are given by applying the Rademacher index of the L_q spaces. There have been many results in the literature of distribution regression, on learning of probability density functions. The authors do not provide any comparisons with the existing methods for approximating probability density functions. Using convolutions for approximations is fine, but regularity of the approximated function is not used. 
clarity,_quality,_novelty_and_reproducibility: The paper does not give a clear introduction for deep belief networks. The presentation can be improved. The mathematical results are not so deep, without using any regularity of the approximated function. 
summary_of_the_review: The topic of approximation by deep belief networks is interesting. Rates of convergence given by applying the Rademacher index of the L_q spaces might have applications in some other problems. But a large literature of distribution regression is missing in the paper. Using convolutions for approximations without involving regularity of the approximated function is rather shallow.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This manuscript investigates the approximation error of classic deep belief networks (DBNs), in particular DBNs with two hidden layers of size m and m+1, respectively. It is demonstrated that, under both  L^q-norm and Kullback-Leibler divergence, DBNs are universal approximators. Moreover,  as claimed by the author, sharp bounds are obtained for the approximation error. 
strength_and_weaknesses: Strengths:

1. This is a solid theoretical work on the analysis of approximation error of DBN, which has been an open problem. 

2. Two metrics, L^q-norm and KL deivergence, are considered. 

Weaknesses:

1. It seems that the main results of this manuscript are restricted only to the case of DBNs with two hidden layers of size m and m+1 respectively. Can the results still hold for general size m and n for two layers? If not, why? 

2. The authors stated that, e.g., in the abstract,  "we establish a sharp quantitative bounds on the approximation error in terms of the number of hidden units ". How to verify the sharpness of the obtained bounds? I did not see any supportive results to show that the obtained bounds are sharp. Can the authors add more details or explanations on this point? I would be very nice if some empirical evidence is provided. 
clarity,_quality,_novelty_and_reproducibility: This paper is well-written. The result of the theoretical analysis in this paper is novel and the obtained bounds of the approximation error of DBNs in the case of two hidden layers of size m and m+1, respectively.
summary_of_the_review: This manuscript is theoretically studied the approximation error of DBNs with   two binary hidden layers of sizes m and m + 1, respectively. In particular, under both L^q and Kullback-Leibler divergence metrics,  DBNs are proven to be universal approximators and the bounds of the approximation errors have been obtained.  It is a solid work with theoretical contributions. My main concern lies in the restriction of the sizes of the hidden layers to be m and m + 1, as well as a lack of (empirical) evidence of the sharpness of the obtained bounds.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proves univeral approximation theorems for deep belief networks when the targeted distribution is continuous, with quantitative bounds for $L^p$ space with $p>1$. The proof idea is to make use of the efficient approximation of convex hull, each item is represented in the first layer, while the second layer is used to approximate the convex combination utilizing previous results for the discrete case.
strength_and_weaknesses: Strength:

The results are new and solid, generalizing previous results for the discrete case to the continuous case.

The proof idea is simple yet effective, through which this paper solves the targeted problem in a clean way.

Weaknesses:

The result is well-expected due to numerous analogical universal approxiamtion results for neural networks, and similar techniques have appeared in that literature.

What's the dependence of $M$ on $\epsilon$ in theorem 3?

The analysis is based on some technical propositions from previous works without proof. Adding more explanation/proof idea/easy example to these introduced propositions would make this paper more readable. For instance, proposition 11 could benefit from explaining the special case of $L^2$, which admits a short proof because it's a Hilbert space.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to follow. I believe the writing can be improved by moving some less important math to appendix and add more explanantion/discussion to the main-text.
summary_of_the_review: The results are new and solid, written in a mathematically clean way. I recommend accept.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The article investigates the approximation power of deep belief networks with continuous visible units. 

* Strengths are clarity of writing and novelty of the presented approximation error bounds for mixtures of continuous distributions in the context of shallow DBNs. 
* Weaknesses are the restriction to DBN architectures with two hidden layers and limited description beyond mixtures, moderate innovation in terms of the proof techniques, and missed opportunity to further explore different types of visible distributions (called parental distributions in the submission). 
justification_for_why_not_higher_score: The paper makes promising and interesting contributions to the theoretical understanding of DBNs with continuous visible units and I appreciate that the authors made several improvements to the manuscript following the discussions with the reviewers. Still, I find that the article could be further developed in some ways that would have made it a stronger contribution. 

* The article includes many references (particularly after the rebuttal), but misses relevant works such as [1], which gave approximation error bounds for Gaussian Bernoulli RBMs and binary Gaussian DBNs and should be referenced and discussed. The submission has some differences in that it considers approximation in Lp norms and other types of parental distributions. Nonetheless this does to some degree diminish the novelty value of the submission. I appreciate that [1] is relatively recent, but note that it appeared almost 4 months before the ICLR 2023 deadline. 
* The contribution would have been stronger by adding a discussion of the comparison of different parental distributions, which the authors identified as an interesting direction but deferred to future work. 
* The contribution would have been stronger by adding an empirical illustration of the rates, which the authors again deferred to future work. 
* While the results remain valid for deeper architectures, they do not clarify particular benefits of deeper architectures. Similarly, they have limited explanatory power in comparing DBNs with plain mixture models. 

Minor points 

* If not the title, then at least the abstract should more explicitly indicate the focus on DBNs with two hidden layers and continuous probability distributions. 
* The main results appear to be restricted to upper bounds and it would be good to more explicitly and clearly indicate which bounds are sharp and in what sense. The comment after Proposition 12 seems to pertain to mixtures. 


[1] Linyan Gu, Lihua Yang, Feng Zhou, Approximation properties of Gaussian-binary restricted Boltzmann machines and Gaussian-binary deep belief networks, Neural Networks, Volume 153, 2022, Pages 49-63. 


justification_for_why_not_lower_score: NA
Decision: Reject