PaperlayerView exact revision on arXiv

Source-linked AI summary

A Sharp Dynamic Haussler Lemma

Shihao Shao, Dacheng Tao

arXiv:2610.29898v1cs.LGcs.DS

TL;DR

The paper asks whether one fixed family of causal experts can cover every target across all instance sequences, rather than choosing a cover after the sequence is known. It develops a global dynamic covering approach for bounded real-valued classes using sequential fat-shattering dimension, and states a horizon-independent global covering theorem.

  • Problem

    Prior covers may depend on the sequence or tree, and known fractional bounds do not directly yield finite global integral covers without a logarithmic overhead.

    Source: §1 · p. 3, §1.2 · p. 7

  • Method

    The proof uses a separated subclass and outlier reduction, with shared-parent routing to distribute continuations across compatible sampled histories.

    Source: §2.1 · pp. 7–8, §1.2 · p. 7

  • Results

    The paper states a global dynamic covering theorem for bounded real-valued classes with finite sequential fat-shattering dimension, for every finite p and horizon.

    Source: §1.1 · p. 4, §3.3 · p. 14

  • Takeaways & Limitations

    A single family of causal experts fixed independently of the instance sequence is the paper’s global covering guarantee.

    Source: §1 · p. 3

    The identification conditions are defined set-theoretically and are not required to be efficiently computable.

    Source: §6.1 · p. 33

Abstract

from arXiv · show

Haussler's covering lemma (JCTA 1995) gives the sharp $(C/\delta)^d$ metric-entropy bound for binary VC classes under normalized $\ell_1$ distance. We prove a sharp global dynamic analogue for bounded real-valued classes in normalized $\ell_p$, for every $1\le p<\infty$. Writing $d=\operatorname{sfat}_{\varepsilon/32}(\mathcal F)$, we obtain a global dynamic cover of size at most $(C/\varepsilon^p)^d$ for every horizon and $0<\varepsilon<1/2$. Here a single family of deterministic causal experts, fixed independently of the instance sequence, covers every target on every sequence. For $0<\varepsilon<1/4$, a matching worst-case lower bound $(c/\varepsilon)^{pd}$ holds already for binary classes on one fixed sequence, even with real-valued experts. The constants are universal, independent of $p$. For $p=2$, this resolves the horizon-independent sequential $\ell_2$ covering problem of Rakhlin, Sridharan, and Tewari (PTRF 2015) in a stronger global form. For $p=1$, it gives the sharp $(C/\delta)^{\operatorname{Ldim}(\mathcal H)}$ global dynamic covering bound for binary classes, resolving questions of Alon, Ben-Eliezer, Dagan, Moran, Naor, and Yogev (STOC 2021) and Malliaris and Moran (Trans. AMS 2024). Our proof combines rank-decreasing correction schedules and accurate sampled prefixes with exact continuations after target identification. Shared-parent routing distributes these continuations among eligible prefixes, eliminating the logarithmic overhead.

1 Introduction

The introduction asks whether a single sequence-independent family of causal experts can approximate every target across all instance sequences. It presents a sharp dynamic covering theorem for bounded real-valued classes and explains how its global, integral guarantee differs from prior covers.

1 Introduction

  • The global guarantee requires one fixed family whose experts predict consistently on shared prefixes, unlike a cover chosen after seeing the sequence.The motivating classical Haussler cover may depend on the entire instance sequence.Source: §1 · pp. 3–4

1.1 Our Contributions

  • For every finite p ≥ 1, the paper gives horizon-independent global dynamic covers for bounded real-valued classes, controlled by sequential fat-shattering dimension at scale ε/32.The stated accuracy range is 0 < ε < 1/2; the constants are universal and independent of p, d, T, and ε.Source: §1.1 · p. 4
  • The p = 2 theorem gives horizon-independent integral sequential ℓ2 covers in a stronger global form than the tree-dependent result of Block, Dagan, and Rakhlin [BDR21].It resolves the sequential ℓ2 covering question of Rakhlin, Sridharan, and Tewari.Source: §1.1 · p. 4
  • For binary classes, the p = 1 case yields a sharp global dynamic covering bound in terms of Littlestone dimension, addressing questions of Alon et al. [Alo+21] and Malliaris and Moran.The binary-class construction also gives a matching worst-case lower bound.Source: §1.1 · p. 5
  • Shared-parent routing distributes exact continuations across eligible prefixes, eliminating the logarithmic overhead while supporting a deterministic global cover.The proof also uses rank-decreasing correction schedules and tolerant replays to produce accurate histories without target labels.Source: §1.1 · p. 5

1.2 Historical Context and Related Work

  • Earlier sequential covers can depend on a fixed instance tree, while fractional covers do not directly provide finite global integral families without a logarithmic overhead.The paper uses shared-parent routing rather than a general fractional-to-integral conversion.Source: §1.2 · pp. 5–7

2 Technical Overview

The proof builds global dynamic covers from rank-decreasing correction schedules, accurate sampled prefixes, and exact continuations after target identification. Shared-parent routing removes the logarithmic overhead, while a finite-horizon game argument yields deterministic experts and a matching lower bound holds on one fixed sequence.

2 Technical Overview

  • Correction schedules use SOA-style predictions and rank-decreasing version-space updates; once a target is identified, an exact continuation preserves its accurate past.Children copy parent outputs until assigned to an activated function, then predict that function exactly from the assignment round onward.Source: §2 · p. 7, §2.1 · p. 8, §2.3 · pp. 9–10

2.1 Outlier Reduction and Correction Schedules

  • Rank-decreasing correction schedules encode at most d updates without target labels, giving a global outlier cover fixed independently of the instance sequence.For the ℓp upper bound, uniform separation at η = ε/32 and an outlier budget R = 16/ε^p give a cover of size at most (16C0/ε^p)^d.Source: §2.1 · pp. 7–8

2.2 From One Pool to Many Short Pools

  • Multiple short pools provide many accurate histories per target, but retaining every pool’s schedules costs an extra factor of log R.The common master and tolerant replays give each target at least 3k/4 accurate histories with fewer than b/8 outliers, with probability above 15/16.Source: §2.2 · p. 9

2.3 Shared-Parent Routing and Sharp Counting

  • Shared-parent routing cancels the factor from maintaining multiple pools, reducing the continuation capacity required per parent and eliminating the logarithmic overhead.Activated targets have many eligible parents but need only one exact continuation.Source: §2.2 · p. 9, §2.3 · pp. 10–11

2.4 Simultaneous Accuracy and Global Determinization

  • A finite-horizon game argument turns positive-probability simultaneous coverage, even against adaptive inputs, into a deterministic global family of causal experts.On the successful event, activated targets receive exact continuations from accurate prefixes; unactivated targets have accurate parent schedules.Source: §2.3 · pp. 9–10, §2.4 · p. 12

2.5 The Matching Lower Bound

  • The matching lower bound uses binary classes on one fixed sequence, where even real-valued covering vectors cannot cover more than one trace.Hyperplane indicators yield a packing with separation greater than 2ε, establishing the exponent pd.Source: §2.5 · pp. 12–13

3 Definitions and Main Results

The section defines the sequential complexity and global dynamic cover used in the paper, then states sharp upper and lower bounds and consequences for binary and sequential covers. The bounds are horizon-independent, with accuracy dependence governed by the sequential fat-shattering dimension.

3.1 Sequential Fat-Shattering Dimension

  • Sequential fat-shattering dimension measures the depth of a tree whose two branches are separated around node-dependent thresholds; for binary classes it equals Littlestone dimension.The definition uses a margin η/2 on each side of the threshold, leaving a gap η between branches.Source: §3.1 · p. 13

3.2 Global Dynamic Covering Numbers

  • A global dynamic cover is a finite family of causal experts fixed before instances are revealed, with one expert approximating each target on each sequence.The witnessing expert may depend on the target and the complete sequence, and need not be identifiable online.Source: §3.2 · p. 14

3.3 Sharp Upper and Lower Bounds

  • The constant C is independent of p, d, T, ε, and the class; when d = 0, the covering number is exactly one.Source: §3.3 · p. 14
  • For every finite p ≥ 1, the lower bound holds for a binary class on one fixed sequence, even when covering predictions may be real-valued.The class and sequence may depend on p, d, and ε; this is a worst-case, not per-class, lower bound.Source: §3.3 · p. 15

3.4 Binary Classes and Sequential Covering

  • For every binary class H with finite Littlestone dimension d, T ≥ 1, and 0 < δ < 1, a sharp global dynamic cover by causal binary experts achieves normalized Hamming error at most δ with size at most (Cbin/δ)^d, where Cbin = 2C.Source: §3.4 · p. 16

4 Correction Schedules and Adaptive Sampling

This section develops rank-decreasing causal correction schedules and adaptive sampling on histories, with prediction rules independent of target values. It preserves predictability when conditioning on the sampled union and uses a red–blue discrepancy bound to apply schedule-specific correction guarantees to every target.

4.1 Separation and Rank-Decreasing Centers

  • A uniformly η-separated subclass approximates every function within η, and a separated rank-zero class is covered exactly by its unique member.The reduction applies even to infinite classes; separation also yields the d = 0 case of the upper-bound proposition.Source: §4.1 · pp. 17–18
  • Rank-decreasing centers make each sufficiently separated sign update lower sequential fat-shattering rank by at least one.Gluing two shattered trees below a common root supplies the key rank argument; thus a rank-r version space permits at most r valid updates.Source: §4.1 · pp. 18–19

4.2 Correction Schedules and Pointwise Covers

  • Schedules of at most r signed corrections form a fixed family of at most Qr(m) causal experts that achieves pointwise error at most η on every selected round.The family covers every target in the initial version space; repeated selected-round ordinals are allowed, and the witnessing schedule is chosen without giving target values to its expert.Source: §4.2 · pp. 19–20

4.3 Partial Binary Completion and Adaptive Sampling

  • Partial error labels use 0 for discrepancies at most η, 1 for discrepancies at least 2η, and ∗ in between; their Littlestone dimension is controlled by sequential fat-shattering at scale η.Finite causal completion families match every defined label, and the adaptive low-hit sampling lemma applies when inputs depend on earlier Bernoulli-γ selections, with γ ≤ 1/2.Source: §4.3 · pp. 21–23
  • Conditioning on the sampled union leaves independent fair colors, while the compressed input stream remains predictable from preceding colors.Generate independent union bits with inclusion probability 2γ, then assign each included round an independent fair red-or-blue color.Source: §4.3 · p. 24
  • On E′, a rule from the fixed family V matches all defined labels and has at least γB/4 blue ones and at most q red ones.The family contains at most Sr(M) deterministic binary causal rules; matching blue definite ones forces the blue count, while red ones are bounded by the target’s red nonzero count.Source: §4.3 · p. 24
  • A nonnegative martingale controls each rule’s red–blue discrepancy, and a union bound over V and union patterns yields the asserted bound conditional on ω.Each rule’s next prediction precedes the color reveal; Markov’s inequality and the union bound complete the estimate.Source: §4.3 · pp. 24–25
  • For a target’s reference schedule, each sampled nonzero partial error requires a correction, so its count is at most d; a union bound over schedules extends the guarantee to every target.The schedule stream pairs each instance with its provisional prediction, and sampled nonzero values record one-sided provisional errors exceeding η.Source: §4.3 · p. 25

5 Master Histories and Multi-Pool Accuracy

The section constructs a target-dependent analytical master and tolerant replays across multiple sampling pools, reproducing target-driven schedules on capped selection histories. These yield uniform master accuracy and, on a common event of probability greater than 15/16 under a universal parameter choice, accurate schedules on at least 3k/4 pools for every target, with target constraints satisfied by a positive margin.

5.1 The Analytical Master and Uniform Accuracy

  • Every update retains h and decreases the sequential fat rank; therefore, the procedure makes at most d corrections over the entire horizon.Source: §5.1 · p. 27

5.2 Tolerant Replay and Buffered Corrections

  • The 4η-tolerant replay retains each target, makes at most d corrections, and performs each correction only when the target value is more than 3η from the replay center.Each correction strictly decreases rank; on selected rounds the replay terminates within 4η of the master’s final value.Source: §5.2 · p. 29
  • Charging large selected disagreements to master or replay corrections bounds charged rounds by 2d; when D_j < b/16, both outlier counts are below 3b/32 < b/8.On Master, final replay errors of size at least 8η can occur only on unselected rounds, where provisional and final predictions agree.Source: §5.2 · p. 30

5.3 Simultaneous Accuracy Across Pools

  • With probability greater than 15/16, every target has at least 3k/4 pools satisfying the simultaneous replay-accuracy guarantee.The proposition holds for every allowed input rule in the regime b > 32αd.Source: §5.3 · p. 31
  • A sufficiently large universal α ensures Pr(Good) > 15/16, independently of the input rule and the law of its independent auxiliary seed.The same probability bound applies in both the union and all-round regimes.Source: §5.3 · pp. 31–32
  • On Good, every target has at least 3k/4 accurate schedules across the pools.The conclusion holds for all targets on every outcome in Good.Source: §5.3 · pp. 31–32
  • On Cap, each target-driven replay is reproduced by a sign schedule of depth at most d on its pool’s capped selection history.This transfers replay accuracy to schedules on the corresponding pool histories.Source: §5.3 · p. 32

6 Robust Identification and Eligible Parents

The section turns robust schedule certificates into bounded local identification and activation, then uses parent schedules and child experts to cover targets whether or not they activate.

6.1 Robust Identification and Local Counting

  • Robust certificates impose a 2η margin beyond each retained update boundary, and their tests require no externally supplied target labels.The conditions are set-theoretic and need not be efficiently computable.Source: §6.1 · p. 33
  • A pool identifies at most Qr(m) functions within any subclass of sequential fat-shattering dimension at most r.The proof separates identified functions by more than 2η on a selected instance and applies a covering bound to those instances.Source: §6.1 · p. 34
  • Requiring identification by at least k/2 pools yields at most 2Qd(m) activated functions overall.Identification persists after activation, enabling the count across pools.Source: §6.1 · p. 34

6.2 Parent and Child Experts

  • Preallocated parents follow fixed sign schedules, while each child copies its parent until assignment and then predicts its assigned target exactly.Assignment does not change any past prediction.Source: §6.2 · p. 35

6.3 Eligibility and Many Compatible Parents

  • On Good, every activating target has more than k/4 eligible parents, with one selected representative from each eligible pool.Eligibility is determined at activation from past predictions and does not use future instances or future accuracy.Source: §6.3 · pp. 36–37
  • A target that never activates has an accurate permanent parent, while an activated target can receive an eligible parent’s child for exact continuation.The section leaves capacity selection and distribution of activations to the routing analysis.Source: §6.3 · p. 37

7 Shared-Parent Routing and Load Balancing

The section routes activated targets among compatible parents and bounds parent loads so child capacities suffice. On Good and NoOverload, every activation receives an unused child.

7 Shared-Parent Routing and Load Balancing

  • Shared-parent routing selects among eligible parents, distributing one-per-target continuations across compatible sampled histories.Each activation chooses uniformly from its retained eligible set when that set has at least k/4 members.Source: §7 · p. 38, §7.1 · p. 38

7.1 The Causal Routing Protocol

  • The causal protocol reveals fresh routing permutations after each round’s instance and schedule updates, while inputs are chosen before current randomness is revealed.The sampling guarantee gives Pr(Good) > 15/16 for the routing protocol.Source: §7.1 · pp. 38–39

7.2 Routing Probabilities and Load Bounds

  • An exponential-moment bound on parent loads supports capacities chosen to control overload, even when later inputs depend on earlier routing choices.On Good ∩ NoOverload, every activating function receives an unused child on its activation round.Source: §7.2 · pp. 39–41

8 Expert Counting and Global Determinization

Section 8 counts a finite family of parent and child indices and establishes simultaneous coverage for every target. A finite-horizon game argument then turns randomized coverage into deterministic causal experts fixed independently of the instance sequence.

8.1 Expert Counting and Simultaneous Coverage

  • The expert count is bounded by a universal-constant multiple of the rank-dependent budget, with logarithmic and rounding overhead absorbed into the count.The depth-i parent factor cancels the reciprocal factor in child capacity; the resulting constants are universal.Source: §8.1 · pp. 41–42
  • The preallocated parent and child indices suffice for simultaneous coverage: each target has a witnessing index, whether it activates or not.Activated targets use an eligible parent’s routed child; nonactivated targets use a parent supplied by Corollary 27.Source: §8.1 · p. 42

8.2 Game Determinization and Main Upper Bound

  • A finite-horizon game argument converts randomized success against every deterministic adversary into a deterministic constructor strategy that wins against every adversary.Backward induction establishes the deterministic strategy; its actions and predictions through each round depend only on the observed input prefix.Source: §8.2 · pp. 43–44
  • The resulting causal family is fixed independently of the instance sequence and has size at most (16C0/ε^p)^d.Here d = sfat_(ε/32)(F); the proof handles d = 0 with one expert and uses a separated subclass when d ≥ 1.Source: §8.2 · pp. 44–45

9 Matching Lower Bounds

Section 9 constructs a finite-field hyperplane class with Littlestone dimension d, then packs its indicators on one fixed sequence. The packing yields a lower bound even for real-valued covering experts.

9.1 Finite-Field Hyperplanes and Their Dimensions

  • The affine-hyperplane indicator class over F_q has Littlestone dimension d.A predictor that maintains the affine span of positive examples makes at most d mistakes, while the standard basis points are shattered to depth d.Source: §9.1 · pp. 45–46

9.2 Fixed-Sequence Packing and Lower Bound

  • On the sequence listing every domain point once, normalized ℓ_p distance between hyperplane indicators is determined by the fraction of points in their symmetric difference.The identity holds for every finite p because binary differences raised to p are 1 exactly where the indicators disagree.Source: §9.2 · p. 46
  • Choosing the field size to ensure separation gives the matching worst-case lower bound from the size of the hyperplane class.The construction uses the class’s scale-ε/32 dimension d on the sequence of all q^d domain points.Source: §9.2 · pp. 46–47
  • Distinct hyperplanes are separated on that fixed sequence, so a real-valued prediction vector can cover at most one indicator within error ε.The triangle inequality would otherwise contradict the pairwise separation.Source: §9.2 · p. 47

AI Disclosure

The authors disclose using ChatGPT 6 Pro during technical development and manuscript preparation.

AI Disclosure

  • The authors report using ChatGPT 6 Pro for discussions and iterative refinement of routing and parameter choices, manuscript organization, and clarity; they take responsibility for the paper’s content and proofs.The disclosure states that the authors take full responsibility for correctness.Source: AI Disclosure · p. 47
Loading 2610.29898v1…