jax_privacy.batch_selection.RandomAllocationSampling#

class jax_privacy.batch_selection.RandomAllocationSampling(total_participations, iterations, cycle_length=1, partition_type=PartitionType.INDEPENDENT, sampling_prob=1.0)[source]#

Bases: BatchSelectionStrategy

Implements k-out-of-t random allocation (aka balanced-iteration sampling).

Each example independently selects exactly \(k\) steps (out of the steps it is eligible for) to participate in, uniformly at random. For \(k=1\) and cycle_length=1, this participation pattern is equivalent to BallsInBinsSampling, and for total_participations = ceil(iterations / cycle_length) and sampling_prob < 1, it recovers CyclicPoissonSampling (without batch truncation).

If cycle_length > 1, each example is first independently assigned to one of cycle_length groups uniformly at random, and group \(j\) is only eligible to participate in iterations \(i\) with i % cycle_length == j. Two consecutive participations of an example are then always at least cycle_length iterations apart, which satisfies the min-separation requirement of a cycle_length-banded matrix mechanism. cycle_length == 1 retrieves standard random allocation.

References

Formal guarantees of the batch_iterator:
  • All batches consist of indices in the range [0, num_examples).

  • Each example only appears in batches with index i such that i % cycle_length == j for some fixed j chosen uniformly at random independently for each example.

  • Each example appears in exactly \(k\) of the batches it is eligible for, chosen uniformly at random without replacement.

  • The allocation for each example is independent of all other examples.

Accounting:

For DP-SGD with Gaussian noise (cycle_length = 1), and for amplified BandMF with a cycle_length-banded strategy matrix, exact analytical privacy accounting under the add-or-remove-one adjacency notion is supported via random_allocation_dpsgd_event() and random_allocation_bandmf_event() respectively.

Variables:
  • total_participations – The number of eligible steps each example participates in (k). If iterations is not a multiple of cycle_length, the schedule runs as if for the next multiple of cycle_length and truncates after iterations steps.

  • iterations – The total number of iterations / batches to generate (t).

  • cycle_length – If > 1, the examples are independently partitioned into cycle_length groups which participate in a round-robin fashion, so that each example participates at most once every cycle_length iterations. cycle_length == 1 retrieves standard random allocation.

  • partition_type – How to partition the examples into groups before random allocation. INDEPENDENT is the default, while EQUAL_SPLIT shuffles and splits into groups of equal size (discarding num_examples % cycle_length examples).

  • sampling_prob – Probability of independently keeping each allocated participation. Defaults to 1.0 (no subsampling).

Methods

__init__

batch_iterator

Yields 1D batches of data indices.

Attributes

total_participations: int#
iterations: int#
cycle_length: int = 1#
partition_type: PartitionType = 1#
sampling_prob: float = 1.0#
batch_iterator(num_examples, rng=None)[source]#

Yields 1D batches of data indices.

Return type:

Iterator[ndarray]