PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Learning with Label Differential Privacy

Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Chiyuan Zhang

arXiv:2102.06062v2cs.LGcs.DS

TL;DR

The paper addresses the accuracy loss of randomized response and private deep learning by introducing RRWithPrior, which incorporates priors while preserving RR-level privacy. Applied to LabelDP, the method substantially improves private model performance, and the analysis shows that protecting labels can be easier than protecting both inputs and labels.

  • Problem

    Randomized response and differentially private deep learning can incur substantial accuracy loss, motivating more accurate methods when only labels require protection.

  • Method

    RRWithPrior prunes the label alphabet using prior information, and the paper applies it through multi-stage training and self-supervised-learning-derived priors for LabelDP.

  • Results

    The LabelDP models significantly improve previous private baselines, including 20% higher CIFAR-10 accuracy than DP-SGD and performance within 2% of the non-private baseline on CIFAR-100 at ε = 8.

  • Takeaways & Limitations

    Using priors under LabelDP narrows the accuracy gap between private and non-private deep-learning models.

  • Takeaways & Limitations

    The algorithms protect labels but not input points, which may be insufficient when input privacy is also required.

Abstract

from arXiv · show

The Randomized Response (RR) algorithm is a classical technique to improve robustness in survey aggregation, and has been widely adopted in applications with differential privacy guarantees. We propose a novel algorithm, Randomized Response with Prior (RRWithPrior), which can provide more accurate results while maintaining the same level of privacy guaranteed by RR. We then apply RRWithPrior to learn neural networks with label differential privacy (LabelDP), and show that when only the label needs to be protected, the model performance can be significantly improved over the previous state-of-the-art private baselines. Moreover, we study different ways to obtain priors, which when used with RRWithPrior can additionally improve the model performance, further reducing the accuracy gap between private and non-private models. We complement the empirical results with theoretical analysis showing that LabelDP is provably easier than protecting both the inputs and labels.

1 Introduction

The paper introduces RRWithPrior and applies it to LabelDP, using priors to improve accuracy while preserving privacy, with empirical and theoretical evidence supporting the approach.

  • Motivation and approach: RRWithPrior improves randomized response by leveraging available prior information while retaining RR's privacy level.Priors may come from domain knowledge, public data, or historical training runs.
  • Label differential privacy: LabelDP protects sensitive labels while treating input points as non-sensitive, covering advertising, recommendation, surveys, and analytics.The paper presents LP-MST for training deep neural networks under this setting.
  • Empirical results: 20% higher accuracy than DP-SGD is reported on CIFAR-10, alongside improvements on MovieLens.The paper also reports the first non-trivial DP learning results on CIFAR-100.
  • Practical context: DP-SGD remains technically challenging to scale to larger models or mini-batch sizes because it requires per-instance gradient computation and clipping.This is presented as a technical limitation of the baseline comparison.
  • Scope: LP-MST goes beyond methods designed only to be robust to label noise and can use state-of-the-art deep-learning architectures such as ResNet.The comparison is made with label-noise robustness methods surveyed in prior work.
  • Theory: Label privacy can be significantly easier than jointly protecting labels and inputs, with dimension-independent sample-complexity bounds for stochastic convex optimization.The analysis also shows that a good prior can reduce population error for non-convex loss.

2 Preliminaries

The preliminaries define randomized response and differential privacy, then specialize privacy to training datasets that differ in one label.

  • Randomized response: Randomized response operates on labels from a finite alphabet and returns the true label or a randomized alternative according to ε.The formal setup defines labels y ∈[K] and privacy parameter ε ≥0.
  • Differential privacy: Differential privacy bounds output-distribution changes between neighboring datasets by e^ε, with an additive δ term.The definition applies to any randomized algorithm and neighboring-dataset relation.
  • Label differential privacy: LabelDP applies the privacy requirement to datasets differing in the label of a single example.In this setting, labels are sensitive while input points are not.

3 Randomized Response with Prior

RRWithPrior prunes the label alphabet using a prior, selects the subset size that maximizes correctness, and is optimal among ε-DP label-randomization algorithms.

  • Setup: RRWithPrior uses a prior distribution over labels to improve the probability that a randomized output equals the input.The prior need not be private, while the input label must satisfy ε-DP.
  • Algorithm: RRTop-k restricts randomized response to the k labels with largest prior probabilities.Labels outside the selected set are mapped uniformly into that set.
  • Algorithm: RRWithPrior dynamically chooses k* to maximize Pr[RRTop-k(y) = y].It evaluates candidate subset sizes using the prior and then runs RRTop-k with the selected size.
  • Privacy: RRTop-k is ε-DP, and RRWithPrior is ε-DP because its choice of k does not depend on the private label.The privacy guarantee follows directly from the subroutine's guarantee.
  • Application: For LabelDP learning, the method queries one randomized label per example and reuses it across training epochs before applying a learner robust to random label noise.This differs from DP-SGD, which makes new gradient queries in every epoch.
  • Optimality: Among all ε-DP algorithms that randomize the input label given prior p, RRWithPrior maximizes Obj_p(R), the probability of returning the correct label.The optimality argument characterizes the best mechanism through a linear program.

4 Application of RRWithPrior: Multi-Stage Training

LP-MST bootstraps from uniform priors, progressively refines them through partitioned multi-stage training, and preserves ε-LabelDP while enabling scalable private learning.

  • Multi-stage training: LP-MST bootstraps from a uniform prior and progressively learns refined priors, allowing use without publicly available domain-specific priors.The framework can be applied to arbitrary domains.
  • Multi-stage training: At each stage, a probabilistic classifier predicts class probabilities, RRWithPrior randomizes labels, and the learner trains on accumulated randomized datasets.The dataset is partitioned into label-independent subsets before training proceeds.
  • Multi-stage training: LP-1ST is equivalent to vanilla randomized response, while additional stages use progressively learned priors.The partition may be chosen arbitrarily provided it does not depend on the labels.
  • Privacy: LP-MST is ε-LabelDP whenever RRWithPrior is ε-DP.The guarantee relies on each sensitive label being used only once and parallel composition across stages.
  • Efficiency and scope: RRWithPrior has quasi-linear running time in the number of labels K, while the paper focuses on small to modest label spaces.Sorting the prior dominates the mechanism's computation, whereas gradient estimation can dominate overall training.

5 Empirical Evaluation

The empirical evaluation applies multi-stage LabelDP training to image classification and collaborative filtering, and uses SSL-derived priors for image classification. Across evaluated datasets, the methods improve private-model performance and narrow the gap to non-private models.

  • Multi-Stage Training: 20% higher accuracy than previous state-of-the-art private baselines is achieved on CIFAR-10 across all ε’s.The comparison uses ResNet18, whose non-private accuracy is 95%; CIFAR-100 pre-training further improves performance.
  • Multi-Stage Training: For ε = 8 on CIFAR-100, the algorithm is only 2% below the non-private baseline.CIFAR-100 has 10× more classes than CIFAR-10, and these are described as the first non-trivial reported DP results on the dataset.
  • Multi-Stage Training: On MovieLens-1M, the evaluation reports test RMSE for collaborative filtering.The dataset contains 1 million anonymous ratings of approximately 3,900 movies from 6,040 users, split 80% for training and 20% for testing.
  • Multi-Stage Training: Across all evaluated datasets, the algorithms significantly outperform previous methods and greatly shrink the performance gap between private and non-private models.The paper identifies this reduced gap as critical for real-world deep-learning applications with privacy concerns.
  • Multi-Stage Training: Moving from LP-2ST to LP-3ST consistently improves test accuracy by 1–2% in the reported cases.Going beyond T > 4 stages leads to diminishing returns on some datasets in preliminary experiments.
  • Domain-Specific Priors: SSL-based priors are obtained by clustering representations of unlabeled images and querying each group’s label histogram with the discrete Laplace mechanism.The queried histograms serve as label priors for group members and are then fed to RRWithPrior for discriminative learning.

6 Theoretical Analysis

The theoretical analysis studies LabelDP for stochastic convex optimization and explains why randomized response on labels can yield dimension-independent guarantees. Extending the analysis to top-k priors introduces a population-loss penalty tied to prior quality.

  • LabelDP Versus DP: For PAC learning, finite VC dimension implies LabelDP learnability, whereas finite VC dimension alone is insufficient for DP algorithms.This prior result motivates the claim that LabelDP can be provably easier than protecting both inputs and labels in certain settings.
  • Stochastic Convex Optimization: LabelDP is shown to admit dimension-independent excess population-loss bounds in stochastic convex optimization.The result contrasts with standard DP, where feature privacy must also be maintained.
  • Stochastic Convex Optimization: The LP-RR-SGD algorithm applies randomized response to labels, debiases the resulting noise, and runs SGD on the noisy dataset.The resulting gradient estimates are unbiased, according to the proof discussion.
  • Stochastic Convex Optimization: Theorem 5’s guarantee is independent of the parameter-space dimension p and is tight up to polylogarithmic factors and dependence on the number of classes K.The comparison notes that the standard-DP bound depends on p and is known to be tight in that setting.
  • Top-k Priors: Using RRTop-k before debiased SGD yields a population-loss bound that depends on the quality of the priors.With a perfect top-k set, the bound replaces K with the smaller k; inaccurate priors incur a penalty term.

7 Conclusions and Future Directions

The paper introduces RRWithPrior for LabelDP and shows that priors can improve private model performance while preserving privacy constraints. It also identifies open questions about training tools, privacy models, and approximate DP, while stressing that the method protects labels but not inputs.

  • Contributions: RRWithPrior incorporates prior information into randomized label querying while maintaining privacy constraints.The paper presents LP-MST, which bootstraps from uniform priors, and a clustering-based approach that extracts priors from self-supervised representations.
  • Contributions: The LP-MST framework is general-purpose and applies even when domain-specific priors are unavailable.
  • Contributions: The clustering-based framework uses domain-specific algorithms to extract priors and performs well with very small privacy budgets.
  • Contributions: The approach improves performance over prior DP models that protect both inputs and outputs, narrowing the gap between private and non-private models.
  • Scope and future directions: The method protects labels but not input points, which may be insufficient when input privacy is also required.
  • Future directions: Open questions concern combining the procedure with DP-SGD tools, extending it to central DP, and improving accuracy under approximate DP.

A.1 Proof of Lemma 1

The proof establishes that RRTop-k satisfies ε-DP by comparing the largest probability of any output under one input with the smallest probability under another input.

  • For any output ỹ, its probability under RRTop-k is maximized when the input equals ỹ.
  • The probability of the same output is minimized when the alternative input lies in Y_k \ {ỹ}.
  • These maximum and minimum probabilities imply that RRTop-k is ε-DP.

B Details of the Experimental Setup

The experiments evaluate the methods across image-classification and MovieLens settings using standard neural architectures, training procedures, privacy mechanisms, and prior-extraction pipelines. The setup includes multi-stage training, self-supervised representations, clustering, and private histogram evaluation.

  • Datasets: The evaluation covers MNIST, Fashion MNIST, KMNIST, CIFAR-10, CIFAR-100, and MovieLens.The image datasets cover 10-class handwritten digits, clothing, Hiragana characters, and 10- or 100-class image classification; MovieLens ratings are treated as categorical labels.
  • Architectures: CIFAR-10 and CIFAR-100 use adapted ResNet18 V2 architectures for 32×32 images.The initial ImageNet-scale convolution and pooling block is replaced with a single 3×3 convolution with stride 1.
  • Training Procedures: Training uses mini-batch SGD with momentum, dataset-specific batch sizes and schedules, and 40 or 200 epochs depending on the dataset.MNIST-family models use 40 epochs, while CIFAR models use 200 epochs with piecewise learning-rate schedules.
  • Training Procedures: All datasets use cross-entropy with ℓ2 regularization, and networks are randomly initialized unless CIFAR-10 explicitly studies CIFAR-100 pretraining.
  • Multi-Stage Training: Multi-stage training initializes later stages from earlier models and can filter privately queried labels using prior-model predictions.For stage 2, labels outside the top k predicted classes are excluded from training.
  • Priors from Self-supervised Learning: Self-supervised priors are obtained from BYOL or DINO representations, clustered with k-means, and combined with private class histograms.BYOL uses unlabeled CIFAR-10 images, while DINO uses models pretrained on ImageNet.
  • Private Histogram Evaluation: Figure 2 compares CIFAR-10 test accuracy for private histogram querying with k-means features learned by BYOL on CIFAR-10 and DINO on ImageNet.
  • Private Histogram Evaluation: The clustering evaluation extracts joint training and test features, privately queries training histograms, assigns each cluster its maximum-vote class, and measures test accuracy.Smaller clusters improve accuracy but become more sensitive to geometric-mechanism noise at small privacy budgets.

C Extra Results on Multi-Stage Training

Additional experiments show that multi-stage training outperforms previous methods across privacy levels on MNIST and Fashion MNIST, with especially pronounced gains on the harder Fashion MNIST task.

  • Multi-stage training outperforms previous methods across all privacy budgets on MNIST and Fashion MNIST.
  • The performance gap is more pronounced on Fashion MNIST, which is slightly harder than MNIST.
  • LP-2ST consistently improves over LP-1ST on the reported MNIST and Fashion MNIST experiments.
  • KMNIST results under different privacy losses are qualitatively similar to those for MNIST and Fashion MNIST.

D Learning Dynamics of Multi-stage Training

On CIFAR-10 with ε = 2, LP-2ST uses a weaker first-stage model to provide a useful prior for second-stage training, enabling improved learning despite reduced first-stage data.

  • LP-2ST’s stage-1 model, trained on 65% of the data, clearly underperforms LP-1ST trained on the full dataset.
  • The stage-1 model remains useful because its top-2 accuracy reaches 90% at the end of training.
  • RRWithPrior selects an average k = 1.86 for the remaining 35% of the training data.
  • LP-2ST continues training in stage 2 using the prior produced by stage 1.

E Analysis of Robustness to Hyperparameters

The experiments examine hyperparameter robustness in multi-stage LabelDP training, while the theoretical results establish dimension-independent guarantees and characterize privacy–utility behavior for label-private optimization.

  • Robustness to Hyperparameters: Hyperparameter tuning is omitted from the rigorous privacy accounting because private combinatorial optimization is outside the paper’s main focus.
  • Robustness to Hyperparameters: The algorithms remain robust across a large range of hyperparameters, providing guidance for selecting practical settings.
  • Data Splits and Prior Temperature: Stage-1 ratios slightly above 50% balance learning a better prior against retaining enough stage-2 training samples.
  • Data Splits and Prior Temperature: Lower prior temperatures sparsify predictions, whereas temperatures approaching infinity produce a uniform prior; temperatures above 1 are generally unhelpful.
  • Theoretical Analysis: LP-RR-SGD provides dimension-independent LabelDP rates by using randomized-response labels to construct unbiased gradient estimates.
  • Theoretical Analysis: Theorem 9 is tight up to O(K log n/ε) relative to the non-private stochastic-convex-optimization lower bound.
Loading 2102.06062v2…