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

Rejection sampling for histogram max #62

Open
mjdemedeiros opened this issue Aug 2, 2024 · 0 comments
Open

Rejection sampling for histogram max #62

mjdemedeiros opened this issue Aug 2, 2024 · 0 comments
Labels
Middle end Queries building on abstract DP system Priority : low

Comments

@mjdemedeiros
Copy link
Collaborator

The function privMaxBinAboveThreshold, which is a helper function for privMeanHistogram has a nonzero chance of failing and this has type List T -> PMF (Option (Fin numBins)).

For backwards compatibility, we should keep this function as-is. However, we could also get rid of the Option by repeatedly trying to sample from privMaxBinAboveThreshold until it succeeds. In order to show that this is a PMF we must prove that privMaxBinAboveThreshold has a nonzero probability of success. This may not be provable in the abstract, but should be provable for both Pure and Zero-Concentrated DP.

@mjdemedeiros mjdemedeiros added Middle end Queries building on abstract DP system Priority : low labels Aug 2, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Middle end Queries building on abstract DP system Priority : low
Projects
None yet
Development

No branches or pull requests

1 participant