Abstract
This paper investigates the fundamental sample complexity required to handle threshold functions under the constraints of $(\epsilon, \delta)$-differential privacy (DP). We establish that the tasks of releasing, distribution learning, and properly PAC learning threshold functions over a data universe $X$ require a sample size that scales with the iterated logarithm of the domain size, $\Omega(\log^* |X|)$. This result provides the first known separation between the sample complexity of private and non-private proper PAC learning for a class with a small Vapnik–Chervonenkis (VC) dimension. Furthermore, our findings imply that these tasks are impossible to perform privately over infinite data universes, such as the real numbers, even when allowing for approximate differential privacy.
Introduction
In classical statistics and machine learning, learning a threshold function—identifying a value $x$ such that most data points fall on one side—is a trivial task. It requires a constant number of samples, independent of the size or density of the data universe. However, the introduction of differential privacy (DP) fundamentally alters this landscape. Differential privacy requires that the inclusion or exclusion of any single individual's data does not significantly alter the output distribution of an algorithm.
This research addresses whether it is possible to maintain this privacy guarantee while performing three core tasks: private query release (answering all threshold queries), private distribution learning (learning a distribution with respect to Kolmogorov distance), and private PAC learning (learning a hidden threshold from labeled examples). The central discovery is that these tasks are intrinsically tied to the "resolution" of the data universe, characterized by the $\log^*$ function.
The Interior Point Problem
The paper’s primary methodological contribution is the reduction of complex learning tasks to a simpler primitive: the Interior Point Problem. In this problem, given a database $D$ drawn from a totally ordered universe $X$, an algorithm must output any value $z$ such that $\min(D) \le z \le \max(D)$.
The authors demonstrate that any $(\epsilon, \delta)$-DP algorithm capable of solving the Interior Point Problem can be used to solve threshold release and learning. Consequently, the lower bounds established for the Interior Point Problem serve as a bottleneck for all threshold-related private data analysis.
Methodological Framework
Lower Bound via Recursive Compression
To prove that a significant number of samples is necessary, the authors employ a recursive construction. They demonstrate that if a solution to the Interior Point Problem exists for a domain of size $|X|$ using $n$ samples, that solution can be "compressed" to solve the problem for a significantly smaller domain using $n-1$ samples. This iterative reduction leads to the $\Omega(\log^* |X|)$ lower bound. The $\log^*$ function (the iterated logarithm) represents the number of times one must apply the logarithm function to a number before the result is less than or equal to 1. This growth is incredibly slow, yet its presence signifies a fundamental dependence on the domain size that does not exist in non-private settings.
Upper Bound: The RecPrefix Algorithm
On the algorithmic side, the authors propose RecPrefix, a recursive mechanism designed to solve the Interior Point Problem. The algorithm functions by pairing elements and identifying their longest common prefixes in a binary representation. By recursing on these prefixes, the algorithm effectively shrinks the effective domain at each step. While the initial analysis provided an upper bound of $2^{(1+o(1))\log^* |X|}$, the authors acknowledge that subsequent research has tightened this to match the $\Theta(\log^* |X|)$ lower bound.
Key Insights and Implications
The Impossibility of Infinite Domains
A striking consequence of the $\log^*$ lower bound is the impossibility of private threshold learning over infinite domains (e.g., the set of all natural numbers or the interval $[0, 1]$). Because the required sample size $n$ grows with $|X|$, no single $(\epsilon, \delta)$-DP algorithm can succeed for all possible domain sizes. This highlights a strict limitation of approximate differential privacy that mirrors known impossibilities in "pure" ($\delta=0$) differential privacy.
Proper vs. Improper Learning
The paper identifies a critical gap in proper learning, where the learner is restricted to outputting a hypothesis from the same class (in this case, a threshold function). While non-private proper learning of thresholds is possible with $O(1)$ samples, private proper learning requires $\Omega(\log^* |X|)$. This provides a clear separation between private and non-private sample complexity for concept classes with small VC dimensions.
High-Dimensional Extensions
The research extends these findings to multi-dimensional thresholds. For thresholds in $\ell$ dimensions, the lower bound scales linearly with the dimension: $\Omega(\ell \cdot \log^* |X|)$. This suggests that the "privacy cost" of thresholds compounds as the complexity of the data attributes increases.
Conclusion and Future Directions
This work establishes the iterated logarithm as a fundamental limit in private data analysis. While thresholds serve as a foundational test case, the results suggest that the sample complexity of many geometric and logical concept classes under DP may be governed by similar domain-dependent factors. Future research continues to explore the characterization of improper learners—which are not restricted to outputting a threshold—and how the Littlestone dimension might provide a more general framework for understanding private learnability.
Summary updated