Optimized Tradeoffs for Private Prediction with Majority Ensembling

Gauri Joshi; Qiuyi (Richard) Zhang; Shuli Jiang

REVIEW 3 major objections 5 minor 27 references

Optimized Tradeoffs for Private Prediction with Majority Ensembling

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that tuning private majority ensembling with a data-dependent noise function is tractable, because infinitely many privacy constraints reduce to a polynomial set, making the best noise schedule a linear program.

desk verdict Useful optimization machinery for private majority ensembling, but the 'all private algorithms' claim and the O(K^7) tractability result both rest on an unstated conditional-independence assumption. read the letter →

arxiv 2411.17965 v1 pith:AKMC3GUF submitted 2024-11-27 cs.LG cs.CR

Shuli Jiang , Qiuyi (Richard) Zhang , Gauri Joshi This is my paper · ORCID

classification cs.LGcs.CR

keywords differentialprivacyprivatepredictionmajorityensemblingrandomizedresponseamplificationdata-dependentnoisepoissonbinomialdistributionPATE

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Privacy-sensitive systems often aggregate the answers of several private mechanisms — teacher models voting on a label, for example — with standard tools like subsampling and randomized response that add noise without looking at the vote. This paper claims both are suboptimal and that the best possible private majority is a randomized response whose coin bias depends on the observed vote count. The central discovery is that choosing that data-dependent noise function to maximize accuracy is a linear program, because the infinitely many privacy constraints collapse to a polynomial-sized set: $O(K^7)$ in general and $O(K^3)$ in pure differential privacy. In the special case of identical independent teachers with pure privacy, the paper exhibits an explicit noise schedule provably twice as private as subsampling at the same accuracy, and with a privacy allowance beyond half the teachers the exact majority is already private. If the claims hold, private ensembles can be tuned rather than composed pessimistically, buying accuracy at a fixed privacy budget.

What carries the argument

The load-bearing object is the privacy cost objective of Lemma 3.4: a linear functional $f(p_1,\dots,p_K,p'_1,\dots,p'_K;\gamma)$ of the noise curve $\gamma$, whose coefficients are formed from the differences of the vote-count probabilities $\alpha_l=\Pr[L(D)=l]$ and $\alpha'_l=\Pr[L(D')=l]$ under a Poisson-binomial law. DaRRM is $(m\epsilon,\delta)$-private exactly when this functional stays below $e^{m\epsilon}-1+2\delta$ for every adjacent pair of datasets. Two structural facts make optimizing $\gamma$ tractable: each pair $(p_i,p'_i)$, forced to be close by the $\epsilon$-DP of mechanism $i$, lives in a polytope with eight corners (four when $\delta=0$), so the worst case is attained at corners; and the Poisson-binomial distribution is invariant under permuting its parameters, which collapses the corner combinations to $O(K^7)$ representatives ($O(K^3)$ when $\delta=0$). For the provable factor-two amplification in the i.i.d. pure-DP case, the argument runs through a 'symmetric form family' of noise functions built from hypergeometric tail probabilities and a binomial-expectation recurrence identity that converts privacy gradients into a comparison of two such expectations.

What would settle it

Solve a small instance — $K=3$ or $K=5$ — for the optimized $\gamma$, then brute-force the continuous maximization of the privacy cost $f$ over a fine grid of feasible pairs $(p_i,p'_i)$, or directly audit the released majority's output ratio on a neighboring dataset, and check whether the true worst case stays below $e^{m\epsilon}-1+2\delta$; the $O(K^7)$ reduction predicts it must, so any violation would falsify the central claim. A second check targets the independence premise: run two $(\epsilon,\Delta)$-DP mechanisms that share a single random coin and test whether the certified bound still holds.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that every reasonable private majority algorithm — anything no worse than a random guess — is exactly a data-dependent randomized response, called DaRRM, whose noise function $\gamma$ maps the observed vote count $L(D)$ to a probability of disclosing the true majority. Privacy of DaRRM reduces to a linear inequality $f(p_1,\dots,p_K,p'_1,\dots,p'_K;\gamma) \le e^{m\epsilon}-1+2\delta$ that must hold for all adjacent datasets. The paper's structural result is that the worst case over the continuous parameter pairs $(p_i,p'_i)$ always occurs at one of eight corners per mechanism (four when $\delta=0$), and permutation-invariance of the Poisson-binomial distribution then leaves only $O(K^7)$ distinct constraints ($O(K^3)$ when $\delta=0$), so maximizing utility over all private majorities is a linear program. In the i.i.d. pure setting the paper further proves that the majority of $2m-1$ subsampled votes is already $m\epsilon$-DP, a factor-of-two privacy amplification over simple composition, and that for $m \ge (K+1)/2$ the un-noised majority is already private. Empirically, at equal per-query privacy, the optimized DaRRM outperforms the subsampling baseline and the GNMax PATE baseline on private-teacher image-label ensembling.

Load-bearing premise

The load-bearing premise is that the $K$ mechanisms' outputs are independent conditional on the dataset, so the vote count follows a Poisson-binomial distribution; the eight-corner worst-case analysis and the $O(K^7)$ constraint reduction both depend on that structure, yet the paper never states independence explicitly in Problem 1.1.

Editorial extensions

If this is right

The best private majority for given $K$, $m$, $\epsilon$, $\delta$ is computable: the linear program over the reduced constraint set yields a noise curve that maximizes accuracy within the privacy budget, without any knowledge of the teachers' output distributions.
With i.i.d. teachers and pure differential privacy, the majority of $2m-1$ subsampled votes is certified $m\epsilon$-DP — a provable factor-two privacy gain over simple composition at the same utility; for $m \ge (K+1)/2$, releasing the exact majority is already private.
Subsampling is provably optimal only at $m=1$; for larger privacy allowances the optimized noise curve dominates both the subsampling curve and constant-probability randomized response in the reported simulations.
In private-teacher label ensembling at equal per-query privacy loss, the optimized DaRRM beats the subsampling baseline and the GNMax PATE baseline, with gains up to 30 percentage points on Fashion-MNIST when the number of teachers is small ($K=11$, $m=3$).

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A direct extension the paper leaves implicit: the optimization objective accepts any prior over the teachers' voting probabilities, so a data-derived prior (from a public holdout, for instance) should push accuracy beyond the uniform-prior simulations reported.
The paper's own practical-limitation note concedes that exact optimization with the $O(K^7)$ constraint set is limited to roughly $K \le 41$ on a laptop when $\delta>0$; pruning or sampling the constraint polytope, or exploiting more symmetry, is the natural route to larger ensembles.
Because the entire reduction assumes the vote count follows a Poisson-binomial law, the certificate would silently weaken if teachers were correlated given the data — shared randomness, overlapping training subsets, or bagging; measuring that leakage is a concrete stress test the paper does not run.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing to know: this paper is a real contribution to private prediction, but its headline claims are wider than the proofs. The DaRRM framework — data-dependent randomized response for majority ensembling — is new and useful. It generalizes classical RR, and the optimization machinery that reduces infinitely many privacy constraints to a polynomial set is genuinely clever. Under the right assumptions, the LP gives a tractable way to tune the noise function, and the experiments show consistent accuracy gains over GNMax, subsampling, and constant-RR baselines. I believe the core mechanism works.

The main soft spots are two overclaims. Lemma 3.3 says any algorithm at least as good as random guess can be represented as DaRRM. That is true if gamma can depend on the full output vector S. But the paper then restricts gamma to be a symmetric function of the vote sum L(S). That loses generality: an algorithm that treats the K mechanisms asymmetrically — e.g., trusting one teacher more than another — cannot be captured by a sum-based gamma. So the abstract's 'class of all private algorithms' is not the class the optimization actually searches. The claim should be narrowed to symmetric sum-based algorithms.

The second issue is the independence assumption, and it's load-bearing for the tractability result. Lemma 5.1 and Appendix C use that L(D) follows a Poisson binomial distribution. That requires the S_i to be independent conditional on D. Problem 1.1 never says that. If the mechanisms share randomness — a common seed, correlated noise — the pmf of L(D) is not determined by the marginals p_i, and the O(K^7) constraint reduction collapses. This is fixable: add an explicit conditional-independence assumption to Problem 1.1 and the math goes through. But as written, the optimization does not cover the stated problem.

Minor points: the 'factor of 2 privacy amplification' is really a factor-of-2 in subsample size at fixed epsilon; that's fine but the framing is a bit generous. The paper is honest about the O(K^7) limit and provides code.

Verdict: this deserves serious peer review. The idea is solid, the proofs are detailed, and the empirical gains are concrete. I would accept with minor revisions after the authors narrow the 'all algorithms' claim and state the conditional-independence assumption. For anyone working on private ensembling or composition, it's worth reading.

Referee Report

3 major / 5 minor

Summary. The paper studies the problem of privately aggregating K binary (epsilon, Delta)-DP mechanisms into an (m epsilon, delta)-DP majority vote. It introduces DaRRM, a randomized-response variant whose success probability is a data-dependent function gamma of the vote sum, and claims that optimizing gamma yields the best privacy-utility tradeoff over all private majority algorithms. The main technical results are: (1) a representational lemma showing any 'reasonable' majority algorithm is a DaRRM instance; (2) a privacy-cost characterization in terms of a function f of the mechanism output probabilities; (3) a factor-2 privacy amplification theorem for i.i.d. mechanisms in the pure-DP case; and (4) a reduction of the infinitely many privacy constraints in the utility optimization to O(K^7) (or O(K^3) for delta=0) constraints, making the optimization a linear program. The paper also reports simulation results and private semi-supervised knowledge-transfer experiments on MNIST and Fashion-MNIST, where optimized DaRRM outperforms PATE-style GNMax and subsampling baselines at equal per-query privacy.

Significance. If the claims hold as stated, this would be a valuable contribution: it offers the first systematic, constraint-based utility optimization for private majority ensembling, with a nontrivial structural reduction of the privacy constraints, a clean factor-2 amplification result in a special case, and reproducible experiments with an anonymous code link. The proofs in the appendix are detailed and mostly self-contained, and the linear-programming formulation with explicit privacy constraints is a principled way to search over noise functions. However, the advertised scope—'all private algorithms' and 'any m <= K'—is broader than what the technical assumptions support, so the significance depends on the authors clarifying and narrowing those claims.

major comments (3)

[§5, Lemma 5.1 and Appendix C.3] The O(K^7) constraint reduction is valid only if the K mechanism outputs S_1,...,S_K are independent conditional on D, because the proof identifies L(D)=sum_i S_i with a Poisson-binomial random variable and uses permutation invariance of its parameters p_i. Problem 1.1 defines S_i ~ M_i(D) but does not state this independence, and mechanisms sharing randomness (e.g., a common random seed) are not excluded. If the S_i are correlated, alpha_l = Pr[L(D)=l] is not determined by the marginals p_i alone, the linearity/corner argument in Appendix C.3 no longer applies, and the finite set P does not control the true worst-case privacy loss. Please add the conditional-independence assumption explicitly to Problem 1.1 and to the tractable-optimization claim, or extend the proof to handle correlated mechanisms.
[Abstract and §5 ("Optimizing Over All Algorithms")] The paper claims that the optimization 'enables efficient utility optimization over the class of all private algorithms' and that DaRRM 'captures all private majority algorithms.' Lemma 3.3 represents a general algorithm only with an unrestricted function gamma(S); the optimization in Eq. (2) restricts gamma to gamma(L) with gamma(l)=gamma(K-l). The reduction to a function of L is harmless for the output distribution because the majority g depends only on L, but the symmetry restriction is justified only under a permutation-symmetric prior T (e.g., the default uniform prior) or an explicitly symmetric utility objective. As stated, for a fixed heterogeneous mechanism tuple or an asymmetric prior, the optimized symmetric gamma need not dominate all algorithms. Please restate the optimality claim with the precise class and prior assumptions under which it is proved.
[Lemma 5.1] The statement 'if beta = max_{(p_i,p'_i)} in P f(...;gamma), then f(p*_1,...,p*_K,p'*_1,...,p'*_K;gamma) <= beta' has the inequality backwards relative to the intended claim. Since P is a subset of the feasible set, max_P f <= f(p*) always; the proof needs to establish the opposite inequality (or equality) to justify checking only P. As written, the lemma cannot support the replacement of the infinitely many constraints by the polynomial set, even though the proof's orbit-counting argument appears repairable. Please correct the statement and make the claimed equality explicit.

minor comments (5)

[Problem 1.1, Lemma 3.1, Theorem 4.1] The privacy allowance m is declared real-valued in Problem 1.1, but the subsampling formula in Lemma 3.1, the h(l) definition in Section 4, and the statement of Theorem 4.1 all use binomial coefficients or subsampling counts that require integer m; please disambiguate or handle fractional m explicitly.
[Lemma 3.3 proof] The proof contains the typo 'there exists a a general function' and should read 'there exists a general function'.
[Section 2.1 and Appendix C.2.2] There are minor typos: 'amout' in Section 2.1 and 'invovles' in Appendix C.2.2; please proofread.
[Section 5] The phrase 'we only need to optimize K+1/2 variables' is ambiguous; it should be written as (K+1)/2 variables.
[Footnote on practical limitation] The footnote correctly notes that O(K^7) constraints become intractable for large K (the authors report K <= 41 for delta > 0). The abstract's word 'tractable' should carry this qualification, since polynomial degree 7 is not practically tractable for large K.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation chain is self-contained and the main concern is an unstated independence assumption, which is a scope gap rather than a self-referential reduction.

full rationale

No circular reduction is present in the paper's derivation chain. Lemma 3.4 derives the privacy cost objective f directly from the definition of differential privacy applied to Algorithm 1, and Lemma 5.1's reduction of infinitely many privacy constraints to O(K^7) constraints follows from the multilinearity of the Poisson-binomial pmf in each p_i, the eight-corner characterization of the (epsilon,Delta)-DP feasible region, and permutation invariance; none of these steps re-uses the claimed conclusion as an input. The representation result in Lemma 3.3 is a translation between any reasonable algorithm and a suitable gamma, not a circular fit, and the later restriction to symmetric, sum-only gamma functions is a scope limitation rather than a tautology. Theorem 4.1 is proved by an independent gradient analysis and is not a restatement of simple composition. The optimized gamma is obtained by solving an explicit linear program subject to privacy constraints, not by fitting to test accuracy; comparisons in the image-classification experiments are against external baselines such as subsampling, randomized response, and PATE GNMax. The simulation plots in Section 6.1 report the very objective being optimized, so they are not empirical predictions, though this is a presentation choice rather than a circular derivation. The one substantive concern is that the Poisson-Binomial structure, and hence the O(K^7) constraint reduction, requires the K mechanisms' outputs to be conditionally independent given D, an assumption not stated in Problem 1.1. This is a correctness/scope gap in the problem formulation, not a circular step in the paper's derivations.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard DP composition theorems and on the implicit independence of the mechanisms. The paper's own algorithmic constructs (DaRRM, gamma, symmetric form family) are not invented entities in the sense of new physical or mathematical objects. The optimization introduces approximation parameters tau and T, which are computational and do not affect privacy guarantees.

free parameters (3)

tau = 50
Number of equally spaced grid points in [0.5, 1) used in the rectangular-rule approximation of the utility objective. A computational choice, not fitted to test data.
T = 10000
Number of Monte Carlo samples used in the integration approximation of the objective in Algorithm 5. A computational choice, not fitted to test data.
privacy allowance m = 3 in main experiments
The main experiment uses m=3, described as 'more interesting'; other m values are reported in the appendix. This selection does not affect the theoretical claims.

assumptions (5)

domain assumption Each teacher mechanism M_i is (epsilon, Delta)-differentially private.
This is the premise of Problem 1.1 and is used throughout the privacy analysis, e.g., Lemma 3.4 and Lemma 5.1.
domain assumption The mechanism outputs S_i are independent conditional on D, so L(D) follows a Poisson Binomial distribution.
Invoked in Section 5 (after Eq. 2) and Lemma 5.1 to justify the permutation-invariance constraint reduction. Not explicitly stated in Problem 1.1.
standard math Simple composition and general composition theorems (Dwork et al., Kairouz et al.) correctly upper-bound the privacy loss of composing DP mechanisms.
Used in Lemma A.1 and Table 2 to set baseline privacy parameters.
standard math The binomial expectation recurrence identity of Zhang et al. (2019) is correct.
Used in Lemma B.9 to derive expectation identities for h(l) in Theorem 4.1.
ad hoc to paper Theorem 4.1 restricts gamma to a symmetric monotone class (the 'symmetric form family').
The monotonicity assumption (gamma(l) >= gamma(l+1) for low l, etc.) is introduced in Appendix B to enable the gradient analysis; the theorem does not claim optimality over all gamma functions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Optimized Tradeoffs for Private Prediction with Majority Ensembling." pith.science (2026). https://pith.science/paper/AKMC3GUF

@misc{pith2026241117965,
  author       = {Pith},
  title        = {Pith review of: Optimized Tradeoffs for Private Prediction with Majority Ensembling},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AKMC3GUF}},
  note         = {Machine review of arXiv:2411.17965}
}

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.

Figures

Figures reproduced from arXiv: 2411.17965 by the authors.

**Figure 2.** Plots of the shape and E(DaRRMγ) of different γ functions: the optimized γopt , and the baselines γSub (corresponding to subsampling) and γconst (corresponding to RR). Here, K = 11, m ∈ {1, 3, 5, 7}, ϵ = 0.1, ∆ = 10−5 and δ = 1 − (1 − ∆)m ≈ m∆. We compare the shape and the error E(DaRRMγ) of different γ functions: an optimized γopt and the subsampling γSub as in Lemma 3.14 . We also compare against pconst in the cla… view at source ↗

**Figure 3.** A visualization of the above LP problem. [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

Figures from the paper (7 more)

**Figure 4.** Figure 4: The feasible region F is plotted as the blue area. The four boundaries are implied by p, p′ satisfying ϵ-differential privacy. Roadmap of Proof of Theorem 4.1. Since γ needs to enable Eq. 54 to be satisfied for all p, p′ ∈ [0, 1], we begin by showing characteristics o…

**Figure 5.** Figure 5: An illustration of the feasible region Fi . Proof. Part I: Reducing # privacy constraints from ∞ to exponentially many. Consider (pi , p′ i ) for an arbitrary i ∈ [K] and fixing (pj , p′ j ), ∀j ̸= i. Given any noise function γ, recall the privacy cost objective f(p1, …

**Figure 6.** Figure 6: Plots of the shape and E(DaRRMγ) of different γ functions: the optimized γSub, and the baselines γSub (corresponding to subsampling) and γconst (corresponding to RR). Here, K = 35, M ∈ {10, 13, 15, 20}, ∆ = 10−5 , ϵ = 0.1, δ ′ = 0.1. D.1.2 Comparison in Pure Differenti…

**Figure 7.** Figure 7: Plots of shape and E(DaRRMγ) of different γ functions: the optimized γOpt, the baselines γSub and γDSub (Theorem 4.1), and the constant γconst (corresponding to RR). Here, K = 11, m ∈ {1, 3, 5, 7, 9, 11}, ϵ = 0.1 and δ = ∆ = 0. Note when m ∈ {7, 9}, the cyan line (γDSu…

**Figure 8.** Figure 8: Plots of shape and E(DaRRMγ) of different γ functions: the optimized γOpt, the baselines γSub and γDSub (Theorem 4.1), and the constant γconst (corresponding to RR). Here, K = 101, m ∈ {10, 20, 30, 40, 60, 80}, ϵ = 0.1 and δ = ∆ = 0. 52 [PITH_FULL_IMAGE:figures/full_f…

**Figure 9.** Figure 9: Comparison of the shape and E(DaRRMγ) of different γ functions: 1) γ optimized under prior TU , 2) γ optimized under prior TP , 3) γSub (corresponding to the subsampling baseline) and 4) γconst (corresponding to the RR baseline). Here, K = 11, m ∈ {3, 5}, ϵ = 0.1. Obse…

**Figure 10.** Figure 10: Plots of [PITH_FULL_IMAGE:figures/full_fig_p055_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 26 canonical work pages

[1]

If l≤ K 2 , γ(l)−γ(l + 1) = (1− 2h(l))− (1− 2h(l + 1)) = 2h(l + 1)− 2h(l)

work page
[2]

7) needs to hold for worst case output probabilitiesq∗ x,q′∗ x that cause the maximum privacy loss

The above inequality ofpconst (Eq. 7) needs to hold for worst case output probabilitiesq∗ x,q′∗ x that cause the maximum privacy loss. That is,pconst needs to satisfy pconst·maxqx,q′xh(qx,q′ x)≤ 1 2emϵ− 1 2 +δ (8) 16 Published in Transactions on Machine Learning Research (November/2024) To find the worst case output probabilities, we solve the following L...

work page 2024
[3]

Double Subsampling

satisfies the monotonicity assumption, the privacy cost objectivef(p,p′;γ) is maximized whenp≥p′. Proof of Lemma B.3.Following Eq. 33 and Eq. 38 in the proof of Lemma 3.4, and thatδ = 0, Pr[DaRRMγ(D) = 1]≤emϵ Pr[DaRRMγ(D′) = 1] (75) ⇐⇒ K∑ l=K+1 2 (αl−emϵα′ l)γ(l)− K−1 2∑ l=0 (αl−emϵα′ l)γ(l) /bracehtipupleft/bracehtipdownright/bracehtipdownleft/bracehtipu...

work page 2024
[4]

K = 11, m∈{ 1, 3, 5, 7, 9, 11}

γconst (Baseline): the constantγ function that corresponds to the classical Randomized Response (RR) algorithm Setting 1. K = 11, m∈{ 1, 3, 5, 7, 9, 11}. 51 Published in Transactions on Machine Learning Research (November/2024) 0 0.5 1 m = 1 m = 3 0 0.5 1 m = 5 m = 7 0 5.5 110 0.5 1 m = 9 0 5.5 11 m = 11 Support l {0, 1, . . . , K} values Shape of functio...

work page 2024
[5]

If l≥ K 2 , γ(l + 1)−γ(l) = (2h(l + 1)− 1)− (2h(l)− 1) = 2h(l + 1)− 2h(l)

work page
[6]

symmetric form family

Since γ(K−1 2 ) =γ(K+1 2 ), 2γ(K− 1 2 ) = ( γ(K− 1 2 ) +γ(K + 1 2 ) ) (113) = ( 1− 2h(K− 1 2 ) + 2h(K + 1 2 )− 1 ) (114) = 2h(K + 1 2 )− 2h(K− 1 2 ) (115) Hence, following Eq. 112, the gradient,∇p′f(p′;γ), given a “symmetric form family”γ can be written as ∇p′f(p′;γ) K =−emϵ K−1∑ l=0 (K− 1 l ) p′l(1−p′)K−l ( 2h(l + 1)− 2h(l) ) (116) 36 Published in Transa...

work page 2024
[7]

On the boundaryp =eϵp′,∀p∈ [0, 1 1+e−ϵ ],∇p′f(p′;γ)≤ 0

work page
[8]

symmetric form family

On the boundary1−p′ =eϵ(1−p),∀p∈ [ 1 1+e−ϵ, 1],∇q′f(q′;γ)≥ 0 where q′ = 1−p′ then the global worst case probabilities given thisγ is (p∗,p′∗) = arg max(p,p′)∈Ff(p,p′;γ) = (0, 0). Further- more, since by Eq. 119,f(0, 0;γ)≤emϵ− 1 for anyγ, this impliesDaRRMγ is mϵ-differentially private by Lemma 3.4. Now, ifγ belongs to the “symmetric form family”, by Eq. 1...

work page 2019

Show all 27 references

[9]

If m = 0, theni = 0. 1 ( 1
[10]

EX(1)[ (X 0 )(1−X 0 ) ] = EX(1)[1] = 1, and (0 0 ) p0(1−p)0 = 1
[11]

If m = 1, (a) i = 0, 1 ( 1
[12]

EX(1)[ (X 0 )(1−X 1 ) ] = EX(1)[1−X] = 1−p, and (1 0 ) p0(1−p)1 = 1−p (b) i = 1, 1 ( 1
[13]

symmetric form family

EX(1)[ (X 1 )(1−X 0 ) ] = EX(1)[X] =p, and (1 1 ) p1(1−p)0 =p. Hence, Eq. 127 holds for the base case. Induction Hypothesis: Suppose the statement holds for someK ≥ 1 and 0≤ i ≤ m ≤ K. Consider 1≤i≤m≤K + 1, 1(K+1 m )EX(K+1) [(X i )(K + 1−X m−i )] (128) = 1(K+1 m )EX(K+1)[ X! i...

2024
[14]

If p = 0 or p = 1, αl =αK−l
[15]

Otherwise, forp∈ (0, 1), (a) If p≥ 1 2, αl αK−l = pl(1−p)K−l pK−l(1−p)l =p2l−K(1−p)K−2l = ( p 1−p/bracehtipupleft/bracehtipdownright/bracehtipdownleft/bracehtipupright ≥1 ) 2l−K/bracehtipupleft/bracehtipdownright/bracehtipdownleft/bracehtipupright ≥0 ≥ 1, ⇒αl≥αK−l (187) (b) If...

2024
[16]

the same distribution

+ K∑ l=K+1 2 αl(1 2− 1 2γ(l)) ⏐⏐⏐   (195) The above follows by conditioning onL =l∈{ 0, 1,...,K }, i.e. the sum of observed outcomes inS = Ep1,p2,...,pK∼T   ⏐⏐⏐1 2 K∑ l=K+1 2 (αl−αK−l) (1−γ(l)) ⏐⏐⏐   (196) The above follows by symmetry ofγ Furthermore, notice the objecti...

2024
[17]

γopt (Ours): optimizedγ function using our optimization framework
[18]

γSub (Baseline): theγ function that corresponds to outputting the majority ofm out K subsampled mechanisms
[19]

γDSub (Baseline): theγ function that corresponds to outputting2m− 1 subsampled mechanisms from Theorem 4.1, aka., Double Subsampling (DSub)
[21]

γopt−U denote theγ function optimized underpi∼T U
[22]

γopt−P denote theγ function optimized underpi∼T P
[23]

γSub, corresponding to the subsampling baseline
[24]

the actualpi distributions, regardless of the prior used to optimizeγ

γconst, corresponding to theRR baseline Note when we compute the error, we take the expectation w.r.t. the actualpi distributions, regardless of the prior used to optimizeγ. In the experiments, we consider three different actualpi distributions:"
[25]

Actual: Uniform([0, 1])

“Actual: Uniform([0, 1])”: pi∼T U,∀i∈ [K]
[26]

Actual:pi = 0.5

“Actual:pi = 0.5”: pi = 0.5,∀i∈ [K] This setting implies the mechanisms do not have a clear majority
[27]

Actual: Uniform([0, 0.1])

“Actual: Uniform([0, 0.1])”: pi∼ Uniform([0, 0.1]),∀i∈ [K] This setting implies the mechanisms have a clear majority (i.e., 0) Since our prior TP is closer to Uniform([0, 0.1]) (i.e., there is a clear majority), we would expect E(DaRRMγopt−P ) to be the lowest whenpi∼ Uniform[...

2018
[2017]

private prediction strikes back!

doi: 10.1007/978-3-319-57048-8_7. URL https://doi.org/10.1007/978-3-319-57048-8_7. Laurens van der Maaten and Awni Hannun. The trade-offs of private prediction, 2020. Ming Xiang and Lili Su. $\beta$-stochastic sign SGD: A byzantine resilient and differentially private gradient...

2020

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

If l≤ K 2 , γ(l)−γ(l + 1) = (1− 2h(l))− (1− 2h(l + 1)) = 2h(l + 1)− 2h(l)

work page

[2] [2]

7) needs to hold for worst case output probabilitiesq∗ x,q′∗ x that cause the maximum privacy loss

The above inequality ofpconst (Eq. 7) needs to hold for worst case output probabilitiesq∗ x,q′∗ x that cause the maximum privacy loss. That is,pconst needs to satisfy pconst·maxqx,q′xh(qx,q′ x)≤ 1 2emϵ− 1 2 +δ (8) 16 Published in Transactions on Machine Learning Research (November/2024) To find the worst case output probabilities, we solve the following L...

work page 2024

[3] [3]

Double Subsampling

satisfies the monotonicity assumption, the privacy cost objectivef(p,p′;γ) is maximized whenp≥p′. Proof of Lemma B.3.Following Eq. 33 and Eq. 38 in the proof of Lemma 3.4, and thatδ = 0, Pr[DaRRMγ(D) = 1]≤emϵ Pr[DaRRMγ(D′) = 1] (75) ⇐⇒ K∑ l=K+1 2 (αl−emϵα′ l)γ(l)− K−1 2∑ l=0 (αl−emϵα′ l)γ(l) /bracehtipupleft/bracehtipdownright/bracehtipdownleft/bracehtipu...

work page 2024

[4] [4]

K = 11, m∈{ 1, 3, 5, 7, 9, 11}

γconst (Baseline): the constantγ function that corresponds to the classical Randomized Response (RR) algorithm Setting 1. K = 11, m∈{ 1, 3, 5, 7, 9, 11}. 51 Published in Transactions on Machine Learning Research (November/2024) 0 0.5 1 m = 1 m = 3 0 0.5 1 m = 5 m = 7 0 5.5 110 0.5 1 m = 9 0 5.5 11 m = 11 Support l {0, 1, . . . , K} values Shape of functio...

work page 2024

[5] [5]

If l≥ K 2 , γ(l + 1)−γ(l) = (2h(l + 1)− 1)− (2h(l)− 1) = 2h(l + 1)− 2h(l)

work page

[6] [6]

symmetric form family

Since γ(K−1 2 ) =γ(K+1 2 ), 2γ(K− 1 2 ) = ( γ(K− 1 2 ) +γ(K + 1 2 ) ) (113) = ( 1− 2h(K− 1 2 ) + 2h(K + 1 2 )− 1 ) (114) = 2h(K + 1 2 )− 2h(K− 1 2 ) (115) Hence, following Eq. 112, the gradient,∇p′f(p′;γ), given a “symmetric form family”γ can be written as ∇p′f(p′;γ) K =−emϵ K−1∑ l=0 (K− 1 l ) p′l(1−p′)K−l ( 2h(l + 1)− 2h(l) ) (116) 36 Published in Transa...

work page 2024

[7] [7]

On the boundaryp =eϵp′,∀p∈ [0, 1 1+e−ϵ ],∇p′f(p′;γ)≤ 0

work page

[8] [8]

symmetric form family

On the boundary1−p′ =eϵ(1−p),∀p∈ [ 1 1+e−ϵ, 1],∇q′f(q′;γ)≥ 0 where q′ = 1−p′ then the global worst case probabilities given thisγ is (p∗,p′∗) = arg max(p,p′)∈Ff(p,p′;γ) = (0, 0). Further- more, since by Eq. 119,f(0, 0;γ)≤emϵ− 1 for anyγ, this impliesDaRRMγ is mϵ-differentially private by Lemma 3.4. Now, ifγ belongs to the “symmetric form family”, by Eq. 1...

work page 2019