Thank you for your feedback!
Thank you for your feedback and questions! We are glad you found our results new and non-trivial, and our writing clear. Hopefully the clarifications below ameliorate your concerns.
**Contribution of Theorem 2**: You are correct that our results are a generalization of Koehler et al. (2022). While the overall proof strategy is similar, Theorem 2 is important in two ways:
(1) **Conceptually** our result makes it clear that there is nothing special about *Langevin diffusion* (and its mixing time, as captured through the standard Poincare constant). In particular, for *any diffusion* of the form (7), one can connect the statistical complexity of the corresponding generalized score matching loss to the mixing time of the diffusion. This provides a “dictionary” to translate between fast-mixing diffusions and corresponding score losses with good statistical complexity. Furthermore, the results in Koehler et al. (2022) also only apply to exponential families—our proof shows this restriction is not needed.
(2) **Technically** the main new ingredient is Lemma 4 (along with the calculations in Lemmas 3, 11 and Lemma 13) which connects the Hessian of the generalized score matching loss to the Dirichlet form of the corresponding diffusion. Again, these calculations are completely new compared to Koehler et al. (2022).
**Clarification on Theorem 5**:
*(Q1) Computational efficiency of training score loss, motivation*: The general motivation behind score-matching methods is to avoid calculating a partition function, by fitting the score function through the integration by parts formula (eq (2)). In our case, as in Proposition 6, the CTLD score loss can also be rewritten by integration by parts as an expectation of expressions involving the fitted scores.
Note that even for basic score matching, the corresponding loss may not be convex, so all that’s guaranteed is that a gradient-based method can be efficiently run (which is not the case for maximum likelihood due to the partition function). Nevertheless, there **is** an algorithmic gain compared to maximum likelihood (the possibility of running a gradient-based algorithm efficiently)—so the question of understanding the "statistical cost” (how much worse it is compared to maximum likelihood) is meaningful.
*(Q2) Dependence on K*: the reason why we phrase the result as $\lVert\Gamma_{SM}\rVert_{OP} \leq C \lVert\Gamma_{MLE}\rVert^2_{OP}$ is that we are trying to compare how much (statistically) less efficient score matching is compared to MLE. We stress the point about $C$ not depending on $K$ for two reasons:
(1) While MLE could potentially depend on $K$—the dependence is likely to be mild (we are estimating $K$ vectors, so the dependence would be no worse than linear); if $C$ depends poorly (e.g. exponentially in $K$) it would render our result uninteresting for mixtures with large number of components. Moreover, since MLE is asymptotically statistically optimal, whatever dependence on $K$ it incurs is unavoidable.
(2) Theorem 2 proceeds via a decomposition result, similar as prior analyses of simulated tempering (Lee et al, Ge et al (2018)) — and all these results incur a dependence on $K$. This is because their setup is somewhat different — in particular, they analyze discrete tempering, where the annealing is done via temperature scaling (rather than Gaussian convolution).
*(Q3) Comparison with prior work on Gaussian mixture models*: We are happy to expand on the discussion in Appendix I. Mostly though, these results are incomparable: they focus on end-to-end provable algorithms for learning mixtures in various regimes—typically trying to deal with the case of mixtures with not-well-separated means. Our focus is on understanding the *statistical complexity of score matching losses*—not on providing new end-to-end provable algorithms for Gaussian mixtures. (Note, the CTLD loss is not convex, and we don’t analyze what gradient descent or related algorithms would converge to.) Gaussian mixtures are just chosen as a very natural toy model for multimodal data, and as a “proof of concept” that annealed score matching is statistically well-behaved for many distributions for which vanilla score matching is not (via the lower bound in Koehler et al (2022)).
*(Q4) Gaussians with different covariance*: it is quite likely that our results apply to mixtures with covariances which are $1+O(1/d)$ away from each other, but not larger (were d is the ambient dimension). The reason for this is that annealing “distorts” exponentially the relative volumes of the Gausians (technically, what breaks is the chi-squared divergence bound in Lemma 21). However, we note that for universal approximation using mixtures, one can use a mixture of (exponentially many) Gaussians with covariance $\epsilon I$ to $\epsilon$-approximate the distribution of choice.