# Private Multi-Winner Voting for Machine Learning

arXiv: https://arxiv.org/abs/2211.15410 · HTML: https://mlsanity.com/paper/2211.15410/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 71 references that are in the map.
- First posted on arXiv 23 Nov 2022.

## Builds on (most cited first, 30 of 32)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [CheXpert: A Large Chest Radiograph Dataset with Uncertainty Labels and Expert Comparison](https://mlsanity.com/paper/1901.07031/) (2019)
- [MixMatch: A Holistic Approach to Semi-Supervised Learning](https://mlsanity.com/paper/1905.02249/) (2019)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [MIMIC-CXR-JPG, a large publicly available database of labeled chest radiographs](https://mlsanity.com/paper/1901.07042/) (2019)
- [Label-Only Membership Inference Attacks](https://mlsanity.com/paper/2007.14321/) (2020)
- [Asymmetric Loss For Multi-Label Classification](https://mlsanity.com/paper/2009.14119/) (2020)
- [Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data](https://mlsanity.com/paper/1610.05755/) (2016)
- [PadChest: A large chest x-ray image dataset with multi-label annotated reports](https://mlsanity.com/paper/1901.07441/) (2019)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [GS-WGAN: A Gradient-Sanitized Approach for Learning Differentially Private Generators](https://mlsanity.com/paper/2006.08265/) (2020)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [On the limits of cross-domain generalization in automated X-ray prediction](https://mlsanity.com/paper/2002.02497/) (2020)
- [Enabling Fast Differentially Private SGD via Just-in-Time Compilation and Vectorization](https://mlsanity.com/paper/2010.09063/) (2020)
- [Interpreting Chest X-rays via CNNs that Exploit Hierarchical Disease Dependencies and Uncertainty Labels](https://mlsanity.com/paper/2005.12734/) (2020)
- [Chasing Your Long Tails: Differentially Private Prediction in Health Care Settings](https://mlsanity.com/paper/2010.06667/) (2020)
- [CaPC Learning: Confidential and Private Collaborative Learning](https://mlsanity.com/paper/2102.05188/) (2021)
- [Federated Heavy Hitters Discovery with Differential Privacy](https://mlsanity.com/paper/1902.08534/) (2019)
- [Practical Locally Private Heavy Hitters](https://mlsanity.com/paper/1707.04982/) (2017)
- [LSHTC: A Benchmark for Large-Scale Text Classification](https://mlsanity.com/paper/1503.08581/) (2015)
- [Differentially Private Random Decision Forests using Smooth Sensitivity](https://mlsanity.com/paper/1606.03572/) (2016)
- [A bounded-noise mechanism for differential privacy](https://mlsanity.com/paper/2012.03817/) (2020)
- [Multi-label classification: do Hamming loss and subset accuracy really conflict with each other?](https://mlsanity.com/paper/2011.07805/) (2020)
- [What Do Multiwinner Voting Rules Do? An Experiment Over the Two-Dimensional Euclidean Domain](https://mlsanity.com/paper/1901.09217/) (2019)
- [PATE-AAE: Incorporating Adversarial Autoencoder into Private Aggregation of Teacher Ensembles for Spoken Command Classification](https://mlsanity.com/paper/2104.01271/) (2021)
- [Extreme Multi-label Classification from Aggregated Labels](https://mlsanity.com/paper/2004.00198/) (2020)

## Abstract (arXiv)

Private multi-winner voting is the task of revealing k-hot binary vectors satisfying a bounded differential privacy (DP) guarantee. This task has been understudied in machine learning literature despite its prevalence in many domains such as healthcare. We propose three new DP multi-winner mechanisms: Binary, τ, and Powerset voting. Binary voting operates independently per label through composition. τ voting bounds votes optimally in their ℓ2 norm for tight data-independent guarantees. Powerset voting operates over the entire binary vector by viewing the possible outcomes as a power set. Our theoretical and empirical analysis shows that Binary voting can be a competitive mechanism on many tasks unless there are strong correlations between labels, in which case Powerset voting outperforms it. We use our mechanisms to enable privacy-preserving multi-label learning in the central setting by extending the canonical single-label technique: PATE. We find that our techniques outperform current state-of-the-art approaches on large, real-world healthcare data and standard multi-label benchmarks. We further enable multi-label confidential and private collaborative (CaPC) learning and show that model performance can be significantly improved in the multi-site setting.