English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the problem of hypothesis selection under the constraint of localdifferential privacy. Given a class $\mathcal{F}$ of $k$ distributions and aset of i.i.d. samples from an unknown distribution $h$, the goal of hypothesisselection is to pick a distribution $\hat{f}$ whose total variation distance to$h$ is comparable with the best distribution in $\mathcal{F}$ (with highprobability). We devise an $\varepsilon$-locally-differentially-private($\varepsilon$-LDP) algorithm that uses $\Theta\left(\frac{k}{\alpha^2\min\{\varepsilon^2,1\}}\right)$ samples to guarantee that $d_{TV}(h,\hat{f})\leq\alpha + 9 \min_{f\in \mathcal{F}}d_{TV}(h,f)$ with high probability. Thissample complexity is optimal for $\varepsilon<1$, matching the lower bound ofGopi et al. (2020). All previously known algorithms for this problem required$\Omega\left(\frac{k\log k}{\alpha^2\min \{ \varepsilon^2 ,1\}} \right)$samples to work.  Moreover, our result demonstrates the power of interaction for$\varepsilon$-LDP hypothesis selection. Namely, it breaks the known lower boundof $\Omega\left(\frac{k\log k}{\alpha^2\min \{ \varepsilon^2 ,1\}} \right)$ forthe sample complexity of non-interactive hypothesis selection. Our algorithmbreaks this barrier using only $\Theta(\log \log k)$ rounds of interaction.  To prove our results, we define the notion of \emph{critical queries} for aStatistical Query Algorithm (SQA) which may be of independent interest.Informally, an SQA is said to use a small number of critical queries if itssuccess relies on the accuracy of only a small number of queries it asks. Wethen design an LDP algorithm that uses a smaller number of critical queries.

Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity