Denoising Score Matching via Random Fourier Features

Olga Tsymboi, Yermek Kapushev, Evgeny Burnaev, Ivan V. OseledetsIEEE Access 2022 · DOI · OpenReview

Abstract

Density estimation is a critical task in statistics and machine learning, yet it is often hampered by the intractability of normalizing constants and the failure of score matching on distributions with bounded support. This paper introduces a novel framework that combines Kernel Exponential Families (KEF) with Denoising Score Matching (DSM) and Random Fourier Features (RFF). By deriving an exact analytical solution for the denoising objective, the authors eliminate the need for expensive higher-order derivatives and provide a model that is significantly faster than previous kernel-based approaches. Experimental results on synthetic and real-world datasets, including the large-scale MiniBoone dataset, demonstrate that the proposed method maintains high accuracy while offering superior scalability.

Introduction

Learning the underlying probability distribution of a dataset—density estimation—is central to many statistical applications. Traditional Maximum Likelihood Estimation (MLE) is often hindered by the need to calculate the "partition function" or normalizing constant, which is mathematically intractable for complex models. Score matching offers an alternative by matching the gradient of the log-density, thereby bypassing the normalizing constant. However, standard score matching struggles when data resides on low-dimensional manifolds or has bounded support.

Denoising Score Matching (DSM) was developed to solve these support issues by perturbing the data with small amounts of noise. While effective, DSM typically requires complex Taylor series approximations or computationally intensive higher-order derivatives to remain tractable. This paper addresses these challenges by leveraging Random Fourier Features to create a scalable and analytically exact DSM framework.

Methodology

The proposed approach integrates three key components:

  1. Kernel Exponential Families (KEF): A flexible class of models capable of representing a wide variety of complex distributions.
  2. Denoising Score Matching (DSM): An objective function that ensures consistency even for "difficult" data distributions by convolving the model with a noise distribution.
  3. Random Fourier Features (RFF): A technique used to scale kernel methods, reducing the computational cost from $O(n^3d^3)$ to a linear dependency on the number of features.

The primary innovation lies in the derivation of an exact analytical expression for the DSM objective when using RFFs. Unlike previous methods that rely on Nyström approximations or Taylor expansions, this approach implicitly incorporates higher-order derivative regularization. This means the model naturally penalizes high-frequency oscillations, with each feature's weight being proportional to $\exp(-\frac{\sigma^2}{2}\|w_i\|^2)$, where $\sigma$ is the noise variance.

Experimental Evaluation

The method was evaluated against several benchmarks to assess speed, accuracy, and scalability.

Datasets

  • Synthetic 2D Distributions: A variety of challenging shapes, including Mixture of Gaussians, Uniform, Banana, and Ring distributions.
  • Real-World Data: The RedWine and WhiteWine datasets from the UCI repository, and the large-scale MiniBoone dataset.

Key Results

  • Scalability: The DSM-RFF method successfully scaled to the MiniBoone dataset, which is typically too computationally expensive for exact kernel solutions.
  • Efficiency: Training was completed in a fraction of the time required by competing Nyström-type approximations.
  • Accuracy: On metrics such as Fisher Divergence and Wasserstein Distance, the approach consistently matched or outperformed standard score matching, particularly on distributions with bounded support (e.g., Uniform distributions).
  • Robustness: DSM proved significantly better than standard score matching at estimating density in the "gaps" between data modes where density values are near zero.

Discussion and Insights

A significant advantage of this approach is its implicit regularization. The noise variance $\sigma$ acts as a built-in smoother, automatically suppressing high-frequency noise. This explicit dependence on $\sigma$ also simplifies hyperparameter tuning, allowing the use of validation loss to determine the optimal noise level—a task that is often difficult in other denoising models.

Despite its empirical success, the paper identifies several areas for future research. The theoretical convergence properties of RFFs specifically for score matching are not yet fully understood, and the current error bounds between the RFF solution and the exact kernel solution are not yet tight. Additionally, while the model performs well, it can occasionally "oversmooth" boundaries in multimodal cases, such as Mixture of Uniforms, leading to slight inaccuracies in estimating the relative weights of different components.

Conclusion

By combining Kernel Exponential Families with Random Fourier Features and Denoising Score Matching, this work provides a powerful and efficient tool for density estimation. The derivation of an analytical solution for the DSM objective represents a significant step forward in making kernel-based score matching practical for high-dimensional, large-scale data.

Summary updated

Abstract

The density estimation is one of the core problems in statistics. Despite this, existing techniques like maximum likelihood estimation are computationally inefficient in case of complex parametric families due to the intractability of the normalizing constant. For this reason, an interest in score matching has increased, being independent on the normalizing constant. However, such an estimator is consistent only for distributions with the full space support. One of the approaches to make it consistent is to add noise to the input data called Denoising Score Matching. In this work we build computationally efficient algorithm for density estimate using kernel exponential family as a model distribution. The usage of the kernel exponential family is motivated by the richness of this class of densities. To avoid calculating an intractable normalizing constant we use Denoising Score Matching objective. The computational complexity issue is approached by applying Random Fourier Features-based approximation of the kernel function. We derive an exact analytical expression for this case which allows dropping additional regularization terms based on the higher-order derivatives as they are already implicitly included. Moreover, the obtained expression explicitly depends on the noise variance, so that the validation loss can be straightforwardly used to tune the noise level. Along with benchmark experiments, the method was tested on various synthetic distributions to study the behavior of the method in different cases. The empirical study shows comparable quality to the competing approaches, while the proposed method being computationally faster. The latter one enables scaling up to complex high-dimensional data.
BibTeX
@article{tsymboi2022denoising,
  author = {Olga Tsymboi and Yermek Kapushev and Evgeny Burnaev and Ivan V. Oseledets},
  title = {{Denoising Score Matching via Random Fourier Features}},
  journal = {IEEE Access},
  year = {2022},
  doi = {10.1109/access.2022.3159976},
}
Figure