Abstract
Differentially private machine learning trains models while protecting the privacy of sensitive training data. The key to obtaining differentially private models is to introduce noise or randomness to the training process. In particular, existing differentially private machine learning methods add noise to the training data, the gradients, the loss function, and/or the model itself. Bagging, a popular ensemble learning framework, randomly creates subsamples of the training data, trains a base model for each subsample using a base learner, and takes a majority vote among the base models when making predictions. Bagging has intrinsic randomness in the training process as it randomly creates subsamples. Our major theoretical results show that such intrinsic randomness already makes Bagging differentially private without the need for additional noise. Moreover, we prove that if no assumptions about the base learner are made, our derived privacy guarantees are tight. We empirically evaluate Bagging on MNIST and CIFAR10. Our experimental results demonstrate that Bagging achieves significantly higher accuracies than state-of-the-art differentially private machine learning methods with the same privacy budgets.
Introduction
Training machine learning models on sensitive data—such as medical records or financial history—risks leaking information about individual training examples through attacks like membership inference. To mitigate this, researchers typically employ Differential Privacy (DP), which ensures that the presence or absence of a single individual in a dataset does not significantly alter the model's output.
Standard DP methods in machine learning, such as DPSGD (Differential Privacy Stochastic Gradient Descent) or PATE (Private Aggregation of Teacher Ensembles), rely on injecting artificial noise into gradients or predictions. However, this noise often leads to a substantial degradation in model accuracy. This research explores whether Bagging (Bootstrap Aggregating), which inherently uses randomness to improve generalization, provides sufficient intrinsic privacy to satisfy formal DP requirements without additional noise injection.
Theoretical Framework: Privacy for Free
The core contribution of this work is the rigorous theoretical analysis of Bagging's privacy guarantees. Bagging works by creating $N$ subsamples of a training dataset of size $n$, training a base model on each, and aggregating their predictions via majority vote.
The authors analyzed two primary variants:
- Bagging with replacement: Subsamples of size $k$ are created by picking examples from the dataset, allowing duplicates.
- Bagging without replacement: Subsamples consist of $k$ unique examples.
By treating the subsampling process itself as the source of privacy, the authors derived $(\epsilon, \delta)$-differential privacy bounds. Crucially, these bounds are proven to be tight under the assumption that no specific properties of the base learner are known. This means that Bagging provides a "privacy for free" benefit: the same randomness used to boost accuracy also protects individual data points.
Empirical Evaluation
The effectiveness of Bagging as a private learning mechanism was evaluated on standard benchmarks: MNIST and CIFAR10.
As shown in Figure 5, testing accuracy increases significantly as the subsample size $k$ grows. Interestingly, there is very little difference in performance between bagging with and without replacement across both datasets.
Impact of Ensemble Size
The study also examined how the number of base models $N$ affects performance when the total number of samples used across all models ($N \cdot k$) is held constant.
Figure 1 illustrates that for a fixed budget of $N \cdot k$, increasing the number of base models $N$ (which implies smaller individual subsample sizes $k$) leads to a slight decrease in testing accuracy. This suggests that the quality of individual base models (determined by $k$) is a critical factor in the ensemble's overall performance.
Comparison with State-of-the-Art
Bagging demonstrated superior performance compared to traditional DP methods:
- CIFAR10 (No Public Data): With a privacy budget of $\epsilon \approx 0.2$, Bagging achieved 65.25% accuracy, vastly outperforming DPSGD, which reached only 27.86%.
- Transfer Learning: When combined with pre-trained models on public data, Bagging reached 79.55% accuracy on CIFAR10 ($\epsilon=0.2, \delta=0.18$), while PATE and DPSGD trailed at 42.55% and 30.63%, respectively.
- MNIST: Bagging achieved over 98% accuracy with a small privacy budget, nearly matching non-private performance.
Discussion and Limitations
While Bagging offers a powerful alternative for private ML, it has specific constraints. The derived theory shows that Bagging can only provide DP where $\delta \ge 1/n$. This "just a few" guarantee protects most training examples but may not meet the extremely strict requirements of environments demanding cryptographically small $\delta$ (e.g., $10^{-5}$).
Furthermore, while the bounds are tight for any base learner, the privacy could be even stronger if the base learner itself is "stable" (i.e., its output doesn't change much with small perturbations in input). Future research could explore the interaction between learner stability and bagging to further tighten these guarantees.
Conclusion
This work establishes that the intrinsic randomness of Bagging provides formal differential privacy guarantees. By avoiding the need for accuracy-destroying noise injection, Bagging achieves significantly higher performance than existing DP-ML methods, particularly in low-privacy-budget regimes.
Summary updated