Learning Privately from Multiparty Data

Jihun Hamm; Paul Cao; Mikhail Belkin

Source-linked AI summary

Learning Privately from Multiparty Data

Jihun Hamm, Paul Cao, Mikhail Belkin

arXiv:1602.03552v1Feb 10, 2016cs.LGcs.CR

TL;DR

The paper asks how to combine locally trained classifiers from multiple parties into an accurate differentially private global classifier without accessing private data. It transfers ensemble knowledge through auxiliary unlabeled data, then trains a private classifier with a confidence-weighted risk. The resulting generalization error includes an O(ε^-2M^-2) term relative to a non-private solution, and the method is demonstrated on three realistic tasks.

Problem
The paper addresses how to learn an accurate differentially private global classifier from multiple parties without collecting their private data.
Method
The method labels auxiliary unlabeled data with the local-classifier ensemble and trains a differentially private global classifier using a risk weighted by ensemble class probabilities.
Results
The generalization error relative to a non-private solution includes an O(ε^-2M^-2) term, and the method is evaluated on activity recognition, network intrusion detection, and malicious URL detection.
Takeaways & Limitations
With many parties, the private solution can approach the expected risk of a non-private solution while avoiding access to parties’ private data.
Takeaways & Limitations
The theoretical bounds do not establish how the ensemble compares with a centrally trained classifier using all private data without privacy.

Abstract

from arXiv · show

Learning a classifier from private data collected by multiple parties is an important problem that has many potential applications. How can we build an accurate and differentially private global classifier by combining locally-trained classifiers from different parties, without access to any party's private data? We propose to transfer the `knowledge' of the local classifier ensemble by first creating labeled data from auxiliary unlabeled data, and then train a global $ε$-differentially private classifier. We show that majority voting is too sensitive and therefore propose a new risk weighted by class probabilities estimated from the ensemble. Relative to a non-private solution, our private solution has a generalization error bounded by $O(ε^{-2}M^{-2})$ where $M$ is the number of parties. This allows strong privacy without performance loss when $M$ is large, such as in crowdsensing applications. We demonstrate the performance of our method with realistic tasks of activity recognition, network intrusion detection, and malicious URL detection.

1. Introduction

The paper addresses private learning from multiparty data by combining locally trained classifiers without accessing parties’ private data. It transfers ensemble knowledge through auxiliary data and releases a differentially private global classifier.

Private multiparty learning avoids centrally collecting sensitive party data, which can be exposed during transmission, storage, and processing.
The method transfers ensemble knowledge to auxiliary data, then uses the resulting labels to train and sanitize a global classifier.
Majority-voted labels are highly sensitive to individual local votes, causing substantial performance loss after differential-privacy sanitization.
The proposed weighted risk uses ensemble class-probability confidence to reduce sensitivity to individual votes.
The generalization error relative to a non-private solution includes O(ε^-2M^-2) and O(N^-1) terms, where M is the number of parties.
The method supports mixed local-classifier types, protects all samples of a party, and is evaluated on realistic application tasks.

2. Preliminary

This section defines differential privacy and output perturbation for releasing classifiers while controlling information leakage. The privacy guarantee is stated under assumptions on the loss, features, and classifier form.

Differential privacy limits how much an algorithm’s output distribution can change when one database item is added or removed.
A vector-valued output can be privatized by adding noise calibrated to its global L2 sensitivity.
Output perturbation sanitizes an empirical-risk-minimizing classifier by perturbing its parameters before public release.
The paper’s setting protects all samples belonging to a party, which is stronger than protecting only a single sample.
The global-classifier guarantee assumes linear classifiers, convex differentiable loss, bounded derivative, Lipschitz derivative, and bounded features.

3. Transferring knowledge of ensemble

The paper treats local classifiers as black boxes and transfers their knowledge through auxiliary unlabeled data rather than directly releasing classifier parameters or repeatedly privatizing predictions.

Local classifiers may be of any type and are trained independently from private samples drawn from a common distribution.
The party-level data split resembles Subagging more closely than Bagging because party samples are drawn without replacement.
3.2. Privacy issues of direct release: Directly releasing all classifier parameters has constant sensitivity and can require stronger perturbation than releasing insensitive aggregate statistics.
3.3. Leveraging auxiliary data: The method labels auxiliary unlabeled data with the ensemble and trains a global classifier whose release has O(M^-1) sensitivity.
3.3. Leveraging auxiliary data: The number of auxiliary samples does not affect privacy, while larger auxiliary datasets bring the global classifier closer to the ensemble with an O(N^-1) bound.
3.3. Leveraging auxiliary data: Unlike sanitized prediction-query answers, the sanitized global classifier can be used repeatedly without additional privacy impact.

4. Finding a global private classifier

The paper compares majority-voted and soft-labeled weighted empirical-risk minimization for training a private global classifier from local ensembles. Majority voting is highly sensitive to individual votes, whereas weighted risk reduces sensitivity and yields a generalization bound improving with the number of parties.

Majority-voted ERM: The ensemble assigns labels to auxiliary unlabeled data, which are then used to train a global classifier through empirical-risk minimization and output perturbation.The procedure avoids directly releasing sanitized local classifier parameters.
Majority-voted ERM: Majority voting treats the ensemble output as a deterministic target concept, but changing one local classifier can reverse labels when the remaining votes are tied.Differential privacy must calibrate noise to this worst-case sensitivity.
Majority-voted ERM: The majority-voted ERM bound contains an O(ε^-2) term, which can be large for small ε and therefore does not guarantee successful learning.The bound is attributed to the sensitivity of majority-voted ERM.
Weighted ERM with soft labels: Weighted risk uses ensemble confidence α(x) instead of a hard vote, making nearly split votes insensitive to a single local classifier while preserving the original loss for unanimous votes.A single vote changes the weighted loss by only a factor of 1/M.
Weighted ERM with soft labels: The weighted loss is asymptotically equivalent to standard expected loss when the target is the probabilistic prediction of a random local hypothesis.The ensemble estimates the relevant class probability from local predictions.
Privacy and performance: The weighted private classifier requires 1/M times smaller noise for the same ε-differential privacy guarantee, producing an O(M^-2ε^-2) generalization term.For fixed ε, increasing M can bring expected risk close to that of a non-private solution.
Privacy and performance: The reported bounds compare private ERM with non-private solutions for different target concepts and do not establish performance relative to centrally trained, non-private learning from all private data.That comparison is left to empirical evaluation.
Extensions: The method can also protect auxiliary data, but allowing one auxiliary feature to change increases sensitivity by a factor of (N+M-1)/N and requires proportionally more noise.Algorithm 1 already provides privacy for labeled and auxiliary data under the stated single-sample change setting.

5. Related work

Prior work studied private multiparty learning through parameter averaging and private gradient exchange, while this paper aggregates classifier decisions and uses unlabeled data to augment training.

Earlier methods included parameter averaging through secure multiparty computation and private exchange of gradient information.
This paper averages classifier decisions rather than parameters, allowing arbitrary and mixed classifier types.
The method uses non-private unlabeled data to augment labeled data during training, constituting a semi-supervised learning approach.

6. Experiments

Experiments compare private and non-private classifiers across activity recognition, network intrusion detection, and malicious URL detection. Across tasks, private methods can outperform individually trained classifiers at stronger privacy levels, while performance declines as privacy weakens.

Experimental setup: The experiments compare batch, soft, parameter averaging, majority voting, and individually trained classifiers on three real-world datasets.All methods use binary or multiclass logistic regression, with λ fixed to 10^-4; 10% of training data serves as auxiliary unlabeled data.
Evaluation tasks: The three evaluations use activity recognition, network intrusion detection, and malicious URL detection as the tested application settings.Figures 2–4 report test accuracy for private and non-private algorithms in these respective tasks.
Activity recognition: At around 0.90 test accuracy, batch substantially exceeds the approximately 0.47 accuracy of individually trained classifiers in activity recognition.The activity-recognition simulation uses M = 1K parties, each with 6 local samples, while 1K samples are auxiliary unlabeled data.
Network intrusion detection: For network intrusion detection, private algorithms lie roughly between batch and indiv at small 1/ϵ, then become worse than indiv as 1/ϵ increases.This tendency is reported for M = 5K, 10K, and 20K parties, with 22 samples per party and 43K auxiliary unlabeled samples.
Malicious URL detection: For malicious URL detection, the gap between batch and other algorithms is larger than in network intrusion detection, likely because each party has only 9 samples.The overall tendency remains similar, using M = 5K, 10K, and 20K parties and 16K auxiliary unlabeled samples.

7. Conclusion

The paper builds global differentially private classifiers from local classifiers by transferring ensemble knowledge through auxiliary unlabeled data and weighted empirical risk minimization. It presents this approach as a way to reduce the performance gap between private and non-private ensembles on real-world tasks.

Conclusion: The proposed method transfers local-ensemble knowledge through auxiliary unlabeled data and trains a global classifier using weighted empirical risk minimization.The weights use class-probability estimates from the ensemble.
Conclusion: The paper presents the method as minimizing the classification-performance gap between private and non-private ensembles on real-world tasks.

A.1. Proof of Theorem 1

The proof analyzes the sensitivity of the regularized-risk minimizer used by the majority-vote private algorithm when one party’s data changes. Adding noise calibrated to this sensitivity yields ε-differential privacy.

Theorem statement: Theorem 1 perturbs the majority-vote algorithm’s regularized-risk minimizer with noise to obtain a private output.The theorem defines the perturbed output as wp = ws + η and specifies a noise density proportional to e^−λϵ.
Sensitivity analysis: Changing one party’s private data changes only that party’s local classifier and can alter labels throughout the auxiliary training set.The proof compares neighboring datasets differing at party 1 and the resulting majority-vote labels.
Sensitivity analysis: Under the assumptions ∥x∥≤1 and |l′(·)|≤1, the worst-case label changes bound the relevant risk difference and the minimizer’s L2 sensitivity.The proof considers the case where every auxiliary label changes between neighboring datasets.
Privacy guarantee: The sensitivity result establishes ε-differential privacy for the perturbed output.

A.2. Proof of Theorem 3

The proof establishes privacy for Algorithm 2 by bounding the sensitivity of the weighted empirical-risk minimizer and perturbing it with calibrated noise. It then bounds the private solution’s deviation from the non-private minimizer using smoothness and concentration.

Algorithm 2 adds noise to the non-private minimizer, with the perturbation distribution calibrated to M, λ, and ε.
The proof compares neighboring party datasets whose features are fixed while ensemble-derived probabilities may differ.
Because each class probability changes by at most 1/M, the minimizer’s L2 sensitivity is at most 2/(λM), yielding ε-differential privacy.
Smoothness of the regularized risk and a concentration lemma control the private minimizer’s excess risk relative to the non-private solution.

A.5. Proof of Theorem 4

Theorem 4 combines privacy-mechanism error with sampling error to bound the regularized risk of the private classifier relative to a reference hypothesis. The argument compares private and non-private minimizers and invokes smoothness and empirical-risk generalization.

The proof compares the private minimizer with the minimizers of regularized empirical and expected risks.
The private classifier’s risk is decomposed into a privacy perturbation term and a sampling generalization term.
Theorem 4 follows by combining the privacy and sampling bounds with a union bound.
The framework is extended to multiclass classification using multiclass logistic regression and a sketch of its differential-privacy proof.

B.1. Standard ERM

This section derives sensitivity bounds for standard and weighted multiclass logistic-regression ERM, and compares them with parameter averaging. The analysis uses neighboring datasets, strong convexity, and gradient bounds.

Standard multiclass ERM: Multiclass logistic regression uses a stacked parameter vector and a softmax loss for K classes.
Standard multiclass ERM: The regularized empirical risk is λ-strongly convex, supporting sensitivity analysis of its minimizer.
Standard multiclass ERM: The standard multiclass minimizer’s sensitivity is bounded by analyzing the gradient difference between neighboring labeled datasets.
Majority-labeled ERM: The sensitivity of majority-labeled multiclass logistic regression is obtained from a gradient bound involving potentially different labels.
Weighted ERM: Weighted multiclass loss uses α_k(x) as an unbiased estimate of P(v = k|x), producing a corresponding weighted regularized empirical risk.
Weighted ERM: The weighted multiclass minimizer has sensitivity derived from probability differences whose nonzero components are bounded by 1/M.
Parameter averaging: Parameter averaging has sensitivity equal to 1/M times the sensitivity of a single classifier when one party’s full training data may change.