A Sharp Dynamic Haussler Lemma

Introduction

How many predictors are needed to approximate an entire function class? In the classical setting, Haussler’s covering lemma [16] gives a sharp answer for binary classes. For every class $\mathcal{H} \subseteq\{0,1\}^{\mathcal{X}}$ of VC dimension $d$, every finite instance sequence $x_1,\ldots,x_T$, and every $0 < \delta< 1$, there is a set of at most $(C/\delta)^d$ representatives such that each target in $\mathcal{H}$ disagrees with some representative on at most $\delta T$ positions. The bound is independent of the sequence length, and the exponent is exactly the combinatorial dimension. VC dimension originated in uniform-convergence theory [33] and became a central parameter in distribution-free PAC learnability [7]. The connection between combinatorial dimensions and metric entropy extends to real-valued function classes [21] and plays a central role in uniform convergence and generalization [34, 9]. More broadly, metric entropy underlies chaining bounds for stochastic processes [14, 32].

The classical cover may be chosen after the entire instance sequence is known. Such hindsight dependence is unsuitable for online prediction, where future instances are unavailable. To eliminate this dependence, one may instead maintain a bounded number of candidate prediction streams, updating their predictions as instances arrive. This leads to the notion of a causal expert, whose prediction at time $t$ may depend on the observed prefix $x_1,\ldots,x_t$. We ask whether a single finite family of such experts, specified in advance, can approximate every target on every possible input sequence. This global guarantee requires consistency across different sequences: whenever two sequences share a prefix, each expert must make identical predictions along that prefix.

We study this question for bounded real-valued classes, measuring approximation in normalized $\ell_p$ distance for any $1 \le p < \infty$. Let $\mathcal{F} \subseteq[0,1]^{\mathcal{X}}$ be nonempty, and fix a horizon $T \ge1$. A deterministic causal expert is a tuple $g=(g_t)_{t=1}^{T}$ with $g_t:\mathcal{X}^{t}\to[0,1]$. A finite family $\mathcal{G}$ is a global dynamic $\ell_p$ cover at accuracy $\varepsilon$ if

We write $N_p^{\mathrm{dyn}}(\mathcal{F},\varepsilon,T)$ for the smallest cardinality of such a family. The family may depend on $\mathcal{F}$, $p$, $\varepsilon$, and $T$, but is fixed before the instances are revealed. Its experts receive no target values, and the expert witnessing the approximation may depend on both the target and the entire sequence. Thus global refers to a single family that works on all instance sequences; integral refers to an actual finite family of experts.

Sequential covering has a substantial history. The Littlestone dimension characterizes the optimal deterministic mistake bound in realizable online learning [18]. Extending this characterization to agnostic online learning, Ben-David, Pál, and Shalev-Shwartz Ben-David, Pál, and Shalev-Shwartz [10] constructed a global exact cover for every binary class of Littlestone dimension $d$, consisting of at most $\sum_{i=0}^{\min\{d,T\}}\binom{T}{i}$ deterministic causal experts. Allowing a positive error rate suggests that the dependence on $T$ might disappear. In the real-valued setting, Rakhlin, Sridharan, and Tewari Rakhlin, Sridharan, and Tewari [23, 25, 26] developed sequential covering numbers and asked for an $\ell_2$ bound independent of the horizon. Related sequential complexity methods also apply to objectives beyond external regret, including calibration and approachability [24]. Sequential covering numbers also have direct applications to online prediction. Rakhlin and Sridharan Rakhlin and Sridharan [22] established optimal regret rates for online nonparametric regression in terms of sequential entropy. Gaillard and Gerchinovitz Gaillard and Gerchinovitz [15] subsequently developed chaining-based forecasters with entropy-dependent regret guarantees. The global approximate covering question for binary classes was posed in [2], and Malliaris and Moran Malliaris and Moran [19] explicitly asked for a dynamic analogue of Haussler’s lemma. Horizon-independent fractional covering bounds were established for global binary covering by Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev [2] and for tree-dependent real-valued sequential covering by Block, Dagan, and Rakhlin [5]. The former provides one distribution over causal experts, whereas the latter allows the distribution to depend on the prescribed instance tree. Haussler’s lemma, however, guarantees an actual finite family of representatives. A sharp, horizon-independent integral dynamic analogue, together with its extension to real-valued classes, has remained open.

Our Contributions

We establish a sharp global dynamic covering theorem for bounded real-valued classes, uniformly over all finite $p \ge1$. The controlling parameter is the sequential fat-shattering dimension $\operatorname{sfat}_{\eta}(\mathcal{F})$, the scale-sensitive sequential analogue of VC dimension. Informally, it is the maximum depth of a complete binary instance tree on which every path can be realized by a function in $\mathcal{F}$, with the two alternatives at each node separated by a gap $\eta$ around a node-dependent threshold. For binary classes, this dimension equals Littlestone dimension at every scale $0 < \eta\le1$. The precise definition is given in the preliminaries.

The theorem identifies the exact worst-case accuracy exponent $pd$, with universal constants in the base. The more precise upper bound (3) retains $d$ as the outer exponent and has a base constant independent also of $p$. Thus the bounds for $p = 1$ and $p = 2$ are $(C/\varepsilon)^d$ and $(C/\varepsilon^2)^d$, respectively. In every case, the dimension is measured at scale $\varepsilon/32$, corresponding to pointwise accuracy, while the mean $p$th-power error budget is $\varepsilon^p$.

The lower bound is given by indicators of affine hyperplanes over a finite field. On one fixed instance sequence, their prediction vectors form a normalized $\ell_p$ packing with separation greater than $2\varepsilon$. Since the $p$th power of the normalized $\ell_p$ distance between binary vectors equals their normalized Hamming distance, the same construction explains the exponent $pd$ for every finite $p$. The triangle inequality shows that even a real-valued expert can cover at most one vector in this packing.

Sequential covering and the $p = 2$ problem. Restricting every global expert to a fixed instance tree gives a sequential cover on that tree, with the same cardinality. Theorem 1 therefore yields horizon-independent integral sequential $\ell_p$ covers for every $1 \le p < \infty$. In particular, its $p = 2$ case resolves the sequential $\ell_2$ covering question of Rakhlin, Sridharan, and Tewari [26] in a stronger global form: a single family of causal experts, fixed independently of the instance sequence, suffices to approximate every target on every possible sequence. It supplies an integral covering theorem alongside the fractional result of Block, Dagan, and Rakhlin [5].

Binary classes and the $p = 1$ case. For a binary class $\mathcal{H}$ of Littlestone dimension $d$, the $p = 1$ case yields a family of at most $(C'/\delta)^d$ binary causal experts such that

for every $0 < \delta< 1/4$. Indeed, apply (3) with $p = 1$ and $\epsilon= \delta/2$, then round each prediction at $1/2$. Each binary mistake contributes at least $1/2$ to the original absolute error, so the number of mistakes is at most $\delta T$. The finite-field construction gives a matching worst-case lower bound $(c'/\delta)^d$. This settles the global dynamic covering question posed in [2] and the dynamic Haussler problem of Malliaris and Moran [19]. A global cover also supplies a finite reference family for prediction-with-expert-advice methods [12], although our theorem does not address efficient construction of the experts.

Proof ideas. Our proof first establishes an outlier cover of size $(C_0R)^d$ for a uniformly separated class, with pointwise error at least $8\eta$ on fewer than $T/(8R)$ rounds. Setting $\eta= \epsilon/32$, passing to a maximal uniformly $\eta$-separated subclass of $\mathcal{F}$, and choosing $R = 16/\epsilon^p$ then yields mean $p$th-power error at most $(9\epsilon/32)^p + \epsilon^p/128 < \epsilon^p$ for the original class. This gives the bound $(16C_0/\epsilon^p)^d$ for every finite $p$.

To obtain the outlier guarantee, SOA-style predictions and correction schedules implement rank-decreasing version-space updates without target labels. A common master and tolerant replays across short sampling pools give each target many accurate histories. A pool identifies a function when a robust certificate isolates it in a singleton version space; the function activates once identified by at least half the pools. Bounds on the number of functions each pool can certify within a low-rank version space, combined with this activation threshold, limit how many activated targets can be eligible for any given parent.

Rather than retaining every full schedule as an expert, we use parent schedules to cover unactivated targets or provide accurate prefixes for activated ones. Each activated target has many eligible parents but needs only one exact continuation. Shared-parent routing spreads these requests, avoiding worst-case concentration on individual parents and reducing their leading continuation capacity by a factor proportional to the number of pools. This eliminates the logarithmic overhead. A finite-horizon game argument then yields a deterministic global cover.

Historical Context and Related Work

Two distinctions clarify the relation between our theorem and earlier covering results: whether the cover may depend on a prescribed instance sequence or tree, and whether covering is witnessed by finitely many representatives or by a probability measure assigning uniformly positive mass to successful approximations.

Static, sequential, and global covers. In Haussler’s classical theorem [16], the representatives may be chosen after the sample is specified. The sequential covers of Rakhlin, Sridharan, and Tewari [26] are instead defined on a fixed binary instance tree $x$. A cover is a finite family $\mathcal{V}_x$ of real-valued prediction trees such that, for every target $f$ and every root-to-leaf path $\sigma$, some $v \in\mathcal{V}_x$ approximates the target trace along that path. The family may depend on the entire instance tree, including nodes outside the realized path. The distinction is captured by the following quantifier orders

In the first line, accuracy is measured on the path $\sigma$ of $x$; the second line has the accuracy requirement in (1). In both cases the witnessing member may depend on the target and the complete path or sequence. The global formulation additionally specifies consistent predictions on every shared instance prefix, across all input sequences. Restricting a global family to a tree gives a sequential cover of the same size. Taking a supremum of sequential covering numbers over trees does not, by itself, interchange the first two quantifiers.

Globality is already present in the exact binary expert construction of Ben-David, Pál, and Shalev-Shwartz [10], whose size grows with $T$, and in the fractional dynamic covers of [2]. The global approximate covering questions in [2, 19] ask for a horizon-independent finite family. Our theorem supplies such a family with the sharp dimension and accuracy dependence, and extends the guarantee to bounded real-valued classes.

These questions also connect online learning to model-theoretic stability. Malliaris and Shelah [20] established regularity lemmas for stable graphs, while Malliaris and Moran [19] subsequently studied excellent sets through agnostic online learning.

Real-valued metric entropy. Scale-sensitive dimensions have long been used to control static covering numbers for real-valued function classes, both on finite samples and under distribution-dependent metrics [3, 6, 21]. Empirical entropy also yields oracle inequalities and risk bounds for nonparametric regression [27]. Recently, Aiyer, Mansour, Moran, Shao, and Waknine [1] obtained sharp results for empirical $\ell_\infty$ covering numbers at optimal scales. In these settings, covering families may depend on the sample or probability measure defining the metric. Our theorem instead provides a single finite family of causal experts, with sharp global dynamic bounds in every finite $\ell_p$ metric.

Geometric refinements. Haussler’s static packing bound has also been refined for shallow geometric set systems [13]. These refinements exploit additional structure of static set systems, whereas our focus is global causal covering.

Fractional and integral covering. For a target–sequence pair $(f, x_{1:T})$, let $B_\varepsilon(f, x_{1:T})$ be the set of causal experts satisfying the error bound in (1) for that pair. A global fractional cover of size $\Gamma\ge1$ is a probability measure $\mu$, fixed independently of the input sequence, such that

This is the probability-mass formulation used for binary dynamic covers in [2]. A tree-dependent fractional cover instead chooses a measure $\mu_x$ on prediction trees for each fixed $x$, and imposes the same mass condition for every target and path on that tree, as in Bloch, Dagan, and Rakhlin [5].

An integral cover requires an actual finite family $\mathcal{G}$ intersecting every set $B_\varepsilon(f, x_{1:T})$. The uniform distribution on a family of size $K$ satisfies (6) with $\Gamma= K$. The converse is not immediate: $\Gamma$ controls the reciprocal of the mass of each successful set, rather than the cardinality of the support of $\mu$. In particular, even a finitely supported fractional cover need not have support of size at most $\Gamma$. Here integral concerns the selection of representatives; the representatives themselves may make real-valued predictions.