tf_privacy.tree_aggregation.EfficientTreeAggregator

Efficient tree aggregator to compute accumulated noise.

tf_privacy.tree_aggregation.EfficientTreeAggregator(
    value_generator: Union[tf_privacy.tree_aggregation.ValueGenerator, Callable[[], Any]]
)

This class implements the efficient tree aggregation algorithm based on Honaker 2015 "Efficient Use of Differentially Private Binary Trees". The noise standard deviation for a node at depth d is roughly sigma * sqrt(2^{d-1}/(2^d-1)). which becomes sigma / sqrt(2) when the tree is very tall.

random_generator = GaussianNoiseGenerator(...) tree_aggregator = EfficientTreeAggregator(random_generator) state = tree_aggregator.init_state() for leaf_node_idx in range(total_steps): assert leaf_node_idx == get_step_idx(state)) noise, state = tree_aggregator.get_cumsum_and_update(state)

value_generator A ValueGenerator or a no-arg function to generate a noise value for each tree node.

value_generator A ValueGenerator or a no-arg function to generate a noise value for each tree node.

Methods

get_cumsum_and_update

View source

@tf.function
get_cumsum_and_update(
    state: tf_privacy.tree_aggregation.TreeState
) -> Tuple[tf.Tensor, tf_privacy.tree_aggregation.TreeState]

Returns tree aggregated noise and updates TreeState for the next step.

TreeState is updated to prepare for accepting the next leaf node. Note that get_step_idx can be called to get the current index of the leaf node before calling this function. This function accept state for the current leaf node and prepare for the next leaf node because TFF prefers to know the types of state at initialization. Note that the value of new node in TreeState.level_buffer will depend on its two children, and is updated from bottom up for the right child.

Args
state TreeState for the current leaf node, index can be queried by tree_aggregation.get_step_idx(state.level_buffer_idx).

Returns
Tuple of (noise, state) where noise is generated by tree aggregated protocol for the cumulative sum of streaming data, and state is the updated TreeState..

init_state

View source

init_state() -> tf_privacy.tree_aggregation.TreeState

Returns initial TreeState.

Initializes TreeState for a tree of a single leaf node: the respective initial node value in TreeState.level_buffer is generated by the value generator function, and the node index is 0.

Returns
An initialized TreeState.

reset_state

View source

reset_state(
    state: tf_privacy.tree_aggregation.TreeState
) -> tf_privacy.tree_aggregation.TreeState

Returns reset TreeState after restarting a new tree.