In classical learning theory, the Vapnik-Chervonenkis (VC) dimension is the gold standard for characterizing learnability. If a hypothesis class has a finite VC dimension, it can be learned via the Probably Approximately Correct (PAC) framework; if it is infinite, it cannot.
However, when we introduce the constraint of Differential Privacy (DP)—which requires that a trained model does not reveal whether any single individual's data was included in the training set—the predictive power of the VC dimension breaks down. As demonstrated by Brenner et al. (2014), the VC dimension fails to provide tight sample complexity bounds for private learning. Some simple concept classes with a VC dimension of one require an arbitrarily large volume of training data, or are entirely unlearnable, when privacy is mandated.
This discrepancy left a fundamental question open: What is the true combinatorial yardstick that characterizes private learnability? The answer came from a surprising connection to an entirely different paradigm: online learning.
The Bridge: Littlestone Dimension
In online learning, an algorithm receives examples sequentially and must make a prediction for each instance before seeing the true label, aiming to minimize its total number of mistakes. The complexity of this setting is governed by the Littlestone dimension, which measures the depth of the largest binary tree of instances whose labels can be completely "shattered" by the hypothesis class.
Intuitively, the Littlestone dimension captures how severely an adaptive adversary can force a sequential learner to make mistakes. Feldman et al. (2015) showed that this online metric provides a fundamental lower bound for the sample complexity of private learning algorithms. If a concept class is difficult to learn in an online, mistake-bound setting, it inherently requires more data to be learned under differential privacy.
This connection was solidified into a necessary condition for privacy by Alon et al. (2018). The authors proved that a finite Littlestone dimension is required for approximate differentially private PAC learning. For example, they showed that the class of 1D thresholds over an infinite domain—which has a VC dimension of one but an infinite Littlestone dimension—cannot be learned with approximate differential privacy.
Standard PAC Learning ◄───► VC Dimension
│
▼ (Fails under privacy)
Private PAC Learning ◄───► Littlestone Dimension ◄───► Online Learning
Why Stability Connects Privacy and Sequential Learning
To understand why a metric designed for sequential mistakes dictates the feasibility of data privacy, we must look at the core mechanism underlying both paradigms: algorithmic stability.
Differential privacy fundamentally demands that a learning algorithm's output distribution changes very little if a single training sample is added, removed, or modified. This means the algorithm cannot over-index or "memorize" specific individual data points; it must rely strictly on global, stable patterns.
Now consider online learning. If a concept class has a high Littlestone dimension, an adversary can construct a tree of instances where every path forces the learner to flip its predictions repeatedly based on the historical sequence. To achieve a bounded number of mistakes, an online learner must be capable of converging to a stable hypothesis that resists being derailed by localized, adversarial updates.
Thus, both private learning and online learning are constrained by the same bottleneck: the capacity of a hypothesis class to resist drastic shifts from localized data variations. This deep structural connection culminated in a landmark result by Bun et al. (2020), who established a complete qualitative equivalence for binary classification: a concept class is privately learnable if and only if it is online learnable.
Generalizing the Equivalence
Following the binary classification breakthrough, researchers sought to determine whether this equivalence represents a universal law of learning theory.
Multiclass and Regression
The equivalence is not an artifact of binary labels. Jung et al. (2020) and Sivakumar et al. (2021) extended the online-to-private mapping to multi-class classification and regression tasks. In these settings, private learnability remains tightly bound to the Littlestone dimension or its continuous analogue, the fat-shattering dimension with tolerance.
Private Online Learning
The connection also operates in reverse: if a class has a finite Littlestone dimension, can we learn it both online and privately at the same time? Golowich et al. (2021) and Li et al. (2025) proved that a finite Littlestone dimension is indeed necessary and sufficient for private online learning, even when facing adaptive adversaries.
Graph-Theoretic Unification
Recently, Alon et al. (2024) provided a unified graph-theoretic framework showing that learnability under approximate differential privacy is determined by the growth rate of the largest set of mutually contradicting datasets (the clique number of a specific dataset graph). This framework provides a direct quantitative bridge back to the Littlestone dimension, proving that the combinatorial obstacles to learning from sequential data are fundamentally identical to those that prevent privacy-preserving learning.
Where the Equivalence Diverges
While the information-theoretic boundaries of private and online learning align perfectly for standard classification, the equivalence collapses when we change the computational or structural rules of the game.
Computational Hardness
Information-theoretically, the classes of functions learnable in both settings are identical. However, Bun et al. (2024) demonstrated that polynomial-time online learnability and polynomial-time differentially private PAC learnability are computationally incomparable. There is no generic, efficient method to transform an online learning algorithm into a differentially private one, meaning the equivalence is strictly an information-theoretic phenomenon.
List Learning
When the learning objective shifts from predicting a single label to outputting a short "list" of candidate labels, the equivalence breaks down completely. As shown by Hanneke et al. (2025), online list learnability is a strictly weaker property than private list learnability. Private list learning is subject to a broader set of combinatorial constraints, requiring the finiteness of both tree-based and monotone-based dimensions.
The Cost of Continual Observation
In purely online environments, adding privacy constraints introduces a fundamental complexity shift. While a non-private online learner can achieve mistake bounds independent of the time horizon, Cohen et al. (2024) showed that a private online learner's mistake bound must scale logarithmically with the time horizon. This reveals that while the feasibility of learning is identical between the two fields, maintaining privacy over streaming data over time incurs a persistent efficiency penalty.
Key Foundational Work
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity (2015) — contributed 2 concept elements to this direction.
Bounds on the sample complexity for private learning and private data release (2014) — contributed 1 concept elements to this direction.
Characterizing the Sample Complexity of Private Learners (2014) — contributed 1 concept elements to this direction.