Advance composition in PipelineDP

[dvadym]

Short DP references

Definition: Basic (or naive) composition of differential privacy mechanisms with parameters (eps1, delta1) and (eps2, delta2) is a mechanism with parameter (eps1+eps2, delta1+delta2).

There are many advance composition methods (RDP, CDP, Privacy Loss Distributions (PLD) etc), which allow to get total budget smaller than with basic composition.

There is dp_accounting library developed by Google, which implements PLD and RDP methods.

PipelineDP budget accounting design

In the PipelineDP initial release only Basic DP composition was supported, but the budget accounting was designed with keeping in mind introduction of other types of composition later.

The basic budget accounting is performed by class NaiveBudgetAccountant.

There is already class PLDBudgetAccountant, but it's not fully supported by PipelinedP.

How BudgetAccountant is used

BudgetAccountant is used in the following steps:

1. Specify total budget
2. Specify DP mechanisms by requesting budget for them
3. Compute budget per mechanism
4. Use budget per mechanism.

To be specific the following is an example of NaiveBudgetAccountant usage:

    #  Creating budget accountant with specified total budet.
    budget_accountant = NaiveBudgetAccountant(total_epsilon=1, total_delta=1e-6) 
    # Request budget for 2 mechanisms - laplace and gaussian.
    budget1 = budget_accountant.request_budget(mechanism_type=MechanismType.LAPLACE)
    budget2 = budget_accountant.request_budget(
        mechanism_type=MechanismType.GAUSSIAN, weight=3)
    # Having all mechanisms it computes the budget per mechanism.
    budget_accountant.compute_budgets()
  
    # As a result the budget (1, 1e-6) splits over 2 mechanism, with weight 1 and 3:
    # budget1.eps = 0.25, budget1.delta = 0  
    # budget2.eps = 0.75, budget2.delta = 1e=6

Goals

Main goal: To introduce full support of PLD
Side goals: To introduce full support of RDP and other advance composition methods (please advice).

The main missing part now is that currently all mechanisms require (eps, delta), but PLDBudgetAccountant returns the mechanism specification for Laplace/Gaussian (i.e. noise_std_dev). So the code which applies Laplace/Gaussian mechanism needs to be updated for using noise_std_dev.

Here is the code that applies Laplace/Gaussian mechanism. It uses a wrapper from PyDP of Google C++ DP building block library.

[ricardocarvalhods]

Hello @dvadym , I'd like to work on this if that's ok.

[dvadym]

Hi @ricardocarvalhods , sure, go ahead. Thanks!

[ricardocarvalhods]

Hey @dvadym , could you please clarify this for me?
When applying each Laplace/Gaussian mechanism using their corresponding noise_std_dev:

• Should I use any direct implementation of Laplace/Gaussian noise generation given noise_std_dev? I couldn't find such an implementation (both PyDP and Google C++ DP have addNoise only given a mechanism defined by epsilon/delta, instead of a generic noise generation given noise_std_dev).
• Or should I use PLD.from_laplace/gaussian_mechanism to get the PLD and then obtain each epsilon using PLD.get_epsilon_for_delta?

[dvadym]

Hey @ricardocarvalhods,

Great question! Yeah unfortunately Google C++ DP doesn't have an API for setting parameters for noise directly. I'll try to add it, but it will require some time on discussions and getting approvals from all project owners (I'd say it will not be not earlier than in 3 months).

Your proposal with computing eps/delta from noise_std_dev looks like the best option. Yeah, we can use the formula laplace_b = sensitivity/eps for Laplace mechanism and PLD.get_epsilon_for_delta for Gaussian.