{"ID":2868952,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.16180","arxiv_id":"2509.16180","title":"Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph","abstract":"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.","short_abstract":"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 individ...","url_abs":"https://arxiv.org/abs/2509.16180","url_pdf":"https://arxiv.org/pdf/2509.16180v2","authors":"[\"Gautam Kamath\",\"Alireza F. Pour\",\"Matthew Regehr\",\"David P. Woodruff\"]","published":"2025-09-19T17:41:15Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\",\"stat.ML\"]","methods":"[]","has_code":false}