Fast and Near-Optimal Algorithms for Private Hypothesis Selection

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.

Imagine a medical dataset contributed by many patients, which you want to use to study a disease. You have a long list of candidate explanations for the data, and you want to pick the best-fitting one without revealing any individual patient's information. Existing methods force a choice: the accurate ones are painfully slow, comparing every candidate against every other, while the fast ones demand far more data. Our methods avoid that trade-off with a shortcut. Instead of comparing all pairs, we cheaply find a few strong candidates, then measure everyone else against just those — skipping the vast majority of comparisons while still finding the best fit, using close to the least data possible. The payoff is a method that is both accurate and fast, making privacy-preserving data analysis far more practical when the list of candidates is large.