Beyond Smoothness: Incorporating Low-Rank Analysis into Nonparametric Density Estimation
Authors: Robert A. Vandermeulen
Antoine Ledent
Venue: NeurIPS 2021 Poster (2021)
Keywords: Low-rank
nonparametric
density estimation
statistical learning theory
matrix factorization
tensor factorization
multi-view model

Abstract: The construction and theoretical analysis of the most popular universally consistent nonparametric density estimators hinge on one functional property: smoothness. In this paper we investigate the theoretical implications of incorporating a multi-view latent variable model, a type of low-rank model, into nonparametric density estimation. To do this we perform extensive analysis on histogram-style estimators that integrate a multi-view model. Our analysis culminates in showing that there exists a universally consistent histogram-style estimator that converges to any multi-view model with a finite number of Lipschitz continuous components at a rate of $\widetilde{O}(1/\sqrt[3]{n})$ in $L^1$ error. In contrast, the standard histogram estimator can converge at a rate slower than $1/\sqrt[d]{n}$ on the same class of densities. We also introduce a new nonparametric latent variable model based on the Tucker decomposition. A rudimentary implementation of our estimators experimentally demonstrates a considerable performance improvement over the standard histogram estimator. We also provide a thorough analysis of the sample complexity of our Tucker decomposition-based model and a variety of other results. Thus, our paper provides solid theoretical foundations for extending low-rank techniques to the nonparametric setting.

Beyond Smoothness: Incorporating Low-Rank Analysis into Nonparametric Density Estimation
Robert A. Vandermeulen
Antoine Ledent
Machine Learning Group
Machine Learning Group
Technische Universiät Berlin
Technische Universität Kaiserslautern
Berlin, Germany
Kaiserslautern, Germany ledent@cs. uni-kl.
wandermeulen@tu--ee
Abstract
The construction and theoretical analysis of the most popular universally consistent nonparametric density estimators hinge this paper we investigate the theoretical implications of incorporating a multi- view latent variable model, type of low-rank model, into nonparametric density estimation. To do this we perform extensive analysis on histogram-styyle estimators that integrate multi-view model. Our analysis culminates in showing that there exists a universally consistent histogram-styy estimator that converges to any multi-view model with finite number of Lipschitz continuous components a rate of ((1/ Vn) in L error. In contrast, the standard histogram estimator can converge at a rate slower than 1/ /n/n the same class of densities. We also introduce new nonparametric latent variable model based on the Tucker decomposition. A rudimentary implementation of our estimators experimentally demonstrates a considcrable performance improvement over the standard histogram estimator. We also provide a thorough analysis of the sample complexity of our Tucker decomposition-bar based model and a variety of other results. Thus, our paper provides solid theoretical foundations for extending low-rank techniques the nonparametric setting.
functional property: smoothness.
1 Introduction
Nonparametric density estimators are density estimators capable estimating a density p while making few assumptions on p. Two commonly used nonparametric density estimators include the histogram estimator and the kernel density estimator (KDE). A common characteristic these two estimators is that they make estimation tractable via hyperparameter that relates to smoothness, namely bin width and bandwidth. Large bin width or bandwidth allows for good control of estimation error' the cost of increased approximation error via large bin volume for the histogram and smoothing for KDEs. Selection of this parameter is crucial for estimator performance. In fact a recent survey on bandwidth selection for KDEs found at least 30 methods for setting this value along with few surveys dedicated to the topic [15].
While nonparametric density estimation has been shown to be effective for many tasks, has been observed empirically that estimator performance typically declines as data dimensionality increases, manifestation of the curse of dimensionality. For the histogram and KDE this phenomenon has concrete mathematical analogs. For example, these estimators are only universally consistent
"For estimator V restricted space of densities P, the estimation error refers to the difference between ||V pl and minger |p--g 4ll. where p is the target density. This similar to estimator variance. A density estimator is universally consistent if asymptotically recovers any density.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

- oc and h + O, with n/ + oo, where is the number of samples, d is the data dimension, and h is the bin width for the histogram and bandwidth parameter for the KDE [14]. One may then wonder whether there exists some other way to constrain model capacity so to alleviate this exponential dependence on dimension.
In this paper we theoretically analyze the advantages of including constraint akin to matrix/tensor rank in a nonparametric density estimator. We do so by analyzing histogram-style estimators (estimators that output a density that are piecewise constant on bins defined by a grid) that are enforced have a low-rank PARAFAC or Tucker decomposition. Enforcing this low-rank constraint in the histogram estimator allows for much faster rates on h + O, while still controlling estimation error. This can remove the exponential penalty on rate of convergence that dimensionality produces with the standard histogram estimator.
The bulk of this work focuses on analysis of hypothetical estimators that, while offering large statistical advantages over the standard histogram estimator, are not computationally tractable. At the end of this work include experiments demonstrating that low-rank histograms, computed using an off-the-shelf nonnegative tensor factorization library [23], consistently outperform the standard histogram estimator.
1.1 Density Models
Here we introduce the low-rank models that will be used to constrain our estimators. The first is
a multi-view model. A multi-view model p is finite mixture = > Wifi whose components
are separable densities f: = Pi,1 @ Pr. @ ... @ Pr.a" [19, 1, 37, 36). A multi-view model has the following form
k
I2..... Fz) =
W:Pr, (21) Pr,2 (12) .. Pi,a (Fa).
(1)
multi-view model with one component is typically called a naive Bayes model. For the estimators we propose, the component marginals Pt,j will have the form of one-dimensional histograms and the number of components l will be limited to restrict estimator capacity. When k = the model is equivalent naive Bayes model, p (11, T2, ... T..) = P1 (x1) P2 (I2) ... Pa (Ir))- When the component marginals Pt.j are histograms increasing expands the set potential estimates from all possible histogram estimates.
naive Bayes models when
The models in this paper are motivated by nonnegative tensor factorizations so we term them generally nonparametric nonnegative tensor factorization (NNTH) models. The previous model was related to nonnegative PARAFAC [34]. Our second model is based on the nonnegative Tucker decomposition [22]. A density in this model utilizes d collections, Fi..... Fd. of k one-dimensional densities, F. = [Pi.I..... Pi, }. and some probability measure that randomly selects one density from each
F.. This measure can be represented by tensor W R where the probability of selecting (p.......... .P....) from Fi X ... X Fa is W Wi....gg To sample from this model we first randomly select the marginal distributions P1,ij.--- Pd.iy according to W, and an observation is sampled according to the d-dimensional distribution Pı, & P2,12 8 ... @ P2,12- The density of this model
p (01, 32, .......... Rd)
Σ
Σ
W PI. (a1 ... Paaii (xa)-
We are unaware of previous works investigating this model for general probability distributions so we will simply term it the Tucker model. Again we will investigate estimators where the component marginals are diedemensioonl histograms and small corresponds to reduced model capacity. We remark that Tucker decompositions typically have rank vector [ ku] which for our model would mean that each F; contains k; vectors and W would lie in RAIx-- x- This sort of rank restriction could be used in our methods however, for simplicity, we just set kj k2 = h A
For two functions f.g let f 1 (x,y) + f())((v). This is analogous to the tensor product of 1 functions.

---

1.2 Overview of Results
The principal contribution of this paper is to analyze the advantage of incorporating rank restriction into density estimation. In Section 2.1 we precisely introduce the multi-view histogram and histogram based on the Tucker model. With these models we investigate how quickly we can let bin width h go to zero and rank & grow, in relation to the amount of data n, while still being able to control estimation error and select an estimator that nearly optimal for the allowable set. For the multi-view histogram we show that one can control estimation error so long as k/h is asymptotically dominated by n and for the Tucker histogram we need k/h + ka to be asymptotically dominated by (we are omitting logarithmic factors here for convenience). This stands in stark contrast to standard space of histogram estimators which requires 1/h² to be asymptotically dominated by We furthermore show that these estimators are universally consistent and that these rates cannot be significantly improved.
For second style of analysis provide finite-sample bounds the convergence of NNTF histogram estimators. We then construct a class of universally consistent density estimators that converge at rate / 8 on all densities that are a multi-view model with Lipschitz continuous component marginals. Note that the NNTF histogram estimators we construct do not require the target density to be an NNTF model to function well. Our estimators will select good estimator so long as there exists any NNTF histogram that approximates the target density well; so our hypothetical estimators "fail elegantly" in some sense. We further show that the standard histogram can converge at a rate w(1 Vn)) on the same class of densities. In Section we experimentally investigate the efficacy of using NNTF histograms real-world data. In lieu of the computationally intractable methods we investigated our theoretical analyses, we use an existing low-rank nonnegative Tucker factorization algorithm to fit an NNTF histogram to data. Surprisingly even this method outperforms the standard histogram estimator with very high statistical significance. Lastly we mention that this paper is an extension of [42] and contains a fair amount of overlap with that text.
1.3 Previous Work
Nonparametric density estimation has been extensively studied with the histogram estimator and KDE being some of the most well-known methods. There do exist, however, alternative methods for density estimation, e.g. the forest density estimator [24] and k-nearest neighbor density estimator [25]. The L3, L22 and L convergence of the histogram and KDE has been studied extensively [14, 904 16]. The KDE is generally regarded as the superior density estimator, with some mathematical justification [14, 35J. Numerous modifications and extensions of the KDE have been proposed including utilizing variable bandwidth [39], robust KDEs [20, 41, 44], methods for enforcing support boundary constraints [33], and supervised variant [43]. The work [46] investigated using KDEs for nonparametric mixture modeling. Finally we mention [21] that demonstrated that uniform convergence of KDE to its population estimate suffered when the intrinsic dimension of the data was lower than the ambient dimension, a phenomenon seemingly at odds with the curse of dimensionality.
For our review of NNTF models we also include general review of tensor/matrix factorizations since both can be viewed being low-rank models. In particular, for the multi-view model we have the following analogy
k
w.pr, (z1) pi. (12) .Pid (xa) ~ A 8 Vi, Ø Σ
X Vi.d
(3)
A great deal of work has gone into leveraging low-rank assumptions improve matrix estimation, particularly in the field of compressed sensing [10, 30j. The most basic version of compressed sensing is concerned with estimating a "tall" vector x from a "short" vector y - Az where A is a known "short and fat" matrix. One can recover y if it is sparse and A satisfics property known as the restricted isometry property (RIP) [47, 7]. These methods can be extended to the estimation of matrices when is low-rank matrix [30, 26, 27J. In this extension A is an order-3 tensor which acts
fn E Ō(gm) + 3E s.t. fo E O (gn log" gm) 'I, E w (g..) +
[fa/9al + oo in probability. In d-dimensional space the standard histogram can
converge slower than 1/ Vn.
3

---

as a linear operator on r and satisfies an adjusted form of RIP. RIP commonly arises from matrices and tensors whose entries are random. Because of this compressed sensing techniques are useful in settings where one wants to estimate x from random linear transforms of z. For example, in matrix completion observing the (i,j)-th entry of can represented as an inner product of with an indicator matrix Gi,j. i.e. (r.)) p. Thus the random observed indices (11, ; (82, ..... ..... can be represented as random matrices Ji diz.2:.... which are then stacked into A. Now A is a random linear operator that is applied to to represent the observation of random entries of and the methods of compressed sensing can be used to recover x. Compressed sensing has also proven useful for multivariate regression and autoregressive models [26, 27]. Such techniques don't 't appear to be extensible to histogram estimation due to the lack of a linear sampling scheme.
General matrix/tensor factorization, including nonnegative matrix/tensor factorizations, has been extensively studied despite being inherently difficult due to non-convexity. The identifiability and recovery of mixtures of product distributions was studied in [18, 38, 13). The special case of mixtures of power distributions has also been investigated [29, 45). The works [11, 5] present potential theoretical grounds for avoiding the computational difficulties of nonnegative matrix factorization. One notable approach to tensor factorization is to assume, in the tensor representation in (3), that d 2 3 and the collections of vectors Vi.j...., Ve.j are linearly independent for all j. Under this assumption we are guaranteed that the factorization (3) is unique [1, 18]. In [4] the authors present a method for recovering this factorization efficiently and demonstrate its utility for variety of tasks. This work was extended in [36] to recover a multi-view KDE satisfying an analogous linear independence assumption and theoretically analyze the estimator's ''s convergence to the true low-rank components. In [36] the authors investigate the sample complexity of their estimator but do not demonstrate that their technique has potential for improving rates for nonparametric density estimation in general. In [37] it was observed that using low-rank embeddings can improve density estimation. A multi-view histogram was investigated in [17] where the authors present an identifiability result and algorithm for recovering latent factors of the distribution. The related works [2. 3] consider a low-rank characteristic function as an approach to improving nonparametric density estimation. Though earlier works have observed that a low-rank approach improves nonparametric density estimation [37, 36. 17, 2. 3], we are the first to demonstrate this through theoretical analysis of sample complexity. Finally we note that the Tucker decomposition has been utilized in Bayesian statistics [32]. We are unaware of any literature on factoring functions in Rd + ER in Tucker-inspiree as we do in (2).
Theoretical Results
In this section we mathematically demonstrate that histogram estimators can achieve greater perfor- mance by restricting to NNTF models and using a proper procedure to select a representative from these using data. To simplify analysis we will only consider densities on the unit cube [0. 1)a and analyze the number of bins per dimension b which is the inverse of the bin width, i.e. b = 1/h. To state our results precisely we must introduce a fair amount of notation.
2.1 Notation
We will denote the L and L Lebesgue space norms via I or 2 subscript. Let Da be the set of all densities on [o, 1)a By density we mean probability measures that are absolutely continuous with respect to the d-dimensional Lebesgue measure on [o, 1) We define a probability vector or nonnegative and sum to one. Let A denote the set of probability vectors in IR' and Ta,b the set of probability tensors in R The product symbol II will always mean the standard outer product, e.g. set product" or tensor product, when the multiplicands are not real rt The natural numbers N will always denote positive integers. For any natural number b let [b] {1...., b}. We will let 1 be the indicator function and Cony be the convex hull. Later we will use projection operator where >||g; for every instance in this work this projection is unique
probability tensor to simply mean a vector tensor whose entries
Projs x - arg min
||
'R xd is the set of b x ... x b tensors. For example R x2 is the set of 6 b matrices.
times "Foo sets Si..... S. we have II S, = St x x S2 = (s1....., sa) 81 E S.ii..
For functions fi...., fa then I fi = fi Sa (01, ( Ia) + II fi (z:).

---

We will now construct the space of histograms on [0. 1)". We begin with one- mie-dimensional histograms, which will serve as the Pi,j terms in (1) or (2). We define h1,4, with i E [b] to the neeedimensional histogram where all weight is allocated to the ith bin. Formally we define this as
i (
11,4 (x) bl
Note that this is a valid density due to the leading coefficient. We use these to construct higher- dimensional histograms. For a multi-index A [b] let
A
ALD.Ac
1=1
i.e. the d-dimensional histogram with b bins per dimension whose entire density is allocated to the bin indexed by A. Finally we define Ad,b,A be the support of ha,b,A, ie. the "bins" of a histogram estimator,
A.B,A
II
d
A.
11-1-
A b
For dataset X' = Xn) in [0, 1)", the standard histogram estimator is
HaP (2) a n
Σ
habaaa (X: E Ad5,,))
AE(D)
Let Hd, A Conv (Mreesa (eo_)(()(()))))))))))))))))))) the set of all d-dimensional histograms with b bins per dimension. Let Hé be the set of histograms with at most separable components, i.e.
k
H
Pi.j E Ak, Pi.j E Hiib
(4)
We will refer to elements in this space as multi-view histograms. Elements in this space have the same form (1) in Section 1.1. Similarly we define the space of Tucker histograms be
Hi.h
Σ
Ws I
PLS.. im1
W E Ta,,,Pisj E H1.b
SE(K)
These have the same form as (2) in Section 1.1.
We emphasize that the collections of densities H and H/. are primary objects of interest this paper. The results we present are concerned with finding good density estimators restricted to these sets as k and b vary.
2.2 Estimator Theoretical Results
We present two approaches the analysis of NNTF histogram estimators. All proofs and additional results are contained in the appendix.
First provide an asymptotic analysis of NNTF histogram estimators in terms of estimation error control: how fast can we let b and le grow, with respect to n, while still controlling estimation error all densities? An advantage of this analysis is that we can demonstrate that these rates approximately optimal (up to logarithmic terms).
For our second approach present finite-sample bound analysis. In this analysis we first present a -edpedut bound that, for an estimator restricted to H& depends on n, b, and H ||p - 4 where is the data generating "target" distribution. We follow this up with distribution-fii frre bounds.
5

---

Distribution-fri -ree bounds for nonparametric density estimation require that the target distribution belong to well-behaved class of distributions (such as Sobolev or Hölder classes) enable bounding of the approximation error [40]. Our distribution-free finite-sample analysis assumes that the target density is multi-view model whose component marginals are Lipschitz continuous. We construct an estimator that converges at rate of approximately 1/ yn on this class of densities, independent of d. For comparison we show that the standard histogram estimator can converge at a rate worse than 1/ y on this same class of densities. We mention again that this estimator shouldn't fail catastrophically when these distributional assumptions aren't exactly met so long as its approximation error, minpeR5, |pp 112 isn't large. For brevity, and because the results are virtually direct analogues their multi-view histogram counterparts, we reserve all finite- sante- results for Tucker histogram for the appendix.
Main Technical Tools Our results rely on finding L s-coverings of the spaces of NNTF histograms and using Theorem 3.7 from [6] to select a good representative from that collection. The aforemen- tioned theorem is slight extension of Theorem 6.3 in [9] and is essentially proven in [48]. As was mentioned in [6]. the application of these results typically does not yield a computationally practical algorithm. Likewise our results are simply meant highlight the potential of NNTF models and are not practically implementable as is.
2.2.1 Asymptotic Error Control
The following theorem states that one control the estimation error of multi-view histograms with components and bins per dimension so long as n ~ bk (omitting logarithmic factors). Recall that 6d, so we have removed the exponential dependence of
the standard histogram estimator requires bin rate on dimensionality. Here and elsewhere the rv symbol is not a precise mathematical statement but rather signifies that the two values should be of the same order in general sense. In the following b and & are functions of n so the space of histograms changes as one acquires more data.
Theorem 2.1. For any pairs of sequences b - oc and k: - co satisfying n/(bb log(b) + & (k)) oc,
there exists an estimator Vn E HH2 such that, for all > 0
sup P ||,n pll, > 3 min llp
all +5-
- +0,
DE
TEH
where Vn, is a function of XI...., X, p
The sample complexity for the multi-view histogram is perhaps more accurately approximated as being on the order of dbk however the d disappears the asymptotic analysis. The following theorem states that one can control the error of Tucker histogram estimates so long as n bk + kd (omitting logarithmic factors).
Theorem 2.2. For any pairs of sequences b > oo and k: + oo satisfying n/ (bk log(b) + a.d log (R:5) - 00,
there exists an estimator Vn E Hig such that, for all E > 0
sup P
||Vn - pll, 3 min Il all, +0) - 0. gE
pEDx
where V, is function of X1, X, did p.
Allowing b grow aggressively as possible we achieve consistent estimation so long as n ~ b log b and & grows sufficiently slowly, regardless of dimensionality.
Corollary 2.1. For all k fix Rh to be either H',s n/ (b log b) + oi, there exists a sequence k + oo and estimator Vn, E R2i such that, for all e > 0
b or H'a 43, For any sequence b + oo with
sup P
VV, pll1 3 min 1p- all, +E + 0. yER
DEDa
#R is tixed to H. H. and doesn't change n, b, & vary.

---

where Vn a function of XI,..., , Xn sid p. where vn a function of X....., Xn, äid
p.
The following result shows that the approximation error of the estimators in Theorem 2.1, Theorem 2.2, and Corollary 2.1 go to zero for all densities. Thus these estimators are universally consistent even when the NNTF model assumption is not satisfied.
Lemma 2.1. Let p E Da- If
and co then neHt, I/p 411 + 0.
straightforward consequence of this is that the Tucker histogram approximation error also goes to zero.
Lemma 2.2. Let p E Da- Ifk + oo and + co then min Ri, |pp - 411 + O.
The next theorem shows that the rate on bk in Theorem 2.1 cannot be made significantly faster.
Theorem 2.3. Let d 2 2, b + oc, and + 2o with b 2 and n/ (bk) - O. There exists no estimator Vn E Hd, such that, for all 0, the following limit holds
sup P [1 pll,
3 min |p all +s) + HE
DEDs
Likewise the rate on bk kd can also not be significantly improved in Theorem 2.2.
Theorem 2.4. Let d 2 2, b + cc, and k + co with b 2 k and n// (bk k²) - 0. There exists no estimator Vn E Hdg, such that, for all e > O, the following limit holds
sup P PED,
[ -pl1
1p all, + gEHs.
min
where V, is a function of X1,
X,,
iid ~ p
2.2.2 Finite-Sample and Distribation-Indeeendedl Bounds
In this section we investigate the convergence multi-view histogram estimators to densities that satisfy the multi-vies view assumption. This will be done via standard bias/variance decomposition style of argument. We begin with the following distribution-depe derreutioo-deeendentt finite finite-sample bound.
Proposition 2.1. Let d, n and 0 < 8 < 1. There exists an estimator Vn E Hhi such that
2bdk log(4bd)kn)
log(3)
sup P 11p- Vnlli 3 min ||p 1/l1 +7V pEDa
+ VV
8,
De DEAE
2n
where V,, function of X.....,
idd
p
To analyze the approximation error, ||p gll1. we first consider the case where p has single component with L-Lipschitz marginals, so p I[ P.. Using the indicator function over the unit cube with Hölder's 's Inequality we have that ||p glli || (p 9) 1 S llp glla ||1 ||p gllz- is possible to show that the 1/2 projection of p onto H s is achieved by simply projecting each marginal to its best approximating one-dimensional marginal i.c. (see the appendix)
d
arg min
II
P:
9 = II Proj Pt-
gEM
Let Lip, be the set of L-Lipschitz probability density functions [0, 1] and let my & supretáp, |l The following theorem characterizes the approximation error for separable densities with Lipschitz continuous marginals.

---

Theorem 2.5. Let 82 /12 and fa. be elements of Lip,, then
d II f. Projec II fo 4,6 x=l
L
m
m
1262
We show the appendix that this decays a rate of O (b-1) and that this rate is tight. To characterize the behavior of m we have the following.
Proposition 2.2. Let mL = suppeetpy
ll then
1.2 12 +1
05L52
m
8L
L
The following theorem is finite-sample bound for well-constructed multi-view histogram estimator.
Theorem 2.6. Fix n, d E N. L 222 2, and 1 8 > 0. There exists b and an estimator Vn, E H2g such that
21dh
log(
sup P PE(
[|Vn ppl1
log (oLg3ddk + +TV
8,
T13
2n
where Q is the set of densities of the form Σ wi 11 Pig with Pij E Lip w E Do. and Vn is
a function of X XI....,
sid p.
Here analyze the asymptotic rate which the estimator in Theorem 2.6 converges to large class of multi-view models. To this end let
K
Qa
W.Pi,
X ... Pid & E N, we E Av, L' 2 0,Pi, Lipp
ie.. 12 is the space of all multi-view models whose component marginals are all Lipschitz continuous. Consider letting - xo, k co, and 8 in Theorem 2.6 arbitrarily slowly - co. For some element in Du its respective maximum Lipschitz constant and component number, L' and k', are fixed, for sufficiently large n we have L > L' and k' and the bound from Theorem 2.6 applies. From this follows that IVV, - -ll (1/ Vn)) So we can construct an estimator that converges at rate Ô (1/ for any multi-view model in 1a. independent of dimension! This rate appears to be approximately optimal since "for smooth densities, the average I error for the histogram estimate must vary least as n -1/3. ([14), p. 99). For comparison the histogram estimator's convergence rate is hindered exponentially in dimension.
Proposition 2.3. Let V. be the standard histogram estimator with n/bó + 0o. There exists E Qa such that Vn pll w11 T/)
2.3 Discussion
While Theorem 2.6 gives an estimator with good convergence, the class of densities Q is somewhat restrictive and likely not realistic for many situations where one would want to apply nonparametric density estimator. Proposition 2.1, the other hand, is not so restrictive since it depends on minge lpy - 7 411+ and more clearly conveys the message of this paper. Typical works on multi- view nonparametric density estimation assume that the target density p is multi-view model and are interested in recovering the model components Pı,j and w from (1). Similarly to how the standard histogram estimator doesn't I assume p E Ma. our work isn' meant to assume that is a multi-view model, but instead meant to explore the benefits including hyperparameter k. in addition to b, to restrict rank of the estimator. Just as the histogram can approximate any density as b -> oo, Lemmas 2.1 and 2.2 show that the inclusion of & does not hinder the approximation power of the estimator.
8

---

To explore the trade-off between b and & first observe that setting k = ba gives H Ha, since one can allocate one component each bin. Theorem 2.1 and Proposition 2.1 with 6 gives sample complexity of approximately n ~ bd+1 which coincides with standard histogram estimator. Alternatively, setting & 1 restricts the estimator to separable histograms H226. with a sample complexity of approximately maximal & corresponding to the standard histogram and minimal & corresponding to naive Bayes assumption. We observe Section 3 that this trade-off useful in practice: we virtually never want k to be maximized.
b. Thus we have span of yielding different estimators with
Experiments
The previous section proved the existence of estimators that select NNTF histograms that offer advantages over the standard histogram. Unfortunately these estimators are not computationally tractable and only demonstrate the potential benefit incorporating an NNTF model in nonparametric density estimation. It would be nonetheless interesting to observe the behavior of an NNTF histogram estimator, even if it lacks the theoretical guarantees developed in the previous section. To this end we consider an L'è-minimizing NNTF histogram estimator. For all d, b, k fix RÿJ, to be either Hÿ,
b.b or
ddh- We consider an estimator Un. that attempts to minimize
U, argmin |1 -p1
Note that
b 21 |101 -2 (p. +1111.
(5)
The llel2 term in (5) relevant when minimizing over p. Additionally for data X1, .... Xn iid the law of large numbers gives us
p
(v.0) Jo plx))(x)dx= = Ex-p lb ~ 1 EXx.)
10.1
so we may consider
Un P ard. 1P112
Σ p(x.)
(6)
practical version of (5) which conveniently equivalent nonnegative tensor factorization (see the appendix).
Risk expressions for nonparametric density estimation based on L'-minimization similar to (6) have appeared in previous works related to kernel density estimation [41, 8, 31]. Proving optimal rates on bandwidth in these settings seems challenging, however.
Table 1: Experimental Results
Datasel
Red.
Dim.
Hist, Perf.
Tucker Perf.
Hist. Bins
Tucker Bins
Tucker l
p-val.
2
-1.455+0.089
-1.50240.102
6.331 499
8.375=$1.780
4.968:1.9976 1.776
5c-4
3
2.040-10.196
2.2268::0.195
4.7811:0738
6.718:11.66
1.781+:1.440
2e-4
3.532.10.996
4.014:1..555
4.01110.585
1.34
4.375.10.695
2e:3
4.673411.022
2.744229224
3.468-10.99
4.343-10.922
3.21110-514
4e.5
MNIST
2003410.1000 100
100
6.062:11199
1.362:1
20002:
3c-5
3.086.10.207
6.843-11.227
1.699
Rand.
4
-4, 3.00
-5.711404455
3.500=+0.559
5.656+20.622
1.593=
8c-7
5
-.327220.522
3.250-1--433
4.718:00.711
2.562+1.087
8e-7
120
1221210.113
5.71811 304
1.46
1,02402222
8c-6
3
3.010-:0.364
3.606:+0400
3.593:20.860
7.0624:1.08
1,543
2c-6
PCA
4.423-10.70
3.000-10.000
5
66.39960.661
4.043+11.92
3.000++0.000
3.750=+0.968
1.84++00617
0.91
Diabetes
2
3.074::0.224
3.27744-2277
6.843::1 227
9.250:11.956
1.093:+0.384
7e-5
3
4,736
5.353-10.51
4.968 10.769
1.406
1
2e:5
6.017-10.873
-7.73211199 497
4.022-0.704
6.718 328
2.09311115 155
le-5
-8. -.9866 1.292
-12.61+2477
3.062+02242
5.093++0.221
2.53
20-6
For our experiments we used the Tensorly library [23] to perform the nonnegative Tucker decom- position [22] with Tucker rank [k, k...,, k] which was then projected to the simplex of probability

---

tensors using [12]. We also performed experiments with nonnegative PARAFAC decompositions using [34, 23]. These decompositions performed poorly. This is potentially because the PARAFAC optimization is more difficult or the additional flexibility of the Tucker decomposition was more appropriate for the experimental datasets.
3.1 Experimental Setup
Our experiments were performed on the Scikit-learn [28] datasets MNIST and Diabetes [28], with labels removed. We use the estimated risk from (6) to evaluate estimator performance (which may cause negative performance values, however lower values always indicate smaller estimated - distance). Our experiments considered estimating histograms in d 2, 3, 4, dimensional space. We consider two forms of dimensionality reduction. First we consider projecting the dataset onto its top principle components. We also performed experiments projecting each dataset onto a random subspace of dimension d. These random subspaces were constructed so that each additional dimension adds a new index without affecting the others. To do this, we first randomly select an orthonormal basis for each dataset that remains unchanged for all experiments V1, ........ Then to transform a point X dimension d we perform the following transform: Xeeuued dim. [V val" X. We consider both transforms since PCA may select dimensions where the features tend to be independent, e.g. multivariate Gaussian. After dimensionality reduction we scale and translate the data to fit in the unit cube.
With our preprocessed dataset, each experiment consisted of randomly selecting 200 samples for training and using the rest to evaluate performance (again using (6)). For the estimators we tested all combinations using I to bmax bins per dimension and A: from I to kimax. As d increased the best cross validated and value decreased, so we reduced bmax and kmax for larger d to reduce computational time, while still leaving sizable gap between the best cross validated b and i and 6max and kmax across all runs of all experiment. For d = 2.3 we have bmax = 15 and kmax = 10; for = 4 we have Ama = 12 and kimax 8; for d 5 have binax 8 and kimux 6. For parameter fitting used random subset cross validation repeated 80 times using 40 of the 200 samples to evaluate the performance of the estimator fit using the other 160 samples. Performing 80 folds of cross validation was necessary because of the high variance of the histogram's 's estimated risk. This high variance is likely due to the noncontinuous nature of the histogram estimator itself and the noncontinuity of the histogram as a function of the data, i.e. slightly moving one training sample can potentially change histogram bin in which it lies. Each experiment was run 32 times and report the mean and standard deviations of estimator performance as well as the best parameters found from cross validation. We additionally apply the two-tailed Wilcoxon signed rank test the 32 pairs of performance results to statistically determine if the mean performance between the standard histogram and our algorithm are different and report the corresponding p-value.
3.2 Results
Our results are presented in Table 1. Apart from the density estimators' performance ("Hist. Perf." and "Tucker Perf.") this table contains the mean and standard deviation over the 32 trials for the optimal cross validated parameters for the estimators. This includes the number of bins, corresponding to b from the earlier sections, and the Tucker rank k. We that the Tucker histogram usually outperforms the standard histogram ("Tucker Perf." is less than "Hist. Perf.") with high statistical significance (small p-val). As one would expect, the Tucker histogram cross validates for more bins, presumably reducing the k in exchange for more bins. Note that the MNIST PCA experiments always cross validated for the largest and yielded less statistically significant performance increases (outside of the unusual Diabetes PCA d = 5 experiment). Presumably this experiment fit the NNTF assumption the least well (hence the large k) and thus received the least benefit.
4 Conclusion
In this paper we have theoretically and experimentally demonstrated the advantages of including rank restriction into nonparametric density estimation. In particular, rank restriction may be way to overcome the curse of dimensionality since it reduces the sample complexity penalty incurred from dimensionality from exponential to linear. This paper is an initial theoretical foray for demonstrating the potential of combining rank restriction with nonparametric methods.
10

---

Acknowledgments and Disclosure of Funding
Robert A. Vandermeulen acknowledges support by the Berlin Institute for the Foundations of Learning and Data (BIFOLD) sponsored by the German Federal Ministry of Education and Research (BMBF). Antoine Ledent acknowledges support by the German Research Foundation (DFG) award KL. 2698/5- I and the Federal Ministry of Science and Education (BMBF) award 011S1805 18051A A. The authors thank Marius Kloft and Clayton Scott for useful discussions related to this work. The authors thank Nicholas D. Sidiropoulos for bringing to our attention some previous works on low-rank nonparametric density estimation.
References
[1] Elizabeth S. Allman, Catherine Matias, and John A. Rhodes. Identifiability of parameters in latent structure models with many observed variables. Ann. Statist., 37(6A):309--3132, 12 2009.
[2] Magda Amiridi, Nikos Kargas, and Nicholas D. Sidiropoulos. Low-rank Characteristic Tensor Density Estimation Part I: Foundations. arXiv e-prints, page arXiv:2008. 12315, August 2020.
[3] Magda Amiridi, Nikos Kargas, and Nicholas D. Sidiropoulos. Low-rank Characteristic Tensor Density Estimation Part II: Compression and Latent Density Estimation. arXiv e-prints, page arXiv:2106. 10591, June 2021.
[4] Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15:2773-2832, 2014.
[5] Sanjeev Arora, Rong Ge, Ravindran Kannan, and Ankur Moitra. Computing a nonnegative matrix factorization - provably. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC 12, pages 145-162, New York, NY, USA, 2012. ACM.
[6] Hassan Ashtiani, Shai Ben-David, Nicholas Harvey, Christopher Liaw, Abbas Mehrabian, and Yaniv Plan. Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 1412-34211 Curran Associates, Inc., 2018
[7] Emmanuel J Candes and Terence Tao. Reflections on compressed sensing. IEEE Information Theory Society Newsletter, 58(4):20-23, 2008
[8] Eirén Cruz Cortés and Clayton Scott. Consistent Kernel Density Estimation with Man-Vanig Bandwidth. arXiv e-prints, page 1XXiv:1705.08977 May 2017.
[9] I. Devroye and G. Lugosi. Combinatorial Methods in Density Estimation. Springer, New York, 2001.
[10] D. I.. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289- 13 1306, April 2006.
[11] David Donoho and Victoria Stodden. When does non-negative matrix factorization give correct decomposition into parts? In S. Thrun, L. K. Saul, and B. Schölkopf, editors, Advances Neural Information Processing Systems 16, pages 1141-1148 148. MIT Press, 2004.
[12] John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. Efficient projections onto the -ball for learning in high dimensions. In Proceedings of the 25th International Conference on Machine Learning, ICML. '08, page 272-279, New York, NY, USA, 2008. Association for Computing Machinery.
[13] Spencer Gordon, Bijan H Mazaheri, Yuval Rabani, and Leonard Schulman. Source identifi- cation for mixtures of product distributions. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2193-2216. PMLR, 15-19 Aug 2021.
11

---

[14] Läszlò Györfi, Luc Devroye, and Laszlo Gyorf. Nonparametric density estimation: the LI view. John Wiley & Sons, New York; Chichester, 1985.
[15] Blls-Battian Heidenreich, Anja Schindler, and Stefan Sperlich. Bandwidth selection for kernel density estimation: a review of fully automatic selectors. ASIA Advances in Statistical Analysis, 97(4))403-433, Oct 2013.
[16] Heinrich Jiang. Uniform convergence rates for kernel density estimation. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1694-1703, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
[17] Nikos Kargas and Nicholas D. Sidiropoulos. Learning mixtures of smooth product distributions: Identifiability and algorithm. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceed- ings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 388-396. PMIR, 16-18 Apr 2019.
[18) Nikos Kargas, Nicholas D. Sidiropoulos, and Xiao Fu. Tensors, learning, and "kolmogorov extension" for finite-alphabet random vectors. IEEE Transactions on Signal Processing, 66(18):4854-4868 2018
[19] Hiroyuki Kasahara and Katsumi Shimotsu. Non- kon-parametric identification and estimation of the number of components in multivariate mixtures. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76(1):97-111, 2014
[20] J. Kim and C. Scott. Robust kernel density estimation. J. Machine Learning Res., 13:2529-2565. 2012.
[21] Jisu Kim, Jaehyeok Shin, Alessandro Rinaldo, and Larry Wasserman. Uniform Convergence Rate of the Kernel Density Estimator Adaptive Intrinsic Volume Dimension. arXiv e-prints, page arXiv: 18 10.05935, Oct 2018.
[22] Yong-Deok Kim and Seungjin Choi. Nonnegative tucker decomposition. 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1-8, 2007.
[23] Jean Kossaifi, Yannis Panagakis, Anima Anandkumar, and Maja Pantic. TensorLy: Tensor Learning in Python. arXiv e-prints. page 11X.v:1610.005555, Oct 2016.
[24] Han Liu, Min Xu, Haijie Gu, Anupam Gupta, John Lafferty, and Larry Wasserman. Forest density estimation. J. Mach. Learn. Res., 12:907-951. July 2011.
[25] Y. P. Mack and M. Rosenblatt. Multivariate k-nearest neighbor density estimates. Journal of Multivariate Analysis, 911::111,, March 1979.
[26] Sahand Negahban and Martin J. Wainwright. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. Ann. Statist., 39(2) 04 2011.
[27] Sahand Negahban and Martin J. Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. Mach. Learn. Res., 13: 13:1665-1697, May 2012.
[28] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[29] Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy. Learning mixtures of arbitrary distributions over large discrete domains. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS 14, pages 207-224, New York, NY, USA, 2014. ACM.
[30] Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev., 52(3)-471-50, August 2010.
12

---

[31] Alexander Ritchie, Robert A. Vandermeulen, and Clayton Scott. Consistent estimation of identifiable nonparametric mixture models from grouped observations. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1676-11686. Curran Associates, Inc., 2020.
[32] Aaron Schein, Mingyuan Zhou, David Blei, and Hanna Wallach. Bayesian poisson tucker decomposition for learning the structure of international relations. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 28 2--1899, New York, New York, USA, 20-22 Jun 2016. PMLR.
[33]
Eugene F. Schuster. Incorporating support constraints into nonparametric estimators of densities. Communications in Statistics Theory and Methods, (4(5):1123-1133) 1985.
[34] Amnon Shashua and Tamir Hazan. Non-negative tensor factorization with applications to statistics and computer vision. Proceedings of the 22Nd International Conference on Machine Learning, ICML '05, pages 792-799, New York, NY, USA, 2005. ACM.
[35] B. W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall, London, 1986.
[36] Le Song, Animashree Anandkumar, Bo Dai, and Bo Xie. Nonparametric estimation of multi- view latent variable models. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 640-648, Bejing, China, 22-24 Jun 2014, PMLR.
[37] Le Song and Bo Dai. Robust low rank kernel embeddings of multivariate distributions. In C. J. C. Burges, L.. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[38] Behrooz Tahmasebi, Seyed Abolfazl Motahari, and Mohammad Ali Maddah-Ali. On the Identi- fiability of Finite Mixtures of Finite Product Measures. arXiv e-prints, page arXiv: 100::180.0000 .54444, July 2018
[39] George R. Terrell and David W. Scott. Variable kernel density estimation. Ann. Statist., 2063):12661125,, 09 1992.
[40] Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Publishing Company, Incorporated, 1st edition, 2008
[41] Robert Vandermeulen and Clayton Scott. Consistency of robust kernel density estimators. In Shai Shalev-Shwart. and Ingo Steinwart, editors, Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 568-591. Princeton, NJ, USA, 12-14 Jun 2013. PMLR.
[42] Robert A. Vandermeulen. Improving Nonparametric Density Estimation with Tensor Decompo- sitions. arXiv e-prints, page arXivv2010.024255 October 2020.
[43] Robert A. Vandermeulen, René Saitenmacher, and Alexander Ritchie. A proposal for supervised density estimation. In NeurlPS 2020 Workshop on Pre-registration in Machine Learning, 2020.
[44] Robert A. Vandermeulen and Clayton Scott. Robust kernel density estimation by scaling and projection in hilbert space. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 433 441. Curran Associates, Inc 2014.
[45] Robert A. Vandermeulen and Clayton D. Scott. An operator theoretic approach to nonparametric mixture models. The Annals of Statistics, 47(5):2704 2733, 2019.
[46] Leena C. Vankadara, Sebastian Bordt, Ulrike von Luxburg, and Debarghya Ghoshdastidar. Recovery guarantees for kernel-based clustering under non-parametric mixture models. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Confer- ence on Artificial Intelligence and Statistics, volume 130 Proceedings of Machine Learning Research, pages 3817-3825. PMLR. 13-15 Apr 2021.
13

---

[47] Roman Vershynin. High-DDmensional Probability: An Introduction with Applications in Data Science. Number 47 in Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
[48] Yannis G. Yatracos. Rates of Convergence of Minimum Distance Estimators and Kolmogorov's Entropy. The Annals of Statistics, 13(2):668 774, 1985.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Complete proofs in the appendix, with a few notes on general methods in main text.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
14


Reviews:
[{"review_id": "hka3tQMwXk5", "reviewer": "Reviewer_gXvQ", "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.", "questions": "", "limitations": "", "rating": 5, "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": "--- Strength:\n\n(1) The theoretical problems above are well studied in the paper. All the results are rigorously presented.\n \n(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.\n\n(3) The experiment also sheds some light on the superiority of the proposed method in some specific cases.\n\n--- Weakness:\n\n(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.\n\n(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. \n\n--- Point to improve:\n\n(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. \n\n(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.\n\n--- References:\n\nThe 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. \n\n[1] N. Ho, S. G. Walker. Multivariate smoothing via the Fourier integral theorem and Fourier kernel. Arxiv preprint Arxiv: 2012.14482, 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any foreseeable limitations and negative societal impact of this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not detect any ethical issues with the paper.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "goQqFawOT3C", "reviewer": "Reviewer_LSLp", "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^{-⅓}.$\n\n\n", "questions": "", "limitations": "", "rating": 7, "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": "Theoretical results in the manuscript are substantial. \n\nThey only prove the existence of a low-rank estimator; they do not devise such an estimator. \n\nIt is surprising that there is no $d$ in the asymptotic convergence results. I did not have time to check the proof.\n\nMinor comments, mostly typos:\n- In the paragraph below equation (3), $x$ is called a matrix, even though it is a vector\n- Page 5, just before \"Main Technical Tools\", should be $n^{-1/3}$ not $d^{-1/3}$\n- Theorem 2.6: the first line in the statement has some indexing errors in the product\n- Equation (12): sum should be until $n$, and a factor of $1/n$ is missing\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No concerns.", "review_text": "", "extra_scores": {"ethical_concerns": "No concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "c8y9nOKvv8", "reviewer": "Reviewer_JhG3", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "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.\n\n* 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).\n\n* Could the authors comment and provide the reader with some intuition about the obtained rate\n($1/\\sqrt[3]{n}$ instead of $1/\\sqrt[d]{n}$). Why should we expect a cubic root?\n\n* What would happen if we were to consider components with different degrees of smooth-ness (more general Holder classes) instead of Lipschitz?\n\n* As a follow-up question:  do you expect the obtained rates to be tight;  namely, can one construct a corresponding lower bound?\n\n* Further explain what the different columns of Table 1 correspond to.\n\n* Typos.\n    * p.1  nonparametric\n    * p.3  asymptotically\n    * p.4  entries\n    * p.7  Lipschitz", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Ma74aFL38ee", "reviewer": "Reviewer_W5MH", "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.", "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": "The approach described is novel, and the theoretical results are interesting and nontrivial.\n\nThe 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.\n\nThe paper should be much better polished.  The paper has many typos, and missing information -- some of this impedes understanding.\n“Nonparametreic” in the second sentence.\nIn section 1.3, what is “M” (i.e. “M satisfies a property”).\n“Who’s” should be “whose”\n“One can recover y”, should “y” be “x”?\n\nIn 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? \n\nWhat 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?\n\nSome sentences do not make sense grammatically. E.g. in section 3, “This problem when seems be further…”\n\nThe authors have not included line numbers, which would have been helpful for referencing certain parts of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One sentence describing no foreseen societal impacts is provided.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)