  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, $\tau$, and Powerset voting. Binary voting operates independently per
label through composition. $\tau$ voting bounds votes optimally in their
$\ell_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.
