PaperlayerView exact revision on arXiv

Source-linked AI summary

Collecting and Analyzing Multidimensional Data with Local Differential Privacy

Ning Wang, Xiaokui Xiao, Yin Yang, Jun Zhao, Siu Cheung Hui, Hyejin Shin, Junbum Shin, Ge Yu

arXiv:1907.00782v1cs.CRcs.CYcs.DBcs.LG

TL;DR

The paper addresses insufficiently effective collection of multidimensional data under LDP, including the basic problem of estimating numeric means. It proposes PM and HM, extends them to mixed numeric and categorical records, and builds an LDP-compliant SGD algorithm; experiments report consistent advantages over existing methods.

  • Problem

    Existing LDP research largely targets complex data or analyses, while numeric and multidimensional data collection remains insufficiently addressed.

  • Method

    The paper proposes PM and HM for numeric data, extends them to multidimensional mixed-type records, and uses them to collect private gradients for LDP-compliant SGD.

  • Results

    Experiments on real datasets report that PM and HM consistently outperform existing approaches across mean estimation and empirical-risk-minimization tasks.

  • Takeaways & Limitations

    The proposed mechanisms provide accurate LDP statistics for mixed-type multidimensional records and support machine-learning models including linear regression, logistic regression, and SVM classification.

Abstract

from arXiv · show

Local differential privacy (LDP) is a recently proposed privacy standard for collecting and analyzing data, which has been used, e.g., in the Chrome browser, iOS and macOS. In LDP, each user perturbs her information locally, and only sends the randomized version to an aggregator who performs analyses, which protects both the users and the aggregator against private information leaks. Although LDP has attracted much research attention in recent years, the majority of existing work focuses on applying LDP to complex data and/or analysis tasks. In this paper, we point out that the fundamental problem of collecting multidimensional data under LDP has not been addressed sufficiently, and there remains much room for improvement even for basic tasks such as computing the mean value over a single numeric attribute under LDP. Motivated by this, we first propose novel LDP mechanisms for collecting a numeric attribute, whose accuracy is at least no worse (and usually better) than existing solutions in terms of worst-case noise variance. Then, we extend these mechanisms to multidimensional data that can contain both numeric and categorical attributes, where our mechanisms always outperform existing solutions regarding worst-case noise variance. As a case study, we apply our solutions to build an LDP-compliant stochastic gradient descent algorithm (SGD), which powers many important machine learning tasks. Experiments using real datasets confirm the effectiveness of our methods, and their advantages over existing solutions.

I. INTRODUCTION

The paper studies collecting multidimensional numeric and categorical data under LDP, where users perturb records locally before aggregation. It proposes PM and HM, extends them to multidimensional data, and applies them to LDP-compliant SGD.

  • Motivation: LDP has been deployed in systems including Chrome, iOS, macOS, and Windows Insiders, with users sending only locally randomized data to an aggregator.This protects users because true private values do not leave their devices and also limits the aggregator’s access to exact private information.
  • Problem: Existing LDP work emphasizes complex data or analyses, while numeric-data collection and its extension to multidimensional records remain insufficiently addressed.For values in [−1, 1], prior options include unbounded Laplace noise or perturbed outputs outside the original domain; multidimensional extension is non-trivial.
  • Contributions: The paper proposes Piecewise Mechanism (PM) and Hybrid Mechanism (HM) for numeric attributes, with HM’s worst-case noise variance at least no worse and usually better than existing methods.HM is built upon PM, while the paper reports higher or comparable accuracy against prior solutions.
  • Contributions: PM and HM extend to multidimensional data containing numeric and categorical attributes while achieving asymptotically optimal error and remaining simple to implement.For multidimensional numeric data, the proposed methods have a smaller constant than Duchi et al.’s asymptotically optimal solution.
  • Applications: An LDP-compliant SGD algorithm uses the proposed mechanisms to collect private gradients, and real-dataset experiments report consistent advantages over existing approaches.The experiments cover varying users, dimensionality, privacy budgets, and empirical-risk-minimization tasks; more users and lower dimensionality improve accuracy.
  • Applications: The mechanisms support mean and frequency estimation as well as empirical-risk-minimization models including linear regression, logistic regression, and SVM classification.Categorical frequencies can be transformed into means through one-hot encoding, and the paper focuses on these three machine-learning tasks.

A. Existing Solutions

Existing solutions collect numeric data under LDP using Laplace noise or bounded randomized outputs, but their variance advantages depend on the privacy budget and input value. These trade-offs motivate a perturbation method combining bounded outputs with values close to the input.

  • Laplace mechanism: The Laplace mechanism adds zero-mean noise to a value in [−1, 1], and the aggregator estimates the mean by averaging perturbed values.Its noise variance is 8/ϵ^2.
  • Other mechanisms: SCDF and Staircase inject noise from a piece-wise constant distribution, with Staircase optimal for unbounded input values.The paper experimentally compares these methods with the proposed solutions.
  • Duchi et al.’s solution: Duchi et al.’s one-dimensional solution releases a perturbed value through a Bernoulli-based algorithm and yields an unbiased estimator.The aggregator computes the mean by averaging the released tuples.
  • Deficiencies of existing solutions: The motivating design combines Duchi et al.’s confined output range with Laplace’s ability to keep released values close to the input with reasonably large probability.This intuition leads to a new perturbation method.

B. Piecewise Mechanism

The Piecewise Mechanism (PM) perturbs numeric values using a bounded, piecewise-constant output distribution under LDP. Its worst-case variance is strictly below Laplace’s and becomes preferable to Duchi et al.’s solution for ϵ above 1.29, while favoring small-magnitude inputs.

  • PM takes a numeric value in [−1, 1] and outputs a perturbed value using a bounded piecewise-constant distribution.Its output range is bounded by [−C, C], unlike the unbounded outputs of SCDF and Staircase.
  • PM satisfies ϵ-local differential privacy and returns an unbiased estimator after scaling for a general domain [−r, r].The user must know the domain bound r.
  • PM’s worst-case variance is considerably smaller than Duchi et al.’s solution when ϵ ≥ 1.29 and strictly smaller than Laplace’s for every ϵ.For ϵ < 1.29, PM’s variance is only slightly larger than Duchi et al.’s.
  • PM’s variance decreases as |t_i| decreases, making it especially effective when input values are concentrated near zero.Duchi et al.’s solution exhibits the opposite variance trend with respect to |t_i|.
  • The aggregator estimates the mean by averaging perturbed values, whose estimator variance is 1/n times the average output variance.The paper states a corresponding accuracy guarantee in Lemma 2.

C. Hybrid Mechanism

The Hybrid Mechanism (HM) combines PM with Duchi et al.’s solution by selecting between them according to the input and privacy parameter. This preserves PM’s advantages while achieving worst-case variance no higher than competing methods, with HM reducing to Duchi et al.’s solution for small ϵ.

  • HM combines PM and Duchi et al.’s solution to avoid PM’s occasional worst-case disadvantage relative to Duchi et al.’s method.The mechanism is designed to preserve PM’s strengths while remaining no worse than Duchi et al.’s solution.
  • HM chooses PM or Duchi et al.’s solution based on a coin flip with head probability α and the input value’s region.Heads invoke PM, while tails invoke Duchi et al.’s solution.
  • HM often dominates both PM and Duchi et al.’s solution in minimizing worst-case noise variance.The paper characterizes this comparison through threshold privacy parameters and the one-dimensional case in Table I.
  • HM’s worst-case noise variance is consistently no higher than the compared methods, and HM reduces to Duchi et al.’s solution when ϵ ≤ ϵ∗.PM’s accuracy is close to HM’s in the reported comparison.

IV. COLLECTING MULTIPLE ATTRIBUTES

Collecting multiple attributes separately requires dividing the privacy budget across dimensions, which can substantially reduce utility as dimensionality grows. The paper identifies this as a central multidimensional-data challenge.

  • A straightforward multidimensional solution collects each attribute separately using a single-attribute mechanism with privacy budget ϵ/d.The composition theorem then gives ϵ-LDP for the full tuple.
  • Splitting the privacy budget across d attributes yields inferior utility because the resulting error can grow super-linearly with d.The paper notes that this can become excessive when d is large.

A. Existing Solution for Multiple Numeric Attributes

Duchi et al.’s multidimensional numeric mechanism perturbs vectors in a scaled binary domain and lets the aggregator average each attribute. It provides an unbiased mean estimator with an asymptotically optimal error bound, but does not support mixed numeric and categorical tuples.

  • Duchi et al.’s solution takes t_i ∈ [−1, 1]^d and outputs a perturbed vector whose coordinates lie in {−B, B}.The scaling factor B depends on d and ϵ.
  • The aggregator estimates each attribute’s mean by averaging the corresponding coordinates of the perturbed vectors.The scaling factor ensures that a perturbed attribute has the same expected value as the exact attribute.
  • Each sampled coordinate is processed through a single-attribute mechanism to obtain a noisy value.The method samples k attribute indices uniformly without replacement before perturbation.
  • Duchi et al.’s estimator is unbiased for each attribute mean and has an asymptotically optimal error bound.These guarantees are stated for the multidimensional numeric setting.
  • The method cannot handle tuples combining numeric and categorical attributes, motivating the paper’s PM and HM extensions.Those extensions aim to retain the privacy and asymptotic-error guarantees while supporting arbitrary attribute combinations.

B. Extending PM and HM for Multiple Numeric Attributes

The paper extends PM and HM to multidimensional numeric tuples by sampling and perturbing a subset of attributes, balancing privacy allocation against estimation error. The resulting estimators retain asymptotically optimal accuracy, while both mechanisms improve worst-case variance over Duchi et al.’s solution.

  • Multidimensional numeric mechanism: Algorithm 4 samples k attributes uniformly without replacement and perturbs each sampled numeric value using PM or HM with privacy budget ϵ/k.Each perturbed value is scaled by d/k before submission.
  • Multidimensional numeric mechanism: Choosing k balances the reduced noise from allocating ϵ/k per sampled attribute against the additional estimation error from sampling only k of d attributes.The paper derives k by minimizing Algorithm 4’s worst-case noise variance.
  • Multidimensional numeric mechanism: Algorithm 4 satisfies ϵ-local differential privacy and produces a noisy tuple for each input tuple.
  • Accuracy guarantees: The mean estimator for each numeric attribute matches Duchi et al.’s accuracy guarantee and is asymptotically optimal.
  • Accuracy guarantees: For any d > 1 and ϵ > 0, both PM and HM outperform Duchi et al.’s solution in worst-case noise variance.
  • Accuracy guarantees: For d = 5, 10, 20, 40, HM’s worst-case variance is at most 77% of Duchi et al.’s, while PM’s is also smaller.

C. Handling Categorical Attributes

The multidimensional extension also handles categorical attributes by sampling attributes, applying numeric perturbation to numeric fields, and using any single-attribute ϵ-LDP categorical mechanism for categorical fields. The aggregator then estimates numeric means and categorical value frequencies.

  • Attribute-wise perturbation: Users sample k attributes uniformly from the d attributes before submitting their perturbed values.
  • Attribute-wise perturbation: For each sampled attribute, the user applies numeric perturbation to numeric data or a single-attribute categorical mechanism with privacy budget ϵ/k.
  • Aggregation: The aggregator estimates each numeric attribute’s mean using the multidimensional numeric procedure.
  • Aggregation: For a categorical attribute, the aggregator estimates the frequency of each value by comparing submitted perturbed values with that value.
  • Accuracy: The frequency estimator’s accuracy depends on dimensionality and the accuracy of the single-attribute categorical perturbation algorithm.

V. STOCHASTIC GRADIENT DESCENT UNDER LOCAL DIFFERENTIAL PRIVACY

The paper applies its mechanisms to LDP-compliant SGD for empirical-risk-minimization models, including linear regression, logistic regression, and SVM classification. Users privately submit clipped noisy gradients, which the aggregator averages for parameter updates, while repeated participation degrades performance under privacy composition.

  • Learning tasks: The SGD case study targets linear regression, logistic regression, and SVM classification under ϵ-LDP.
  • SGD procedure: SGD starts from β0 and iteratively updates parameters using a gradient and learning rate γt.
  • Private gradient collection: Because gradients are unavailable directly, users submit noisy gradients after clipping every entry to [−1, 1], and the aggregator updates parameters using their mean.
  • Privacy composition: Users participating in multiple iterations must divide the privacy budget across iterations, setting ϵi = ϵ/m in the described case.
  • Privacy composition: With m > 1 participation, the group size becomes m2 times larger and the total number of iterations is inversely proportional to 1/m, degrading algorithm performance.

VI. EXPERIMENTS

The experiments evaluate accuracy on real census datasets from Brazil and Mexico and use figures covering numeric mean estimation, categorical frequency estimation, and synthetic multidimensional numeric data. The datasets contain millions of records with mixed numeric and categorical attributes.

  • Evaluation metrics: Figure 4 reports result accuracy for mean estimation on numeric attributes and frequency estimation on categorical attributes.
  • Synthetic evaluation: Figure 5 evaluates result accuracy on synthetic 16-dimensional datasets whose dimensions follow truncated Gaussian distributions N(µ, 1/16).
  • Datasets: The evaluation uses BR and MX census datasets from Brazil and Mexico, each containing 4M records.
  • Datasets: BR has 16 attributes, including 6 numeric and 10 categorical, while MX has 19 attributes, including 5 numeric and 14 categorical.
  • Datasets: Both datasets include total income as the dependent attribute for linear regression, logistic regression, and SVM experiments.

A. Results on Mean Value / Frequency Estimation

Experiments evaluate multidimensional mean and frequency estimation across privacy budgets, user counts, dimensionalities, and data distributions. PM and HM consistently outperform existing approaches, while more users and lower dimensionality improve accuracy.

  • Experimental setup: Accuracy is reported against privacy budget, number of users, and dimensionality across the evaluated datasets.Figures 6–8 cover different distributions, user counts, and dimensionalities.
  • Real datasets: The proposed solution consistently and significantly outperforms the best-effort approach combining existing methods on BR and MX.Evaluation uses MSE for estimated numeric means and categorical frequencies as privacy budget varies.
  • Numeric attributes: PM and HM outperform Duchi et al.’s solution in all numeric-attribute settings.The paper attributes this to smaller constants and the compatibility of PM and HM with categorical attributes without suboptimal privacy-budget splitting.
  • Data distributions: PM and HM produce similar performance on synthetic datasets drawn from Gaussian, uniform, and power law distributions.Results on the uniform and power law datasets lead to conclusions similar to those on real and Gaussian-distributed data.
  • Users and dimensionality: More users and lower dimensionality both lead to more accurate results on the MX dataset.The observed trend agrees with the theoretical analysis in Lemma 5.

B. Results on Empirical Risk Minimization

The paper evaluates PM and HM for empirical risk minimization under LDP using linear regression, logistic regression, and SVM classification. Across these tasks, the proposed methods consistently outperform existing approaches, with some settings approaching non-private accuracy.

  • Experimental setup: The evaluated tasks use gradients collected under LDP and compare PM, HM, Duchi et al.’s method, Laplace, and a non-private setting.The experiments use BR and MX, with 10-fold cross-validation repeated five times and regularization factor λ = 10^-4.
  • Classification: PM and HM consistently outperform Duchi et al.’s solution for logistic regression and SVM classification.Their advantage is attributed to smaller constants and effectiveness on gradients whose elements often have small absolute values.
  • Classification: For SVM on BR with ϵ ≥2, PM and HM approach the accuracy of the non-private method in some settings.This comparison concerns misclassification rates as privacy budget varies.
  • Linear regression: PM and HM consistently outperform Duchi et al.’s solution for linear regression.Laplace results are omitted because their MSE is far higher than those of the other three methods.
Loading 1907.00782v1…