Abstract:
Inspired by the common subtask of ensembling or calibrating private models, we study the problem of computing an m*epsilon-differentially private majority of K epsilon-differentially private algorithms for m < K. We introduce a general framework to compute the private majority via Randomized Response (RRM) with a data-dependent noise function gamma that subsumes any non-trivial private majority algorithm, including the natural subsampling approach. Using the RRM framework, we derive an analytical framework for well-behaved gamma functions that explores the privacy utility tradeoff for different noise functions, showing a privacy amplification by a factor of 2 for computing the majority for i.i.d. mechanisms. Furthermore, we exploit the generality of our framework by applying a novel learning approach to find an optimized gamma that maximizes the utility while guaranteeing the output to be m*epsilon-differentially private. To support our theory, we demonstrate the effectiveness of the optimization approach in both simulations and a private image classification task, highlighting the outstanding performance of the optimized gamma against several baselines.

Committee:
Gauri Joshi (Chair)
Steven Wu
Jean Oh
Jack Good