PSD Representations for Effective Probability Models
Authors: Alessandro Rudi
Carlo Ciliberto
Venue: NeurIPS 2021 Poster (2021)
Keywords: Kernel methods
Statistical Learning Theory
Positive Definite Models
Probabilistic Inference
Bayesian Inference
Decision Theory
Density Estimation
Probability Representation

Abstract: Finding a good way to model probability densities is key to probabilistic inference. An ideal model should be able to concisely approximate any probability while being also compatible with two main operations: multiplications of two models (product rule) and marginalization with respect to a subset of the random variables (sum rule). In this work, we show that a recently proposed class of positive semi-definite (PSD) models for non-negative functions is particularly suited to this end. In particular, we characterize both approximation and generalization capabilities of PSD models, showing that they enjoy strong theoretical guarantees. Moreover, we show that we can perform efficiently both sum and product rule in closed form via matrix operations, enjoying the same versatility of mixture models. Our results open the way to applications of PSD models to density estimation, decision theory, and inference.

PSD Representations for Effective Probability Models
Alessandro Rudi
Carlo Ciliberto
Inria, Ecole normale supérieure,
Department Computer Science University College London, London, UK c.ciliberto@ucl. ac.
CNRS, PSL. Research University, Paris, France alessandro. rudi fr
Abstract
Finding good way model probability densities is key to probabilistic inference. An ideal model should be able to concisely approximate any probability while being also compatible with two main operations: multiplications of two models (product rule) and marginalization with respect to a subset of the random variables (sum rule). In this work, show that recently proposed class of positive semi- definite (PSD) models for non-negative functions is particularly suited to this end. In particular, of PSD models, showing that they enjoy strong theoretical guarantees. Moreover, we show that we can perform efficiently both sum and product rule in closed form via matrix operations, enjoying the same versatility of mixture models. Our results open the way to applications PSD models density estimation, decision theory and inference.
characterize both approximation and generalization capabilities
Introduction
Modeling probability distributions is a key task for many applications in machine learning [17, 5]. To this end, several strategies have been proposed in the literature, such as adopting mixture models (e.g. Gaussian mixtures) [5], exponential models [32], implicit generative models [11, 13] kernel (conditional) mean embeddings [16]. An ideal probabilistic model should have two main features: i) efficiently perform key operations for probabilistic inference, such
rule (i.e. marginalization) and product rule [5] and, ix) concisely approximate a large class of probabilities. Finding models that satisfy these conditions challenging and current methods tend to tackle only of the two. Exponential and implicit generative models have typically strong approximation properties (see e.g. [32, 29]) but cannot easily perform operations such marginalization. On the contrary, mixture models are designed to efficient integrate and multiply probabilities, but tend to require large number of components approximate complicated distributions.
In principle. mixture models would offer an appealing strategy to model probability densities since they allow for efficient computations when performing key operations such as and product rule. However, these advantages in terms of computations, come as a disadvantage in terms of expres- siveness; even though mixture models universal approximators (namely they can approximate arbitrarily well any probability density), they require a significant number n of observations and of components do that. Indeed is known that models that are non-negative mixtures of non-negative components lead to learning rates that suffer from the curse of dimensionality. For example, when approximating probabilities nents has rates slow 2/(4+dd) (see, e.g. [38, page 100]), and cannot improve with the regularity (smoothness) of the target probability (see e.g. [9, Thm. 16.1] for impossibility results the one dimensional case).
Rd kernel density estimation (KDE) [21] with non-negative compo-
In the past decades, this limitation has been overcome by removing either the non-negativity of the weights of the mixture (leading to RBF networks [27][35]), or the non-negativity of the components
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Sum Rule
Product Rule
Concise Approximation
Optimal Learning
Efficient Sampling
Non-negative
Linear Models
x
Mean Embeddings
X
V
x
Mixture Models
X
v
Exponential Models
V
X
PSD Models
V
V
/
(see [14])
(Prop. 1)
(Prop. 2)
(Thm. 6)
(Thm. 7)
(see [15])
Table I: Summary of the main desirable properties for a probability model.
used in the mixture (leading to KDE with oscillating kernel [35]), or both. On the positive side this allows to achieve a learning rate of n n=9/(22+4) for ß-times differentiable densities on Rd. Note that such rate is minimax optimal [10] and overcomes the curse of dimensionality when 33 2 d. O(n//9) centers are necessary to achieve the optimal rate [36]. However, on the negative side, the resulting model is not a probability, since it may attain negative values, and so it cannot be used where proper probability is required.
Additionally the resulting model is very concise, since only
In this paper, we show that the positive semidefinite (PSD) models, recently proposed in [14], offer a way out of this dichotomy. By construction PSD models generalize mixture models by allowing also for negative weights, while still guaranteeing that the resulting function is non-negative everywhere. Here, we prove that they get the best of both worlds: expressivity (optimal learning and approximation rates with concise models) and flexibility (exact and efficient sum and product rulc).
Contributions. The main contributions of this paper are:
i) Showing that PSD models can perform exact sum and product rules in terms of efficient matrix operations (Sec. 2.1).
ii) Characterizing the approximation and learning properties of PSD models with respect to large family of probability densities (Sec. 3).
iii) Providing a "compression" method to control the number of components of a PSD model (introduced in Sec. 2.2 and analyzed in Sec. 3.3).
iv) Discussing a number of possible applications of PSD models (Sec. 4).
Summary of the results. Table I summarizes all the desirable properties that probability model should have and which of them are satisfied by state-of-the estimators. Among these we have: non-negativity, the model should be point-wise non-negative; sum and product rule, the model should allow for efficient computation of such operations between probabilities; concise approximation, a model with the optimal number of components m O(e-d/() enough to approximate with error neg-negative function in a wide family of smooth 8-times differentiable functions [36]; optimal learning, the model achieves optimal learning rates of order n (/(24++) when learning the unknown target probability from i.i.d. samples [35]; efficient sampling the model allows extract i.i.d. samples without incurring in the curse of dimensionality in terms of computational complexity. We note that for PSD models, this last property has been recently investigated in [15]. We consider under the umbrella of linear models all the models which corresponds to a mixture ΣØ= W1J5 (x:) of functions or fj 2 0, Vj = 1, ... or both. We denote
fa X + R. with either W/ 2 O, Vj= = 1,.... by mixture models the mixture models defined as above, where w, 2 0, ; 2 O, Vj = I,.... m. By mean embeddings, we denote the kernel mean embedding estimator framework from [30] see also [16)). With exponential models we refer to models of the form exp(E,=1 (xx)) with my E RR X - IR [32]. With PSD models we refer to the framework introduced in [14] and studied in this paper. We note that this work contributes in showing that the latter the only probability models to satisfy all requirements (we recall that non-negativity and efficient sampling have been shown respectively in [14] and [15]).
Notation.
We denote by Rd the space vectors in Id with positive entries, Raxd the space of x d matrices, S (IR") the space of positive semidefinite n x n matrices. Given vector
gd we denote diag(n) E pdxd the diagonal matrix associated to n, We denote by A o B
m

---

and A @ B respectively the entry-wise and Kronecker product between two matrices A and B. We denote by ||A||r,||
vec(A) and A respectively the Frobenius norm, the operator norm (i.e. maximum singular value), the determinant, the (column-wise) vectorization of matrix and the (conjugate) transpose of A. With some abuse of notation, where clear from context we write element-wise products and division of vectors v I as ue, u/v. Given two matrices X E [Rxxdi, Y E Rnxdaa with same number of rows, we denote by [X, Y] E [ex((d+dd)) their concatenation row-wise. The term 1, E Re denotes the vector with all entries equal to 1.
2 PSD Models
Following [14], in this work we consider the family of positive semi-definite (PSD) models, namely non-negative functions parametrized by feature map X H from input space X' suitable feature space H (a separable Hilbert space e.g. IR') and linear operator M E S+ (H), of the form
f(x; M, Φ) o(x) T ((z).
(1)
PSD models offer a general way to parametrize non-negative functions (since M is positive semidef- inite, f(a; M, () 2 0 for any E X) and enjoy several additional appealing properties dis- cussed in the following. In this work, we will focus on a special family of models of the form (I) to parametrize probability densities over X R.. In particular, we will consider the case where: i) On IR + Hy is a feature map associated to the Gaussian kernel [26] (x), 0,(x)) (,(r) = =--(=-=)) diag(n))==s), with 1) E IR and, ii) the operator M lives in the span of ((11)..... 6(In) for a given set of points (r,)ī=1- namely there exists A E S such that M = -eg (g0(2,)((zz) We define Gaussian PSD model by specializing the definition in (1) as
n
f(z; A,X,))
Σ 1,1=1
E
(2)
in terms of the coefficient matrix E Sh, the base points matrix X E Raxd whose i-th row corresponds to the point 2; for each i = 1, I....,7 and kernel parameter 1). In the following, given two base point matrices X E Rnd and X' RRmid, we denote by Kx.x',, E RR= the kernel matrix with entries (K) = (x,, x²)) where æ;, are the i-th and j-th rows of X, X' respectively. When clear from context, in the following we will refer to Gaussian PSD models as PSD models.
Remark (PSD models generalize Mixture models). Mixture models (a mixture of Gaussian distributions) are a special case of PSD models. Let A diag(a) be diagonal matrix of positive weights a E R7+. We have f(z; n, = Σm= Askn//((I,; Ei= (,kn( x).
Remark 2 (PSD models allow negative weights). From (2), we immediately see that PSD models generalize mixture models by allowing also for negative weights: e.g., f(:: A, X. 17) with A (1, 2 1 32, = X,X = (I1: and x1 = 0, = 2, corresponding to f(x; A,), =
22
e 2(=-2)² -e- Lee. mixture of Gaussians with also negative weights.
2.1 Operations with PSD models
In Sec. 3 we will show that PSD models can approximate wide class of probability densities, significantly outperforming mixture models. Here we show that this improvement does not come at the expenses of computations. In particular, we show that PSD models enjoy the same flexibility of mixture models: &) they are closed with respect to key operations such as marginalization and multiplication and ii) these operations can be performed efficiently in terms of matrix sums/products. The derivation of the results reported in the following is provided in Appendix F. They follow from well-known properties of the Gaussian function.
Evaluation. Evaluating a PSD model in a point xo E corresponds to f(" = zo; X,X, = KT. AK AKx.00.0 Moreover, partially evaluating PSD in one variable yields x
fa y= = yo: A, (X,Y), (0),)))) = f(x; B,X,)) with B= A o (Ky.un. KJ m- (3)
Note that f(x; B, B,X,m) is still PSD model since B is positive semidefinite.
3

---

Sum Rule (Marginalization and Integration). The integral of a PSD model can be computed as with
| A, A, dr = C2n Tr(A xx
On = (0,(0, dr,
(4)
where Cy = Td/2 det (diaa(()) (1)) -1/2. This is particularly useful to model probabiliy densities with PSD models. Let - (xx X, 17)dr, then the function f(x; A/Z, X,)) = z X,X,)) is a probability density. Integrating only one variable of PSD model we obtain the sum rule.
Proposition (Sum Rule- Marginalization), Let X E Raxd, Y Faxdd, E (R.)) and n E Rd 44+,0/ n/ E 4- Then, the following integral a PSD model
f flzyy; (I. de f(y: B,Y,n),
with
B= B= A K x
(5)
The result above shows that we can efficiently marginalize a PSD model with respect to one variable by means of entry-wise multiplication between two matrices.
Remark 3 (Integration and marginalization on the hypercube). The integrals in (4) and (5) can be performed also when X' is hypercube H II [ar, by] rather than the entire space R.. This leads to a closed form, where the matrix K Xx.x. # is replaced by a suitable Kx.x.4 4 that can be computed with same number of operations (the full form of such matrix is reported in Appendix F).
Product Rule (Multiplication). Multiplying two probabilities is key to several applications in probabilistic inference [5]. The family of PSD models is closed with respect to this operation. Proposition 2 (Multiplication). Let X E Raxd, Y Raxd2, Y' gaxdd, Z E maxds A E s4. B E 8T and 7n E R4 12, v/ E R E Rd4. Then
f(z.V; U: [x, Y1. (m, 12) ff) B. Y Z1, (12. ns)) = f(z v. C, C.W.
(6)
is PSD model, where C = (A @ B) (vec( v, np vee Kv. RT) with îoz = 92% base
72
matrix W = [ & 1mp
Tt +
x 1m
m 1, X Y', 1, X / and = (m m2 + T/2 na)
We note that, despite the heavy notation, multiplying two PSD is performed via simple operations such as tensor and entry-wise product between matrices. particular, we note that X @ 1mm E Ramxd and 1, & Z E Ramxd xds correspond respectively to the nm x d1 mm-tixx containing m copies of each row of X and the nm x dg-maarix containing n copies of Z. Finally, 12 @ 1m, + 1/ I @ Y the nm x d2 base point matrix containing all possible sums (184 + 1/ //))).j=1 of points from Y and Y'.
n.tm
Reduction. As observed above, when performing operations with PSD models, the resulting base point matrix might be of the form X @ 1m (e.g. if couple the multiplication in (6) with marginalization as in a Markov transition, see the corollary below). In these cases we can reduce the PSD model to have only base points (rather than nm), as follows
f(x: A, X Im: 11) f(x; B,
with
B = -I, o AI,,, & 1m),
where STm and In e R= is the n identity matrix. The reduction operation is useful to avoid the dimensionality of the PSD model grow unnecessarily. This is for instance the case of Markov transition.
Corollary (Markov Transition). Let X Raxdi Y E Ruxds Y' E Rmxd2 A ST B E Be
and 1j E R + 12, 1/2 E 144 Then
J [C..:: A, (2,, B,Y", (1) dy = f(x: C,X.m).
(8)
with C' E 84 obtained by applying in order. Prop. 2, Prop. I and reduction (7).
We remark that the result of a Markov transition retains the same base point matrix X and parameters 7) of the transition kernel. This is thanks to the reduction operation in (7), which avoids the resulting matrix C to be nm x nm. This fact particularly useful in applications that require multiple Markoy transitions, such as in hidden Markov models (see also Sec. 4).

---

2.2 Compression of a PSD model
From Prop. we note that the multiplication operation can rapidly yield a large number of base points and thus incur in high computational complexity in some settings. It might therefore be useful to have a method reduce the number of base points while retaining essentially the same model. To this purpose, here we propose a dimensionality reduction strategy. In particular, given set of points $1...., 3mm E RRd we leverage the representation of the PSD model in terms of reproducing kernel Hilbert spaces [3] to use powerful sketching techniques as Nyström projection (see, e.g.. [40]), to project the PSD model on new PSD model now based only on the new points. Given E $4, X RTxd -7 R4+. Let X E R be the base point matrix whose j-rows corresponds to the point Zy. The compression of f(:; A, X, 1)) corresponds to
f(;; n,)
with Á = BAB E EST
B B=
K XxxX, X,8,1 X
E R R
which it is still a PSD model since the matrix BAB ST. We not that even with a rather simple strategy to choose the new base points .1..... 7mm such as uniform sampling compression is an effective tool to reduce the computational complexity of costly operations. particular, in Sec. 3.3 we show that a compressed model with only Ott volylog( (1/E)) centers (instead of t²) can e-approximate the product of two PSD models with points each.
3 Representation power of PSD models
In this section we study the theoretical properties of Gaussian PSD models. We start by showing that they admit concise approximations of the target density (in the sense discussed the introduction to this paper and of Table 1). We then proceed to studying the setting in which we aim to learn an unknown probability from i.i.d. samples. We conclude the section by characterizing the approximation properties of the compression operation introduced in Sec. 2.2.
3.1 Approximation properties of Gaussian PSD models
We start the section recalling that Gaussian PSD models are universal approximators for probability densities. In particular, the following result restates [Thm. 2 14] for the case of probabilities. Proposition 4 (Universal consistency - Thm. 2 in [14]). The Gaussian PSD family is universal approximator for probabilities that admit a density.
The result above is not surprising since Gaussian PSD models generalize classical Gaussian mixtures (see Remark 1), which are known be universal [5]. We now introduce mild assumption that will enable us to complement Prop. 4 with approximation and learning results. In the rest of the section we assume that X (-1, 1)d (or more generally an open bounded subset of I2 with Lipschitz boundary). Here L (X') and (x) denote respectively the space of essentially bounded and cuuare-ittegrable functions over X, while W (X) denotes the Sobolev space of functions whose weak derivatives up to order 33 are square- intterabete on X' (see [1] or Appendix A for more details).
Assumption 1. Let B > 0, q E N. There exists fI....,Jo E W ( (2),, such that the density p X - TR. satisfies
p(x)= = Σ (a)²
Ve E..
(10)
The assumption above is quite general and satisfied by wide family of probabilities, discussed in the following proposition. The proof is reported in Appendix D.1 Proposition 5 (Generality of Assumption 1). The assumption above is satisfied by
(a) any probability density p E W:O (2) (X) and strictly positive on [-1, [|4,
(b) any exponential model p(x) = e with E W (2') n L (X')
(c) any mixture model of Gaussians or, more generally, of exponential models from (b), (d) any p that is 3 + 2-times differentiable on 1-1, 11d, with a finite set of zeros, all in (-1, and with positive definite Hessian in each zero. E.g. p(x) x =22
5

---

Moreover if p is 8-times differentiable over 1-1, 11", then it belongs to (2))
We note that in principle the class Cs w (2e) n (X)) is larger than the Nikolskii class usually considered in density estimation [10] when 3 E N, but Assumption I imposes a restriction on However, Prop. 5 shows that the restriction imposed by Assumption 1 is quite mild, since it the resulting space includes all probabilities that are B-times differentiable and strictly positive (it also contains probabilities that are not strictly positive but have some zeros, see (24]). We can now proceed to the main result of this work, which characterizes the approximation capabilities of PSD models.
Theorem 6 (Conciseness of PSD Approximation), Let p satisfy Assumption I. Let > O. There exists a Gaussian PSD model of dimension m E N, i.e., (x) = f(x; Am, Xmy ha)) with Am E S and Xm E I mxd and Mm E IR+ such that
lp Pm [x((x) S, with m m= 4/8 (log 2).
(11)
The proof of Thm. 6 is reported in Appendix D.3. According to the result, the number of base points needed for a PSD model to approximate a density up to precision depends on its smoothness (the smoother the better) and matches the bound m = ed//3 that is optimal for function interpolation [18], corresponding to models allowing for negative weights, and is also optimal for convex combinations of oscillating kernels [36].
3.2 Learning a density with PSD models
In this section we study the capabilities of PSD models to estimate a density from n samples. Let X 1)) and let p be probability on X. Denote by Fi....; In the samples independently and identically distributed according to p. with n E N. We consider a Gaussian PSD estimator Pn,m = f(x; A, A,X.n that is built on top of m additional points Tj.... Em. sampled independenly and uniformly at random in X. In particular, 7) E RQ4,, X E mmxd is the base point matrix whose j-th row corresponds to the point ãg and Å E 8 is trained as follows
/ f(x; A,X,n) - 2 Σ f(r:: A,X,,) + NIKK4A
Å = argmin AEST
(12)
where K = Kx X Note that the functional is constituted by two parts. The first two elements are an empirical version of |lf 2 modulo constant independent of (and so not affecting the optimization problem), since x; are identically distributed according to and so E R (x)))(x))d The last term is a regularizer and corresponds to i.c. the Frobenius norm of M = mm Ar On (āz)),, (ã,)) The problem in (12) corresponds to quadratic problem with semidefinite constraint and can be solved using techniques such as Newton method [24] first order dual methods [14]. We are now ready state our result.
TrK,
Theorem 7. Let n, m E E 0, E TR4 and p be a density satisfying Assumption I. With the definitions above, let Pa,m be the model Pn,m (x) fxx; Å, X, n). with Å the minimizer of (12).
Let 1 = L and X 23 2d 2544 When m 2 C'n (log n) log(("
(" nmmologg)) n)), the following
holds with probability at least 6,
ll - (m..mlLL((X) S On I [logn)442
(13)
where constant C depends only on B, d and p and the constants C²,C" C" depend only on B, d.
The proof of Thm. 7 is reported in Appendix E.2. The theorem guarantees that under Assump- tion 1, Gaussian PSD models can achieve the rate OOn-OO((nnnn///)000 -/((28+))) that is optimal for the 3-times differentiable densities - while admitting a concise representation. Indeed, it needs number m ((24/(28+)) of base points, matching the optimal rate in [36]. When B d, a model with m- 133 centers achieves optimal learning rates.
3.3 The Effect of compression
We have seen in the previous section that Gaussian PSD models achieve the optimal learning rates, with concise models. However, we have seen in the operations section that multiplying two PSD

---

models of m centers leads to PSD model with m² centers. Here we study the effect of compression, show that it possible to obtain an E-approximation of the product via compressed model with (m polylog(1/s)) centers. In the following theorem we analyze the effect in terms of the 7 distance on a domain [-1, induced by the compression, when using points taken independently and uniformly at random from the same domain.
Let A E S X E R2xd, 17 E IR4++ we want to study the compressibility of the PSD model p(æ) = f(z; n,). Let X E R.mxd be the base point matrix whose j-rows corresponds to the point J; with T1,... F.m be sampled independently and uniformly at random from [-1, 1J Denote
by (2) the PSD model (x) = f(z; A, X,,)) where À is the compression of A via (9). We have the following theorem.
Theorem 8 (Compression of Gaussian PSD models). Let 8 (0, 1}, no max(1, m Tc)- When m satisfies
m 2 0 ((1
422 log =
d L googg11gg log 1ogg))
(14)
then the following holds with probability at least 6,
(p(x) - Pm (x)] S 8² +=v=v((())
Vo [-1,1,,
(15)
The proof of the theorem above is in Appendix C.I. To understand its relevance, let Pí be a PSD model trained via (12) on points sampled from pr and îa trained from n points sampled from
P2. where both Pl, P2 satisfy Assumption I for the same |3 and m, 7, are chosen as Thm. 7, in particular m = n d2(++4) and 7 = 7,,d, 77 = 22/(24+d) Consider the model ý = P1 P22 By construction p has m² = n 22 centers, since it is the pointwise product of p1. Pa (see Prop. 2) and approximates P1 P2 with error & = n (224(24+d) polylog(n), since both fr, P2 are e-approximators of P1, Instead, by compressing p. we obtain an estimator p. that according to Thm. 8, achieves error & with a number of center
m' = On polylog(1/E) = Onn polylog(1/E)) = Om (olyloogg(()))
(16)
Then approximates p1 PP at the optimal rate n -9/(20+)) but with number of centers m' that is only Omm polylog(n)). instead of m² This means that p is essentially as good as if we learned from samples taken directly from p1 P2. This renders compression a suitable method to reduce the computational complexity of costly inference operations as the product rule.
Applications
PSD models are strong candidate in a variety of probabilistic settings. On the one hand, they computationally amenable to performing key operations such as sum and product rules, similarly to mixture models (Sec. 2.1). On the other hand, they are remarkably flexible and approximate/learm (coincisely) a wide family of target probability densities (Sec. 3). Building on these properties, in this section we consider different possible applications of PSD models in practice.
4.1 PSD Models for Decision Theory
Decision theory problems (see e.g. [5] and references therein) can be formulated as a minimization
0. argmin L(0) = Ez-p 2(),x)),
(17)
where é is a loss function, θ is the space of target parameters (decisions) and is the underlying data distribution. When we can sample directly from p - e.g. in supervised or unsupervised learning settings we can apply methods such as stochastic gradient descent to efficently solve (17). However, in many applications, sampling from p is challenging or computationally unfeasible. This for instance the case when p has been obtained via inference (e.g. it is the t-th estimate in hidden Markov model, see Sec, 4.3) or fully known but has a highly complex form (e.g. the dynamics of physical system). In contexts where sampling cannot be performed efficiently, it is advisable to consider alternative approaches. Here we propose a strategy to tackle (17) when p can be modeled (or well-approximatee) by PSD model. Our method hinges on the following result.
7

---

Proposition 9. Let p(z) - f(x; 1,), with X E Raxd, A E S 17 E B4 Let g R - R
and define (g.((2) = [[ -11===1? dx for any E R. Then Eap g(x) = (A G)
with
Gyy 2n
(18)
Thanks to Prop. 9 we can readily compute several quantities related to PSD model such as its mean [x][2] = b with b = (A o Kx Kx,n/2)1n its covariance or its characteristic function (see Appendix F for the explicit formulas and derivations). However, the result above is particularly useful to tackle the minimization in (17). In particular, since (L( = Expp Vel(0, x), we can use Prop. 9 to directly compute the gradient of the objective function: it is sufficient to know how to evaluate (or approximate) the integral (z) Then, we can use first order optimization methods, such as gradient descent, to efficiently solve (17). Remarkably, this approach works well also when we approximate p with a PSD model p. If is convex, since ş is non-negative, the resulting [(() Er E(0,, x)) is still convex functional (see also the discussion on structured prediction in Sec. 4.2). This is not the case if we use more general estimators of p that do not preserve non-negativity.
I Vol(O, ar) -=/======= dx for any 0 θ and z E IRd
4.2 PSD Models for Estimating Conditional Probabilities
In supervised learning settings, one is typically interested in solving decision problems of the form mingge ()) ((hp(1)).)) y) where p is probability over the joint input-output space X' y and he : X' + 3' is a function parameterized by 0. It is well-known [see c.g. 34] that the ideal solution of this problem is the 0, such that for any x E X' the function heg (z) = argminggg yyrpp(((=) f(z, y) is the minimizer with respect to 2 ) of the conditional expectation of f(z. y) given æ. This leads to target functions that capture specific properties of p. such as moments. For instance, when & is the squared loss, he_ (x) = Byy-p-l-e) corresponds to the conditional expectation of y given x, while for é the absolute value loss, ho. recovers the conditional median of p-
In several applications, associating input to a single quantity he(x)) in output is not necessarily ideal. For instance, when p(y]z) is multi-modal, estimating the mean or median might not yield useful predictions for the given task. Moreover, estimators of the form he require access to the full input x to return a prediction, and therefore cannot be used when some features are missing (e.g. due to data corruption). In these contexts, alternative viable strategy is to directly model the conditional probability. When using PSD models, conditional estimation can be performed in two steps, by first modeling the joint distribution p(y, x) f ii; A, [Y, X], (7, n/)) (e.g. by learning it as suggested Sec. 3) and then use the operations in Sec. 2.1 to condition it with respect to vp E
X as
p(y(=a) ply, mo) = f(y; B,Y,)) with B = p(
A o (K (Kx,5o.v KJ x..ooo)))
(19)
C24 (T o (Kx,zon KJ X Ky,y,)
In case data corruption, it is sufficient to first marginalize p(y, xr) on the missing variables and then apply (19). Below we discuss a few applications of the conditional estimator.
Conditional Expectation. Conditional mean embeddings [31] are a well-established tool to effi- ciently compute the conditional expectation (yr=p(((zg) g(v) of a function y - R. However, although they enjoy good approximation properties [16]. they to not guarntee the resulting estimator to take only non-negative values. In contrast, when is a PSD model (or an approximation), we can apply Prop. to p(- in (19) and evaluate the conditional expectation of any g for which we know how to compute (or approximate) the integral (g.n(2) = ggly)e-nlla=s)) -ills=lll? dy. In particular we have Eyyp((1a) l)) g(v) Tr[(B GY) with B as in (19) and G the matrix with entries
Gi = Cg ( ). Remarkably, differently from conditional mean embeddings estimators, this strategy allows us compute the conditional expectations also of functions g not in Hyy
Structured Prediction. Structured prediction identifies supervised learning problems where the output space y has complex structures so that it is challenging to find good parametrizations for he : X + ) [4, 19]. In [7], a strategy was proposed to tackle these settings by first learning an approximation 02 x) ~ Ea)
l(2, v) and then model hz(x)) argmin Via (2,22.). However, the resulting function (-0(-,27 2)) is not guaranteed to be convex, even when é is convex. In contrast, by combining the conditional PSD estimator in (19) with the reasoning Sec. 4.1, we have a strategy that overcomes this issue: when p(- (z) is PSD model approximating p, we can compute its gradient
8

---

Algorithm PSD Hidden Markov Model
Input:
Transition 2( = 2 B, 4 X]. 1)), initial p(2o) = f( Ao, No. and
observation (yy x) f2, C, (Moba r')) distributions. X in Prop. 10. 4+ +7+
nbv +n=
X X 2 1um
+ , 1n @ &X,
and 17
n' 4444
For any new observation ye:
C
B, = [B @ A 0 NY.
// Partial evaluation (x(x+) wyy = yt, xx+) // Product (x(x,,)) = f(x+ 2) p)) (v::e-1)
(x,0(K
Dr = (In @ 1mm (B. K & .g (Tn @ lum)
// Marginalization (((x+) = f 3: (x+, x) do
E. = (Ci @ Di) o (vec(K, X1 x .3 )vec (K
X 11.11. xxx))))))
// Product (x(x+) = (x (2r (x(x4) // Normaizztiion p(x+/vr.)) J *
A. Ec/cs, with +2( Tr B.K
8.8, stot
Return f(a;; A., X,n + 114)
By-p(-la)) V V=l(2, By-p((la) ((,y) y) is also convex, and we can use methods such as gradient descent to find h(x) exactly,
y) as mentioned in Sec. 4.1 using Prop. 9. Moreover, E(: y) is convex, the term
Mode Estimation. When the output distribution p(y (ar) is multimodal, having access to an explicit form for the conditional density can be useful to estimate its modes. This problem is typically non-convex, yet, when the output y belongs to a small dimensional space (e.g. in classification or vallud regression settings), efficient approximations exist (e.g. bisection).
4.3 Inference on Hidden Markoy Models
We consider the problem of performing inference on hidden Markov models (HMM) using PSD models. Let (æt)teN and (ye keN denote two sequences of states and observations respectively. For each t 2 1, we denote by Toa = To...., It and V1: = V1....: Ve and we assume that p(zs T0: (/:--11))))))))))))))))))))))(
22-1 and p(3 To.., V1:111) = p(yolz,) w(t,, 22) with T X x X - R and w : y x X R, respectively the transition and observation functions.
p( -1)
Our goal is to infer the distribution of possible states da at time I, given all the observations yı.r and probability p(rn) on the possible initial states. We focus on this goal for simplicity, but other forms of inferences assume that the transition and observation functions can be well approximated by PSD models f and w (c.g. by learning them or known a-priori for the problem's 's dynamics). Then, given a PSD model estimate ((xa) of the initial state p(za), we can recursively define the sequence of estimates
possible (c.g. estimating Im+te namely
steps into the future the past). We
+ f(ve, xz) w(2,, T2- =1 (1tr)))))((//_---)) dx:-1
p(a.)ye1) J J x ( -t-1 11-1)) 11:1-1) da
(20)
Note that when i, à. p(aro) correspond to the real transition, observation and initial state probability, the formula above yields the exact distribution p( (y::e) over the states at time / (this follows directly by subsequent applications of Bayes' rule. See also e.g. [5]). If i, a. p(rr) are PSD models, then each the ((xr1 is a PSD model recursively defined only in terms of the previous estimate and the operations introduced in Sec. 2.1. In particular, we have the following result.
Proposition 10 (PSD Hidden Markov Models (HMM)). Let Xo Ro X_, E Ruxd, X' Rmmdd Y E mm Ao E 8% A ST. B ST and no: 1) n, 1/4 E BR4 Moos E IRd Let
f(x4,2) = (x4, F; B, [X 1IX..XI X1, ())))))
w(y,z) = fly.:; C, CYYY,), (Nots: 1')), (21)
be approximate transition and observation functions. Then, given the initial state probability p(x)) = f(xo Ag, Xa, no). for any 2 1, the estimate p in (20) is PSD model of the form
D(z,lue.) = f(xe; Ar, n + n+);
(22)
where X = n' X' 8'60 8744
20 In
7+ +++ 1m @ X+ and A, is recursively obtained from Ar- as in Alg. I.

---

Remark 4 (Sum-produus product Algorithm). Eq. (20) is an instance of the so-called sum- cun-product algorithm. a standard inference method for graphical models [5] (of which HMMs are a special case). The application of the sum-product algorithm relies mainly on sum and product rules for probabilities (as the case for HMMs (20)). Hence, according to Sec. 2.1, is highly compatible with PSD models.
5 Discussion
In this work we have shown that PSD models are strong candidate in practical application related to probabilistic inference. They satisfy both requirements for an ideal probabilistic model: i) they perform exact sum and product rule in terms of efficient matrix operations: ii) we proved that they can concisely approximate wide range of probabilities.
Future Directions. We identify three main directions for future work: a) when performing inference on large graphical models (see Remark 4) the multiplication of PSD models might lead to inflation in the number of base points. Building on our compression strategy, we plan to further investigate low-rank approximations to mitigate this issue. ii) An interesting problem is to understand how to efficiently sample from a PSD model. A first answer to this open question was recently given in [15]. iii) The current paper has purely theoretical and algorithmic focus. In the future, we plan to investigate the empirical behavior of PSD) models on the applications introduced in Sec. 4. Related to this, we plan to develop a library for operations with PSD models and make available to the community.
Acknowledgments. A.R. acknowleges the support of the French government under management of Agence Nationale de la Recherche as part of the "Investissements d' avvveii"" program, reference (PRAIRIE 3IA Institute) and the support of the European Research Coun- cil (grant REAL 947908). C.C. acknowledges the support of the Royal Society (grant SPREM RGS (21111))1114)) and Amazon.com com Inc. (Amazon Research Award ARA 2020)
References
[1] Robert A Adams and John JF Fournier. Sobolev spaces. Elsevier, 2003.
[2] Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Weed. Massively scalable sinkhorn distances via the nyström method. arXiv preprint 1rXivv1812.055 2018
[3] Nachman Aronszajn. Theory of reproducing kernels. Transactions of the American Mathemati- cal Society, 68(3):337-404, 1950.
[4] G. H. Bakir, T. Hofmann, B. Schölkopf, A. J. Smola, B. Taskar, and S. V. N. Vishwanathan. Predicting Structured Data. MIT Press, 2007.
[5] Christopher M Bishop. Machine learning and pattern recognition. Information Science and Statistics. Springer, Heidelberg. 2006.
[6] René Erlín Castillo and Humberto Rafeiro. An introductory course in Lebesgue spaces. Springer, 2016.
[7] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A general framework for consistent structured prediction with implicit loss embeddings. Journal of Machine Learning Research, 21 21(98):1-67, 2020.
[8] Felipe Cucker and Ding Xuan Zhou. Learning theory: an approximation theory viewpoint, volume 24. Cambridge University Press, 2007.
[9] Lue Devroye and Gábor Lugosi. Combinatorial methods in density estimation. Springer Science & Business Media, 2012.
[10] Alexander Goldenshluger and Oleg Lepski. On adaptive minimax density estimation on rd Probability Theory and Related Fields, 159(3-4)449-543 2014.
[11] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672-2680, 2014.
10

---

[12] Lars Hörmander. The analysis of linear partial differential operators 1I: Differential operators with constant coefficients. Springer, 1990.
[13] Diederik P Kingma and Max Welling, Auto-encoding variational bayes. International Confer- ence on Learning Representation (ICLR. 2014.
[14] Ulysse Marteau-Ferey, Francis Bach, and Alessandro Rudi. Non-parametric models for non- negative functions. In Advances in neural information processing systems, 2020.
[15] Ulysse Merteau-Ferey, Francis Bach, and Alessandro Rudi. Sampling from arbitrary functions via psd models. arXiv preprint arXiv:2110.10522 2021.
[16] Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, and Bernhard Schölkopf. Kernel mean embedding of distributions: A review and beyond. Foundations and Trends(r) in Machine Learning Series, 2017.
[17] Kevin P Murphy, Machine learning: probabilisticc perspective. MIT press, 2012.
[18] Erich Novak. Deterministic and stochastic error bounds in numerical analysis. Springer, 2006.
[19] Sebastian Nowozin, Christoph H Lampert, et al. Structured learning and prediction in computer vision. Foundations and Trends in Computer Graphics and Vision, 2011.
[20] Nicolò Pagliana, Alessandro Rudi, Ernesto De Vito, and Lorenzo Rosasco. Interpolation and learning with scale dependent kernels. arXiv preprint arXiv:2006.09988 2020.
[21] Emanuel Parzen. On estimation of probability density function and mode. The annals of mathematical statistics, 3363) 1962.
[22] Christian Rieger and Barbara Zwicknagl. Sampling inequalities for infinitely smooth func- tions, with applications interpolation and machine learning. Advances in Computational Mathematics, 32(1) 3003, 2010.
[23] Luke Gervase Rogers. A
Sobolev extension operator. Yale University, 2004.
[24] Alessandro Rudi, Ulysse Marteau-Ferey, and Francis Bach. Finding global minima via kernel approximations. arXiv preprint arXiv:20/2./1978, 2020.
[25] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In NIPS, pages 2215-3225, 2017.
[26] Bernhard Schölkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
[27] John Shawe-Taylor and N Cristianini. An introduction support vector machines and other kernel-based learning methods, volume 204. Volume, 2000.
[28] Winfried Sickel. Composition operators acting sobolev spaces of fractional order survey on sufficient and necessary conditions. Function spaces, differential operators and nonlinear analysis (Paseky nad Jizerou, 1995), pages 159-182, 1996.
[29] Shashank Singh, Ananya Uppal, Boyue Li, Chun-Liang Li, Manzil Zaheer, and Barnabás Póczos. Nonparametric density estimation with adversarial losses. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 10246-10257. Curran Associates Inc., 2018.
[30] Alex Smola, Arthur Gretton, Le Song, and Bernhard Schölkopf. A hilbert space embedding for distributions. In International Conference on Algorithmic Learning Theory, pages 13-31. Springer, 2007.
[31] Le Song, Kenji Fukumizu, and Arthur Gretton. Kernel embeddings of conditional distributions: unified kernel framework for nonparametric inference graphical models. IEFE Signal Processing Magazine, 1014)

---

[32] Bharath Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Aapo Hyvärinen, and Revant Kumar. Density estimation infinite dimensional exponential families. Journal of Machine Learning Research, 18, 2017.
[33] Elias M Stein and Guido Weiss. Introduction Fourier Analysis Euclidean Spaces (PMS-32), Volume 32. Princeton university press, 1971.
[34] Ingo Steinwart and Andreas Christmann. Support Vector Machines. Information Science and Statistics. Springer New York, 2008
[35] Alexandre B Tsybakov. Introduction nonparametric estimation. Springer Science & Business Media, 2008.
[36] Paxton Turner, Jingbo Liu, and Philippe Rigollet. A statistical perspective coreset density estimation. International Conference on Artificial Intelligence and Statistics, pages 2512- 2520. PMLR, 2021.
[37] Adrien Vacher, Boris Muzellec, Alessandro Rudi, Francis Bach, and Francois dimension-free computational upper-boung bound for smooth optimal transport estimation. arXiv preprint arXiv:2101.05380 2021.
Trancois-Xavier Xavier Vialard.
[38] Matt P Wand and M Chris Jones. Kernel smoothing. CRC press, 1994.
[39] Holger Wendland, Scattered Data Approximation, volume 17, Cambridge University Press, 2004.
[40] Christopher Williams and Matthias Seeger. Using the nyström method to speed kernel machines. In Proceedings of the 14th annual conference on neural information processing systems, pages 682 688, 2001.
[41] Vadim Yurinsky. Sums and Gaussian vectors. Springer, 1995.
12


Reviews:
[{"review_id": "dgwvkK-4cxl", "reviewer": "Reviewer_ME1H", "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.", "questions": "", "limitations": "", "rating": 7, "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 paper is well-written. Even though I am not an expert in the topic, I could follow the exposition without major problems.\n\nThe 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.\n\nThat 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.\n\nI 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?\n\n&nbsp;\n### References\n[1] Ulysse Marteau-Ferey, Francis Bach, and Alessandro Rudi. Non-parametric models for non-negative functions. NeurIPS, 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "O0aE9dzso-E", "reviewer": "Reviewer_zSeK", "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.", "questions": "", "limitations": "", "rating": 7, "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 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. \n\nSome minor comments:\n\n- Please comment on how can solve the estimation problem (12) to get \\hat{A}.\n- 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?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not relevant", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "MNL7tbPv15N", "reviewer": "Reviewer_1NBG", "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.", "questions": "", "limitations": "", "rating": 6, "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": "Originality:  The work builds heavily off of [15], but there is more than enough novelty in this specific case to justify a separate work.\n\nQuality:  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)?\n\n2) 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?\n\n3)  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.\n\nClarity: 1) There are a significant number of typos that should be corrected via a thorough proofreading.\n2) 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.\n\nSignificance:  Efficient density estimation techniques are of general interest.  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Appropriate.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "-amlVqBWCO2", "reviewer": "Reviewer_JxqL", "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.", "questions": "", "limitations": "", "rating": 7, "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 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.\n\nThere 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.\n\nAnother 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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?\n- Does the parameter estimation consider the kernel parameter?\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

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)