Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy Elena Ghazi∗1
Jawad Nasser2
Flavio Calmon1
Ibrahim Issa2
1
arXiv:2606.07443v1 [cs.IT] 5 Jun 2026
2
Harvard University American University of Beirut
Abstract We study optimal design of ε-locally differentially private mechanisms for binary hypothesis testing. Each observation is drawn from one of two known distributions P0 , P1 on a finite alphabet of size k, privatized by a mechanism Q, and then used to infer which distribution generated the data. We measure testing utility using an f -divergence—including total variation, KL, and hockey-stick divergences—between the two induced output distributions. Previous work established structural properties of optimal mechanisms, but only yielded exponential-time algorithms. We prove a sharp structure: for every ε and every f -divergence objective, after sorting the alphabet by likelihood ratio, there exists an optimal mechanism that partitions the sorted alphabet into contiguous blocks and applies randomized response to the block label. We call this class Sort-Partition-Randomize (SPR). This characterization yields an exact dynamic program that computes an optimal mechanism in O(k3 ) time, and more generally in O(ℓk2 ) time with an ℓ-output budget. Our results make it possible to efficiently compute and characterize the exact optimum across the full privacy range, beyond asymptotic privacy regimes.
Contents 1 Introduction
3
2 Problem setup and SPR mechanisms
5
3 Main results
7
3.1
SPR optimality theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.2
Exact dynamic program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.3
Closed-form optimal mechanism for Eγ -divergences . . . . . . . . . . . . . . . . . . . . . .
8
3.4
Other objectives: Rényi divergences and ℓr distance . . . . . . . . . . . . . . . . . . . . .
9
3.5
Numerical illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
4 Geometry of SPR optimality
10
4.1
Extreme refinements: from extreme points to LR-contiguous staircase channels . . . . . .
10
4.2
Convex hull of SPR mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
∗ Corresponding author: [email protected]
1
4.3
Nontrivial coarsenings are not extreme . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4.4
Proof of the SPR theorem and its f -divergence corollary . . . . . . . . . . . . . . . . . . .
12
5 Exact dynamic program
13
5.1
Interval scores and DP recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
5.2
Runtime, output constraint, and traceback . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
5.3
Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
6 Conclusion and limitations
16
A Extreme points admit LR-contiguous staircase refinements
18
A.1 Staircase refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
A.2 Staircase obstructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
A.3 Perturbation lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
A.4 Proof of Proposition 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
B Convex hull of SPR mechanisms
31
C Nontrivial coarsenings of SPR mechanisms
35
D Optimality of the generalized binary mechanism for Eγ
38
E Numerical experiments
39
E.1 Monte-Carlo verification of the joint-range polytope . . . . . . . . . . . . . . . . . . . . .
39
E.2 KL comparison: setup, bootstrap CIs, and runtimes . . . . . . . . . . . . . . . . . . . . .
40
2
1
Introduction
Balancing privacy and utility is a central challenge in data disclosure control. A canonical instance of this challenge is privacy-preserving binary hypothesis testing: a set of samples is drawn from one of two distributions, denoted by P0 and P1 , and each sample is randomized to ensure privacy. An analyst then performs a hypothesis test to infer which distribution generated the samples given the privatized outputs. A natural measure of how much testing power survives randomization is an f -divergence between the privatized output distributions induced by P0 and P1 . Different choices of f capture different operational quantities: total variation determines the probability of correct guessing under a balanced prior (i.e., when the two hypotheses are equally likely), Eγ (or hockey-stick) divergences trace operating points along the Neyman–Pearson ROC curve, and KL divergence controls the exponential decay of error probabilities as the analyst accumulates samples [1–3]. We study privacy-preserving binary hypothesis testing under local differential privacy (LDP). LDP [4, 5] is among the most stringent notions of privacy, requiring each sample to be randomized individually prior to disclosure. However, this strictness comes at a substantial utility cost in statistical applications [6, 7]. A natural design objective is therefore to find LDP mechanisms that maximize an f -divergence between the privatized output distributions induced by P0 and P1 . Formally, for ν ∈ {0, 1}, an observation X ∼ Pν on a finite alphabet X of size k is privatized through an ε-locally differentially private channel Q(· | x) with finite output alphabet Y, producing an output Y ∈ Y. The ε-LDP constraint requires that for all x, x′ ∈ X and all y ∈ Y, Q(y | x) ≤ eε Q(y | x′ ).
(1)
Denote by Mν := Q⊤ Pν the output distribution induced by Pν and Q. Given a convex function f : R+ → R with f (1) = 0, our goal is to design Q to maximize the f -divergence defined as: X 0 (y) Df (M0 ∥M1 ) := M1 (y)f M (2) M1 (y) . y∈Y
Let Qε be the set of ε-LDP channels (with input alphabet X ). We can formulate our optimization as: max Df (Q⊤ P0 ∥Q⊤ P1 ).
Q∈Qε
(3)
We also consider the case in which the output alphabet is constrained to be less than or equal to a given size ℓ (referred to as a communication constraint by Pensia et al. [3]). To wit, we replace Qε in (3) by Qε,ℓ , the set of ε-LDP channels with at most ℓ outputs: max Df (Q⊤ P0 ∥Q⊤ P1 ).
Q∈Qε,ℓ
(4)
Despite the relative simplicity of the formulations, exact optimal mechanisms were previously understood only in special regimes: a binary-output mechanism for all f -divergences at sufficiently small ε, and randomized response on the original alphabet for KL at sufficiently large ε [8] (the latter requires ℓ ≥ k in the constrained case). The intermediate regime, where privacy and utility must genuinely be balanced—and arguably the case of greatest practical interest—has remained computationally out of reach: although significant results on the structure of the optimizers have been derived by Kairouz et al. [8] and Pensia et al. [3], the resulting algorithms are exponential in k (in the unconstrained output size case) or in ℓ (in the constrained case). Contributions.
Our contributions in this paper are threefold:
1) We provide the first polynomial time algorithm to find an optimal mechanism. In particular, we provide a dynamic program that runs in O(k 3 ) in the unconstrained case, and O(ℓk 2 ) in the constrained case. 3
0.8
0.8
Dkl (M0 kM1 ) / Dkl (P0 kP1 )
1.0
Dkl (M0 kM1 ) / Dkl (P0 kP1 )
1.0
0.6
0.6
0.4
0.4
optimal (KOV LP) SPR mechanism (DP, ours) binary mechanism k-ary randomized response
0.2
0.0
0
2
4
ε
6
8
0.2
0.0
10
(a) k = 6.
SPR mechanism (DP, ours) binary mechanism k-ary randomized response 0
2
4
ε
6
8
10
(b) k = 100.
Figure 1: Average normalized KL utility Dkl (M0 ∥M1 )/Dkl (P0 ∥P1 ) versus ε, averaged over T = 100 Dirichlet(1k ) pairs (P0 , P1 ) (NumPy seed 0, ε grid {0, 0.1, . . . , 10}). a k = 6, where the KOV LP is tractable. b k = 100, where the KOV LP is infeasible. Full setup, mechanism implementations, runtimes, and bootstrap bands are in Appendix E.
Consequently, our results enable the design of optimal mechanisms for alphabet sizes that were previously computationally infeasible. We illustrate this in Figure 1 for the unconstrained optimization with k = 100. 2) Our dynamic program follows from a sharp structural characterization of the optimizers of (3) and (4), formally stated in Theorem 3.1. Specifically, after sorting the input symbols by the likelihood ratios P0 (x)/P1 (x), there is an optimal channel that partitions the sorted alphabet into contiguous blocks and applies randomized response to the block label (we illustrate an example in Figure 2). We refer to mechanisms of this form as sort–partition–randomize (SPR) mechanisms. Beyond computational efficiency, SPR mechanisms yield a simple interpretable description of the optimal privatization strategy: aggregate symbols with similar likelihood ratios, then privatize only the resulting coarse label. Furthermore, the optimality of SPR mechanisms immediately implies that an optimal mechanism does not require more than k outputs (as a partition of an alphabet of size k cannot have more than k blocks). This recovers a result by Kairouz et al. [8]. Moreover, it enables us to jointly address both formulations (3) and (4). In fact, our approach shows that SPR mechanisms are optimal for any convex objective. However, the dynamic program further utilizes the decomposability of f -divergences. 3) We recover and extend optimality results when Df is the Eγ divergence. In particular, there exists an optimal binary-output mechanism, for every ℓ ≥ 2, which can be viewed as a privatized version of the Neyman-Pearson threshold. Zamanlooy et al. [9] provided an upper bound on the optimal value in (3) for the Eγ divergence. The upper bound was known to be tight for binary input distributions. We show that this result follows from our structural characterization theorem, and prove that it is tight for any input alphabet size. Prior work. Kairouz et al. [8] showed that, for a broad class of utilities including f -divergences, an optimal ε-LDP mechanism may be chosen to be staircase: for each output y, the probabilities Q(y | x) take only two values, θy and eε θy , as x varies. This reduces the optimization over arbitrary mechanisms to a finite linear program with one variable for each possible high set H ⊆ X , hence 2k variables. They also identified simple optimal mechanisms in extreme regimes: a binary-output mechanism for sufficiently 4
small ε for any f -divergence, and randomized response on the original alphabet (i.e., k-ary randomized response) for sufficiently large ε in the KL case, with distribution-dependent ε thresholds. Our work replaces this exponential search by an O(k 3 ) dynamic program, giving exact optimization across the full privacy range. Pensia et al. [3] studied the geometry of achievable pairs of output distributions under LDP and communication constraints. In the ε-LDP setting with an ℓ-output budget, they showed that extreme achievable pairs can be realized by first quantizing the input using likelihood-ratio thresholds into at most 2ℓ2 intermediate symbols, and then applying an extreme ε-LDP channel from this intermediate alphabet to 2 3 the ℓ outputs. This gives an algorithm with runtime polynomial in k ℓ and 2O(ℓ log ℓ) [3, Corollary 4], hence polynomial in k only when ℓ is treated as a constant. Building on this geometric perspective and a perturbation-based argument, we sharpen the structure substantially: in the pure LDP, f -divergence setting, the intermediate quantizer and arbitrary private channel collapse to an SPR mechanism, yielding the O(ℓk 2 ) dynamic program. Tsitsiklis [10] studied the non-private analogue and showed the optimality of likelihood-ratio quantizers for broad classes of binary testing and quantization problems. Our SPR mechanisms are the private counterpart: sort by likelihood ratio, partition into contiguous blocks, and then apply randomized response. As ε → ∞, randomized response becomes deterministic, so SPR mechanisms recover the non-private likelihood-ratio quantizers. The remainder of this paper is organized as follows. Section 2 fixes notation and introduces staircase and SPR mechanisms. Section 3 states our main theorems: SPR optimality, the dynamic program, the closed-form mechanism for Eγ -divergences, and consequences for Rényi divergences and ℓr distance objectives. Section 4 develops the joint-range geometry behind SPR optimality and proves Theorem 3.1 and Corollary 3.2. Section 5 gives the O(ℓk 2 ) dynamic program, including its runtime, traceback, and pseudocode.
2
Problem setup and SPR mechanisms
This section fixes notation and introduces the two structural objects on which the rest of the paper is built: staircase mechanisms and sort–partition–randomize (SPR) mechanisms. Notation. We recall the setup from Section 1. An observation X ∼ Pν for ν ∈ {0, 1} on a finite alphabet X is privatized through an ε-LDP channel Q with finite output alphabet Y, i.e., Q(y | x) ≤ eε Q(y | x′ ) for all x, x′ ∈ X and y ∈ Y, producing an output Y ∈ Y. The induced output marginals are Mν := Q⊤ Pν , and utility is measured by an f -divergence Df (M0 ∥M1 ) for a convex f : R+ → R with f (1) = 0. The goal is to design Q to maximize Df (M0 ∥M1 ). Likelihood-ratio ordering and reduction of ties. We first remove a few degenerate cases so that the likelihood-ratio order is strict, which is the setting used in intermediate arguments. Deleting symbols with zero mass under both hypotheses and merging symbols with the same likelihood ratio P0 (x)/P1 (x) does not change the induced output pair (M0 , M1 ) of any ε-LDP mechanism: within each likelihood-ratio class, replacing the corresponding rows by the appropriate weighted average preserves ε-LDP and leaves both induced marginals unchanged. Conversely, any mechanism on the reduced alphabet can be lifted to the original alphabet by copying its row to all symbols in the corresponding class. We relabel the reduced likelihood-ratio-sorted alphabet as [k], and write p, q for the reduced distributions. Thus k may be smaller than |X |, and 0 ≤ r1 < r2 < · · · < rk ≤ ∞,
5
ri :=
pi . qi
(5)
Output constraints and the joint range. Let Qε denote the set of ε-LDP channels with input alphabet [k]. For ℓ ≥ 1, let Qε,ℓ denote the set of ℓ-output ε-LDP channels, n o Qε,ℓ := Q ∈ Rk×ℓ : Q1ℓ = 1k , Q is ε-LDP , (6) + and the fixed-output joint range n o Rℓ (p, q) := (Q⊤ p, Q⊤ q) : Q ∈ Qε,ℓ .
(7)
We assume ε > 0 throughout. When ε = 0, every feasible channel is input-independent, so Q⊤ p = Q⊤ q and every f -divergence objective is zero. Staircase mechanisms. For any channel Q, an output y ∈ Y is active if Q(y | ·) is not identically zero.
Definition 2.1 (Staircase mechanism and high set). An ε-LDP mechanism Q is a staircase mechanism if, for every active y and for all x and x′ , Q(y|x)/Q(y|x′ ) ∈ {e−ε , 1, eε }. Moreover, for each y, we define the high set Hy ⊆ X as: Hy = {x ∈ X : Q(y|x) = max Q(y|x′ )}. ′ x ∈X
If Q is staircase, it will be convenient to express each active column y as Q(i, y) = θy 1 + (eε − 1)1{i ∈ Hy } , θy > 0, Hy ⊆ [k].
(8)
(9)
We call θy the column scale and Hy the high set of column y. When an active staircase column is constant, i.e., Q(i, y) ≡ αy > 0, we write it as Q(i, y) = αy e−ε 1 + (eε − 1)1{i ∈ [k]} . (10) With this convention, every active high set is nonempty. SPR mechanisms and example. If τ : [m] → [ℓ] is a deterministic map and Q ∈ Rk×m , we write + P τ ◦ Q ∈ Rk×ℓ for the post-processed channel (τ ◦ Q)(i, y) := Q(i, z). An LR-contiguous partition + z:τ (z)=y of [k] is a partition π = (B1 , . . . , Bs ) into nonempty intervals in the likelihood-ratio order. Definition 2.2 (Sort–partition–randomize mechanism). A sort–partition–randomize (SPR) mechanism first sorts the input symbols as x1 , . . . , xk by likelihood ratio P0 (xi )/P1 (xi ), partitions this ordered alphabet into contiguous blocks π = (B1 , . . . , Bs ), and then applies s-ary randomized response (RR) to the block label: eε ε , x ∈ Bj , Qπ (j | x) = e +1s − 1 (11) , x ∈ / B . j eε + s − 1
Equivalently, Qπ is a staircase mechanism whose active high sets are exactly the likelihood-ratio-contiguous blocks B1 , . . . , Bs . When needed, we may also view Qπ as a channel with a larger output alphabet by relabeling its s active outputs and padding the remaining columns with zeros.
Example 2.3. Figure 2 illustrates an SPR mechanism. Here k = 6, the inputs are already ordered by likelihood ratio, and the partition has s = 3 contiguous blocks. Each row has one high entry and two low entries, so after normalization the channel is exactly 3-ary RR on the block label. Remark 2.4. The binary mechanism of Kairouz et al. [8] is a special case with s = 2. Their KL-optimal randomized response mechanism in the sufficiently low-privacy / large-ε regime is the special case in which every block is a singleton (k-ary RR). 6
x1 x2 x3 x4 x5 x6
B1
B2
B3
ε
1
1
B1 = [1:2]
B2 = [3:5] staircase patterns B3 = [6:6]
e
ε
e
1
1
eε
1
eε
1
eε
1
1
B1
B2
B3
1 1 eε B1 ε 1 e + 2 eε + 2 eε + 2 1 ε 1 1 e B 2 ε + 2 eε + 2 eε + 2 e 1 apply ε 3-ary RR 1 1 e B 1 to block label 3 eε + 2 eε + 2 eε + 2 eε
Figure 2: An LR-contiguous partition and the corresponding staircase pattern, with inputs labeled so that r1 ≤ r2 ≤ · · · ≤ r6 where ri = pi /qi . After normalization, this becomes 3-ary RR on the block label.
3
Main results
This section collects the headline statements of the paper. Section 3.1 states the structural characterization of optimal mechanisms; Section 3.2 states the resulting polynomial-time algorithm; Sections 3.3 and 3.4 state consequences for Eγ -divergences and other utility objectives.
3.1
SPR optimality theorem
Our main structural result is that, after sorting the alphabet by likelihood ratio, every extreme point of the fixed-output joint range Rℓ (p, q) is attained by an SPR mechanism. Theorem 3.1 (Extreme points are sort–partition–randomize). If (u, v) ∈ Rℓ (p, q) is an extreme point, then there exists an LR-contiguous partition π = (B1 , . . . , Bs ) of [k] such that (u, v) is induced by an ℓ-output channel obtained from Qπ by relabeling its active outputs and padding with zero columns. In particular, necessarily s ≤ ℓ and s ≤ k. Equivalently, every extreme point of Rℓ (p, q) is realized by a sort–partition–randomize mechanism. Since every f -divergence is convex in the induced pair (M0 , M1 ), the maximum over Rℓ (p, q) is attained at an extreme point. Theorem 3.1 therefore yields the following optimality statement. Corollary 3.2 (SPR optimality for f -divergences). For every f -divergence, the following hold. 1. Over all finite-output ε-LDP mechanisms, the optimum is attained by an SPR mechanism with at most k active outputs. 2. For any output budget 1 ≤ ℓ ≤ k, maxQ∈Qε,ℓ Df (Q⊤ p∥Q⊤ q) is attained by an SPR mechanism with at most ℓ active outputs.
3.2
Exact dynamic program
Corollary 3.2 reduces the search for an optimal mechanism to a search over LR-contiguous partitions of [k]. We exploit the additive decomposability of f -divergences across blocks to obtain an exact dynamic program.
7
For z ∈ Rk+ , let µ(z) := (q ⊤ z) f
1 ≤ a ≤ b ≤ k, let
⊤ p z be the column score associated with the chosen f -divergence. For q⊤ z
k µ[a : b] := µ 1 + (eε − 1)1{a ≤ i ≤ b} i=1 .
(12)
Proposition 3.3 (Dynamic program with an output budget). Fix 1 ≤ ℓ ≤ k. For 1 ≤ s ≤ ℓ and s ≤ i ≤ k, let F [s, i] be the maximum raw score over all partitions of [1 : i] into exactly s nonempty contiguous blocks. Then F [1, i] = µ[1 : i], and for s ≥ 2, n o F [s, i] = max F [s − 1, t] + µ[t + 1 : i] . (13) s−1≤t<i
The optimal ℓ-output utility is max
F [s, k]
1≤s≤ℓ eε + s − 1
.
Corollary 3.4 (Runtime). For an output budget 1 ≤ ℓ ≤ k, the optimal value and an optimal SPR mechanism can be computed in O(ℓk 2 ) time and O(ℓk) space. In particular, the unconstrained-output problem is obtained by taking ℓ = k, giving O(k 3 ) time and O(k 2 ) space. The proofs of Proposition 3.3 and Corollary 3.4, together with pseudocode for the algorithm, are given in Section 5.
3.3
Closed-form optimal mechanism for Eγ -divergences
For γ ≥ 1, define the Eγ - (or hockey-stick) divergence Eγ (P0 ∥P1 ) := sup P0 (A) − γP1 (A) ,
(14)
A⊆X
which corresponds to the convex function fγ (t) = (t − γ)+ , with γ = 1 recovering total variation. The Eγ -divergence has a direct testing interpretation. If a test decides P0 on an event A ⊆ Y, then M0 (Ac ) is its missed-detection probability and M1 (A) is its false-alarm probability. Therefore Eγ (M0 ∥M1 ) = 1 − inf {M0 (Ac ) + γM1 (A)}. A⊆Y
(15)
Maximizing Eγ is equivalent to minimizing this weighted testing risk: γ = 1 gives total variation, while γ > 1 captures asymmetric costs. Such asymmetry is common in privacy-sensitive decisions (rare-event detection, medical screening, fraud or abuse detection, and content moderation) where false alarms and missed detections need not have comparable costs. For the Eγ -divergences, the SPR dynamic program collapses to a closed form. Definition 3.5 (Generalized binary mechanism). With Sγ := {x ∈ X : P0 (x) ≥ γP1 (x)}, the generalized binary mechanism is the binary-output channel Qγ defined by eε , x ∈ Sγ , ε Qγ (0 | x) = 1 + e Qγ (1 | x) = 1 − Qγ (0 | x). (16) 1 , x∈ / S , γ 1 + eε Theorem 3.6 (Optimal Eγ mechanism). For every γ ≥ 1 and every ε-LDP mechanism Q with induced marginals M0 , M1 , ε e −1 1−γ Eγ (M0 ∥M1 ) ≤ E (P ∥P ) + . (17) γ 0 1 eε + 1 eε + 1 + The generalized binary mechanism Qγ attains (17) with equality, and therefore maximizes Eγ (M0 ∥M1 ) over Qε . 8
In the non-private problem, the event maximizing P0 (A) − γP1 (A) is the threshold set Sγ = {x ∈ X : P0 (x) ≥ γP1 (x)}, obtained by selecting exactly the points where P0 (x) − γP1 (x) ≥ 0. Theorem 3.6 states that privacy does not change this threshold: the optimal private mechanism applies binary randomized response to the bit 1{X ∈ Sγ }. Notably, Sγ does not depend on ε: privacy leaves the classical likelihoodratio threshold unchanged and privatizes only the resulting bit. This captures a private Neyman–Pearson lemma for the weighted-risk formulation. Since hockey-stick divergences also underlie privacy profiles and worst-case LDP contraction bounds [11, 2], this result identifies, for the fixed pair (P0 , P1 ), the ε-LDP channel that preserves the largest possible Eγ -separation. Zamanlooy et al. [9] (Theorem 3) established the upper bound (17); Theorem 3.6 shows that the generalized binary mechanism Qγ attains it. ThePargument is short: under Qγ , the contribution of the output 0 to Eγ (M0 ∥M1 ) is M0 (0) − γM1 (0) = x (P0 (x) − γP1 (x))Qγ (0 | x). Splitting this sum over Sγ and Sγc and using the Neyman–Pearson identity Eγ (P0 ∥P1 ) = P0 (Sγ ) − γP1 (Sγ ) yields exactly the right-hand side of (17). The full proof is given in Appendix D; the same appendix shows that the upper bound (17) can also be recovered directly from SPR optimality, by analyzing the contribution of each block of an LR-contiguous partition.
3.4
Other objectives: Rényi divergences and ℓr distance
SPR optimality applies to any objective maximized at extreme points of the joint-range polytope; the O(ℓk 2 ) dynamic program, however, requires an additive decomposition over contiguous blocks, as f divergences have. Rényi divergences fit the same framework via a monotone reduction to an f -divergence; for ℓr distance, the optimum coincides with the TV-optimal binary SPR mechanism. Proposition 3.7 (SPR optimality for Rényi divergences). For every fixed finite order α > 0, the SPR optimality result and the O(ℓk 2 ) dynamic program apply to maximization of Dα . Proof. The case α = 1 is KL divergence, an f -divergence. For α ̸= 1, Dα (u∥v) =
X 1 1−α log uα , y vy α−1 y
(18)
so maximizing Dα is equivalent to maximizing the f -divergence with f (t) = tα − 1 for α > 1 and f (t) = 1 − tα for 0 < α < 1; both are convex with f (1) = 0. Proposition 3.8 (Optimal mechanism for ℓr distance is binary). For any 1 ≤ r ≤ ∞ and any ε-LDP channel Q with at least two outputs, ∥Q⊤ p − Q⊤ q∥r ≤ 21/r tanh(ε/2) dTV (p, q),
21/∞ := 1.
(19)
The maximum is achieved by binary randomized response applied to S := {i ∈ [k] : pi ≥ qi }. Proof. Let ∆ := Q⊤ p − Q⊤ q and m := dTV (Q⊤ p, Q⊤ q). By the total-variation contraction for ε-LDP channels, m ≤ tanh(ε/2) dTV (p, q).
(20)
The positive entries of ∆ sum to m, and the negative entries have absolute values summing to m. Hence, for 1 ≤ r < ∞, ∥∆∥rr ≤ mr + mr = 2mr ,
(21)
∥∆∥r ≤ 21/r tanh(ε/2) dTV (p, q).
(22)
therefore,
9
For r = ∞, the same argument gives ∥∆∥∞ ≤ tanh(ε/2) dTV (p, q).
(23)
For tightness, let S = {i ∈ [k] : pi ≥ qi } and apply binary randomized response to 1{i ∈ S}. Since p(S) − q(S) = dTV (p, q), the output difference vector is (a, −a) where a := tanh(ε/2) dTV (p, q). Its ℓr norm is 21/r a, with 21/∞ := 1.
3.5
Numerical illustration
Figure 1 illustrates SPR optimality on the KL utility for ε-LDP mechanisms. We compare the SPR dynamic program (Algorithm 1) against the closed-form binary mechanism, k-ary randomized response, and (where tractable) the Kairouz–Oh–Viswanath staircase linear program [8], on T = 100 Dirichlet(1k ) pairs (P0 , P1 ) at each ε on a uniform grid in [0, 10]. For k = 6 the LP is tractable and the SPR DP curve coincides with it to numerical precision (≤ 6.1 × 10−14 across the T × 101 grid), validating Theorem 3.1 empirically. For k = 100 the LP has 2100 ≈ 1.27 × 1030 variables and is omitted, while the SPR DP completes the entire sweep in under 20 seconds on a laptop. The binary mechanism plateaus and k-ary RR is uninformative for small ε; the SPR optimum interpolates between them across the full privacy range. Full setup, bootstrap confidence bands, and runtime details are reported in Appendix E.
4
Geometry of SPR optimality
This section assembles the geometric ingredients behind the SPR optimality theorem (Theorem 3.1) and its f -divergence corollary (Corollary 3.2). The argument has three steps, each carried out by one proposition: every extreme image point can be realized by a staircase channel whose active columns are LR-contiguous (§4.1); every such staircase channel lies in the convex hull of SPR mechanisms (§4.2); and deterministically merging active outputs of an SPR mechanism never produces a new extreme point (§4.3). Section 4.4 chains these three propositions to prove Theorem 3.1 and Corollary 3.2. Figure 3 previews the resulting polytope for a representative (p, q) at k = 5, ℓ = 2, ε = 2.
4.1
Extreme refinements: from extreme points to LR-contiguous staircase channels
We first show that every extreme image point can be realized, up to deterministic post-processing, by a staircase channel whose active columns respect the likelihood-ratio order. Proposition 4.1 (Extreme points admit LR-contiguous staircase refinements). If (u, v) ∈ Rℓ (p, q) is an e ∈ Qε,m , and a deterministic map extreme point, then there exist an integer m ≥ 1, a staircase channel Q τ : [m] → [ℓ] such that e ⊤ p, (τ ◦ Q) e ⊤q , (u, v) = (τ ◦ Q)
(24)
e has an LR-contiguous high set. and every active column of Q The proof is given in Appendix A.4. Starting from an arbitrary extreme image point, we refine it to a staircase channel and then show that any noncontiguous active column creates a local obstruction that contradicts extremality. This step adapts the joint-range perturbation idea of Pensia et al. [3]: we rule out such a column by producing two feasible induced pairs whose midpoint is the original pair.
10
{1, 2, 3, 4, 5} [1]
1.2
{1, 2, 3, 4} | {5} [1,2] (interior) 1.0
hQ> q, e1 i (probability output 1 under q)
{1, 2, 3} | {4, 5} [1,2] {1, 2} | {3, 4, 5} [1,2]
0.8
{1} | {2, 3, 4, 5} [2,1] (interior)
0.6
0.4
0.2
{1, 2} | {3, 4, 5} [2,1]
{1} | {2, 3, 4, 5} [1,2] (interior)
{1, 2, 3} | {4, 5} [2,1]
0.0
−0.2
{1, 2, 3, 4, 5} [2]
{1, 2, 3, 4} | {5} [2,1] (interior)
SPR-induced extreme point SPR-induced interior point (dominated) predicted polytope (Thm. 3.1)
−0.2
0.0
0.2
0.4
0.6
0.8
1.0
1.2
hQ> p, e1 i (probability output 1 under p)
Figure 3: Geometry of SPR optimality for k = 5, ℓ = 2, ε = 2, with p = (0.04, 0.09, 0.22, 0.47, 0.18) and q = (0.25, 0.49, 0.13, 0.10, 0.03). The joint range R2 (p, q) = {(Q⊤ p, Q⊤ q) : Q ∈ Qε,2 } is the shaded hexagon, equal to the convex hull of the 2(k − 1) + 2 = 10 SPR-induced candidate points (Theorem 3.1). Since ℓ = 2, the plotted coordinates determine the full pair (Q⊤ p, Q⊤ q): the omitted coordinates are their complements. Thus this two-dimensional plot is a lossless representation of R2 (p, q). Each candidate is the image of one LR-contiguous partition into two blocks together with a block-to-output assignment [a, b] meaning B1 → a, B2 → b, plus the two constant s = 1 mechanisms at (0, 0) and (1, 1). Six of the ten are extreme (filled red); the other four are dominated (hollow red): they are SPR mechanisms but sit strictly inside the polytope as convex combinations of others, so by Corollary 3.2 they cannot maximize any f -divergence. Whether a given SPR mechanism is extreme depends on (p, q) and ε.
11
4.2
Convex hull of SPR mechanisms
Once the active columns are LR-contiguous, the staircase channel decomposes into a convex combination of SPR mechanisms. Proposition 4.2 (Convex hull of SPR channels). Let m ≥ 1, and let Q ∈ Qε,m be a staircase channel. Assume every active column of Q has an LR-contiguous high set, with active constant columns represented b (1) , . . . , Q b (N ) ∈ Qε,m , by the high set [k]. Then there exist LR-contiguous partitions π1 , . . . , πN , channels Q PN and coefficients β1 , . . . , βN > 0 with t=1 βt = 1 such that Q=
N X
b (t) , βt Q
(25)
t=1
b (t) is obtained from the SPR mechanism Qπt by relabeling its active outputs where, for each t, the channel Q into [m] and padding the remaining columns with zeros. The proof is deferred to Appendix B. It rewrites Q as a weighted family of LR-contiguous intervals, uses the row-sum condition to show that every row sees the same total interval weight, and then peels this weighted interval system into layers, each layer being a partition of [k]. Each layer yields an SPR mechanism on the same output alphabet after relabeling and zero-padding. This peeling step can be viewed as a weighted flow-decomposition argument [12] specialized to interval families.
4.3
Nontrivial coarsenings are not extreme
Finally, we show that deterministically merging active outputs of an SPR mechanism does not create new extreme points. Proposition 4.3 (Nontrivial coarsenings are not extreme). Let π = (B1 , . . . , Bs ) be an LR-contiguous partition of [k], let Qπ ∈ Qε,s be the associated SPR mechanism, and let τ : [s] → [ℓ] be deterministic. If t := |τ ([s])| satisfies 1 < t < s, then the image point (τ ◦ Qπ )⊤ p, (τ ◦ Qπ )⊤ q ∈ Rℓ (p, q) (26) is not an extreme point of Rℓ (p, q). The proof is deferred to Appendix C. The key observation is that such a coarsened image decomposes into a randomized-response point on the coarser partition induced by τ , together with a hypothesis-independent remainder coming from an input-independent channel. This gives a nontrivial convex decomposition inside Rℓ (p, q).
4.4
Proof of the SPR theorem and its f -divergence corollary
Putting these three propositions together gives the main geometric statement: Theorem 3.1. Proof of Theorem 3.1. Let (u, v) ∈ Rℓ (p, q) be extreme. By Proposition 4.1, there exist m ≥ 1, a staircase e ∈ Qε,m whose active columns are LR-contiguous, and a deterministic map τ : [m] → [ℓ] such channel Q e ⊤ p, (τ ◦ Q) e ⊤ q . By Proposition 4.2, Q e = PN βt Q b (t) , with βt > 0 and PN βt = 1, that (u, v) = (τ ◦ Q) t=1 t=1 b (t) is a relabeled and zero-padded SPR mechanism. Applying τ and taking induced marginals where each Q gives (u, v) =
N X t=1
b (t) )⊤ p, (τ ◦ Q b (t) )⊤ q . βt (τ ◦ Q 12
(27)
Since (u, v) is extreme, every term with βt > 0 must already equal (u, v). Fix such a t. b (t) has only one active output, then its induced pair is realized by the one-block partition π = ([k]), If τ ◦ Q b (t) viewed as an ℓ-output channel by relabeling its unique active output and padding zeros. Otherwise τ ◦ Q has more than one active output. Since its induced pair is (u, v) and hence extreme, Proposition 4.3 b (t) . Thus τ ◦ Q b (t) differs from Q b (t) only by relabeling implies that τ does not merge two active outputs of Q active outputs and padding zeros. In either case, (u, v) is induced by an SPR mechanism, up to relabeling and zero-padding. The extreme-point characterization converts into optimal mechanisms, both with and without a communication constraint, via Corollary 3.2. Proof of Corollary 3.2. Fix any ℓ′ ≥ 1 and any Q ∈ Qε,ℓ′ , and set (u, v) = (Q⊤ p, Q⊤ q) ∈ Rℓ′ (p, q). Since Rℓ′ (p, q) is a compact convex polytope, write (u, v) as a convex combination of its extreme points: PN PN (u, v) = t=1 λt (u(t) , v (t) ) for λt ≥ 0, t=1 λt = 1. By convexity of Df , Df (u∥v) ≤
N X t=1
λt Df (u(t) ∥v (t) ) ≤ max Df (u(t) ∥v (t) ), t
(28)
so some extreme point (u(t) , v (t) ) satisfies Df (u(t) ∥v (t) ) ≥ Df (u∥v). By Theorem 3.1, that extreme point is induced by an SPR mechanism with at most min(ℓ′ , k) active outputs. For the unconstrained claim, take ℓ′ arbitrary: every finite-output ε-LDP mechanism is matched or improved by an SPR mechanism with at most k active outputs, and any such SPR mechanism is itself a feasible finite-output mechanism. Hence the unconstrained finite-output optimum is attained among SPR mechanisms with at most k active outputs. For the output-constrained claim, take ℓ′ = ℓ: every ℓ-output mechanism is matched or improved by an SPR mechanism with at most ℓ active outputs, and any such SPR mechanism can be viewed as an element of Qε,ℓ by padding zero columns.
5
Exact dynamic program
Fix an f -divergence objective and an output budget 1 ≤ ℓ ≤ k. By Corollary 3.2, it is enough to optimize over LR-contiguous partitions of [k] into at most ℓ nonempty blocks. The unconstrained finite-output problem is the case ℓ = k. We now use this partition structure to obtain an O(ℓk 2 ) dynamic program, and hence an O(k 3 ) algorithm in the unconstrained case. Section 5.3 gives a pseudocode version.
5.1
Interval scores and DP recurrence
For z ∈ Rk+ , let µ(z) := (q ⊤ z) f
1 ≤ a ≤ b ≤ k, let
⊤ p z be the column score associated with the chosen f -divergence. For q⊤ z
k µ[a : b] := µ 1 + (eε − 1)1{a ≤ i ≤ b} i=1 .
(29)
Thus µ[a : b] is the contribution of the unnormalized staircase pattern with high set [a : b]. If π = (B1 , . . . , Bs ) is an LR-contiguous partition of [k] into s nonempty blocks, then each output column of Qπ is the corresponding unnormalized staircase pattern divided by eε + s − 1. Therefore Ps µ(Bt ) π ⊤ π ⊤ Df (Q ) p∥(Q ) q = εt=1 , (30) e +s−1
where µ(Bt ) = µ[a : b] when Bt = [a : b]. Thus, for each fixed s ∈ {1, . . . , ℓ}, it is enough to maximize the numerator over all partitions of [k] into s nonempty contiguous blocks. This yields Proposition 3.3. 13
Proof of Proposition 3.3. The base case is immediate. For the recurrence, take an optimal partition of [1 : i] into s contiguous blocks, and let its last block be [t + 1 : i]. Then the prefix [1 : t] must already be partitioned optimally into s − 1 contiguous blocks; otherwise we could replace it by a better one and improve the whole partition. This gives the recurrence. The last equation follows because for fixed s the denominator eε + s − 1 is constant.
5.2
Runtime, output constraint, and traceback
Proof of Corollary 3.4. Sorting the input alphabet by likelihood ratio takes O(k log k) time, which is Pi Pi dominated by the O(ℓk 2 ) DP fill. Let Pi := j=1 pj and Qi := j=1 qj with P0 = Q0 = 0. Then for any interval [a : b], 1 + (eε − 1)(Pb − Pa−1 ) µ[a : b] = (1 + (eε − 1)(Qb − Qa−1 )) f . (31) 1 + (eε − 1)(Qb − Qa−1 ) Thus each interval score can be evaluated in O(1) time from the prefix sums, without precomputing or storing the O(k 2 ) possible scores. The DP table F [s, i] has O(ℓk) states, and each state checks O(k) split points, evaluating the needed interval score on demand from the prefix sums. Hence filling the table takes O(ℓk 2 ) time. The prefix sums use O(k) space and the DP table uses O(ℓk) space, so the total space is O(ℓk). To recover an optimal mechanism, first choose s⋆ ∈ arg max
F [s, k]
1≤s≤ℓ eε + s − 1
.
Then trace backward from (s⋆ , k): at state (s, i), choose any n o t ∈ arg max F [s − 1, t] + µ[t + 1 : i] , s−1≤t<i
(32)
(33)
record the block [t + 1 : i], and continue from (s − 1, t). The final block is [1 : i]. This traceback uses only the stored F table and the prefix sums, so it does not change the O(ℓk) space bound. It adds at most O(ℓk) time, since at most ℓ states are traced back and each recomputes one maximization over O(k) split points. Thus the dominant running-time cost remains the O(ℓk 2 ) DP fill, which becomes O(k 3 ) when ℓ = k.
14
5.3
Pseudocode
Algorithm 1: Optimal SPR mechanism via dynamic programming Input: Distributions p, q ∈ ∆k , privacy level ε > 0, output budget 1 ≤ ℓ ≤ k, convex generator f with f (1) = 0. Output: Optimal value V ⋆ , optimal LR-contiguous partition π ⋆ = (B1 , . . . , Bs⋆ ), and the associated SPR ⋆ mechanism Qπ . // Stage 1: sort by likelihood ratio and compute prefix sums Let σ be a permutation of [k] with pσ(1) /qσ(1) ≤ · · · ≤ pσ(k) /qσ(k) Relabel so that pi ← pσ(i) and qi ← qσ(i) for i = 1, . . . , k Set P0 ← 0, Q0 ← 0 for i = 1, . . . , k do Pi ← Pi−1 + pi Qi ← Qi−1 + qi // Interval-score oracle: O(1) from prefix sums Function IntervalScore(a, b): ∆P ← Pb − Pa−1 ∆Q ← Qb − Qa−1 1 + (eε − 1)∆P return 1 + (eε − 1)∆Q f 1 + (eε − 1)∆Q // Stage 2: fill the DP table F [s, i] Initialize F [s, i] ← −∞ for all 1 ≤ s ≤ ℓ, 1 ≤ i ≤ k for i = 1, . . . , k do F [1, i] ← IntervalScore(1, i)
for s = 2, . . . , ℓ do for i = s, . . . , k do F [s, i] ← max F [s − 1, t] + IntervalScore(t + 1, i) s−1≤t<i
// Stage 3:
select the optimal block count and value F [s, k] s⋆ ← arg max ε 1≤s≤ℓ e + s − 1 F [s⋆ , k] V⋆ ← ε e + s⋆ − 1 // Stage 4: traceback to recover the partition (in sorted order) i←k for s = s⋆ , s⋆ − 1,. . . , 2 do t⋆ ← arg max F [s − 1, t] + IntervalScore(t + 1, i) s−1≤t<i
es ← [t⋆ + 1 : i] B i ← t⋆ e1 ← [1 : i] B // Undo the sort to express blocks on the original alphabet for s = 1, . . . , s⋆ do es } Bs ← {σ(j) : j ∈ B π ⋆ ← (B1 , . . . , Bs⋆ )
// Stage 5: instantiate the SPR mechanism for s ∈ [s⋆ ], x ∈ [k] do ⋆ 1 + (eε − 1)1{x ∈ Bs } Qπ (s | x) ← eε + s ⋆ − 1 ⋆ ⋆ π⋆ return V , π , Q
15
6
Conclusion and limitations
We showed that the exact mechanism-design problem for binary testing under local privacy has a much smaller structure than the general staircase formulation suggests. After sorting by likelihood ratio, optimal mechanisms can be chosen by partitioning the ordered alphabet into contiguous blocks and applying randomized response to the block label (Section 4), yielding an exact polynomial-time dynamic program (Section 5). For Eγ -divergences this collapses to a closed-form binary mechanism, and the same machinery extends to Rényi divergences and ℓr distance objectives (Sections 3.3–3.4). Our characterization is specific to simple binary hypothesis testing under pure, non-interactive ε-LDP on a finite alphabet. Extending the SPR geometry to multi-hypothesis or composite testing, approximate or Rényi local privacy, and interactive protocols remains open. On the algorithmic side, the O(ℓk 2 ) dynamic program relies on the additive block decomposition of f -divergences; finding comparably efficient exact algorithms for broader quasi-convex objectives, such as Chernoff information, is an interesting direction. Another natural question is how to adapt the mechanism-design results when the hypotheses P0 , P1 are not known exactly and must be estimated or specified through uncertainty classes.
16
References [1] John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 429–438, 2013. doi: 10.1109/FOCS.2013.53. [2] Shahab Asoodeh, Maryam Aliakbarpour, and Flavio P. Calmon. Local differential privacy is equivalent to contraction of eγ -divergence, 2021. URL https://arxiv.org/abs/2102.01258. [3] Ankit Pensia, Amir R. Asadi, Varun Jog, and Po-Ling Loh. Simple binary hypothesis testing under local differential privacy and communication constraints. IEEE Transactions on Information Theory, 71(1):592–617, 2025. doi: 10.1109/TIT.2024.3461361. [4] Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793–826, 2011. doi: 10.1137/090756090. URL https://doi.org/10.1137/090756090. [5] Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69, 1965. ISSN 01621459, 1537274X. URL http://www.jstor.org/stable/2283137. [6] John C. Duchi and Feng Ruan. The right complexity measure in locally private estimation: It is not the fisher information, 2020. URL https://arxiv.org/abs/1806.05756. [7] Shahab Asoodeh and Huanyu Zhang. Contraction of locally differentially private mechanisms. IEEE Journal on Selected Areas in Information Theory, 5:385–395, 2024. doi: 10.1109/JSAIT.2024.3397305. [8] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. J. Mach. Learn. Res., 17(1):492–542, January 2016. ISSN 1532-4435. [9] Behnoosh Zamanlooy, Shahab Asoodeh, Mario Diaz, and Flavio P. Calmon. Eγ -mixing time. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 3474–3479, 2024. doi: 10.1109/ISIT57864.2024.10619250. [10] J.N. Tsitsiklis. Extremal properties of likelihood-ratio quantizers. IEEE Transactions on Communications, 41(4):550–558, 1993. doi: 10.1109/26.223779. [11] Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy profiles and amplification by subsampling. Journal of Privacy and Confidentiality, 10(1), 2020. doi: 10.29012/jpc.726. [12] Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
17
A
Extreme points admit LR-contiguous staircase refinements
We prove Proposition 4.1 under the assumption that inputs with the same likelihood ratios have been merged, i.e., that the likelihood ratios are strictly increasing in the LR order. Let (u, v) ∈ Rℓ (p, q) be an extreme point. We will show that (u, v) is realized, up to deterministic post-processing, by a staircase channel whose active columns are LR-contiguous. The proof has three steps. First, we refine an arbitrary channel realizing (u, v) into a staircase channel. Second, we show that if one of its active columns is not LR-contiguous, then on some LR-ordered triple it creates a forbidden local configuration. Third, we use a perturbation argument to show that each such configuration yields a nontrivial midpoint decomposition of (u, v), contradicting extremality. Figure 4 traces the logical flow of the proof: starting from an extreme image pair, we refine to a staircase (Lemma A.1), assume for contradiction that some active column has a non-contiguous high set, apply the dichotomy of Lemma A.6, perturb in either branch (Lemmas A.8 and A.9), push the perturbations back through τ , and reach a contradiction with extremality.
A.1
Staircase refinement
The next lemma shows that any fixed-output ε-LDP channel can be refined into a staircase channel that merges back to the original one under a deterministic post-processing map. This lets us work at the staircase level and later transfer a contradiction back to the original image point. Example A.3 below illustrates the construction on a small 5 × 2 channel.
Lemma A.1 (Nested staircase refinement). Let Q ∈ Rk×ℓ be a row-stochastic ε-LDP channel, where + e e ∈ Rk×m ε > 0. Then there exist a staircase ε-LDP channel Q with output alphabet Ye = [m], e and a + e deterministic map τ : Y → [ℓ] such that X e ỹ) Q(i, y) = Q(i, (i ∈ [k], y ∈ [ℓ]). ỹ:τ (ỹ)=y
Moreover, for each y ∈ [ℓ], the high sets of the fine columns merged into y are nested. Proof. Zero columns need no refinement, so fix a nonzero column Q(·, y) of Q. Because Q is ε-LDP and this column is nonzero, every entry in it is positive. Let θ := min Q(i, y) > 0 i∈[k]
be its smallest entry. Then every entry in this column lies between θ and eε θ. We now show that this column can be written as a sum of staircase columns with nested high sets. Write each entry as Q(i, y) = θ 1 + (eε − 1)ui ,
ui ∈ [0, 1],
where ui :=
Q(i, y) − θ ∈ [0, 1]. (eε − 1)θ
Here, ui records how much of the maximum possible “extra above the minimum” row i receives. If ui = 0 for all i, then the column is already constant: Q(i, y) = θ for all i. In that case we define a single fine column by e (y, 0)) := θ Q(i, 18
(i ∈ [k]),
Consider (u, v) ∈ Rℓ (p, q) extreme, realized by some Q ∈ Qε,ℓ Lemma A.1
e post-processed back to Q Staircase refinement Q, by a deterministic τ , with nested per-output high sets
for contradiction
e has Suppose some active column of Q non-contiguous high set: pattern (1, 0, 1) on a triple a < b < c
Lemma A.6 3-cycle (1, 0, 1) + (1, 1, 0) + (0, 1, 1)
Zigzag (1, 0, 1) + (0, 1, 0)
Lemma A.8
Lemma A.9
e+ , Q e − , differing from Q e only Construct feasible Q on the involved columns, with distinct image pair e image pair whose midpoint is Q’s apply τ
e ± by τ yields feasible ε-LDP Q± Post-processing Q with distinct image pair whose midpoint is still (u, v)
(u, v) is a nontrivial midpoint of two points in Rℓ (p, q) contradicts extremality
e is LR-contiguous Every active column of Q
Figure 4: Logical structure of the proof of Proposition 4.1. Blue boxes are established facts; the red dashed arrow marks the assumption-for-contradiction trail; yellow boxes are the two forbidden configurations; the green box is the conclusion.
19
and there is nothing further to do for this y. Otherwise, let 0 = λ0 < λ1 < · · · < λL ≤ 1 be the distinct values taken by the ui ’s. For each level t = 1, . . . , L, let Ht := {i ∈ [k] : ui ≥ λt }. Then H1 ⊇ H2 ⊇ · · · ⊇ HL , because rows with a larger boost automatically belong to all smaller-boost groups. Each ui is obtained by adding the jump sizes λt − λt−1 for exactly those sets Ht that contain row i: ui =
L X t=1
(λt − λt−1 )1{i ∈ Ht }.
Now let H0 = ∅, set αt := θ(λt − λt−1 )
(t = 1, . . . , L),
and α0 := θ(1 − λL ). Substituting the expression for ui into Q(i, y) = θ 1 + (eε − 1)ui gives Q(i, y) =
L X t=0
αt 1 + (eε − 1)1{i ∈ Ht } .
For this fixed y, define the corresponding fine columns by e (y, t)) := αt 1 + (eε − 1)1{i ∈ Ht } Q(i,
(t = 0, . . . , L).
Then Q(i, y) =
L X
e (y, t)) Q(i,
t=0
(i ∈ [k]). (y)
Apply the same construction to every nonzero column of Q, using for each column y its own levels λt , (y) (y) e Let τ send each sets Ht , and coefficients αt . The resulting fine columns form the refined channel Q. fine column back to the original column it came from. Thus, X e ỹ) Q(i, y) = Q(i, (i ∈ [k], y ∈ [ℓ]). ỹ:τ (ỹ)=y
Each fine column has the form α 1 + (eε − 1)1{i ∈ H} for some α ≥ 0 and some set H ⊆ [k], so it has staircase form. Since within each original column the fine columns sum back to that column, summing e equals the corresponding row sum of Q; hence Q e over all original columns shows that each row sum of Q is row-stochastic. Finally, for a fixed original output y, the fine columns coming from Q(·, y) have high (y) sets among the sets Ht , and these sets are nested. 20
Remark A.2. In the proof of Lemma A.1, we allow constant fine columns to be written with high set ∅, since this makes the decomposition clearer. Elsewhere in the paper, when discussing staircase channels abstractly, we use the convention that an active constant column is represented with high set [k]. These are just two equivalent representations of the same constant column, and the choice here is purely for notational convenience. Example A.3 (Staircase refinement of a 5 × 2 channel). Take ε = 1, so eε = e, and consider the 5 × 2 mechanism 0.3124 0.6876 0.4017 0.5983 Q≈ 0.2865 0.7135 . 0.3588 0.6412 0.4279 0.5721 Up to rounding, each row sums to 1 and each column has max/min ratio at most eε , so Q is ε-LDP; this is a generic non-staircase example. We decompose each output column into staircase pieces with nested high sets. For the first output, ε 0.3124 1 e 1 1 1 0.4017 1 eε eε eε 1 Q(·, y1 ) ≈ 0.2865 = 0.2042 1 + 0.0151 1ε + 0.0270 1ε + 0.0250 1 + 0.0152 1 . 0.3588 1 e e 1 1 ε ε ε 0.4279 1 e e e eε The high sets are {1, 2, 4, 5} ⊃ {2, 4, 5} ⊃ {2, 5} ⊃ {5}.
For the second output, ε ε ε 0.6876 1 e e e 1 0.5983 1 eε 1 1 1 ε ε ε ε Q(·, y2 ) ≈ 0.7135 = 0.4898 1 + 0.0152 eε + 0.0250 eε + 0.0270 e + 0.0151 e . 0.6412 1 e e 1 1 0.5721 1 1 1 1 1 The high sets are {1, 2, 3, 4} ⊃ {1, 3, 4} ⊃ {1, 3} ⊃ {3}. Refined channel.
Stacking the staircase columns from both outputs gives e ≈ [ A | B ], Q
where A holds the y1 staircase columns and B holds the y2 staircase columns: 0.2042 0.0151 eε 0.0270 0.0250 0.0152 0.2042 0.0151 eε 0.0270 eε 0.0250 eε 0.0152 , 0.2042 0.0151 0.0270 0.0250 0.0152 A≈ 0.2042 0.0151 eε 0.0270 eε 0.0250 0.0152 0.2042 0.0151 eε 0.0270 eε 0.0250 eε 0.0152 eε 0.4898 0.0152 eε 0.4898 0.0152 eε ε B≈ 0.4898 0.0152 eε 0.4898 0.0152 e 0.4898 0.0152
0.0250 eε 0.0250 0.0250 eε 0.0250 eε 0.0250
0.0270 eε 0.0270 0.0270 eε 0.0270 0.0270
0.0151 0.0151 0.0151 eε . 0.0151 0.0151
Summing the columns of A recovers Q(·, y1 ), and summing the columns of B recovers Q(·, y2 ), so Q is e by deterministic post-processing. obtained from Q 21
A.2
Staircase obstructions
We now identify the local staircase configurations that obstruct LR-contiguity. We first show that if a staircase refinement contains a noncontiguous pattern (101) on some LR-ordered triple, then on that same triple it must contain one of two forbidden configurations. In the next subsection, we show that either configuration yields a nontrivial midpoint decomposition and hence contradicts extremality. Definition A.4 (The Zigzag Configuration). Let Q ∈ Rk×m be an ε-LDP staircase channel with ε > 0, + and assume the inputs [k] are ordered in strictly increasing likelihood ratio. We say that Q contains a zigzag configuration if there exist three (LR-ordered) rows a < b < c and two distinct columns j = ̸ j ′ such that for some θj , θj ′ > 0, (Q(a, j), Q(b, j), Q(c, j)) = (eε θj , θj , eε θj ), and (Q(a, j ′ ), Q(b, j ′ ), Q(c, j ′ )) = (θj ′ , eε θj ′ , θj ′ ). Equivalently, restricted to rows {a, b, c}, column j has pattern (101) and column j ′ has pattern (010). In matrix form. The entries shown sit at rows a < b < c and columns j, j ′ as in the definition above; remaining entries (denoted · · · ) are arbitrary: ··· ··· ··· ··· ··· · · · eε θj · · · θj ′ · · · · · · · · · · · · ··· · · · θj · · · eε θj ′ · · · Q= · · · . · · · · · · · · · · · · · · · · · · eε θj · · · θj ′ · · · ··· ··· ··· ··· ··· Definition A.5 (The 3-Cycle Configuration). Let Q ∈ Rk×m be an ε-LDP staircase channel with ε > 0, + and assume the inputs [k] are ordered in strictly increasing likelihood ratio. We say that Q contains a 3-cycle configuration if there exist three (LR-ordered) rows a < b < c and three distinct columns j1 , j2 , j3 such that for some θj1 , θj2 , θj3 > 0, (Q(a, j1 ), Q(b, j1 ), Q(c, j1 )) = (eε θj1 , θj1 , eε θj1 ), (Q(a, j2 ), Q(b, j2 ), Q(c, j2 )) = (eε θj2 , eε θj2 , θj2 ), and (Q(a, j3 ), Q(b, j3 ), Q(c, j3 )) = (θj3 , eε θj3 , eε θj3 ). Equivalently, restricted to rows {a, b, c}, the three columns realize the three patterns (101), (110), and (011) (in any column order). In matrix form. The entries shown sit at rows a < b < c and columns j1 , j2 , j3 as in the definition above; remaining entries (denoted · · · ) are arbitrary: ··· ··· ··· ··· ··· ··· ··· · · · eε θj1 · · · eε θj2 · · · θj3 · · · · · · ··· ··· ··· ··· ··· · · · θj1 · · · eε θj2 · · · eε θj3 · · · Q= · · · . · · · · · · · · · · · · · · · · · · · · · ε · · · eε θj1 · · · θj2 · · · e θj3 · · · ··· ··· ··· ··· ··· ··· ··· 22
To prove LR-contiguity, it is enough to rule out the local pattern (101) on LR-ordered triples. Indeed, a staircase column has noncontiguous high set if and only if there exist rows a < b < c on which the column has pattern (101). The next lemma shows that any such (101) pattern forces a more structured forbidden configuration on the same triple. Lemma A.6 (Any 101 triple forces a zigzag configuration or 3-cycle configuration on that triple). Let Q ∈ Rk×m be a row-stochastic staircase ε-LDP channel with ε > 0, and fix a staircase representation of + its columns: for each y ∈ [m], choose θy ≥ 0 and Hy ⊆ [k] such that Q(i, y) = θy 1 + (eε − 1)1{i ∈ Hy } . Fix rows a < b < c. For each s ∈ {0, 1}3 , let ws :=
m X
θy 1
y=1
1{a ∈ Hy }, 1{b ∈ Hy }, 1{c ∈ Hy } = s .
If w101 > 0, then either w010 > 0, or both w110 > 0 and w011 > 0. Proof. For i ∈ {a, b, c}, define X
hi :=
θy .
y:i∈Hy
Since Q is row-stochastic, 1=
m X y=1
Q(i, y) =
m X y=1
θy + (eε − 1)
X
θy ,
y:i∈Hy
so ha = hb = hc . Also, ha = w100 + w101 + w110 + w111 , hb = w010 + w011 + w110 + w111 , hc = w001 + w011 + w101 + w111 . Hence w100 + w101 = w010 + w011 ,
(34)
w001 + w101 = w010 + w110 .
(35)
Assume w101 > 0. If w010 > 0, we are done. If w010 = 0, then w011 = w100 + w101 > 0,
w110 = w001 + w101 > 0
by (34) and (35). This gives the claimed alternative.
23
A.3
Perturbation lemmas
The next step is to show that each forbidden local configuration makes the induced point in the joint range non-extreme. The general strategy is to build small feasible perturbations of the staircase channel that preserve row-stochasticity and ε-LDP, and then choose them so that the original point becomes a nontrivial midpoint of two distinct feasible image points. We first record a simple perturbation criterion for staircase channels. Lemma A.7 (Perturbation criterion for staircase channels). Let Q ∈ Rk×m be a row-stochastic staircase + ε-LDP channel with ε > 0. Let D ∈ Rk×m be supported on active columns of Q, and assume D1 = 0. Assume also that for every modified column y, every row h that is high in column y, and every row ℓ that is low in column y, (36)
Dh,y ≤ eε Dℓ,y . Then Q + γD is row-stochastic and ε-LDP for all sufficiently small γ > 0.
Proof. Since D1 = 0, every row sum of Q + γD equals the corresponding row sum of Q, hence equals 1. Because D is supported on active columns and every active staircase column is strictly positive entrywise, each modified entry of Q starts strictly positive. Since there are finitely many modified entries, there exists γ0 > 0 such that Q + γD ≥ 0 for all 0 < γ < γ0 . Fix a modified column y. In a staircase column, every entry is either θy or eε θy for some θy > 0. Thus:
• if both rows are high, or both are low, then the two entries are equal, so the ordered privacy inequality is Qi,y ≤ eε Qi′ ,y , which is strict because ε > 0; • if row h is high and row ℓ is low, then Qh,y = eε Qℓ,y , so this is the only potentially tight ordered privacy inequality; • if row ℓ is low and row h is high, then Qℓ,y < eε Qh,y , so that ordered inequality is also strict. Therefore it is enough to check the high-to-low pairs. For such a pair, Qh,y = eε Qℓ,y , so after perturbation we get Qh,y + γDh,y ≤ eε Qℓ,y + γDℓ,y
by (36). All other ordered privacy inequalities are strict at γ = 0, so by continuity they remain valid for all sufficiently small γ > 0. Since there are only finitely many such inequalities, shrinking γ0 if necessary gives a single γ0 > 0 for which every privacy inequality holds for all 0 < γ < γ0 . Therefore Q + γD is row-stochastic and ε-LDP for all sufficiently small γ > 0. 24
The next lemma adapts the midpoint perturbation argument used in the proof of Theorem 6 of [3]. There, Pensia et al. rule out a non-threshold deterministic channel by showing that the induced point in the fixed-output joint range is not extreme. We use the same perturbative idea here for staircase ε-LDP channels containing a zigzag configuration. Lemma A.8 (Zigzag configuration implies non-extremality in the joint range). Let p, q ∈ ∆k be in reduced strict extended likelihood-ratio order: all input symbols with pi = qi = 0 have been deleted, equal extended likelihood ratios have been merged, and 0 ≤ r1 < r2 < · · · < rk ≤ ∞,
ri :=
pi , qi
with the convention that pi /0 = ∞ when pi > 0. Let Q ∈ Rk×m be a row-stochastic staircase ε-LDP + channel with ε > 0. If Q contains a zigzag configuration, then the induced point (Q⊤ p, Q⊤ q) is not an extreme point of Rm (p, q) := {(T ⊤ p, T ⊤ q) : T ∈ Rk×m is row-stochastic and ε-LDP}. + Equivalently, there exist row-stochastic ε-LDP channels Q′ , Q′′ ∈ Rk×m such that + (Q⊤ p, Q⊤ q) = 12 (Q′⊤ p, Q′⊤ q) + 12 (Q′′⊤ p, Q′′⊤ q), and (Q′⊤ p, Q′⊤ q) ̸= (Q′′⊤ p, Q′′⊤ q). Moreover, the channels Q′ and Q′′ may be chosen so that they differ from Q only in the two columns participating in the zigzag configuration. Proof. Let a < b < c and j = ̸ j ′ witness the zigzag configuration, so that on rows (a, b, c) the columns j and j ′ have patterns 101,
010.
Let ej , ej ′ be the standard basis vectors in Rm . Since the likelihood ratios are strictly ordered and a < b < c, the rows a and b have finite likelihood ratio, hence qa , qb > 0. The row c may have finite likelihood ratio, in which case qc > 0, or it may be the unique infinite-likelihood-ratio endpoint, in which case qc = 0 and pc > 0. Define A, B ∈ Rk×m by
qa , qb
Aa,j = −1,
Aa,j ′ = 1,
Ab,j =
Bb,j = qc ,
Bb,j ′ = −qc ,
Bc,j = −qb ,
··· +1 ··· qa − qb ··· 0 ···
··· · · · · · · B= · · · · · · · · · ···
Ab,j ′ = −
qa , qb
Bc,j ′ = qb ,
and all other entries equal to 0. Equivalently, ··· · · · · · · A = · · · · · · · · · ···
··· −1 ··· qa + qb ··· 0 ···
··· ··· ··· ···
··· ··· ···
··· · · · · · · · · · , · · · · · · ··· 25
··· 0 ··· +qc ··· −qb ···
··· ··· ··· ··· ··· ··· ···
··· 0 ··· −qc ··· +qb ···
··· · · · · · · · · · . · · · · · · ···
When qc > 0, this B is exactly qc times the original finite-ratio perturbation with entries 1, −1, −qb /qc , qb /qc . When qc = 0, it reduces to the endpoint perturbation supported only on row c. Both A and B are supported on the active columns j, j ′ and satisfy A1 = 0,
B1 = 0.
Moreover, in each modified column, every high-row perturbation is nonpositive and every low-row perturbation is nonnegative: for the rows not listed above, the perturbation is 0. Hence the pairwise inequalities of Lemma A.7 hold for both A and B. It follows that Q + γA,
Q + γB
are row-stochastic and ε-LDP for all sufficiently small γ > 0. Their images are ⊤
A q = 0,
⊤
A p=
qa −pa + pb (ej − ej ′ ) = qa (rb − ra )(ej − ej ′ ), qb
and B ⊤ q = 0,
B ⊤ p = (qc pb − qb pc )(ej − ej ′ ).
Define ∆ab := qa (rb − ra ) > 0,
∆bc := qb pc − qc pb .
Then A⊤ p = ∆ab (ej − ej ′ ),
B ⊤ p = −∆bc (ej − ej ′ ).
We have ∆bc > 0. Indeed, if qc > 0, then ∆bc = qb qc (rc − rb ) > 0, while if qc = 0, then pc > 0 and ∆bc = qb pc > 0. Set λ :=
qa (rb − ra ) ∆ab = . ∆bc qb pc − qc pb
Then λ > 0, and (λB)⊤ q = 0,
(λB)⊤ p = −A⊤ p.
Since λ ≥ 0, the same sign condition also holds for λB, so Q + γA,
Q + γλB
are row-stochastic and ε-LDP for all sufficiently small γ > 0. Choose γ > 0 small enough that both Q′ := Q + γA,
Q′′ := Q + γλB
26
are row-stochastic and ε-LDP. Then (Q⊤ p, Q⊤ q) =
1 1 ′⊤ (Q p, Q′⊤ q) + (Q′′⊤ p, Q′′⊤ q), 2 2
because (A⊤ p, A⊤ q) + ((λB)⊤ p, (λB)⊤ q) = 0. This convex combination is nontrivial since Q′⊤ p − Q⊤ p = γA⊤ p = γqa (rb − ra )(ej − ej ′ ) ̸= 0. Hence (Q⊤ p, Q⊤ q) is not an extreme point of Rm (p, q).
By construction, Q′ and Q′′ differ from Q only in the two columns j and j ′ . In matrix form. The perturbed channels Q′ = Q + γA and Q′′ = Q + γλB have entries ··· ··· ··· ··· ··· ··· ··· ··· ··· ε · · · eε θj − γ · · · · · · ′ + γ θ · · · e θ · · · θj ′ j j · · · · · · · · · · · · · · · · · · · · · · · · · ·· qa qa ε ′ ′′ ε ′ , · · · · · · θ + γ · · · e θ − γ · · · θ + γλq · · · e θ − γλqc Q′ = Q = j j j c j qb qb · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · eε θj − γλqb · · · θj ′ + γλqb eε θj ··· θj ′ · · · ··· ··· ··· ··· ··· ··· ··· ··· ···
··· · · · · · · · · · , · · · · · · ···
−ra ) with λ = qqbap(rc b−q and remaining entries (denoted · · · ) unchanged from Q. c pb
We now turn to the 3-cycle configuration.
Lemma A.9 (3-cycle configuration implies non-extremality in the joint range). Let p, q ∈ ∆k and let ri := pqii be strictly increasing in the LR order. Let Q ∈ Rk×m be a row-stochastic staircase ε-LDP channel + with ε > 0. Suppose Q contains a 3-cycle configuration. Then the induced point (Q⊤ p, Q⊤ q) is not an extreme point of the joint range Rm (p, q) := {(T ⊤ p, T ⊤ q) : T ∈ Rk×m is ε-LDP and row-stochastic}. + Equivalently, there exist row-stochastic ε-LDP channels Q+ , Q− ∈ Rk×m such that + (Q⊤ p, Q⊤ q) = 12 (Q+ )⊤ p, (Q+ )⊤ q + 21 (Q− )⊤ p, (Q− )⊤ q , and (Q+ )⊤ p, (Q+ )⊤ q = ̸ (Q− )⊤ p, (Q− )⊤ q . Moreover, the channels Q+ and Q− may be chosen so that they differ from Q only in columns participating in the 3-cycle configuration. Proof. Let e1 , . . . , em be the standard basis of Rm . Choose rows a < b < c and distinct columns u, v, w witnessing the 3-cycle, so that on rows (a, b, c) the columns u, v, w have patterns 101,
110,
011.
We take column u as the reference column. For each row i, define ( 1, if row i is high in column u, αi = e−ε , if row i is low in column u, 27
and set q̄ =
k X
qi αi ,
p̄ =
i=1
k X
pi αi .
i=1
Then q̄ > 0. We distinguish two cases: Case I: p̄ ≥ rb q̄,
Case II: p̄ < rb q̄.
In the two cases, define x, z, ∆, λ as follows: x
z
∆
λ
Case I
a
w
qa (rb − ra )
Case II
c
v
pc − qc rb
p̄ − rb q̄ ∆ rb q̄ − p̄ . ∆
In both cases, row x is high in column u and low in column z, while row b is low in column u and high in column z. Also ∆ > 0 in both cases. In Case I this follows from qa > 0 and rb > ra . In Case II, if qc > 0 then ∆ = pc − qc rb = qc (rc − rb ) > 0, while if qc = 0, then by the reduced extended likelihood-ratio order pc > 0, and hence ∆ = pc > 0. Therefore λ ≥ 0 in both cases. Define D+ , G, and C by
(D+ )b,u =
q̄ , qb
Gi,u = −αi ,
(D+ )b,z = −
q̄ , qb
(i ∈ [k]),
Gi,z = +αi
and Cx,u = −1,
Cx,z = 1,
Cb,u =
qx , qb
Cb,z = −
qx , qb
with all other entries equal to zero. Finally set D− := G + λC. Each of D+ , G, and C is supported on the two columns u, z and has row sums equal to zero. Hence D− 1 = 0 as well. We now verify the high–low inequality in Lemma A.7. For D+ , in column u the only nonzero perturbation is on the low row b and is nonnegative, while in column z the only nonzero perturbation is on the high row b and is nonpositive. Thus D+ satisfies the required high–low inequality. For C, in column u the nonzero perturbations are −1 on the high row x and qx /qb ≥ 0 on the low row b, while in column z they are 1 on the low row x and −qx /qb ≤ 0 on the high row b. Thus C also satisfies the high–low inequality. For G, in column u every high-row perturbation is −1 and every low-row perturbation is −e−ε , so the high–low inequality holds with equality. In column z, all entries of G lie in {1, e−ε }, and hence for every high row h and low row ℓ, Gh,z ≤ 1 ≤ eε Gℓ,z . 28
Since λ ≥ 0, the same high–low inequality holds for D− = G + λC. Therefore, by Lemma A.7, Q + γD+ ,
Q + γD−
are row-stochastic and ε-LDP for all sufficiently small γ > 0. We now compute the induced image increments. By construction, ⊤ D+ q = q̄(eu − ez ),
⊤ D+ p = rb q̄(eu − ez ),
G⊤ q = −q̄(eu − ez ),
G⊤ p = −p̄(eu − ez ).
and
Moreover, qx qx C ⊤ q = −qx + qb eu + qx − qb ez = 0, qb qb and qx qx C ⊤ p = −px + pb eu + px − pb ez = (qx rb − px )(eu − ez ). qb qb By the definitions of ∆ and λ, in both cases λ(qx rb − px ) = p̄ − rb q̄. Indeed, in Case I, qx rb − px = qa (rb − ra ) = ∆, while in Case II, qx rb − px = qc rb − pc = −∆.
Therefore,
⊤ D− q = G⊤ q + λC ⊤ q = −q̄(eu − ez ),
and ⊤ D− p = G⊤ p + λC ⊤ p = −p̄ + λ(qx rb − px ) (eu − ez ) = −rb q̄(eu − ez ). Hence ⊤ ⊤ ⊤ ⊤ (D− p, D− q) = −(D+ p, D+ q).
Choose γ > 0 small enough that both Q− := Q + γD−
Q+ := Q + γD+ , are row-stochastic and ε-LDP. Then, by linearity, (Q⊤ p, Q⊤ q) =
1 1 (Q+ )⊤ p, (Q+ )⊤ q + (Q− )⊤ p, (Q− )⊤ q . 2 2
This convex combination is nontrivial because (Q+ )⊤ q − (Q− )⊤ q = 2γ q̄(eu − ez ) ̸= 0, since q̄ > 0 and u ̸= z. Hence (Q+ )⊤ p, (Q+ )⊤ q = ̸ (Q− )⊤ p, (Q− )⊤ q , so (Q⊤ p, Q⊤ q) is not an extreme point of Rm (p, q).
By construction, Q+ and Q− differ from Q only in the two modified columns, namely {u, w} in Case I and {u, v} in Case II. In particular, they differ from Q only in columns participating in the 3-cycle configuration. 29
A.4
Proof of Proposition 4.1
Proof of Proposition 4.1. Let (u, v) ∈ Rℓ (p, q) be an extreme point, and let Q be an ℓ-output rowstochastic ε-LDP channel such that (Q⊤ p, Q⊤ q) = (u, v). e and a deterministic map τ : Ye → [ℓ] such that By Lemma A.1, there exist a staircase ε-LDP channel Q X e ỹ) Q(i, y) = Q(i, (i ∈ [k], y ∈ [ℓ]), ỹ:τ (ỹ)=y
and, for each y ∈ [ℓ], the high sets of the fine columns merged into y are nested.
e is not LR-contiguous. Then for some LR-ordered triple a < b < c it Suppose some active column of Q has pattern (101), so w101 > 0 for the weights defined in Lemma A.6. By that lemma, either w010 > 0 or e contains either a zigzag configuration or a 3-cycle configuration on that w110 > 0 and w011 > 0. Hence Q triple. These columns are distinct, since one column cannot realize two different patterns on the same triple. Let S be the set of columns involved in that local configuration.
No two columns in S can be merged into the same coarse output. Indeed, for a fixed coarse output, the high sets of the fine columns merged into it are nested; but in a zigzag the two patterns (101) and (010) are not nested on {a, b, c}, and in a 3-cycle the three patterns (101), (110), and (011) are pairwise non-nested on {a, b, c}. By the corresponding perturbation lemma (Lemma A.8 in the zigzag case and Lemma A.9 in the 3-cycle e + and Q e − , differing from Q e only in columns case) there exist feasible row-stochastic ε-LDP channels Q from S, such that e ⊤ p, Q e ⊤ q) = 1 (Q e + )⊤ p, (Q e + )⊤ q + 1 (Q e − )⊤ p, (Q e − )⊤ q , (Q 2 2
with distinct endpoints. e × ℓ post-processing matrix induced by τ , and define Let Π be the |Y| e − Π. Q− := Q
e + Π, Q+ := Q
Since deterministic post-processing preserves row-stochasticity and ε-LDP, both Q+ and Q− are feasible ℓ-output channels. Moreover, by linearity of post-processing, (Q⊤ p, Q⊤ q) = 12 (Q+ )⊤ p, (Q+ )⊤ q + 21 (Q− )⊤ p, (Q− )⊤ q . It remains to show that the two coarse endpoints are still distinct. Let e + )⊤ p − ( Q e − )⊤ p, ∆p := (Q
e + )⊤ q − ( Q e − )⊤ q. ∆q := (Q
e + and Q e − differ only in columns from S, both ∆p and ∆q are supported on S. They are not both Since Q zero because the fine endpoints are distinct. If the coarse endpoints were equal, then (Q+ )⊤ p = (Q− )⊤ p,
(Q+ )⊤ q = (Q− )⊤ q.
e + Π and Q− = Q e − Π, this would give Since Q+ = Q Π⊤ ∆p = 0,
Π⊤ ∆q = 0.
30
But the columns in S are sent to distinct coarse outputs, so the restriction of Π⊤ to vectors supported on S is injective. Hence ∆p = ∆q = 0, a contradiction. Therefore (Q+ )⊤ p, (Q+ )⊤ q ̸= (Q− )⊤ p, (Q− )⊤ q . Thus (u, v) = (Q⊤ p, Q⊤ q) is a nontrivial midpoint of two distinct points in Rℓ (p, q), contradicting the assumption that (u, v) is extreme. e is LR-contiguous. Since (u, v) is realized by a deterministic We conclude that every active column of Q e post-processing of Q, this proves the proposition.
B
Convex hull of SPR mechanisms
We isolate the combinatorial core of the proof as a decomposition lemma for weighted interval families with constant coverage. Lemma B.1 (Layer decomposition of constant-coverage interval families). Suppose we have finitely many nonempty intervals Iy ⊆ [k], indexed by y ∈ A, and positive weights θy > 0. Assume that for each i ∈ [k], the total weight of intervals covering i, X h(i) := θy , y: i∈Iy
is the same positive constant. Then there exist subsets Π1 , . . . , ΠN ⊆ A and numbers λ1 , . . . , λN > 0 such that: 1. for each t, the intervals {Iy : y ∈ Πt } form a partition of [k]; 2. for each y ∈ A, X
θy =
λt .
t: y∈Πt
The lemma says that if weighted intervals overlap in such a way that every position i ∈ [k] sees the same total weight, then the whole system can be peeled into layers, each of which is a partition of [k]. The coefficients λt record how much weight each layer contributes, and adding the layers back together recovers the original interval weights. This can be viewed as the standard flow-decomposition theorem [12] applied to the DAG that identifies each interval [a : b] with an edge a − 1 → b. Proof. We peel off the interval family one partition layer at a time. At each stage, we keep track of the remaining weight on each interval and choose a collection of intervals that partitions [k]; we then subtract the same amount from every interval in that layer. Formally, start with remaining weights wy := θy . At any stage, let X hcur (i) := wy y: i∈Iy
be the total remaining weight covering i. Initially hcur is constant by assumption, and after each layer is removed it will remain constant. As long as some wy is positive, we build one layer from left to right. Since some positive-weight interval is nonempty, there is at least one point with positive remaining coverage. Because hcur is constant, this implies that hcur (i) > 0 for every i ∈ [k], in particular for i = 1. Hence there exists a positive-weight 31
interval containing 1, and since it is an interval, it must be of the form [1 : b1 ] for some b1 . Now suppose we have already chosen disjoint positive-weight intervals [1 : b1 ], [b1 + 1 : b2 ], . . . , [br−1 + 1 : br ] and that br < k. Because hcur (br ) = hcur (br + 1), the total remaining weight of intervals ending at br equals the total remaining weight of intervals starting at br + 1: X X wy = wy . y: br ∈Iy , br +1∈I / y
y: br ∈I / y , br +1∈Iy
The last chosen interval ends at br , so the left-hand side is positive. Hence the right-hand side is also positive, and there exists a positive-weight interval starting at br + 1. Choose one as the next block. This shows that the construction cannot stop before reaching k. Therefore it produces a set of intervals {Iy : y ∈ Πt } that partitions [k]. Now let
λt := min wy > 0, y∈Πt
and subtract λt from the weight of every interval in this layer: ( wy − λ t , y ∈ Π t , wy ← wy , y∈ / Πt . Since the intervals in Πt partition [k], each point of [k] lies in exactly one of them, so hcur (i) decreases by exactly λt for every i. Thus hcur remains constant. Also, by the choice of λt , at least one interval in Πt now has remaining weight zero. Therefore the process terminates after finitely many steps. Finally, each time Iy appears in a layer Πt , we subtract exactly λt from its remaining weight. Since Iy starts with weight θy and ends with weight 0, the total amount removed from it is X θy = λt . t: y∈Πt
This proves the lemma. Proof of Proposition 4.2. We first view Q as a weighted family of LR-contiguous intervals, and then apply Lemma B.1. Example B.2 at the end of this section illustrates the construction on a 5 × 5 instance. Let A ⊆ [m] be the set of active columns of Q. For each y ∈ A, choose a scale θy > 0 and a nonempty LR-contiguous interval Iy ⊆ [k] such that Q(i, y) = θy 1 + (eε − 1)1{i ∈ Iy } (i ∈ [k]).
(If column y is constant, take Iy = [k] and choose θy to be the common entry divided by eε .) For y ∈ / A, we have Q(i, y) = 0 for all i. Define the “coverage” function h(i) :=
X
θy .
y∈A: i∈Iy
Since Q is row-stochastic, 1=
X y∈A
Q(i, y) =
X y∈A
32
θy + (eε − 1)h(i),
so h(i) is independent of i. It is also positive: because A ̸= ∅ and each Iy is nonempty, there exist y ∈ A and i ∈ Iy , giving h(i) ≥ θy > 0.
Lemma B.1 therefore yields subsets Π1 , . . . , ΠN ⊆ A and numbers λ1 , . . . , λN > 0 such that, for each t, the family {Iy : y ∈ Πt } is a partition of [k], and X θy = λt (y ∈ A). t: y∈Πt
For each layer t, the set Πt is a partition of [k] into st := |Πt | contiguous blocks. We now turn this partition into an ε-LDP mechanism by applying st -ary randomized response to the block label. Thus, for row i, the unique block in Πt containing i gets probability eε /(eε + st − 1), and each of the other st − 1 active outputs gets probability 1/(eε + st − 1). We index these active outputs by the corresponding y ∈ Πt , and keep the output alphabet [m] by setting all other columns to zero. This gives the mechanism b (t) , which is just the SPR mechanism associated with Πt , relabeled and zero-padded. Q The layer decomposition tells us how much raw staircase weight comes from each layer: λt is the thickness b (t) is the normalized SPR mechanism associated with that layer, we choose of layer t. Since Q βt := λt (eε + st − 1) > 0 so that the normalization factor cancels. Indeed, for any y ∈ Πt , b (t) (i, y) = λt 1 + (eε − 1)1{i ∈ Iy } , βt Q b (t) (i, y) = 0. Thus layer t contributes exactly the raw staircase amount coming while for y ∈ / Πt we have Q from the interval decomposition. We now verify that Q=
N X
b (t) . βt Q
t=1
If y ∈ / A, then both sides are identically zero in column y. If y ∈ A, then N X
b (t) (i, y) = βt Q
t=1
X t: y∈Πt
=
λt 1 + (eε − 1)1{i ∈ Iy }
X
λt
t: y∈Πt
1 + (eε − 1)1{i ∈ Iy }
= θy 1 + (eε − 1)1{i ∈ Iy } = Q(i, y), using the decomposition of θy . Hence the identity holds entrywise. b (t) are row-stochastic. Summing over the entries in any fixed row of Q = Both Q and Q therefore gives 1=
N X
βt .
t=1
Thus Q is a convex combination of relabeled, zero-padded SPR mechanisms, as claimed.
33
PN
b (t) t=1 βt Q
Example B.2 (Convex decomposition of a one-run staircase mechanism). We consider a staircase mechanism Q where each column has exactly one run of eε , and exhibit a convex combination Q = b (1) + β2 Q b (2) + β3 Q b (3) with Q b (1) , Q b (2) , Q b (3) all SPR. Take ε = 1, so eε = e, and let D := 17 + 14e. β1 Q Consider the five output columns with high sets I1 = [1, 1],
I2 = [1, 2],
I3 = [2, 2],
I4 = [2, 5],
I5 = [3, 5],
and weights θ1 =
10 , D
θ2 =
4 , D
θ3 =
3 , D
θ4 =
7 , D
θ5 =
7 . D
Define Q ∈ R5×5 by + Q(i, y) = θy 1 + (e − 1)1{i ∈ Iy } . Equivalently, 10e 10 1 10 Q= D 10 10
4e 4e 4 4 4
3 7 7 3e 7e 7 3 7e 7e . 3 7e 7e 3 7e 7e
Each row sums to 1, since for example 10e + 4e + 3 + 7 + 7 = 14e + 17 = D, and similarly for the other rows. The total weight of intervals containing each input is constant: θ1 + θ2 =
14 , D
θ2 + θ 3 + θ4 =
14 , D
θ4 + θ 5 =
14 . D
Thus the weighted interval family has constant row-coverage. Now peel off partition layers: • First layer: Π1 = {I1 , I4 } = {[1, 1], [2, 5]},
λ1 = min{θ1 , θ4 } =
7 . D
Subtracting λ1 leaves θ1′ =
3 , D
θ2′ =
4 , D
θ3′ =
3 , D
θ4′ = 0,
θ5′ =
7 . D
• Second layer: λ2 = min{θ2′ , θ5′ } =
Π2 = {I2 , I5 } = {[1, 2], [3, 5]},
4 . D
Subtracting λ2 leaves θ1′′ =
3 , D
θ2′′ = 0,
θ3′′ =
3 , D
θ4′′ = 0,
θ5′′ =
3 . D
λ3 =
3 . D
• Third layer: Π3 = {I1 , I3 , I5 } = {[1, 1], [2, 2], [3, 5]}, After subtracting λ3 , all remaining weights are zero. 34
So the original weights decompose as θ1 = λ1 + λ3 ,
θ2 = λ2 ,
θ3 = λ3 ,
θ4 = λ1 ,
θ5 = λ2 + λ3 .
b (t) , relabeled onto the common output alphabet [5]: Each layer Πt gives an SPR mechanism Q e 1 0 0 e+1 0 e+1 1 e e+1 0 0 e+1 0 1 (1) e b Q = e+1 0 0 e+1 0 , 1 e e+1 0 0 e+1 0 1 e 0 0 e+1 0 e+1 0 0 b (2) = Q 0 0 0
e e+1 e e+1 1 e+1 1 e+1 1 e+1
0
0
0 0 0 0
0 0 0 0
e
0
1 e+2 e e+2 1 e+2 1 e+2 1 e+2
e+2 1 e+2 1 b (3) = Q e+2 1 e+2 1 e+2
0 0 0 0
1 e+1 1 e+1 e , e+1 e e+1 e e+1
0 0 0 0 0
1 e+2 1 e+2 e . e+2 e e+2 e e+2
With β1 = λ1 (e + 1) =
7(e + 1) , D
β2 = λ2 (e + 1) =
4(e + 1) , D
β3 = λ3 (e + 2) =
3(e + 2) , D
we have β1 + β 2 + β 3 =
7(e + 1) + 4(e + 1) + 3(e + 2) 14e + 17 = = 1, D D
and b (1) + β2 Q b (2) + β3 Q b (3) . Q = β1 Q
C
Nontrivial coarsenings of SPR mechanisms
We show that a nontrivial deterministic merging of the outputs of an SPR mechanism never creates a new extreme point. The reason is that, after merging, one copy of each coarse output still carries the usual randomized-response signal, while the remaining merged copies contribute only hypothesis-independent noise. Proof of Proposition 4.3. Let π = (B1 , . . . , Bs ) be an LR-contiguous partition of [k], and let Qπ be the corresponding SPR channel. Equivalently, Qπ applies s-ary randomized response to the partition label: eε ε , x ∈ Bj , Qπ (j | x) = e + s − 1 1 , x∈ / Bj . eε + s − 1 35
Let τ : [s] → [ℓ] be a deterministic merging map, and write τ ◦ Qπ for the induced channel X (τ ◦ Qπ )(y | x) := Qπ (j | x) (x ∈ [k], y ∈ [ℓ]). j:τ (j)=y
Write A := τ ([s]) ⊆ [ℓ] for the coarse output labels that remain active, with t := |A|. Assume 1 < t < s, so at least one pair of fine outputs is merged, but the channel is not collapsed to a single active output. For each y ∈ A, define [ ny := |τ −1 (y)|, Cy := Bj . j:τ (j)=y
Thus ny is the number of fine labels merged into y, and the sets {Cy : y ∈ A} form the coarser partition of [k] induced by τ . We now define two ℓ-output channels. The first is randomized response on the coarser partition {Cy : y ∈ A}, and the second is an input-independent channel capturing the remaining mass. • Let R be randomized response on the coarser partition: ε 1 + (e − 1)1{x ∈ Cy } , eε + t − 1 R(y | x) = 0, • Let U be the input-independent channel n − 1 y , y ∈ A, s−t U (y | x) = 0, y∈ / A, This is well defined because Set α :=
P
y∈A (ny − 1) =
y ∈ A, y∈ / A.
x ∈ [k].
P
y∈A ny − t = s − t.
eε + t − 1 ∈ (0, 1). We claim that eε + s − 1 τ ◦ Qπ = αR + (1 − α)U.
Fix x ∈ [k] and y ∈ [ℓ]. If y ∈ / A, then both sides are zero. Now suppose y ∈ A. • If x ∈ Cy , then among the ny fine outputs merged into y, exactly one corresponds to the block eε 1 containing x, and therefore has probability eε +s−1 ; the other ny − 1 have probability eε +s−1 . Hence (τ ◦ Qπ )(y | x) =
eε + n y − 1 eε ny − 1 = α + (1 − α) . eε + s − 1 eε + t − 1 s−t
• If x ∈ / Cy , then none of the ny fine outputs merged into y corresponds to the block containing x, so 1 all ny of them have probability eε +s−1 . Therefore (τ ◦ Qπ )(y | x) =
ny 1 ny − 1 =α ε + (1 − α) . ε e +s−1 e +t−1 s−t
36
This proves the claim. Let M0 := ((τ ◦ Qπ )⊤ p),
and similarly let
M0R := R⊤ p,
M1 := ((τ ◦ Qπ )⊤ q),
M1R := R⊤ q,
M0U := U ⊤ p,
M1U := U ⊤ q.
Since U is input-independent, we have M0U = M1U . Write this common distribution as c := M0U = M1U , or equivalently, n − 1 y , y ∈ A, s−t c(y) = M0U (y) = M1U (y) = 0, y∈ / A.
Taking induced marginals under p and q in the identity
τ ◦ Qπ = αR + (1 − α)U
gives
(M0 , M1 ) = α(M0R , M1R ) + (1 − α)(c, c).
Both terms on the right lie in Rℓ (p, q): the pair (M0R , M1R ) comes from the ε-LDP channel R, and (c, c) comes from the input-independent channel U . • If (M0R , M1R ) ̸= (c, c), this is already a nontrivial convex decomposition, so (M0 , M1 ) is not extreme. • If (M0R , M1R ) = (c, c), then c = M0R = M1R , and (M0 , M1 ) = α(c, c) + (1 − α)(c, c) = (c, c), so it suffices to show that (c, c) is not an extreme point of Rℓ (p, q). For every y ∈ A, so
R(y | x) ≥
1 eε + t − 1
c(y) = M0R (y) ≥ Since t = |A| > 1, choose distinct y1 , y2 ∈ A and
for all x ∈ [k], 1 > 0. eε + t − 1
0 < η < min{c(y1 ), c(y2 )}. Obtain two new probability distributions by moving mass η from y2 to y1 and in the opposite direction: c(y1 ) + η, y = y1 , c(y1 ) − η, y = y1 , c+ (y) = c(y2 ) − η, y = y2 , c− (y) = c(y2 ) + η, y = y2 , c(y), otherwise, c(y), otherwise. Then c+ ̸= c− and
1 + (c + c− ). 2 Since c± are probability distributions, the input-independent channels c=
U ± (y | x) := c± (y)
are feasible, so (c+ , c+ ), (c− , c− ) ∈ Rℓ (p, q). Therefore (c, c) =
1 + + 1 (c , c ) + (c− , c− ) 2 2
is not an extreme point of Rℓ (p, q). In either case, the image point induced by τ ◦ Qπ is not an extreme point of Rℓ (p, q). 37
D
Optimality of the generalized binary mechanism for Eγ
Proof of Theorem 3.6. Let Sγ := {x ∈ X : P0 (x) ≥ γP1 (x)}. If Sγ = ∅ or Sγ = X , then Eγ (P0 ∥P1 ) = 0, and the theorem is immediate: in the second case, summing P0 (x) ≥ γP1 (x) over x gives 1 ≥ γ, which together with γ ≥ 1 forces γ = 1 and P0 = P1 , hence M0 = M1 . So assume both Sγ and Sγc are nonempty. Zamanlooy et al. [9] (Theorem 3) show the upper bound in Theorem 3.6. We show that the generalized binary mechanism attains this bound. Under Qγ , X M0 (0) − γM1 (0) = P0 (x) − γP1 (x) Qγ (0 | x). x
By the Neyman-Pearson characterization of Eγ , Eγ (P0 ∥P1 ) = P0 (Sγ ) − γP1 (Sγ ),
P0 (Sγc ) − γP1 (Sγc ) = (1 − γ) − Eγ (P0 ∥P1 ).
(37)
Splitting the sum over Sγ and Sγc and using (37), we get M0 (0) − γM1 (0) =
=
eε 1 P0 (Sγ ) − γP1 (Sγ ) + P0 (Sγc ) − γP1 (Sγc ) 1 + eε 1 + eε
eε − 1 1−γ eε Eγ (P0 ∥P1 ) + (1 − γ − Eγ (P0 ∥P1 )) = ε Eγ (P0 ∥P1 ) + ε . ε 1+e e +1 e +1
Since Eγ (M0 ∥M1 ) is the supremum over all events, it is at least the value of the event {0} and also at least 0 (by taking the empty event). Hence ε 1−γ e −1 Eγ (M0 ∥M1 ) ≥ max{0, M0 (0) − γM1 (0)} = Eγ (P0 ∥P1 ) + ε . eε + 1 e +1 + Combined with the upper bound, this proves equality and therefore optimality. We show that one can recover the bound from our results as well: Corollary D.1 (Recovering the Eγ upper bound from SPR optimality). SPR optimality implies ε e −1 1−γ Eγ (M0 ∥M1 ) ≤ E (P ∥P ) + . γ 0 1 eε + 1 eε + 1 + Proof. Since Eγ is an f -divergence, it is enough to optimize over SPR mechanisms. Consider an arbitrary SPR mechanism induced by an LR-contiguous partition π = (B1 , . . . , Bs ) into s blocks. If s = 1, then the SPR mechanism has a single output and is input-independent, so M0π = M1π . Since γ ≥ 1, this implies Eγ (M0π ∥M1π ) = 0, which is at most the right-hand side of the claimed bound because the latter is nonnegative by definition of (·)+ . Hence it remains to consider s ≥ 2.
The induced output probabilities at the output corresponding to block B are M0π (B) =
1 + (eε − 1)P0 (B) , eε + s − 1
M1π (B) =
38
1 + (eε − 1)P1 (B) . eε + s − 1
Therefore the contribution of this output to Eγ (M0π ∥M1π ) is 1 − γ + (eε − 1) P0 (B) − γP1 (B)
M0π (B) − γM1π (B) + =
=
+
eε + s − 1
γ−1 eε − 1 P (B) − γP (B) − , 0 1 eε + s − 1 eε − 1 +
where the last equality factors out eε − 1 > 0. Summing over blocks, eε − 1 X γ−1 . Eγ (M0π ∥M1π ) = ε P0 (B) − γP1 (B) − ε e +s−1 e −1 +
(38)
B∈π
We upper-bound the partition score: Let Pos(π) denote the blocks of π that contribute positively to the sum, i.e., Pos(π) := {B ∈ π : P0 (B) − γP1 (B) > eγ−1 ε −1 }. If Pos(π) = ∅, then the sum in (38) is zero. γ−1 ≥ 0, eε − 1 X γ−1 = P0 (B) − γP1 (B) − ε e −1 +
Otherwise, since |Pos(π)| ≥ 1 and
B∈π
≤ ≤
X B∈Pos(π)
X B∈Pos(π)
γ−1 P0 (B) − γP1 (B) − |Pos(π)| ε e −1 γ−1 P0 (B) − γP1 (B) − ε e −1
k X
γ−1 P0 (i) − γP1 (i) + − ε e −1 i=1
= Eγ (P0 ∥P1 ) − Thus, in all cases, X B∈π
P0 (B) − γP1 (B) −
γ−1 . eε − 1
γ−1 γ−1 ≤ Eγ (P0 ∥P1 ) − ε . ε e −1 + e −1 +
(39)
Combining (38) and (39) gives eε − 1 γ−1 E (P ∥P ) − γ 0 1 eε + s − 1 eε − 1 + ε e −1 γ−1 ≤ ε Eγ (P0 ∥P1 ) − ε e +1 e −1 + ε 1−γ e −1 = E (P ∥P ) + . γ 0 1 eε + 1 eε + 1 +
Eγ (M0π ∥M1π ) ≤
By SPR optimality for f -divergence objectives, the same bound holds for every ε-LDP mechanism. ε
−1 Equation (38) conveys the intuition behind the optimal mechanism being binary: the factor eεe+s−1 γ−1 decreases with the number of outputs, and the eε −1 penalty scales with the number of outputs.
E
Numerical experiments
E.1
Monte-Carlo verification of the joint-range polytope
Figure 5 empirically corroborates Theorem 3.1 at three privacy levels for the same (p, q) used in Figure 3. For each ε ∈ {0.4, 2, 5} we sample random ε-LDP channels Q ∈ Qε,2 , plot their induced image points 39
ε = 0.4
1.4
Joint range R2 (p, q) for k = 5, m = 2 across three privacy levels; p = (0.04, 0.09, 0.22, 0.47, 0.18), q = (0.25, 0.49, 0.13, 0.1, 0.03)
ε=2
1.4
1.2
1.2
1.0
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
0.0
−0.2
−0.2
−0.2
hQ> q, e1 i
1.2
−0.4 −0.4
−0.2
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
hQ> p, e1 i random ε-LDP channel (Monte Carlo)
−0.4 −0.4
−0.2
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
hQ> p, e1 i
SPR-induced extreme point
ε=5
1.4
SPR-induced interior point (dominated)
−0.4 −0.4
−0.2
0.0
0.2
0.4
0.6
0.8
1.0
1.2
1.4
hQ> p, e1 i
predicted polytope (Thm. 3.1)
Figure 5: Monte-Carlo verification of R2 (p, q) at three privacy levels for k = 5, ℓ = 2, p = (0.04, 0.09, 0.22, 0.47, 0.18), q = (0.25, 0.49, 0.13, 0.10, 0.03). Each panel shows random ε-LDP channels (gray cloud), the 2(k − 1) + 2 = 10 SPR-induced candidate points (red: filled if extreme, hollow if dominated), and the predicted polytope (Theorem 3.1, in blue). The hull contains every sampled channel at each ε. At ε = 0.4 only 4 of 10 SPR candidates are extreme; at ε = 2 that grows to 6; at ε = 5 all 10 are extreme. Again, because ℓ = 2, the plotted coordinates give the full induced pair (Q⊤ p, Q⊤ q), so points marked as non-extreme are not artifacts of a lower-dimensional projection.
(Q⊤ p, Q⊤ q), and overlay the predicted polytope: the convex hull of the 2(k − 1) + 2 = 10 SPR-induced candidate points from Theorem 3.1. As ε grows the feasible set of channels expands, the cloud of Monte-Carlo samples spreads accordingly, and additional SPR vertices become extreme; in every panel the cloud is contained in the predicted hull. Sampling procedure. Each panel uses N = 2,000,000 candidate channels drawn as follows. For ε = 0.4, each of the k rows is sampled uniformly on [0, 1]2 and then renormalized so that the two row entries sum to 1; for ε ∈ {2, 5}, the k rows are instead drawn from a Beta(0.3, 0.3) corner-seeking distribution and renormalized analogously, which concentrates proposals near the boundary of the feasible set where the LDP constraint is most likely to bind. A candidate is then kept only if every column ratio lies in [e−ε , eε ], i.e. the channel is ε-LDP. The corresponding rejection-sampling acceptance rates were 0.147%, 1.675%, and 26.336% for ε = 0.4, 2, 5 respectively. Proposals are generated with NumPy’s default_rng(20260503), so the figure is bit-exactly reproducible.
E.2
KL comparison: setup, bootstrap CIs, and runtimes
We numerically compare the SPR dynamic program (Algorithm 1) against the closed-form binary mechanism, k-ary randomized response, and (where tractable) the Kairouz–Oh–Viswanath linear program [8], on the KL utility Dkl (M0 ∥M1 ) , Dkl (P0 ∥P1 )
Mν = Q⊤ Pν ,
which we maximize over ε-LDP channels Q. (t)
(t)
Setup. For each value of the alphabet size k, we draw T = 100 pairs (P0 , P1 ) ∼ Dirichlet(1k ) ⊗ Dirichlet(1k ) once at the start of the experiment (NumPy seed 0), uniform on the probability simplex. The same 100 pairs are reused for every mechanism and every ε, so the comparison is paired across 40
mechanisms. We sweep a uniform privacy grid ε ∈ {0, 0.1, . . . , 9.9, 10.0} (101 values), and at each (ε, t) (t) (t) evaluate every mechanism on the same (P0 , P1 ). Curves report the mean of the normalized KL utility (t) (t) over the T = 100 trials, skipping the (measure-zero) trials with Dkl (P0 ∥P1 ) = 0. Confidence bands. For each mechanism we additionally report a 95% percentile-bootstrap confidence interval for the mean curve (Figure 6), computed by resampling the T = 100 trials with replacement 5000 times and taking the 2.5th and 97.5th percentiles of the resampled mean at each ε. The bootstrap is non-parametric and assumes only that the trials are exchangeable; no Gaussianity is assumed, and the band is asymmetric in general. The variability captured is over the random Dirichlet draws of (P0 , P1 ) only. The same bootstrap indices are used for every mechanism so that the paired structure across mechanisms is preserved at the band level. The bands are intentionally light because the k = 6 optimality claim is not statistical: it is the load-bearing fact that the SPR dynamic program agrees with the KOV LP on every (t) (t) trial. Empirically, maxt,ε |VSPR (ε) − VKOV (ε)| ≤ 6.1 × 10−14 across the full T × 101 grid, consistent with floating-point round-off only. Mechanisms compared. The KOV LP solves the 2k -variable staircase linear program with HiGHS via scipy.optimize.linprog; this is the exact ε-LDP optimum but is only tractable for small k. The SPR DP runs in O(ℓ k 2 ) time after sorting the alphabet by likelihood ratio, with output budget ℓ = k; for k = 100 we use a vectorized cumulative-max along columns of A[r, i] = F [s − 1, r] + µ[r + 1 : i], which keeps each s-step at one NumPy call. The binary mechanism uses the high set H0 = {x : P0 (x) ≥ P1 (x)}; randomized response is the standard k-ary channel with diagonal probability eε /(k − 1 + eε ). Results (Figure 1). In Figure 1a (k = 6) the LP is tractable and we use it as a baseline. The SPR DP curve coincides with the LP curve to floating-point precision: the maximum absolute gap across the 10,100 evaluations (t, ε) is at most 6.1 × 10−14 , consistent with round-off only. This is the empirical version of Theorem 3.1: SPR mechanisms attain the same optimum as the LP. The binary mechanism plateaus around 0.72 for ε ≳ 5, while k-ary randomized response is uninformative for small ε (below 25% of the SPR optimum at ε = 0.5) and only reaches within 5% of the SPR curve by ε ≈ 4, with full parity around ε ≈ 6.
In Figure 1b (k = 100) the LP has 2100 ≈ 1.27 × 1030 variables and is not solvable; the SPR DP, in contrast, finishes the entire 101 × 100 sweep in under 20 seconds on a laptop (median 17.8 s over three runs on a MacBook Pro with an Apple M3 Pro chip and 36 GB RAM, isolated from the other mechanisms). By Theorem 3.1, the SPR curve is the value the LP would achieve if it could be run. Two regime changes are visible relative to k = 6: the binary plateau drops from ≈ 0.72 to ≈ 0.56, since a single likelihood-ratio threshold discards more information at larger k; and randomized response is essentially uninformative for small ε, only catching up to the optimum once eε ≳ k − 1, i.e. for ε above roughly ln(k − 1) ≈ 4.6.
41
0.8
0.8
Dkl (M0 kM1 ) / Dkl (P0 kP1 )
1.0
Dkl (M0 kM1 ) / Dkl (P0 kP1 )
1.0
0.6
0.6
0.4
0.4
optimal (KOV LP) SPR mechanism (DP, ours) binary mechanism k-ary randomized response
0.2
0.0
0
2
4
ε
6
8
0.2
0.0
10
(a) k = 6.
SPR mechanism (DP, ours) binary mechanism k-ary randomized response 0
2
4
ε
6
8
10
(b) k = 100.
Figure 6: Same curves as Figure 1, with shaded 95% percentile-bootstrap confidence intervals (5000 resamples) for the mean across the T = 100 paired Dirichlet draws. The same bootstrap indices are used for every mechanism, so the paired structure of the experiment is preserved at the band level. At k = 6 the SPR and KOV bands coincide to within bootstrap noise; the substantive SPR-vs-KOV comparison is the per-trial agreement (t) (t) maxt,ε |VSPR − VKOV | ≤ 6.1 × 10−14 reported in the text, not the bands.
42