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 <x, u>, 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 np.dot(u, x). Because the optimization is in one dimension, we can solve using a dynamic program with running time O(len(x) * (max_participations + 1)).
Reference: See [(Amplified) Banded Matrix Factorization: A unified approach to private training](https://arxiv.org/abs/2306.08153), 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\) min_sep, so e.g. min_sep=1 means adjacent indices can be selected.max_participations (
Optional[int]) – Optional, the maximum number of participations. If None, then max_participations is determined from len(x) and min_sep.
- Return type:
float- Returns:
The optimal value.