The Complexity of Computing the Optimal Composition of Differential Privacy

1 Introduction

• Composition matters when multiple statistics are released or several private algorithms are combined on one database, because their privacy parameters degrade together.Composition theorems also help analyze algorithms built by combining simpler differentially private algorithms.Source: §1 · p. 2
• Because Theorem 1.3 gives only an asymptotically correct but non-exact upper bound for ϵg and applies only to homogeneous compositions with identical (ϵ, δ) parameters, an exact characterization matters in practice.Empirically (see Appendix A), the optimal bound provides a 30-40% savings in ϵg compared to Theorem 1.3 and a 20% savings compared to the improved asymptotic bound from.Source: §1 · p. 3

1.1 Our Results

• Theorem 1.5 exactly characterizes optimal composition for arbitrary algorithms with heterogeneous privacy parameters.The characterization also gives an exponential-time computation by summing over subsets of the algorithms.Source: §1.1 · pp. 3–4
• Computing OptComp is #P-complete, even when every algorithm has δ_i = 0.Thus exact computation is infeasible in polynomial time unless FP = #P.Source: §1.1 · p. 4
• A polynomial-time algorithm approximates OptComp to arbitrary accuracy using a modification of dynamic programming for counting knapsack solutions.Its guarantee permits relative error η in δ_g and additive error η in ϵ_g.Source: §1.1 · p. 4
• The proof of the heterogeneous result also gives a simpler proof of the homogeneous Kairouz–Oh–Viswanath theorem using elementary techniques.The earlier proof used a hypothesis-testing view and geometric arguments.Source: §1.1 · p. 4

2 Technical Preliminaries

• Differential privacy can be expressed as a bound on the δ-approximate max-divergence between outputs on neighboring databases.The text states that this criterion is equivalent to (ϵ, δ)-differential privacy.Source: §2 · p. 5
• Adaptive composition allows an adversary to choose each algorithm and neighboring databases based on earlier outputs, with privacy measured on its full view.The model generalizes adaptive composition to algorithms with differing privacy parameters.Source: §2 · p. 5
• The computational model uses rational privacy parameters and measures real-valued outputs to a requested number of bits of precision.For a q-bit computation, the output must be within 1/2^q of the target value.Source: §2 · pp. 5–6

3 Characterization of OptComp

• A two-stage simulator first represents an arbitrary private algorithm using a generalized randomized-response variant, then simulates that variant using the standard one.The generalized variant permits distinct δ0 and δ1, each no greater than δ.Source: §3 · pp. 6, 9
• Analyzing the composition of the canonical four-output randomized-response variants suffices to determine optimal composition for arbitrary differentially private algorithms.Each such variant can simulate an algorithm with the same privacy parameters, and postprocessing preserves differential privacy.Source: §3 · pp. 6, 11
• OptComp is unchanged when arbitrary algorithms with parameters (ϵ_i, δ_i) are replaced by their corresponding canonical variants.This equality lets the composition analysis focus on the variants rather than the original algorithms.Source: §3 · p. 12
• The same OptComp criterion characterizes whether privacy parameters satisfy (ϵ_g, δ_g)-differential privacy under adaptive composition.The section first characterizes algorithms chosen in advance and run on the same database, then establishes equivalence with the more general adaptive model.Source: §3 · p. 13

4 Hardness of OptComp

• Computing OptComp is #P-easy: a #P oracle counts witnesses encoding an approximation to the subset sum needed to compute the composition.The construction approximates each summand and represents its scaled value through witnesses (S, n), so one oracle call counts the total and yields the sum to the required precision.Source: §4 · p. 15
• Starting from #INT-PARTITION, which is #P-complete, the reduction shows that #PARTITION is #P-hard even for inputs satisfying the stated constant-bound restriction.The construction chooses a root degree and preserves a one-to-one correspondence between solutions to the original and reduced instances.Source: §4 · pp. 15, 17
• #T-PARTITION is #P-hard: adding one element makes solutions that include it correspond one-to-one with #PARTITION solutions, while the excluded case contributes none except for an easily handled all-ones input.Thus the #T-PARTITION oracle’s count on the augmented instance gives the #PARTITION answer.Source: §4 · pp. 17–18
• Four calls to a SUM-PARTITION oracle suffice to solve #T-PARTITION, establishing that SUM-PARTITION is #P-hard.The reduction uses gaps between possible partition products to choose rational thresholds and recover the integer count by approximation and rounding.Source: §4 · pp. 19–21
• For a SUM-PARTITION instance with ∏ᵢwᵢ ≤ c, disregarding precision, the proposed mapping sets εᵢ = ln(wᵢ), δᵢ = 0 for all i, and εg = ln(r).The product bound gives ∑ᵢ ln(wᵢ) ≤ ln(c).Source: §4 · p. 21

• The reduction uses polynomial-precision inputs to preserve the set of partitions being summed and keep the output error within 2^-q.Source: §4 · pp. 22, 24
• An OptComp oracle lets the reduction approximate SUM-PARTITION to q bits in polynomial time, establishing that computing OptComp is #P-hard.Source: §4 · p. 25

5 Approximation of OptComp

• For rational privacy parameters and η∈(0,1), ε* lies between OptComp((ε1,δ1),…,(εk,δk),δg) and OptComp((ε1,δ1),…,(εk,δk),e^-η/2·δg)+η.The algorithm’s stated running-time claim assumes constant-time arithmetic operations.Source: §5 · pp. 25–26
• A slight modification of Dyer’s dynamic program for counting knapsack solutions computes the weighted subset sums used in the approximation.The underlying dynamic program tabulates values by recurrence; filling its table takes O(Bk) time.Source: §5 · pp. 25–26
• Increasing each ε_i by c_i changes the bound by at most c=Σc_i while comparing against a target δg scaled by e^-c/2.The proof’s parameter choices make the additive error terms at most η.Source: §5 · pp. 26, 29
• The algorithm rounds each ε_i upward to multiples of ε0=ln(1+β), tests candidate global bounds, and uses binary search to find the minimum passing multiple.The discretized values are chosen so e^ε0 is rational, enabling the decision test.Source: §5 · p. 28

A Comparison of Composition Theorems

• The comparison composes k mechanisms with the same (ε,δ) parameters and tracks the resulting global (εg,δg) guarantee.The four curves represent basic composition, advanced composition, the KOV bound, and optimal composition.Source: A Comparison of Composition Theorems · p. 31
• Optimal composition gives substantial εg savings over the four theorems, even for moderate k.Figure 1’s right panel zooms in on k<100.Source: Figure 1 · p. 31
• KOV-bound εg is about 20% above optimal, while advanced-composition εg is about 30–40% above optimal.The relative performances of KOV and DRV appear to converge to a constant.Source: Figure 2 · p. 32