Privately Counting Partially Ordered Data
Abstract
We consider differentially private counting when each data point consists of $d$ bits satisfying a partial order. Our main technical contribution is a problem-specific $K$-norm mechanism that runs in time $O(d^2)$. Experiments show that, depending on the partial order in question, our solution dominates existing pure differentially private mechanisms and can reduce their error by an order of magnitude or more.
Cite
Text
Joseph et al. "Privately Counting Partially Ordered Data." International Conference on Learning Representations, 2025.Markdown
[Joseph et al. "Privately Counting Partially Ordered Data." International Conference on Learning Representations, 2025.](https://mlanthology.org/iclr/2025/joseph2025iclr-privately/)BibTeX
@inproceedings{joseph2025iclr-privately,
title = {{Privately Counting Partially Ordered Data}},
author = {Joseph, Matthew and Ribero, Mónica and Yu, Alexander},
booktitle = {International Conference on Learning Representations},
year = {2025},
url = {https://mlanthology.org/iclr/2025/joseph2025iclr-privately/}
}