Profile Reconstruction from Private Sketches

Hao Wu, Rasmus Pagh

TL;DR

This paper presents a highly efficient, near-linear time algorithm for reconstructing dataset "profiles" (frequency distributions) from sketches protected by differential privacy. By treating the noise-reversal process as a signal processing problem—leveraging circulant matrices and the Fast Fourier Transform (FFT)—the authors achieve a massive computational speedup over previous methods while proving their error bounds are theoretically optimal.

Introduction

In data analysis, a profile (sometimes called a "histogram of histograms") is a fundamental statistic. Given a dataset of users, the profile answers questions like: "How many users appeared exactly once? Exactly twice? Exactly $k$ times?" This metric is essential for calculating rarity, prevalence, or the degree distribution of a social graph.

However, calculating profiles in the real world faces three major hurdles:

  1. Space Constraints: In distributed or streaming systems, storing the entire dataset is infeasible; a compact "sketch" is required.
  2. Updatability: As new data flows in, the sketch must be easily updatable without recomputing everything from scratch.
  3. Privacy: To protect individuals, the sketch must satisfy Differential Privacy (DP), ensuring that the presence or absence of a single person doesn't significantly change the output.

Previous work by Dwork et al. (2010) demonstrated that profiles could be reconstructed by adding noise to a histogram and then "reversing" that noise using Linear Programming (LP). However, their LP approach was computationally expensive (running in polynomial time) and lacked tight, high-probability error guarantees.

Methodology

The authors propose a framework to "invert" the effects of discrete Laplace noise added to a histogram. Their approach hinges on several clever mathematical observations:

  • Circulant Matrix Inversion: They show that the expected value of a noisy profile is a linear transformation of the true profile. Because the noise is symmetric and independent, this transformation can be represented as a circulant matrix.
  • FFT Acceleration: A key property of circulant matrices is that they can be diagonalized by the Discrete Fourier Transform. This allows the authors to replace slow Linear Programming with the Fast Fourier Transform (FFT), slashing the time complexity from polynomial to a near-linear $O(d + n \log n)$, where $d$ is the domain size and $n$ is the number of items.
  • Unfolding Clipped Histograms: In practice, DP histograms are often "clipped" to a specific range (e.g., $[0, n]$). The authors provide a recovery procedure that uses the memoryless property of geometric distributions to "unfold" these clipped values back into a distribution that behaves like standard, unclipped noise.
  • Violation Fixing: Raw matrix inversion might result in an "invalid" profile (e.g., containing negative values or fractions that don't sum to 1). To resolve this, they introduce a projection-based rounding algorithm that fixes these violations while strictly maintaining the theoretical error bounds.
Algorithm 3: The rounding procedure used to fix profile violations.

Evaluation and Theoretical Proofs

As a theoretical paper focused on algorithmic complexity and information-theoretic bounds, this work does not rely on specific real-world training datasets or empirical benchmarks. Instead, the authors evaluate their algorithm through rigorous mathematical proofs, guaranteeing its performance across any multiset of $n$ items from a finite domain $\mathcal{D}$.

Key Insights

  • The $1/\sqrt{d}$ Efficiency: The authors prove that the reconstruction error scales with $O(1/\sqrt{d})$. Interestingly, this means that as the domain size ($d$) grows, the relative accuracy of the profile reconstruction actually improves.
  • The "Updatability" Tax: A major contribution is an information-theoretic lower bound. Using a reduction from the "two-party inner product estimation" problem, they prove that for any updatable private sketch, an error of $\Omega(1/\sqrt{d})$ is unavoidable. This confirms that their algorithm is asymptotically optimal.
  • Symmetry as a Tool: By recognizing that the noise process is shift-invariant, they successfully transformed a complex optimization problem into a signal processing task, unlocking the use of the FFT.

Key Results

  • Speed: The algorithm runs in $O(d + n \log n)$ time, making it highly practical for large-scale streaming and distributed systems.
  • Accuracy: The error in $\ell_1, \ell_2,$ and $\ell_\infty$ norms is tightly bounded by $O(1/\sqrt{d})$.
  • Optimality: The provided matching lower bound proves that no other updatable private sketch can achieve a better error rate than their proposed method.

Limitations and Future Work

  • Updatability vs. Batch Processing: The lower bound of $\Omega(1/\sqrt{d})$ specifically targets updatable sketches. The authors note that if the sketch does not need to be updated (i.e., a "central" model where a curator has all data at once), better error bounds might be achievable.
  • Privacy Parameter $\epsilon$: While the dependence on the domain size $d$ is optimal, the authors acknowledge that the dependence on the privacy parameter $\epsilon$ (specifically for the $\ell_\infty$ norm) might have room for further refinement to match lower bounds found in simpler DP tasks.
  • Non-Laplacian Noise: The current work is tailored specifically to discrete Laplace noise. Exploring how these techniques translate to other noise distributions, such as Gaussian noise, in pan-private or distributed settings remains an open path for future research.

Summary updated

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 the algorithm from polynomial time to $O(d + n \log n)$, 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 = |\mathcal{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