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

Alireza F. Pour, Hassan Ashtiani, Shahab Asoodeh
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:4240-4275, 2024.

Abstract

We study the problem of hypothesis selection under the constraint of local differential privacy. Given a class F of k distributions and a set of i.i.d. samples from an unknown distribution h, the goal of hypothesis selection is to pick a distribution ˆf whose total variation distance to h is comparable with the best distribution in F (with high probability). We devise an ε-locally-differentially-private (ε-LDP) algorithm that uses Θ(kα2min samples to guarantee that d_{TV}(h,\hat{f})\leq \alpha + 9 \min_{f\in \mathcal{F}}d_{TV}(h,f) with high probability. This sample complexity is optimal for varepsilon<1, matching the lower bound of Gopi 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 bound of \Omega\left(\frac{k\log k}{\alpha^2 \varepsilon^2} \right) for the sample complexity of non-interactive hypothesis selection. Our algorithm achieves this using only \Theta(\log \log k) rounds of interaction. To prove our results, we define the notion of \emph{critical queries} for a Statistical Query Algorithm (SQA) which may be of independent interest. Informally, an SQA is said to use a small number of critical queries if its success relies on the accuracy of only a small number of queries it asks. We then design an LDP algorithm that uses a smaller number of critical queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-pour24a, title = {Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity}, author = {Pour, Alireza F. and Ashtiani, Hassan and Asoodeh, Shahab}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {4240--4275}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/pour24a/pour24a.pdf}, url = {https://proceedings.mlr.press/v247/pour24a.html}, abstract = {We study the problem of hypothesis selection under the constraint of local differential privacy. Given a class $\mathcal{F}$ of $k$ distributions and a set of i.i.d. samples from an unknown distribution $h$, the goal of hypothesis selection is to pick a distribution $\hat{f}$ whose total variation distance to $h$ is comparable with the best distribution in $\mathcal{F}$ (with high probability). 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. This sample complexity is optimal for $varepsilon<1$, matching the lower bound of Gopi 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 bound of $\Omega\left(\frac{k\log k}{\alpha^2 \varepsilon^2} \right)$ for the sample complexity of non-interactive hypothesis selection. Our algorithm achieves this using only $\Theta(\log \log k)$ rounds of interaction. To prove our results, we define the notion of \emph{critical queries} for a Statistical Query Algorithm (SQA) which may be of independent interest. Informally, an SQA is said to use a small number of critical queries if its success relies on the accuracy of only a small number of queries it asks. We then design an LDP algorithm that uses a smaller number of critical queries.} }
Endnote
%0 Conference Paper %T Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity %A Alireza F. Pour %A Hassan Ashtiani %A Shahab Asoodeh %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-pour24a %I PMLR %P 4240--4275 %U https://proceedings.mlr.press/v247/pour24a.html %V 247 %X We study the problem of hypothesis selection under the constraint of local differential privacy. Given a class $\mathcal{F}$ of $k$ distributions and a set of i.i.d. samples from an unknown distribution $h$, the goal of hypothesis selection is to pick a distribution $\hat{f}$ whose total variation distance to $h$ is comparable with the best distribution in $\mathcal{F}$ (with high probability). 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. This sample complexity is optimal for $varepsilon<1$, matching the lower bound of Gopi 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 bound of $\Omega\left(\frac{k\log k}{\alpha^2 \varepsilon^2} \right)$ for the sample complexity of non-interactive hypothesis selection. Our algorithm achieves this using only $\Theta(\log \log k)$ rounds of interaction. To prove our results, we define the notion of \emph{critical queries} for a Statistical Query Algorithm (SQA) which may be of independent interest. Informally, an SQA is said to use a small number of critical queries if its success relies on the accuracy of only a small number of queries it asks. We then design an LDP algorithm that uses a smaller number of critical queries.
APA
Pour, A.F., Ashtiani, H. & Asoodeh, S.. (2024). Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:4240-4275 Available from https://proceedings.mlr.press/v247/pour24a.html.

Related Material