2024/11/27 by Shuli Jiang, Jiang, Shuli, Ying Zhang +4
Computer Science · Decision Sciences · #Auction Theory and Applications #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2411.17965
openalex publication_date 2024/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a classical problem in private prediction, the problem of computing an (mε, δ)-differentially private majority of K (ε, Δ)-differentially private algorithms for 1 ≤ m ≤ K and 1 > δ≥ Δ≥ 0. Standard methods such as subsampling or randomized response are widely used, but do they provide optimal privacy-utility tradeoffs? To answer this, we introduce the Data-dependent Randomized Response Majority (DaRRM) algorithm. It is parameterized by a data-dependent noise function γ, and enables efficient utility optimization over the class of all private algorithms, encompassing those standard methods. We show that maximizing the utility of an (mε, δ)-private majority algorithm can be computed tractably through an optimization problem for any m ≤ K by a novel structural result that reduces the infinitely many privacy constraints into a polynomial set. In some settings, we show that DaRRM provably enjoys a privacy gain of a factor of 2 over common baselines, with fixed utility. Lastly, we demonstrate the strong empirical effectiveness of our first-of-its-kind privacy-constrained utility optimization for ensembling labels for private prediction from private teachers in image classification. Notably, our DaRRM framework with an optimized γ exhibits substantial utility gains when compared against several baselines.