Fast and Near-Optimal Algorithms for Private Hypothesis Selection

Hilal Asi, Hongjie Chen
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:4221-4237, 2026.

Abstract

We study the problem of private hypothesis selection: given samples from an unknown distribution drawn from a finite hypothesis class, the goal is to identify the best hypothesis under the constraint of differential privacy. Existing algorithms for this problem are either computationally expensive or achieve sub-optimal statistical rates. We propose new algorithms that achieve near-optimal rates while running in nearly linear time in the number of hypotheses. Rather than applying the exponential mechanism directly with a score function that requires pairwise comparisons between hypotheses, our approach introduces a carefully designed loss function based on a small set of strong hypotheses. This structure allows the score to be evaluated efficiently for most hypotheses, yielding significant computational savings. We further extend our algorithms to the agnostic setting, where the true distribution may not belong to the hypothesis class. As an application, we obtain faster differentially private algorithms for universal statistical estimation in low dimensional settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-asi26a, title = {Fast and Near-Optimal Algorithms for Private Hypothesis Selection}, author = {Asi, Hilal and Chen, Hongjie}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {4221--4237}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/asi26a/asi26a.pdf}, url = {https://proceedings.mlr.press/v306/asi26a.html}, abstract = {We study the problem of private hypothesis selection: given samples from an unknown distribution drawn from a finite hypothesis class, the goal is to identify the best hypothesis under the constraint of differential privacy. Existing algorithms for this problem are either computationally expensive or achieve sub-optimal statistical rates. We propose new algorithms that achieve near-optimal rates while running in nearly linear time in the number of hypotheses. Rather than applying the exponential mechanism directly with a score function that requires pairwise comparisons between hypotheses, our approach introduces a carefully designed loss function based on a small set of strong hypotheses. This structure allows the score to be evaluated efficiently for most hypotheses, yielding significant computational savings. We further extend our algorithms to the agnostic setting, where the true distribution may not belong to the hypothesis class. As an application, we obtain faster differentially private algorithms for universal statistical estimation in low dimensional settings.} }
Endnote
%0 Conference Paper %T Fast and Near-Optimal Algorithms for Private Hypothesis Selection %A Hilal Asi %A Hongjie Chen %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-asi26a %I PMLR %P 4221--4237 %U https://proceedings.mlr.press/v306/asi26a.html %V 306 %X We study the problem of private hypothesis selection: given samples from an unknown distribution drawn from a finite hypothesis class, the goal is to identify the best hypothesis under the constraint of differential privacy. Existing algorithms for this problem are either computationally expensive or achieve sub-optimal statistical rates. We propose new algorithms that achieve near-optimal rates while running in nearly linear time in the number of hypotheses. Rather than applying the exponential mechanism directly with a score function that requires pairwise comparisons between hypotheses, our approach introduces a carefully designed loss function based on a small set of strong hypotheses. This structure allows the score to be evaluated efficiently for most hypotheses, yielding significant computational savings. We further extend our algorithms to the agnostic setting, where the true distribution may not belong to the hypothesis class. As an application, we obtain faster differentially private algorithms for universal statistical estimation in low dimensional settings.
APA
Asi, H. & Chen, H.. (2026). Fast and Near-Optimal Algorithms for Private Hypothesis Selection. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:4221-4237 Available from https://proceedings.mlr.press/v306/asi26a.html.

Related Material