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:
- 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.
- 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)$.
- 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.
- 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