Statistical Efficiency of Score Matching: The View from Isoperimetry
Authors: Frederic Koehler
Alexander Heckett
Andrej Risteski
Venue: ICLR 2023 notable top 5% (2023)
Keywords: score matching
log-Sobolev inequality
isoperimetry
relative efficiency
sample complexity

Abstract:   Deep generative models parametrized up to a normalizing constant (e.g. energy-based models) are difficult to train by maximizing the likelihood of the data because the likelihood and/or gradients thereof cannot be explicitly or efficiently written down. Score matching is a training method, whereby instead of fitting the likelihood $\log p(x)$ for the training data, we instead fit the score function $\nabla_x \log p(x)$ --- obviating the need to evaluate the partition function. Though this estimator is known to be consistent, its unclear whether (and when) its statistical efficiency is comparable to that of maximum likelihood --- which is known to be (asymptotically) optimal. We initiate this line of inquiry in this paper, and show a tight connection between statistical efficiency of score matching and the isoperimetric properties of the distribution being estimated --- i.e. the Poincar\'e, log-Sobolev and isoperimetric constant --- quantities which govern the mixing time of Markov processes like Langevin dynamics. Roughly, we show that the score matching estimator is statistically comparable to the maximum likelihood when the  distribution has a small isoperimetric constant. Conversely, if the distribution has a large isoperimetric constant --- even for simple families of distributions like exponential families with rich enough sufficient statistics --- score matching will be substantially less efficient than maximum likelihood. We suitably formalize these results both in the finite sample regime, and in the asymptotic regime. Finally, we identify a direct parallel in the discrete setting, where we connect the statistical properties of pseudolikelihood estimation with approximate tensorization of entropy and the Glauber dynamics.


Published as a conference paper at ICLR 2023
STATISTICAL EFFICIENCY OF SCORE MATCHING: THE VIEW FROM ISOPERIMETRY
Frederic Koehler
Alexander Heckett
Stanford University
Carnegie Mellon University
fkoehle erdstanford.edu
tieckettt@andreee cmu cdd
Andrej Risteski
Carnegie Mellon University
aristeske andrew. cmu, edu
ABSTRACT
Deep generative models parametrized up to a normalizing constant (e.g. energy- based models) difficult to train by maximizing the likelihood of the data be- cause the likelihood and/or gradients thereof cannot be explicitly or efficiently written down. Score matching is a training method, whereby instead of fitting the likelihood log for the training data, we instead fit the score function V log p(z) obviating the need evaluate the partition function. Though this estimator is known to be consistent, its unclear whether (and when) its statistical efficiency comparable that of maximum likelihood (asymptotically) optimal. We initiate this line of inquiry in this paper, and show a tight connection between statistical efficiency of score matching and the isoperi- metric properties of the distribution being estimated - i.e. the Poincaré, log- Sobolev and isoperimetric constant - quantities which govern the mixing time of Markov processes like Langevin dynamies. Roughly, show that the score matching estimator is statistically comparable to the maximum likelihood when the distribution has small isoperimetric constant. Conversely, if the distribution has a large isoperimetric constant even for simple families of distributions like exponential families with rich enough sufficient statistics score matching will be substantially less efficient than maximum likelihood. We suitably formalize these results both in the finite sample regime, and in the asymptotic regime. Fi- nally, we identify a direct parallel in the discrete setting, where we connect the statistical properties of pseudolikelihood estimation with approximate tensoriza- tion of entropy and the Glauber dynamics.
which is known be
INTRODUCTION
Energy-based models (EBMs) are deep generative models parametrized up to a constant of parametrization, namely p(x) ex)( The primary training challenge the fact that eval- uating the likelihood (and gradients thereof) requires evaluating the partition function of the model, which is generally computationally intractable even when using relatively sophisticated MCMC techniques. The seminal paper of Song and Ermon (2019) circumvented this difficulty by instead fitting the score function of the model, that is log p(z). Though not obvious how evaluate this loss from training samples only, Hyvärinen (2055 showed this can be done via integration by parts, and the estimator is consistent (that is, converges
correct value the limit of infinite samples).
The maximum likelihood estimator is the de-facto choice for model-fitting for its well-known prop- erty of being statistically optimal in the limit where the number of samples goes to infinity (Van der Vaart 2000 It is unclear how much worse score matching can be thus, it's unclear how much statistical efficiency we sacrifice for the algorithmic convenience of avoiding partition functions. In the seminal paper (Song and Ermon 2019), dimensional manifold structure may cause difficulties for score matching. Though the intuition for this is natural: having poor estimates for the score in "low probability" regions of the distribution
conjectured that multimodality, well as a low-

---

Published as a conference paper at ICLR 2023
can "propagate" into bad estimates for the likelihood once the score vector field is "integrated" making this formal seems challenging.
We show that the right mathematical tools to formalize, and substantially generalize such intuitions are functional analytic tools that characterize isoperimetric properties of the distribution in question. Namely, we show three quantities, the Poincaré, log-Sobolev and isoperimetric constants (which are all in turn very closely related, see Section 2). tightly characterize how much worse the efficiency of score matching is compared maximum likelihood. These quantities can be (equivalently viewed as: (1) characterizing the mixing time of Langevin dynamics - a stochastic differential equation used sample from a distribution p(z) x exp(f(xx), given access to a gradient oracle for f: (2) characterizing "sparse cuts" in the distribution: that is sets S. for which the surface area of the set can be much smaller than the volume of S. Notably, multimodal distributions, with well- separated, deep modes have very big wwwooole/ooincar//iippreiiiiiiie 2004 2005). as do distributions supported over manifold with negative curvature (Hsu) (002) (like hyperbolic manifolds). Since it is commonly thought that complex, high dimensional distribution deep generative models are trained to learn do in fact exhibit multimodal and low-dimensional mani- fold structure, our paper can be interpreted as showing that in many of these settings, score matching may be substantially less statistically efficient than maximum likelihood. Thus, our results can be thought of formal justification of the conjectured challenges for score matching in [Song and Ermon (2019), as well as a vast generalization of the set of "problem cases" for score matching. This also shows that surprisingly, the same obstructions for efficient inference (i.e. drawing samples from a trained model, which is usual done using Langevin dynamics for EBMs) are also an obstacle for efficient learning using score matching [[ We roughly show the following results:
constants (Gayrard et al.)
1. For finite number of samples n, we show that if we are trying to estimate a distribution from a class with Rademacher complexity bounded by Rn, as well log-Sobolev constant bounded by CLS, achieving score matching loss at most implies that we have learned distribution that's s no more than cC,s'R, away from the data distribution in KL divergence. The main tool for this is showing that the score matching objective is at most a multiplicative factor of Cr.s away from the KL divergence to the data distribution.
2. In the asymptotic limit (i.e. the number of samples of estimating the parameters of a probability distribution of an exponential family {po (x) oc exp((0, ((r))) for some sufficient statistics F using score matching. If the distribution pa we are estimating has Poincaré constant bounded by Cp have asymptotic efficiency that differs by at most factor of Cp.. Conversely, we show that if the family of sufficient statistics is sufficiently rich, and the distribution pe we are estimating has isoperimetric constant lower bounded by Cis, then the score matching loss is less efficient than the MIE estimator by at least a factor of Crs-
oc), we focus the special case
3. Based
new conceptual framework, we identify precise analogy between score matching in the continuous setting and pscudolikelihood methods in the discrete (and continuous) setting. This connection is made by replacing the Langevin dynamics with its natural analogue the Glauber dynamics (Gibbs sampler). We show that the approximation tensorization of entropy inequality (Marton| 2013 Caputo et al., (015),, which guarantees rapid mixing of the Glauber dynamics, allows us to obtain finite-sample bounds for learning distributions in KL via pseudo- likelihood in an identical way the log-Sobolev inequality for score matching. A variant of this connection is also made for the related ratio matching estimator of Hyvärinen (2077).
In Section 7 we perform several simulations which illustrate the close connection between isoperimetry and the performance of score matching. We give examples both when fitting the parameters of an exponential family and when the score function is fit using a neural network.
PRELIMINARIES
Definition 1 (Score matching). Given smooth ground truth distribution p with sufficient decay at infinity and a smooth distribution g, the score matching loss (at the population level) is defined to be
(p( =
2 Ex-p //ooo
1
llgg
=xx=p
1 Tr 1o
2 I log qll2 (I)
Note, there is another popular variant of score matching called denoising score matching, in which the data distribution is convolved with Gaussian. This will not be the focus of this paper.
2

---

Published as a conference paper at ICLR 2023
where Kp is a constant independent of q. The last equality is due to Hyvärinen (203)_ Given samples from p. the training loss Jo(g) is defined by replacing the rightmost expectation with the average over data.
Functional and Isoperimetric Inequalities. Let g(x)) be a smooth probability density over Rd A key role in this work is played by the log-Sobolev, Poincaré, and isoperimetric constants of closely related geometric quantities, connected to the mixing of the Langevin dynamics, which have been deeply studied in probability theory and geometric and functional analysis (see e.g. (Gross et al. 2014)). We discuss the background in more detail in Appendix
1975 Ledoux] 2000)
Definition 2. The log-Sobolev constant Cr.((q) 0 is the smallest constant so that for any smooth probability density we have
(L(p.)) q) S Czs(q)I(p)) q) X))] is the Kullback-Leibeer divergence or relative entropy
where KL(P, 4) = (o)ppplopp((((((() and the relative Fisher information I(p] q) is defined as I(p q) :- E, log
The log-Sobolev inequality is equivalent to exponential ergodicity of the Langevin dynamics for q. a canonical Markov process which preserves and is used for sampling q, described by the Stochastic Differential Equation d.X,, = -V log ((X,) x2) di + /22 dB. The log-Sobolev constant can be bounded for log-concave distributions: if P a-strongly log concave, then CLS S 1/2a by Bakry- Emery theory (Bakry et al.) 2014). See Appendix for details.
For class of distributions P. we can also define the restricted log-Sobolev constant CLs(q, P) to be the smallest constant such that (2) holds under the additional restriction that E P - see e.g. Anari et al. (202Tb). For P an infinitesimal neighborhood of p. the restricted log-Sobolev constant of q becomes half of the Poincaré constant or inverse spectral gap Cplg):
Definition 3. The Poincaré constant Cp(g) 2 0 is the smallest constant so that that for all smooth functions f : Rd + R.
Var,(') & Eggg) It is related to the log- log-Sobolev constant by Cp S 2CLs (Lemma 3.28 of Van Handel (2014)).
Both of these inequalities measure the isoperimetric properties of q from the perspective of func- tions; they are closely related to the isoperimetric constant:
Definition 4. The isoperimetric constant Crs(g) (g) is the smallest constant, s.1. for every set S,
min (1 ((x))ar Isc ((x))x < Cis(a) lim inf c-0
Ss. -
(4)
where S. = (x: d(x, S c) and d(xr, S) denotes the (Euclidean) distance of x from the set S. The isoperimetric constant is related to the Poincaré constant by Cp < 4C*s (Proposition 8.5.2 of 1/2, the left hand side can be interpreted
Bakry et al. (2014)) Assuming is chosen so gg((a)d as the volume and the right hand side as the surface area of S with respect to q.
Mollifiers We recall the definition of one of the standard mollifiers/bump functions. as used in e.g. Hörmander (2015). Mollifiers are smooth functions useful for approximating non-smooth functions: convolving function with mollifier makes it "smoother", in the sense of the existence and size of the derivatives. Precisely, define the (infinitely differentiable) function vi : .Rd - as vi(y) 11111(1) for |u| < 1 and (yyy) = O for |yl 2 1, where Ga == f 11111111 For > O. also define "sharpening" of th, namely voy (1) > (1//7) so that f bby
Notation. For random vector X, Σx == XXX E [[ denotes its covariance matrix.
LEARNING DISTRIBUTIONS FROM SCORES: NONASYMPTOTIC THEORY
Though consistency of the score matching estimator was proven in Hyvärinen (205)), it is unclear what one can conclude about the proximity of the learned distribution from a finite number of sam- ples. Precisely, would like a guarantee that shows that if the training loss (i.e. empirical estimate
"hheee are several alternatives formulas for I(p q). see Remark 3.26 of Van Handel 2014
3

---

Published as a conference paper at ICLR 2023
of L is small, the learned distribution is close to the ground truth distribution (e.g. in the KL divergence sense). However, this is not always true! We will see an illustrative example where this is not true in Section 7 and also establish general negative result in Section 4
Our first new observation is that understanding the multiplicative gap between the KL divergence and the score matching test loss is equivalent understanding log- log-Sobolev constants. Based on this, prove (Theorem D that minimizing the training loss does learn the true distribution, assuming that the class of distributions we are learning have bounded complexity and small log-Sobolev constant. First, we formalize the connection to the log-Sobolev constant:
Proposition 1. The log-Sobole log-Sobolev inequality for q is equivalent to the following inequality over all smooth probability densities p:
KL(P. q) S 2Ccs(a)() J.p())
(5)
More generally, for a class of distribution p E P the restricted log-Sobolev constant is the smallest constant such that KL(p, q) S CLslg, (J - Jy())) for all distributions p.
Proof. This follows from the following equivalent form for the relative Fisher information (Shao et al. 2019 Vempala and Wibisono 2019)
I(pl q) E, (V V log P
q
= Ep - v log :
= E log
P V log
P
Epl logp V Vloggl?
(6)
Using this and ① the log-Sobolev inequality can be rewritten as KL q) I CLs(1p(9) - (p)) which proves the first claim, and the same argument shows the second claim.
Remark (Interpretation of Score Matching). The left hand side of (5) is KL q) Epllogp E. Dlg g) The first term is independent of and the second term is the likelihood, the objective for Maximum Likelihood Estimation. So (5 shows that the score matching objective is a relaxation via the log-Sobolev inequality. We discuss connections to other proposed interpretations in Appendix B
(within a multiplicative factor Cr.((g) (g)) of
Remark 2. Interestingly, the log- log-Sobolev constant which appears in the bound is that of q and not the ground truth distribution. This is useful because is known to the learner whereas p is only indirectly observed. If is actually close to p, the log-Sobolev constants are comparable due to the Holley-Stroode perturbution principle (Proposition 5.1.6 of Bakry el al. (0144).
To our knowledge, we are the first to point out the useful connection of the score matching loss with the log- log-Sobolev inequality. Because log- Sobolev constants have been well-studied, this observation has many nice consequences which would otherwise be difficult to prove. Combining Proposition T bounds on log- log-Soeolev constants from the literature, and generalization theory gives knite-sample guarantees for learning distributions in KL divergence via score matching.
Theorem 1. Suppose that P is a class of probability distributions containing and define CLs(P, P) == sup CLs(q, P) S sup,er CL.(q) to be the worst-case (restricted) log- tog-Sobolev constant in the class of distributions. Let
n 6
R₂ = Ex, Exi
sup Σ PEP
Tr 2 (X),) + | log q(x.))p
be the expected Rademacher complexity of the class given n samples XI...,, Xn ~ p i.idd. and in- dependent (1....,6 'n Uni + i.idd. Rademacher random variables. Let & be the score matching estimator from n samples, i.e. p arg arggmnggp Jz(9). Then
EKL(p.P) p) S 4CIs(P,P\RR
In particular, if CCs((P P) < then lim E KLL P) 0 as long lima R, 0.
We use the simplest version of Rademacher complexity bounds to illustrate our techniques. Standard liter- ature, e.g. SShalev-Swaarzz and Ben-David (2014); Bartlett et (200)) contains more sophisticated versions, and techniques readily generalize.
4

---

Published as a conference paper at ICLR 2023
Proof. By the standard symmetrization argument (Theorem 26.3 of Chalev-Shward and Ben- David (2114)) we have E.p(P) 1p(p) $ 2R,, so by Proposition we have E (p P) S
LE - Jz(p)) 4CIs
Example 1. Suppose we are fitting an isotropic Gaussian in d dimensions with unknown mean 1r" satisfying || I R. The class of distributions P is 9u with |pIll I R of the form 4p(z) &
exp (-1 r -xll(/2) ||1|=~1 so the expected Rademacher complexity can be upper bounded as so:
1 R, Esup M n
d/2+ + ||x - m11
-MIl
G
= =Esup 1 Σ 2=1
1 -
1 Σ c
R + d
M
= RE
c.X,
S
R R
E
B
H
where the inequality is Jensen's inequality and in the last step we expanded the square and used that [ege,- = 1(i= and [=|| 112 S. R² + d. Recall that the standard Gaussian distribution is 1-
strongly log concave CLS 1/2. Hence we have the concrete bound E (L S 2Rv ad
4 STATISTICAL COST OF SCORE MATCHING: ASYMPTOTIC RESULTS
In this section, we compare the asymptotic efficiency of the score matching estimator in exponential families to the effiency of the maximum likelihood estimator. Because we are considering asymp- totics, we might expect (recall the discussion in Section 2 that the relevant functional inequality will be the local version of the log-Soboler inequality around the true distribution p, which is the Poincaré inequality for p. Our results will show precisely how this occurs and characterize the situations where score matching substantially less statistically efficient than maximum likelihood.
Setup. In this section, we will focus on distributions from exponential families. We will consider estimating the parameters of an exponential family using two estimators, the classical maximum likelihood estimator (MLE),, and the score matching estimator; will use that the score matching estimator arg ming (p admits a glosed-form formula in this setting.
Definition 5 (Exponential family). For sufficient statistics F Rd + R", the exponential family of distributions associated with is {po (x:) xx cxp ((0, F(x))) 10 E
Definition 6 (MLE, Van der Vaart (2000)). Given i.i.d. samples 21....,Ir, pa, the maximum likelihood estimator is 0MLE arg max È [og por (X)), where E denotes the expectation over the samples. As n + and under appropriate regularity conditions, we have vn (0MLE 0) N [0. where I MILE Ep¹ and Ff is known the Fisher information matrix.
Proposition 2 (Score matching estimator, Equation (34) of Hyvvärnen (2007)). Given i.i.d. samples where
TI,...,Ta En ~ Pa, the score matching estimator equals 0SM = (JF))) (JF)x x d is the Jacobian of F at the point X, Aʃ -, ʃ is the Laplacian and it is applied coordinate wise to the vector- valuur- function F.
4.1 ASYMPTOTIC NORMALITY
Next, we prove asymptotic normality of the score matching estimator and give formula for the limiting renormalized covariance matrix T Since the MLE also satisfies asymptotic normality with an explicit covariance matrix, we can then proceed in the next sections compare their relative efficiency (as in e.g. Section 8.2 of Van der Vaart (2000)) by comparing the asymptotic covariances sM and I MLEE- The proof of the following result is in Appendix C
Proposition 3 (Asymptotic normality). As + JC, and assuming sufficient smoothness and de- cay conditions so that score matching is consistent (see Hyvärinen (2005)) we have the following
convergence in distribution: vni(0sM - 0) + (0, where
T == (((JF)x(JF)XX (
Asymptotic normality was proved in Corollary 1 of SSng et al. 2020) reprove it because in the context of exponential families, will show and use much simpler expression for the limiting covariance.
5

---

Published as a conference paper at ICLR 2023
4.2 STATISTICAL EFFICIENCY OF SCORE MATCHING UNDER POINCARÉ INEQUALITY
Our first result will show that if we are estimating a distribution with a small Poincaré constant (and some relatively mild smoothness assumptions), the statistical efficiency of the score matching estimator is not much worse than the maximum likelihood estimator.
Theorem 2 (Efficiency under a Poincaré inequality). Suppose the distribution satisfies Poincaré inequality with constant Cp. Then we have
||T SP 20% MElloo (101 + EIJAF12)
More generally, the same bound holds assuming only the following restricted version of the Poincaré inequality: for any w, Var((w, F(x))) S C Fx)))1
Remark 3. To interpret the terms in the bound, the quantities Ep (PFFl((F) llóp and E||A| can be seen as measure of the smoothness of the sufficient statistics F, and ||0|| as a bound on the radius of parameters for the exponential family. In Section 7 we will give an example to show bounded smoothness indeed necessary for score matching to be efficient. direct con- sequence of this result (see Appendix D is that with 99% probability and for sufficiently large n, (s002 < (nEEll0 0 O (Cam [[F)) (
B(AF(12) tribution is smooth and Poincaré, score matching achieves small & ervor provided MLE does. We illustrate Theorem for a natural example of a bimodal distribution in Example of Appendix(C
So if the the dis-
The proof of Theorem 2 in Appendix D and the main lemma to prove the theorem is the following:
Lemma 1. ([(JF)(JF)
EpEp where Cp is the Poincaré constant of po-
Proof. For any vector w E IRm", we have by the Poincaré inequality that
Cp(w, ((n,B((())xx)( = CpE F(x) 2 Var((w, F(x))) = (w, ΣFw)
This shows CpF( EF and inverting both sides gives the result.
4.3 STATISTICAL EFFICIENCY LOWER BOUNDS FROM SPARSE CUTS
In this section, prove converse Theorem 2 whereas small (restricted) Poincaré constant upper bounds the variance of the score matching estimator, if the Poincaré constant of our target dis- tribution is large and we have sufficiently rich sufficient statistics, score matching will be extremely inefficient compared to the MLE. In fact, we will be able to do so by taking an arbitrary family of sufficient statistics, and adding a single sufficient statistic Informally, we'll show the following:
Consider estimating a distribution pe in an exponential family with isoperimetric constant CJs. Then, po can be viewed as member of an enlarged exponential family with one more (1as(1)- Lipschitz) sufficient statistic, such that score matching has asymptotic relative efficiency Pas compared to the MLE, where OS denotes the boundary of the isoperimetric cut of pa and Das indicates constant depending only on the geometry of the manifold Os.
As noted in Section 2 a large Poincaré constant implies a large isoperimetric constant so we focus on showing that the score matching estimator is inefficient when there is set S which is "sparse cut". Our proof uses differential geometry, so our final result will depend on standard geometric properties of the boundary 0S (in terms of how small y is, see Appendix E for more discussion, proof sketch, as well as the full proof). We now give the formal statement.
Theorem (Inefficiency of score matching in the presence of sparse cuts). There exists an absolute constant e > 0 so that the following is true. Suppose S is a set with smooth and compact boundary as, and suppose that pot is an element of an exponential family with sufficient statistic F1 and parametericed by elements of 1r Define an additional sufficient statistic Fz 1s 1py so that the enlarged exponential family contains distributions with 0₁ E 00,02 E R of the form
(1)) x exp((01, (x))) + (2))
and consider the MLE and score matching estimators in this exponential family with ground truth Prer, 0)- Suppose that 1 is not an affine function of Fi, and so there exists some on such that

---

Published as a conference paper at ICLR 2023
Sup Cov
Fur .1)
1s
11 51. Then for all 7 sufficiently small in terms of S,
(ar((un,FF))) ())(1ss
there exists a vector w such that the asymptotic relative (in)efficiency of the score matching estimator compared the MLE for estimating (w, 0) admits the following lower bound
(w, I ISMW))
c' *min [Pr(X E S), Pr(X & S)}
(w. I MLEW)
SEEOS p(æ)dx
7
VI-
Nlssas péride: IXXEEXI-PXXEN
provided d' = cd
> 0.
Remark 4. If !fwe choose S to be the set achieving the worst isoperimetric constant, then the right hand side of the bound is simply & SCis- (See the appendix for details.) Finally, we observe that 7[
although d' is exponentially small in d, the bound is still useful in high dimensions because in the bud cases of interest Cıs often exponentially large in d. For example, this is the case for a mixture of standard Gaussians with D2( ((Vd) separation between the means (see e.g. Chen et al. (021a))
Remark 5. The assumption 82 is quantitative way of saying that the function 1, the we are using to define the new sufficient statistic F2, is not already a linear combination of the existing sufficient statistics. The assumptions will always holds with some 81
by the Cauchy- Schwarz inequality. The equality case is when 1s is an affine function of (w), F1) if such a linear dependence exists, the parameterization is degenerate and the coefficient of F2 not identifiable.
Example 2. A concrete example in one dimension with single sufficient statistic is
1 a (xr a) aa² - + x²
Fi(x)
a² a²/8
and 0- 01,0) for parameter Gaussians centered at -a and a. Specializing Theorem 31o to this case, we get:
to be laken large. This looks similar mixture of standard
Corollary There exists absolute constants "oo > and >> O so that the following is true. Suppose that a > 1, 0 (1,0), and expunded exponential family {po for with po (x) x exp (00', (Fi(x), (2(x))) and new sufficient statistic F2 is the output of Theorem applied to Fi, S {x > 0}. and y To. Then there exists that the relative (in)efficiency of estimating (w, 0) is lower bounded as
(we, Tarw))
1
(w, MLEW)
5 DISCRETE ANALOGUES: PSEUDOLIKELIHOOD, GLAUBER DYNAMICS, AND APPROXIMATE TENSORIZATION
Several authors have proposed variants of matching for discrete probability distributions, e.g- (009)): Shao et al. (2019): Hyvärinen (2007). Furthermore, HHyvärinen (2006) 2007) pointed out some connections between lseudolikelihood methods (a classic alternative maximum likelihood in statistics Besag 1975 1977)), Glauber dynamics (a.k.a. Gibbs sampler, see Appendix F for the definition), and score matching. Finally, just like the log-lobolev inequality controls the rapid mixing of Langevin dynamics, there are functional inequalities (Gross) 1975] Bobkov and Tetali, 2006) which bound the mixing time of Glauber dynamics. Thus, we ask: there a discrete analogue of the relationship between score matching and the log-Soboley inequality?
The answer is yes. To explain further, we need a key concept recently introduced by Marton (2013) 2015) and [apuuo al. (2015): if FI), (Ra, are arbitrary measure spaces, we say distribution q on X 0 Q2 satisfies approximation tensortzation of entropy with constant CAT (q) if
KL(P,g) S CAT(a) (K_.-p_, X-i), | X..))]
This inequality is sandwiched between two discrete versions of the log-Sobolev inequality (Propo- sition 1.1 Caputo et al. (2015)): is weaker than the standard discrete version of the log-Sobolev inequality (Diaconis and Caltef-Coste. 1996) and stronger than the Modified Log-Sobolev Inequality
7

---

Published as a conference paper at ICLR 2023
(Bobkov and Tetali 2006) which characterizes exponential ergodicity of the Glauber dynamics. We define a restricted version CAT (g. P) analogously to the restricted log-Sobolev constant.
Finally, we recall the pseudolikelihood objective (Besag 1975 based on entrywise conditional prob- abilities: (g(g) = Ei= Ex-pllog (X;: Xx:)]. With these definition in place, we can show that just as matching objective is a relaxation of maximum likelihood through the log-Sobole inequality, pseudolikelihood a relaxation through approximate tensorization of entropy:
Proposition 4. We have KL(p, q) S CCr(g)(L,,)))) containing p. we have KL(p, 9) S Ca, ()
Lp(g)) and more generally for any class P Lp(g))
Proof. Observe that (p(p) - -p( Ei Ex..R_. [L[p(XX]] X Xxs))], so the result follows by expanding the definition.
Remark 6. Pseudolikelihood methods (and variants like node-wise regression) one of the dom- inant approaches to fitting fully-observed graphical models, e.g. (Wu et al.) 2019: Lokhov et al. 2018 Klivans and Meka 2017 Kelner al. 2020). Like score matching, pseudolikelihood meth- ods do not require computing normalizing constants which can be slow or computationally hard (e.g. (yyy and Sun (2012)). ). Pseudolikelihood is applicable in both discrete and continuous settings, as is our connection with approximate tensorization. An analogous version of Theorem | holds by the same argument (Theorem [ in Appendix 7 and guarantees learning in KL when q satisfies approximate tensorization (e.g. under Dobrushin s uniqueness threshold (Marton 2015))
Remark 7. [[yvärinen 2007) proposed version of score matching for distributions on the hyper- cube { =1] and observed that the resulting method (" ("ratio matching" ") bears similarity to pseudo- likelihood. A similar calculation as the proof of Proposition 4 allows us to arrive at ratio matching based on a strengthening of approximate tensorization studied in (Marton 2015). Our derivation seems more conceptual than the original derivation, explains the similarity to pseudolikelihood, and establishes some useful connections. For space reasons, this is included in Appendix F.2
6 RELATED WORK
Score matching was originally introduced by Hyvärinen (2005), who also proved that the estimator asymptotically consistent. In (Hyvärinen 2007), the authors propose estimators that are defined over bounded domains. (Song and Ermon 2019) scaled the techniques to neurally parameterized energy-based models. leveraging score matching versions like denoising score matching Vincent (011). which involves an annealing strategy by convolving the data distribution with Gaussians of different variances, and sliced score matching (Song al., 2020). The authors conjectured that annealing helps with multimodality and low-dimensional manifold structure in the data distribution and our paper can be seen as formalizing this conjecture.
The connection between score matching objective and the relative Fisher information in (6) was previously observed in (Shao et al. 2019 Nielsen (002T.. We also remark that since I(pl4)
de [L q) It=o for Pt the output of Langevin dynamics at time f, score matching can be inter- preted as finding q minimize the contraction of the Langevin dynamics for g started at p. Previ- ously, (Lyul 2009) observed that the score matching objective can be interpreted as the infinitesimal change in KL divergence we add Gaussian noise see Appendix B for an explanation why these two quantities are equal. In the discrete setting, it was recently observed that approximate ten- sorization has applications to identity testing of distributions in the "coordinate oracle" query model Blancc et al. 2022), which is another application of approximate tensorization outside of sampling otherwise unrelated to our result. Finally, (Block et al.) 2020; Lee et al.) 2022) show guarantees on running Langevin dynamics, given estimates on V log that are only e-correct in the (2(p) sense. They show that when the Langevin dynamics are run for some moderate amount of time, the drift between the true Langevin dynamics (using V log p exactly) and the noisy estimates can be bounded.
7 SIMULATIONS
Exponential family experiments. Fitting bimodal distribution with and without statistic approximating a cut. First, we show the result of fitting a bimodal distribution (as in Example 2 from an exponential family. In Figure [ the difference of the two sufficient statistics we consider
8

---

Published as a conference paper at ICLR 2023
corresponds to the cut statistic used in our negative result (Theorem 3 score matching performs poorly compared to the MLE as the distance between modes grows.
As predicted (Corollary I
In Appendix G show that when the second sufficient statistic (which is correlated with sparse cut in the distribution) is removed, score matching performs nearly as well as MLE. This what our theory predicts (since the statis- tic is removed) and illustrates the use of re-
Store matching
stricted functional inequalities (in Theorem
the restricted Poincaré inequality explains what happens here - see the appendix).
Fitting unimodal but not smooth distribution. For space reasons this is left to Appendix G we demonstrate that, even if the distribution is unimodal, the performance of score matching degrades as the sufficient statistics become less smooth. Hence the dependence on smoothness in our results, e.g. Theorem is really required.
Figure 1: Statistical efficiency of score matching vs MLE for fitting the distribution with ground truth parameters (0o. 01) (1,0) of the form po(a) x eBo("" "x" (224") as we vary the offset a between and 7 and train with fixed number of samples (10%). We see score matching (red) performs very poorly compared to MIE (blue) as the offset (distance between modes) grows, by plotting the log of the Fuclidean distance to the true parameter for both estimators.
(<all)+
Fitting a mixture of Gaussians with a one- layer network. We also show that empirically, our results are robust even beyond exponen- tial families. In Figure we show the results of fitting mixture of two Gaussians via score matching where the score function is param- eterized as one hidden-layer network with tanh activations. We see that the predictions of our theory persist: the distribution is learned successfully when the two modes are close and is not when the modes are far. This matches our expectations, since the Poincaré, log-Sobolev, and isoperimet- ric constants blow up exponentially in the distance between the two modes (see e.g. [Chen et al.) (2021a)) and the neural network is capable of detecting the cut between the two modes. We discuss the interpretation of this result more in the appendix.
022
98
Figure 2: Training a single hidden-layer network score match mixture of Gaussians (ground truth green, score matching output blue) succeeds at learning the distribution when the modes are close (left, small isoperimetric constant), but not when they are distant (right, large isoperimetric constant) in which case it weighs the modes incorrectly.
CONCLUSION
In this paper, we initiate the study of the statistical efficiency of score matching, and identified close connection to functional inequalities which characterize the ergodicity of Langevin dynamics. For future work, it would be interesting to characterize formally the improvements conferred by annealing strategies like (Song and Ermon 2019), like has been done in the setting of sampling using Langevin dynamics (Lec et al. 2018).
'We note that this experiment is similar in flavor to plots in (Figure 2) in Song and Ermon 2019 where they show that the score is estimated poorly near the low-prohability regions of mixture of Gaussians. In our plots, we numerically integrate the estimates of the score produce the pdf of the estimated distribution.

---

Published as a conference paper at ICLR 2023
Acknowledgements: Frederic Kochler acknowledges support by NSF award CCF-1704417 NSF award IIS- 1908774, and N. Anari's Sloan Research Fellowship. Andrej Risteski acknowledges sup- port by NSF awards IIS-2211907 and CCF-2238523, Amazon Research Award "Causal Deep Out-of-Distributiio Learning".
REFERENCES
Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong, Entropic independence high-dimensional expanders: Modified log-sobolev inequalities for fractionally log-concave polynomials and the ising model. arXiv preprint arXiv:2/06.04 2021a.
Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong. Entropic independence optimal sampling and concentration via restricted modified log-sobolev inequal- ities. arXiv preprint (tt::///1.0244: 2021b.
Dominique Bakry, Ivan Gentil, Michel Ledoux, et Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014.
Peter L. Bartlet, Olivier Bousquet, and Shahar Mendelson. Local rademacher complexities. The Annals of Statistics, 33(4); 1497-1537, 2005.
Julian Besag, Statistical analysis of hon-lattice data. Journal of the Royal Statistical Society: Series D (The Statistician), (433):19-1199 1975.
Julian Besag. Efficiency of pseudolikelihood estimation for simple gaussian fields. Biometrika, pages 616-618, 1977.
Antonio Blanca, Zongchen Chen, Daniel Stefankovič, and Eric Vigoda. Identity testing for high- dimensional distributions via entropy tensorization. arXiv preprint arXiv:2207.09102, 2022.
Adam Block, Youssef Mrouch, and Alexander Rakhlin. Generative modeling with denoising auto- encoders and langevin sampling. arXiv preprint arXiv:2002.00107, 2020.
Sergey G Bobkov. An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in gauss space. The Annals of Probability, 25(1):206 224, 1997.
Sergey G Bobkov and Prasad Tetali. Modified logarithmic sobolev inequalities in discrete settings. Journal of Theoretical Probability, 19(2):289-334 2006.
Pietro Caputo, Georg Menz, and Prasad Tetali. Approximate tensorization of entropy at high tem- perature. In Annales de Faculté des sciences de Toulouse: Mathématiques, volume 24, pages 691-716, 2015.
Hong-
Hong-Bin Bin Chen, Sinho Chewi, and Jonathan Niles Weed. Dimension-free sobolee inequalities for mixture distributions. Journal of Functional Analysis, 281 (11): 10:1333,,, 2021a
Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1537-1550, 2021b.
Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
Persi Diaconis and Laurent Saloff-Coste Logarithmic sobolev inequalities for finite markov chains.
The Annals of Applied Probability, 6(3):695-750, 1996.
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
Herbert Federer. Curvature measures. Transactions of the American Mathematical Society. 93(3): 418-491, 1959.
Véronique Gayrard, Anton Bovier, Michael Eckhoff, and Markus Klein. Metastability in reversible diffusion processes i: Sharp asymptotics for capacities and exit times. Journal of the European Mathematical Society, 6(4):399 2004.
10

---

Published as a conference paper at ICLR 2023
Véronique Gayrard, Anton Bovier, and Markus Klein. Metastability in reversible diffusion processes ii: Precise asymptotics for small eigenvalues. Journal of the European Mathematical Sociery, (1):69-99, 2005.
Alfred Gray. Tubes, volume 221. Springer Science & Business Media, 2003.
Leonard Gross. Logarithmic sobolev inequalities. American Journal of Mathematics, 97(4))1061- 1083, 1975.
Lars Hörmander. The analysis of linear partial differential operators I: Distribution theory and Fourier analysis. Springer, 2015.
Elton P Hsu. Stochastic analysis on manifolds. Number 38. American Mathematical Soc., 2002.
Aapo Hyvärinen. Estimation of non-normalized statistical models by score matching. Journal of Machine Learning Research, 6(4), 2005.
Aapo Hyvärinen.
Consistency of pseudolikelihood estimation of fully visible boltzmann machines. Neural Computation, (S(10):2233-2992 2006.
Aapo Hyvärinen. Some extensions of score matching. Computational statistics data analysis, (5):2499-255 2007.
Jonathan Kelner, Frederic Koehler, Raghu Meka, and Ankur Moitra. Learning some popular gaus- sian graphical models without condition number bounds. Advances in Neural Information Pro- cessing Systems, 33: 33:10986-10998, 2020.
Adam Klivans and Raghu Meka. Learning graphical models using multiplicative weights. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 343-354. IEEE, 2017.
Michel Ledoux. The geometry of markov diffusion generators. In Annales de la Faculté des sciences de Toulouse: Mathématiques, volume 9, pages 305-366, 2000.
Holden Lee, Andrej Risteski, and Rong Ge. Beyond log-concavity: Provable guarantees for sampling multi-modal distributions using simulated tempering langevin monte carlo. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Asso- pas.cccpppperr201///11.
ciates, Inc., 2018. URL h pdf
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence for score-based generative modeling with polynomial complexity. arXiv preprint arXiv:2206.06227, 2022.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathe- matical Soc., 2017.
Andrey Lokhov, Mare Vuffray, Sidhant Misra, and Michael Chertkov. Optimal structure and parameter learning of ising models. Science advances, 4(3):e 2018.
Siwei Lyu. Interpretation and generalization of score matching. In Proceedings of the Twenty-Fifth Conference on Uncertainty Artificial Intelligence, pages 359-366, 2009.
Katalin Marton. An inequality for relative entropy and logarithmic sobolev inequalities in euclidean spaces. Journal of Functional Analysis, 264(1):34-61, 2013.
Katalin Marton. Logarithmic sobolev inequalities in discrete product spaces: proof by trans- portation cost distance. arXiv preprint arXiv: 2015.
Frank Niclsen. Fast approximations the jeffreys divergence between univariate gaussian mixtures via mixture conversions to axponential-polyoone
distributions. Entropy, 23(1 (111):1117, 2021.
Partha Niyogi. Stephen Smale, and Shmuel Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 39(1):419- 441, 2008.
11

---

Published as a conference paper at ICLR 2023
Shai Shalev-Shwarle and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Stephane Shao, Pierre E Jacob, Jie Ding, and Vahid Tarokh. Bayesian model comparison with the hyvärinen score: Computation and consistency. Journal of the American Statistical Association, 2019.
Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In 2012 IEEE 53rd Annual Symposium Foundations of Computer Science, pages 361- 369. IEEE, 2012.
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
Yang Song. Sahaj Garg, Jiaxin Shi, and Stefano Ermon. Sliced score matching: scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence, pages 574-584. PMLR, 2020.
Aad W Van der Vaart. Asymptotic statistics, volume 3. Cambridge university press, 2000.
Ramon Van Handel. Probability in high dimension. Technical report, PRINCETON UNIV NJ, 2014.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm:
Isoperimetry suffices. Advances in neural information processing systems, 32, 2019.
Pascal Vincent. connection between score matching and denoising autoencoders. Neural compu- tation, 23(7):1661-1674 2011.
Hermann Weyl. On the volume of tubes. American Journal of Mathematics, 61(2):661-472, 1939.
Shanshan Wu, Sujay Sanghavi, and Alexandros G Dimakis. Sparse logistic regression learns all discrete pairwise graphical models. Advances in Neural Information Processing Systems, 32, 2019.
A FURTHER BACKGROUND
Correspondence between functional inequalities and exponential ergodicity. Pe the dis- tribution of the continuous-time Langevin Dynamics
R for started from Xo p, then I(p g) = d. KL(Pt,g) 9) I-- and so by integrating KL(P,, q) < e t/Crs KL(p.g) q). This holding for any P and is an equivalent characterization of the log-Sobolev constant (Theorem 3.20 of Van Han- del (2014). Similarly, the Poincaré inequality implies exponential ergodicity for the x2 divveeegee x" (p., g) e e-2t/Cr (p. 4). and this holding for every and t is an equivalent characterization of the Poincaré constant (Theorem 2.18 of Van Handel 22014).
de
We can cquivalently view the Langevin dynamics in functional-analhe way through its definition as a Markov semigroup, which is equivalent to the SDE definition via the Fokker-Planck equation Van Handel 2014 BBkkyy et al. 2014). From this perspective, we can write pt qH, 2 where He
the Langevin semigroup for q, so H. = L with generator
Lʃ = V log4, V + Af.
In this case, the Poincaré constant has direct interpretation in terms of the inverse spectral gap of L, i.c. the inverse of the gap between its two largest eigenvalues.
Further remarks. A strengthened isoperimetric inequality (Bobkov inequality) upper bounds the log-Sobolev constant, see Ledoux 2000); Bobkov (197)..
SSee e.g. Vempala and Wihisono/ 2019) for more hackground and the connection to the discrete time dy- namies.
12

---

Published as a conference paper at ICLR 2023
Facts about the mollifier dh We will use the basic estimate 8 8 Gd < BB where Ba is the volume of the unit ball in IRd, which follows from the fact that e- 1n(²) 2 1/4 for llvll S 1/2
and e --1/(1-lal*) < everywhere. It is infinitely differentiable and its gradient is
vybly) - (2/Ga)e 1/01 (1v1))))
(1 11/1312 (1 || 4(2)
2y
It is straightforward check that supy VI (v)ll 1 1/Ga. For y O, we'll also define "sharp- ening" of v,, namely (v) = 7 "v/0/1 /7) so that J |by = and (by chain rule)
-2y/7²
V Vydi(()
(Vb)u/)) (1 11//> 34 (2/7)
so in particular ,V, S 5 --1-
Reach and Condition Number of a Manifold. For smooth submanifold .M of Euclidean space, the reach TM the smallest radius r so that every point with distance at most r to the manifold M has a unique nearest point on M (Federer 1959); the reach is guaranteed to be positive for compact manifolds. The reach has a few equivalent characterizations (see e.g. NNyogg et al. (2008)); a common terminology is that the condition number of manifold is 1 1/TM-
B RECOVERING LYU'S INTERPRETATION OF SCORE MATCHING
As mentioned, the connection between score matching objective and the relative Fisher information was previously observed, for example in (Shao al. 2019 Nielsen 2021 We also remark that if we use the fact I(plq) = d KL(pe. q) It=u. the score matching objective has a natural interpretation in terms of select q to minimize the contraction of the Langevin dynamics for q started at p. On the other hand, Lyu (209)) previously observed that the score matching objective can be interpreted as the infinitesimal change in KL divergence between p and q as we add noise to both of them. We now explain why these two quantities are equal by giving a proof of their equality (which is shorter than the one you get by going through the proof in Lyu (2009)).
de
Before giving the formal proof, we give some intuition for why the statement should be true. The Langevin dynamics approximately adds noise of size (0, 2t) and subtracts gradient step along V log and this dynamics preserves q. For small t, the gradient step is essentially reversible and preserves the KL. So heuristically, reversing the gradient step gives KL(pt, 4) KL(N 21) p, N (0, 21)= q). We now give the formal proof.
Lemma 2. Assuming smooth probability densities p(x) and q(x) decay sufficiently fast at infinity,
d KL(p 2) 1= dt dt
d
KL(p= x NO,, 2t). q NO, 26)) 1=
where * denotes convolution.
Proof. Recalling from Appendix K KL g) = E. log 2 and
A that He e we have that d Pr 4 H d dr
L. Since r log = log + 1, it follows by the chain rule that
q
d KI(p,, = Ey [1o0 P +
I 9
= Eg
P +1 log 9
V logg. g.
A [
dt
= Ey
P log
+1 1
V log 9.
+ Av
pdq
q
where in the last step used the quotient rule A hand, by using the Fokker-Planck equation & * N0. 2t)) the chain rule we have
Ap
2
V Vlog q, v2 9
p4n On the other
9
Ap (Lemma 2 of Lyu 2009 and
d KL(p No, 2(), q * N(O,2()) dt
d dt / (q N(O,21)
p* N NO, 2t)
log p N 21) dx
g * N (0, 2t)
q * N(, 28)
= = (Aq)
p log
p dr Eng
log q
+1
Ap
pdy
q
q
q
q2
13

---

Published as a conference paper at ICLR 2023
Since by the chain rule and integration by parts we have
( 1og P +1 ( 9
'") x1 (
( log P / dr = dr==
/AA log dr,
By
q
g
we see that the two derivatives are indeed equal.
C PROOF OF PROPOSITION 3
Proof. From Hyvärinen (2005), we have consistency of score matching (Theorem 2) and in partic- ular the formula
= =(=(FF))(UPX
We now compute the limiting distribution of the estimator as the number of samples n - oc. We will need to use some standard results from probability theory such as Slutsky's 's theorem and the central limit theorem, see e.g. Van der Vaart 2000) or Durrett (2199) for references. To minimize ambiguity, let E,, denote the empirical expectation over n i.i.d. samples samples and let 0,, denote the score matching estimator ÓSm from n samples. Define ō,,1 and 6n,2 by the equations
(x((J))(JJF)3] (6(()) - 1/Vn/
and
= =AFFFEAG + 6n.2/Vn.
By the central limit theorem, 5, 16 5n,2) converges in distribution to multivariate Gaussian (with a covariance matrix that we won't tt need explicitly) as n - co. From the definition
8. (JF)
EAF
and we now simplify the expression on the right hand side. By applying 9 we have
((JJ))(JJ)) AE E((JF)((JFX]] (EAF + 2n.2/vn
= 6n.2/vn
Since
and +
have by applying Slutsky's 's theorem that
where the standard notation Y,, (p(1/) to indicate that nYm/5(m) 0 in probability for any function ff with f(n) + 0o. Hence
Osm X
- 1
and applying Slutsky's 's theorem again, find
Vn 0) -(UF))(UT)AA"((-B00---2
From the definition, we know
1
Vn 16 0 En.l AFI -EN--DDXXPXOO--I--------X-X-- AF
so altogether by the central limit theorem, we have
v 0) + N 100:NNN000
as claimed.
14

---

Published as a conference paper at ICLR 2023
D PROOF OF THEOREM
First, we will need the following helper lemma:
Lemma 3. For any random vectors A, B we have CA+B A + 2EB.
Proof. For any vector have
Var((w, B)) Var((w, A)) + 2Cov((w, 4YW, B)) Var((w, B))
< (ar((w, A)) + 2 Var((w, Var) B)) + Var (w, ()) B))
S 2Vrr((w, A)) + 2Var((w. ((w, B))
where the first inequality is Cauchy-Schwarz for variance and the second is ab S sa²/2 62/2. We proved for this for every vector which proves the PSD inequality.
With this in mind, we can proceed to the proof of Theorem
Proof of Theorem
2 Recall from Proposition 3 that
I'M
By Lemma 1 and submultiplicativity of the operator norm, we have
S
We will finally bound the two operator norms on the right hand side. By Lemma we have
{UF))(FF (F( 2EAF
Furthermore, we have
and
Farllor < (B(AF) for S TTE(AF)(AA)' ABIFF
which implies the statement of the theorem.
Supporting details for remark after Theorem Since vn(( - ASM) + N (0, I's)) by Propo-
sition 3 for all sufficiently large n it follows from Markov's inequality that with probability at least 99%.
n2|10 0smll2 (E |Z] O(TrIsM)) = (mm][[sMlllp))
On the other hand, by Fatou's 's lemma we have that
lim inf n 70C
MLLL! EZ~N(O.TME 1 Tr(TMLE) 2 |LMeellPPP
where in the first expression MLE implicitly depends on n, the number of samples. Combining these two observations with Theorem and gives the inequality stated in the remark.
E PROOF OF THEOREM 3 AND APPLICATIONS
We restate Theorem 3 for the reader's convenience and in slightly more explicit form in terms of the bounds on y. Note that we use the concept of the reach TM of a manifold which was defined in the preliminaries (Appendix A).
15

---

Published as a conference paper at ICLR 2023
Theorem 4 (Inefficiency of score matching in the presence of sparse cuts, Restatement of Theo- rem 3). There exists an absolute constant с >> 0 such that the following is true. Suppose that pe; is an element of exponential famity with sufficient statistic F1 and parameterized by elements of 11 Suppose S is a set with smooth and compact boundary OS. Let Tas > O denote the reach of Os (see Appendix Al Suppose that 1 is not affine function of F1, so there exists > O such that
sup wy VarVar( Ri))=1
Cov (wi,
(wi)
F1),
1s
S 61.
(10)
Var
Suppose that >> O satisfies
< min
Tas and is small
des (JFi)zllor
enough so that < 5 (VI- + +2
7 Jeons P(a)dr
Define an additional suf-
ficient statistic F2 ig tyy that the enlarged exponential family contains distributions of the form
P(o),02)(a)) exp( Fi(x)) + (2))
and consider the MLE and score matching estimators in this exponential family with ground truth Pigj .0-
Then the asymptotic renormalized covariance matrix T MLE of the MLE is bounded above as MILE I and there there exists some w and corresponding asymptotic
PIXEEXIIPXXESS variances (w), Me so that
Vn 8sM 8) + N(0, (w)),
Vn(w, f - 0) - N(, (w))
and the relative (injefficiency of the score matching estimator compared to the MLE for estimating (w, 8) admits the following lower bound
(w)(w) T MLE (w) 7
(PrnX E Pr(X $ 5)}
Socas p(z)dz
Sc where d' = 1+ DF, lop"
The proof will proceed in two parts: will lower bound O'MM (w) and upper bound MILE (w). The former part will proceed by proving a lower bound on the spectral norm of T (Subsection E. by picking direction in which the quadratic form large. The upper bound on MLy (Subsec- tion E.2 will proceed by relating the Fisher matrix for the augmented sufficient statistic (Fi, F2) with the Fisher matrix for the original sufficient statistic Fi.
Supporting details for remarks after Theorem 3 isoperimetric inequaltiy, the term (ii(Pr(XXeS),P
If we choose S to be the worst set in the
Jreas pla)ds in the bound is simply Crs- To see this,
observe that lim,- Js, p(a)de Loadde--a Ja p(o)do
Sosos p( dx as a special case of Weyl's I's tube formula
Weyl
1939
Gray 2003)
E.
LOWER BOUNDING THE SPECTRAL NORM I'sM
We recall the new statistic Fz, defined in terms of the mollifier & introduced in Section 2
F2(z) = (Is (x) /
J 1s()) yydy = =f v/ - yydy
and the new sufficient statistic is F(x) (Fi (x), (x)). We first show the following lower bound on the largest eigenvalue SMM the renormalized limiting covariance of score matching:
Lemma (Largest eigenvalue of sM). The largest eigenvalue of K satisfies
8 8-d,2
(xia(x,88)5
(IVE) +FF)
Amaz (T sw))
(11)
Pr[d(X (5, 7]
suPd (JF) 13pp
16

---

Published as a conference paper at ICLR 2023
Proof. We have
V2 (xydy, (2F2()) = / Vatt -yddy
V (2)) =
Defining
u: UU
we have, by the variational characterization of eigenvalues of symmetric matrices, that
(u, (LB
Amax (K)
(12)
||u|/
To upper bound the denominator we observe that Ba is the volume of the unit ball,
[V)l2( = 1/5 (Viy)(z yyd
(13)
2
< (d(r 0S) S 57h - d-1 nol (B(x
(14)
- (d(2, s و
(15)
and so
||uI[2 S 8 Pr[d(X S 1
sup
[(JF)x
d(x.as)el--cl
where we used the computation of the derivative of 1hy To lower bound the numerator we have
(u. ((JF))((JJ) (OUUF)XUFXXI""XXXUXPEAAAA
= -0.11"" SunixUrteeHa
uu)
=E((O, 1), (JF)x + AF) E ((V=E)) +FZ)²
The integrand is zero except when d(X, 0S) < so equals
Pr[d(X, 08) < 7/ ax.a9)st-)) (U
and combining gives the result.
We now estimate the right hand side of 11 for small 7, using differential geometric techniques. The main idea is that we take 7 smaller, end up zooming into the manifold as which locally looks closer and closer to being flat. Differential-geomeet quantities describing the manifold ap- pear when we make this approximation rigorous. The most involved term to handle ends up to be calculating the expectation [xxj((X,05)r> ((V (JF)E + AF2 To do this, we first argue that the term with the Laplacian dominates as - O, then by Stokes theorem, we end up integrat- ing (Vub ddN) over intersections of S with small spheres of radius where N is a normal to S. Such quantities can calculated by comparing to the "flat" manifold case -.c. when N does not change. How far away these quantities are (thus how small needs to be) depends on the cur- vature of S (or more precisely, the condition number of the manifold). Lemma makes rigorous the statement that well-conditioned manifolds are locally flat and then Lemma 7 which is part of the proof of Weyl's tube formula (Gray) 2003 Weyl 1939,, lets us rigorously say that the tubular neighborhood (that is, thickening of the manifold) behaves similarly the flat case.
Lemma 5. There exists an absolute constant > 0 such that the following is true. For any ? > 0 satisfying
dd
Tas
min
(1 [[01])) suPa:daa.sss [(JFa)z
for score matching on the extended family with m + sufficient statistics and distribution pe with 0 (0z, 0) we have
e
Amaz (M)
? Jos P(z)dA
17

---

Published as a conference paper at ICLR 2023
Proof. In the denominator, observe by (3) that
I(JFF)=llo> < IJR lÔ II Fall 2 <
27- 2Bg
where the last inequality holds assuming 7 sufficiently small that || 5 In the numerator we can observe
(V 2 (JF) (JF) 2F2
-V)) + (A vydy
(SNB(X)) (VV))((X--)) v)), + (A yddy
-0t -BX..UXX-SS/ (VV)))(1), + (Avr)
J (VV(),
S JO1B(O.In(X-9//) 7 (VVb,, dN)
B(0,))((-9)//1 -f -BOODDICK-S/>> 7
(V)))
Vb. dN)
B(0.1)((-09)//
where the second-to-lad expression is a surface integral which we arrived at by applying the diver- gence theorem, using that the Laplacian is the divergence of the gradient, and the last step we used that vo and all of its derivatives vanish on the boundary of the unit sphere.
Using that (01, 0) have
U T (VV(u), ST S [VO())]I[[F)))xxor000)
(16)
(17)
Let be the point in a(x S)/y which is closest in Euclidean distance the origin. Let n(g) denote the unit normal vector at point oriented outwards (Gauss map). Note that by first-order optimality conditions for p, must have n(p) p/llplI- Since dN n(g)dA where dA is the surface area form, we have
Jmoo))cx--0s/ VN) -f
0ER00.11((X00555 (V((g)) + (m(()) n(p))ddA
22)((g)
(EB(0.))((-005)) (1 12] (q. |||||
(n(g) dd
We now show how to lower bounding the integral by showing (g. T + (n(4) - n(p))) is lower bounded.
Let c(t) be minimal unit-speed geodesic on M (X-OS)/> from p to g. Note that TM = Tas/" so if is very small, M is very well-conditioned. By the fundamental theorem of calculus, we have that
(). (p.p) + S (p,c c(())dtt = (p.p) +
(Projtzce e' (t))
where Te(e) the tangent space to M at the point c(t). Hence by the Cauchy-Schwerr inequality we have
['' Projr (t)lla
Kp, g) 2 (p.r) p)
By Proposition 6.3 of Niyogi et al. (2008). we have that for oi the angle between the tangent spaces
Tp and To(e) that
Φe 2 dm(p,c(t))
=1 dd(p.g).
(18)
TM
TM
18

---

Published as a conference paper at ICLR 2023
Since sin² Φi + cos? Φe and p is orthogonal to the tangent space Tp. it follows that
Proiz pll S ||||| sin Φe = |lll / cos² o, S 1 (/w
hence
S. || Proiic.oo (t)ll' & (2/3) (t/ (P. +
Since lpp all s 2, provided that TM 16 we have by Proposition 6.3 of Niyogi et al. (2008) that
(p 9) S TM( v 1 gll/TM) S 4.
Combining, have for some absolute constant C > 0 that
(p.9) 2 (p.P) CCCT// C/TM)-
Also, we can compute
2 g S
[[((()) - n()]ll = /2- 2cos 01 - V TM
TM
So
8
Ka, - n < - -
S
TM
Hence provided TM > C¹ for some absolute constant C" and || 0.1, we have
VE (1 1-]l22222
-2b(4)
(g: IPll (n(g) (D)))dA
()))
JEB(O..))(X0099/ (1 33 IlPIIA
using that the integrand the left is always negative. We further lower bound the integral by considering the intersection of M with ball of radius r= ااعلد centered at p. We have
f B(B 088/77 (1 |] IpI|dA
(())
(())
lp IPIdA
(EB(()))M (1 ||
2)(g)
|| (cos 0) (B (BM(T))
inf
(E (1
BLV(g)
|p (cos &
inf (E (1 ||
where = the dimension of M and = arcsin(r/27) and we applied Lemma 5.3 of Niyogi al. (2008). If ||pl| (0.1,0.9) this is lower bounded by a constant C₁ >> 0 which is at worst exponentially small in k.
Hence recalling 17 have for any X with d(X,00 aS) (0.17, (0.17,0.97) and for y sufficiently small so that +g++1 [JFF)xllor((()) < Cx/4 for any such X, we have that
(VVFRR + AF2) >
where C/ > is constant that is worst exponentially small in k. Therefore
Ex(a(xa9))e ((VE)) AF5) -Ck Pr(d(X,05 E (0.17,0.97))
Pr(d(X, 08) <))
Combining these estimates, we have for some constant C% > 0 which is at worst exponentially small in & and y sufficiently small (to satisfy the conditions above, including the requirement TM > C") that
C Pr(d(XX aS) E (0.1%, 0.97))
Amaze (T'M)) 2
(19)
Pr(d(X, 05) < 7)
19

---

Published as a conference paper at ICLR 2023
Observe that for any points z, y and 0 (01, have by the mean value theorem that
po(x)/po(v) exp ((01, (2) (i))) S exp
|00]
sup II( [[0R)))+---ppllllllll w/1 eE(o,1]
(20)
so the log of the density is Lipschitz. This basically reduces estimating Pr(d(X, aS) S 7) for small y to understanding the volume tubes around 0s, which can be done using the same ideas as the proof of Weyl's s tube formula (Weyl 1939 Gray 2003).
Lemma (Proposition 6.1 of Niyogi al. (2008),. Let M be a smooth and compact submanifold of dimension in R. At a point p M ler B Tp x T TT denote the second fundamental form, and for unit normal vector u, let Lu be the linear operator defined so that (u, B(v, w)) (V, Lw)) (this matches the notation from Niyogi et al. (2008). ). Then
|LuloPp S TM
Lemma 7 (Lemma 3.14 of Gray 2003)). ) Let M be a smooth and compact submanifold dimen- sion in IRd. Let expp denote the exponential map from the normal bundle at The Jacobian determinant of the map
M M (-1TTM 1/TM) x Sa-q-1 Rdd (p,t,u) + expp(lu)
det(L t..).
We can compute
po(x)dx [ I' f det(l- tLu)ps (exp)p(exxppppeee (exp,(tu)) du dt dA Pr(d(XX r))= Jasd(z
pEBS
where in the second equality we performed a change variables and obtained the result by applying Lemma We have
det(1 - tL.) [(1 [[1-t/r]] (1+
and applying (20 find that if define e c: |up [(JFi)xllor which can be
made arbitrarily small by taking sufficiently small, then
Pr(d(X, 05) I r) [2e ">(1
(21)
where
V / p(x)dA
Note that (1 7/7)* < ch//T and (1 - 7/7)* > expl-O(7kk)) provided that 7/T O(1/k).
Since Pr(d(X, 0S) (0.17, 0.97)) Pr(d(X, 0S) 0.97) Pr(d(XX, as) 0.17) and the
distribution we consider has a density, by combining 21) and 19 we find that for y sufficiently small we have
Amaz (TMM) 2 Ck
Jos
where Cls' is at worst exponentially small in
E.2 RELATING FISHER MATRICES OF AUGMENTED AND ORIGINAL SUFFICIETT STATISTICS
Next, we show that adding the extra sufficient statistic F2 has comparatively minor effect on the efficiency MIE. Intuitively, (1) the variance of F2 is large, that nonzero coefficient of F2 be observed from samples (e.g. when F2 encodes the cut S, the coefficient can estimated by looking at the relative weight between S and 5²), and (2) there is redundancy in the sufficient statisties, e.g. F2 * F; since otherwise different coefficients can encode the same distribution. The proof of this uses that the inverse covariance of the MLE has simple explicit form (the Fisher information, which is the covariance matrix of (Fi, F2)), and conditions (1) and (2) naturally appear when we use this fact.
able to estimate the coefficient of F22 correctly we just need:
Quantitatively, we show:
20

---

Published as a conference paper at ICLR 2023
Lemma 8. Suppose that F == (F1, is random vector valued in Rm+ with F1 valued in R and Eg valued in R. Suppose that Fiy is not in the affine of linear combinations of the coordinates of Fi. i.e. for all wi E Rmm there exists >> 0 such that
Cov((w1: Fi), F2)2 S d'Var((11, Fa)
Then we have the lower bound
ΣF
0
Er z 6)
Var(F2)
in the standard PSD (positive semidefinite) order.
Proof. To show lower bound on
EFi EFI EF = EFAF
ΣF,
observe that
(w, Epw) = (wi, Ei. wi) + (wi, DF, + WZ so under the assumption we have by the AM-GM inequality that
(w.Epe Epw) (1 8) (wn, Σy, w1) + 2gEF=
and hence Ep lower bounded the PSD order as long as Ep, and Er, is.
The lower bound on Var(F2) is guaranteed when Fz corresponds to cut with large mass on both sides since the variance of 132 is lower bounded by its variance conditioned on being away from the boundary of
E.3 PUTTING TOGETIIER
Finally, given Lemma and g complete the proof of Theorem 3
Proof of Theorem
Define p = Pr(X E S) for the purpose of this proof. Observe that by 21
Var(1s F2) < E(1s F2)² < Pr(d(X, S ~) s 4yV
where = = p(x)dA. We have that
Cov((w,, Fi), F2) Cov((w), Fi), 1s) + Cov((w), Fi), F2 1s) so if wi is arbitrary and normalized that Var (w1, Fi)) 1 then we have
[Cov((w), Fi), F2)1 S VI 51 Var(1s) + v Var(F22 - 1s)
AV
1- + 2
/Var(1s).
(11-
Therefore provided 8 we have
Fi
Var(F22
On the other hand, by Lemma we have
Amaz (I (M) >
Hence there exists some such that
dcd
ded
p(1 - p)
2
L w
max |ax]||E7]|1om for, 1/p(1 pp} 7V 1 p1
p) E llo
lop
YV
Using that min (p. - /)/2 p(1 p) 1/4 and dividing by gives the result.
21

---

Published as a conference paper at ICLR 2023
E.4 MULTIMODAL EXAMPLE: PROOF OF COROLLARY
Proof of Corollary
7 First observe that
Fi(4) dx =2 -00/8ita-a)aa/ttt)"
da 2
8c
c (1/88)(x-o)) dr
0
c (22118 dx =:
=
where C' is positive constant independent of a. Using that Fi(z) (1/8)(x (2/ 1)2 it then follows that
-o-1 c Fi
-1118)(r//0+1)
Pr(X 1, 1])
C 00
1_00 e Fi(
C
where C' a positive constant independent of a. From this, we see by the law total variance that (ar(Fi) 2 Var(Fi X la - 1,a + 1]) Pr(X E la - 1, + 1]) C" 0 where C" >> is another positive constant independent of Hence 12Flllop = ((1) independent of Also, if we define 5 {x 0} then
(z) =0
becuase (1 is even, 19 is odd and the distribution is symmetric about zero. So we can take d1 in the statement of Theorem
Therefore, applying Theorem 3 to S and using that Fi -a² /8, therefore get for y smaller than an absolute constant, that the inefficiency is lower bounded by 12 /8 /n). By taking y equal to fixed constant we get the result.
In Section 7 we perform simulations which show the performance of score matching indeed de- grades exponentially beomes large.
F DISCRETE ANALOGUES OF SCORE MATCHING
Glauber dynamics. The Glauber dynamics Gibbs sampler is the standard sampler for discrete spin systems - repeatedly selects a random coordinate and then resamples the spin X; there conditional on all of the other ones (i.e. conditional on X..). See e.g. Levin and Peres (2017). This the standard sampler for discrete systems, but also applies and has been extensively studied for continuous ones (see e.g. Marton (2013)) ). Exponential ergodicity of the Glauber dynamics is most cases where the MLSI is known, approximate tensorization of entropy is also, e.g. Chen et al. (2021b) Anari al. 2021a);
equivalent to the Modified Log-Sobolev Inequality (MLSI)
Marton 2015); Caputo et al. 2015).
F.1 FINITE SAMPLE BOUNDS
We state explicitly the analogue of Theorem I for pseudolikelihood, which follows from the same proof by replacing Proposition I with Proposition
a class of probability distributions containing p and define CAT(P, P) == sup (g P) S supger Car(q) to be the worst-case (restricted) approxi- mate tensorization constant in the class of distributions. Let
Theorem Suppose that
1
Σ log (((i))) (Xi)ma)
R₂ = EX
sup PEP
1=1
be the expected Rademacher complexity of the class given samples X1y... Xn. p i.i.d. and independent Ei...., En ~ Uni{t1} i...d. Rademacher random variables. Let p be the pseudolikeli- hood estimator from n samples, i.e. p = arg mingeP Lp(g). Then
E EKL((pD) < 2CAT (P,,PR.
In particular, if CAT 0o then lim E ELL 0 long as limp Rr 0.
22

---

Published as a conference paper at ICLR 2023
F.2
RATIO MATCHING AND APPROXIMATE TENSORIZATION
Marton 2015) studied a strengthened version of approximate tensorization of the form
()(p..) S Ca)Z(A) Σ Ex.. TV Xx.)) q(X, (xwi))
(22)
(This is known to hold for class of distributions satisfying version of Dobrushin's 's condition and marginal bounds (Marton 2013).) This inequality is stronger than the standard approximate tensorization because of Pinsker's inequality TV (P, Q) X KL(P, Q) (Cover 1999). In the case of distributions on the hypercube, we have
where TV denotes the total variation distance (see Cover 1999
(v( Xx.), ((x, Xxxi)
= -M(X +1 Xwi) - ((x; = +1 | x..))?
-Ex-Xxxxx ||(;; = +1) -(X; = -1 xxxi)
-EX,-XX;IN,, |1(X; ++1)-((X, = =11 X=1)1
where in the last step we used the Pythagorean theorem applied to the Px,IX.., orthogonal decom- position
1(x, +1) 9(X; +1 Xm.) = = - +1 X..))
+ +p((,, = +1 +1| q(,; = +1 Xxi)l
Hence, there exists a constant K2 not depending on such that
E Ex_rpp (V xx)), X..)) = K2 + Mx(9)
(23)
where we define the ratio matching objective function to be
d
Mp(1)= = Σ Exxx
+1) - x(x, = +1 |
(24)
This objective is now straightforward to estimate from data, by replacing the expectation with the average over data. Analogous to before, we have the following proposition: Proposition 5. We have
KL g) S Carz(a)(M(()) Mp(P))
and more generally for any class P containing p. have KL(p. CArz29, (Mp((a) Mp(p)).
We now show how to rewrite Mp(g) to match the formula from the original reference. Observe
Ma(1)=
Σ Ex Ex-p Xx; Ey[Xi X
Ex ~p 11 X.B,(X, X=i]I
Observe that for any E {+1} we have
q(X; Xx1) 9(X, -2 Xai)
z 2E, [X, Xwsl=
q(Xi = Xwi) + g(X; -2 Xax)
and
29(X, = - 1 Xax)
1 1 ==EE,X X
q(X, = v Xwi) + +((X; = - Xam)
1 qX; = X Xxi)/q(Xx -2 Xwi)
23

---

Published as a conference paper at ICLR 2023
MLE Ulimit formulal
Score Matching timmit formula)
0.02
0.02
0.00
0.00
-0.07
-0.00
2.8
0.99
1.00
L.02
1.2
0.98 0.90
1.00
1.02
1.62
Jhslapp
Figure 3: Level sets for the distribution over estimates in the same example as Figure I We see that as the distance between modes increases, the direction of large variance for the score matching estimator (right figure) corresponds to the difference of the sufficient statistics which encodes the sparse cut in the distribution. On the other hand, the MLE (left figure) does not exhibit this behavior and has low variance in all directions.
Also for = E (=1)d df we have q(x; 2, Xai 2ne)/((X, -2 Xmss = 2m1)) q(=)//(==))
where 2-; reprsents 2 with coordinate i flipped, so
1
Mp(g)= Σ E Ex-p (+g(X)/a(X))
which matches the formula in Theorem 1 of Hyvärinen 2007).
Summarizing, minimizing the ratio matching objective makes the right hand side of the strengthened tensorization estimate (22) small, so when (AT2(G) is small it will imply successful distribution learing KL. (The obvious variant of Theorem 5 will therefore hold.) In this way ratio matching can also be understood as a relaxation of maximum likelihood.
G FURTHER SIMULATIONS
Complementary visualization to Fi In Figure we illustrate the distribution of the errors in the bimodal experiment with the cut statistic. As expected based on the theory, the direction where score matching with large offset performs very poorly corresponds to the difference between the two sufficient statistics, which encodes the sparse cut in the distribution.
Fitting a bimodal distribution without a cut statistic. In Figure 4 we show the result fitting the same bimodal distribution using score matching, but remove the second sufficient statistic (which correlated with the sparse cut in the distribution). In this case, score matching fits the distribution nearly well the MLE. This is consistent with our theory (e.g. the failure of score matching in Theorem 3 requires that we have a sufficient statistic approximately representing the cut) and justifies some of the distinctions made in our results: even though the Poincaré constant is very large, the asymptotic variance of score matching within the exponential family is upper bounded by the restricted Poincaré constant (see Theorem (2) which much smaller.
Example 3 (Application of Theorem to this example). To briefly expand the last point, we show how to apply Theorem 2 in this example (Example [ where we have not added bad cut statistic.) The restricted Poincaré constant for applying Theorem 2 will be
= Var(Fi(X)) = Var(X" X /2a²) [(P((X))2
(25)
E(2X 2x3/
24

---

Published as a conference paper at ICLR 2023
Score Natching
-33
33
offsct
Figure 4: Here we the result of running an identical experiment to Figure I only remove the second sufficient statistic, our distribution is now po(x) c 1(20 where 0g 1 and we again vary the offset a between I and 7. With only the single sufficient statistic, score matching performs comparably to MLE.
which asymptotically goes to constant, rather than blowing up exponentially, as a goes to infinity.
(This can made formal using arguments as in the proof of Corollary informally, the distribution is similar to a mixture of two standard Gaussians centered at to so the numerator is close to
Var (o.2) 2)² - Z)² /2a²) ) = Var(2aZ + Z² (4a 62 +42 +2 /a4
(1)
and the denominator is approximately Ex-No.. + Z) 2(a + Z) /2) E(2Z 2(32 +
37 /a+ 73/ /2²a)) = (1)).)
Given this bound the restricted Poincaré constant, can apply Theorem 2 Based similar reasoning to above, one can show that (X)+ (-1/Aa2y'B((X a) (X++Xxa) + (X-a)'X++ a))² (1) and E.F"((X)
E(-3x² /2n² + 1/2)2 ((1), we conclude that ||T SM MLL This proves that score matching will perform not much worse than the MLE, as we saw the experimental result of Figure 4
Remark 8. Exumple 3 shows case where there is a large gap between the restricted and un- restricted Poincaré constants. This also implies a completely analogous gap between appropriate restricted and unrestricted log-Sobolev constants, used e.g. in the context of Theorem [ To elab- orate, we know that the unrestricted log-Sobolev constant blows up exponentially in a, just like the unrestricted Poincaré constant, because CLS Cr/22 (Van Handel 2014). On the other hand, if we fix the ground truth distribution Pa consider the class of distributions
P, {pa' : :aa- - a'l Sr),
we have that
lim CLs(q, P,)= CC2 r-0
where C is the constant defined (25) in terms of (and which ((1) as a + oc). This is because from the defiiiiin an exponential family, we have
(x(x)/pa(<)) = exp ((a - (x))
E. exp ((a a.) a
so
lim KL(Pa. lim an I(pa Pac) ao 2(a - a IVF C/2
(a - d') V') (Fi
where the first equality is by a standard Taylor expansion argument (see proof of Lemma 3.28 of
(an Handel 2014)).
Fitting a unimodal but not smooth distribution. In Figure we demonstrate what happens when the distribution is unimodal (and has small isoperimetric constant), but the sufficient statistic not quantitatively smooth. More precisely, we consider the case (x)) x e 00022/2 /2-0 00 sin(wa) as w
increases. In the figure, we used the formulas from asymptotic normality to calculate the distribution
25

---

Published as a conference paper at ICLR 2023
MIF
Matching
9-
lngicmega)
MLE (imit formula)
Score Matching (limit formula)
1.020
1.000
14
14
10:5
1.055
10:0
1.200
1.000
1.000
0395
0.95
0380
0.880
1.000
1.010 1005
1.000 dherau
1.010
Figure 5: Score matching vs MLE for a distribution with a rapidly oscillating sufficient statistic,
Pe (e()) & 000a0/2220200 /2-0; sin(wx) where (6u, 01) (1, 1). and increasing w. On the top, for increasing show log-log plot of the average Euclidean distance in parameter space between 0 and the output of each estimator. On the bottom, for each value of we draw level set of the distribution within which fixed fraction of returned estimates lie (MLE left, score matching right). Score matching becomes increasingly inaccurate as w increases while the MLE stays extremely accurate.
26

---

Published as a conference paper at ICLR 2023
over parameter estimates from 100,000 samples. We also verified via simulations that the asymptotic formula almost exactly matches the actual error distribution.
The result is that while the MLE can always estimate the coefficient 01 accurately, score matching performs much worse for large values w. This demonstrates that the dependence on smoothness in results (in particular, Theorem 2 is actually required, rather than being an artifact of the proof. Conceptually, the reason score matching fails even when though the distribution has no sparse cuts is this: the gradient of the log density becomes harder fit as the distribution becomes less smooth (for example, the Rademacher complexity from Theorem | will become larger as it scales with V, log and 2 p).
Fitting a mixture of Gaussians with one-layer network: further discussion. We provide some further remarks on the results in Figure 2 In the right hand side example (the one with large separation between modes), the shape of the two Gaussian components is learned essentially perfectly it is only the relative weights of the two components which are wrong. This closely matches the idea behind the proof of the lower bound in Theorem 3 informally, the feedforward network can naturally represent a function which detects the cut between the two modes of the distribution, i.e. the additional bad sufficient statistic F2 from Theorem [3] The fact that the shapes are almost perfectly fit where the distribution is concentrated indicates that the test loss Jp is near its minimum. Recall from (I) that the suboptimality of a distribution q in score matching loss given by 1p(() (p)
v log glI². If we let be the distribution recovered by score matching, we see from the figure that the slopes of the distribution were correctly fit wherever p is concentrated, so Ep V log V log all is small. However near-optimality of the test loss (g) does not imply that y actually close to p: the test loss does not heavily depend on the behavior of log y in between the two modes, but the value of V log in between the modes affects the relative weight of the two modes of the distribution, leading to failure.
E V log
Model details: both models illustrated in the figure have 2048 tanh units and are trained via SGD on fresh samples for 300000 steps. After training the model, the estimated distribution is computed from the learned score function using numerical integration.
27


Reviews:
[{"review_id": "rTEV2Y5jVc", "reviewer": "Reviewer_R2sB", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper analyzes the statistical efficiency of the score estimate obtained by the score matching objective and compares it with the maximum likelihood based approach. Specifically, relation between the loss optimized in score matching J has been compared to the KL divergence between the true distribution p and the estimated distribution q. The paper shows that the bound on the KL depends on the log-Sobolev constant, the score matching estimator converges to a distribution that depends on other quantities like Poincare and smoothness of sufficient statistics. Later this experiments support the main idea of this theorem.", "summary_of_the_review": "I generally liked the new perspective of analyzing the statistical efficiency of the score matching objective discussed in the paper. Many theoretical results have been presented. However, there were some concerns in presentation and a few clarifying questions. Hence, I am on the positive side.", "strength_and_weaknesses": "Many results of the paper are interesting and insightful. And they are fairly novel since this work is probably the first to discuss the statistical efficiency of score estimator.\n\nHowever, the clarity of the paper could be improved. I have a few suggestions below. Also, with some more insightful experiments, the motivation of the paper could be boosted. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "jm7nYQZ2u5", "reviewer": "Reviewer_tSNd", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper studies the statistical properties of the score matching from a geometry viewpoint. The authors show an upper bound for the KL divergence between the underlying data distribution and the score-matching estimator using the log-Sobolev inequality. Moreover, with a focus on the exponential family, they analyzed the asymptotic efficiency of the score-matching estimator compared to the one of the MLE using The Poincaré inequality and isoperimetric inequality.", "summary_of_the_review": "This paper provides useful insights into the popular score-matching estimator. The results seem novel and technically solid to me. I thus vote for acceptance.", "strength_and_weaknesses": "**Strength:**\n1. Score matching is a widely used technique and its statistical analysis is of high interest to the community.\n1. Their theoretical results seem novel and technically solid to me. I found the isoperimetric viewpoint quite interesting.\n1. I found the paper well-written and easy to follow.\n\n**Major comments:**\n1. Why is Thm. 3 about an unknown direction? It makes sense to me if the goal is to estimate $||\\theta||$ or $w_0^\\top \\theta$ for a prescribed $w_0$. The fact that the lower bound is proved for an unknown vector $w$ is confusing to me. Is it possible that there exists some $w'$ such that the score-matching estimator achieves better efficiency?\n1. The paper could benefit from adding more explanations and discussions. For example,\n    1. How large is $C_{LS}(q)$ compared to $C_{LS}(q, \\mathcal{P})$ depending on $\\mathcal{P}$? Can you give an example?\n    1. Can you provide an example for Thm. 2, just like Thms. 1 and 3?\n    1. It would be helpful to give some intuition on the tools used in Sec. 2.\n1. From (1), $J_p(q) - J_p(p)$ is equal to $1/2$ of the RHS of (6). Prop. 1 seems to be missing a factor of 2. This also holds true in the latter results like Thm. 1.\n\n**Minor comments:**\n1. Should $p$ be smooth in Def. 2?\n1. What is $f$ in Def. 3?\n1. The notation $I_d$ in the paragraph Mollifiers can be confused with the identity matrix.\n1. $J_p(q)$ should be $J_p(p)$ in the equation below (6).\n1. The subscripts MLE and SM in Def. 6 and Prop. 2 are too large. Maybe use \\text{}?\n1. In conclusion, \"In tihs paper\" --> \"In this paper\".\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "RoEXiiQM4K", "reviewer": "Reviewer_gNn2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The authors provide a theoretical comparison between maximum likelihood estimators and score matching estimators in the case where the distributions are from the exponential family.\n", "summary_of_the_review": "This work provides a suitable theoretical premise for the well-known observation in score-based generative modeling that noise-perturbations are critical for good performance. For this reason, the most relevant result to me is Theorem 2, which provides theory for this phenomenon under the (albeit simplistic) assumption that the data distribution is exponential.\n", "strength_and_weaknesses": "Strengths:\n- Proofs are clean and straightforward.\n- Theory corroborates with practical observation, that score matching on multimodal data requires noise perturbations.\n\nWeaknesses:\n- Theory is mainly descriptive rather than prescriptive --- it is well known that noise-perturbation is crucial for properly learning scores [1].\n- Non-asymptotic theory is limited to comparing loss values (KL divergence vs expected square error of scores), which does not provide a clear insight into how the resulting densities themselves compare.\n- Asymptotic theory is limited to learning on distributions in the exponential family.\n\n[1] Song, Y. and Ermon, S., 2019. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%