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
uis represented by a set of indices that satisfymin_sepandmax_participations. Note that the signs of the entries inxmatter 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=1means adjacent indices can be selected.max_participations (
int|None) – Optional, the maximum number of participations. IfNone, thenmax_participationsis determined fromlen(x)andmin_sep.
- Return type:
Array- Returns:
The optimal value.