TL;DR
This paper introduces a novel, highly efficient method for generating random noise in a secure, multi-party computation (MPC) setting. This is crucial for enabling differentially private collaborative learning, allowing multiple parties to train a shared model without compromising individual data privacy, and significantly outperforms prior methods in speed and communication efficiency.
What Problem Does This Paper Address?
Collaborative learning (CL) allows multiple parties to jointly train a machine learning model, pooling their data and expertise. To ensure differential privacy (DP) for the training data, noise must be added to gradient updates. In a decentralized CL setting, there's no single trusted party to add this noise. Two main approaches exist:
- Distributed DP: Each party adds noise locally. This requires adding more noise to compensate for potential collusion among parties, which degrades model utility.
- DP via MPC: Noise is sampled within a secure MPC protocol during gradient aggregation. This preserves model utility but has historically been computationally expensive and slow, especially with many parties, making it impractical for large-scale CL.
This paper addresses the inefficiency of MPC-based noise sampling, aiming to make it practical for real-world collaborative learning scenarios.
Methods
The core innovation is a "bottom-up" approach to MPC noise sampling. Instead of adapting existing sampling algorithms for specific distributions to MPC, they develop a generic method to approximate any discrete distribution with a statistically indistinguishable distribution that can be efficiently sampled in MPC.
Key techniques include:
- Dice Ensembles: They represent discrete distributions as "dice ensembles," which are essentially trees of table lookups.
- Table Lookups: The fundamental building block is a uniform random table lookup, analogous to rolling a die. By composing multiple such lookups, they can approximate complex distributions with high fidelity.
- Statistical Indistinguishability: They prove that their constructed distributions are statistically indistinguishable from the target distributions, meaning an adversary cannot tell if the noise came from the original distribution or their approximation.
- Efficient MPC Protocol: They design a secure MPC protocol that leverages these table lookups for fast and communication-efficient noise sampling. This protocol is designed to scale well with the number of participating parties.
Datasets
The paper evaluates their DP-CL method on standard natural language processing datasets:
- SST2
- QQP
- MNLI
- QNLI
These datasets are used in conjunction with the RoBERTa-base model for fine-tuning soft prompts and classifier layers.
Key Insights and Ideas
- "Bottom-Up" Generality is Key: The most significant insight is that by first approximating any target distribution into a form suitable for MPC (table lookups), they achieve both efficiency and flexibility, unlike prior "top-down" methods optimized for specific distributions.
- Table Lookups as a Universal Building Block: The paper demonstrates that a surprisingly small number of table lookups can approximate complex distributions to a degree that is statistically indistinguishable for privacy purposes.
- Scalability Breakthrough: The proposed MPC protocol shows dramatic improvements in runtime and communication as the number of parties increases, a critical factor for practical collaborative learning.
- Collusion Resilience Pays Off: By using centralized MPC noise sampling, their method avoids the need for extra noise to counter collusion, leading to better model utility compared to distributed DP methods that must account for colluding clients.
Key Results
- Massive Speedup: For 32 parties, their protocol is up to 450x faster than prior state-of-the-art MPC noise sampling methods.
- Reduced Communication: For 32 parties, they achieve 13x less communication compared to prior work.
- Statistical Indistinguishability: They provide theoretical guarantees that the sampled noise is statistically indistinguishable from the target distribution.
- Improved Model Utility: In DP-CL experiments, their method achieves comparable or better accuracy than baselines, especially in scenarios with many colluding clients, due to the reduced noise required. For example, on the SST2 dataset, their method achieved 89.68% accuracy compared to 83.44% for distributed DP with 9 colluding clients.
Limitations and Future Work
- Computational Overhead: While significantly improved, the MPC sampling still incurs substantial runtime and communication costs per training round, limiting its immediate practicality in all contexts. Further efficiency improvements are needed.
- Malicious Security Model: The current work focuses on the semi-honest security model. Extending it to the malicious security model, potentially using zero-knowledge proofs for table lookups, is a promising future direction.
- Continuous Distributions: The current method is designed for discrete distributions. Adapting it to continuous noise distributions, perhaps using snapping mechanisms, is another avenue for future research.
Summary updated