tf_privacy.compute_zcdp_single_tree

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 total_steps leaf nodes, where the same sample will appear at most max_participation times, 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

noise_multiplier A non-negative float representing the ratio of the standard deviation of the Gaussian noise to the l2-sensitivity of a single contribution (a leaf node), which is usually set in TreeCumulativeSumQuery and TreeResidualSumQuery from dp_query.tree_aggregation_query.
total_steps Total number of steps (leaf nodes in tree aggregation).
max_participation The maximum number of times a sample can appear.
min_separation The minimum number of nodes between two appearance of a sample. If a sample appears in consecutive x, y steps in a streaming setting, then min_separation=y-x-1.

The zCDP.