Provable benefits of score matching
Authors: Chirag Pabbaraju
Dhruv Rohatgi
Anish Sevekari
Holden Lee
Ankur Moitra
Andrej Risteski
Venue: NeurIPS 2023 spotlight (2023)
Keywords: theory
score matching
exponential families
sample complexity
computational hardness
TL;DR: For natural exponential families, optimizing MLE using zero- and first-order methods can be NP-hard, while score matching is computationally efficient and statistically comparable.

Abstract: Score matching is an alternative to maximum likelihood (ML) for estimating a probability distribution parametrized up to a constant of proportionality. By fitting the ''score'' of the distribution, it sidesteps the need to compute this constant of proportionality (which is often intractable).
While score matching and variants thereof are popular in practice, precise theoretical understanding of the benefits and tradeoffs with maximum likelihood---both computational and statistical---are not well understood. In this work, we give the first example of a natural exponential family of distributions such that the score matching loss is computationally efficient to optimize, and has a comparable statistical efficiency to ML, while the ML loss is intractable to optimize using a gradient-based method. The family consists of exponentials of polynomials of fixed degree, and our result can be viewed as a continuous analogue of recent developments in the discrete setting. Precisely, we show: (1) Designing a zeroth-order or first-order oracle for optimizing the maximum likelihood loss is NP-hard. (2) Maximum likelihood has a statistical efficiency polynomial in the ambient dimension and the radius of the parameters of the family. (3) 
Minimizing the score matching loss is both computationally and statistically efficient, with complexity polynomial in the ambient dimension.

Provable benefits of score matching
Chirag Pabbaraju Stanford University
Dhruy Rohatgi MIT drohatgi@min @mit edu
Anish Sevekari
Carnegie Mellon University asevekar@andrew cmu, edu
cpabbara@cs. stanf ooffford.edu
Holden Lee Johns Hopkins University hlee2830 edu
Ankur Moitra MIT moitra@mit.ccm
Andrej Risteski
Carnegie Mellon University
aristesk@andrez cmu edu
Abstract
Score matching is alternative to maximum likelihood (ML. for estimating a probability distribution parametrized up to constant of proportionality. By fitting the "score" of the distribution, it sidesteps the need to compute this constant of proportionality (which is often intractable). While score matching and variants thereof are popular in practice, precise theoretical understanding of the benefits and tradeoffs with maximum likelihood both computational and statistical are not well understood. In this work, give the first example of natural exponential family of distributions such that the score matching loss computationally efficient optimize, and has comparable statistical efficiency MI., while the MI loss is intractable to optimize using a gradient-based method. The family consists of exponentials of polynomials of fixed degree, and our result a continuous analogue of recent developments in the discrete setting. Precisely, we show: (1) Designing zeroth-order or first-order oracle for optimizing the maximum likelihood loss is NP-hard. (2) Maximum likelihood has a statistical efficiency polynomial in the ambient dimension and the radius of the parameters of the family. (3) Minimizing the score matching loss is both computationally and statistically efficient, with complexity polynomial in the ambient dimension.
be viewed
Introduction
Energy- models are flexible class of probabilistic models with wide-ranging applications. They are parameterized by class of energies (x(x) which in turn determines the distribution
pa (a) (
Zo
up to a constant of proportionality Ze that is called the partition function. One of the major challenges of working with energy-based models is designing efficient algorithms for fitting them data. Statistical theory tells us that the maximum likelihood estimator (MLE)-i.e., the parameters 0 which maximize the likelihood-coe enjoys good statistical properties including consistency and asymptotic efficiency.
However, there is major computational impediment computing the MLE: Both evaluating the log-likelihood and computing its gradient with respect to (i.e., implementing zeroth and first order oracles, respectively) seem require computing the partition function, which is often computationally intractable. More precisely, the gradient of the negative log- ligelikel depends on Va log Za Epo (o)), A popular approach is estimate this quantity by using Markov chain to approximately sample from pa. However in high-dimensional settings, Markov chains often require many, sometimes even exponentially many, steps mix.
Score matching (Hyvärinen, 2005) a popular alternative that sidesteps needing to compute the partition function of sample from pe. The idea is to fit the score of the distribution, in the sense that
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

we want & such that v p(z) matches V. log Po (z) for a typical sample from This approach turns out to have many nice properties. It is consistent in the sense that minimizing the objective function yields provably good estimates for the unknown parameters. Moreover, while the definition depends on the unknown v log p(z), by applying integration by parts, is possible to transform the objective into an equivalent one that can be estimated from samples.
The main question is to bound its statistical performance, especially relative that of the maximum likelihood estimator. Recent work by Koehler et al. (2022) showed that the cost can be quite steep. They gave explicit examples of distributions that have bad isoperimetric properties (i.e., large Poincaré constant) and showed how such properties can cause poor statistical performance.
Despite wide usage, there is little rigorous understanding of when score matching helps. This amounts to finding a general setting where maximizing the likelihood with standard first-order optimization is provably hard, and yet score matching is both computationally and statistically efficient, with only a polynomial loss in sample complexity relative to the MLE. In this work, we show the first such guarantees, and we do so for a natural class of exponential families defined by polynomials. As we discuss in Section 1.1, our results parallel recent developments in learning graphical models-where it is known that pseudolikelihood methods allow efficient learning of distributions that hard to sample from-and can be viewed as a continuous analogue of such results.
In general, an exponential family on R" has the form (2 h(x) exp( T(z))) where h(x) is the base measure, is the parameter vector, and T(x) is the vector of sufficient statistics. Exponential families are one of the most classic parametric families of distributions, dating back to works by Darmois (1935), Koopman (1936) and Pitman (1936). They have a number of natural properties, including: (1) The parameters 0 are uniquely determined by the expectation of the sufficient statisties is the maximum entropy distribution, subject to having given values for Ep,, [T]] (3) They have conjugate priors (Brown, 1986), which allow characterizations of the family for the posterior of the parameters given data.
Ep [T']: (2) The distribution
For any (odd positive integer) constant d and norm bound B 1, we study natural exponential family Pn, on R" where
1. The sufficient statistics T(x) E M- consist of all monomials in Fi,..., Iy of degree least 1 and at most d (where M = ("*2))
2. The base measure is defined as h(xx) exp( 1xp(->i -i 2 +
3. The parameters lie in an -bll: E On = (0 e E 1101 S B).
Towards stating our main results, we formally define the maximum likelihood and score matching objectives, denoting by È the empirical average over the training samples drawn from some p E P,,
(0) = E T [lo pa (x]]
Eamp
1 Exeppl
LSM
V logp(z) V log po (X)]) + K
2
Ennp
Tr logpe (x) + log (2)
(I)
where Kp is constant depending only p and (1) follows by integration by parts (Hyvärinen, 2005). In the special case of exponential families, (1) is quadratic, and in fact the optimum can be written in closed form:
arg min LSM (0) = ()) - AT(x)
(JT)
(2)
A
where (JT).: (M - 1) x n is the Jacobian of T at the point x, Af = 0,5 is the Laplacian, applied coordinate wise to the vector-valued function f.
With this setting in place, we show the following intractability result.
Theorem 1.1 (Informal, computational lower bound). Unless AP = NP, there is no poly(n, N)- time algorithm that evaluates (MLE(0) and LIMEE(() given 0 2g and arbitrary samples I1...., EN E R", for d = 7, B = poly(n) (n). Thus, optimizing the MLE loss using a zeroth-order or first-order method is computationally intractable.
We note that the choice of base measure is for convenience in ensuring tail bounds necessary in our proof.

---

The main idea of the proof is to construct polynomial (r( which has roots exactly at the satisfying assignments of given 3-SAT formula C. We then argue that exp(->Fe(z)), for sufficiently large 0, concentrates near the satisfying assignments. Finally, we show sampling from this distribution or approximating log Zo or Vo log Zy (where E RR--1 the parameter vector corresponding to the polynomial (x)) would enable efficiently finding satisfying assignment.
Our next result shows that MLE, though computationally intractable compute via implementing zeroth or first order oracles, has (asymptotic) sample complexity poly (n, [3) (for constant d).
Theorem 1.2 (Informal, efficiency of MLE). The MLE estimator MLE arg max, MLE(( has asymptotic sample complexity polynomial in n. That is, for all sufficiently large N it holds with probability least 0.99 (over N samples drawn from pe- that:
||êMLE - =1= (
(nB))olyyd)
N
The main proof technique for this is anticoncentration bound of low-degree polynomials, for distributions in our exponential family.
Lastly, we prove that score matching also has polynomial (asymptotic) statistical complexity.
Theorem 1.3 (Informal, efficiency of SM). The score matching estimator PsM arg max, LSM (0) also has asymptotic sample complexity at most polynomial in n. That is, for all sufficiently large N it holds with probability at least 0.99 (over N samples drawn from po- ) that:
(n (nB)poly(d)
10sM - 0-11 0o
(3)
The main ingredient in this result is a bound the restricted Poincaré constant-namely. the Poincaré constant, when restricted to functions that are linear in the sufficient statistics T. We bound this quantity for the exponential family we consider in terms of the condition number of the Fisher matrix of the distribution, which we believe is a result of independent interest. With this tool in hand, we can use the framework of Koehler al. (2022), which relates the asymptotic sample complexity of score matching to the asymptotic sample complexity of maximum likelihood, in terms of the restricted Poincaré constant of the distribution.
1.1 Discussion and related work
Score matching: Score matching was proposed by Hyvärinen (2005), who also gave conditions under which it is consistent and asymptotically normal. Asymptotic normality is also proven for various kernelized variants of score matching in Barp et al. (2019). Koehler et al. (2022) prove that the statistical sample complexity of score matching is not much worse than the sample complexity of maximum likelihood when the distribution satisfies a (restricted) Poincaré inequality. While we leverage machinery from Koehler et al. (2022), their work only bounds the sample complexity of score matching by quantity polynomial in the ambient dimension for a specific distribution in specific bimodal exponential family. By contrast, we can handle an entire class of exponential families with low-degree sufficient statistics.
We note that while Poincaré inequalities are directly related to isoperimetry and mixing of Markov chains, sample efficiency of score matching only depends on the Poincaré inequality holding for restricted class of functions, namely, functions linear in the sufficient statistics. Hence, hardness of sampling only implies sample complexity lower bounds in cases where the family expressive enough-indeed the key to exponential lower bounds for score matching in Koehler et al. (2022) is augmenting the sufficient statistics with function defined by bad cut. This gap means that we can hope to have good sample complexity for score matching even in cases where sampling is hard-whidd we take advantage of in this work.
Poincaré vs Restricted Poincaré:
Despite the fact that exponential families are both classical and ubiquitous, both in statistics and machine learning, there is relatively little understanding about the computational-statie tradeoffs to learn them from data, that is, what sample complexity can be achieved with computationally efficient algorithm. Ren et al. (2021) consider version of the
Learning exponential families:
3

---

"interaction screening" estimator, a close relative of pseudolikelihood, but do not prove anything about the statistical complexity of this estimator. Shah et al. (2021) consider related estimator, and analyze it under various low-rank and sparsity assumptions of reshapings of the sufficient statistics into a tensor. Unfortunately, these assumptions are somewhat involved, and it's unclear if they are needed for designing computationally and statistically efficient algorithms.
Discrete exponential families (Ising models): Ising models have the form P2( o exp Ling Jejazzy + Σ; Jezi) where denotes adjacency in some (unknown) graph, and Jij. J, denote the corresponding pairwise and singleton potentials. Bresler (2015) gave an efficient algorithm for learning any Ising model over a graph with constant degree (and -buunds on the coefficients); also the more recent work (Dagan et al., 2021). In contrast, it is classic result (Arora and Barak, 2009) that approximating the partition function of members in this family is NP-hard.
Similarly, the exponential family we consider is such that it contains members for which sampling and approximating their partition function is intractable (the main ingredient the proof of Theorem 1.1). Nevertheless, by Theorem 3, we can learn the parameters for members in this family computationally efficiently. and with sample complexity comparable to the optimal one (achieved by maximum likelihood). This also parallels other developments in Ising models (Bresler et al., 2014; Montanari, 2015), where it is known that restricting the type of learning algorithm (c.g., requiring it to work with sufficient statistics only) can make tractable problem become intractable.
The parallels can be drawn even on an algorithmic level: a follow up work to Bresler (2015) by Vuffray et al. (2016) showed that similar results can be shown in the Ising model setting by using the "screening estimator", close relative of the classical pseudolikelihood estimator (Besag, 1977) which tries to learn distribution by matching the conditional probability of singletons, and thereby avoids having to evaluate a partition function. Since conditional probabilities of singletons capture changes in single coordinate, they can be viewed as a kind of "discrete gradient" further analogy to score matching in the continuous setting.
2 Preliminaries
We consider the following exponential family. Fix positive integers n, d, B E N where d is odd. Let h(z)) exp(- - Σ 1 ), and let T(z) E RM be the vector of monomials in 21...., of degree at least and at most d (so that M ("*")). Define θ C M- by θ {0 R-1;
|101|.0 I B}. For any 0 O define pe I² - [0, 20) by
po (x) h(x) exp( T(x)))
Ze
where Zo = Sg- hxx) (0, T(x))) de is the normalizing constant. Then we consider the family Pn,d, = (pa)ae Throughout, we will assume that B Z 1.
Polynomial notation: Let R[ Inled denote the space of polynomials in T1..... Fn of
degree at most d. We can write any such polynomial f as f(x) = Σjalga GdTa where d denotes
a degree function d [n] + N, and |d| = Ei_ d(i), and we write za to denote IT 2
d(1) Note
that every d with 1 < |d] S d corresponds to an index of T, i.e. ((x)a = Hd.
Let Il-I denote the e norm of polynomial in the monomial basis; that is, IE Eaaaaallnn mon (Ea o3) 1/2 For any function f :. + E. let || Ee--Uat((-1))) R"
Statistical efficiency of MLE; For any 0 E MR1 the Fisher information matrix of po with respect to the sufficient statistics ((x) is defined as
I(0)= = E (<) 1 Ex-pp (Tx)) [Tx))
is well-known that for any exponential family with no affine dependencies among the sufficient statistics (see e.g., Theorem 4.6 in Van der Vaart (2000)), it holds that for any 0* E M-1, given N
In fact, ratio matching, proposed in Hyvärinen (2007) as discrete analogue of score matching, relies on exactly this intuition.

---

independent samples (1)), x(N) ~ pe-, the estimator MLE MLE (x()) ...)) satisfies
VN (MMLE- -8") -((
Statistical efficiency of score matching: Our analysis of the statistical efficiency of score matching based on a result due to Koehler et al. (2022). We state requisite definition followed by the result. Definition 2.1 (Restricted Poincaré for exponential families). The restricted Poincaré constant of p E P dd is the smallest Cp 0 such that for all w E RM--1 it holds that
Varp((w, (w))( S Cplppp ll
V V (w, T
Theorem 2.2 (Koehler et al. (2022)). Under certain regularity conditions (see Lemma B.4), for any Pg- with restricted Poincaré constant Cp and with Amin (I(0*)) > O, given N independent samples
x(1) (N) par, the estimator fsM (s((( (...,.(()) satisfies
VN(ŪSM - 0*) +N(0T,
where I satisfies
|Pl 2C Topp (x)
Exxopo [
Amin (I(0r))2
= where (JT)(z); (2))()) and - (x))
3 Hardness of Implementing Optimization Oracles for P polyyn)
In this section we prove NP-hardness of implementing approximate zeroth-order and first-order opti- mization oracles for maximum likelihood in the exponential family P,,7,Cn² log(s) (for a sufficiently large constant C) as defined Section 2: also show that approximate sampling from this family is NP-hard. See Theorems 3.4, 3.5, and A.5 respectively. All of the hardness results proceed by reduction from 3-SAT and use the same construction.
The idea is that for any formula C on n variables, we can construct a non-negative polynomial Fo of degree at most 6 in variables Zi...., Tne which has roots exactly at the points of the hypercube H = (-1, 1}" C Rd that correspond to satisfying assignments (under the bijection that æ; = corresponds True and x; -1 corresponds to False). Intuitively, the distribution with density proportional to exp(->Fc(z)) will, for sufficiently large > O, concentrate on the satisfying assignments. It then straightforward to see that sampling from this distribution or efficiently computing either log Ze or V log Zo (where 0 E M-1 is the parameter vector corresponding to the polynomial -)))(x)) would enable efficiently finding satisfying assignment.
The remainder of this section makes the above intuition precise; important details include (1) incorporating the base measure h(x) exp(- > 2;f) into the density function, and (2) showing that a polynomially large temperature y suffices.
Definition 3.1 (Clause/formula polynomials). Given 3-clause formula of the form C = 3z Vāy Vā where 3; = I; or T. -i, we construct a polynomial Ho E R(zi...., tn]]e defined by
Hc(x) = f((x.) (2,
where
S401) (t+1) if x; is negated in C (1--1) otherwise
For example. if D1 V x2 V -r3, then Hc (01 - () - 2)²(2; + 1)2. Further, given 3-SAT formula C = C1 A ... A Om on m clauses?. we define the polynomial
Hc(x) Hc. (z) .... Hc.. (x).
It can be seen that any H corresponds to satisfying assignment for C if and only if Hc(x) 0. Note that there are possibly points outside H which satisfy He(z) = 0. To avoid these solutions, we introduce another polynomial:
It suffices to work with O(n), Theorem A.I.
5

---

Definition 3.2 (Hypereube polynomial). We define G R" - R by G(x) = (1=1(1
Note that G(x)) 2 0 for all z, and the roots of G(x) are precisely the vertices of H. Therefore for any a, 3 > O, the roots (in R²) of the polynomial Pc(2) = aH)(()) + 3G(x) are precisely the vertices of H. that correspond to satisfying assignments for C.
Definition 3.3. Let C. be a 3-CNF formula with n variables and m clauses. Let a, 0. Then we define distribution a with density function
pC)) h(x)) (app-aaH(x))BCaa
Ze,0,,8
where 7c = Jan - dr.
This distribution lies in the exponential family Pn.d, for d = 7 and B = Q23 ma) (Lemma A.2). Thus, if ((C, a. 3) is the parameter vector that induces Pc.a, then it suffices show that (a) approximating log (..). (b) approximating Ve log a.)) and (c) sampling from Pc,a. are NP-hard (under randomized reductions). We sketch the proofs below; details are in Appendix A.
Hardness of approximating log Zc.a.s: In order to prove (a), we bound the mass of Pc.a.s in each orthant of R In particular, show that for Q(()) and / 5m log m), any orthant corresponding to a satisfying assignment has exponentially larger contribution to Zc.a. than any orthant corresponding an unsatisfying assignment. A consequence is that the partition function Zc,o,, a is exponentially larger when the formula C is satisfiable than when it isn't ' (Lemma A.6).
But then approximating Zc,a.9 allows distinguishing a satisfiable formula from an unsatisfiable formula, which is NP-hard. This implies the following theorem (proof in Section A.2):
Theorem 3.4. Fix n E N and let B 2 Cn² for sufficiently large constant C. Unless RP = NP, there is no poly(n)-time algorithm which takes as input an arbitrary 0 E OB and ouiputs an approximation of log Zg with additive error less than n log 1.16.
Hardness of approximating Ve log Zo(c,a.9); Note that V log Ze Ezz-p [T]]], in par- ticular approximating the gradient yields approximation to the mean Ex-pp [z]. Since Pc.a.s is concentrated in orthants corresponding to satisfying assignments of C, we would intuitively expect that if C has exactly one satisfying assignment v², then (i [zr)) corresponds to this assignment.
Formally, we show that if a (n) and 3 = 2(mm log m), then Eg-pe... [M] mx) 2 1/20 for all i [n]] (Lemma A.7).
Since solving formula with a unique satisfying assignment is still NP-hard, we get the following theorem (proof in Section A.3):
Theorem 3.5. Fix n E N and let B 2 Cn² log(n) for a sufficiently large constant C. Unless RP NP, there no poly(n)-tinn algorithm which takes as input an arbitrary 0 E OB and outputs an approximation of V log Za with additive error (in an loo sense) less than 1/20.
With the above two theorems in hand, we are ready to present the formal version of Theorem 1.1; the proof is immediate from the definition of LMLF (see Section A.5).
N and let B > On² log n for a sufficiently large constant C. Unless RP NP, there is no poly(n, , N) -ime algoritiun which takes as input an arbitrary 0 E OB, and an arbitrary sample Z1.... EN IR", and outputs an approximation of LMLE(() up to additive error of log 1.16, or VoLMLE (0) up to an additive error of 1 1/20.
Corollary 3.6. Fix n,
Hardness of approximate sampling: We show that for Q(n) and B 2(m log m). the likelihood that x ~ Pc...8 lies in an orthant corresponding to a satisfying assignment for C is at least 1/2 (Lemma A.4). Hardness of approximate sampling follows immediately (Theorem A.5). Hence, although we show that score matching can efficiently estimate f² from samples produced by nature, knowing 0* isn't enough to efficiently generate samples from the distribution.
4 Statistical Efficiency of Maximum Likelihood
In this section we prove Theorem 1.2 by showing that for any E OB, we can lower bound the smallest eigenvalue of the Fisher information matrix I(0). Concretely, we show:

---

Amin (I))) itself requires lower-bounding the variance of Theorem 4.1. For any 0 E θg it holds that
Amin (I(O)) 2 (nB) (nB)-ord9)
-0(49)
As a corollary, given N samples from pa. it holds as N + oc that (N 8) - (0, NO,,TMML MLLE) where ||_ MIl S (nB)Old)) Moreover, for sufficiently large N, with probability at least 0.99
holds that MLLE - 1 (nB)o(d))/) /N.
Once we have the bound on Amin (I())), the first corollary follows from standard bounds for MLE (Section 2). and the second corollary follows from Markov's 's incquality (see e.g., Remark 4 in Koehler et al. (2022)). Lower-boundigg any polynomial (with respect to Po) in terms of its coefficients. The proof consists of three parts. First, we show that the norm of a polynomial in the monomial basis is hoper-bbunded in terms of its L norm on [-1, 11,11 1]":
Lemma 4.2. For I E R[21. Inlga have I| S (( II (1(,))))))))))))))
The key idea behind this proof is to work with the basis of (tensorized) Legendre polynomials, which orthonormal with respect to the L norm. Once we write the polynomial with respect to this basis, the 2 norm equals the Euclidean norm of the coefficients. Given this observation, all that remains is to bound the coefficients after the change-of-basis. The complete proof is deferred to Appendix C.
Next, we show that if a polynomial f R" + R has small variance with respect to then there is some box on which f has small variance with respect to the uniform distribution. This provides a way of comparing the variance of with its L norm (after an appropriate rescaling).
Lemma 4.3. Fix any A E θB and define p == Po. Define R := nBM. Then for any R [[11....... Fnl sd sá there some a E R" with ||=1| S R and some e 2 (R such that
Var,(f) 2 2e
(arz((),
where Ü is the uniform distribution on {ar E R" || 20000 S {)
In order prove this result, we pick random box of radius e (within large bounding box of radius Rt). In expectation, the variance on this box (with respect to p) is not much less than (ar,
Moreover, for sufficiently small e, the density function of p on this box has bounded fluctuations, allowing comparison of (frp(f) and Var, (f). This argument is formalized in Appendix C.
Together, Lemma 4.2 and 4.3 allow us to lower bound the variance Varp(f) in terms of Ill
Lemma 4.4. Fix any E OB and define p == Pa. Define R 2d+8nBM. Then for any E R [[r,, [I..,..... Inl ,n with (0) 0, it holds that
Var, 22d 1) M ped
Byad IIf l
See Appendix for the proof. We We are now ready to finish the proof of Theorem 4.1.
Proof of Theorem 4.1. Fix 0 E θg. Pick any RM and define f(x) = (w, T(x)). By definition of I()), we have Varp. = w (()).. Moreover, Il = || Thus, Lemma 4.4 gives us that w TI(0 2 (n()))(dd) || using that R = 2d+88BB. and M (=+d). The bound Amia (I(0) 2 (nB) - follows.
5 Statistical Efficiency of Score Matching
In this section we prove Theorem 1.3. The main technical ingredient bound on the restricted Poincaré constants of distributions in Pn.d, B- For any fixed 0 E On we showthat Cp can be bounded in terms of the condition number of the Fisher information matrix I(O). We describe the building blocks of the proof below.
7

---

Fix 0, w E RW-1 and define f(x) := (w, T())) First, we need to upper bound Varpo (f). This where (the first half of) the condition number appears. Using the crucial fact that the restricted Poincaré constant only considers functions f that are linear in the sufficient statistics, and the definition of I()), we get the following bound on Varp. (f) terms of the coefficient vector w. The proof is deferred to Section D.
Lemma 5.1. Fix 0, E TR- and define (() == (w, Tx))) Then
|1 Amin (I(O)) & Varpo (f) 2 |wll Amax (I(O)).
Next, we lower bound Ex-pe (z) To do (u, (=))) over all directions in the basis; however, it is unclear how to choose this basis. Instead, we pick u ~N(O0, In) randomly, and use the following identity:
could pick orthonormal basis and bound
E Ex--p V fx) E Bu (u, vx)(=))²
For any fixed u, the function g(z) = (u, vaf(z)) is also polynomial. If this polynomial had no constant coefficient,
could immediately lower bound E(u, V (xr)) in terms of the remaining
coefficients, as above. Of course, may have a nonzero constant coefficient, but with some case-work over the value of the constant, can still prove the following bound:
Lemma 5.2. Fix 0, i E M-1 and E I, and define ( (w, T(:)) + Then
a² + 100
B Ee-pol9(2)) [9(2))1
min(1, Amin (I()))).
[T))]l
Proof. We have
E Ex-pp ( = Varp, (g) + Farpp [g])]
= Varp, (0 c) + (c + w Enpp (ax))
|| Amin (I))) + (c w Enwno [T (x)))
where the inequality by Lemma 5.1. We now distinguish two cases.
Case I. Suppose that |c + w TE En-pp [T(x)]] 2 c/2. Then
2 + 1
Bazpp [x(x)²) 2 | 1 Amin (I())) +
min(1, Amin (T(O)))
4
Case II. Otherwise, we have |e + の T Ex [<>)] < c/2. By the triangle inequality, it follows
that p1) Rer (xx)) 2 c/2, 2, so ||
2 o/ Ex [Tx))]ll2 Therefore
a² L ? < (1 +
4 Bo [x)]
: |0
from which we get that
c² + | 2
Ez-po [9(x)}}
||0 Amin (I(0))
2
Amin (I()))
+ 4
Egrpo [xx))
as claimed.
With Lemma 5.1 and Lemma 5.2 in hand (taking g(z) (u, V=f(x)) in the latter), all that remains is to relate the squared monomial norm of (u, Vz)(x)) (in expectation over u) the squared monomial norm of f. This crucially uses the choice ~ N (0, Ix). We put together the pieces in the following lemma. The detailed proof is provided in Section D.
Lemma 5.3. Fix 8, w E M-1, Define f(x) := (w, ((x)). Then
Xmmar (I(O))
Var,, po (f) S (4 + | [T())]I1) min(1, 11, Amii (I(O))) Ex- I (x)))
8

---

Finally, putting together Lemma 5.3, Theorem 4.1 (that lower bounds Amin (I(O)), and Lemma B.2 (that upper bounds >max (I)))) straightforward consequence the distributions in Pn,d, having bounded moments), we can prove the following formal version of Theorem 1.3:
Theorem 5.4. Fix n, d, B, N N. Pick any 0 BB and let x(1) xNN) Po- be independent samples. Then as N + oc, the score matching estimator fsM (
(x(1), ,...,, x(N) satisfies
VN(0SM +8) N(O
where [| op S (nB)o(e") As corollary, for all sufficiently large N it holds with probubility at least 0.99 that |8sM 8-) 001 (nB)o
Proof. We apply Theorem 2.2. By Lemma B.4 and the fact that Amin(((0-)) > 0 (Theorem 4.1), the necessary regularity conditions are satisfied so that the score matching estimator is consistent and asymptotically normal, with asymptotic covariance T satisfying
20 20 Ee-po- (z) op + Eawpy- [
|| op
Amin (I(Or))2
where Cp is the restricted Poincaré constant for po- with respect to linear functions in ((x) (see Definition 2.1). By Lemma 5.3, we have
Amax (I(O"))
Cp (4 Pu (x)]112
min(1, Amin (I(O*))
B2d 22442224440)
(4 4B2d M M2422200440044
S (nB)orde)
(nB)-0(d9) 0(ds)
using parts (a) and (b) of Lemma B.2; Theorem 4.1; and the fact that M (a Substituting into (4) and bounding the remaining terms using Lemma B.3 and a second application of Theorem 4.1, we conclude that || < (nd)) claimed. The high-probabilityy bound now follows from Markov's 's inequality; see Remark 4 in Kochler et al. (2022) for details.
6 Conclusion
We have provided a concrete example of an exponential degree polynomials- wheee score matching is significantly more computationally efficient than maximum likelihood estimation (through optimization with a zero- or first-order oracle), while still achieving the same sample efficiency up to polynomial factors. While score matching was designed to be more computationally efficient for exponential families, the determination of statistical complexity more challenging, and we give the first separation between these two methods for general class of functions.
exponentials of bounded
As we have restricted our attention to the asymptotic behavior of both of the methods, interesting future direction is to see how the finite sample complexities differ. One could also give a more fine-grained comparison between the polynomial dependencies of score matching and MLE, which we have not attempted to optimize. Finally, it would be interesting to relate our results with similar results and algorithms for learning Ising and higher-order spin glass models in the discrete setting, and give a more unified treatment of psueudo- likelihood or score/ratio matching algorithms in these different settings.
Acknowledgements
CP is supported by Moses Charikar and Greg Valiant's Simons Investigator Awards. DR is supported in part by U.S. DoD NDSEG Fellowship. AS is supported in part by NSF grants DMS- 20545005503 and 22381 125. AM is supported by grant from the ONR, NSF Award 191 9918656 and a David and Lucile Packard Fellowship. AR is supported part by NSF awards IIS-221 1907, CCF-2238523, and an Amazon Research Award.

---

References
Arora, and Barak, (2009). Computational complexity: a modern approach. Cambridge University Press.
Barp, A., Briol, F.-X., Duncan, A., Girolami, M., and Mackey, L. (2019). Minimum stein discrepancy estimators. Advances in Neural Information Processing Systems, 32.
Besag, J. (1977). Efficiency of pseudolikelihood estimation for simple gaussian fields. Biometrika, pages 616-618.
Bresler, G. (2015). Efficiently learning ising models on arbitrary graphs. In Proceedings of the forty-seventh annual ACM symposium Theory of computing, pages 771-782.
Bresler, G., Gamarnik, D., and Shah, D. (2014). Structure learning of antiferromagnetic ising models. Advances in Neural Information Processing Systems, 27.
Brown, L. D. (1986). Fundamentals of statistical exponential families: with applications in statistical decision theory. Ims.
Cook, S. A. (1971). The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, pages 151-158.
Dagan, Y., Daskalakis, C., Dikkala, N., and Kandiros, A. V. (2021). Learning ising models from one or multiple samples. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 161-168.
Darmois, G. (1935). Sur les lois de probabilitéa estimation exhaustive. 260(1265):85.
CR Acad. Sci. Paris,
Forbes, P. G. and Lauritzen, (2015). Linear estimating equations for exponential families with application to gaussian linear concentration models. Linear Algebra and its Applications, 473:261- 283.
Hyvärinen, A. (2005). Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4).
Hyvärinen, A. (2007). Some extensions of score matching. Computational statistics & data analysis, (1(5):249925122
Koehler, F., Heckett, A., and Risteski, A. (2022). Statistical efficiency of score matching: The view from isoperimetry. arXiv preprint arXiv:2210.00726.
Koepf, W. (1998). Hypergeometric summation. Vieweg, Brauschweig/Wesshuden, 5(6).
Koopman, B. O. (1936). On distributions admitting sufficient statistic. Transactions of the American Mathematical society, 39(3):399
Montanari, A. (2015). Computational implications of reducing data to sufficient statistics.
Pitman, E. J. G. (1936). Sufficient statistics and intrinsic accuracy. In Mathematical Proceedings of the cambridge Philosophical society, volume 32, pages 567-579. Cambridge University Press.
Ren, C. X., Misra, S., Vuffray, M., and Lokhov, A. Y. (2021). Learning continuous exponential families beyond gaussian. arXiv preprint arXiv:2102.09198:
Shah, A., Shah, D., and Wornell, G. (2021). A computationally efficient method for learning exponential family distributions. Advances in neural information processing systems, 34:15841- 15854.
Valiant, L. G. and Vazirani, V. V. (1985). Np is easy as detecting unique solutions. In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 458-463.
Van der Vaart, A. W. (2000). Asymptotic statistics, volume 3. Cambridge university press.
Vuffray, M., Misra, S., Lokhov, A., and Chertkov, (2016). Interaction screening: Efficient and sample-optimal learning of ising models. Advances in neural information processing systems, 29.
10

---

A Omitted Proofs from Section 3
Theorem A.1 (Valiant and Vazirani (1985); Cook (1971)). Suppose that there is a randomized poly(n)-timi) time algoritlum for the following problem: given 3- 3-CNF formula C with n variables and at most 5n clauses, under the promise that C has at most one satisfying assignment, determine whether C is satisfiable. Then, NP RP.
Lemma A.2. In the setting of Definition 3.3, set d == 7 and B == 64ma +33. Then PC.... Pn,d,
Proof. Since aHc(()) + 3G(()) is a polynomial in 21...... Zn of degree at most there is some 0 == 0CC E RM-1 such that (0))()) + + h(x)) exp(-aHHe(x)) - 3G(x)) is proportional to h(x) exp (0, (z))), so Pc.a.. = Ps- Moreover, for any clause C, every monomial of Hc, has coefficient at most 64 in absolute value, so every monomial of He has coefficient most 64m. Similarly, every monomial of G has coefficient most 2 in absolute value. Thus, ||0lloc I 64ma + 28 =: B, so Pe.a. E Pn,d.B-
is constant independent of x. Then
Given point v E H. let (v) {i E RR" z44 2 0: Vi E [n]] denote the octant containing v, and let (v) = {i E R || - 0l1x0 I r) denote the ball of radius r with respect to foo norm.
Lemma A.3. p= PC.a.3 and Z == ac for some 3- CNFC with m clauses and n variables, and some parameters a, > 0. Let r E (0, 1). B 2 40r log(An/r) then for any v E H that a satisfying assignment C,
E -1-81mmr
((xxp(-22 - 3(1 =2²)) dx.
Pr E (r)) zrep
Z
For any H that is not satisfying assignment for C,
S e Z (L, exp( -11- -
Pr E ((w)) amp
dx
Proof. We begin by lower bounding the probability over (v). Pick any clause Ce included in C. We claim that (v) < 81r2 for all v' E (y).). Indeed, say that C₁ = ã, V ž, V Ty- Since v satisfies Ct, at least one of (f.)),, (v,), fx(w)) must be zero. Without loss of generality, say that fo.))) = 0; also observe that (0;)), (f < 2. It follows that for any E (v), (f(( Sr and 1., (f) < + 3 (since S 1). Therefore, we have
(V) < 2² (3)² (3)2 -1r
Summing over all m possible clauses, we have He(v') S 81mr2 for all v E (v).. Hence,
Pr E (,(r)) zrpp
exp
8 aHc(x) BG((x) dr Σ
Z Br(z)
i=1
e 8lmar
Σ i=1
8 3G(x)) dx
exp
Z
Br(r)
é 8lmar
expl- -18 - -3(1 - x2)2) dr
Z
1-7
8lmar?
1
=
1+
exp(-x² 3(1 - =22)) dx
(5)
Z
n2
1- -1marr
n
exp(-x> 3(1 x2)2) dx
7
where the second inequality (5) is by Lemma A.8. Next, we upper bound the probability over (ww). Let C2 be any clause in C that is not satisfied by w. Say that C₁ T; V ăj V Fx. Then [f((w)) (f)()) [fa(w))) 2. Furthermore, for any w' Od(w), we have
11

---

(f (f( 2 1, and hence Hc,(w') 2 1. Since Hc) 2 0 for all 2, C", we
(f conclude that Hc(w") 2 Hc, (w") 2 for all w' E (w:.. In particular, this gives us
(r ((w)) zmp
1 f
exp
Σ
-Hc(())-200) - -BG(x) dr
Z
((w)
i=1
- Σ o -BG(o) do
exp
7
O(w)
1=1
e
exp(- -xx 3(1 z²)2) dx
Z
as claimed.
A.1 Hardness of approximate sampling
Lemma A.4. Let be a satisfiable instance 3- with m clauses and variables. Let a. satisfy 2 2(n + 1) and 3 2 6480m (og(13n (3).mm) Set == Pe,a,8 and Z = Zc,a, If C H the set of satisfiable assignments for C, then
Σ E 2 2
1
mmp
DEV
Proof. Let v E H. be any assignment that satisfies C, and let w be any assignment that does not satisfy C. By Lemma A.3 with 1/2mm, have
Pr (x E O(v))) g0pp
2
Pr x~pp
(x E B,(w)
e a/2
exp(- - =2))) dr
Z
Pr(x O (w)).
Since we chose a sufficiently large that e -1+a/2 2 2", we get that
Pr (x O(v))
Σ
Pr (z E O(w)). gape
xmpe
WENVV
Hence,
Σ Pr (r NEV IMPE
Σ WEHY
Pr (c =1 Σ pxpe
Pr (x ( zmpe VEV
The lemma statement follows.
Theorem A.5. Let B 2 Cnè for a sufficiently large constant C. Unless AP = NP, there is no algorithm which takes imput an arbitrary 0 E On and outputs a sample from distribution Q with (V Q) < 1/3 in poly(n) time.
Proof. Suppose that such an algorithm exists. For each E N define a 2(n + 1) and B = 32400n log(13n Given 3-CNF formula C with variables and at most 5n clauses, can compute = (C,, 3). By Lemma A.2 we have E θg so long as B > Cn² for a sufficiently generate
sample from distribution Q with TV(Pc...s Q) < 1/3. But by Lemma A.4, we have PrewPe.... (signn)) satisfies C] 2 1/2. Thus, Pra-q (s)g(()) satisfies C) 2 1/6. follows that we can find a satisfying assignment with O(1) invocations of the sampling algorithm in expectation. By Theorem A. get NP = RP.
large constant C. Thus, by assumption
L
12

---

A.2 Hardness of approximating zeroth-order oracle
Lemma A.6. Fix n. m and ler a 2 2(n+1) and 6480m log (13nmm) There a constant A = A(n, m, a, 3) so that the following hold for every 3- 3-CNF formula C with n variables and m. clauses:
CfC is unsatisfiable, then Ze S A
* CfC is satisfiable, then Zc B 2 (e/2)"
Proof. If unsatisfiable, then by the second part of Lemma A.3, we have
Z = Z Σ Pr O(w)) c (L exp(-Iut1 3(1 ==))²) dr "
Aunsat-
WEH
On the other hand, if C is satisfiable, then by the first part of Lemma A.3 with r = 11/1==1/111 1162m,
22 (r E Br(w)) 2 21-12 (L/ exp(-xatt 3(1 - 3(1-23)3) do =: Aua-
Since a 2 2(n 1), we get
Aunsat S (2/e)"
as claimed.
Proof Theorem 3.4. First, observe that the following problem is NP-hard (under randomized reductions): given two 3-CNF formulas C² each with variables and at most 10n clauses, where it is promised that exactly one of the formulas satisfiable, determine which of the formulas is satisfiable. Indeed, this follows from Theorem A.1: given a 3-CNF formula C. with variables, at most 5n clauses, and at most one satisfying assignment, consider adjoining either the clause x; the clause -2; to C. If C has satisfying assignment v², then exactly one of the resulting formulas is satisfiable, and determining which one is satisfiable identifies uf. Repeating this procedure for all i [n] yields an assignment v, which satisfies C if and only if C is satisfiable.
For each n E N define a = 2(n + 1) and 3 = 64800n log (1n Suppose that there is poly (oly(n)-tim algorithm which, given 0 θ B. computes an approximation of log Ze with additive error less than n log 1.16. Then given two formulas C and C with n variables and at most 10n clauses each, we can compute 0 OC,, 3) and 0' OC",, a, 3). By Lemma A.2, we have 0, 6' E θg so long as B 2 Cn² for sufficiently large constant C. Hence by assumption we can compute approximations Zo and Zgr of Zg and Zør respectively, with multiplicative error less than 1.16 However, by Lemma A.6 and the assumption that exactly one of C and C" is satisfiable. know that Zo Zo if and only if C is satisfiable. Thus, NP RP.
Let > 0 be chosen later.
A.3 Hardness of approximating first-order oracle
Lemma A.7. Let be a 3-CN with m clauses and n variables, and exactly one satisfying assignment v² H. Let An and 3 25920mn log(102 and define p = PC,a,3 and = Z- Then Eggp [u x.] Z 1/20 for all i E [n].
Proof. Without loss of generality take i = 1 and of = 1. Set r = 1/(v648mm), a = 4n, and 40r log( (n/r). We want to show that Ez-p(z) [21] 1/20. We can write
E E[r1] = B[x [a E (v( )]] B[r, 1/x O(v)) \ B, (b*)]]
Σ DERA(())
E[r, O(v)]
2 (1 - r) Pr(z E By(o"))
max oEA(fe'
E E[m O
(6)
since æ1 2 1 r for x E By")) and x 2 for x E (()).. Now observe that on the one hand,
c e-1-81mar*
(1,0 exp(-x" -Bg(a)) dx
Pr(x E (x))))
Z
13

---

by Lemma A.3. On the other hand, for any v E H. | {o"}.
||| [1|z e [ =
1 //2 Z (o(0)
1.000
|21|es exp
- Σ
z
aH(()) -BG(x) dr
1=1
$ c-a
Z (o(o)
Lal cxp
-
Σ i=1
n
xx - -G((
dx
a
(%/
(1/0 exp(-x² (xp(-xx-Bg(x)) dx
n-1
I eexp(-22 xxxp 3g(xx)) dx
2e a
expl -x - BB(xx)) dx
(8)
where the second inequality is by Lemma A.9 with k = 1. Combining (7) and (8) with (6), we have
r)e 81mar2
2nntle-a
B[ri] 2
exp(-x² - -Bg(x)) dx
Z
10Z (1x-
exp(-x² exp(-x"-Bggr)) -B9(z)) dx
Σ z aH(x) - pC(()) de
cxp
10Z )Ow0)
1
Pr[æ O(v")
10
1
20
where the second inequality is by choice of a and r; the third inequality is by nonnegativity of H (z); and the fourth inequality is by Lemma A.4 and uniqueness of the satisfying assignment v*.
Proof of Theorem 3.5. Suppose that such an algorithm exists. Set = 4n and ,3 129600m² log( (102n2 v5).. Given a 3-CNF formula C with n variables, at most 5n clauses, and exactly one satisfying assignment
E H. we can compute / = (CC, a, 3). Let E R." be the algorithm's estimate of V log Ze g (xx). Then E Ex-re... Txx) Ilo < 1/20. But by Lemma A.7, for each i E [n). the i-th entry of Exxpe.... T (z). which corresponds to the monomial Jy has sign o/ and magnitude at least 1/20. Thus, sign( FE,) of- So can compute 8² in polynomial time. By Theorem A. it follows that NP = RP.
A.4 Integral bounds
Lemma A.8. Fix 3 > 150 and [0, 1]. Define f - RR f(x) - + +1311 x2)2. Pick any r (6/3, 0.04). Then
1- 1 2exp (Brp(()/40)
1+r
dx
exp(- (xx(-f(x)) dx.
r
1-1
In particular, for any m E if 2 -2 100-2lo0mm//// then
10 exp exp(-f(zz) do - 1 1
/ 1-r
1+r
exp(-f(x)) de.
Proof. Set a 1/v2. For any E [a, os) we have f"(x) 56 43 + 123x² > B > for 3 > 150. Thus, f has at most one critical point in (a, oo); call this point l0 Since (((x) =
8yz7 "y="-48x(1-23 we have (1( 87 2 0 and (1-3//3 < 8--4(1133/8)8//16 3/3)
Thus, to E (1 - 1/33,111 1]. Set r' = - 3/B 2 r/2. Then
Nots'
exp(- exp(-f(z)) dx >
-oor exp(-f(x)) dz.
14

---

For every E E define [tt) = l.tt" exp(-f(z)) dr. Since f 3-strongly convex on (a, oc), we have for any t 2 to that
r/2 f(t f(tr))(()22-))) +
p/2 2
B2
where the final inequality is because (t( 2 0 for E 00). Thus, for any 2 to.
t+r ((t+r)= = J.m exp(-f(z)) dx J.
2+
exp(-f(x + r²)) dx exp(-3r (2)
By induction, for any & E N it holds that [[to + kr') S exp(- /t)b///))/((t).....))))))))))>)) so
I(lo)
exp(-J(x)) de =
T(lo + kr') S T(6))
Σ
exp(-xBkit 1oon-BKin Bkr (2) = 1 exp(-3rr211 (9)
k=
h=0
Similarly, for any E la + r', lo]. we have
,²
r22 3
- -()))
-
2 2
using B-strong convexity on (a, 00) and the bound ('( S on [a, to). Thus, for any E |a, to - r'),
I(t [(t-r))= = [ p-
exp(-f(x)) dx = f. grts"
exp(-f(z r')) dr S <xxp(-6r"
so by induction, 1(to - kr) S exp(- 3(k /2)r///2)((t)))) -r) for any 1 k k It follows that
K == L(to - a)/r')
K (lo-krr) < 1 1lto-rlrr expl exp(-3(k-1)rf11) <
1 - -r'
exp(-f(x))dzz de = Σ
1o- Kr
exp( 13 1Brp /2) (10)
k=1
Finally, note that t0 (K 1)r' < <a a 2r < 0.8. For any x E [0, 00,).8) we have ('( < 8x
0.723x = x(8x. - 1.443) < O, since 3 > 150. That is, I is non-increasing on [0, l0 - (K- - 1)rl..
It follows that
to Kr'
10 Kr' (KK-
exp(-5(x)) dx S
exp(-I(x)) dx
rd Ko-Kr
1
< T(lo - Kr')
exp( (B((K 1)r /2)
[ r¹).
rd
Since (K 1)r' to - 0.8 1
0.8 2 0.1, we conclude that
exp(- 33r
exp(- dx I
I[to r¹).
(11)
r'
Combining (9), (10), and (11), we get
1
(oo(-Br/20))
Noto'
exp(-f(x)) dx < Substituting in r' 2 r/2 gives the claimed result.
i 1- cixxx(1Brr222)
expl-s(x)) dr.
r'
Lemma A.9. Fix 3 2 160 log(8.). Then for any S k 58.
| k exppp=s> - 3(1 - 2² dx s 2h l exp(-xx - -3(1 - x²)2) do.
15

---

Proof. Define a distribution ((2) x exp(-x² - = -2))) for oo). We want to show that
[x & 2h. Indeed,
Io exp(-B(1 x²)))) dr
By ex(eep(2 (2
Jo exp(-xt - 3(1 - x²) dr
2 J1/2 exp(-3(1 - 22 )
Jo exp(- --x B(1 x²)2) dr
2 (exp(2 |1 v x s 3/2]
S 2 exx((33/2))
where the first inequality is by an application of Lemma A.8 with 1/2 and m 1. Now by Jensen's inequality we get
E, s log E,(exp(x*)) = log(2) + (3/2)* 2
and consequently, an application of Hölder inequality gives us [x1x]] 2 for any 1 S k S
A.5 Proof of Corollary 3.6
Proof of Corollary 3.6. Recall that log (o())()) = logh(x) + (0, - log Zo. Therefore
(M) = E log h(z) + (0, (x)) - log Ze and VeLMLE(O) = ET(x) log Zg. Note that we compute E log (xx) and (z)) exactly. It follows that if we approximate (M)E(0) up to an additive error of n log 1.16. then we can compute log Zn up to an additive error of n log 1.16. Similarly, if we can compute V (0) up additive error of 1 1/20, then we can compute Vo log Zo up to an additive error of 1/20. This contradicts Theorems 3.4 and 3.5 respectively, completing the proof.
B Moment bounds
Lemma B.1 (Moment bound). For any 0 E On i E [n]. and & E N holds that Euzoa of 32f max B M)2ttaat+)))
Proof. Without loss of generality assume 1. Let To 32 max(e, BM2d+1). Then
s I Lo + Ex-pp -11x===1 > Lo]
= 1o +
Expoo [of Lo < 1| & 2 La]]
k=0
Now for any L > Lo.
a 1[ < |l0/ I 22b]
1
of exp - - d+1 + (0. ((x)))))) dx
Zo Bar. (01.B.))
(2L)a (2L)² exp (-I + (2T)))
Zo
(2T.) exp(-I,a+) /2)
Zo
We can lower bound Zg as
a
Zo 2
exp
d+1 (0,T(x)) dr Σ
x
(1((BM)(O)
2 (BM) exp(-n(BM)
-d- d-1 BM(BM)-1)
2 2BM))
16

---

Thus,
1 - +2 2
E [ < 10
2 exp
(n (n+ E) log(21)
logg (oMg(
[
exp
where the last inequality uses the facts that 2 Lo, B 2 1, and M 2 n to get
L
L
3L
I I
(n + E) log(2L) + 2 log(BM) S max(n, 8)
5
16
16
16
We conclude that
( 222
E Exmpo 01 $ 1/
Σ exp
k=0
S Lo +
S 2
which completes the proof.
Lemma B.2 (Largest eigenvalue bound). For any 0 E BB it holds that
Ex T(x)T(x) B2d 22dd+++22)))))++-1
We also have the following consequences:
(a) [B ( < B M 24+ 222222204000
(b) Amar (I(O)) Bdd M2d+ 124+1122((44)))
(c) Praapo 1| 2 < 1/2.
Proof. Fix any u, v E [M]. Then TT),,((), IT x7" for some nonnegative integers Mir.. The where d' = Ei 7 S 2d. Therefore
Ez-po ((x) = Exane II a < II ) 76/6
< 32d (
by Holder's inequality and Lemma B.1 (with é 2d). The claimed spectral bound follows. To prove
(a), observe that
Ex-py T(x) Ex-po [T(x))1 = TrEppp (x))T(x) & M Dama (Euop, (Bx))
To prove (b), observe that I(0) ~ Exnps T(x)T(x)T To prove (C), observe that for any E [n]]
Ex x2
1
Pr [| 2d+8 n <
BB 2m.
union bound over E [n] completes the proof.
Lemma B.3 (Smoothness bounds). For every O E On, it holds that
M
Ex-pp := Σ
E E (AT;(x)) & n² ad Bdd 21
and
E Exzopo
[I]T) < n²
2u 3d++22dd(++))++++
Proof. Fix any j E [M]; then there is a degree function with 1 s |d| S so that T₃(x) = Ia
Therefore Ih 24 d(i)
(T)
Σ ((k) 1) =: (wxx()
(k)))
17

---

for some E IR M with 1|wl12 = ExEln)a())2 d()) - 1)2 I d² By Corollary B.2, we conclude that
Eampo (z) Ex- (w, T(x))² I dd gdd M M
Summing over j [M] gives the first claimed bound. For the second bound, observe that
M ΣΣ sm1
Or. (5((0) 1500))
Ex (x) I Ezrpo [I(T) = Exrupo
For any E [M] and [n], there some degree function d with |d| I d and - (x())
|d| zd za- (1). Thus, by Holder's inequality and Lemma B.1 (with l 4d), we get
2
M 12
( (o,,
E Ezaopo
ΣΣ
E S E
E Expoo
dxy Ty(())
dx
0z,
$ M d Bdd Mrdggddid+0)++
which proves the second bound.
The following regularity conditions are sufficient for consistency and asymptotic normality of score matching, assuming that the restricted Poincaré constant is finite and Ami (O())) > (see Proposition 2 in Forbes and Lauritzen (2015) together with Lemma in Koehler et al. (2022)). We show that these conditions hold for our chosen exponential family.
Lemma B.4 (Regularity conditions). For any 0 RM, the quantities Ez-po [Vh(z))
Egepp || [T and Ez-po [I(J) lop are all finite. Moreover, po(x) - 0 and V.
0 as |22|| + cc.
Proof. Both of the quantities Vh(())] and |]T(())] be written polynomial in æ. Finite- ness of the expectation under py follows from Holder's inequality and Lemma B. (with parameter B set to ).0))oo). Finiteness of Ez~yp [I( is shown in Lemma B.3 (again, with B = |00l)o)). The decay condition po po(x) -> 0 holds because log po (0() + log Zo En= gdt1 (0,)())) For x E Rn with < ||=||,x < 2L, the RHS is at most - _ + M |00 (2L)a, which goes to -o as L + 00. A similar bound shows that [>)p(<>) + 0.
C Omitted Proofs from Section
Proof of Lemma 4.2. We use the fact that the Legendre polynomials
Lx(x)
Σ 1=0
1)-- (-)
k
(0-
2
2
for integers 0 < k < d, form an orthogonal basis for the vector space R[x]ga with respect to L 1] (see e.g. Koepf (1998)). We consider the normalized versions L. =v 22+11 Lt, that
i 1911.11 = 1. By tensorization, the set of products of I Legendre polynomials
La(x) = II (2.))
as d ranges over degree functions with |d] S d, form an orthonormal basis for Inlea with respect [[][(,,
Using the formula for Lg. we obtain that the sum of absolute values of coefficients of Lg (in the monomial basis) is at most o Ej-o (+)
2* 22k By the bound I|-l|, S ||-Ih and the definition of
i..
1
<
2h: +
L
S
2h + 1 24k
mon
2
2
18

---

and hence for any degree function d with |d| S d.
2d(i) - -2
La
II
Laro)
mon
mon
2
Am
a(1) 2(()))(())) - (16e)*.
Consider any polynomial R[ mo En and write holds that Ej
Ejdlsa ad La By orthonormality
-1 Thus, by the triangle inequality and Gauchy-Schwarr
||
|pllimn
Σ dd/dd
Latia
Σ
ad
Σ dd/sa
I
dd
mon
(m (16e)²
nn
|I [|
as claimed.
Proof of Lemma 4.3. Let [ 3 sa be polynomial of degree most d in 21,..... .n
Define g(x) = f(x: Ex (x:). Set c 1 1/(2(d + () B)) and let (W;) be balls
of radius partitioning {a E R ||>|| c0 I R). Define random variable X x| S R) and let c / be the random index that X W,. Then
(fr = Expp)(<>)
B))(X)
2
E, E,Ex(o(X))1X E W.)
2
where the inequality uses guarantee (c) of Lemma B.2 that Pl > R] S 1/2.
Thus, there exists some t" such that Ex (x(] W.-] 2 2 Varp Let q: R R4 be the density function of X|X E W.-, Since q(x) X p( E W.-]. for any u W,- we have that
((u) ((v)
p(u) huu) exp T(u)))
p(v)
h(v) exp( T())))
exp Σ
d+1
u d+1 + (O,T(w))T(o))
-(w))
Applying Lemma C.I, we get that
g(u) ((v)
S exp (n(d + 1) 1) ||u - -oc-vll-- MBI a())la)
I exp ((n + B) () M(d+1) (u- xl1
I exp(22(n + B)
1)R")
S exp(1)
by choice of e. follows that if the uniform distribution on W.,, then g(x) 2 e((((x)) for all R. Thus,
1 > 2e
1 Vary(9)
1
Varp(f) Exlo(X) w.-1
Varg (f)
2e
2e
as desired.
Lemma C.1. Fix For any degree function d [n] N with |d| s and for any u, T
with |||]aa || I R. it holds that
ddRd d1 ||u 1
Ud
val
19

---

Proof. Define m(x) = =I 4;
d(i) Then
Im(u) m(v) - I|u 0
sup
=cBn(0)
sup ||u v01
Σ ru) ())))
32
1
dR
claimed.
Proof of Lemma 4.4. By Lemma 4.3, there is some E R" with ||=1000 I R and some 2 1/(2(d + (n + B)) so that if l is the uniform distribution on {xr E IR || 211o0 S c). then
1
Var,(f)
(arg(f).
2e
Define V - by ((x) = flea + 2) - Eg Then by Lemma 4.2,
|191lmon S (16e)* M
(16e) M (arg(()
< (16e) M Var,(f).
Write f(x) = - aada and g(x) Eislalaa Saxd. We know that f(x) = g(c-1(x 2))
Egs. Thus, for any nonzero degree function d, we have
Σ -- (-z)d'- 3a
ad
d'2d (d Id
Thus loal 6 dR |13111 S 5 M Igl and so summing over monomials gives Il I 2dd p2dd
|| I (16c) - R2d (fr
Substituting in the choice from Lemma 4.3 completes the proof.
D Omitted Proofs from Section
Proof of Lemma 5.1. We have
Varpo po (f) = Exynpo [f(x) Earpo (fx)))
w E' [T(x]T(z) JJw w Ee-po [x)) [T(x)] (Tx))
w I(O)w,
and since
|| Amin (I(0)) & w I(O) I 2|l11 Amna (I(O),
the lemma statement follows.
Proof of Lemma 5.3. Since f(x) = - Ward, we have for any RR that
(u. vuf(x))) = Σ Σ
(1 + d d (()())aaa()za c(u) +
w(u)aaa
osidicd
1 <d
where c(u) == Ei= (:iii and w(u)a En Gi ui(1 + d(i) (1)- But now
E Ex-po [I Es (u. (x))
- P (c(u) + (w( T(x))) clu)² + /h (w)ll
Ee-N((,.L)) 4 4 Bzzpp [
min (1, Amin (I(O)))
20

---

where the last inequality is by Lemma 5.2. Finally,
(w-N( (c(u)² + [|v((u))
Σ BowN(U
Σ us(1
+ddi))
0. [s/d|cdd
E od
Σ (1 (1+ (a+
2
where the second equality is because E|uuy,
Dí j] for all i [n]], and the last inequality is
because every term wa in ||ll| appears in at least one the terms of the previous summation (and has coefficient at least onc). Putting everything together gives
|
Egaep [[) 2
4+ Epwpo IT (=)] min(1, Annin (I(I)))
min Amia (I(O)))
Varpo (f)
4 4+4
Amax (I()))
where the last inequality is by Lemma 5.1.
21


Reviews:
[{"review_id": "M7lT1r0Ss9", "reviewer": "Reviewer_fYcf", "summary": "The paper attempts to elucidate the theoretical reasoning for the benefits seen in score matching. The author proposes a family of exponential distributions that can efficiently compute the score matching loss while having a comparable statistical efficiency to that of maximum likelihood. ", "questions": "- What is the benefit of using this score matching method than taking the denoising score matching approach?\n- Is this approach more computational efficient than denoising score matching? How well those this score matching approach scale for high dimensional data?", "limitations": "The author has adequately addressed limitations.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written/organized and easy to follow. The author does a good job introducing related theoretical information.\n- Equations are extensively described with a thorough description.", "weaknesses": "- There are no experimental results. It would be nice if there were some machine learning models that were optimized with score matching and ML and compared with each other. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. To address the reviewer's questions:\n\n**Q:** *``What is the benefit of using this score matching method than taking the denoising score matching approach?''* Recall that the latter is score matching applied to an annealed version of the distribution. It's generally believed that the annealing improves the statistical performance of score matching. It's also generally believed that score matching (even without annealing) has computational benefits over MLE. The goal of this paper was to provide a provable example of the latter. The fact that annealing may further improve statistical efficiency in a sense only strengthens the thesis of our paper: that the score matching technique has provable computational benefits over the standard MLE technique, without sacrificing statistical efficiency.\n\n**Q:** *``Is this approach more computational efficient than denoising score matching? How well those this score matching approach scale for high dimensional data?\"* For exponential families, the score matching loss is quadratic, so the global optimum actually has a closed-form expression (see equation (2) in the paper), which can be computed in time polynomial in the number of sufficient statistics and linear in the number of samples. In high dimensional settings one might be interesting in even stronger computational guarantees, but we have not yet investigated whether this is possible, and if it is would likely require new techniques.\n\nIt's possible that the denoising score matching loss could also be optimized efficiently, but it's not immediately clear one way or the other."}, {"review_id": "KhlhNCBohU", "reviewer": "Reviewer_bZrt", "summary": "In this paper, the authors present a mathematical setting where Score Matching (SM) method has more statistical benefits than Maximum Likelihood (ML) technique, when estimating a parameterized probability distribution $p_\\theta \\in P(\\mathbb{R}^n)$ known up to a normalizing constant $Z_\\theta$. In particular, they describe an explicit exponential family of distributions $F$ for which SM loss $L_{SM}$ is efficient to compute, with same statistical efficiency as ML loss $L_{ML}$ (Theorem 2 and 3), while $L_{ML}$ is shown to be intractable in polynomial time depending on the parameters of this family (Theorem 1). Given an odd integer $d$ and $B>0$, any distribution $p_\\theta \\in F$ is notably defined by (i) its vector of sufficient statistics, which consists of all monomials in $x^1,..., x_n$ of at least degree $1$ and at most degree $d$, and (ii) its parameter $\\theta$, which lies in the $\\ell_\\infty$-ball with radius $B$. This work is the first one to put in perspective the statistical efficiency of SM and ML for a large family of continuous probability distributions. \n\n\nThree main theoretical results are stated here. In Theorem 1, the authors prove that, for any $p_\\theta \\in F$ (with $d=7$) and any set of $N$ independent samples from $p_\\theta$, it is NP-hard (in $n$ and $N$) to provide an accurate approximation of $L_{ML}(\\theta)$ and $\\nabla L_{ML}(\\theta)$. This result comes from the difficulty to approximate $Z_\\theta$, which is necessary to compute $L_{ML}(\\theta)$, while it does not appear in $L_{SM}(\\theta)$. In Theorem 2, they derive an upper bound of the $\\ell_2$-error between $\\theta$ and its ML estimator obtained via $N$ samples, in the limit where $N\\to \\infty$, for any $p_\\theta \\in F$. Their proof relies on the asymptotic result given by [1] and consists of lower bounding the smallest eigenvalue of the Fisher information matrix of $p_\\theta$. In Theorem 3, they derive the same upper bound in the case of the SM estimator for any $p_\\theta \\in F$, by invoking the asymptotic result from [2] and bounding the Poincaré constant of $p_\\theta$. Combined together, Theorems 2 and 3 show that ML and SM techniques roundly have the same statistical efficiency.\n\n[1] Asymptotic statistics, Van der Vaart, 2000.\n\n[2] Statistical Efficiency of Score Matching: The View from Isoperimetry, Koehler et al., 2022.", "questions": "Why do the authors do not keep the whole dependence in $d$ in the bound for Theorems 2 and 3 ? Does it change something between SM and ML ?", "limitations": "In this work, the asymptotic theory is elaborated on the fact that the MLE and SM estimators can be computed exactly from a collection of samples. However, to compare these two techniques for practical purpose, one should include approximation error on the estimator.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- This work provides a fair comparison between statistical efficiency for SM and ML technique, which is of primary interest for the community of machine learning.\n- Although Theorems 2 and 3 rely on important theoretical results, their results are not straightforward to obtain, and their proofs are original and clear to understand.", "weaknesses": "Although the theoretical results presented here are interesting in their own, they should be combined with numerical experiments, which should illustrate the trade-off between these two methods in practice, depending on the parameters of the exponential family.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. To address the reviewer's questions:\n\n**Q:** *``Why do the authors do not keep the whole dependence in $d$ in the bound for Theorems 2 and 3 ? Does it change something between SM and ML ?''* In both cases the dependence is $O(d^3)$. We stated the dependence as $\\textsf{poly}(d)$ in the introduction just to make the theorems cleaner \\--- we are thinking of $d$ as a small constant, and the key takeaway is that for both score matching and maximum likelihood, the sample complexity is $\\textsf{poly}(n,B)$. It's certainly plausible that maximum likelihood may achieve a smaller constant in the exponent than score matching; proving such a statistical separation is an interesting direction for future work but complementary to the purpose of this work, which is to establish conditions under which they achieve comparable rates.\n\n**Q:** *``In this work, the asymptotic theory is elaborated on the fact that the MLE and SM estimators can be computed exactly from a collection of samples. However, to compare these two techniques for practical purpose, one should include approximation error on the estimator.''* It's true that there may be some approximation error in computing the MLE from finite samples (even ignoring our evidence that this task may be computationally intractable). However, as shown in Equation (2) in our paper, the score matching estimator has a closed form in our setting, so there is no approximation error."}, {"review_id": "8sEEVuGYrZ", "reviewer": "Reviewer_xxrR", "summary": "This paper provides an example of fitting exponential family models for which score matching \nand MLE are both statistically efficient, but MLE is computationally hard to optimize. ", "questions": "1. Why constant is removed from the construction of the sufficient statistics?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strength is in the construction of an example to showcase the benefit of score matching \nover MLE. ", "weaknesses": "Several aspects  could be improved. \n\n1. First, for the computational lower bound, the points to evaluation loss and gradient is worst case. \nWhen one has samples from such distribution, is solving MLE still computationally hard? \n\n2. Although the aim of this paper is to provide examples to advocate for score matching, but for the \ndistribution family proposed in the paper, are there simple (or simpler) estimators that are both computationally and \nstatistically efficient? \n\n3. In the paper, the analysis of the statistical performance is quite crude, which makes it hard to see what's \nthe statistical cost one needs to pay when computation is the restriction. Is there proper computation-statistic \ntradeoff for the model considered in the paper? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and comments. To address their questions:\n\n**Q:** *``First, for the computational lower bound, the points to evaluation loss and gradient is worst case. When one has samples from such distribution, is solving MLE still computationally hard?''* Good question; unfortunately proving NP-hardness of average-case problems (i.e. when the input is drawn from a nice distribution) is generally not doable. One alternative is to prove a reduction from some conjecturally average-case hard problem such as Planted Clique, but average-case reductions are notoriously tricky. A final alternative common in theoretical computer science is to prove failure of some restricted class of algorithms (e.g. low-degree polynomials). \n\nAll these alternatives are potentially doable, but would become technically involved and stray from the crux of the matter \\--- with enough samples, score matching and MLE are essentially just two different techniques for solving the same computational problem, so our main goal with the worst-case computational lower bounds is to illustrate computational difficulties faced by a standard implementation/analysis of MLE.\n\n**Q:** *``Although the aim of this paper is to provide examples to advocate for score matching, but for the distribution family proposed in the paper, are there simple (or simpler) estimators that are both computationally and statistically efficient?''* We are not aware of any other computationally and statistically efficient estimators for this family. Perhaps the closest related work is the following paper, which suggests a computationally efficient estimator for learning some exponential family distributions. However, they require the family to have bounded support, in addition to several (rather complex) norm assumptions.\n\nShah, Shah, and Wornell. \\emph{``A Computationally Efficient Method for Learning Exponential Family Distributions\".}\n\n**Q:** *``In the paper, the analysis of the statistical performance is quite crude, which makes it hard to see what's the statistical cost one needs to pay when computation is the restriction. Is there proper computation-statistic tradeoff for the model considered in the paper?''* Understanding the statistical cost of score matching at a more fine-grained level is an interesting direction for future work. It is possible that score matching matches the statistical efficiency MLE, although it seems more likely there is some polynomial gap. Speaking more broadly, we are not aware of *any* continuous exponential family with a provable statistical/computational tradeoff. Of course, proving such a lower bound is orthogonal to the purpose of this work, which was simply to show that score matching is roughly as efficient as MLE without the computational drawbacks. But this is still useful context and helps explain why proving lower bounds and separations is challenging even for exponential families. We will add this discussion.\n\n**Q:** *``Why constant is removed from the construction of the sufficient statistics?''* Including a nonzero constant as a sufficient statistic wouldn't actually change the family of distributions captured, since an additive constant in the exponent of the density is canceled out by the constant of proportionality. Note that as a result the parameter corresponding to the constant statistic would not even be statistically identifiable. This shows up in Lemma 4.4, where if we allowed e.g. the constant polynomial $f=1$, this has variance $0$ but monomial norm $1$ so the lemma would not be true."}, {"review_id": "KZ5CNn10T9", "reviewer": "Reviewer_BCHk", "summary": "The authors describe an exponential family where the sufficient statistic $T(x)$ contains all non-constant monomials of degree $\\leq d$, the background density is $h(x) = \\exp(-\\sum_{i=1}^n x_i^{d+1})$, and the parameter $\\theta$ is constrained to have infinity norm bounded by $B$. Using a reduction from $3\\mathsf{SAT}$, they show that under this exponential family, finding the MLE is NP hard, and thus unless $\\mathsf{NP} = \\mathsf{RP}$, that it would take time exponential in the random vector dimension $n$ to compute the MLE. \n\nThey also show that the MLE has asymptotic sample efficiency $(nB)^{O(d^3)}$. They show that score matching also has asymptotic sample efficiency $(nB)^{O(d^3)}$. Unlike the MLE, score matching can be solved in time polynomial in the dimension of $\\theta$, which if $d$ is considered constant, is polynomial in $n$. This is because the objective corresponding to score matching is convex in $\\theta$.\n\nThis is a concrete example of a situation where score matching has a provable advantage over the MLE (same asymptotic sample efficiency, but one needs exponential time unless $\\mathsf{NP} = \\mathsf{RP}$ and the other is polynomial time).", "questions": "- Why is a nonzero constant not allowed for the polynomial defined by the sufficient statistic of the exponential family? It wasn't clear to me, also why that was a requirement for Lemma 4.4 to hold. Does that cause a problem?\n\n- This does not appear necessary to have in this work to me, but how close are we to obtaining finite sample bounds for score matching, analogous to the ones (I assume there are?) for MLE?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- clear contribution\n- relevant related work is discussed\n- this is a significant result (rigorous justification for potential benefit of score matching over MLE)", "weaknesses": "No glaring weaknesses, but the paper was a bit difficult to follow; I found it hard to connect the math-heavy theorem/lemma statements together. For example, I did not understand how Lemmas 4.2 and 4.3 built toward Lemma 4.4 on my initial read. \n\nTypos spotted:\n- Equation under line 172, $\\|\\theta\\|_2^2$ should be $\\|\\theta^*\\|_2^2$?\n- Line 482, $f''(x) = 56\\gamma x^6 - 2\\beta + 6\\beta x^2$ should be $f''(x) = 56\\gamma x^6 - 4\\beta + 12\\beta x^2$ I think, but this doesn't affect anything\n- Lemma A.6, the $(2/e)^n$ should be replaced with $(e/2)^n$\n- Math at the bottom of page 16, second line, you want to minimize the exponent so instead of $-BM(BM)^{-d}$ it should be $-BM(BM)^{-1}$ right? I don't think this affects anything though since you bound it by $-1$ regardless\n- Math under line 519, I'm not sure that $(n+\\ell)\\log(2L) + 2 + n\\log(BM) \\leq \\frac14 L^{d+1}$, unless some lower bound on $d$ is assumed? Like I'm not sure if that holds for $d=1$?\n- Lemma B.3, bound on Laplacian in the Lemma statement doesn't seem to match the derivation (exponent of 2d vs 4d)\n- Line 564 - this appears to be claiming that $\\sum_{j=0}^k \\binom{k}{j}^2 = 2^k$, which is false? I think you could bound it by $2^{2k}$ though by Cauchy-Schwarz, so it probably doesn't matter, just changes some constants down the line.\n- Line 573 - $B_\\iota \\to W_\\iota$\n- Line 583 - $\\alpha_i \\to d_i$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and for a very careful reading. We'll fix the typos -- as the reviewer notes, a few constants will have to be updated but the main results are all unchanged (up to some constant factors in the exponents). To be a bit more precise about the more mathematical typos:\n\n**Q:** *``Math at the bottom of page 16''* You're entirely right, it should be $-BM(BM)^{-1}$; as you say this doesn't change anything.\n\n**Q:** *``Math under line 519\"* Instead of $L_0 := \\max(\\ell, BM2^{d+1})$ we should define $L_0 := 32\\max(\\ell,BM2^{d+1})$. Now in line 519, since $L \\geq L_0$ and $B \\geq 1$ and $M \\geq n$, we can show that $\\frac{1}{4}L^{d+1} \\geq (n+\\ell)\\log(2L) + 2 + n\\log(BM)$. Indeed $(n+\\ell)\\log(2L) \\leq 2\\max(n,\\ell) \\cdot L \\leq L^2/16$. Similarly $2 \\leq L^2/16$ and $n\\log(BM) \\leq L^2/16$. Finally $L^2 \\leq L^{d+1}$. This adds a constant factor of $32^\\ell$ to the moment bound in the lemma statement, which is not substantive.\n\n**Q:** *``Lemma B.3''* Yes, thanks, we'll update the statement to match the derivation (the exponents are off by a factor of $2$).\n\n**Q:** *``Line 564''* Yes, since each binomial is at most $2^k$ we can bound the stated quantity by $2^{2k}$, which changes a constant in the exponent.\n\n**Q:** *``Why is a nonzero constant not allowed for the polynomial defined by the sufficient statistic of the exponential family? It wasn't clear to me, also why that was a requirement for Lemma 4.4 to hold. Does that cause a problem?''* Including a nonzero constant as a sufficient statistic wouldn't actually change the family of distributions captured, since an additive constant in the exponent of the density is canceled out by the constant of proportionality. Note that as a result the parameter corresponding to the constant statistic would not even be statistically identifiable. This shows up in Lemma 4.4, where if we allowed e.g. the constant polynomial $f=1$, this has variance $0$ but monomial norm $1$ so the lemma would not be true.\n\n**Q:** *``This does not appear necessary to have in this work to me, but how close are we to obtaining finite sample bounds for score matching, analogous to the ones (I assume there are?) for MLE?''* We believe that it's probably possible to get analogous finite-sample guarantees by similar techniques. In particular, the prior work by Koehler, Hecket, and Risteski (which shows that the asymptotic efficiency of SM and MLE are related via a restricted Poincare constant) also shows that the finite-sample efficiency can be bounded in terms of a restricted log Sobolev constant and a Rademacher bound. It's certainly not immediate from our results, but we would speculate that our techniques for bounding the restricted Poincare constant can extend to bounding the restricted log Sobolev constant, and that the Rademacher complexity should be bounded via standard arguments. It would then remain to convert the KL-divergence error bound (obtained in Theorem 1 of their work) into a parameter error bound, which ought to follow from our bounds on the Fisher information."}]

Author rebuttal:

Meta-review: This paper theoretically explains the success of score matching by showing that it _can_ be simultaneously computationally and statistically efficient, when the MLE is not. Reviewers agree that this is a significant contribution that is worth sharing with the community. That said, there are some suggestions that could considerably improve the paper. First, a visualization of the results either in terms of synthetic experiments or computational/statistical behavioral comparison between MLE and SM, would help better appreciate the theory. Second, even though prior methods to establish efficient learning make additional assumptions (e.g. Shah et al. 21), a better comparison would be fruitful. Third, the narrative and presentation could be improved. The significance of the main and intermediate results are indeed explained. However, a more top to bottom strategy could help appreciate the analysis: instead of listing lemmas then the theorem, it could help to sketch the theorem first and highlight where the lemmas are needed, and then state them. The authors are also encouraged to incorporate the other minor comments and suggestions raised by the reviewers.
Decision: Accept (spotlight)