Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors discuss an application of recent work in nonnegative function estimation to the problem of density estimation.  In particular, they argue that under mild assumptions, PSD models can concisely model a large range of interesting densities and that these densities can be (more or less) efficiently learned.  The work concludes with a qualitative comparison against existing density estimation strategies.
main_review: Originality:  The work builds heavily off of [15], but there is more than enough novelty in this specific case to justify a separate work.

Quality:  1) For strictly positive densities is there a KL-divergence analog of Thm. 6 (which is a more typical error metric for densities -- though it has issues of its own)?

2) How computationally efficient really is Proposition 8?  In particular, if n is large, there are O(n^2)) integrals that need to be estimated.  The answer may just be that it depends on g, but there doesn't really seem to be any mechanism proposed here to help reduce the complexity with a large n, is there?

3)  The experiments feel very preliminary compared to a typical NeurIPS submission.  While I think the approach has a lot of merit and would be of significant interest, the limited experimental results by themselves are enough for me not to vote for acceptance. In particular, there is no quantitative comparison and no experimental comparison on real data.

Clarity: 1) There are a significant number of typos that should be corrected via a thorough proofreading.
2) The notation is a bit cumbersome in places, e.g., x for the functional dependence and x_i for the rows of the matrix X.  Consider making some notational changes to improve readability.

Significance:  Efficient density estimation techniques are of general interest.  
limitations_and_societal_impact: Appropriate.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors propose a positive semidefinite (PSD) parameterization to model probabilities, which generalizes mixture models by allowing negative weights. They demonstrate that the PSD parameterization enjoys the same computational advantages of mixture models and could approximate a wide class of target densities.
main_review: The paper is well-written and the key idea is clear. The proposed PSD parameterization is a family of nonnegative functions in the reproducing kernel Hilbert space generated by a given kernel. This provides a natural approximation to a rich class of target densities. The authors show that common operations such marginalization and integration can be easily performed in terms of the PSD model. In particular, the PSD model supports a compression operation that reduces the number of base points leveraging the Nystrom projection in reproducing kernel Hilbert space. In addition, the PSD model has the computational advantage that the exact sum and product rules can be performed efficiently. This is demonstrated in an application of the PSD parameterization to the hidden Markov model.

There are two sets of parameters in the PSD parameterization, the coefficient matrix as well as the kernel parameter. It is stated that a benefit of the PSD model involves possible negative weights, i.e., entries of the coefficient matrix. This is a bit confusing as the interpretation of the weights is different from the weights in the mixture model setting where the latter is typically interpreted as membership probabilities.

Another concern is in the parameter estimation. It seems that that only the coefficient matrix will be estimated. This could be done efficiently due to the linear structure. The kernel parameter may also need to be inferred, which could involve expensive non-convex optimization.

limitations_and_societal_impact: - Interpretation of the weights in the PSD model is not very clear to me. Is there a correspondence between PSD coefficients and the membership weights in the mixture model?
- Does the parameter estimation consider the kernel parameter?
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper is based on the positive semi-definite model from reference [15], and propose a positive semi-definite (PSD) models for probability distribution. The paper then focuses on the family of Gaussian PSD, which can be written as a sum of weighted pairwise multiplicative kernels over sample points. Most importantly, the weights do not need to be positive, and it only requires that the matrix of weights is a symmetric positive semidefinite matrix to ensure that the function is positive everywhere. The authors then show that the PSD model facilitates the sum and product rules; and as the number of sample grows large, one can use projection to compress the model. Further, the authors show the approximation capacity of the PSD model and demonstrate the usefulness of the PSD model on some simple tasks.
main_review: The theoretical contribution of this paper is solid, and I enjoy reading most parts of it. On the downside, the paper is rather dense: the appendix is 43 pages, which is rather too long for me to follow all the derivations. I believe that a journal publication may be a better fit for this paper. The paper also lacks strong empirical results to show that the PSD models outperforms other methods on decent ML-related tasks. 

Some minor comments:

- Please comment on how can solve the estimation problem (12) to get \hat{A}.
- Using a dense matrix A is cumbersome when the sample size gets large. Can we use some sparse models of A, such as Toeplitz matrix or a connectivity matrix of a graph?

limitations_and_societal_impact: not relevant
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose using the class of PSD functions in probabilistic modeling. They show that this class of functions is closed under multiplication and marginalization, and that it allows for concise approximation of a wide range of densities.
main_review: The paper is well-written. Even though I am not an expert in the topic, I could follow the exposition without major problems.

The experimental section of the paper is very limited, and seems to just serve as a light proof of concept for the ideas discussed in the paper.

That being said, the theoretical part of the paper is an interesting and relevant contribution to probabilistic modeling. The authors consider using the class of PSD functions [1] to represent probability distributions, in particular, to generalize mixture models. They first show that this class is closed under common operations, such as multiplication, marginalization, and conditioning. They also show that these operations can be performed fairly efficiently. Then, they discuss the representational power of this class, and characterize the number of "base points" required to get an $\epsilon$-approximation of a density. I think both parts are solid theoretical contributions, and the class of PSD densities seems like an interesting object to be investigated further, especially in practical applications.

I have one concern regarding the use of such models in applications that require repeated multiplication operations. Based on the discussion of section 2.2, the authors propose using a Nystrom projection after each multiplication, in order to avoid increasing the number of base points used in the representation. If this is to be done multiple times, could it potentially lead to a gradually accumulating approximation error?

&nbsp;
### References
[1] Ulysse Marteau-Ferey, Francis Bach, and Alessandro Rudi. Non-parametric models for non-negative functions. NeurIPS, 2020.
limitations_and_societal_impact: Yes.
review_title: null

Meta-review: This article considers using a positive semi-definite (PSD) construction for flexible probability models. The basic idea is to parameterize a probability density as $f(x; M, \phi) = \phi(x)^\top M \phi(x)$ where $x\mapsto\phi(x)$ is a mapping to a Hilbert space and $M$ is a positive semi-definite operator (Equation 1).  In particular, this provides a generalization of mixture models that allows negative mixture weights. The paper focuses on the special case of Gaussian PSD models, in which $\phi(x)$ is the feature map associated with the Gaussian kernel.  

This class of PSD models has some attractive properties: it is closed under multiplication (product rule, see Prop 2) and marginalization over a subset of variables (sum rule, see Prop 1).  Further, it exhibits universal consistency: it can approximate any probability density arbitrarily well; see Prop 4.  This paper builds upon recent work by Marteau-Ferey et al (2020), which showed the properties above.

The paper extends this previous work by showing that PSD models obtain the optimal rate of convergence for density approximation (similar to kernel  density estimation with positive and negative weights); see Theorem 7.  This is in contrast with the slow, sub-optimal rate exhibited by kernel density estimation using non-negative weights only. Additionally, the paper applies the PSD framework to several nontrivial applications in decision theory, classification and regression, and hidden Markov models.

The paper is well-written and clear.  The reviewers and I found the ideas to be interesting and well-developed.  The PSD framework seems potentially very useful for nonparametric modeling.

In my view, the main limitations of the paper are as follows.

1) Novelty. Since many of the results are closely related to the previous work of Marteau-Ferey et al (2020), it would be helpful for readers if the paper could more clearly delineate the novel contributions of this work.  Nonetheless, the reviewers and I found the work to contain many innovative contributions.

2) Computational complexity.  The computational cost can be large, particularly under the multiplication rule.  The article discusses using Nystrom projections as a way of mitigating this, but this is an approximation that may hinder performance.

3) Limited experiments.  The experimental results shown are compelling, but the experiments section is quite brief.  More experimental investigation would help demonstrate the utility of the methodology.

Marteau-Ferey, U., Bach, F., & Rudi, A. (2020). *Non-parametric models for non-negative functions.* arXiv preprint arXiv:2007.03926.

Decision: Accept (Poster)