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 into the training process. Existing methods typically add noise to data, gradients, or loss functions. Bagging, a popular ensemble learning framework, naturally incorporates randomness by creating subsamples of the training data. This paper demonstrates that this intrinsic randomness makes Bagging differentially private without requiring additional noise. We derive tight $(\epsilon, \delta)$-differential privacy guarantees for Bagging with and without replacement and show that these bounds are optimal for general base learners. Empirical evaluations on MNIST and CIFAR10 reveal that Bagging achieves significantly higher accuracy than state-of-the-art methods like DPSGD under the same privacy budgets.
Introduction
Training machine learning models on sensitive data—such as medical records or personal financial history—poses a significant risk of leaking individual information. Differential Privacy (DP) offers a rigorous mathematical framework to mitigate this risk, ensuring that the presence or absence of a single individual's data does not substantially alter the model's output.
Standard DP techniques, such as Differentially Private Stochastic Gradient Descent (DPSGD), achieve privacy by "injecting noise" into the training pipeline. While effective, this noise often acts as a "utility tax," significantly degrading model performance. This research explores whether privacy can be achieved through the "intrinsic randomness" already present in common training algorithms, specifically focusing on Bagging (Bootstrap Aggregating).
Theoretical Framework
Bagging builds an ensemble of models by training each on a random subsample of the original dataset. The authors analyze two primary variants: Bagging with replacement and Bagging without replacement.
The core theoretical contribution is the derivation of $(\epsilon, \delta)$-differential privacy guarantees for these methods. The researchers prove that the probability of a specific data point being excluded from a subsample provides a natural privacy shield.
Crucially, these bounds are proven to be tight. By employing a $k$-nearest neighbor algorithm as a "worst-case" base learner, the authors demonstrate that without specific assumptions about the base learner's stability, these formulas represent the absolute limit of provable privacy for the bagging framework.
Experimental Results
The effectiveness of Bagging's intrinsic privacy was evaluated on standard benchmarks including MNIST and CIFAR10. To further test utility, the authors also explored transfer learning scenarios using Fashion-MNIST and ImageNet as public datasets for pre-training.
The results indicate that Bagging provides a superior privacy-utility trade-off compared to traditional noise-injection methods.
As shown in the table above, Bagging maintains high accuracy even under very strict privacy budgets. For instance, on MNIST with $\epsilon \approx 0.005$, Bagging achieves 90.66% accuracy, while DPSGD struggles at 16.41%. Similar trends were observed on CIFAR10, where Bagging reached 79.55% accuracy (at $\epsilon=0.2, \delta=0.18$) compared to DPSGD's 30.63% under the same budget.
Key Insights
- Privacy as a Side Effect: The same mechanism Bagging uses to reduce variance and prevent overfitting—random subsampling—simultaneously provides differential privacy.
- The $\delta$ Trade-off: A theoretical constraint of Bagging is that the privacy parameter $\delta$ is bounded by $1/n$ (where $n$ is the dataset size). While strict DP theory often seeks $\delta \ll 1/n$, the empirical results suggest that the "failure probability" represented by $\delta$ is a worthwhile trade-off for the massive gains in model utility.
- Learner Agnosticism: Because the derived bounds make no assumptions about the base learner, they are universally applicable to any algorithm used within the Bagging ensemble.
Conclusion and Future Work
This work demonstrates that Bagging is an "intrinsically" private algorithm that can outperform specialized DP methods in practical scenarios. However, limitations remain. The inherent lower bound on $\delta$ may not satisfy applications requiring extreme privacy guarantees. Future research could investigate if assuming "base learner stability" could lead to even tighter privacy bounds and further utility improvements.
Summary updated