Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.16180 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915730744672256 |
|---|---|
| author | Kamath, Gautam Pour, Alireza F. Regehr, Matthew Woodruff, David P. |
| author_facet | Kamath, Gautam Pour, Alireza F. Regehr, Matthew Woodruff, David P. |
| contents | We propose an algorithm with improved query-complexity for the problem of hypothesis selection under local differential privacy constraints. Given a set of $k$ probability distributions $Q$, we describe an algorithm that satisfies local differential privacy, performs $\tilde{O}(k^{3/2})$ non-adaptive queries to individuals who each have samples from a probability distribution $p$, and outputs a probability distribution from the set $Q$ which is nearly the closest to $p$. Previous algorithms required either $Ω(k^2)$ queries or many rounds of interactive queries.
Technically, we introduce a new object we dub the Scheffé graph, which captures structure of the differences between distributions in $Q$, and may be of more broad interest for hypothesis selection tasks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_16180 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph Kamath, Gautam Pour, Alireza F. Regehr, Matthew Woodruff, David P. Data Structures and Algorithms Machine Learning We propose an algorithm with improved query-complexity for the problem of hypothesis selection under local differential privacy constraints. Given a set of $k$ probability distributions $Q$, we describe an algorithm that satisfies local differential privacy, performs $\tilde{O}(k^{3/2})$ non-adaptive queries to individuals who each have samples from a probability distribution $p$, and outputs a probability distribution from the set $Q$ which is nearly the closest to $p$. Previous algorithms required either $Ω(k^2)$ queries or many rounds of interactive queries. Technically, we introduce a new object we dub the Scheffé graph, which captures structure of the differences between distributions in $Q$, and may be of more broad interest for hypothesis selection tasks. |
| title | Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2509.16180 |