Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider the density estimation problem in multiple dimensions. They study the convergence properties of a low-rank estimator: the estimator is the sum of a few tensor products of univariate histograms. They give asymptotic and finite sample bounds for convergence. When the true density is a sum of k tensor products of Lipschitz densities, the authors show an $L_1$ convergence rate of $n^{-⅓}.$



main_review: Theoretical results in the manuscript are substantial. 

They only prove the existence of a low-rank estimator; they do not devise such an estimator. 

It is surprising that there is no $d$ in the asymptotic convergence results. I did not have time to check the proof.

Minor comments, mostly typos:
- In the paragraph below equation (3), $x$ is called a matrix, even though it is a vector
- Page 5, just before "Main Technical Tools", should be $n^{-1/3}$ not $d^{-1/3}$
- Theorem 2.6: the first line in the statement has some indexing errors in the product
- Equation (12): sum should be until $n$, and a factor of $1/n$ is missing

limitations_and_societal_impact: No concerns.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper shows a number of results on non-parametric density estimation using mixtures of product histograms with two proposed methods called \textit{multi-view histograms} and \textit{Tucker histograms}. A simple experiment is also performed to show these methods work better than the usual histogram estimation in some specific cases. There are two major theoretical contributions as follows.  Firstly, the authors give some asymptotic error control for the proposed methods for any true density functions based on sample sizes, number of histograms' bins, and number of mixtures.  Secondly, they prove that when the true density is a mixture of product distributions, the proposed methods are more favorable compared to the traditional histograms method in terms of the convergence rate.
main_review: --- Strength:

(1) The theoretical problems above are well studied in the paper. All the results are rigorously presented.
 
(2) The techniques using here are well-known and are applied appropriately to support the proofs. The assumptions of the problem are reasonable and useful.

(3) The experiment also sheds some light on the superiority of the proposed method in some specific cases.

--- Weakness:

(1) The title: "Beyond smoothness": I can not see what is beyond the smoothness here as we still need to assume the smoothness of true density to prove all the results. Even in the case that the true density is "low-rank", the assumptions on smoothness of product densities are required.

(2) Experiments: The shown experiment is too rudiment and does not strongly support the argument in theory part. The description of the experiment is too detailed while the discussion and explanation parts are short. 

--- Point to improve:

(1) In the experiment part, the authors can conduct an simulation study to show the rate when approximating by multi-view histograms compared to the usual histograms method. 

(2) We can also find a number of real data sets having mixtures of product distributions law and try to compare the proposed methods on them. They appear a lot in psychological field (\url{https://arxiv.org/pdf/1904.04378.pdf}), see also the papers which cite \url{https://projecteuclid.org/journals/annals-of-statistics/volume-37/issue-6A/Identifiability-of-parameters-in-latent-structure-models-with-many-observed/10.1214/09-AOS689.full?tab=ArticleLinkCited} for more information.

--- References:

The authors may consider adding some recent references on multivariate density estimation with very fast MISE via sin kernel, such as via the Fourier integral theorem [1]. In particular, this work shows that when the density function has supersmooth Fourier tails, such as Gaussian distribution, the MISE rate is $n^{-1/2}$ (up to some logarithmic term). Furthermore, the usage of sin kernel also circumvents challenge with choosing covariance matrix in standard Gaussian kernel while it is able to learn the dependency in data automatically. 

[1] N. Ho, S. G. Walker. Multivariate smoothing via the Fourier integral theorem and Fourier kernel. Arxiv preprint Arxiv: 2012.14482, 2021.
limitations_and_societal_impact: I do not see any foreseeable limitations and negative societal impact of this work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors propose and analyse a novel method for nonparametric density estimation. They provide a method for providing a density estimate with low rank structure which is a mixture of densities that factorizes across dimensions, with each factor defined as a one dimensional histogram. They provide conditions under which their estimator is consistent and characterize upper and lower bounds on its error.
main_review: The approach described is novel, and the theoretical results are interesting and nontrivial.

The paper has some limitations I will highlight.  The authors could improve the paper by giving more context into why they are solving the problem they address.  In particular, given that the improvement obtained relative to standard histograms is most pronounced in high dimensions, in what settings might it be useful to have a 3 dimensional or higher density estimate of this form?  When the number of samples is large, does this matter for downstream analyses?  If so, of what sort of downstream analyses.

The paper should be much better polished.  The paper has many typos, and missing information -- some of this impedes understanding.
“Nonparametreic” in the second sentence.
In section 1.3, what is “M” (i.e. “M satisfies a property”).
“Who’s” should be “whose”
“One can recover y”, should “y” be “x”?

In section 1.3, what does that last sentence of the second to last paragraph mean?  What is “our setting”, and why is this an important setting to consider? 

What is table 1?  This is not referenced in the main text (or maybe “table 3” is a typo?), and the legend “Experimental results” is not informative.  Are higher or lower values better?

Some sentences do not make sense grammatically. E.g. in section 3, “This problem when seems be further…”

The authors have not included line numbers, which would have been helpful for referencing certain parts of the paper.
limitations_and_societal_impact: One sentence describing no foreseen societal impacts is provided.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work is concerned with the (high-dimensional) density estimation problem.  While most minimax rates  for  the  problem  are  expressed  in  terms  of  some  measure  of  smoothness  that  the  unknown  distribution is assumed to verify, the current approach adds more structure, by requiring that the joint density be tensor-decomposable (in a PARAFAC or in a Tucker sense), with Lipschitz components.  The authors show(theoretical analysis) that this subverts the smoothness-only minimax rates together with their curse of dimensionality. In order to illustrate their method, the authors further perform experiments in which –perhaps controversially– they relax the estimator search to an L2 problem.
main_review: The results seem to be novel. The value of this work is primarily of a theoretical nature, as the estimators are not computationally tractable (as made clear by the authors). This reviewer did not very correctness of the proofs in the appendix.  The authors have addressed the comments that reviewers have raised while under review for previous conferences. Slightly tends towards acceptance.

* On p.2,  the authors already mentions the estimators are not computationally tractable. Briefly already state why here (or at least refer to the Main Technical Tools paragraph).

* Could the authors comment and provide the reader with some intuition about the obtained rate
($1/\sqrt[3]{n}$ instead of $1/\sqrt[d]{n}$). Why should we expect a cubic root?

* What would happen if we were to consider components with different degrees of smooth-ness (more general Holder classes) instead of Lipschitz?

* As a follow-up question:  do you expect the obtained rates to be tight;  namely, can one construct a corresponding lower bound?

* Further explain what the different columns of Table 1 correspond to.

* Typos.
    * p.1  nonparametric
    * p.3  asymptotically
    * p.4  entries
    * p.7  Lipschitz
limitations_and_societal_impact: Adequately addressed.
review_title: null

Meta-review: The authors present an analysis of two classes of histogram-based density estimators that incorporate low-rankness structures analogous to CP and Tucker tensor factorizations, and experiments show that in practice a simple heuristic motivated by the theory outperforms standard histograms. The major contribution of the paper is the theoretical analysis of the convergence of histogram estimators incorporating low-rankedness, both asymptotically and non-asymptotically, that shows their convergence rate is independent of the dimension. These results quantify the benefits of using low-ranked histogram estimators, as the convergence rate of the standard histogram estimator goes down with the dimension. They are significant contributions to the theoretical underpinnings of the growing are of low-rank density estimation.
Decision: Accept (Poster)