tf_privacy.compute_zcdp_single_tree

Computes zCDP of the Tree Aggregation Protocol for a single tree.

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.

[{ "type": "thumb-down", "id": "missingTheInformationINeed", "label":"Missing the information I need" },{ "type": "thumb-down", "id": "tooComplicatedTooManySteps", "label":"Too complicated / too many steps" },{ "type": "thumb-down", "id": "outOfDate", "label":"Out of date" },{ "type": "thumb-down", "id": "samplesCodeIssue", "label":"Samples / code issue" },{ "type": "thumb-down", "id": "otherDown", "label":"Other" }]
[{ "type": "thumb-up", "id": "easyToUnderstand", "label":"Easy to understand" },{ "type": "thumb-up", "id": "solvedMyProblem", "label":"Solved my problem" },{ "type": "thumb-up", "id": "otherUp", "label":"Other" }]