Report Noisy Max

Adds independent Laplace noise with scale \(\Delta / \epsilon\) to each counting query and returns the index of the largest noisy count. For monotone sensitivity-1 counting queries the released index is (epsilon, 0)-differentially private (Dwork-Roth 2014, Claim 3.9); the winning noisy count may be released at no extra privacy cost, the losing counts must not be.

Usage

Reportm(counts, epsilon, sensitivity = 1, seed = 1)

Arguments

counts

Values of the m counting queries.

epsilon

Privacy budget, positive.

sensitivity

Per-query sensitivity (1 for counting queries).

seed

Seed for the shared deterministic stream.

Value

List with index (0-based argmax), winner, estimate, epsilon, scale, n.

Details

Determinism: noise comes from the shared Lehmer minstd stream, so a given seed reproduces the same selection in both language arms. Laplace draws by inverse CDF, \(x = -b\, sign(u - 1/2) \log(1 - 2 |u - 1/2|)\). Ties: first maximum in scan order wins in both arms.

References

Dwork, C., and Roth, A. (2014). The algorithmic foundations of differential privacy. FnT-TCS 9(3-4), 211-487. Section 3.3, Report Noisy Max and Claim 3.9.

Examples

Reportm(counts = c(1, 2, 3, 4, 5, 6, 7, 8), epsilon = 5L)
#> $index
#> [1] 7
#> 
#> $winner
#> [1] 7.954373
#> 
#> $estimate
#> [1] 7
#> 
#> $epsilon
#> [1] 5
#> 
#> $scale
#> [1] 0.2
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "Report Noisy Max (Dwork-Roth 2014, Claim 3.9)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"