# tf_privacy.compute_rdp_single_tree

<br />

|---|
| [![](https://www.tensorflow.org/images/GitHub-Mark-32px.png) View source on GitHub](https://github.com/tensorflow/privacy/blob/v0.9.0/privacy/privacy/analysis/tree_aggregation_accountant.py#L276-L326) |

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>

<br />

<br />

<br />

| ## 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. |

<br />

<br />

<br />

<br />

| ## Returns ||
|---|---|
| The RDPs at all orders. Can be `np.inf`. ||

<br />