M2M: A General Method to Perform Various Data Analysis Tasks from a Differentially Private Sketch

Florimond Houssiau, Vincent Schellekens, Antoine Chatalic, Shreyas Kumar Annamraju, Yves-Alexandre de Montjoye

Abstract

Differential Privacy (DP) often imposes a strict "privacy budget" that limits the number of queries an analyst can perform on a sensitive dataset. While private sketching offers a potential solution by compressing data into a single, reusable noisy vector, it traditionally requires the development of custom, task-specific algorithms for every new analysis. We present Moment-to-Moment (M2M), a general-purpose heuristic that enables an unlimited number of data exploration tasks—including calculating means, covariances, and training regression models—from a single differentially private sketch. By leveraging linear approximations in the sketch's feature space, M2M bypasses the need for specialized algorithm engineering, providing a versatile "universal adapter" for private data analysis.

Introduction

Differential Privacy (DP) is the gold standard for protecting individual privacy, yet its practical application is constrained by the privacy budget. Every query consumes a portion of this budget; once exhausted, the dataset must be retired to prevent privacy leakage. Private sketching addresses this by creating a compressed, noisy representation of the data. Due to the post-processing property of DP, this sketch can be queried indefinitely without further privacy loss.

However, sketches are highly compressed, and extracting useful insights usually requires designing complex, task-specific algorithms. This "engineering wall" has limited the adoption of sketching for general-purpose data exploration. M2M overcomes this barrier by treating the sketching process as a black box and using a linear approximation technique to estimate arbitrary functions of the data.

The M2M Framework

The M2M method bridges the gap between a compressed sketch and arbitrary analysis tasks through a four-step process:

  1. Sketch Generation: The data curator computes a sketch $\hat{z}_D$ by averaging a non-linear feature map $\Phi$ (such as Random Fourier Features or Hashing) over the dataset and adding DP-compliant noise.
  2. Function Approximation: To estimate the average of a target function $f(x)$ over the dataset, M2M seeks a weight vector $a$ such that a linear combination of the sketch's features approximates the target function: $\langle a, \Phi(x) \rangle \approx f(x)$.
  3. Synthetic Training: Because the analyst cannot access the raw data to find these weights, M2M utilizes "synthetic" training points generated from a prior distribution (e.g., a uniform distribution). The weights $a$ are then found by solving a ridge regression problem on this synthetic data.
  4. Estimation: The final estimate is obtained via the dot product $\langle a, \hat{z}_D \rangle$.

Implicit-M2M for Machine Learning

The authors also introduce implicit-M2M, which extends this logic to machine learning. Rather than approximating a single scalar value, implicit-M2M re-weights synthetic data to approximate the loss function of a model (such as logistic regression). This allows analysts to train predictive models directly from the sketch without needing the original sensitive records.

Key Insights

The Power of Linearity

The fundamental insight of M2M is that because the sketching operator is linear (it is a simple average), any linear model in the feature space of the sketch can effectively estimate generalized moments of the original data. This allows the sketch to serve as a foundation for a wide variety of statistical queries.

Noise-Aware Regularization

A critical technical contribution is the proof that the optimal way to handle DP noise within the sketch is through specific regularization. The authors demonstrate that the ridge regression parameter ($\lambda$) should be proportional to the noise variance added during the sketching process to ensure the most accurate results.

Black-Box Versatility

M2M is agnostic to the underlying sketching mechanism. It has been shown to work effectively with Random Fourier Features (RFF), Repeated Array-of-Counts (RACE), and standard Histograms (HIST), making it a flexible tool for various privacy architectures.

Experimental Evaluation

The authors evaluated M2M against three state-of-the-art Synthetic Data Generation (SDG) methods: DP-Copula, PrivBayes, and DP-WGAN. Testing was conducted on synthetic (Random10) and real-world datasets (LifeSci and Building Occupancy).

  • Versatility: M2M successfully estimated means, second-order moments, cumulative distribution functions (CDFs), and covariance matrices from a single sketch.
  • Performance: On the LifeSci dataset, M2M using RFF sketches performed comparably to or better than specialized SDG methods, particularly as the privacy budget ($\epsilon$) increased.
  • Machine Learning: Using implicit-M2M, the authors trained a logistic regression model on the Building Occupancy dataset, achieving an AUC of over 0.9. This performance rivaled dedicated DP-ERM (Empirical Risk Minimization) methods that consume the entire privacy budget for a single task.

Limitations and Future Directions

The primary challenge for M2M is distributional shift. The method's accuracy depends on the analyst's "prior" distribution used to generate synthetic training points. If the real data distribution differs significantly from this prior (e.g., the data is highly clustered while the prior is uniform), approximation error increases.

Future research directions include:

  • Using the sketch itself to refine the prior distribution (e.g., via Kernel Density Estimation).
  • Learning generative models directly from the sketch to produce higher-quality synthetic training data.
  • Exploring non-convex optimization techniques to improve the accuracy of loss minimization in implicit-M2M.

Summary updated

Abstract

Differential privacy is the standard privacy definition for performing analyses over sensitive data. Yet, its privacy budget bounds the number of tasks an analyst can perform with reasonable accuracy, which makes it challenging to deploy in practice. This can be alleviated by private sketching, where the dataset is compressed into a single noisy sketch vector which can be shared with the analysts and used to perform arbitrarily many analyses. However, the algorithms to perform specific tasks from sketches must be developed on a case-by-case basis, which is a major impediment to their use. In this paper, we introduce the generic moment-to-moment ( $$\textrm{M}^2\textrm{M}$$ ) method to perform a wide range of data exploration tasks from a single private sketch. Among other things, this method can be used to estimate empirical moments of attributes, the covariance matrix, counting queries (including histograms), and regression models. Our method treats the sketching mechanism as a black-box operation, and can thus be applied to a wide variety of sketches from the literature, widening their ranges of applications without further engineering or privacy loss, and removing some of the technical barriers to the wider adoption of sketches for data exploration under differential privacy. We validate our method with data exploration tasks on artificial and real-world data, and show that it can be used to reliably estimate statistics and train classification models from private sketches.
BibTeX
@inproceedings{houssiau2022m,
  author = {Florimond Houssiau and Vincent Schellekens and Antoine Chatalic and Shreyas Kumar Annamraju and Yves-Alexandre de Montjoye},
  title = {{M2M: A General Method to Perform Various Data Analysis Tasks from a Differentially Private Sketch}},
  booktitle = {STM},
  year = {2022},
  url = {https://openreview.net/forum?id=kiNF7IUm0RG},
}
Figure