Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

zCDP definition unnecessarily weakens zCDP composition bound #45

Open
mjdemedeiros opened this issue Jul 19, 2024 · 0 comments
Open

zCDP definition unnecessarily weakens zCDP composition bound #45

mjdemedeiros opened this issue Jul 19, 2024 · 0 comments
Labels
Back end Probability monad, sampling algorithms, primitive mechanisms, instances of DP systems Priority : low

Comments

@mjdemedeiros
Copy link
Collaborator

Our definition of zCDPBound _ ε corresponds to (ε^2/2)-zCDP from the literature. This difference is mostly harmless, but since the abstract DP system is specified in terms of ε it means that the abstract composition bound only provides ((ε1+ε2)^2/2)-zCDP, while it could provide (ε1^2/2 + ε2^2/2)-zCDP.

Changing the definition of zCDP to match the literature would allow us to improve this bound, though it would have a sizable impact on the existing codebase. The loose step in the adaptive composition proof is made explicit here, but the loose step in the non-adaptive composition bound is more deeply embedded in the proof.

@mjdemedeiros mjdemedeiros added Middle end Queries building on abstract DP system Priority : low Back end Probability monad, sampling algorithms, primitive mechanisms, instances of DP systems and removed Middle end Queries building on abstract DP system labels Jul 19, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Back end Probability monad, sampling algorithms, primitive mechanisms, instances of DP systems Priority : low
Projects
None yet
Development

No branches or pull requests

1 participant