In standard statistical learning theory, the difficulty of learning a concept class depends entirely on its geometric or combinatorial complexity, such as its VC dimension. For instance, learning a threshold function on a line (e.g., $f_c(x) = 1$ if $x \ge c$ else $0$) requires a constant number of samples, regardless of whether the domain $X$ contains ten elements or represents the infinite set of real numbers $\mathbb{R}$.
However, when we introduce the constraint of Differential Privacy (DP), this independence vanishes. A foundational line of research has revealed a striking barrier: the sample complexity of private learning algorithms must scale with the size or representation length of the underlying data domain $|X|$. This means that over an infinite domain, universally learning even the simplest functions under standard DP constraints becomes mathematically impossible.
Why Privacy Forces Domain Dependency
To understand why this dependency arises, consider the fundamental tension between privacy and thresholding. A differentially private algorithm must produce similar output distributions for two datasets that differ by just a single individual.
If we try to find a threshold that splits a dataset, a single individual's position could be the deciding factor between two very different valid thresholds. As shown by Bun et al. 2015, this task can be reduced to an "interior point problem"—finding a point that lies between the minimum and maximum elements of a dataset. If the domain is massive or infinite, the number of possible configurations grows exponentially. Consequently, the algorithm requires more samples to safely "mask" the impact of any single point without destroying the utility of the threshold.
Feldman et al. 2015 framed this through the lens of communication complexity, demonstrating that private learning requirements scale directly with the bit-representation length of the input domain. Privacy forces the learner to account for the total number of possible inputs, a stark contrast to non-private learning which only cares about the structure of the function class.
The Infinite Domain Barrier and the Littlestone Dimension
This domain dependency is not just a loose upper bound; it is a hard mathematical limit. Bun et al. 2015 proved a lower bound of $\Omega(\log^* |X|)$ samples for releasing threshold functions, where $\log^*$ is the iterated logarithm.
This connection was deeply formalized by Alon et al. 2018, who established a profound equivalence: a hypothesis class is privately learnable under approximate DP if and only if it has a finite Littlestone dimension (a combinatorial measure originally used to characterize online learning). Because threshold functions over an infinite domain have an infinite Littlestone dimension, the authors proved that they cannot be learned privately without restricting the set of possible distributions.
This impossibility extends across various domains of private statistics. For instance, Sheffet et al. 2024 showed that releasing basic statistical properties or performing equivalence testing is impossible over infinite domains without imposing specific constraints or discretization techniques.
Algorithmic Upper Bounds: Navigating the Scaling Cost
Despite this barrier, researchers have designed sophisticated algorithms to minimize the domain-size penalty for finite but large domains. For years, an exponential gap remained between the $\Omega(\log^* |X|)$ lower bound and existing upper bounds.
This gap was nearly closed by Kaplan et al. 2020, who introduced a recursive domain-shrinking algorithm called TreeLog. By recursively pruning the domain space, the authors brought the sample complexity upper bound down to $\tilde{O}((\log^* |X|)^{1.5})$.
The domain-size penalty also appears in higher-dimensional geometric problems. Beimel et al. 2019 demonstrated that the sample complexity for learning halfspaces scales with the size of the underlying coordinate system. Similarly, in clustering, Nissim et al. 2016 showed that private algorithms for locating a small cluster must maintain at least a logarithmic relationship with the domain size, preventing a purely domain-agnostic approach.
Even refined privacy definitions like Zero-Concentrated Differential Privacy (zCDP), introduced by Bun et al. 2016, face similar efficiency losses where sample sizes must scale with the domain size for basic histogram queries.
Circumventing the Barrier via Smoothed Analysis
If domain-dependent scaling makes private learning impractical for continuous or high-dimensional spaces, how can we apply differential privacy to real-world data?
One powerful resolution comes from changing the game's rules via smoothed analysis. Haghtalab et al. 2020 demonstrated that the worst-case impossibility results can be bypassed if we assume nature adds a small amount of adversarial noise to the data. Under this smoothed analysis framework, the sample complexity of private learning algorithms shifts from depending on the restrictive Littlestone dimension (and thus the domain size) to depending purely on the standard VC dimension. This insight provides a theoretical bridge, allowing efficient private learning even in continuous or infinite data universes.
Key Foundational Work
Differentially Private Release and Learning of Threshold Functions (2015) — contributed 4 concept elements to this direction.
Locating a Small Cluster Privately (2016) — contributed 3 concept elements to this direction.
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity (2015) — contributed 2 concept elements to this direction.