jax_privacy.matrix_factorization.sensitivity.max_participation_for_linear_fn

jax_privacy.matrix_factorization.sensitivity.max_participation_for_linear_fn#

jax_privacy.matrix_factorization.sensitivity.max_participation_for_linear_fn(x, min_sep=1, max_participations=None)[source]#

Returns \(\max_u \langle x, u \rangle\), where u respects the given participation pattern.

The vector u is represented by a set of indices that satisfy min_sep and max_participations. Note that the signs of the entries in x matter as we find \(\max_u \langle u, x \rangle\). Because the optimization is in one dimension, we can solve using a dynamic program with running time \(O(\operatorname{len}(x) \cdot (\text{max\_participations} + 1))\).

Reference: See (Amplified) Banded Matrix Factorization: A unified approach to private training, Algorithm 3 (VecSens).

Parameters:
  • x (Array) – A vector of values to optimize over.

  • min_sep (int) – Minimum separation between selected indices, e.g., if \(i\) and \(j\) are selected we must have \(|i - j| \ge \text{min}_\text{sep}\), so e.g. min_sep=1 means adjacent indices can be selected.

  • max_participations (int | None) – Optional, the maximum number of participations. If None, then max_participations is determined from len(x) and min_sep.

Return type:

Array

Returns:

The optimal value.