Profile Reconstruction from Private Sketches

Hao Wu, Rasmus Pagh

Abstract

Given a multiset of $n$ items from $\mathcal{D}$, the profile reconstruction problem is to estimate, for $t = 0, 1, \dots, n$, the fraction $\vec{f}[t]$ of items in $\mathcal{D}$ that appear exactly $t$ times. We consider differentially private profile estimation in a distributed, space-constrained setting where we wish to maintain an updatable, private sketch of the multiset that allows us to compute an approximation of $\vec{f} = (\vec{f}[0], \dots, \vec{f}[n])$. Using a histogram privatized using discrete Laplace noise, we show how to "reverse" the noise, using an approach of Dwork et al. (ITCS '10). We show how to speed up their LP-based technique from polynomial time to $O(d + n \log n)$, where $d = |\mathcal{D}|$, and analyze the achievable error in the $\ell_1$, $\ell_2$ and $\ell_\infty$ norms. In all cases the dependency of the error on $d$ is $O( 1 / \sqrt{d})$ -- we give an information-theoretic lower bound showing that this dependence on $d$ is asymptotically optimal among all private, updatable sketches for the profile reconstruction problem with a high-probability error guarantee.

Introduction

In data analysis, a profile (also known as a "histogram of histograms") is a fundamental statistic. For a multiset of items, the profile describes the distribution of frequencies: what fraction of the domain appears exactly zero times, once, twice, and so on. This is crucial for estimating unique element counts in streams or degree distributions in social networks.

When handling sensitive data, Differential Privacy (DP) is often employed to protect individual records. A common method is maintaining a "private sketch"—a histogram where counts are perturbed by random noise, such as the Discrete Laplace mechanism. However, this noise "smears" the profile, making simple counting inaccurate. Previous methods to "reverse" this noise relied on computationally expensive Linear Programming (LP) solvers. This paper presents a near-linear time algorithm for reconstructing profiles with provable optimality.

Methodology

The proposed pipeline "inverts" the effects of the Discrete Laplace Mechanism through several key stages:

1. Private Profile Generation

The process begins with the creation of a perturbed profile. As shown in Algorithm 1, the input vector is processed by adding noise sampled from a Discrete Laplace distribution to each frequency count.

Algorithm 1: The Private Profile Generator adds Discrete Laplace noise to the input profile.

2. Matrix Inversion via FFT

The core insight is that the expected value of a noisy profile is a linear transformation of the true profile, represented by a circulant matrix. Because circulant matrices are diagonalized by the Fourier basis, the authors utilize the Fast Fourier Transform (FFT) to invert the transformation in $O(n \log n)$ time. This bypasses the need for general-purpose LP solvers.

Algorithm 2: The estimation procedure uses matrix inversion to reconstruct the profile from noisy observations.

3. Constrained Optimization and Rounding

Raw inversion may produce invalid profiles (e.g., negative values). The authors introduce a fast rounding procedure to project results back onto the space of valid probability distributions while maintaining error guarantees.

Key Results and Insights

  • Computational Efficiency: Reconstruction time is reduced from polynomial time to $O(d + n \log n)$, where $d$ is the domain size and $n$ is the number of items.
  • Privacy-Utility Optimality: The algorithm achieves an estimation error of $O(1/\sqrt{d})$ across $\ell_1, \ell_2,$ and $\ell_\infty$ norms. The paper provides an information-theoretic lower bound proving that this $1/\sqrt{d}$ dependence is asymptotically optimal for any private, updatable sketch.
  • Updatability: The algorithm works with sketches that can be updated as new data arrives, making it suitable for streaming and distributed environments.

Limitations and Future Work

While the dependence on domain size $d$ is optimal, the dependence on the privacy parameter $\epsilon$ (specifically $O(1/\epsilon^{1.5})$ for the $\ell_\infty$ norm) may not be perfectly tight compared to the $\Omega(1/\epsilon)$ lower bound for simpler counters. Future work could explore extending these bounds to the local differential privacy model and conducting empirical validations on real-world datasets like password frequencies or browser telemetry.

Summary updated

Abstract

Given a multiset of $n$ items from $\mathcal{D}$, the \emph{profile reconstruction} problem is to estimate, for $t = 0, 1, \dots, n$, the fraction $\vec{f}[t]$ of items in $\mathcal{D}$ that appear exactly $t$ times. We consider differentially private profile estimation in a distributed, space-constrained setting where we wish to maintain an updatable, private sketch of the multiset that allows us to compute an approximation of $\vec{f} = (\vec{f}[0], \dots, \vec{f}[n])$. Using a histogram privatized using discrete Laplace noise, we show how to ``reverse'' the noise, using an approach of Dwork et al.~(ITCS '10). We show how to speed up their LP-based technique from polynomial time to $O(d + n \log n)$, where $d = |\mathcal{D}|$, and analyze the achievable error in the $\ell_1$, $\ell_2$ and $\ell_\infty$ norms. In all cases the dependency of the error on $d$ is $O( 1 / \sqrt{d})$ -- we give an information-theoretic lower bound showing that this dependence on $d$ is asymptotically optimal among all private, updatable sketches for the profile reconstruction problem with a high-probability error guarantee.
BibTeX
@inproceedings{wu2024profile,
  author = {Hao Wu and Rasmus Pagh},
  title = {{Profile Reconstruction from Private Sketches}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=AqGCEHK9dZ},
}
Figure