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

This paper presents a sample-optimal, locally differentially private algorithm for hypothesis selection that achieves the information-theoretic lower bound of $\Theta(k/(\alpha^2 \min\{\varepsilon^2, 1\}))$ using only $O(\log \log k)$ rounds of interaction, thereby demonstrating the provable power of interactivity to overcome the $\Omega(k \log k)$ sample complexity barrier inherent in non-interactive approaches.

The Gist

Imagine you are a detective trying to solve a mystery, but you have a very strict rule: you cannot look at the evidence directly.

In this story, the "evidence" is a pile of sensitive data (like medical records or financial habits) belonging to a mysterious person we'll call The Unknown. You have a list of $k$ suspects (hypotheses), each claiming to be The Unknown. Your goal is to pick the suspect who is most similar to The Unknown.

The catch? To protect privacy, every piece of evidence must be scrambled (privatized) before you see it. This is called Local Differential Privacy (LDP). It's like asking a witness to whisper their observation into a noisy machine that adds static before you hear it.

The Problem: The "Noisy" Tournament

In the past, if you wanted to find the best suspect among $k$ options using these noisy whispers, you had to play a massive game of "Rock, Paper, Scissors" where every suspect fought every other suspect.

• The Old Way (Non-Interactive): Imagine a tournament where everyone fights everyone. If you have 1,000 suspects, that's nearly a million fights. Because the whispers are so noisy, you need a huge crowd of witnesses (samples) to be sure who won each fight. The old algorithms needed roughly $k \times \log(k)$ witnesses. That's a lot of data!
• The Interactive Way: Some researchers realized that if you can talk back and forth (interact) with the witnesses, you can be smarter. You can say, "Okay, Suspect A lost to Suspect B, so let's stop asking about A and focus on B." This helped, but the best previous method still needed $k \times \log(k) \times \log(\log(k))$ witnesses. It was better, but still not perfect.

The Breakthrough: The "Critical Query" Insight

The authors of this paper asked a simple question: "Do we really need to know the result of every single fight to find the winner?"

They realized the answer is no.

Imagine you are trying to find the tallest person in a stadium. You don't need to measure every single person against every other person. You just need to make sure the actual tallest person isn't accidentally knocked out early.

The authors introduced a concept called "Critical Queries."

• Non-Critical Queries: These are fights between two suspects who are both clearly not the best. Whether they win or lose doesn't matter much.
• Critical Queries: These are the specific fights involving the actual best suspect (or someone very close to them). If we get these wrong, the whole game is over.

The Analogy:
Think of a "Whisper-Down-the-Lane" game.

• Old Method: You whisper a message to 1,000 people, and they all whisper to 1,000 others. You need a massive crowd to ensure the message survives the noise.
• New Method: You realize you only care if the one specific person holding the real message survives. You don't need to track the noise of the other 999 people. You just need to ensure the path for the "Real Message" is clear.

The Solution: The "BOKSERR" Algorithm

The authors built a new algorithm (funny name: BOKSERR) that uses this "Critical Query" idea. Here is how it works in three steps:

1. The Knockout (Boosted Knockout): They run a series of quick, noisy tournaments. They don't care who wins the minor fights; they only care that the "Best Suspect" isn't accidentally eliminated. They use a clever trick to ensure the Best Suspect survives even if the noise is high, as long as they don't get paired with a "bad" suspect too often.
2. The Elimination (Boosted Sequential Round-Robin): They take the survivors and group them. They run more tournaments, but this time they are very careful about the groups. They repeat the process a few times to boost the confidence that the Best Suspect is still in the running.
3. The Final Showdown (MDE-Variant): Once they have whittled the list down to a tiny, manageable group of "likely winners," they do a final, careful comparison to pick the single best one.

Why This Matters

1. Fewer Samples: The old methods needed data proportional to $k \log k$. This new method only needs data proportional to $k$.
   • Simple Math: If you have 1 million suspects, the old way needed data for roughly 20 million comparisons. The new way only needs data for 1 million. That's a massive saving in time and resources.
2. The Power of Interaction: This proves that talking back and forth (interactivity) is a superpower in privacy. Without it, you are stuck with the expensive $k \log k$ cost. With just a few rounds of talking (about $\log \log k$ rounds, which is very small), you can get the optimal cost.
3. Real-World Impact: Companies like Apple and Google use Local Privacy to collect data from your phone without seeing your actual data. This paper tells them: "You can get the same accuracy with 10x less data (or 10x more accuracy with the same data) just by changing how you ask the questions."

The Bottom Line

The paper is like finding a shortcut through a maze. Previously, everyone thought you had to walk every single path to find the exit. The authors realized you only need to walk the paths that lead to the exit. By focusing only on the "critical" steps and ignoring the rest, they solved the problem with the absolute minimum amount of data required, setting a new gold standard for private data analysis.

Technical Summary

Here is a detailed technical summary of the paper "Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity" by Pour, Ashtiani, and Asoodeh.

1. Problem Statement

The paper addresses the Hypothesis Selection problem under the constraint of Local Differential Privacy (LDP).

• Goal: Given a class of $k$ candidate distributions $\mathcal{F}$ and i.i.d. samples from an unknown distribution $h$, the goal is to select a distribution $\hat{f} \in \mathcal{F}$ such that its Total Variation (TV) distance to $h$ is close to the best possible distribution in $\mathcal{F}$. Specifically, the algorithm must satisfy:
  $$d_{TV}(h, \hat{f}) \leq C \cdot \min_{f \in \mathcal{F}} d_{TV}(h, f) + \alpha$$
  with high probability, where $C$ is a constant approximation factor and $\alpha$ is the accuracy parameter.
• Constraint: The algorithm must operate under $\varepsilon$-Local Differential Privacy. In this model, each data point is privatized locally before being sent to the algorithm; the algorithm never sees the raw data.
• The Gap: Prior work (Gopi et al., 2020) established that non-interactive LDP hypothesis selection requires $\Omega(k \log k)$ samples. While interactive algorithms existed, the best known upper bound was $O(k \log k \log \log k)$, leaving a gap between the lower bound ($\Omega(k)$ for interactive) and the upper bound. The central question was: Can interactive LDP hypothesis selection achieve a sample complexity linear in $k$ (i.e., $O(k)$)?

2. Methodology

The authors propose a new algorithm named BOKSERR (Boosted Sequential Round-Robin MDE-Variant) and a novel analytical framework based on Critical Queries.

A. The Statistical Query (SQ) Viewpoint

The authors frame hypothesis selection within the Statistical Query (SQ) model. Instead of accessing raw samples, the algorithm queries an oracle for estimates of expectations of specific functions (queries).

• Standard SQO: Requires accuracy for all $n$ queries. In LDP, simulating this requires a union bound over all queries, leading to a $\log n$ factor in sample complexity ($O(n \log n)$).
• Critical Queries (SQOC): The authors introduce the concept of Critical Queries. An algorithm is said to use $m$ critical queries if its success depends only on the accuracy of a subset of size $m$ (where $m \ll n$), even though it makes $n$ total queries.
  • Key Insight: If an algorithm only relies on $m$ critical queries, the LDP sample complexity can be reduced from $O(n \log n)$ to $O(n \log m)$, effectively removing the $\log n$ penalty if $m$ is small.

B. The BOKSERR Algorithm

The algorithm consists of three main sub-routines designed to minimize the number of critical queries while reducing the candidate set size:

1. Boosted Knockout:

   • Runs in $t$ rounds.
   • Randomly pairs distributions and performs Scheffé tests (pairwise comparisons).
   • Keeps distributions that win a high fraction of comparisons.
   • Criticality: Only the comparisons involving the optimal distribution $f^*$ are critical. The analysis shows that the number of critical queries is small relative to the total queries made.
   • Output: Two lists, $K_1$ (survivors) and $K_2$ (random sample). With high probability, either $f^* \in K_1$ or a "good" distribution is in $K_2$.

2. Boosted Sequential Round-Robin (BSRR):

   • Takes $K_1$ as input.
   • Partitions candidates into groups, runs round-robin tournaments within groups, and keeps winners.
   • Boosting: Unlike previous methods, this repeats the grouping process $O(\log(1/\beta))$ times per round to boost success probability without increasing the critical query count significantly.
   • Criticality: All queries made by BSRR are critical, but because the input size $|K_1|$ has been drastically reduced by the Knockout phase, the total number of critical queries remains manageable.

3. MDE-Variant (Minimum Distance Estimate):

   • Takes the union of lists from previous steps ($R_1 \cup R_2 \cup K_2$).
   • Runs a standard MDE-variant (which makes $O(|S|^2)$ queries) on this small set.
   • Since the input size is small, the quadratic cost here does not dominate the overall complexity.

3. Key Contributions

1. Optimal Sample Complexity: The paper proves that interactive LDP hypothesis selection can be solved with $\Theta(k)$ sample complexity (specifically $O(\frac{k}{\alpha^2 \varepsilon^2})$), matching the theoretical lower bound for interactive protocols. This closes the gap left by previous $O(k \log k \log \log k)$ algorithms.
2. Critical Query Framework: The authors define and utilize the notion of Critical Queries for Statistical Query Algorithms. This framework allows breaking the standard union-bound barrier in LDP by showing that an algorithm's success often hinges on a small subset of queries, not all of them.
3. Provable Benefits of Interactivity: The work provides a concrete separation between non-interactive and interactive LDP.
   • Non-interactive: $\Omega(k \log k)$ samples required.
   • Interactive: $O(k)$ samples sufficient.
   • The algorithm achieves this using only $\Theta(\log \log k)$ rounds of interaction.
4. Improved Approximation and Failure Bounds:
   • Achieves an approximation factor of 9 (improving on the previous 27).
   • Provides high-probability guarantees for any failure parameter $\beta$, with only a polylogarithmic cost $(\log 1/\beta)^2$, whereas previous bounds were loose or restricted to specific $\beta$.

4. Results

• Theorem 5 (Main Result): There exists an $\varepsilon$-LDP algorithm (BOKSERR) that solves hypothesis selection in $O(\log \log k)$ rounds with an approximation factor of 9.
• Sample Complexity: The algorithm uses $O\left(\frac{k (\log 1/\beta)^2}{\alpha^2 \min\{\varepsilon^2, 1\}}\right)$ samples.
• Corollary 6: For constant $\beta$, the sample complexity is $\Theta\left(\frac{k}{\alpha^2 \varepsilon^2}\right)$, which is optimal.
• Comparison:
  • Round-Robin (Non-private): $O(k^2)$ queries.
  • Gopi et al. (2020): $O(k \log k \log \log k)$ samples.
  • This Work (BOKSERR): $O(k)$ samples.

5. Significance

• Theoretical Breakthrough: This paper resolves a major open problem in differentially private learning by demonstrating that the "logarithmic penalty" often associated with local privacy can be eliminated for hypothesis selection through clever interaction and analysis.
• Practical Implications: Since many real-world applications (e.g., Google, Apple) use LDP, reducing the sample complexity from $O(k \log k)$ to $O(k)$ means significantly fewer users are needed to achieve the same level of accuracy, or higher accuracy can be achieved with the same user base.
• Methodological Innovation: The concept of Critical Queries is a powerful new tool for analyzing private algorithms. It suggests that many existing SQ-based algorithms might be re-analyzed to achieve better sample complexity in the LDP setting if their dependency on the accuracy of all queries can be relaxed.
• Interactivity: The work solidifies the understanding that a small number of interaction rounds ($\log \log k$) is sufficient to bridge the gap between non-interactive and interactive privacy models for certain statistical tasks.

In summary, the authors successfully design an algorithm that is sample-optimal for locally private hypothesis selection by introducing a novel "critical query" analysis technique, proving that interaction is not just beneficial but essential for achieving linear sample complexity in this domain.