![]() |
Computes RDP of the Tree Aggregation Protocol for a single tree.
tf_privacy.compute_rdp_single_tree(
noise_multiplier: float,
total_steps: int,
max_participation: int,
min_separation: int,
orders: Union[float, Collection[float]]
) -> 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
Args | |
---|---|
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. |
Returns | |
---|---|
The RDPs at all orders. Can be np.inf .
|