Privacy-preserving Stochastic Gradual Learning

Bo Han, Ivor W. Tsang, Xiaokui Xiao, Ling Chen, Sai-Fu Fung, Celina Ping YuIEEE TKDE 2018 · DOI · OpenReview

TL;DR

This paper introduces PRESTIGE, a novel method for training machine learning models on sensitive data while preserving privacy and maintaining robustness. PRESTIGE combines private stochastic gradient descent with curriculum learning to overcome the "robustness degeneration" issue often seen in privacy-preserving algorithms, achieving a better trade-off between privacy and model accuracy.

What Problem Does This Paper Address?

In today's data-driven world, machine learning models are increasingly trained on large-scale, sensitive datasets (e.g., health records, financial data). While stochastic optimization methods are efficient for handling such large datasets, their direct application can lead to "privacy leakage." This means that even with de-identification techniques, sensitive information can be inferred from the model's outputs through reverse engineering.

Existing privacy-preserving methods, like Duchi et al.'s private sampling strategy, aim to address this by injecting noise into gradients. However, this noise injection, while preserving privacy, often degrades the model's robustness, leading to "robustness degeneration." This means the model becomes less accurate and reliable, especially when dealing with noisy or imperfect data. The challenge, therefore, is to develop a method that can achieve both strong privacy guarantees and robust model performance on sensitive data.

Methods

The core innovation of PRESTIGE lies in its integration of two key concepts:

  • Private Sampling (Local Privacy): This technique, building on Duchi et al.'s work, ensures privacy at the individual data point level. It involves perturbing and rescaling gradients to mask the contribution of each data point, adhering to local differential privacy.
  • Curriculum Learning (CL): Inspired by how humans learn, CL involves training a model on "easier" tasks first and gradually progressing to "harder" ones. In PRESTIGE, this translates to learning from "beneficial" labels (those that reliably guide the model) before moving to "adverse" labels (those that are noisy or potentially misleading).

PRESTIGE implements a "private curriculum" where the order of learning is determined by a combination of the true label and the model's current prediction. This private curriculum is designed to mitigate the negative impact of noisy labels introduced by private sampling. The algorithm dynamically adjusts a threshold, initially focusing on beneficial labels and gradually incorporating adverse ones as training progresses, thereby building a robust model from the outset.

Datasets

The paper evaluates PRESTIGE on a variety of datasets:

  • UCI Datasets: A7A, MNIST38, SUSY, REAL-SIM. These datasets represent a range of sizes and dimensionality.
  • Real-World Sensitive Datasets: Cyberbully detection (social networks) and Diabetes prediction (healthcare). These datasets are chosen to reflect the practical application of privacy-preserving methods in sensitive domains.

Key Insights and Ideas

  • Robustness Degeneration is a Key Hurdle: The paper clearly articulates that standard privacy-preserving techniques often sacrifice model robustness. This is a critical problem for real-world applications where accuracy is paramount.
  • Curriculum Learning as a Solution: The insight that curriculum learning's structured approach to learning can combat label noise is central. By learning from reliable data first, the model builds a strong foundation that can better handle noisy data later.
  • "Private but Robust" is Achievable: PRESTIGE demonstrates that it's possible to achieve both strong privacy guarantees and improved robustness simultaneously, a significant advancement over existing methods.
  • The Power of a "Private Curriculum": By carefully ordering the learning process based on perturbed labels, PRESTIGE effectively navigates the trade-off between privacy and robust learning.

Key Results

  • Improved Robustness: Across multiple UCI and real-world datasets, PRESTIGE consistently achieves lower testing error rates (TER) compared to vanilla SGD and DJW (a strong privacy-preserving baseline) under various privacy budgets. For instance, on the A7A dataset, PRESTIGE shows a noticeable improvement over DJW.
  • Effective Privacy Preservation: The method maintains strong privacy guarantees, as evidenced by its performance across different privacy budget levels.
  • Mini-Batch Effectiveness: Experiments show that using mini-batches further enhances the robustness of PRESTIGE and DJW, leading to lower TERs and standard deviations.
  • Loss Function Impact: The paper explores different loss functions, finding that while logistic loss is generally robust, Gompertz loss shows a marginal advantage for PRESTIGE, potentially due to its ability to handle noisy labels introduced by private sampling.

Limitations and Future Work

  • Convergence Rate: While PRESTIGE converges, its rate is noted to be similar to existing methods. The authors suggest future work to speed up convergence using techniques like Nesterov's accelerated strategy.
  • Adaptive Privacy Budget Allocation: The paper uses a fixed ratio for allocating privacy budgets between curriculum and sampling (εr : εs = 1 : 4). Future work could explore adaptive methods for choosing this ratio to optimize robustness on different datasets.
  • Extension to Deep Learning: The current implementation is demonstrated for linear classification. The authors propose extending PRESTIGE to deep neural networks, which would significantly broaden its applicability.
  • Optimal Trade-off: The paper acknowledges that increasing batch size can decrease convergence rate. Future research will explore the optimal trade-off between convergence and robustness.

Summary updated

Abstract

It is challenging for stochastic optimizations to handle large-scale sensitive data safely. Recently, Duchi et al. proposed private sampling strategy to solve privacy leakage in stochastic optimizations. However, this strategy leads to robustness degeneration, since this strategy is equal to the noise injection on each gradient, which adversely affects updates of the primal variable. To address this challenge, we introduce a robust stochastic optimization under the framework of local privacy, which is called Privacy-pREserving StochasTIc Gradual lEarning (PRESTIGE). PRESTIGE bridges private updates of the primal variable (by private sampling) with the gradual curriculum learning (CL). Specifically, the noise injection leads to the issue of label noise, but the robust learning process of CL can combat with label noise. Thus, PRESTIGE yields "private but robust" updates of the primal variable on the private curriculum, namely an reordered label sequence provided by CL. In theory, we reveal the convergence rate and maximum complexity of PRESTIGE. Empirical results on six datasets show that, PRESTIGE achieves a good tradeoff between privacy preservation and robustness over baselines.
BibTeX
@article{han2018privacy,
  author = {Bo Han and Ivor W. Tsang and Xiaokui Xiao and Ling Chen and Sai-Fu Fung and Celina Ping Yu},
  title = {{Privacy-preserving Stochastic Gradual Learning}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2018},
  doi = {10.1109/tkde.2020.2963977},
}
Figure