Attend the Women in ML Symposium on December 7 Register now


Stay organized with collections Save and categorize content based on your preferences.

Computes RDP 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"

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.
orders An array (or a scalar) of RDP orders.

The RDPs at all orders. Can be np.inf.