Differential privacy with compression

By Shuheng Zhou, Katrina Ligett, Larry A. Wasserman. 2009

67 citations recorded by the source corpus.

This work studies formal utility and privacy guarantees for a simple multiplicative database transformation, where the data are compressed by a random linear or affine transformation, reducing the number of data records substantially, while preserving the number of original input variables.We provide an analysis framework inspired by a recent concept known as differential privacy. Our goal is to show that, despite the general difficulty of achieving the differential privacy guarantee, it is possible to publish synthetic data that are useful for a number of common statistical learning applications. This includes high dimensional sparse regression [24], principal component analysis (PCA), and other statistical measures [16] based on the covariance of the initial data.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Privacy Aware Learning (2012, background): “More recently, there has been a large amount of computationally oriented work on privacy [Dwork et al. 2006; Dwork 2008; Zhou et al. 2009a; Wasserman and Zhou 2010; Hall et al. 2011; Dinur and Nissim 2003; Blum et al. 2008; Chaudhuri et al. 2011; Rubinstein et al. 2012].”
Differentially Private Empirical Risk Minimization (2009, positive): “Wasserman and Zhou (2010) provide a more statistical view of differential privacy, and Zhou et al. (2009) provide a technique of generating synthetic data using compression via random linear or affine transformations.”
Privacy via the Johnson-Lindenstrauss Transform (2012, methodology): “The high-level idea of using a condensed representation of the input obtained via some randomized transformation in order to protect privacy while preserving the utility of some computations has been explored by [38, 46, 29, 45, 32, 12].”
Compressive mechanism: utilizing sparse representation in differential privacy (2011, unknown): “[48, 47, 32] apply random projections to differential privacy.”
Differentially Private Model Selection via Stability Arguments and the Robustness of the Lasso (2013, result): “Zhou et al. (2009) studied the specific problem of private sparse regression in low dimension, where p n; their techniques do not give meaningful results when p ≥ n. Kifer et al. (2012) gave the first results on private sparse regression in high dimension.”
Sample Complexity Bounds for Differentially Private Learning (2011, background): “Zhou et al. (2009) study some issues in defining differential privacy when dealing with continuous outcomes; however, they do not consider the question of learning classifiers on such data.”
Near-Optimal Algorithms for Differentially-Private Principal Components (2012, background): “, 2006b; Wasserman and Zhou, 2010; Dwork et al., 2006a). The second privacy guarantee is weaker; the parameter δ bounds the probability of failure, and is typically chosen to be quite small. In our experiments we chose small but constant δ—Ganta et al. (2008) suggest δ < 1 n2 is more appropriate.”
A rigorous and customizable framework for privacy (2012, methodology): “Finally, we use Pufferfish to provide approximate privacy semantics for δ-constrained α-differential privacy [41] and ZLW distributional privacy [41] (Section 7.”
Randomized requantization with local differential privacy (2016, background): “Fourier coefficients drawn according to P = N (10, 2) but we optimize over the set P = {N (μ, σ) : μ ∈ [8, 12], σ ∈ [1, 3]}.”
A rate-disortion perspective on local differential privacy (2014, background): “Other researchers have also studied ratedistortion approaches for differential privacy [5], as well as the structure of optimal mechanisms for function computa-”
Pufferfish (2014, methodology): “P uffer F ish( S , pairs ) satisﬁes the axioms of convexity and transformation invariance.”