Source-linked AI summary
Marginal Release Under Local Differential Privacy
Tejas Kulkarni, Graham Cormode, Divesh Srivastava
TL;DR
Accurate multidimensional marginals support correlation analysis and other data tasks, but releasing them while protecting each data subject locally remains challenging. The paper develops and analyzes LDP marginal-release algorithms, including Hadamard-transform methods. The evaluated applications favor Hadamard-based releases, which the authors find preferable and most scalable in practice.
Problem
Prior LDP work focused on one-dimensional statistics, while useful correlations and many data-analysis tasks require low-order marginals; prior local-model work on two-way marginals was limited.
Source: §1 · p. 2Method
Results
Hadamard-based methods are most effective across tested data dimensionalities and marginal sizes, and are preferable and most scalable in Bayesian modeling and correlation-testing applications.
Source: §1 · p. 2Takeaways & Limitations
The authors conclude that Hadamard-based marginal release has strong theoretical guarantees and is suitable for incorporation into browser and mobile LDP deployments.
Source: §7 · p. 12The correlation significance test is uncorrected; developing robust correlation tests under LDP is left for future work.
Source: §6.2 · p. 10
Abstract
from arXiv · showhide
Many analysis and machine learning tasks require the availability of marginal statistics on multidimensional datasets while providing strong privacy guarantees for the data subjects. Applications for these statistics range from finding correlations in the data to fitting sophisticated prediction models. In this paper, we provide a set of algorithms for materializing marginal statistics under the strong model of local differential privacy. We prove the first tight theoretical bounds on the accuracy of marginals compiled under each approach, perform empirical evaluation to confirm these bounds, and evaluate them for tasks such as modeling and correlation testing. Our results show that releasing information based on (local) Fourier transformations of the input is preferable to alternatives based directly on (local) marginals.
1. INTRODUCTION
The paper addresses how to release useful low-order marginals under local differential privacy, where each person protects their own data. It develops and evaluates methods for this task, finding that Hadamard-based releases are preferable in the evaluated applications.
Background
- LDP lets each participant ensure their disclosed information meets the privacy guarantee without revealing raw data to a trusted aggregator.The paper situates this model against the trusted-aggregator approach to differential privacy.Source: §1 · p. 1
Motivation
- Prior LDP work focused on one-dimensional frequency statistics, which do not capture the rich correlations present in real data.Low-order marginals provide population-level correlations useful for modeling, hypothesis testing, and recommender systems.Source: §1 · pp. 1–2
- Low-order marginals are widely useful for understanding distributions, identifying correlations, query answering, statistical inference, and machine learning.The paper focuses on two-way and three-way marginals.Source: §1 · p. 2
Problem
- The paper targets accurate, on-demand release of arbitrary marginals under LDP, addressing limited prior work on two-way marginals in that model.Marginal cells can expose sensitive attributes, for example when a salary-and-zip-code cell identifies a sole high earner.Source: §1 · p. 2
Our Contributions
- Hadamard-based methods are most effective across tested data dimensionalities and marginal sizes, capturing more information per user than direct data-space methods.The evaluation also finds the Hadamard-based approach preferable and most scalable for Bayesian modeling and correlation testing.Source: §1 · p. 2
2. RELATED WORK
Prior LDP work addressed single attributes and heavy hitters, while much private marginal-release work assumed a trusted aggregator. The paper identifies why existing approaches do not directly meet the local-model challenge of perturbing individual sparse records while preserving correlations.
2.1 Local Differential Privacy (LDP)
- Earlier LDP methods cover randomized-response frequency collection and one-dimensional histograms or heavy hitters, but not the multidimensional marginals studied here.A Hadamard-isomorphic basis had also been proposed for one-dimensional data, rather than multidimensional data.Source: §2.1 · pp. 2–3
2.2 Publishing Marginals Privately
- Prior work on releasing individual marginals or datacubes generally assumes a trusted aggregator.The paper reviews representative approaches for whether they can be applied under LDP.Source: §2.2 · p. 3
- Sensitivity-calibrated noise transfers to LDP for a single marginal, and prior work also applies such releases to data transformations.The paper refines and analyzes transformed marginal release under LDP.Source: §2.2 · p. 3
- Centralized subset selection does not naturally translate to LDP, while multiplicative weights needs coordination that users with individual records cannot readily provide.Chebyshev-polynomial perturbation could plausibly adapt, but the required steps are not immediate.Source: §2.2 · p. 3
- The unresolved challenge is independently perturbing each user's sparse record while preserving the underlying correlations.The paper therefore develops new algorithms and analyses for the local model.Source: §2.2 · p. 3
3. MODEL AND PRELIMINARIES
The paper models users as holding binary attributes and an untrusted aggregator seeking arbitrary k-way marginals under LDP. It introduces local randomization mechanisms and marginal and Hadamard-transform notation used to formulate the release problem.
3. MODEL AND PRELIMINARIES
- Users have binary attribute vectors, and an untrusted aggregator may pose arbitrary queries over at most k attributes without knowing the queries in advance.The goal is accurate reconstruction of k-way marginal tables under LDP.Source: §3 · p. 3
3.1 Local Differential Privacy
- LDP requires each user's output to be perturbed, providing plausible deniability but typically more noise than trusted-aggregator DP.For simplicity, the paper states results with a shared privacy parameter ϵ.Source: §3.1 · pp. 3–4
- Budget splitting applies (ϵ/m)-LDP to each of m items, while sampling one item and releasing it with ϵ-LDP can improve accuracy in general.The paper analyzes its protocols as confirming this accuracy advantage.Source: §3.1 · p. 4
- Preferential sampling favors the true index in a sparse vector, whereas parallel randomized response independently perturbs its bits and also meets ϵ-LDP.For preferential sampling, the reported true index has probability ps and each incorrect index probability (1−ps)/(m−1).Source: §3.1 · p. 4
3.2 Marginal Tables
- A k-way marginal sums full-table cells that agree on the selected attributes; the full set of k-way marginals includes marginals of order j ≤ k.The release problem is to approximate any such marginal of the full distribution.Source: §3.2 · p. 4
- The target is small total-variation error for the marginals, with bounds expressed using population size N, dimension d, marginal size k, and privacy parameter ϵ.The stated aim is to achieve the guarantee with at least constant probability, with larger-error probability made arbitrarily small.Source: §3.2 · pp. 4–5
- Hadamard transforms spread information in sparse inputs, and coefficients of degree at most k suffice to evaluate any k-way marginal.For d = 4 and k = 2, the text gives 11 needed coefficients out of 16 total.Source: §3.2 · p. 5
4. PRIVATE MARGINAL RELEASE
The section builds six baseline algorithms by combining choices about whether to work with full inputs or marginals and whether to release direct values or Hadamard coefficients. It develops accuracy guarantees and compares input-based, marginal-based, and EM approaches for private marginal release.
4. PRIVATE MARGINAL RELEASE
- The six baseline algorithms combine two choices: whether to represent the data as marginals or a full input distribution, and whether to release direct values or sampled Hadamard coefficients.The Hadamard approach samples a coefficient and releases it via randomized response; preferential and parallel randomized response require sparse inputs.Source: §4 · p. 5
4.1 Accuracy Guarantees
- The accuracy analysis provides unbiased estimates and bounds marginal total variation error as a function of sampling and randomized-response parameters.The analysis chooses a threshold c proportional to 1/√(Nps) to obtain constant probability.Source: §4.1 · pp. 5–6
4.2 Input Perturbation Based Methods
- INPRS perturbs all 2^d input locations, INPPS reports a preferentially sampled location, and INPHT releases a sampled Hadamard coefficient needed to reconstruct target marginals.The input-based analysis assumes N is at least proportional to 2^d.Source: §4.2 · p. 6
- For k = 2, INPHT uses O(d) coefficients, compared with a 2^(d/2) term for INPRS.For k < d, INPHT's required coefficient count is below 2^d.Source: §4.2 · p. 6
4.3 Marginal Perturbation Based Methods
- INPHT has a d^(k/2) dimension factor, compared with at least (2^d)^(k/2) for marginal-based methods and 2^d for direct input methods, giving it the best asymptotic performance.The paper notes that these bounds can be close in practical regimes such as k = 2.Source: §4.3 · p. 7
- Marginal-based methods incur a dimension factor of at least (2^d)^(k/2), while MARGHT does not share information across marginals.The section gives bounds for MARGPS and MARGHT and a separate bound for MARGRS; each method samples or materializes information at the marginal level.Source: §4.3 · p. 7
4.4 Expectation-Maximization Heuristic
- INPEM uses budget sharing and iterative expectation maximization, but has no worst-case accuracy guarantee and performs less accurately than the new methods.In some cases, EM stops after one step and returns the uniform prior.Source: §4.4 · p. 7
5. EXPERIMENTAL EVALUATION
The experiments compare marginal-release algorithms on MovieLens and NYC Taxi, testing reconstruction error across population size, privacy budget, and dimensionality, then evaluating an EM alternative.
5.1 Experimental Setting
- Experiments use MovieLens and NYC Taxi records, sample 50K–0.5M users at ϵ=0.2–1.4, and repeat each small-marginal reconstruction ten times.The study focuses on k=1, 2, 3 marginals.Source: §5.1 · p. 8
5.2 Impact of varying population size N
- INPPS degrades rapidly with d and may not improve with N, while INPHT has the lowest or near-lowest error; MARGPS beats MARGRS and can outperform MARGHT.INPRS is among the better methods at smaller d and k, but its runtime scales with 2^d; MARGRS becomes hard to justify at larger k because it materializes the full marginal.Source: §5.2 · pp. 8–9
- As N grows, error falls for all six algorithms, roughly halving when the population quadruples; error generally rises with k and d, with algorithm-dependent scaling.For the population-size comparison, ϵ=1.1 and MovieLens are fixed while N varies.Source: §5.2 · p. 8, Figure 4 · p. 9
5.3 Impact of privacy parameter ϵ
- INPHT outperforms the other algorithms across configurations as ϵ varies and is the most consistently accurate, fast method across the experiments.The authors rank INPHT first, followed by MARGPS and MARGHT.Source: §5.3 · p. 9, §5.2 · p. 9
- As ϵ increases, error declines; INPPS, INPRS, and MARGRS become unfavorable for k≥2, while MARGPS’s advantage over MARGHT depends on ϵ, d, and k.MARGHT is preferable at small ϵ when d and k are larger.Source: §5.3 · p. 9
5.4 Impact of increasing dimensionality d
- INPEM gives reasonable results that improve with ϵ, but is several times less accurate than INPHT and MARGPS, lacks an accuracy guarantee, and can take thousands of iterations.Its convergence time was observed to grow linearly with d; the unbiased estimators are found instantaneously.Source: §5.4 · p. 9
6. APPLICATIONS AND EXTENSIONS
The section applies private marginals to association testing and Bayesian modeling, then extends the methods to categorical attributes. Across these applications, the reported results favor the Hadamard-based INPHT approach.
6. APPLICATIONS AND EXTENSIONS
- The applications use 1- and 2-way marginals for association testing and dependency-tree fitting, selecting MARGPS and INPHT based on accuracy results.The section also discusses extending the methods to non-binary attributes.Source: §6 · pp. 9–10
6.2 Bayesian Modeling
- For k=2 on NYC taxi data at larger d, the best algorithms outperform INPEM at small ε; INPHT trees nearly match non-private mutual information on MovieLens.MARGPS is less accurate at low ε but catches up as ε increases.Source: Figure 6 · p. 11, Figure 8 · p. 11, §6.2 · p. 11
6.1 Association Testing
- INPHT χ² values are close to non-private values, while MARGPS often misses dependence for pairs whose statistics are near the critical value.The comparison uses a 95% confidence interval and a log-scale plot.Source: §6.1 · p. 10, Figure 7 · p. 11
6.3 Categoric Attributes
- Categorical attributes can be encoded with ⌈log₂ r⌉ bits each; INPHT on this binary encoding provides an effective solution, particularly for low-cardinality data.The paper defines effective binary dimension as the sum of these per-attribute bit counts.Source: §6.3 · p. 11
- An Efron-Stein decomposition can supply coefficients for categorical marginals, and the authors conjecture that a resulting low-order scheme could be among the best solutions.The proposed approach would add noise to a randomly selected coefficient and let an aggregator construct an unbiased estimate.Source: §6.3 · pp. 11–12
7. CONCLUDING REMARKS
The conclusion finds Fourier (Hadamard)-based methods effective for private marginal release, with strong theoretical guarantees and potential for browser and mobile deployment.
7. CONCLUDING REMARKS
- Fourier (Hadamard)-based methods are effective for private marginal release and have strong theoretical guarantees.The paper addresses release of population marginal statistics under local differential privacy.Source: §7 · p. 12
- The algorithms are described as straightforward to implement and suitable for current browser and mobile LDP deployments.Incorporation would require only small modifications to RAPPOR or iOS.Source: §7 · p. 12
- The INPHT user routine samples a coefficient index from Hk and computes a scaled coefficient value from the user's signal index.The routine is presented as an example of the user-side procedure.Source: §7 · p. 13
APPENDIX
The appendix presents the INPHT aggregator routine, which collects users’ coefficient reports and uses them to evaluate target marginals.
APPENDIX
- The aggregator sets the zeroth Hadamard coefficient to 1.Source: APPENDIX · p. 13
- It populates an array of coefficient reports from users and computes an estimate for each coefficient using its reported frequency count.Source: APPENDIX · p. 13
- The aggregator applies Lemma 2 to the estimated coefficients to evaluate any marginal of order at most k.Source: APPENDIX · p. 13
A. DEFERRED PROOFS
The deferred proofs establish accuracy by analyzing per-user estimation errors, combining estimates, and bounding the resulting marginal reconstruction error. The INPHT analysis specifically uses Hadamard coefficients to construct marginals.
A. DEFERRED PROOFS
- The appendix describes INPHT as sampling a relevant coefficient per user, applying randomized response, then bias-correcting and normalizing reports before evaluating marginals.Source: A. DEFERRED PROOFS · p. 13
- The general proof strategy first obtains an unbiased estimate of each user's contribution, combines user estimates for the population, and analyzes their variance to bound error.Source: A. DEFERRED PROOFS · p. 13
- For the marginal-based analysis, a union bound controls errors across input estimates, followed by a Hoeffding bound on the sums used to reconstruct marginal entries.The resulting total-variation guarantee is obtained by summing the entrywise errors.Source: A. DEFERRED PROOFS · p. 14
- The INPRS proof analyzes errors when a user samples the correct or an incorrect location, then combines entry estimates to bound marginal total-variation error.Source: A. DEFERRED PROOFS · p. 14
- The INPHT proof scales user inputs to ±1 Hadamard coefficients, estimates the coefficients, and uses their linear relationship to marginals to bound reconstruction error.The proof applies a concentration bound to sums of coefficient estimates.Source: A. DEFERRED PROOFS · pp. 14–15