Sensitivity off by a factor of 2 with 'replace_one' neighbouring relation

[mtcairneyleeming]

The (descriptions) of the sensitivity of a GaussianDpEvent are inconsistent between the class definition and its use in the Renyi accountant, in Python:

The Gaussian mechanism event is defined with a noise multiplier = noise variance / clipping threshold.

class GaussianDpEvent(DpEvent):
  """Represents an application of the Gaussian mechanism.

  For values v_i and noise z ~ N(0, s^2I), this mechanism returns sum_i v_i + z.
  If the norms of the values are bounded ||v_i|| <= C, the noise_multiplier is
  defined as s / C.
  """
  noise_multiplier: float

For ADD_OR_REMOVE_ONE sensitivity, this is the same as the ratio 'noise variance' / 'sensitivity of sum', but for a REPLACE_ONE neighbouring relation, the l2 sensitivity of the function is twice the clipping bound (in the worst case, we replace +C with -C), so he GaussianDpEvent.noise_multiplier is twice as high as the 'true' noise multiplier of the mechanism.

But, this quantity is then passed directly into the Renyi accountant with subsampling: here, and is assumed to the be true noise multiplier for the REPLACE_ONE neighbouring relation:

Args:
    q: The sampling proportion =  m / n.  Assume m is an integer <= n.
    noise_multiplier: The ratio of the standard deviation of the Gaussian noise
      to the l2-sensitivity of the function to which it is added.
    orders: An array of RDP orders.

Similarly, when subsampling is not applied (here), the GaussianDpEvent.noise_multiplier is passed directly into code that assumes a
ADD_OR_REMOVE_ONE or REPLACE_SPECIAL neighbouring relation.

elif isinstance(event, dp_event.GaussianDpEvent):
      if do_compose:
        self._rdp += count * _compute_rdp_poisson_subsampled_gaussian(
            q=1.0, noise_multiplier=event.noise_multiplier, orders=self._orders
        )

I suspect this neighbouring relation is not widely used, but I think it would be good to sort this out somehow. The simplest is probably to rephrase the definition of the GaussianDpEvent to use sensitivity, and maybe mention what that means for the different neighbouring relations?

[galenmandrew]

Thanks for pointing this out.

I suspect the function _compute_rdp_sample_wor_gaussian expects noise_multiplier/sigma to be the ratio of the noise to the clip (as defined in GaussianDpEvent) and not the ratio of the noise to the sensitivity (as written in the pydoc for _compute_rdp_sample_wor_gaussian, I believe erroneously). Perhaps the pydoc was copied from _compute_rdp_poisson_subsampled_gaussian without the necessary change.

If you are familiar with the paper describing the method, maybe you could confirm that? If that is right, only the pydoc for _compute_rdp_sample_wor_gaussian needs to be fixed.

[mtcairneyleeming]

My understanding is that the docstring of _compute_rdp_sample_wor_gaussian describes the function correctly, but then it's used incorrectly, when called via the compose function with a GaussianDpEvent.

Looking at the paper, if $f= \sum_{x \in X} \mathrm{clip}(x,C)$, the start of page 4 defines sensitivity as $S_f = \max_{X\sim X'} \left|f (X) − f (X')\right|$ where X, X' are adjacent inputs, and as the current adjacency is "one element replaced", we have $S_f=2\cdot C$, because we could have $f(X)=C,f(X')=-C$.

They then define the Gaussian mechanism as $\mathcal{G}(X) := f (X) + N (0, S_f^2 \sigma^2)$, still at the top of pg 4.

They also make the standard simplification that the sensitivity is $1$, so that they can just use just one variable, giving a noise multiplier $ \sigma/S_f$ (which also aligns with GaussianDpEvent when the neighbouring relation is add/remove/replace_special). Their definition of the RDP, $\epsilon(\alpha)=\frac{\alpha}{2\sigma^2}$ (page 9, start of section 4) is also (implicitly) using the noise multiplier $\sigma/S_f$, so that simplifies to $\frac{\alpha}{2\sigma^2/(2C)^2}$.

Given noise_multiplier is defined as in the docstring of _compute_rdp_sample_wor_gaussian: "ratio of the standard deviation of the Gaussian noise to the l2-sensitivity", all of the above is implemented following the paper.

However, in compose, the noise_multiplier is passed directly from the GaussianDpEvent, which has "If the norms of the values are bounded ||v_i|| <= C, the noise_multiplier is defined as s / C", and these two disagree, but obviously only for this neighbouring relation.

I think a factor of 2 has to be added somewhere in the code, either by changing the docstrings of _compute_rdp_sample_wor_gaussian and its siblings to use $\sigma/C$ and then handling within those functions; or by keeping the docstrings as is, and changing where it's called in compose. I'm not sure which one would be more elegant.

(sorry for the very slow reply!)