# Optimized Tradeoffs for Private Prediction with Majority Ensembling

Source: [Optimized Tradeoffs for Private Prediction with Majority Ensembling](<https://www.sota2.com/research/paper/68fa75e81e209131cea6a919>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-27T06:43:58.474Z

Authors: Shuli Jiang, Qiuyi (Richard) Zhang, Gauri Joshi

Published: 2024-11-27T00:48:48.000Z

## Abstract

We study a classical problem in private prediction, the problem of computing an $(m\\epsilon, \\delta)$-differentially private majority of $K$ $(\\epsilon, \\Delta)$-differentially private algorithms for $1 \\leq m \\leq K$ and $1 \> \\delta \\geq \\Delta \\geq 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 $\\gamma$, 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\\epsilon, \\delta)$-private majority algorithm can be computed tractably through an optimization problem for any $m \\leq 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 $\\gamma$ exhibits substantial utility gains when compared against several baselines.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2411.17965>)

[PDF](<https://arxiv.org/pdf/2411.17965.pdf>)
