PaperlayerView exact revision on arXiv

Source-linked AI summary

Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy

Thông T. Nguyên, Xiaokui Xiao, Yin Yang, Siu Cheung Hui, Hyejin Shin, Junbum Shin

arXiv:1606.05053v1cs.DB

TL;DR

Organizations want to analyze smart-device data, but collecting sensitive personal information creates privacy and breach risks, while existing LDP solutions have limited functionality or emphasize theory over practical systems. Harmony provides LDP-compliant analytics for mixed numerical and categorical data, covering basic statistics and several machine-learning tasks. The paper reports optimal asymptotic error bounds, high practical accuracy, efficiency, and effectiveness on real data, while noting boundaries around multiple snapshots and known issues in prior methods.

  • Problem

    Existing LDP solutions have restricted functionality or focus on asymptotic analysis rather than practical systems, leaving mixed-data machine learning insufficiently addressed.

  • Method

    Harmony collects randomized records under ε-LDP and analyzes multi-attribute data containing both numerical and categorical attributes.

  • Results

    Harmony computes means, frequencies, linear regression, logistic regression, and SVM models with optimal asymptotic error bounds, high practical accuracy, and efficient overhead on real data.

  • Takeaways & Limitations

    Harmony offers a practical approach to collecting and analyzing smart-device user data while preserving LDP guarantees.

  • Takeaways & Limitations

    The paper guarantees privacy for each snapshot separately; joint ε-LDP across arbitrarily many recollected snapshots remains an open problem.

Abstract

from arXiv · show

Organizations with a large user base, such as Samsung and Google, can potentially benefit from collecting and mining users' data. However, doing so raises privacy concerns, and risks accidental privacy breaches with serious consequences. Local differential privacy (LDP) techniques address this problem by only collecting randomized answers from each user, with guarantees of plausible deniability; meanwhile, the aggregator can still build accurate models and predictors by analyzing large amounts of such randomized data. So far, existing LDP solutions either have severely restricted functionality, or focus mainly on theoretical aspects such as asymptotical bounds rather than practical usability and performance. Motivated by this, we propose Harmony, a practical, accurate and efficient system for collecting and analyzing data from smart device users, while satisfying LDP. Harmony applies to multi-dimensional data containing both numerical and categorical attributes, and supports both basic statistics (e.g., mean and frequency estimates), and complex machine learning tasks (e.g., linear regression, logistic regression and SVM classification). Experiments using real data confirm Harmony's effectiveness.

1. INTRODUCTION

Smart-device data can benefit organizations, but collecting sensitive personal information creates privacy and breach risks. Harmony addresses limitations in existing LDP solutions by supporting practical analytics over mixed numerical and categorical data.

  • Motivation: Smart-device data can help hardware designers and application developers understand usage patterns and improve products.Examples include analyzing smartphone UI-feature popularity and usage.
  • Motivation: Organizations face a tradeoff between mining users’ personal data and exposing themselves to privacy breaches.Accidental leaks involving AOL, Netflix, and Ashley Madison caused serious consequences and substantial damage.
  • Existing LDP: Local differential privacy collects randomized responses instead of exact personal information while providing rigorous privacy guarantees and plausible deniability.Unlike central differential privacy, LDP performs randomization before the aggregator receives user data.
  • Existing LDP: Rappor cannot directly handle numeric attributes, its error grows linearly with the number of independent attributes, and its support for complex machine learning tasks is unclear.The limitations include missing numeric aggregates such as average app running time and uncertain support for logistic regression and SVM classification.
  • Harmony: Harmony supports analytics over arbitrary numbers of numerical or categorical attributes and reports improved practical accuracy with non-trivial asymptotical error bounds.The system is presented as a practical data-analytics tool conforming to LDP requirements.
  • Potential Use Case: Samsung’s diagnostic use case combines sensitive numeric and categorical device data with analytical needs such as predicting system errors.Rappor’s focus on a single categorical attribute does not cover this mixed-data setting or complex learning tasks.

2. PRELIMINARIES

The preliminaries define Harmony’s LDP setting, in which users perturb multi-attribute records before transmission. The paper targets basic statistics and empirical-risk-minimization models while treating each collected snapshot separately for privacy.

  • LDP Setting: Each user holds a tuple of d numerical or categorical attributes, while the aggregator knows user identities but not their private data.Numeric attributes are modeled over [-1, 1], and categorical attributes use finite discrete domains.
  • LDP Mechanism: Users apply a randomized perturbation function to their tuples before sending them, creating a privacy–utility tradeoff controlled by the perturbation.Unperturbed data would provide perfect utility but no privacy.
  • LDP Mechanism: Under ε-LDP, randomized outputs must limit the aggregator’s ability to distinguish any two possible input tuples, providing plausible deniability.The privacy guarantee is defined for every pair of inputs and every possible output, with ε controlling distinguishability.
  • Supported Analytics: Harmony targets mean and frequency estimation alongside empirical-risk-minimization tasks such as linear regression, logistic regression, and SVM classification.Means concern numeric attributes, while frequencies concern possible categorical values.
  • Scope Boundary: Privacy is guaranteed for each individual snapshot when user data are recollected over time, whereas joint privacy for arbitrarily many snapshots remains open.The paper explicitly distinguishes per-snapshot protection from a stronger guarantee over all collected snapshots.

3. ESTIMATING MEANS AND FREQUENCIES

Harmony develops practical LDP mechanisms for estimating means of numeric attributes and frequencies of categorical attributes across multi-attribute data. Its numeric method preserves privacy and unbiasedness while using one transmitted bit per user, and its categorical method addresses instability and multiple-attribute limitations.

  • Estimating Mean Values for Numeric Attributes: Each user transmits one bit per numeric attribute in the basic numeric perturbation design.The perturbed output for each attribute is binary, taking values B or −B.
  • Estimating Mean Values for Numeric Attributes: The aggregator averages perturbed numeric tuples, using a scaling factor B so each perturbed attribute has the same expected value as the exact attribute.This makes the resulting mean estimator unbiased when the expected perturbed value matches the original attribute value.
  • Estimating Mean Values for Numeric Attributes: Duchi et al.’s method can be biased and violate ε-LDP when the number of attributes d is even.The paper attributes the problem to the Bernoulli variable definition in Line 3 and gives a revised choice that restores privacy and the error bound.
  • Estimating Mean Values for Numeric Attributes: Harmony’s numeric method provides the same privacy assurance and asymptotic error bound as Duchi et al.’s method while slightly improving empirical accuracy and reducing communication to one bit.The paper reports that experiments show slightly better estimated-mean accuracy and that one-bit transmission is optimal.
  • Estimating Frequencies for Categorical Attributes: For categorical attributes, Harmony replaces a noisy random projection matrix with a binary matrix whose columns are pairwise orthogonal, improving accuracy when k = o(n).The alternative targets instability in Bassily and Smith’s method for relatively small categorical domains.
  • Estimating Frequencies for Categorical Attributes: Existing methods based on composite categorical attributes estimate combination frequencies but not the frequencies of individual values across multiple attributes.The paper states that this limitation also applies to existing work including Rappor, which does not handle mixtures of numeric and categorical attributes.
  • Harmony estimates means for numeric attributes and frequencies for categorical attributes across multiple attributes.The design handles numerical and categorical attributes separately while supporting their combination.
  • Estimating Frequencies for Categorical Attributes: Harmony randomly selects one attribute per user and applies an ε-differentially private submission algorithm, preserving ε-LDP while providing categorical frequency guarantees.For numeric attributes, the resulting accuracy matches Algorithm 2; categorical estimators receive a high-probability error bound.

4. BUILDING MACHINE LEARNING MODELS USING STOCHASTIC GRADIENT DESCENT

Harmony builds linear regression, logistic regression, and SVM models under ε-LDP by privately collecting noisy gradients. Mini-batching reduces gradient noise, while dimension reduction makes the required batches smaller for linear regression.

  • Empirical risk minimization: Harmony formulates linear regression, logistic regression, and SVM classification as empirical risk minimization under ε-LDP.The section focuses on these three common learning tasks.
  • Private gradient methods: Private SGD perturbs each selected user’s gradient, but the resulting noise can make the learned models inaccurate.The aggregator cannot directly access the gradient and must collect a noisy version privately.
  • Mini-batching: Mini-batch gradient descent averages noisy gradients from a group of users to reduce the noise in each update.Each iteration involves a group G and updates the parameter vector using the mean of their noisy gradients.
  • Mini-batching: Allowing users to participate in m > 1 iterations divides the privacy budget across iterations and increases the noise in each gradient.The composition constraint requires the per-iteration budgets to sum to at most ε; setting ε_i = ε/m produces the stated trade-off.
  • Dimension reduction: Dimension reduction projects each d-dimensional input into an r-dimensional subspace, reducing noisy-gradient dimensionality and the acceptable mini-batch size.Harmony uses a random r × d projection with r < d; the experiments set r = 20.

5. EXPERIMENTS

Experiments on US and BR census datasets evaluate Harmony for noisy statistics and empirical risk minimization. Harmony is more accurate than Hybrid for categorical frequencies, slightly outperforms it for means, and dimension-reduction methods approach non-private accuracy in regression.

  • Datasets: US contains 9M tuples and 23 attributes, while BR contains 4M records and 18 attributes, with both numeric and categorical attributes.Each dataset has six numeric attributes; US has 17 categorical attributes and BR has 12.
  • Means and frequencies: The first experiments estimate numeric means and categorical-value frequencies from one noisy tuple per user.Hybrid combines separate state-of-the-art mechanisms for numeric and categorical attributes while preserving ε-LDP.
  • Means and frequencies: Harmony’s categorical-frequency error is around one-quarter of Hybrid’s error across the evaluated privacy budgets and datasets.The experiments measure L∞ frequency error averaged over 100 runs.
  • Means and frequencies: Harmony slightly outperforms Hybrid for numeric mean estimation on both datasets across privacy-budget values.Harmony also requires each user to transfer only 1 bit and is simpler than Hybrid for this task.
  • Empirical risk minimization: For empirical risk minimization, the experiments evaluate private SGD, MGD, MGD-DR, and non-private SGD after transforming categorical attributes into binary attributes.The transformed dimensionality is 85 for US and 95 for BR, and performance is assessed with 10-fold cross-validation.
  • Empirical risk minimization: MGD-DR achieves linear-regression accuracy close to non-private SGD, while private SGD has prohibitive errors and MGD remains unsatisfactory.Figures also report misclassification rates for logistic regression and SVM, and the results demonstrate the effectiveness of mini-batches and dimension reduction.

6. RELATED WORK

Differential privacy provides rigorous privacy guarantees, while local differential privacy avoids collecting exact personal data by shifting protection to the user side. Prior work established LDP mechanisms for binary and categorical frequency estimation and introduced RAPPOR for binary vectors with Bloom filters.

  • Differential privacy offers semantic, information-theoretic privacy guarantees rather than merely syntactic protection.
  • Local differential privacy removes the trusted curator and prevents collection of individuals’ exact private information.
  • Prior LDP research established minimax error bounds, privacy–accuracy trade-offs, and optimal randomized-response mechanisms for binary and categorical attributes.
  • RAPPOR combines randomized response with a Bloom filter to publish binary vectors under LDP, increasing protection while complicating statistical estimation.

7. CONCLUSION

Harmony collects randomized records under ε-local differential privacy and analyzes multidimensional data containing numeric and categorical attributes. It supports statistics and machine-learning models, with optimal asymptotic error, practical accuracy, efficiency, and effectiveness demonstrated on real data.

  • Harmony analyzes multiple numeric and categorical attributes under ε-local differential privacy, collecting only randomized user data.
  • Harmony supports mean and frequency estimation alongside linear regression, logistic regression, and SVM classification.
  • Harmony achieves an optimal asymptotic error bound and high practical accuracy while maintaining low communication and computational overhead.
  • Extensive experiments on real data demonstrate Harmony’s effectiveness.

APPENDIX

The appendix proves that the set returned by Algorithm 5 is orthogonal. The proof uses induction, showing that the base set is orthogonal and that the construction preserves zero inner products.

  • Lemma 5 states that Algorithm 5 returns an orthogonal set.
  • The proof establishes the base case using S = {[1, −1], }, which is orthogonal.
  • The inductive step constructs S′ by concatenating each vector with itself and its negation, yielding zero inner products in both cases.
Loading 1606.05053v1…