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.
Three 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.
[1] Asymptotic statistics, Van der Vaart, 2000.
[2] Statistical Efficiency of Score Matching: The View from Isoperimetry, Koehler et al., 2022.
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.
- 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.
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 ?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
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.