These labels were automatically added by AI and may be inaccurate. For details, see About Literature Database.
Abstract
Given a collection of vectors $x^{(1)},\dots,x^{(n)} \in \{0,1\}^d$, the
selection problem asks to report the index of an "approximately largest" entry
in $x=\sum_{j=1}^n x^{(j)}$. Selection abstracts a host of problems--in machine
learning it can be used for hyperparameter tuning, feature selection, or to
model empirical risk minimization. We study selection under differential
privacy, where a released index guarantees privacy for each vectors. Though
selection can be solved with an excellent utility guarantee in the central
model of differential privacy, the distributed setting lacks solutions.
Specifically, strong privacy guarantees with high utility are offered in high
trust settings, but not in low trust settings. For example, in the popular
shuffle model of distributed differential privacy, there are strong lower
bounds suggesting that the utility of the central model cannot be obtained. In
this paper we design a protocol for differentially private selection in a trust
setting similar to the shuffle model--with the crucial difference that our
protocol tolerates corrupted servers while maintaining privacy. Our protocol
uses techniques from secure multi-party computation (MPC) to implement a
protocol that: (i) has utility on par with the best mechanisms in the central
model, (ii) scales to large, distributed collections of high-dimensional
vectors, and (iii) uses $k\geq 3$ servers that collaborate to compute the
result, where the differential privacy holds assuming an honest majority. Since
general-purpose MPC techniques are not sufficiently scalable, we propose a
novel application of integer secret sharing, and evaluate the utility and
efficiency of our protocol theoretically and empirically. Our protocol is the
first to demonstrate that large-scale differentially private selection is
possible in a distributed setting.