|View source on GitHub|
Computes zCDP of the Tree Aggregation Protocol for a single tree.
tf_privacy.compute_zcdp_single_tree( noise_multiplier: float, total_steps: int, max_participation: int, min_separation: int ) -> Union[float, Collection[float]]
The accounting assume a single tree is constructed for
nodes, where the same sample will appear at most
and there are at least
min_separation nodes between two appearance. The key
idea is to (recurrently) count the worst-case occurence of a sample
in all the nodes in a tree, which implements a dynamic programming algorithm
that exhausts the possible
num_participation appearance of a sample in
steps leaf nodes.
See Appendix D of "Practical and Private (Deep) Learning without Sampling or Shuffling" https://arxiv.org/abs/2103.00039
The Zero-Concentrated Differential Privacy (zCDP) definition is described in "Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds" https://arxiv.org/abs/1605.02065