Differentially Private Compressive K-means

Vincent Schellekens, Antoine Chatalic, Florimond Houssiau, Yves-Alexandre de Montjoye, Laurent Jacques, Rémi Gribonval

TL;DR

This paper introduces a novel framework for learning from large datasets while guaranteeing differential privacy. By combining compressive sketching with differential privacy mechanisms, they enable efficient, distributed k-means clustering without compromising individual data privacy.

What Problem Does This Paper Address?

The exponential growth of datasets presents a dual challenge for machine learning: computational feasibility and data privacy. Traditional methods struggle with the sheer volume of data, requiring significant computational resources. Simultaneously, using and publishing this data raises serious privacy concerns, as individuals' sensitive information could be exposed. While compressive learning offers a way to reduce data size for efficient processing, it doesn't inherently provide privacy guarantees. This paper tackles this by proposing a method that compresses data into a smaller "sketch" while ensuring differential privacy, making it suitable for distributed environments where data is spread across multiple devices.

Methods

The core of this work lies in a "differentially private compressive k-means" framework. It builds upon the idea of compressive learning, where a large dataset is summarized into a compact "sketch" (a vector of generalized random moments). The novelty here is the integration of differential privacy.

The proposed method involves:

  • Private Sketching: Each device locally computes a "scrambled sketch" of its data. This is achieved by:
  • Subsampling: Computing moments from subsets of the local data.
  • Laplace Noise Addition: Adding Laplace noise to the computed moments to ensure differential privacy. This noise is carefully calibrated based on the sensitivity of the operation.
  • Distributed Aggregation: These local scrambled sketches are then sent to a central analyst who combines them into a single global scrambled sketch.
  • Compressive Learning: The k-means clustering algorithm is then performed on this global scrambled sketch, which is significantly smaller than the original dataset.

The authors introduce a complex Laplace distribution for noise generation and define both local and global sketching mechanisms. They also propose a signal-to-noise ratio (SNR) as a measure of utility for the privacy-preserving sketch.

Datasets

Not discussed in the paper. The experiments were conducted on synthetic data generated from a mixture of Gaussian distributions.

Key Insights and Ideas

  • Sketching as a Privacy Enabler: The paper demonstrates that the inherent aggregation in sketching mechanisms can be a good starting point for building privacy-preserving methods.
  • Distributed Privacy: The framework is designed for distributed settings, allowing multiple devices to contribute to a global analysis without sharing raw data. This is crucial for scenarios involving sensitive data spread across various sources.
  • Signal-to-Noise Ratio (SNR) for Utility: Defining SNR as a measure of sketch quality provides a quantifiable way to understand the impact of privacy mechanisms on learning performance. This allows for a clear analysis of the privacy-utility tradeoff.
  • Masking for Efficiency and Privacy: The subsampling (masking) mechanism not only improves privacy by reducing the contribution of individual data points but also significantly reduces computational time.

Key Results

  • The proposed method achieves differential privacy (e-DP) for the local and global sketching mechanisms.
  • Experimental results show that the Signal-to-Noise Ratio (SNR) is a good indicator of the utility (measured by relative SSE for k-means) of the scrambled sketch.
  • The paper demonstrates that their method performs comparably to or better than existing differentially private k-means algorithms (like DPLloyd and EUGKM) in terms of utility, while requiring less computation and memory, especially in a distributed setting.
  • For a privacy parameter $\epsilon > 10^{-2}$, good clustering results (relative SSE below 1.2) were achieved with a single device setup.

Limitations and Future Work

  • Synthetic Data: The experiments were conducted on synthetic data. Evaluating the method on real-world datasets would be valuable.
  • Generalization to Other Tasks: While the framework is presented for k-means, its applicability to other learning tasks like Gaussian mixture fitting or principal component analysis is suggested but not fully explored.
  • Quantized Sketches: The authors suggest exploring the use of quantized sketches for further efficiency.
  • Leveraging Fast Transforms: Investigating the use of fast transforms to speed up the sketching process is another avenue for future work.
  • Additive Noise on Data Samples: The possibility of adding noise directly to data samples is also mentioned as a potential future direction.

Summary updated

Abstract

This work addresses the problem of learning from large collections of data with privacy guarantees. The sketched learning framework proposes to deal with the large scale of datasets by compressing them into a single vector of generalized random moments, from which the learning task is then performed. We modify the standard sketching mechanism to provide differential privacy, using addition of Laplace noise combined with a subsampling mechanism (each moment is computed from a subset of the dataset). The data can be divided between several sensors, each applying the privacy-preserving mechanism locally, yielding a differentially-private sketch of the whole dataset when reunited. We apply this framework to the k-means clustering problem, for which a measure of utility of the mechanism in terms of a signal-to-noise ratio is provided, and discuss the obtained privacy-utility tradeoff.
BibTeX
@inproceedings{schellekens2019differentially,
  author = {Vincent Schellekens and Antoine Chatalic and Florimond Houssiau and Yves-Alexandre de Montjoye and Laurent Jacques and Rémi Gribonval},
  title = {{Differentially Private Compressive K-means}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2019},
  doi = {10.1109/icassp.2019.8682829},
}
Figure