Optimistic Rates for Multiclass PAC Learning

Optimistic Rates for Multiclass PAC Learning Xiaoyu Li1

Andi Han2

1 University of New South Wales 2 University of Sydney

Jiaojiao Jiang1

Junbin Gao2

{xiaoyu.li2,jiaojiao.jiang}@unsw.edu.au {andi.han,junbin.gao}@sydney.edu.au

arXiv:2608.10869v1 [cs.LG] 11 Aug 2026

Abstract Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension 𝑑N and Daniely–Shalev-Shwartz dimenp sion 𝑑DS , the optimal excess risk is known at the two endpoints (𝑑DS /𝑛 realizable, 𝑑N /𝑛+𝑑DS /𝑛 agnostic [HMZ24, CEH+ 26, Pab26]) and open in between. We close the gap: at every fixed oracle risk 𝐿★ , the optimal excess risk is ! r ★𝑑 𝐿 𝑑 N DS e , Θ + 𝑛 𝑛 uniformly in the alphabet size, attained by a learner that knows neither 𝐿★ nor the confidence level.∗ The upper bound composes the cover–menu–compression architecture of [CEH+ 26], at the realizable rate of [Pab26], with a new comparator-facing relative compression theorem: a size-𝑘 compression rule that empirically dominates a comparator ℎ has population risk at most p 𝐿(ℎ) + 𝑂( 𝐿(ℎ)Γ + Γ) with Γ = (𝑘 log 𝑛 + log(1/𝛿))/𝑛, without stability; this transfers the comparison principle of the sharp binary theory [MQZ26] while discarding its Boolean-cube geometry, which does not lift to multiclass labels. The lower bound forces both terms using one class and one distribution at every fixed 𝐿★ , by a pair-Assouad scheme calibrated to 𝐿★ and a fiber argument on the pseudo-cubes underlying the Natarajan-versus-DS separation of [BCD+ 22]. Both theorems extend to list learning: against the best 𝑟-tuple of hypotheses, the same architecture and the same two engines yield an optimistic rate and a lower bound of the same shape, forcing the fluctuation term that [Pab26] expected to be necessary against list comparators, and removing the factor 𝑟 from the known realizable list lower bound.

∗ The main theorems are machine-checked in Lean 4; Section D records what is verified and in which form, and the development is available at https://github.com/xiaoyulics/multiclass-pac-learning.

1

Contents 1

Introduction

3

2

Setting and proof architecture 2.1 Setting and the two capacity parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The menu as a selective binaryization . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Three blocks for three logically different tasks . . . . . . . . . . . . . . . . . . . . . . .

7 7 8 9

3 The upper bound and its two modules 3.1 The learner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The module that preserves coefficient one . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Assembling coverage and localization . . . . . . . . . . . . . . . . . . . . . . . . . . .

11 11 12 14

4 A matching lower bound

14

5

Extension: optimistic rates for list learning

17

6

Discussion

20

A Proofs for the upper bound A.1 Imported modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Proof of the relative compression theorem . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Proof of the multiclass theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25 25 30 32

B Proofs for the lower bound B.1 The noisy pair-Assouad lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 The realizable pseudo-cube bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 Dimension calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.4 Proof of the lower bound theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.5 Which engine for which structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33 34 35 35 36 37

C Proofs for the list extension C.1 The list menu calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 Relative compression with product messages . . . . . . . . . . . . . . . . . . . . . . . C.3 Fixed-menu compression for tuple comparators . . . . . . . . . . . . . . . . . . . . . C.4 Proof of Theorem 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.5 The (𝑟 + 1)-ary Assouad lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.6 The list leave-one-out bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.7 The band family and 𝑟-ary dimension calculus . . . . . . . . . . . . . . . . . . . . . . C.8 Proof of Theorem 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38 38 39 39 40 41 42 43 43

D Machine-checked formalization

45

2

1

Introduction

The statistical difficulty of classification should depend on how much error is left in the best available hypothesis. When that hypothesis is nearly correct, the learner is not facing the same problem as in the fully agnostic regime: most observations carry no disagreement with the comparator, and the fluctuation term ought to reflect this. Guarantees with this property—interpolating between the realizable fast rate and the agnostic slow rate according to the level of realizability—are called optimistic rates [Pan02, SST10]. The requirement is easiest to see at the boundary. A class with VC dimension 𝑑 admits the fast rate 𝑑/𝑛 when it is exactly realizable, and a class whose best hypothesis errs on one observation in a trillion is statistically indistinguishable from a realizable p one at any practical sample size; yet the worst-case agnostic bound charges the same slow rate 𝑑/𝑛 for both 𝐿★ = 10−12 and 𝐿★ = 13 . An optimistic rate must instead degrade continuously: at 𝐿★ = 10−12 , the lop calized fluctuation 𝐿★ 𝑑/𝑛 remains within a factor of two of the realizable rate for every 𝑛 ≤ 1012 𝑑. In binary classification the desired statement is now precise. If the class has VC dimension 𝑑, the distribution-free fixed-risk benchmark is r ★ ★ b − 𝐿  𝐿 (𝑑 + log(1/𝛿)) + 𝑑 + log(1/𝛿) . 𝐿( ℎ) (1.1) 𝑛 𝑛 The first term is the agnostic fluctuation at the actual oracle risk; the second is the realizable remainder; lower bounds of this localized form are classical [DL95]. [HLZ24] showed that empirical risk minimization, and any other proper learner, misses the benchmark by a factor that grows as 𝐿★ decreases, and gave a learner attaining it over most of the range of 𝐿★ . [AHV25] determined the fine structure of the remaining small-error regime, including lower bounds that exhibit the localized term as unavoidable. [MQZ26] then constructed a parameter-free learner attaining (1.1) up to universal constants. Their proof uses a localized orientation of the Boolean cube and, crucially, a high-probability comparison that preserves coefficient one on the oracle risk. All of this line is binary; it is the multiclass version of the question that concerns us here. The multiclass problem is not obtained by changing the alphabet in this argument. It has two capacity parameters with different jobs. The Daniely–Shalev-Shwartz dimension 𝑑DS [DS14] characterizes realizable learnability [BCD+ 22], whereas the Natarajan dimension 𝑑N [Nat89] controls the leading agnostic term. The cover–menu–compression reduction of [CEH+ 26] established the 3/2 two-parameter structure with a 𝑑DS coverage term; [Pab26] then resolved the realizable sample complexity at 𝑑DS , and Corollary 1.2 of that paper records the resulting worst-case rate   𝑑DS 𝑑N + log(1/𝛿) e 𝑂 + . (1.2) 𝜖 𝜖2 This rate has the correct two-dimensional structure, but it treats an oracle of risk 10−3 in the same way as an oracle of constant risk. The question of this paper is whether the two structures can be kept at once: can the Natarajan term localize at 𝐿★ , while the DS term remains a realizable-order remainder? Why the literal transfer fails. The first attempt is to replace the Boolean cube by a 𝐾-ary Hamming graph and repeat the binary orientation argument. This construction records binary error patterns relative to a reference labeling, so its natural capacity is Graph dimension rather than DS or Natarajan dimension [Nat89, DSBS15]. For a finite alphabet this route introduces an unwanted 3

Table 1: Risk bounds at a glance, with upper- and lower-bound sources separated. The binary row has 𝑑 = VC(H); the multiclass rows use 𝑑N and 𝑑DS . In the highlighted row both directions are proved in this paper, and they match up to logarithmic factors.

Setting Binary Multiclass Multiclass

Excess-risk scale p 𝐿★ 𝑑/𝑛 + 𝑑/𝑛 p 𝑑N /𝑛 + 𝑑DS /𝑛 p 𝐿★ 𝑑N /𝑛 + 𝑑DS /𝑛

Upper bound

Lower bound

[MQZ26] [CEH+ 26, Pab26]

[DL95, AHV25] [CEH+ 26, HMZ24]

this work (Theorem 3.1)

this work (Theorem 4.1)

alphabet dependence; for a general label space Graph dimension may even be infinite when DS dimension is finite [DSBS15, BCD+ 22]. This is the obstruction behind the failure of direct ERM-style multiclass arguments [CEH+ 26]. Multiclass one-inclusion orientations remain fundamental—see, for example, [ADD+ 24]—but the Boolean-cube geometry is not the part of the binary proof that can be carried over unchanged. The result. We instead obtain, for finite label sets, a learner RMC achieving the two-dimensional optimistic rate ! r ★𝑑 𝐿 𝑑 N DS ★ e 𝐿(RMC(𝑆)) − 𝐿 = 𝑂 + . (1.3) 𝑛 𝑛 The learner uses neither 𝐿★ nor 𝛿. The fully quantified statement in Theorem 3.1 contains a 𝑑N log3 (𝑒𝑛) localized term and a 𝑑DS log2 (𝑒𝑛) coverage term. The rate is optimal: Theorem 4.1 constructs, forpevery pair (𝑑N , 𝑑DS ), a class on which every learner, at every fixed 𝐿★ , incurs excess risk Ω( 𝐿★ 𝑑N /𝑛 + 𝑑DS /𝑛), with both terms forced by one distribution. Upper and lower bounds together give the multiclass analogue of (1.1), up to logarithmic factors. The comparison is summarized in Table 1; confidence terms and polylogarithms are suppressed there. What is transferred. The coefficient-one comparison principle is inspired by [MQZ26]; the learned-menu device and correct-label outside-menu decomposition are inherited from [CEH+ 26, Section 1.1 and Theorem 3.5]. The useful invariant from the binary proof is not its cube but its comparison principle: keep coefficient one on the comparator risk, and make the fluctuation scale with that same risk. To make this principle compatible with multiclass capacity, we first reduce the label geometry to a short learned menu. There are then two distinct ways to be wrong. A correct comparator label may be missing from the menu; this is a coverage failure and is paid for by 𝑑DS . Conditional on a fixed menu, the learner may choose the wrong label inside it; this is an ordinary binary loss whose description length is controlled by 𝑑N . The proof is designed so that these two charges never merge. This separation explains both the three-way sample split and the form of the bound. The threestage skeleton is adapted from [CEH+ 26, Algorithm 4]. The first block compresses the correct region of any comparator into a finite family. The second block learns a menu that covers the labels of a canonical member of that family. Only after the menu is frozen does the third block fit an empiricalrisk-dominating menu-loss compressor. At that point the remaining question is purely statistical: can a compression rule that beats a comparator empirically be compared with it in population risk p without paying an absolute 𝑘/𝑛 term?

4

The relative compression theorem in Theorem 3.3 answers this question. If a deterministic compression rule of size 𝑘 has no larger empirical loss than a fixed comparator ℎ, then ! r 𝐿(ℎ)(𝑘 log 𝑛 + log(1/𝛿)) 𝑘 log 𝑛 + log(1/𝛿) 𝐿(𝐴(𝑆)) ≤ 𝐿(ℎ) + 𝑂 + . (1.4) 𝑛 𝑛 No stability is required. The mechanism is the classical one for compression bounds: ordered descriptions are counted, and after their selected coordinates are removed, one-sided Bernstein inequalities control the untouched observations. Bernstein refinements of exactly this type already localize lossy compression at the reconstruction’s empirical error [GKN17, Theorem 8]. What the composition consumes is a different interface: comparator-facing rather than reconstruction-facing, and order-dependent with repeated indices. The concentration step itself is elementary; the contribution is to formulate it in the form that can be composed with the random menu while preserving coefficient one. What the paper adds. There are three mathematical pieces and one structural conclusion. First, we prove the comparator-facing relative compression theorem with explicit constants, ordered messages, repeated indices, and no stability assumption; the proof route is the counting-plus-Bernstein one of the compression literature, and the claim of novelty is confined to the interface, not the mechanism. Second, we place the theorem at the final stage of the source-checked cover–menu– compression reduction of [CEH+ 26], taking care that the menu is independent of the final sample and that empty and singleton menus introduce neither a singular log 𝑝 nor hidden side information. Third, we prove a matching fixed-𝐿★ lower bound (Theorem 4.1): a single class and a single distribution activate both dimensions at every fixed 𝐿★ , so the rate of (1.3) is optimal up to logarithmic factors. The construction pairs a noisy Natarajan cube with a Natarajan-free pseudo-cube obtained from the separation of [BCD+ 22]. The resulting risk decomposition identifies the roles of the dimensions: 𝑑DS controls correct-label coverage, while 𝑑N controls localized fluctuations inside the learned menu, and the lower bound certifies that this division of labor is intrinsic rather than an artifact of the analysis. Extension to list learning. The architecture never uses the fact that the final block outputs a single label, and Section 5 exploits this: for learners that output 𝑟 labels per point, the same three blocks yield an optimistic rate against the best 𝑟-tuple of hypotheses (Theorem 5.1), and the two lower-bound engines upgrade to a bound of the same two-term shape with exact calibration (Theorem 5.2), whose fluctuation term is of the kind [Pab26] expected to be necessary against list comparators. A byproduct of the second engine removes the factor 𝑟 from the realizable list lower bound of [HMZ24] (Corollary 5.3). The multiclass theorems remain the paper’s center; the list section is a short demonstration that the comparison principle composes beyond single-valued prediction. Further related work. The Natarajan dimension is the classical multiclass analogue of the VC dimension [Nat89]; the Graph dimension governs ERM-style uniform-convergence arguments but not learnability at large alphabets [DSBS15]. The DS dimension entered through the multiclass one-inclusion framework of [DS14], and its finiteness characterizes multiclass PAC learnability [BCD+ 22]. One-inclusion prediction originates with [HLW94] and was brought to multiclass loss by [RBR06]; optimal realizable bounds for binary VC classes were later obtained from it without uniform convergence [ACSZ23]. In the multiclass realizable problem, the rate was improved by 5

[HMZ24] and settled by [Pab26], who bounded the one-inclusion density through the DS dimension; a sharp 𝑘-ary Sauer–Shelah–Perles inequality in the same currency appears in [HMMS26]. The learned menu is a list-valued object. List prediction entered the multiclass story as a tool in the characterization of [BCD+ 22]; list learnability in its own right was characterized by [CP23], whose rates were successively sharpened through multiclass boosting [BDMM23] and the optimal 𝑘-ary Sauer lemma of [HMMS26], and brought to near-optimal form by [Pab26], against the realizable lower bound of [HMZ24]. Prediction that is graded on only part of the observation space is the subject of partial concept classes [AHHM21]. Section 5 engages the list thread directly: it upgrades both main theorems to list learners, with the comparator strengthened to the best tuple of hypotheses and the fluctuation localized at the oracle list risk, refining the worst-case agnostic list rates of [CP23, Pab26] in the same sense in which (3.1) refines the worst-case multiclass rate. Sample compression enters PAC learning with the unpublished 1986 manuscript of Littlestone and Warmuth; [FW95] tied compression size to the VC dimension, and [DMY16] brought boostingto-compression arguments to the multiclass setting, the tradition in which the cover stage sits. Compression bounds at nonzero empirical risk begin with [GHS05], which also isolated the role of message order and repetition conventions. Two facts calibrate what p compression alone can deliver: generic agnostic schemes of size 𝑘 cannot beat the worst-case rate 𝑘 log(𝑛/𝑘)/𝑛 [HK19], and stability removes logarithmic factors where it is available [HK21]. Theorem 3.3 trades neither: it keeps the logarithm and the stability-free interface, and instead moves the anchor to a fixed comparator’s population risk with coefficient one. The localization obtained this way is distribution-free, entering only through 𝐿★ with no Massart- or Tsybakov-type condition; it is therefore not a fastrate statement in the local-complexity sense of [BBM05]. It belongs instead to the optimistic-rate tradition: relative-deviation inequalities whose fluctuation scales with the risk itself go back to Vapnik and Chervonenkis and were extended by [Pan02]; the name is from [SST10], which proved such rates for smooth losses; and [ZH18] developed localization for VC classification beyond local Rademacher complexities, a precursor of the binary fixed-risk line above. Scope. The result is information-theoretic: the compression and one-inclusion routines need not be computationally efficient for an abstract class. The label alphabet is finite, although the bound is uniform in its cardinality. Logarithmic factors remain in the upper bound; the lower bound of Theorem 4.1 matches it up to those factors and does not address the sharp log(1/𝛿) dependence. The lower-bound family uses label alphabets growing with 𝑑DS /𝑑N , which Remark 4.6 shows is necessary, and which the uniformity in 𝐾 of Theorem 3.1 anticipates. Organization. Section 2 develops the upper-bound proof as a sequence of obstacles and design choices, ending with the error identity that separates the two dimensions. Section 3 states the relative compression theorem, the learner, and the main risk bound. Section 4 proves the matching lower bound. Section 5 extends both bounds to list learners. Section 6 interprets the results. The appendix places each source-convention check immediately after its restated external lemma, gives the complete concentration argument and full probability bookkeeping, and closes with the proofs for the lower bound and for the list extension.

6

2

Setting and proof architecture

The direct multiclass lift fails because it asks one combinatorial object to do two jobs: represent the label geometry and control the stochastic fluctuation. The proof below separates these jobs. A learned menu first turns multiclass prediction into a selective binary loss; an exact algebraic identity then shows that only correct comparator labels missing from that menu must be restored. This section develops that identity before any of the compression machinery, and then explains why each of the three sample blocks is needed. The cover–menu–compression backbone is inherited from the three-phase learner of [CEH+ 26, Sections 3.1–3.4]. Our modification is at its final statistical interface: we replace the absolute compression comparison by a comparator-facing relative one and then track how that change propagates through the composition. Notation. For 𝑚 ∈ N we write [𝑚] = {1, . . . , 𝑚}. Logarithms are natural, and 1{·} denotes the indicator of an event. A sample is a finite iid sequence of labeled observations; for a distribution D, the law of a sample of 𝑛 observations is D𝑛 . Expectations over auxiliary finite indices are written with subscripts, as in E𝜎 . Universal constants 𝐶, 𝑐 > 0 may change value between occurrences, and e suppresses factors polylogarithmic in 𝑛, 𝑑N , and 𝑑DS . 𝑂(·)

2.1

Setting and the two capacity parameters

We use the finite-alphabet dimension and learning conventions of [CEH+ 26, Section 2]. Let (X , X ) be a measurable space, let [𝐾] = {1, . . . , 𝐾}, and let H ⊆ [𝐾] X . For a distribution D on Z = X × [𝐾], write 𝐿D (𝑓) = P (𝑋,𝑌)∼D (𝑓(𝑋) ≠ 𝑌),

𝐿★ = inf 𝐿D (ℎ). ℎ∈H

Unless another distribution is named, P and E are taken under the ambient D and their subscript is omitted. For a finite sequence 𝑠 = (𝑧1 , . . . , 𝑧𝑁 ), b 𝐿𝑠 (𝑓) denotes its average zero–one loss. Samples are iid unless stated otherwise. Assumption 2.1 (Measurability and tie-breaking). The label alphabet is finite. Every hypothesis evaluation, learning map, selection map, reconstruction map, and finite-class sampling rule used below is jointly measurable after deterministic tie-breaking, or the class is restricted by the usual countability/separability convention that ensures this property. This convention keeps all probability statements literal rather than phrased in outer probability. It is the only regularity condition beyond iid sampling. Definition 2.2 (Natarajan dimension [Nat89]). A sequence 𝑥1 , . . . , 𝑥𝑑 is Natarajan-shattered by H if there are label pairs 𝑦𝑖 ≠ 𝑦𝑖0 such that every one of the 2𝑑 coordinatewise choices is realized by the trace of H. The largest such 𝑑 is the Natarajan dimension 𝑑N . Definition 2.3 (DS dimension [DS14]). A nonempty finite set 𝑉 ⊆ [𝐾] 𝑑 is a 𝑑-dimensional pseudocube if, for each 𝑣 ∈ 𝑉 and coordinate 𝑖, there is 𝑣0 ∈ 𝑉 that differs from 𝑣 only at coordinate 𝑖. A sequence is DS-shattered if the trace of H contains such a pseudo-cube; the largest length is the Daniely–Shalev-Shwartz dimension 𝑑DS .

7

Finiteness of 𝑑DS characterizes multiclass PAC learnability [BCD+ 22]. Every Natarajan cube is a pseudo-cube, and therefore 𝑑N ≤ 𝑑DS . (2.1) The inequality does not make the two quantities interchangeable. In the argument below, 𝑑DS controls whether a correct label is represented at all, while 𝑑N controls the complexity of choosing among labels that have already been represented. Both dimensions also vanish together: a single point at which two hypotheses disagree is already Natarajan- and DS-shattered, so 𝑑DS = 0 forces all hypotheses of H to coincide pointwise, in which case any fixed member attains 𝐿★ and there is nothing to learn. The standing assumption 1 ≤ 𝑑N ≤ 𝑑DS < ∞ in Theorem 3.1 therefore excludes only this degenerate case; in particular it forces H ≠ ∅.

2.2

The menu as a selective binaryization

Following [CEH+ 26, Section 3.3], a 𝑝-menu is a measurable map 𝜇 : X → 2 [𝐾] with sup𝑥 |𝜇(𝑥)| ≤ 𝑝. Once a menu is fixed, define the inside-menu loss ℓ𝜇 (𝑓, (𝑥, 𝑦)) = 1{𝑓(𝑥) ≠ 𝑦, 𝑦 ∈ 𝜇(𝑥)},

𝐿𝜇 (𝑓) = E ℓ𝜇 (𝑓, (𝑋, 𝑌)).

(2.2)

This is a binary-valued selective loss: the predictor remains multiclass, but the loss deliberately ignores observations whose label lies outside the menu. The apparent danger is that ignored observations might hide arbitrary error. The following elementary identity shows exactly what has to be put back; it isolates the pointwise algebra behind [CEH+ 26, Theorem 3.5], the hinge on which the localized refinement turns. Lemma 2.4 (Selective-menu decomposition). Let 𝜇 be a menu. For all classifiers 𝑓 and ℎ, P(ℎ(𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋)) ≤ P(ℎ(𝑋) = 𝑌 ≠ 𝑓(𝑋)) + P(𝑓(𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋));

(2.3)

for all classifiers 𝑔 and ℎ, 𝐿D (𝑔) − 𝐿D (ℎ) ≤ 𝐿𝜇 (𝑔) − 𝐿𝜇 (ℎ) + P(ℎ(𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋));

(2.4)

and, for every classifier ℎ, 𝐿𝜇 (ℎ) ≤ 𝐿D (ℎ).

(2.5)

Proof. For (2.3), consider a point on which ℎ is correct but its label is absent from the menu. Either 𝑓 disagrees with this correct label, which is the first event on the right, or 𝑓 is also correct, which is the second event. For (2.4), fix (𝑥, 𝑦). If 𝑦 ∈ 𝜇(𝑥), the difference between the zero–one losses of 𝑔 and ℎ is exactly their inside-menu loss difference. If 𝑦 ∉ 𝜇(𝑥), both inside-menu losses vanish. The ordinary loss difference can then be positive only when ℎ(𝑥) = 𝑦, and in that case it is at most one. This is precisely the last indicator in (2.4). Taking expectations proves the inequality. Finally, ℓ𝜇 (ℎ, (𝑥, 𝑦)) ≤ 1{ℎ(𝑥) ≠ 𝑦} pointwise, which gives (2.5). □ The decomposition is the conceptual center of the proof. Put 𝛼𝜇 (ℎ) := P(ℎ(𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋)). 8

Block 𝑆1 : cover replace H by a finite family b| ≲ 𝑑DS log2 𝑛 log | F

finite family

Block 𝑆2 : menu cover correct labels of a canonical witness

fixed menu

Block 𝑆3 : compress learn under the frozen binary loss ℓ𝜇 𝑘 ≲ 𝑑N log2 𝑛

𝛼𝜇 (ℎ) ≲ 𝑑DS log2 𝑛/𝑛

Figure 1: The proof does not apply one complexity measure to the original multiclass loss. It first pays 𝑑DS to make correct labels visible, then pays 𝑑N to learn within the resulting menu.

Then the desired comparison has the form
𝐿D (𝑔) − 𝐿D (ℎ) ≤ 𝐿𝜇 (𝑔) − 𝐿𝜇 (ℎ) + 𝛼𝜇 (ℎ).

(2.6)

The first term asks how well the learner predicts inside a fixed menu. The second asks only whether the menu contains labels on which the comparator is correct. In particular, oracle mistakes outside the menu are not charged a second time. This is where coefficient one on 𝐿D (ℎ) is won or lost. An idealized case makes the point transparent. Suppose a menu is fixed in advance and contains every correct label of ℎ. Then 𝛼𝜇 (ℎ) = 0, so it is enough to compare 𝑔 with ℎ under the binary loss ℓ𝜇 . If this comparison localizes at 𝐿𝜇 (ℎ), then (2.5) automatically localizes it at 𝐿D (ℎ). The full learner has only one additional task: construct such a menu approximately, with a correct-label miss probability of realizable order.

2.3

Three blocks for three logically different tasks

The three-block construction is shown in Figure 1. The split is not merely a convenience for applying concentration inequalities. Each fresh block freezes an object that becomes the statistical environment for the next block. Block 𝑆1 : make the comparator finite without learning it. The menu learner used in the second block operates on a finite family, while the original class H may be infinite. The one-inclusion, boosting-to-compression, and cover steps are due to [CEH+ 26, Proposition 3.3 and Theorem 3.2]; the sharp conversion of their realizable parameter to 𝑑DS uses [Pab26, Corollary 1.1]. Together they produce a deterministic ordinary compressor of size 𝑂(𝑑DS log 𝑛). Enumerating all of its messages b For a labeled sequence 𝑠 and a classifier ℎ, write 𝑠[ℎ] for the ordered on 𝑆1 gives a finite family F. subsequence on which ℎ is correct. More importantly, for every fixed comparator ℎ, the family contains a canonical witness 𝑓ℎ,𝑆1 = 𝐴1 (𝑆1 [ℎ]) satisfying, with high probability, b| ≤ 𝐶𝑑DS log2 (𝑒𝑛), log | F

P(ℎ(𝑋) = 𝑌 ≠ 𝑓ℎ,𝑆1 (𝑋)) ≤ 𝐶

𝑑DS log2 (𝑒𝑛) + log(1/𝜂) |𝑆1 |

(2.7)

(the native scale of both logarithms is 𝑒|𝑆1 |; since |𝑆1 | ≤ 𝑛, we state them at the common scale 𝑒𝑛 once and for all). The second guarantee is deliberately restricted to the region on which ℎ is correct. That is all (2.3) will ask us to control; approximating ℎ on its errors would solve a stronger and unnecessary problem.

9

b Block 𝑆2 : cover the witness rather than identify the oracle. Conditional on 𝑆1 , the family F and the canonical witness are fixed. The multiplicative-weights menu learner and its correct-label coverage guarantee are due to [CEH+ 26, Algorithm 3 and Theorem 3.4]. When run for 𝑇 = |𝑆2 | rounds, it returns classifiers ℎ1 , . . . , ℎ𝑇 −1 and hence the menu 𝜇(𝑥) = {ℎ1 (𝑥), . . . , ℎ𝑇 −1 (𝑥)},

sup |𝜇(𝑥)| ≤ 𝑇 − 1. 𝑥

b its correct-label menu miss For every fixed 𝑓 ∈ F, 𝛽𝑓 (𝜇) := P(𝑓(𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋)) is, with high probability,

b| + 14 log(3/𝜂) + 12 4 log | F . 𝑇 Apply this to 𝑓ℎ,𝑆1 . The set inclusion (2.3), together with (2.7)–(2.8), gives 𝛽𝑓 (𝜇) ≤

𝛼𝜇 (ℎ) ≲

𝑑DS log2 (𝑒𝑛) + log(1/𝜂) . 𝑛

(2.8)

(2.9)

The menu need not reveal which hypothesis is the oracle. It only has to contain, most of the time, the labels produced by one canonical witness on the oracle’s correct region. Block 𝑆3 : localize only after the menu is frozen. For a binary loss ℓ : F × Z → {0, 1}, call a deterministic compression rule 𝐴 = (𝜅, 𝜌) empirical-risk-dominating if it selects an ordered sequence of at most 𝑘 sample elements, reconstructs 𝐴(𝑠) = 𝜌(𝜅(𝑠)), and satisfies b 𝐿𝑠ℓ (ℎ) 𝐿𝑠ℓ (𝐴(𝑠)) ≤ inf b ℎ∈H

(2.10)

for every sample 𝑠. Repeated selected indices are allowed. Conditional on the first two blocks and the menu seed, 𝜇 is fixed and 𝑆3 remains iid. The fixed-menu compression construction of [CEH+ 26] then supplies a rule satisfying (2.10) under ℓ𝜇 , with description length 𝑘 ≲ 𝑑N log(𝑇 − 1) log(𝑒|𝑆3 |) ≲ 𝑑N log2 (𝑒𝑛) when 𝑇 ≥ 3; empty and singleton menus admit a size-zero finalizer. p At this point a worst-case compression theorem would give a fluctuation of order 𝑑N /𝑛, erasing the information that the oracle is nearly correct. The remaining module must instead compare the final reconstruction with a fixed comparator at the comparator’s own Bernoulli variance scale. This is the role of Theorem 3.3. Why the order cannot be shortened. The cover must be frozen before the menu rounds, otherwise the finite-family guarantee does not apply to a fixed family. The menu must be frozen before the final compression sample, otherwise ℓ𝜇 is not a fixed loss on the observations used by the compression theorem. The canonical witness depends on 𝑆1 , but it is not supplied to the menu algorithm: the menu guarantee is pointwise for every member fixed after conditioning on 𝑆1 . These independence relations explain the architecture; the exact sigma-fields and tower-property calculation are recorded in Section A.3. Every imported result used in the preceding discussion is restated as a formal lemma in Section A.1, with its source locator, convention mapping, and applicability check. Thus the main text can follow the proof’s causal order without turning the reader away to another paper. 10

3

The upper bound and its two modules

Let RMC denote the three-block learner described formally in Algorithm 1. We state its guarantee before entering the two technical modules, so that the role of each intermediate bound remains visible. Theorem 3.1 (Small-error multiclass learning). Suppose Assumption 2.1 holds and H ⊆ [𝐾] X has 1 ≤ 𝑑N ≤ 𝑑DS < ∞. There is a universal constant 𝐶 > 0 such that, for every distribution D on X × [𝐾], every 𝑛 ≥ 3, and every 𝛿 ∈ (0, 1), the output of RMC satisfies, with probability at least 1 − 𝛿 over the sample and the menu learner’s randomness, s ! 𝐿★ (𝑑N log3 (𝑒𝑛) + log(1/𝛿)) 𝑑N log3 (𝑒𝑛) + 𝑑DS log2 (𝑒𝑛) + log(1/𝛿) ★ + . (3.1) 𝐿D (RMC(𝑆)) ≤ 𝐿 +𝐶 𝑛 𝑛 The learner is independent of 𝐿★ and 𝛿, and may be computationally inefficient. The theorem answers the interpolation question in the same risk scale as (1.1). At 𝐿★ = 0, the stochastic square-root term vanishes and the DS contribution has realizable order. When 𝐿★ is constant, the result recovers the established worst-case rate up to logarithms. Between these endpoints, only the Natarajan fluctuation is multiplied by the actual oracle risk. The interpolation is not merely consistent with the two endpoints: Theorem 4.1 exhibits a single class in which a single distribution forces both terms at every fixed 𝐿★ , so (3.1) is optimal up to logarithmic factors. Remark 3.2 (Constants). The coefficient of 𝐿★ in (3.1) is exactly one; 𝐶 multiplies only the fluctuation and the remainder. Let 𝑐1 , 𝑐2 , 𝑐3 be the absolute constants of the three imported bounds, which the source states asymptotically: the compression size 𝑘1 (𝑚) ≤ 𝑐1 (𝑑RE (H) + 1) log(𝑒𝑚) of Lemma A.2, the correct-region guarantee of Lemma A.3 in its (𝑘𝐴 (𝑚) + 1)-form, and the size bound (S.4) of Lemma A.5. Every other constant in the proof is explicit—12 and 20 in Theorem 3.3, the ceiling of Lemma A.1, the menu constants of (S.3), block sizes 𝑛𝑖 ≥ 𝑛/5, three 𝛿/3 events—and tracking them through Section A.3 shows that one may take p 𝐶 = 12 5(𝑐3 + 2) + 100(𝑐3 + 2) + 5(𝑐2 + 4) (2636 𝑐1 + 4), the factor 2636 bounding (𝑑RE (H)+1)/𝑑DS via Lemma A.1. The lower bound needs no bookkeeping: (4.1) holds with the absolute constants 1/12 and 1/15.

3.1

The learner

The formal learner mirrors Figure 1. The objects 𝐴1 , Cover, MW, and 𝐵𝜇,𝑇 are the deterministic ordinary compressor, its induced cover, the finite-family menu routine, and the fixed-menu finalizer, respectively. Their full interface statements are collected in Section A.1. Algorithm 1 retains the three-stage skeleton of [CEH+ 26, Algorithm 4]. Its first-stage 𝑑DS size uses the realizable guarantee of [Pab26, Corollary 1.1]; its new step is to analyze the last-stage reconstruction through Theorem 3.3 instead of an absolute square-root bound.

11

Algorithm 1 Relative menu compression RMC Require: Sample 𝑆 ∈ (X × [𝐾]) 𝑛 , class H, 𝑛 ≥ 3 1: Split 𝑆 into independent consecutive blocks 𝑆1 , 𝑆2 , 𝑆3 whose sizes differ by at most one; put 𝑇 = |𝑆2 |. b ← Cover(𝑆1 , H, 𝐴1 ). 2: Form the compression cover F b 3: Learn the menu 𝜇 ← MW(𝑇 , 𝑆2 , 1/2, F). 4: return 𝐵𝜇,𝑇 (𝑆3 ), the fixed-menu empirical-risk-dominating reconstruction under ℓ𝜇 . The last line includes all menu sizes. When 𝑇 ≤ 2, 𝐵𝜇,𝑇 is a size-zero rule that predicts the unique menu member when there is one; when 𝑇 ≥ 3, it is the list sample-compression rule with the deterministic menu bound 𝑇 − 1. The small-menu branch is not a coding convention: for an empty or singleton menu, predicting the unique menu member incurs zero inside-menu loss pointwise, so the size-zero rule is automatically empirical-risk-dominating. This detail is formalized in Lemma A.6; the statistical point is that the last rule and its loss are fixed before 𝑆3 is observed. The guarantee of [CEH+ 26] is stated as a sample complexity, and its proof chooses the block lengths as functions of the target accuracy and confidence. The fixed-risk form (3.1) instead holds for the balanced split simultaneously for every 𝑛 and 𝛿. This uniformity is not cosmetic: it is exactly what the claim that RMC uses neither 𝐿★ nor 𝛿 requires, since a split tuned to the target accuracy would reintroduce the parameter the learner is supposed to avoid. The parameter-freeness target itself is the one set by the binary fixed-risk line [HLZ24, MQZ26].

3.2

The module that preserves coefficient one

Once the menu has been frozen, the multiclass geometry has disappeared from the concentration step. We have a binary loss ℓ, a deterministic compression rule that dominates a comparator empirically, and a description length 𝑘. A standard compression bound would control population loss p by empirical loss plus 𝑂( 𝑘 log 𝑁/𝑁). That is too coarse here: even if the comparator makes no errors, the square-root term remains. Compression bounds at nonzero empirical risk go back to [GHS05], where the role of message order and repetition conventions is already explicit. The closest antecedent is the empiricalBernstein compression bound of [GKN17, Theorem 8], which shares both devices of the proof below—description counting and Bernstein control of the held-out observations—and localizes the risk at the reconstruction’s empirical error. We make no claim of a new concentration mechanism. The statement below differs from that antecedent in three ways, each forced by the composition it must enter. It is anchored at a fixed comparator’s population risk with coefficient one, rather than at the reconstruction’s empirical error; this is what survives substitution into the menu decomposition. Its messages are ordered with repeated indices, matching the compressor the menu construction actually produces. And it holds for every 𝑁 and 𝑘 with explicit constants and no restriction on the error level, which the conditional application inside a random-menu composition consumes verbatim. The target—coefficient one on the comparator risk with fluctuation at its own Bernoulli scale—is inspired by the binary small-error comparison of [MQZ26]. The theorem below does not import their cube geometry; it realizes that comparison principle through compression-message counting and one-sided Bernstein inequalities. The size-zero case suggests the correct replacement. If a single fixed predictor has no larger empirical loss than a fixed comparator, then two one-sided Bernoulli deviations compare their 12

population risks. The fluctuation is proportional to the square root of the comparator’s mean, not to one. A nonzero compression message changes only how many such comparisons must hold simultaneously. For a binary loss ℓ : F × Z → {0, 1}, write 𝑁 1 Õ b 𝐿𝑠ℓ (𝑓) = ℓ(𝑓, 𝑧𝑖 ). 𝑁 𝑖=1

ℓ 𝐿D (𝑓) = E𝑍∼D ℓ(𝑓, 𝑍),

For integers 𝑁 ≥ 1 and 𝑘 ≥ 0, and 𝛿 ∈ (0, 1), define Γ𝑁 (𝑘, 𝛿) :=

(𝑘 + 1) log(𝑁 + 1) + log(4/𝛿) . 𝑁

(3.2)

Theorem 3.3 (Relative compression). Let (Z, Z ) and (F, F ) be measurable spaces, let H ⊆ F, and let ℓ : F × Z → {0, 1} be jointly measurable. Fix 𝑁 ≥ 1 and an integer 𝑘 ≥ 0. Let 𝐴 = (𝜅, 𝜌) be a measurable deterministic selection scheme such that, on every sample 𝑠 ∈ Z 𝑁 , 𝜅(𝑠) is an ordered sequence of at most 𝑘 elements of 𝑠 (indices may repeat), 𝐴(𝑠) = 𝜌(𝜅(𝑠)), and b 𝐿𝑠ℓ (𝐴(𝑠)) ≤ inf b 𝐿𝑠ℓ (ℎ). ℎ∈H

(3.3)

Then, for every probability distribution D on (Z, Z ), 𝑆 ∼ D𝑁 , every fixed ℎ ∈ H, and every 𝛿 ∈ (0, 1), with probability at least 1 − 𝛿, q ℓ ℓ ℓ (ℎ)Γ (𝑘, 𝛿) + 20Γ (𝑘, 𝛿). 𝐿D (𝐴(𝑆)) ≤ 𝐿D (ℎ) + 12 𝐿D (3.4) 𝑁 𝑁 No stability assumption on the selection map is required. Í How the proof works. There are at most 𝑀 = 𝑘𝑗=0 𝑁 𝑗 ≤ (𝑁 + 1) 𝑘+1 ordered descriptions. Fix one of them, let 𝑈 be the set of distinct sample coordinates it names, and condition on those coordinates. The reconstruction is now fixed, while the observations outside 𝑈 are still iid. Let e 𝐿𝐼 (𝑓𝐼 ) be its average loss on these untouched observations. A one-sided Bernstein inequality therefore gives, simultaneously over all descriptions, q log(2𝑀/𝛿) ℓ ℓ (𝑓 )𝑠 + 𝑠𝐼 , 𝐿D (𝑓𝐼 ) ≤ e 𝐿𝐼 (𝑓𝐼 ) + 2𝐿D 𝑠𝐼 = . (3.5) 𝐼 𝐼 3 𝑁 − |𝑈 | The deletion of 𝑈 is essential: it is what makes the reconstruction fixed relative to the observations on which its loss is measured. Repeated indices create no additional dependence because only distinct coordinates are deleted; they are nevertheless counted as different ordered messages. For the description selected on the realized sample, empirical domination does not directly compare held-out loss with the comparator. It first gives the deterministic inequality e 𝐿𝐼 (𝑓𝐼 ) ≤

𝑁 bℓ 𝐿 (ℎ). 𝑁 − |𝑈 | 𝑆

(3.6)

A second one-sided Bernstein inequality bounds the fixed comparator’s empirical loss by its popℓ (ℎ). Substituting this bound into (3.6) and then into (3.5) leaves an implicit inulation loss 𝐿 = 𝐿D equality √ because the unknown reconstruction risk appears under the square root. Solving it gives 𝐿 + 𝑂( 𝐿Γ + Γ). The full proof in Section A.2 records the two probability events, the effect of 𝑁 − |𝑈 |, and every constant leading to 12 and 20. Unlike that empirical-error antecedent, the form above gives the fixed-comparator, orderdependent comparison required by the random-menu composition, without a stability assumption. 13

3.3

Assembling coverage and localization

We now follow the learner from left to right. This is also the shortest way to see why the two dimensions land in different terms of (3.1). The cover and menu guarantees in the first two blocks are inherited from [CEH+ 26, Theorems 3.2 and 3.4], with their realizable parameter converted to 𝑑DS by [Pab26, Corollary 1.1]. The new operation in the assembly is the conditional application of Theorem 3.3 to the third block. Fix 𝜖 > 0 and choose ℎ★ ∈ H with 𝐿D (ℎ★ ) ≤ 𝐿★ + 𝜖. On the first block, the compression cover contains the canonical witness 𝑓1★ = 𝐴1 (𝑆1 [ℎ★ ]). Conditional on 𝑆1 , the menu theorem applies to this fixed witness on the fresh second block. The two correct region guarantees and (2.3) yield 𝛼𝜇 (ℎ★ ) = P(ℎ★ (𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋)) ≤ 𝐶

𝑑DS log2 (𝑒𝑛) + log(1/𝛿) . 𝑛

(3.7)

This is the entire DS contribution. Next freeze 𝑆1 , 𝑆2 and the menu seed. The menu 𝜇, the binary loss ℓ𝜇 , and the final compression rule are now fixed, whereas 𝑆3 remains iid. The final rule is empirical-risk-dominating and has message length 𝑂(𝑑N log2 (𝑒𝑛)). Applying Theorem 3.3 under the conditional distribution gives s ! 3 ★ ) (𝑑 log3 (𝑒𝑛) + log(1/𝛿)) 𝐿 (ℎ 𝑑 log (𝑒𝑛) + log(1/𝛿) 𝜇 N N 𝐿𝜇 (RMC(𝑆)) − 𝐿𝜇 (ℎ★ ) ≤ 𝐶 + . (3.8) 𝑛 𝑛 This is the entire Natarajan contribution. It remains to put the two estimates in the same currency. The exact menu decomposition (2.6) gives 𝐿D (RMC(𝑆)) − 𝐿D (ℎ★ ) ≤ 𝐿𝜇 (RMC(𝑆)) − 𝐿𝜇 (ℎ★ ) + 𝛼𝜇 (ℎ★ ). (3.9) Finally, 𝐿𝜇 (ℎ★ ) ≤ 𝐿D (ℎ★ ) by (2.5). Thus substituting (3.7) and (3.8) into (3.9) preserves coefficient one on 𝐿D (ℎ★ ). A union bound over the three blockwise events and 𝜖 ↓ 0 prove Theorem 3.1. The complete proof in Section A.3 names the conditioning sigma-fields, derives the Γ𝑁 bound, handles the two small-menu branches, and justifies the limit when the infimum defining 𝐿★ is not attained. Corollary 3.4 (Small-error sample complexity). For any target excess error 𝜖 ∈ (0, 1), the same learner achieves 𝐿D (RMC(𝑆)) ≤ 𝐿★ + 𝜖 with probability at least 1 − 𝛿 from a sample of size  ★  𝐿 (𝑑 + log(1/𝛿)) 𝑑 + log(1/𝛿) N DS e 𝑛=𝑂 + , (3.10) 𝜖 𝜖2 e are in 𝑛, 𝑑N , 𝑑DS . where the logarithms hidden by 𝑂 The two terms in (3.10) are not the result of inverting one undifferentiated worst-case bound. The first is the sample size needed to resolve inside-menu fluctuations at oracle risk 𝐿★ ; the second is the sample size needed to make correct labels visible. The algorithm does not need to know which term dominates.

4

A matching lower bound

Theorem 3.1 interpolates between two endpoints whose optimality was, until now, supported by separate constructions: at 𝐿★ = 0 the 𝑑DS /𝑛 term matches the realizable lower bound [Pab26], and 14

for constant 𝐿★ the localized term is supported through binary subclasses and the worst-case agnostic lower bound [CEH+ 26]. This section closes the gap between those endpoints. We construct a single class in which a single distribution, at every fixed 𝐿★ , forces the localized term and the coverage term of (3.1) simultaneously. Everything in this section is finitely supported, so no measurability issues arise and Assumption 2.1 is not needed. Theorem 4.1 (Fixed-𝐿★ lower bound). For all integers 1 ≤ 𝑑N ≤ 𝑑DS there are a finite label set [𝐾] and a finite class H ⊆ [𝐾] X with 𝑑N ≤ Nat(H) ≤ 𝑑N + 1,

DS(H) = 𝑑N + 𝑑DS ,

such that for every 𝑛 ≥ 1, every 𝐿★ ∈ [0, 1/8], and every learner 𝐴, possibly randomized, there is a distribution D on X × [𝐾] with inf ℎ∈H 𝐿D (ℎ) = 𝐿★ exactly, under which r n𝑑 o   1 𝐿★ 𝑑N 1 DS 1 ★ ★ E 𝐿D (𝐴(𝑆)) − 𝐿 ≥ 1{𝐿 ≥ 𝑑N /𝑛} + min , , (4.1) 12 𝑛 15 𝑛 4 the expectation being over 𝑆 ∼ D𝑛 and the learner’s internal randomness. Both terms are forced by the same distribution, drawn from a finite family that depends only on (H, 𝐿★ , 𝑛) and not on the learner. Here Nat(H) and DS(H) denote the two dimensions of Definitions 2.2 and 2.3. Three reading notes. First, the indicator gate is harmless: for 𝐿★ < 𝑑N /𝑛 the localized term is below 𝑑DS /𝑛 on both sides of the comparison, so (3.1) and (4.1) still match. Second, since Nat(H) ≤ 𝑑N + 1 and DS(H) ≤ 2𝑑DS , the right-hand side of (4.1) can equivalently be written with the class’s own dimensions at the cost of a factor two in the constants. Third, the bound is stated in expectation; because the excess risk is bounded by one, it implies that excess at least half the right-hand side occurs with probability at least half the right-hand side, so Theorem 3.1 is matched at fixed confidence, up to logarithmic factors. The sharp log(1/𝛿) dependence is not addressed here. The two shattered structures. The class is a product over a disjoint domain, ( ℎ1 (𝑥), 𝑥 ∈ X1 , H := Hcube ⊕ W, (ℎ1 , ℎ2 )(𝑥) = ℎ2 (𝑥), 𝑥 ∈ X2 . The first factor carries the Natarajan structure and the noise: X1 = {𝑥0 , 𝑥1 , . . . , 𝑥𝑑N }, and Hcube consists of the 2𝑑N hypotheses 𝑔𝜎 , 𝜎 ∈ {±1}𝑑N , with 𝑔𝜎 (𝑥0 ) = 𝑦0 on an anchor point and 𝑔𝜎 (𝑥𝑖 ) ∈ {𝑎 𝑖 , 𝑏𝑖 } according to 𝜎𝑖 , for distinct labels 𝑎 𝑖 ≠ 𝑏𝑖 and an anchor label 𝑦0 . The second factor carries the DS structure without paying Natarajan capacity, and this is the one place an external ingredient enters. Lemma 4.2 (Separation pseudo-cubes). For every 𝐷 ∈ N there are a finite label set [𝐾𝐷 ] and a pseudocube 𝑉 ⊆ [𝐾𝐷 ] 𝐷 whose induced class W = {𝑣(·) : 𝑣 ∈ 𝑉} on the domain [𝐷] satisfies Nat(W) ≤ 1 and DS(W) = 𝐷. Proof. [BCD+ 22] construct a class H0 with Nat(H0 ) = 1 that is not PAC learnable, and prove that PAC learnability is characterized by finiteness of the DS dimension; hence DS(H0 ) = ∞. Fix 𝐷 and a DS-shattered sequence of length 𝐷: its trace contains a pseudo-cube 𝑉, which is a finite set by definition, so only finitely many labels occur in it. Any Natarajan shattering of the induced class W transfers, through the realizing hypotheses, to a Natarajan shattering of H0 on the corresponding 15

points, so Nat(W) ≤ Nat(H0 ) = 1. Finally DS(W) ≥ 𝐷 because the full sequence is shattered by 𝑉, and DS(W) ≤ 𝐷 because the domain has 𝐷 points and no sequence with a repeated point is DS-shattered: at a repeated coordinate every trace vector takes equal values, while a pseudo-cube requires a neighbor differing at exactly one of the two copies. □ Example 4.3 (The 6-cycle). At 𝐷 = 2 the object of Lemma 4.2 can be written down: 𝑉 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 1)} ⊆ [3] 2 . Every element has a neighbor in each coordinate, so 𝑉 is a pseudo-cube and DS = 2; no two rows share two columns, so no pair of witness labels is shattered and Nat = 1. Products of such cycles do not give the general case: by Lemma 4.4 below, Natarajan dimension adds across products, which is exactly why Lemma 4.2 needs the global construction of [BCD+ 22]. Lemma 4.4 (Dimension calculus). The restriction of a pseudo-cube to a nonempty subset of its coordinates is a pseudo-cube. Consequently, for classes on disjoint domains, Nat(H1 ⊕ H2 ) = Nat(H1 ) + Nat(H2 ),

DS(H1 ⊕ H2 ) = DS(H1 ) + DS(H2 ),

and anchor points on which all hypotheses agree contribute to neither dimension. With W from Lemma 4.2 at 𝐷 = 𝑑DS , Lemma 4.4 gives Nat(H) = 𝑑N + Nat(W) ∈ {𝑑N , 𝑑N + 1} and DS(H) = 𝑑N + 𝑑DS , as claimed in Theorem 4.1. The two engines. The localized term is produced by a noisy pair-Assouad construction on the cube factor (Lemma B.1), the multiclass transplant of the classical binary construction [DL95]: each p 𝑥𝑖 receives mass 𝜏  𝐿★ /𝑑N and a label drawn from the witness pair with bias 𝛾  𝑑N /(𝑛𝐿★ ), while the anchor absorbs the remaining mass at a deterministic label, keeping the oracle risk equal to 𝐿★ for every sign pattern simultaneously. Distinguishing the favored label at one point from 𝑛 samples is then a two-point testing problem whose error is bounded through the total variation between the two sample laws [Tsy09, Chapter 2], and each undecided point costs excess 2𝛾𝜏. The coverage term is produced on the pseudo-cube factor by a realizable leave-one-out argument, in the tradition of the classical realizable lower bounds [EHKV89]. Its combinatorial core deserves to be stated on its own; the pseudo-cube axiom enters exactly once. Lemma 4.5 (Fiber lemma). Let 𝑉 ⊆ [𝐾] 𝐷 be a pseudo-cube, let 𝐽 ⊆ [𝐷] be nonempty, and suppose the cloud 𝐶 = {𝑢 ∈ 𝑉 : 𝑢𝑗 = 𝑤𝑗 ∀𝑗 ∉ 𝐽} is nonempty for some fixed values 𝑤. Then for every 𝑖 ∈ 𝐽 and every label 𝑦, {𝑢 ∈ 𝐶 : 𝑢𝑖 = 𝑦} ≤ 21 |𝐶|. Proof. Partition 𝐶 into fibers: 𝑢 ∼ 𝑢0 iff 𝑢𝑗 = 𝑢𝑗0 for all 𝑗 ≠ 𝑖. For 𝑢 ∈ 𝐶, its pseudo-cube neighbor 𝑢 (𝑖) agrees with 𝑢 off 𝑖, hence lies in 𝐶 (because 𝑖 ∈ 𝐽) and in the fiber of 𝑢; so every fiber has at least two elements. Within a fiber, distinct elements differ exactly at coordinate 𝑖, so their 𝑖th entries are pairwise distinct and each label occurs at most once per fiber. Hence |{𝑢 ∈ 𝐶 : 𝑢𝑖 = 𝑦}| ≤ #{fibers} ≤ |𝐶|/2. □ In the realizable problem “labels drawn by an unknown 𝑣 ∈ 𝑉,” the cloud is precisely the posterior support after observing the sample, and the posterior under the uniform prior is uniform on it. Lemma 4.5 therefore says that at every unseen coordinate, every prediction is wrong with conditional probability at least 12 —the pseudo-cube keeps all of its coordinates permanently ambiguous. Uniformly spreading mass 𝜈/𝐷 over the 𝐷 points leaves each point unseen with probability (1 − 𝜈/𝐷) 𝑛 , and 𝜈 := min{𝐷/𝑛, 41 } balances mass against ambiguity (Lemma B.2). 16

Putting it all together. The final distribution family places mass 1 − 𝜈 on the noisy cube component, calibrated so that the total oracle risk is exactly 𝐿★ , and mass 𝜈 on the pseudo-cube component with labels given by 𝑣 ∈ 𝑉: e𝜎 + 𝜈 U𝑣 , D𝜎,𝑣 := (1 − 𝜈) D

(𝜎, 𝑣) ∈ {±1}𝑑N × 𝑉,

where U𝑣 denotes the uniform distribution on the 𝐷 labeled pairs {(𝑧𝑖 , 𝑣𝑖 ) : 𝑖 ∈ [𝐷]}. Because H is a product class over disjoint supports, its infimum risk splits into the two components; the pseudocube component is realizable, so inf ℎ 𝐿D𝜎,𝑣 (ℎ) = 𝐿★ for every (𝜎, 𝑣), and excess risks add across the two components. Averaging the side-1 bound over 𝜎 and the side-2 bound over 𝑣, the expected excess of any learner against the uniform prior is at least the sum of the two terms in (4.1), so some single (𝜎, 𝑣) achieves it. The full proof, with all constants, is in Section B. Remark 4.6 (Growing alphabets are necessary). For 𝑑DS  𝑑N the label alphabet in Theorem 4.1 must grow. At constant excess risk, Lemma B.2 forces 𝑛 ≥ 𝑐 DS(H) samples in the realizable case; ERM arguments give 𝑛 = 𝑂(𝑑𝐺 ) at constant excess, where 𝑑𝐺 is the Graph dimension [DSBS15]; and 𝑑𝐺 = 𝑂(𝑑N log 𝐾) by the classical comparison of the two dimensions [BCHL95]. Chaining the three, DS(H) = 𝑂(Nat(H) log 𝐾): a separation 𝑑DS  𝑑N is only possible when 𝐾 ≥ exp(Ω(𝑑DS /𝑑N )). This is why Theorem 3.1’s uniformity in 𝐾 is the right setting for the two-dimensional rate: at bounded alphabets the two dimensions collapse to within a logarithmic factor, and the interpolation question degenerates. Remark 4.7 (Beyond the constructed family). If the exact-𝐿★ constraint is relaxed to inf ℎ 𝐿D (ℎ) ≤ 𝐿★ , the two terms of (4.1) hold for every class, with Nat(H) − 1 and DS(H) − 1 in place of the constructed dimensions: fix one coordinate of a shattered structure and use its value as the anchor; the subfamily fixing that coordinate is again a shattering structure of one lower dimension, both for sign cubes and, by the neighbor axiom, for pseudo-cubes. The exact-𝐿★ , single-distribution form of Theorem 4.1 genuinely uses the constructed product class: for an entangled class the two structures need not admit a common distribution whose infimum risk is computable exactly.

5

Extension: optimistic rates for list learning

The intermediate object of the upper-bound architecture is already a list-valued predictor: the menu of Section 2 assigns each point a set of candidate labels, and the final block exists only to collapse that set to a single label. It is therefore natural to ask what the architecture says about list learning, where the learner is allowed to output a bounded list of labels and is charged only when the true label misses the entire list. List PAC learning was characterized by [CP23]: for a fixed list size 𝑟, learnability is equivalent to finiteness of their 𝑟-DS dimension. The quantitative picture has been sharpened in a rapid sequence of works, through multiclass boosting [BDMM23], an optimal 𝑘-ary Sauer lemma [HMMS26], and the resolution of the Daniely–Shalev-Shwartz density conjecture [Pab26], whose rates are the current state of the art. All of these guarantees, however, compare the list learner to the best single hypothesis, and their fluctuation terms are worst-case in the oracle risk. This section states the optimistic-rate analogue: the comparator is upgraded to the best 𝑟-tuple of hypotheses, the fluctuation is localized at the oracle list risk, and a matching construction forces both terms of the rate at every fixed oracle level. The lower bound proves, quantitatively and with exact calibration, an expectation recorded in [Pab26], that a fluctuation term of 𝑟-ary Natarajan type is necessary against list comparators; and its second engine yields, as a byproduct, a factor-𝑟 improvement of the known realizable list lower bound (Corollary 5.3). 17

Table 2: List-learning risk bounds. Each cell shows the excess-risk scale and its source; constants, logarithms, and the truncations of Theorems 4.1 and 5.2 are suppressed. Binary labels admit no nontrivial lists: for 𝐾 = 2 and 𝑟 ≥ 2 the full-label list has zero risk. In the third row the first rates are due to [CP23], successively 𝑟 /(𝑟𝑛), and Corollary 5.3 improved by [BDMM23, HMMS26, Pab26]; the lower bound of [HMZ24] reads 𝑑DS removes its factor 𝑟. Its two columns differ in shape because a list can hedge against a single comparator, so no fluctuation-type lower bound is possible there (Remark 5.5). In the highlighted row the comparator is the best 𝑟-tuple, both columns share one shape, and the dimension gap is Remark 5.5.

Setting Binary, 𝑟 = 1 Multiclass, 𝑟 = 1

Upper bound p 𝐿★ 𝑑/𝑛 + 𝑑/𝑛

Lower bound p 𝐿★ 𝑑/𝑛 + 𝑑/𝑛

[MQZ26]

[DL95, AHV25]

p 𝐿★ 𝑑N /𝑛 + 𝑑DS /𝑛

Theorem 3.1

𝑟-list vs. single ℎ

q 𝑟 /𝑛 + 𝑟𝑑 𝑟 /𝑛 𝑟4 𝑑N DS

𝐿★ 𝑑N /𝑛 + 𝑑DS /𝑛

Theorem 4.1 𝑟 /𝑛 𝑑DS

Corollary 5.3, cf. [HMZ24]

[CP23, Pab26]

𝑟-list vs. 𝑟-tuple

p

p 𝐿𝑟★ 𝑟𝑑N /𝑛 + 𝑟𝑑DS /𝑛

q 𝑟 /𝑛 + 𝑑 𝑟 /𝑛 𝐿𝑟★ 𝑑N DS

this work, Theorem 5.1

this work, Theorem 5.2

Setting. An 𝑟-list predictor is a measurable map 𝜆 : X → {𝑌 ⊆ [𝐾] : |𝑌 | ≤ 𝑟}, and its list risk is
list 𝐿D (𝜆) = P 𝑌 ∉ 𝜆(𝑋) . For an 𝑟-tuple ℎ® = (ℎ1 , . . . , ℎ𝑟 ) ∈ H𝑟 , write Λℎ® (𝑥) = {ℎ1 (𝑥), . . . , ℎ𝑟 (𝑥)} and list 𝐿𝑟★ = inf 𝐿D (Λℎ® ), ® 𝑟 ℎ∈H

the oracle list risk. Since a singleton is a 1-tuple, 𝐿𝑟★ ≤ 𝐿★ , so a bound localized at 𝐿𝑟★ implies the corresponding bound against single comparators. We use the list dimensions of [CP23]: a sequence 𝑥1 , . . . , 𝑥𝑑 is 𝑟-Natarajan shattered if there are witness sets 𝑌𝑖 ⊆ [𝐾] with |𝑌𝑖 | = 𝑟 + 1 such that the Î 𝑟 is the largest such 𝑑; a sequence is 𝑟-DS shattered trace of H contains the full product 𝑖 𝑌𝑖 , and 𝑑N if some finite trace set gives every member, in every coordinate, at least 𝑟 neighbors differing from 𝑟 is the largest such length. At 𝑟 = 1 these are Definitions 2.2 and 2.3, and it exactly there, and 𝑑DS 𝑟 𝑟 𝑑N ≤ 𝑑DS ≤ 𝑑DS with both sequences nonincreasing in 𝑟. Table 2 places the two theorems of this section against the known list-learning rates. Theorem 5.1 (Optimistic rates for list learners). Suppose Assumption 2.1 holds, H has 1 ≤ 𝑑N ≤ 𝑑DS < ∞, and 𝑟 ≥ 1. There is a universal constant 𝐶 > 0 and a learner RMC𝑟 , outputting lists of size at most 𝑟, such that for every distribution D, every 𝑛 ≥ 3, and every 𝛿 ∈ (0, 1), with probability at least 1 − 𝛿, s

!
𝐿𝑟★ 𝑟 𝑑N log3 (𝑒𝑛) + log(1/𝛿) 𝑟 𝑑N log3 (𝑒𝑛) + 𝑑DS log2 (𝑒𝑛) + log(𝑒𝑟/𝛿) list ★ 𝐿D RMC𝑟 (𝑆) ≤ 𝐿𝑟 +𝐶 + . 𝑛 𝑛 (5.1) ★ The learner is independent of 𝐿𝑟 and 𝛿. At 𝑟 = 1 the statement is Theorem 3.1.

18

The proof is in Section C. Blocks 𝑆1 and 𝑆2 are reused verbatim: the same menu covers each component of a comparator tuple at realizable order. The only new module is the third block, a fixed-menu compression scheme whose reconstructions are 𝑟-lists and whose empirical domination is against every 𝑟-tuple. It needs no new capacity analysis: on the subsample where an optimal tuple is list-correct, the points split into 𝑟 groups according to which component covers them, each group is a realizable instance for the single-hypothesis scheme of Lemma A.5, and the union of the 𝑟 reconstructions dominates. The message is an 𝑟-tuple of ordinary messages, and Theorem 3.3 applies with the description count adjusted accordingly: its proof never inspects the loss or the message format beyond measurability, boundedness, and the number of possible descriptions. Theorem 5.2 (Lower bound for list learners). Let 𝑟 ≥ 1. For all integers 𝑑 ≥ 1 and even 𝐷 with 2 ≤ 𝐷 ≤ 2𝑑 there are a finite label set [𝐾] and a finite class H ⊆ [𝐾] X with 𝑟 𝑑 ≤ 𝑑N (H) ≤ 𝑑 + 𝐷2 ,

𝑟 𝑑DS (H) = 𝑑 + 𝐷,

1 such that for every 𝑛 ≥ 1, every 𝐿𝑟★ ∈ [0, 8(𝑟+1) ], and every learner 𝐴 outputting lists of size at most 𝑟, ★ list possibly randomized, there is a distribution D on X × [𝐾] with inf ℎ∈H ® 𝑟 𝐿D (Λℎ® ) = 𝐿𝑟 exactly, under which r n𝐷 1o  list  1 𝐿𝑟★ 𝑑 1 ★ ★ E 𝐿D (𝐴(𝑆)) − 𝐿𝑟 ≥ 1{𝐿𝑟 ≥ 𝑑/𝑛} + min , . (5.2) 48 𝑛 15 𝑛 4 Both terms are forced by the same distribution, and the calibration is Bayes-exact: every list of size 𝑟, from any class, has risk at least 𝐿𝑟★ under every member of the family.

The proof, also in Section C, upgrades both engines of Section 4. The pair-Assouad construction becomes (𝑟 + 1)-ary: each hard point now carries 𝑟 + 1 candidate labels, of which the oracle list drops the lightest, and a learner’s list must still exclude at least one candidate. Distinguishing which candidate is light remains a two-point testing problem, because the two laws obtained by exchanging the roles of two candidates differ on exactly two atoms; the testing chain of Lemma B.1 1 applies with the pair masses 𝑟+1 ± 𝛾-type in place of 12 ± 𝛾. The padded leave-one-out argument runs on pseudo-cube structures of width 2𝑟: every fiber then offers at least 2𝑟 distinct values, of which an 𝑟-list covers at most half, so Lemma B.2 survives with the same constant. The width-2𝑟 device has a consequence for the classical, single-hypothesis-realizable list set𝑟 + ting that seems worth recording separately. The best known realizable list lower bound, Ω (𝑑DS
log(1/𝛿))/(𝑟𝜖) of [HMZ24] (see the summary table of [Pab26]), loses a factor 𝑟 because its hard structures offer 𝑟 + 1 values per coordinate, of which an 𝑟-list misses only one; doubling the width removes the loss. Corollary 5.3 (Realizable list learning without the factor 𝑟). For every 𝑟 ≥ 1 and 𝐷 ≥ 1 there are a finite 𝑟 (H) = 𝐷 such that for every 𝑛 ≥ 1 and every learner 𝐴 outputting label set and a finite class H with 𝑑DS lists of size at most 𝑟, possibly randomized, there is a distribution realizable by H under which n𝐷 1o  list  1 E 𝐿D (𝐴(𝑆)) ≥ min , . 15 𝑛 4 𝑟 /𝜖): the dimension Consequently the realizable sample complexity of 𝑟-list learning is Ω(𝑑DS term of [HMZ24] improves by a factor of 𝑟, and of the 1/𝑟-versus-𝑟 gap to the upper bound
𝑟 + log(1/𝛿))/𝜖 of [Pab26, Corollary 1.3] only the single factor 𝑟 remains. The proof 𝑂 𝑟(𝑑DS (Section C) pads the full width-2𝑟 product class on 𝐷 points and applies the list leave-one-out bound; no Assouad component is involved. Three remarks calibrate the pair of results. 19

Remark 5.4 (What lists buy, and what they do not). The fluctuation term of (5.2) carries no gain in 𝑟: its constant is absolute. This is a cancellation, not an accident of the proof. Spreading one unit of side-1 mass over 𝑟 + 1 candidates divides the per-candidate testing signal 𝛾 by Θ(𝑟), but calibrating the oracle list risk to 𝐿𝑟★ multiplies the per-point mass 𝜏 by Θ(𝑟), and the excess per testing mistake is 𝛾𝜏-scaled, so the two effects cancel in the product 𝛾𝜏𝑑. Lists therefore do not shrink the fluctuation attached to a given oracle level; what they buy is the smaller oracle level itself, 𝐿𝑟★ ≤ 𝐿★ , and the 𝑟 ≤ 𝑑 , 𝑑𝑟 ≤ 𝑑 smaller dimensions 𝑑N N DS at which the terms are charged. DS Remark 5.5 (The dimension gap). The fluctuation of (5.1) scales with 𝑟𝑑N , the fluctuation of (5.2) 𝑟 , and 𝑑 𝑟 ≤ 𝑑 always, with arbitrarily large gaps possible. We conjecture that the truth with 𝑑N N N 𝑟 is 𝑑N up to factors polynomial in 𝑟, and two facts support this. First, in the single-comparator worst-case setting the fluctuation is already controlled by the 𝑟-ary Natarajan dimension: [Pab26, q 𝑟 4 e 𝑟 𝑑 /𝑛) via a fixed-menu list compression of size 𝑂(𝑟 e 4 𝑑𝑟 ) built on the Corollary 1.4] pays 𝑂( N

N

list one-inclusion machinery of [CP23, HMMS26]. Second, [Pab26] records, after that corollary, the expectation that a term of this type is necessary once the algorithm must compete with the best list formed from hypotheses of H, while noting that the standard 𝑟 = 1 lower-bound strategy fails against single comparators because a list can hedge; Theorem 5.2 proves exactly this expectation, 𝑟 of the constructed class. What is missing on the quantitatively and with exact calibration, at the 𝑑N 𝑟 upper side is a fixed-menu compression at 𝑑N whose empirical domination holds against every 𝑟-tuple rather than every single hypothesis: the scheme of [Pab26] dominates single comparators only, and our partition device pays 𝑟𝑑N instead. Symmetrically, the deterministic terms of the two 𝑟 respectively; replacing the cover of block 𝑆 by one built from a bounds are stated at 𝑑DS and at 𝑑DS 1 𝑟 in (5.1), at the cost of reworking realizable list learner [CP23, Pab26] is the natural route toward 𝑑DS the imported modules, and we leave it open. Remark 5.6 (Scope). At 𝑟 = 1 the two theorems reproduce Theorems 3.1 and 4.1, with worse constants in the lower bound; we did not optimize the 𝑟-uniform chain. The restriction 𝐷 ≤ 2𝑑 in Theorem 5.2 mirrors the unconditional diagonal of Theorem 4.1: the general range reduces, ex𝑟 -dimension one at every actly as in Lemma 4.2, to importing a width-2𝑟 separation family with 𝑑N size 𝐷, a list analogue of [BCD+ 22] that we state as an interface in Section C and verify by hand at 𝐷 = 2.

6

Discussion

What transfers from the binary argument. The construction of [MQZ26] contains two conceptually different ingredients: a binary edge-isoperimetric mechanism, and a coefficient-one comparison whose fluctuation is localized by the comparator error. Only the second is used here. The multiclass label geometry is first compressed by the cover and menu of [CEH+ 26, Sections 3.1–3.3], with the realizable parameter sharpened to 𝑑DS using [Pab26]; once the effective loss is binary, relative compression supplies the first-order comparison. This separation is useful: it suggests that an optimistic bound need not reproduce the combinatorial geometry of the problem that originally revealed it. The two dimensions have different statistical roles. In Equation (3.1), 𝑑DS controls the probability that a label on which the oracle is correct never enters the learned menu. This is a realizable-style coverage event and therefore contributes linearly in 1/𝑛. Conditional on the menu, 𝑑N controls the 20

description length of the final empirical-risk-dominating rule. Its contribution is multiplied by 𝐿★ inside the square root. The decomposition (3.9) is what keeps these roles separate; charging all labels outside the menu would mix oracle noise into the coverage term and destroy coefficient one. Theorem 4.1 certifies that the separation is a property of the problem and not of the proof: the same two structures can be made to charge any learner separately, in one class and one distribution. Limitations. First, the logarithmic factors have not been optimized. One logarithm comes from boosting a realizable learner into a compressor, one from enumerating the compression cover or the final list compressor, and one from the stability-free description union bound in Theorem 3.3. The last factor is not removable for generic agnostic compression schemes [HK19]. Stable compression schemes can remove it [HK21], but the fixed-menu compressor used here is not known to be stable, so that route does not follow from the present argument. Second, the learner is information-theoretic. For an abstract hypothesis class, the one-inclusion and reconstruction operations can be intractable. Representation-preserving reductions are an active route toward more algorithmic multiclass guarantees [HMS25], but Theorem 3.1 makes no oracle-efficiency claim. Third, the theorem assumes a finite alphabet. The rate is uniform in 𝐾, and the menu prevents an explicit log 𝐾 term, but the realizable theorem used in Lemma A.1 is invoked in its finite-label form. The finite-DS/infinite-Graph examples motivating the rejection of a direct Graph argument belong to the more general label-space setting; we do not claim an infinite-label extension here. Open questions. Three questions seem especially concrete. p 1. Can one obtain 𝐿★ 𝑑N /𝑛 + 𝑑DS /𝑛 without any logarithmic loss by jointly sharpening the boosted cover and the menu compressor? Stability alone can address only the final descriptioncounting factor. 2. Theorem 4.1 is stated in expectation and leaves the sharp log(1/𝛿) dependence at fixed 𝐿★ open; the binary small-error theory [AHV25] suggests the target form. 3. Can the three independent blocks be replaced by cross-fitting while retaining coefficient one and a learner independent of 𝐿★ and 𝛿? The relative-compression theorem is intentionally modular: any improvement to the menu construction or its final description length immediately sharpens the corresponding term in Equation (3.1). AI Disclosure. The authors acknowledge the use of GPT-5.6 Solar and Claude Fable 5 as assistive tools in preparing this manuscript. The project began with our reading of the binary optimal-rate theory of [MQZ26]; the question of the multiclass analogue, the choice to route it through the cover– menu–compression architecture, and the design of the lower-bound construction were developed in extended discussions with both models, which also supported the drafting and polishing of the exposition and the detailed proof steps. The Lean 4 formalization was written by Claude Fable 5. All AI-assisted material, including every theorem statement, proof, and formalization choice, was reviewed, edited, and validated by the authors, who take full responsibility for the final manuscript and its results.

21

References [ACSZ23]

Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, and Nikita Zhivotovskiy. Optimal PAC bounds without uniform convergence. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science, pages 1203–1223, 2023.

[ADD+ 24] Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, and Shang-Hua Teng. Regularization and optimal multiclass learning. In Proceedings of the 37th Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 260–310, 2024. [AHHM21] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of PAC learnability of partial concept classes. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science, pages 658–671, 2021. [AHV25]

Julian Asilis, Mikael Møller Høgsgaard, and Grigoris Velegkas. On agnostic PAC learning in the small error regime. In Advances in Neural Information Processing Systems 38, 2025. arXiv:2502.09496.

[BBM05]

Peter L. Bartlett, Olivier Bousquet, and Shahar Mendelson. Local Rademacher complexities. The Annals of Statistics, 33(4):1497–1537, 2005.

[BCD+ 22]

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science, pages 943–955, 2022.

[BCHL95]

Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler, and Philip M. Long. Characterizations of learnability for classes of {0, . . . , 𝑛}-valued functions. Journal of Computer and System Sciences, 50(1):74–86, 1995.

[BDMM23] Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran. Multiclass boosting: Simple and intuitive weak learning criteria. In Advances in Neural Information Processing Systems 36, pages 1403–1425, 2023. [BLM13]

Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, Oxford, 2013.

[CEH+ 26]

Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang. Sample complexity of agnostic multiclass classification: Natarajan dimension strikes back. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026. arXiv:2511.12659.

[CP23]

Moses Charikar and Chirag Pabbaraju. A characterization of list learnability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023.

[DL95]

Luc Devroye and Gábor Lugosi. Lower bounds in pattern recognition and learning. Pattern Recognition, 28(7):1011–1018, 1995.

[DMY16]

Ofir David, Shay Moran, and Amir Yehudayoff. Supervised learning through the lens of compression. In Advances in Neural Information Processing Systems 29, pages 2784– 2792, 2016. 22

[DS14]

Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Proceedings of the 27th Conference on Learning Theory, volume 35 of Proceedings of Machine Learning Research, pages 287–316, 2014.

[DSBS15]

Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the ERM principle. Journal of Machine Learning Research, 16:2377–2404, 2015.

[EHKV89] Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247–261, 1989. [FW95]

Sally Floyd and Manfred Warmuth. Sample compression, learnability, and the Vapnik– Chervonenkis dimension. Machine Learning, 21(3):269–304, 1995.

[GHS05]

Thore Graepel, Ralf Herbrich, and John Shawe-Taylor. PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification. Machine Learning, 59(1–2):55–76, 2005.

[GKN17]

Lee-Ad Gottlieb, Aryeh Kontorovich, and Pinhas Nisnevitch. Nearly optimal classification for semimetrics. Journal of Machine Learning Research, 18(37):1–22, 2017.

[HK19]

Steve Hanneke and Aryeh Kontorovich. A sharp lower bound for agnostic learning with sample compression schemes. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learning Research, pages 489–505, 2019.

[HK21]

Steve Hanneke and Aryeh Kontorovich. Stable sample compression schemes: New applications and an optimal SVM margin bound. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 697–721, 2021.

[HLW94]

David Haussler, Nick Littlestone, and Manfred K. Warmuth. Predicting {0, 1}functions on randomly drawn points. Information and Computation, 115(2):248–292, 1994.

[HLZ24]

Steve Hanneke, Kasper Green Larsen, and Nikita Zhivotovskiy. Revisiting agnostic PAC learning. In Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science, 2024.

[HMMS26] Steve Hanneke, Qinglin Meng, Shay Moran, and Amirreza Shaeiri. An optimal Sauer lemma over 𝑘-ary alphabets, 2026. arXiv:2604.12952. [HMS25]

Steve Hanneke, Qinglin Meng, and Amirreza Shaeiri. Representation preserving multiclass agnostic to realizable reduction. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 21995–22008, 2025.

[HMZ24]

Steve Hanneke, Shay Moran, and Qian Zhang. Improved sample complexity for multiclass PAC learning. In Advances in Neural Information Processing Systems 37, 2024. 23

[MQZ26]

Markus Engelund Mathiasen, Jian Qian, and Nikita Zhivotovskiy. An optimal agnostic PAC algorithm, 2026. arXiv:2608.06363.

[Nat89]

Balas K. Natarajan. On learning sets and functions. Machine Learning, 4(1):67–97, 1989.

[Pab26]

Chirag Pabbaraju. The optimal sample complexity of multiclass and list learning, 2026. arXiv:2604.24749.

[Pan02]

Dmitriy Panchenko. Some extensions of an inequality of Vapnik and Chervonenkis. Electronic Communications in Probability, 7:55–65, 2002.

[RBR06]

Benjamin I. P. Rubinstein, Peter L. Bartlett, and J. Hyam Rubinstein. Shifting, oneinclusion mistake bounds and tight multiclass expected risk bounds. In Advances in Neural Information Processing Systems 19, 2006.

[SST10]

Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Optimistic rates for learning with a smooth loss, 2010. arXiv:1009.3896. Conference version: Smoothness, low noise and fast rates, NeurIPS 2010.

[Tsy09]

Alexandre B. Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, 2009.

[ZH18]

Nikita Zhivotovskiy and Steve Hanneke. Localization of VC classes: Beyond local Rademacher complexities. Theoretical Computer Science, 742:27–49, 2018.

24

A

Proofs for the upper bound

A.1

Imported modules

This subsection states every external result used in the proof in the exact form in which it is applied. The statements are collected here so that the main text can follow the causal order of the argument; no proof step depends on an unstated result. Each source locator, convention change, and applicability check is recorded in the proof immediately following the corresponding statement. Figure 2 displays the dependency structure of the upper-bound proof and separates the imported modules from the statements proved in this paper; the lower bound of Theorem 4.1 is handled separately in Section B. 𝑑RE (H) ≤ 𝐶𝑑DS [Pab26, Cor. 1.1]; Lemma A.1

b compression cover F [CEH+ 26, Prop. 3.3, Thm. 3.2];

finite family

menu 𝜇 [CEH+ 26, Thm. 3.4];

fixed menu ℓ𝜇

fixed-menu compressor [CEH+ 26, Prop. 3.6];

Lemma A.4

Lemmas A.2 and A.3

Lemmas A.5 and A.6 (3.3)

coverage error (3.7): 𝛼𝜇 (ℎ★ ) ≲ 𝑑DS log2 (𝑒𝑛)/𝑛

relative compression this paper; Theorem 3.3 (3.8)

selective-menu identity Lemma 2.4

p e 𝐿★ 𝑑N /𝑛+𝑑DS /𝑛) 𝐿D (RMC(𝑆)) ≤ 𝐿★ +𝑂(

Theorem 3.1:

Figure 2: Dependency structure of the proof. Blue boxes are imported modules: each carries its source locator and the lemma below in which it is restated with its convention checks. Red boxes are proved in this paper. Gray boxes are the intermediate estimates and the pointwise identity that composes them. The concentration input to Theorem 3.3 is the one-sided Bernstein inequality of Lemma A.7 [BLM13, Sections 2.4 and 2.8].

Realizable dimension. For a learner 𝐵, let RE E𝐵,H (𝑚) =

sup

D: inf ℎ∈H 𝐿D (ℎ)=0

E𝑆∼D𝑚 ,𝐵 𝐿D (𝐵 (𝑆))

be its worst-case expected error over H-realizable distributions; the expectation includes the learner’s internal randomness. Following [CEH+ 26, Definition 2.8], define RE 𝑑RE (H, 𝑟) = inf inf {𝑚 ∈ N : E𝐵,H (𝑚) ≤ 𝑟}, 𝐵

25

𝑑RE (H) = 𝑑RE (H, 1/(9𝑒)).

Lemma A.1 (DS-to-realizable-dimension bridge). Let H ⊆ [𝐾] X have 1 ≤ 𝑑DS < ∞. Then 
 𝑑RE (H) ≤ 9.64(18𝑒) 𝑑DS + log(36𝑒) ≤ 𝐶𝑑DS for a universal constant 𝐶. Proof. [Pab26, Corollary 1.1] gives, for every finite-label class of DS dimension 𝑑DS , a realizable learner whose error is at most 𝜀0 , with probability at least 1 − 𝛿0 , whenever the sample size is at least 𝑑DS + log(2/𝛿0 ) 9.64 𝜀0 observations. Take 𝜀0 = 𝛿0 = 1/(18𝑒). Since the loss is at most one, the learner’s expected error is at most 1 (1 − 𝛿0 )𝜀0 + 𝛿0 ≤ 𝜀0 + 𝛿0 = . 9𝑒 This is exactly the expected-error threshold in [CEH+ 26, Definition 2.8], including the learner’s internal randomness. Substituting log(2/𝛿0 ) = log(36𝑒) and 1/𝜀0 = 18𝑒, then taking the ceiling, proves the first inequality. The second follows because log(36𝑒) is a numerical constant and 𝑑DS ≥ 1. □ For a deterministic selection scheme 𝐴 = (𝜅, 𝜌) defined on samples of every finite length, write 𝑘𝐴 (𝑁) := sup

sup |𝜅(𝑠)|

1≤𝑚≤𝑁 𝑠∈Z 𝑚

for its size function. Lemma A.2 (Ordinary compression from realizable dimension). Let H ⊆ [𝐾] X have finite DS dimension and 𝑑RE (H) < ∞. There is a measurable deterministic zero–one empirical-risk-dominating compression scheme 𝐴1 , defined on all finite samples, whose size function satisfies 𝑘1 (𝑚) ≤ 𝐶 (𝑑RE (H) + 1) log(𝑒𝑚),

𝑚 ≥ 1.

Consequently, under the hypotheses of Lemma A.1, 𝑘1 (𝑚) ≤ 𝐶𝑑DS log(𝑒𝑚). Proof. [CEH+ 26, Equation (17) and Lemma C.1 in Appendices B–C] compare the optimal expectederror rate encoded by 𝑑RE with the deterministic one-inclusion density. Proposition 3.3 of the same paper then boosts the resulting one-inclusion rule into a deterministic ordinary compression scheme, in the boosting-to-compression tradition of [DMY16]. In the source’s notation, the construction is defined for every finite sample, its reconstruction has no larger empirical zero–one loss than any comparator in H, and its size obeys 𝑘1 (𝑚) ≤ 𝐶 (𝑑RE (H) + 1) log(𝑒𝑚),

𝑚 ≥ 1.

Thus it is precisely an empirical-risk-dominating selection scheme in the sense used here. Two degenerate branches deserve explicit conventions. On the empty sample the message is empty, and we fix 𝜌(∅) = ℎ† for an arbitrary fixed classifier ℎ† . If a nonempty sample 𝑠 contains no observation on which any hypothesis of H is correct, then inf ℎ∈H b 𝐿𝑠 (ℎ) = 1, so every reconstruction, in particular the empty-message one, satisfies the domination requirement automatically. Neither branch affects the size bound. The measurability clause is covered by Assumption 2.1. Finally, Lemma A.1 and 𝑑DS ≥ 1 give 𝑑RE (H) + 1 ≤ 𝐶𝑑DS , and hence 𝑘1 (𝑚) ≤ 𝐶𝑑DS log(𝑒𝑚). □ 26

𝑚 , 𝑚 ≥ 1, and a classifier ℎ, let 𝑠[ℎ] be the ordered subseFor a labeled sequence 𝑠 = ((𝑥𝑖 , 𝑦𝑖 ))𝑖=1 quence of examples for which ℎ(𝑥𝑖 ) = 𝑦𝑖 . For 𝑗 ≥ 0, let 𝑠𝑗 be the ordered 𝑗-tuples drawn from the entries of 𝑠, with repetition allowed; 𝑠0 contains only the empty tuple.

Lemma A.3 (Compression cover). Let 𝐴 = (𝜅, 𝜌) be a measurable deterministic ordinary compression scheme for H, with size function 𝑘𝐴 . Define  𝑘𝐴 (𝑚)    Ø     𝑠𝑗 , Cover(𝑠, H, 𝐴) = 𝜌(𝑡) : 𝑡 ∈     𝑗=0  

𝑓ℎ,𝑠 = 𝐴(𝑠[ℎ]).

Then 𝑓ℎ,𝑠 ∈ Cover(𝑠, H, 𝐴), and |Cover(𝑠, H, 𝐴)| ≤

𝑘Õ 𝐴 (𝑚)

𝑚𝑗 ≤ (𝑚 + 1) 𝑘𝐴 (𝑚)+1 .

𝑗=0

For every distribution D, every fixed ℎ ∈ H, and every 𝜂 ∈ (0, 1), if 𝑆 ∼ D𝑚 , then with probability at least 1 − 𝜂, (𝑘𝐴 (𝑚) + 1) log(𝑒𝑚) + log(1/𝜂) P(ℎ(𝑋) = 𝑌 ≠ 𝑓ℎ,𝑆 (𝑋)) ≤ 𝐶 . 𝑚 Under the hypotheses of Lemma A.1, choose 𝐴 = 𝐴1 from Lemma A.2 and, for 𝑆 ∼ D𝑚 , set b = Cover(𝑆, H, 𝐴1 ). For every realization of 𝑆, F b| ≤ 𝐶𝑑DS log2 (𝑒𝑚). log | F

(S.1)

Moreover, for each fixed ℎ ∈ H, with probability at least 1 − 𝜂, P(ℎ(𝑋) = 𝑌 ≠ 𝑓ℎ,𝑆 (𝑋)) ≤ 𝐶

𝑑DS log2 (𝑒𝑚) + log(1/𝜂) . 𝑚

(S.2)

The family and the canonical witness 𝑓ℎ,𝑆 = 𝐴1 (𝑆 [ℎ]) are measurable functions of 𝑆 under Assumption 2.1. Proof. Fix 𝑠 and ℎ. The message 𝜅(𝑠[ℎ]) is an ordered sequence of entries of 𝑠. If 𝑠[ℎ] is empty, the selection property forces this message to be empty as well. If 𝑠[ℎ] is nonempty, the definition of the size function gives |𝜅(𝑠[ℎ])| ≤ 𝑘𝐴 (|𝑠[ℎ]|) ≤ 𝑘𝐴 (𝑚). Thus, in both cases, |𝜅(𝑠[ℎ])| ≤ 𝑘𝐴 (𝑚). Consequently 𝑓ℎ,𝑠 = 𝜌(𝜅(𝑠[ℎ])) belongs to the displayed cover. There are at most 𝑚𝑗 ordered messages of length 𝑗, so |Cover(𝑠, H, 𝐴)| ≤

𝑘Õ 𝐴 (𝑚)

𝑚𝑗 ≤ (𝑚 + 1) 𝑘𝐴 (𝑚)+1 .

𝑗=0

The last envelope follows, for example, by comparing with the binomial expansion of (𝑚+1) 𝑘𝐴 (𝑚)+1 ; unlike the shorthand 𝑚𝑘𝐴 (𝑚)+1 , it remains valid at 𝑚 = 1. [CEH+ 26, Algorithm 2 and Theorem 3.2] apply this very witness 𝐴(𝑆 [ℎ]) and give, pointwise for every fixed comparator ℎ, P(ℎ(𝑋) = 𝑌 ≠ 𝑓ℎ,𝑆 (𝑋)) ≤ 𝐶

(𝑘𝐴 (𝑚) + 1) log(𝑒𝑚) + log(1/𝜂) 𝑚 27

with probability at least 1 − 𝜂. This is a correct-region guarantee: no claim is made on examples on which ℎ(𝑋) ≠ 𝑌. Now take 𝐴 = 𝐴1 . The preceding cardinality bound and Lemma A.2 yield b| ≤ (𝑘1 (𝑚) + 1) log(𝑚 + 1) ≤ 𝐶𝑑DS log2 (𝑒𝑚), log | F which is (S.1); substituting the same size estimate into the source generalization bound gives (S.2). Finally, Assumption 2.1 makes the compression map and reconstruction measurable. Taking orb dered subsequences and forming the finite family therefore preserves measurability, both for F and for the canonical witness 𝑓ℎ,𝑆 . □ Lemma A.4 (Finite-family menu). Let G be a sigma-field. Conditional on G, let F0 be a fixed nonempty finite family and let 𝑓 ∈ F0 be fixed. Let 𝑇 ∈ N, 𝑇 ≥ 1, let 𝑍1 , . . . , 𝑍𝑇 ∼ D be iid and independent of G, and let the random seed be independent of 𝜎(G, 𝑍1 , . . . , 𝑍𝑇 ). Run [CEH+ 26, Algorithm 3] with learning rate 1/2 on these observations. Its classifiers ℎ1 , . . . , ℎ𝑇 −1 define 𝜇(𝑥) = {ℎ1 (𝑥), . . . , ℎ𝑇 −1 (𝑥)},

sup |𝜇(𝑥)| ≤ 𝑇 − 1. 𝑥

For every 𝜂 ∈ (0, 1), with conditional probability at least 1 − 𝜂, P(𝑓(𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋)) ≤

4 log |F0 | + 14 log(3/𝜂) + 12 . 𝑇

(S.3)

The probability is over the fresh observations and the algorithm’s random seed; the assertion is pointwise in the comparator 𝑓. Proof. After conditioning on G, both F0 and the comparator 𝑓 are fixed, while the observations and the algorithmic seed retain the independence required by the source theorem. [CEH+ 26, Algorithm 3 and Theorem 3.4], specialized to learning rate 1/2, run multiplicative weights for 𝑇 iid rounds on this finite family. The output classifiers are ℎ1 , . . . , ℎ𝑇 −1 , so their pointwise union satisfies sup𝑥 |𝜇(𝑥)| ≤ 𝑇 − 1. For every comparator fixed before those rounds, the theorem gives P(𝑓(𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋)) ≤

4 log |F0 | + 14 log(3/𝜂) + 12 𝑇

with probability at least 1 − 𝜂. This is exactly (S.3). Since the theorem is applied on each conditional probability space, its probability is only over the fresh observations and the independent seed, as claimed. □ Lemma A.5 (Fixed-menu loss compression). Let 𝜇 be a fixed measurable 𝑝-menu with 𝑝 ∈ N, 𝑝 ≥ 2, and let H have Natarajan dimension 𝑑N ≥ 1. For every 𝑁 ∈ N, 𝑁 ≥ 1, there is a measurable deterministic empirical-risk-dominating compression scheme, denoted LSCS(𝜇, H, 𝑝), under ℓ𝜇 , whose size satisfies 𝑘𝜇 (𝑁) ≤ 𝐶𝑑N log(𝑝) log(𝑒𝑁).

(S.4)

Here 𝑝 may be any deterministic upper bound on sup𝑥 |𝜇(𝑥)|, rather than its exact value. Proof. [CEH+ 26, Proposition 3.6 and Algorithm 8] construct, for every fixed 𝑝-menu with 𝑝 ≥ 2, an ℓ𝜇 -sample-compression scheme of size 𝐶𝑑N log(𝑝) log(𝑒𝑁). Their defining condition says that the reconstructed classifier’s empirical ℓ𝜇 -loss is no larger than that of any comparator in H; this 28

is exactly empirical domination in (2.10). The construction is deterministic once 𝜇 is fixed, and measurability is supplied by Assumption 2.1. Inspecting the source construction shows that the parameter 𝑝 enters in exactly two places, and both are monotone. Algorithmically, 𝑝 sets the subsample length 𝑚 = b60𝑑N log 𝑝c of the weak learners that are majority-voted; a larger 𝑝 only lengthens these subsamples, which preserves each weak guarantee. Quantitatively, with the source’s constants, a weak learner run on subsamples of length 𝑚 = b60𝑑N log 𝑝c over a menu of true width 𝑞 ∈ [2, 𝑝] has expected error at most 20𝑑N log 𝑞 20𝑑N log 𝑝 1 ≤ = , 𝑚+1 60𝑑N log 𝑝 3 which is exactly the threshold the boosting step consumes; true widths below two only shrink the restricted trace further. Analytically, the proof uses 𝑝 only through the pointwise inequality |𝜇(𝑥)| ≤ 𝑝 on the restricted trace, which any upper bound satisfies a fortiori. Thus running the scheme with a deterministic upper bound in place of the exact supremum leaves every step of the source proof valid and only loosens the stated size (S.4), which is the direction in which it is consumed. The displayed Algorithm 8 contains a term singular at 𝑝 = 1 (the subsample length vanishes), which explains the restriction 𝑝 ≥ 2; the size-zero branch in Lemma A.6 handles the empty- and singleton-menu cases used in our algorithm. As in Lemma A.2, we fix the degenerate branch by convention: if no hypothesis of H is correct on any inside-menu observation of 𝑠, the selector returns the empty message and the reconstruction is a fixed classifier. Every comparator then incurs ℓ𝜇 -loss on every observation with 𝑦𝑖 ∈ 𝜇(𝑥𝑖 ), so ℓ 𝐿𝑠 𝜇 (ℎ) equals the fraction of such observations, while the ℓ𝜇 -loss of any reconstruction is at inf ℎ∈H b most that fraction; empirical domination on this branch is automatic. □ The source compression interface begins at 𝑝 = 2, whereas the learned menu may be empty or a singleton when the second block is small. The following internal lemma closes this edge case without changing the algorithmic or statistical argument. Lemma A.6 (Menu finalizer). Let 𝜇 be a fixed measurable menu and let H have Natarajan dimension 𝑑N ≥ 1. Suppose 𝑇 ∈ N, 𝑇 ≥ 1, and sup𝑥 |𝜇(𝑥)| ≤ 𝑇 − 1. If 𝑇 ≤ 2, define 𝑔𝜇 (𝑥) to return the unique member of 𝜇(𝑥) when present and a fixed label otherwise, and let 𝐵𝜇,𝑇 be the size-zero selection scheme with empty message and reconstruction 𝜌(∅) = 𝑔𝜇 . If 𝑇 ≥ 3, let 𝐵𝜇,𝑇 = LSCS(𝜇, H, 𝑇 − 1). Then, for every 𝑁 ∈ N, 𝑁 ≥ 1, the scheme 𝐵𝜇,𝑇 is empirical-risk-dominating under ℓ𝜇 . Its compression size on 𝑁 observations is zero when 𝑇 ≤ 2, and is at most 𝐶𝑑N log(𝑇 − 1) log(𝑒𝑁) when 𝑇 ≥ 3. Proof. If 𝑇 ≤ 2, every menu is empty or a singleton. Whenever 𝑦 ∈ 𝜇(𝑥), its unique member is 𝑦, so ℓ𝜇 (𝑔𝜇 , (𝑥, 𝑦)) = 0 pointwise. Thus 𝑔𝜇 is a size-zero empirical-risk-dominating selection scheme with the stated empty message. If 𝑇 ≥ 3, use Lemma A.5 with the deterministic upper bound 𝑝 = 𝑇 − 1 ≥ 2. □ Lemma A.7 (One-sided Bernoulli Bernstein inequality). Let 𝑊1 , . . . , 𝑊𝑚 be iid Bernoulli random variÍ ables with mean 𝑝, let 𝑊 = 𝑚−1 𝑚 𝑖=1 𝑊𝑖 , and let 𝑢 > 0. Each of the inequalities r r 2𝑝𝑢 𝑢 2𝑝𝑢 𝑢 𝑊 ≤𝑝+ + , 𝑝≤𝑊+ + 𝑚 3𝑚 𝑚 3𝑚 holds with probability at least 1 − 𝑒−𝑢 . 29

Proof. We use Bernstein’s inequality in its sub-gamma tail form:√if 𝑋1 , . . . , 𝑋𝑚 are independent, Í Í centered, bounded above by 1, with 𝑖 E𝑋𝑖2 ≤ 𝑣, then 𝑖 𝑋𝑖 ≤ 2𝑣𝑢 + 𝑢/3 with probability at Í least 1 − 𝑒−𝑢 [BLM13, Sections 2.4 and 2.8]. Apply this separately to the sums 𝑚 𝑖=1 (𝑊𝑖 − 𝑝) and Í𝑚 𝑖=1 (𝑝 − 𝑊𝑖 ). In both cases the summands are centered, bounded above by one, and have total variance 𝑚𝑝(1 − 𝑝) ≤ 𝑚𝑝, so 𝑣 = 𝑚𝑝 is admissible. Dividing the resulting bounds by 𝑚 proves the two claims. □

A.2

Proof of the relative compression theorem

Theorem 3.3 (Relative compression). Let (Z, Z ) and (F, F ) be measurable spaces, let H ⊆ F, and let ℓ : F × Z → {0, 1} be jointly measurable. Fix 𝑁 ≥ 1 and an integer 𝑘 ≥ 0. Let 𝐴 = (𝜅, 𝜌) be a measurable deterministic selection scheme such that, on every sample 𝑠 ∈ Z 𝑁 , 𝜅(𝑠) is an ordered sequence of at most 𝑘 elements of 𝑠 (indices may repeat), 𝐴(𝑠) = 𝜌(𝜅(𝑠)), and b 𝐿𝑠ℓ (ℎ). 𝐿𝑠ℓ (𝐴(𝑠)) ≤ inf b

(3.3)

ℎ∈H

Then, for every probability distribution D on (Z, Z ), 𝑆 ∼ D𝑁 , every fixed ℎ ∈ H, and every 𝛿 ∈ (0, 1), with probability at least 1 − 𝛿, q ℓ ℓ ℓ (ℎ)Γ (𝑘, 𝛿) + 20Γ (𝑘, 𝛿). 𝐿D (3.4) (𝐴(𝑆)) ≤ 𝐿D (ℎ) + 12 𝐿D 𝑁 𝑁 No stability assumption on the selection map is required. ℓ (ℎ) and Γ = Γ (𝑘, 𝛿). If Γ ≥ 1/20, the claim is immediate because 20Γ ≥ 1 and Proof. Write 𝐿 = 𝐿D 𝑁 the loss is at most one. We henceforth assume Γ < 1/20. In particular, 𝑁 ≥ 2 and

Γ 𝑘 ≤ < 0.073. 𝑁 log 2

(A.1)

For every ordered index sequence 𝐼 = (𝑖1 , . . . , 𝑖𝑗 ), 0 ≤ 𝑗 ≤ 𝑘, let 𝑈𝐼 ⊆ [𝑁] be its set of distinct indices, let 𝑟𝐼 = |𝑈𝐼 |, and define 𝑓𝐼 = 𝜌(𝑍𝑖1 , . . . , 𝑍𝑖𝑗 ),

e 𝐿𝐼 (𝑓𝐼 ) =

1 Õ ℓ(𝑓𝐼 , 𝑍𝑖 ). 𝑁 − 𝑟𝐼 𝑖∉𝑈 𝐼

There are at most 𝑀=

𝑘 Õ

𝑁 𝑗 ≤ (𝑁 + 1) 𝑘+1

(A.2)

𝑗=0

such descriptions. For a fixed 𝐼, condition on (𝑍𝑖 )𝑖∈𝑈𝐼 . Then 𝑓𝐼 is fixed, while the remaining 𝑁 −𝑟𝐼 observations are iid. The second inequality in Lemma A.7, integrated over the selected observations and followed by a union bound over (A.2), shows that, with probability at least 1 − 𝛿/2, simultaneously for every 𝐼, p 𝑠𝐼 𝑝𝐼 ≤ e 𝐿𝐼 (𝑓𝐼 ) + 2𝑝𝐼 𝑠𝐼 + , 3

ℓ 𝑝𝐼 = 𝐿 D (𝑓𝐼 ),

𝑠𝐼 =

log(2𝑀/𝛿) . 𝑁 − 𝑟𝐼

(A.3)

Repeated indices cause no difficulty: only the distinct coordinates in 𝑈𝐼 are removed, while ordered sequences are still counted in 𝑀. 30

For the realized sample, choose any index sequence 𝐼 whose value sequence equals 𝜅(𝑆). The simultaneous event (A.3) was established before this pointwise choice, so no measurable selector among duplicate representations is needed. Empirical domination and nonnegativity give e 𝐿𝐼 (𝑓𝐼 ) ≤

𝑁 bℓ 𝑁 bℓ 𝐿𝑆 (𝑓𝐼 ) ≤ 𝐿 (ℎ). 𝑁 − 𝑟𝐼 𝑁 − 𝑟𝐼 𝑆

(A.4)

Separately, the first inequality in Lemma A.7, applied to the fixed comparator, implies with probability at least 1 − 𝛿/2, r 2𝐿 log(2/𝛿) log(2/𝛿) b + . (A.5) 𝐿𝑆ℓ (ℎ) ≤ 𝐿 + 𝑁 3𝑁 On the intersection of these two events, put 𝜃 = 𝑘/𝑁; the letter 𝑢 stays reserved for the deviation parameter of Lemma A.7. By (A.1), 𝜃 < 0.073, so (1 − 𝜃) −1 ≤ 1.08. Moreover, log(2/𝛿) ≤ 𝑁Γ and log(2𝑀/𝛿) ≤ 𝑁Γ. Set 𝑞𝐼 = e 𝐿𝐼 (𝑓𝐼 ). Therefore   √ 1 Γ 𝑞𝐼 ≤ 𝐿 + 2𝐿Γ + 1−𝜃 3 √ 2𝐿Γ + Γ/3 𝜃 𝐿+ . =𝐿+ 1−𝜃 1−𝜃 Because 𝐿 √ ≤ 1, 𝜃 ≤ Γ/log 2, and (1 − 𝜃) −1 ≤ 1.08, the three excess terms on the last line are at most 1.56Γ, 1.53 𝐿Γ, and 0.36Γ, respectively. Also 𝑠𝐼 ≤

𝑁Γ ≤ 1.08Γ. 𝑁−𝑘

Thus, after rounding constants upward,

√ 𝑞𝐼 ≤ 𝐿 + 2 𝐿Γ + 2Γ,

𝑠𝐼 ≤ 1.08Γ.

(A.6)

It remains to solve the implicit inequality in (A.3). If 𝑝𝐼 ≤ 𝑞𝐼 , the desired conclusion follows directly from (A.6). Otherwise, put 𝑑 = 𝑝𝐼 − 𝑞𝐼 > 0. Subadditivity of the square root and Young’s inequality give p p 𝑠𝐼 𝑑 ≤ 2𝑞𝐼 𝑠𝐼 + 2𝑠𝐼 𝑑 + 3 p 𝑑 4𝑠𝐼 ≤ 2𝑞𝐼 𝑠𝐼 + + , 2 3 and therefore

p 8𝑠𝐼 𝑝𝐼 ≤ 𝑞𝐼 + 2 2𝑞𝐼 𝑠𝐼 + . 3 To make the last substitution explicit, subadditivity of the square root, (A.6), and √ q √ 𝐿Γ + Γ , Γ 𝐿Γ ≤ 2 give

(A.7)

q   √ √ √ p √ √ 2𝑞𝐼 𝑠𝐼 ≤ 2.16 𝐿Γ + 2Γ 𝐿Γ + 2 Γ ≤ 2.51 𝐿Γ + 3.12Γ.

Substitution into (A.7) now gives

√ 𝑝𝐼 ≤ 𝐿 + 8 𝐿Γ + 12Γ.

The looser constants 12 and 20 in (3.4) follow. The two failure probabilities sum to at most 𝛿. 31

□

A.3

Proof of the multiclass theorem

Theorem 3.1 (Small-error multiclass learning). Suppose Assumption 2.1 holds and H ⊆ [𝐾] X has 1 ≤ 𝑑N ≤ 𝑑DS < ∞. There is a universal constant 𝐶 > 0 such that, for every distribution D on X × [𝐾], every 𝑛 ≥ 3, and every 𝛿 ∈ (0, 1), the output of RMC satisfies, with probability at least 1 − 𝛿 over the sample and the menu learner’s randomness, s ! 2 ★ (𝑑 log3 (𝑒𝑛) + log(1/𝛿)) 𝑑 log3 (𝑒𝑛) + 𝑑 𝐿 log (𝑒𝑛) + log(1/𝛿) N N DS 𝐿D (RMC(𝑆)) ≤ 𝐿★ +𝐶 + . (3.1) 𝑛 𝑛 The learner is independent of 𝐿★ and 𝛿, and may be computationally inefficient. Proof. Let 𝑛𝑖 = |𝑆𝑖 | and 𝑇 = 𝑛2 . For the balanced split in Algorithm 1, 𝑛𝑖 ≥ b𝑛/3c ≥ 𝑛/5 for 𝑛 ≥ 3; all three block sizes are therefore comparable to 𝑛 up to universal constants. Fix 𝜖 > 0 and choose ℎ★ ∈ H such that 𝐿D (ℎ★ ) ≤ 𝐿★ + 𝜖.

(A.8)

b = Cover(𝑆1 , H, 𝐴1 ), and define the canonical Let 𝐴1 be the deterministic scheme in Lemma A.2, let F witness 𝑓1★ = 𝑓ℎ★ ,𝑆1 = 𝐴1 (𝑆1 [ℎ★ ]). b and 𝑓★ are 𝜎(𝑆1 )-measurable, and 𝑓★ ∈ F b for every realization of 𝑆1 . By Lemma A.3, with Both F 1 1 probability at least 1 − 𝛿/3, the event E1 holds on which P(ℎ★ (𝑋) = 𝑌 ≠ 𝑓1★ (𝑋)) ≤ 𝐶

𝑑DS log2 (𝑒𝑛) + log(3/𝛿) . 𝑛

(A.9)

Conditional on 𝜎(𝑆1 ), the family and 𝑓1★ are fixed before 𝑆2 and the independent menu seed are drawn. Apply Lemma A.4 with 𝜂 = 𝛿/3. The tower property turns its conditional failure bound into the unconditional bound P(E2𝑐 ) ≤ 𝛿/3, where 𝛽𝑓1★ (𝜇) ≤

b| + 14 log(9/𝛿) + 12 4 log | F 𝑑DS log2 (𝑒𝑛) + log(1/𝛿) ≤𝐶 . 𝑛2 𝑛

On E1 ∩ E2 , apply (2.3) with ℎ = ℎ★ and 𝑓 = 𝑓1★ . Together with (A.9), this gives 𝛼𝜇 := P(ℎ★ (𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋)) ≤ 𝐶

𝑑DS log2 (𝑒𝑛) + log(1/𝛿) . 𝑛

(A.10)

Let 𝑅𝜇 be an independent random seed encoding the draws in Algorithm 3, and condition on G2 = 𝜎(𝑆1 , 𝑆2 , 𝑅𝜇 ). Then 𝜇 and the final rule 𝐵𝜇,𝑇 from Lemma A.6 are fixed, while 𝑆3 ∼ D𝑛3 remains iid and independent of G2 . Write 𝑓b = 𝐵𝜇,𝑇 (𝑆3 ) = RMC(𝑆). The rule is empirical-risk-dominating under ℓ𝜇 . Its size 𝑘2 (𝑛3 ) is zero if 𝑇 ≤ 2; if 𝑇 ≥ 3, then 𝑘2 (𝑛3 ) ≤ 𝐶𝑑N log(𝑇 − 1) log(𝑒𝑛3 ) ≤ 𝐶𝑑N log2 (𝑒𝑛).

(A.11)

Thus, in either branch, (𝑘2 (𝑛3 ) + 1) log(𝑛3 + 1) + log(12/𝛿) 𝑛3 3 𝑑N log (𝑒𝑛) + log(1/𝛿) . ≤𝐶 𝑛

Γ𝑛3 (𝑘2 (𝑛3 ), 𝛿/3) =

32

(A.12)

Here the additive constant in log(12/𝛿) is absorbed by 𝑑N log3 (𝑒𝑛), using 𝑑N ≥ 1 and 𝑛 ≥ 3. Apply Theorem 3.3 conditionally on G2 , with comparator ℎ★ and failure probability 𝛿/3. It produces an event E3 satisfying P(E3𝑐 | G2 ) ≤ 𝛿/3 almost surely. Taking expectations gives P(E3𝑐 ) ≤ 𝛿/3. On E3 , (A.12) and (3.4) imply s ! 3 ★ ) (𝑑 log3 (𝑒𝑛) + log(1/𝛿)) 𝐿 (ℎ 𝑑 log (𝑒𝑛) + log(1/𝛿) 𝜇 N N ★ b − 𝐿𝜇 (ℎ ) ≤ 𝐶 𝐿𝜇 ( 𝑓) + . (A.13) 𝑛 𝑛 Here 𝐿𝜇 is the population loss for the realized fixed menu. The decomposition (2.4), applied with 𝑔 = 𝑓b and ℎ = ℎ★ , holds deterministically for every realization of the menu: b − 𝐿D (ℎ★ ) ≤ 𝐿𝜇 ( 𝑓) b − 𝐿𝜇 (ℎ★ ) + 𝛼𝜇 . 𝐿D ( 𝑓)

(A.14)

Probability enters only through the estimates substituted into its right-hand side. By (2.5), 𝐿𝜇 (ℎ★ ) ≤ 𝐿D (ℎ★ ). On E1 ∩ E2 ∩ E3 , substituting (A.10) and (A.13) into (A.14), then using (A.8), proves (3.1) with 𝐿★ replaced by 𝐿★ + 𝜖. Indeed, the three displayed failure bounds sum to at most 𝛿. It remains to let 𝜖 ↓ 0: take a sequence 𝜖𝑗 ↓ 0. The learner is the same for every 𝑗—in particular, it uses neither 𝜖𝑗 , 𝐿★ , nor 𝛿—and the deterministic risk thresholds obtained above decrease to the right-hand side of (3.1). Continuity from above of probability therefore yields the stated event with e form in (1.3). probability at least 1 − 𝛿. Finally, (2.1) gives the simpler 𝑂 □

B

Proofs for the lower bound

This appendix proves Theorem 4.1. Except for the import recorded in Lemma 4.2, whose four-line derivation from [BCD+ 22] already appears in the main text, the argument is self-contained. All distributions below are finitely supported, so every infimum over the finite class H is attained and no measurability conditions are required. Figure 3 displays the dependency structure. separation pseudocube 𝑉, Nat ≤ 1 [BCD+ 22]; Lemma 4.2

fiber lemma Lemma 4.5

class Hcube ⊕ W

dimension calculus: Nat and DS are additive Lemma 4.4

padded leave-one-out

noisy pair-Assouad

Lemma B.2

Lemma B.1 localized term (B.11)

coverage term (B.10) dimensions

  Theorem 4.1: E 𝐿D (𝐴(𝑆)) − 𝐿★ = p
Ω 𝐿★ 𝑑N /𝑛 + 𝑑DS /𝑛 at exact 𝐿★

Figure 3: Dependency structure of the lower bound, in the format of Figure 2. The single imported module is the separation family of [BCD+ 22], restated with its derivation in Lemma 4.2; every red box is proved in this paper. The testing inputs to Lemma B.1 are Pinsker’s inequality and the Neyman–Pearson two-point bound [Tsy09, Chapter 2].

33

Throughout, a learner is a map 𝐴 : (X ×[𝐾]) 𝑛 ×R → [𝐾] X together with an arbitrary distribution over the seed set R; all bounds are on expectations over the sample and the seed jointly, so it suffices to prove them for each fixed seed, that is, for deterministic 𝐴.

B.1

The noisy pair-Assouad lemma

Lemma B.1 (Localized Natarajan lower bound). Let 𝑑 ≥ 1 and let the points 𝑥0 , 𝑥1 , . . . , 𝑥𝑑 ∈ X , the labels 𝑎 𝑖 ≠ 𝑏𝑖 , and the anchor label 𝑦0 be as in Section 4, with a class H whose restrictions to {𝑥0 , . . . , 𝑥𝑑 } ¯ ∈ [𝑑/𝑛, 1/6], and set are exactly the cube family {𝑔𝜎 : 𝜎 ∈ {±1}𝑑 }. Fix 𝑛 ≥ 1 and 𝐿 r  1i ¯ ¯ 1 𝑑 𝐿 4 𝐿 𝛾 := , 𝑑𝜏 = 1 ≤ . ∈ 0, , 𝜏 := 1 ¯ 8 𝑛𝐿 8 9 𝑑( 2 − 𝛾) 2 −𝛾 e𝜎 place mass 1 − 𝑑𝜏 on (𝑥0 , 𝑦0 ) and mass 𝜏 on each 𝑥𝑖 , with label 𝑎 𝑖 with probability For 𝜎 ∈ {±1}𝑑 let D 1 1 2 + 𝛾𝜎𝑖 and 𝑏𝑖 with probability 2 − 𝛾𝜎𝑖 . Then:
¯ for every 𝜎, attained by any hypothesis restricting to 𝑔𝜎 . (i) inf ℎ∈H 𝐿De𝜎 (ℎ) = 𝑑𝜏 12 − 𝛾 = 𝐿 (ii) For every learner 𝐴, with 𝜎 uniform on {±1}𝑑 , 



s

¯ ≥ 1 E𝜎 E𝑆∼De𝑛 𝐿De𝜎 (𝐴(𝑆)) − 𝐿 𝜎 10

¯ 𝐿𝑑 . 𝑛

Proof. Write 𝑦𝑖(+1) := 𝑎 𝑖 and 𝑦𝑖(−1) := 𝑏𝑖 . Risk identity and (i). For any classifier 𝑔,

𝐿De𝜎 (𝑔) = (1 − 𝑑𝜏) 1{𝑔(𝑥0 ) ≠ 𝑦0 } +

𝑑 Õ

(𝜎𝑖 )  1  ,  2 − 𝛾, 𝑔(𝑥𝑖 ) = 𝑦𝑖    (−𝜎𝑖 ) 1 𝑟𝑖 (𝑔) = 2 + 𝛾, 𝑔(𝑥𝑖 ) = 𝑦𝑖 ,     1, otherwise. 

𝜏 𝑟𝑖 (𝑔),

𝑖=1

(B.1)

Since 𝑟𝑖 ≥ 12 − 𝛾 always, every 𝑔 has risk at least 𝑑𝜏( 12 − 𝛾), with equality iff 𝑔(𝑥0 ) = 𝑦0 and 𝑔(𝑥𝑖 ) = 𝑦𝑖(𝜎𝑖 ) for all 𝑖; the hypothesis restricting to 𝑔𝜎 achieves this, and by the restriction hypothesis no member of H does better. This proves (i). Moreover, comparing (B.1) against the minimum and


using 12 + 𝛾 − 12 − 𝛾 = 2𝛾 and 1 − 12 − 𝛾 ≥ 2𝛾, ¯ ≥ 2𝛾𝜏 𝐿De𝜎 (𝑔) − 𝐿

𝑑 Õ  1 𝑔(𝑥𝑖 ) ≠ 𝑦𝑖(𝜎𝑖 ) .

(B.2)

𝑖=1

e𝜎𝑛 Per-coordinate testing. Fix a coordinate 𝑖 and a value of 𝜎−𝑖 , and compare the two sample laws D with 𝜎𝑖 = ±1. They differ only in the label law at 𝑥𝑖 , so, writing kl(𝛼 k 𝛽) for the divergence between Bernoulli laws, the per-observation divergence is  𝜏 · kl 12 + 𝛾

1 2 −𝛾



1

+𝛾

4𝛾 2 ≤𝜏· 1 ≤ 16𝜏𝛾 2 , − 𝛾 − 𝛾 2 2

= 𝜏 · 2𝛾 log 21

(B.3)

using log(1 + 𝑡) ≤ 𝑡 and 𝛾 ≤ 14 . By the chain rule and Pinsker’s inequality (see, e.g., [BLM13]), s   p 1 1 𝑛 𝑛 2 e 𝑖,+ , D e 𝑖,− ≤ 8𝑛𝜏𝛾 = TV D (B.4) ≤√ , 𝜎 𝜎 1 8( 2 − 𝛾) 3 34

1 where we substituted 𝑛𝜏𝛾 2 = 64(1/2−𝛾) from the definitions of 𝛾 and 𝜏, and used 𝛾 ≤ 81 . Define the

test Ψ := +1 if 𝐴(𝑆)(𝑥𝑖 ) = 𝑎 𝑖 and Ψ := −1 otherwise; then 1{𝐴(𝑆)(𝑥𝑖 ) ≠ 𝑦𝑖(𝜎𝑖 ) } ≥ 1{Ψ ≠ 𝜎𝑖 } in both cases of 𝜎𝑖 . By the Neyman–Pearson two-point bound (see, e.g., [Tsy09, Chapter 2]), for 𝜎𝑖 uniform and conditionally on 𝜎−𝑖 , √ 1 − TV 1 − 1/ 3 1 E𝜎𝑖 E 1{Ψ ≠ 𝜎𝑖 } ≥ ≥ ≥ . (B.5) 2 2 5 Combining. Averaging (B.5) over 𝜎−𝑖 , summing over 𝑖, and inserting into (B.2): 



¯ ¯ ¯ ¯ ≥ 2𝛾𝜏 · 𝑑 = 2𝛾 · 𝐿 ≥ 4𝛾 𝐿 = 4𝐿 · 1 E𝜎 E𝑆∼De𝑛 𝐿De𝜎 (𝐴(𝑆)) − 𝐿 1 𝜎 5 5 2 −𝛾 5 5 8

B.2

r

s 𝑑 1 = ¯ 10 𝑛𝐿

¯ 𝐿𝑑 . 𝑛

□

The realizable pseudo-cube bound

Lemma B.2 (Padded leave-one-out bound). Let 𝑉 ⊆ [𝐾] 𝐷 be a pseudo-cube realized by hypotheses of H on distinct points 𝑧1 , . . . , 𝑧𝐷 . Fix 𝜈 ∈ (0, 12 ] and let {D𝑣 }𝑣∈𝑉 be distributions of the form D𝑣 = (1 − 𝜈) Q + 𝜈 U𝑣 , where the outside component Q does not depend on 𝑣 and is supported off {𝑧1 , . . . , 𝑧𝐷 }, and U𝑣 is the uniform distribution on the 𝐷 labeled pairs {(𝑧𝑖 , 𝑣𝑖 ) : 𝑖 ∈ [𝐷]}. Then for every learner 𝐴, with 𝑣 uniform on 𝑉, " # 𝐷 𝜈 𝑛 𝜈 𝜈 Õ 𝜈 E𝑣 E𝑆∼D𝑣𝑛 1− ≥ 𝑒−2𝜈𝑛/𝐷 . (B.6) 1{𝐴(𝑆)(𝑧𝑖 ) ≠ 𝑣𝑖 } ≥ 𝐷 𝑖=1 2 𝐷 2 Proof. Let 𝐽 ⊆ [𝐷] be the set of indices 𝑖 such that 𝑧𝑖 does not occur in the sample. The 𝑥-part of the sample has the same law for every 𝑣, and the labels at the observed 𝑧𝑗 equal 𝑣𝑗 deterministically, while the labels of the outside component carry no information about 𝑣. Fix the entire sample except for the identity of 𝑣: under the uniform prior, the posterior of 𝑣 is uniform on the cloud 𝐶 = {𝑢 ∈ 𝑉 : 𝑢𝑗 = 𝑣𝑗 ∀𝑗 ∉ 𝐽}, because every 𝑢 ∈ 𝐶 generates the observed sample with the same probability and every 𝑢 ∉ 𝐶 with probability zero. For 𝑖 ∈ 𝐽, the prediction 𝐴(𝑆) (𝑧𝑖 ) is a fixed label given the sample, so by Lemma 4.5 it disagrees with 𝑣𝑖 with conditional probability at least 1 2 . Hence " # 𝐷 𝜈 Õ 𝜈 𝜈 𝑛 𝜈 1 E𝑣 E𝑆∼D𝑣𝑛 · E |𝐽 | = 1 − , 1{𝐴(𝑆)(𝑧𝑖 ) ≠ 𝑣𝑖 } ≥ 𝐷 𝑖=1 𝐷 2 2 𝐷 since each index is unseen with probability (1 − 𝜈/𝐷) 𝑛 . The final bound in (B.6) is the inequality 1 − 𝑡 ≥ 𝑒−2𝑡 for 𝑡 ∈ [0, 12 ], applied with 𝑡 = 𝜈/𝐷 ≤ 12 . □

B.3

Dimension calculus

Lemma 4.4 (Dimension calculus). The restriction of a pseudo-cube to a nonempty subset of its coordinates is a pseudo-cube. Consequently, for classes on disjoint domains, Nat(H1 ⊕ H2 ) = Nat(H1 ) + Nat(H2 ),

DS(H1 ⊕ H2 ) = DS(H1 ) + DS(H2 ),

and anchor points on which all hypotheses agree contribute to neither dimension. 35

Proof. Projection. Let 𝑉 ⊆ [𝐾] 𝐷 be a pseudo-cube and 𝑆 ⊆ [𝐷] nonempty. For 𝑢 ∈ 𝑉 | 𝑆 pick a preimage 𝑣 ∈ 𝑉 and a coordinate 𝑖 ∈ 𝑆; the neighbor 𝑣 (𝑖) , which differs from 𝑣 exactly at 𝑖, restricts to an element of 𝑉 | 𝑆 differing from 𝑢 exactly at 𝑖. Hence 𝑉 | 𝑆 is a pseudo-cube. Sums, lower direction. Concatenating a Natarajan-shattered (resp. DS-shattered) sequence of H1 with one of H2 shatters the concatenation, because a product of sign cubes is a sign cube and a product of pseudo-cubes is a pseudo-cube: a single-coordinate neighbor changes one factor only. Sums, upper direction. The trace of H1 ⊕ H2 on a mixed sequence is the product of the factor traces. If it contains a pseudo-cube 𝑊, the projection of 𝑊 to the side-1 coordinates is a pseudocube contained in the trace of H1 , so the number of side-1 coordinates is at most DS(H1 ); likewise for side 2, giving DS(H1 ⊕ H2 ) ≤ DS(H1 ) + DS(H2 ). The Natarajan case is identical, since restricting the 2𝑑 sign patterns to a coordinate subset yields all sign patterns on that subset. Anchors. In a shattered sequence every coordinate takes at least two values in the trace: a witness pair for Natarajan shattering, a differing neighbor for DS shattering. Both fail at a point on which all hypotheses agree. □

B.4

Proof of the lower bound theorem

Theorem 4.1 (Fixed-𝐿★ lower bound). For all integers 1 ≤ 𝑑N ≤ 𝑑DS there are a finite label set [𝐾] and a finite class H ⊆ [𝐾] X with 𝑑N ≤ Nat(H) ≤ 𝑑N + 1,

DS(H) = 𝑑N + 𝑑DS ,

such that for every 𝑛 ≥ 1, every 𝐿★ ∈ [0, 1/8], and every learner 𝐴, possibly randomized, there is a distribution D on X × [𝐾] with inf ℎ∈H 𝐿D (ℎ) = 𝐿★ exactly, under which r o n𝑑   1 𝐿★ 𝑑N 1 DS 1 E 𝐿D (𝐴(𝑆)) − 𝐿★ ≥ (4.1) 1{𝐿★ ≥ 𝑑N /𝑛} + min , , 12 𝑛 15 𝑛 4 the expectation being over 𝑆 ∼ D𝑛 and the learner’s internal randomness. Both terms are forced by the same distribution, drawn from a finite family that depends only on (H, 𝐿★ , 𝑛) and not on the learner. Proof. The class. Let W be the class of Lemma 4.2 with 𝐷 := 𝑑DS , realized by a pseudo-cube 𝑉 ⊆ [𝐾𝐷 ] 𝐷 on points 𝑧1 , . . . , 𝑧𝐷 , with Nat(W) ≤ 1 and DS(W) = 𝐷. Let Hcube be the cube family of Section 4 on 𝑥0 , . . . , 𝑥𝑑N . Since binary pseudo-cubes are connected under single-coordinate flips, the only pseudo-cube in a sign cube is the full cube, so Nat(Hcube ) = DS(Hcube ) = 𝑑N , the anchor contributing nothing by Lemma 4.4. Set H := Hcube ⊕ W on the disjoint union of the two domains, with the label alphabet the union of the two label sets. By Lemma 4.4, Nat(H) = 𝑑N + Nat(W) ∈ {𝑑N , 𝑑N + 1} and DS(H) = 𝑑N + 𝑑DS , as stated. The distribution family. Fix 𝑛 ≥ 1 and 𝐿★ ∈ [0, 1/8], and set 𝜈 := min

n𝐷 1o , , 𝑛 4

h i h i ★ ¯ := 𝐿 𝐿 ∈ 𝐿★ , 43 𝐿★ ⊆ 0, 61 . 1−𝜈

e𝜎 is chosen by cases. If 𝐿★ ≥ 𝑑N /𝑛, take D e𝜎 as in Lemma B.1 with The inner side-1 distribution D ¯ = (𝑑N , 𝐿); ¯ this is admissible because 𝐿 ¯ ≥ 𝐿★ ≥ 𝑑N /𝑛 and 𝐿 ¯ ≤ 1/6. If 0 < 𝐿★ < 𝑑N /𝑛, parameters (𝑑, 𝐿) e𝜎 (independent of 𝜎) place mass 2𝐿 ¯ on 𝑥1 with the label uniform on {𝑎 1 , 𝑏1 } and mass 1 − 2𝐿 ¯ let D ¯ on (𝑥0 , 𝑦0 ); every hypothesis then has side-1 risk exactly 𝐿, which calibrates the oracle risk without

36

any claim of hardness. If 𝐿★ = 0, place all side-1 mass on (𝑥0 , 𝑦0 ). In all cases define, for (𝜎, 𝑣) ∈ {±1}𝑑N × 𝑉, e𝜎 + 𝜈 U𝑣 . D𝜎,𝑣 := (1 − 𝜈) D (B.7) Because H is a product class and the two supports are disjoint, ¯ = 𝐿★ inf 𝐿D𝜎,𝑣 (ℎ) = (1 − 𝜈) inf 𝐿De𝜎 (ℎ1 ) + 𝜈 · 0 = (1 − 𝜈) 𝐿

ℎ∈H

ℎ1

(B.8)

¯ by Lemma B.1(i) in the first case and by direct computation for every (𝜎, 𝑣): the side-1 infimum is 𝐿 in the other two, and the side-2 component is realizable (the hypothesis realizing 𝑣 makes no error there). Excess risk therefore decomposes as 𝐷
𝜈 Õ ¯ 1{𝑔(𝑧𝑖 ) ≠ 𝑣𝑖 }, 𝐿D𝜎,𝑣 (𝑔) − 𝐿 = (1 − 𝜈) 𝐿De𝜎 (𝑔) − 𝐿 + 𝐷 𝑖=1 ★

(B.9)

where the first term is nonnegative for every 𝑔 by the side-1 infimum property. e𝜎 for each fixed 𝜎: the outside component does not Side-2 term. Lemma B.2 applies with Q = D depend on 𝑣 and avoids {𝑧𝑖 }. Averaging over 𝜎 as well, " # 𝐷 n𝐷 1o 𝜈 Õ 𝜈 1 𝑛 (B.10) E𝜎,𝑣 E𝑆∼D𝜎,𝑣 1{𝐴(𝑆)(𝑧𝑖 ) ≠ 𝑣𝑖 } ≥ 𝑒−2𝜈𝑛/𝐷 ≥ min , , 𝐷 𝑖=1 2 15 𝑛 4 1 by the two regimes of 𝜈: if 𝑛 ≥ 4𝐷 then 𝜈 = 𝐷/𝑛 ≤ 41 and 2𝜈 𝑒−2𝜈𝑛/𝐷 = 2𝑒𝐷2 𝑛 ≥ 15 · 𝐷𝑛 ; if 𝑛 < 4𝐷 then 1 · 14 . 𝜈 = 14 and 2𝜈𝑛/𝐷 < 2, so 2𝜈 𝑒−2𝜈𝑛/𝐷 ≥ 18 𝑒−2 ≥ 15 ★ Side-1 term. Suppose 𝐿 ≥ 𝑑N /𝑛. The argument of Lemma B.1(ii) applies to the padded family {D𝜎,𝑣 } with 𝑣 fixed: for each coordinate 𝑖, the two laws D𝜎 𝑖,± ,𝑣 differ only in the label law at 𝑥𝑖 , whose mass is now (1 − 𝜈)𝜏 ≤ 𝜏, so the per-observation divergence is at most the bound (B.3) and (B.4)–(B.5) are unchanged. The excess decomposition (B.9) carries the factor (1 − 𝜈), and with √ p √ √ √ ¯ (1 − 𝜈) 𝐿 = 1 − 𝜈 𝐿★ ≥ 3/4 𝐿★ , s r √ r h ¯ N
i 𝐿𝑑 1 𝐿★ 𝑑N 1 3 𝐿★ 𝑑N ¯ 𝑛 E𝜎,𝑣 E𝑆∼D𝜎,𝑣 (1 − 𝜈) 𝐿De𝜎 (𝐴(𝑆)) − 𝐿 ≥ (1 − 𝜈) · ≥ ≥ . (B.11) 10 𝑛 20 𝑛 12 𝑛

e𝜎 is read off the same decomposition (B.1), which only concerns (The side-1 risk of 𝐴(𝑆) under D the side-1 points; the side-2 part of the sample is shared by the two tested laws and enters the test as ancillary information.) For 𝐿★ < 𝑑N /𝑛 no side-1 claim is made and the first term of (4.1) is zero. Conclusion. Summing (B.11) and (B.10) inside (B.9), r n𝑑 o   1 𝐿★ 𝑑N 1 DS 1 ★ ★ 𝑛 𝐿D𝜎,𝑣 (𝐴(𝑆)) − 𝐿 ≥ E𝜎,𝑣 E𝑆∼D𝜎,𝑣 1{𝐿 ≥ 𝑑N /𝑛} + min , , 12 𝑛 15 𝑛 4 and some (𝜎, 𝑣) attains at least the average, giving a single distribution D := D𝜎,𝑣 with the stated properties. The family (B.7) depends only on (H, 𝐿★ , 𝑛). □

B.5

Which engine for which structure

The two engines of this appendix, and the classical devices they replace, are separated by the combinatorial structure they consume; Table 3 records the comparison, since the choice is reusable beyond this paper. 37

Table 3: Lower-bound devices and the structure they require. The fiber engine is the one that survives when the shattered structure is a pseudo-cube but not a product; at width 𝑤 its per-coordinate yield becomes (𝑤 − 𝑟)/𝑤 against 𝑟-lists (Section C), which is where Corollary 5.3 gains its factor 𝑟. Device

Structure required

Per-coordinate yield

Pair-Assouad (Lemma B.1, Lemma C.4)

full product cube of witness labels in the trace; commuting coordinate flips index the family

testing: excess 𝛾𝜏 per tested coordinate, fluctuation type

Leave-one-out [EHKV89]

realizable completions at unseen points, classically again a product trace

realizable type, 1/𝑛 per coordinate

Fiber engine (Lemma 4.5, Lemma B.2, Lemma C.5)

pseudo-cube only: a neighbor in each direction; no product, no involution structure

conditional error ≥ 21 per unseen coordinate; ≥ (𝑤 − 𝑟)/𝑤 at width 𝑤

The six-cycle of Example 4.3 shows that the extra generality of the third row is not hypothetical, and it makes the phrase “does not lift” from the abstract concrete. The six-cycle is a pseudo-cube on two coordinates with six vertices, and 6 ≠ |𝑆1 | · |𝑆2 | for any witness sets realizing its trace as a product, so no Assouad indexation by sign patterns exists. Its per-coordinate flips are well defined, since every fiber has exactly two elements, but they do not commute: writing 𝜑1 , 𝜑2 for the two flips, on the vertex (0, 0) one has 𝜑1 𝜑2 (0, 0) = (1, 1) while 𝜑2 𝜑1 (0, 0) = (2, 2); the two flips generate a rotation of the hexagon rather than a {±1}2 -action. Every binary-flavored argument that pairs distributions along commuting coordinate involutions therefore breaks on this class, while the fiber engine only reads the sizes of fibers and proceeds. This is why side 2 of the construction in Section B.4 runs on the leave-one-out engine and not on an Assouad engine. A second reusable pattern is the calibration recipe behind (B.8). To pin the oracle risk of a family ¯ = 𝐿★ /(1 − 𝜈), and spread 𝐿 ¯ exactly at a prescribed 𝐿★ , pad with weight 𝜈 of realizable mass, set 𝐿 ¯ there pointwise; the infimum is over the noisy component so that every classifier pays at least 𝐿 ★ ¯ then (1 − 𝜈) 𝐿 = 𝐿 exactly, it is attained inside the class, and, since the pointwise bound holds for every classifier, the calibration is Bayes-exact (Section D, finding (1)). The family depends only on (H, 𝐿★ , 𝑛), never on the learner. Any fixed-oracle-level lower bound that claims equality rather than an inequality for its oracle risk can reuse this padding unchanged.

C

Proofs for the list extension

Throughout this appendix 𝑟 ≥ 1 is the list size. We identify a classifier 𝑓 with the singleton list 𝑥 ↦→ {𝑓(𝑥)}; under this identification every definition below restricts to its counterpart in the main text at 𝑟 = 1. For a menu 𝜇 and a list-valued 𝜆, the inside-menu list loss is
ℓ𝜇 𝜆, (𝑥, 𝑦) = 1{𝑦 ∉ 𝜆(𝑥), 𝑦 ∈ 𝜇(𝑥)}, 𝐿𝜇 (𝜆) = E ℓ𝜇 (𝜆, (𝑋, 𝑌)), (C.1) ℓ

𝐿𝑠 𝜇 are defined as in Section 2. which extends (2.2) verbatim. Empirical versions b

C.1

The list menu calculus

Lemma C.1 (List selective-menu decomposition). Let 𝜇 be a menu. For all list-valued 𝜆, 𝜆0,
list list 0 𝐿D (𝜆) − 𝐿D (𝜆 ) ≤ 𝐿𝜇 (𝜆) − 𝐿𝜇 (𝜆0) + P 𝑌 ∈ 𝜆0 (𝑋), 𝑌 ∉ 𝜇(𝑋) , 38

(C.2)

list (𝜆). Moreover, for every tuple ℎ ® = (ℎ1 , . . . , ℎ𝑟 ) ∈ H𝑟 and every classifier tuple (𝑓1 , . . . , 𝑓𝑟 ), and 𝐿𝜇 (𝜆) ≤ 𝐿D 𝑟 h

i
Õ P ℎ𝑗 (𝑋) = 𝑌 ≠ 𝑓𝑗 (𝑋) + P 𝑓𝑗 (𝑋) = 𝑌, 𝑌 ∉ 𝜇(𝑋) . P 𝑌 ∈ Λℎ® (𝑋), 𝑌 ∉ 𝜇(𝑋) ≤

(C.3)

𝑗=1

Proof. For (C.2), fix (𝑥, 𝑦). If 𝑦 ∈ 𝜇(𝑥), the difference of the two list losses equals the difference of the two inside-menu list losses. If 𝑦 ∉ 𝜇(𝑥), both inside-menu losses vanish, and the list-loss difference can be positive only when 𝑦 ∈ 𝜆0 (𝑥), in which case it is at most one. Taking expectations proves (C.2); the comparison ℓ𝜇 (𝜆, 𝑧) ≤ 1{𝑦 ∉ 𝜆(𝑥)} is pointwise. For (C.3), on the event {𝑌 ∈ Λℎ® (𝑋), 𝑌 ∉ 𝜇(𝑋)} there is some 𝑗 with ℎ𝑗 (𝑋) = 𝑌 ∉ 𝜇(𝑋); bound the probability of each such event by (2.3) with ℎ = ℎ𝑗 and 𝑓 = 𝑓𝑗 , and sum. □

C.2

Relative compression with product messages

The proof of Theorem 3.3 in Section A.2 interacts with the selection scheme only through the count of possible descriptions: a message of at most 𝑘 ordered sample elements has at most (𝑁 + 1) 𝑘+1 realizations, and the argument is a union bound over them. The following variant records the count for messages that are 𝑟-tuples of ordinary messages. Lemma C.2 (Relative compression, product messages). Let ℓ : F × Z → {0, 1} and H ⊆ F be as in Theorem 3.3, and let 𝐴 be a measurable deterministic scheme whose message on a sample 𝑠 ∈ Z 𝑁 is an 𝑟-tuple (𝑡1 , . . . , 𝑡𝑟 ) of ordered sequences of at most 𝐿 elements of 𝑠 each, with 𝐴(𝑠) = 𝜌(𝑡1 , . . . , 𝑡𝑟 ), and which satisfies the domination premise (3.3). Then the conclusion (3.4) of Theorem 3.3 holds with Γ𝑁 (𝑘, 𝛿) taken at 𝑘 + 1 = 𝑟(𝐿 + 1), that is, with Γ=

𝑟(𝐿 + 1) log(𝑁 + 1) + log(4/𝛿) . 𝑁

Proof. The proof of Theorem 3.3 fixes a description, conditions on the named coordinates, applies Lemma A.7 on the untouched coordinates, and takes a union bound over all descriptions; the number of descriptions enters only through the bound 𝑀 ≤ (𝑁 + 1) 𝑘+1 on their count, which sets the (𝑘 + 1) log(𝑁 + 1) term of Γ. An 𝑟-tuple of ordered sequences of at most 𝐿 sample elements has at
𝑟 most (𝑁 + 1) 𝐿+1 = (𝑁 + 1) 𝑟(𝐿+1) realizations, and each tuple names at most 𝑟𝐿 sample coordinates, so every step of the argument is unchanged after replacing 𝑀 by this count. □

C.3

Fixed-menu compression for tuple comparators

Lemma C.3 (Fixed-menu list compression). Let 𝜇 be a fixed measurable menu with sup𝑥 |𝜇(𝑥)| ≤ 𝑝 for a deterministic 𝑝 ≥ 2, and let H have Natarajan dimension 𝑑N ≥ 1. For every 𝑁 ≥ 1 there is a measurable deterministic scheme whose message is an 𝑟-tuple of ordered sequences of at most 𝐿 = 𝑘𝜇 (𝑁) ≤ 𝐶𝑑N log(𝑝) log(𝑒𝑁) sample elements, whose reconstruction is a list rule of size at most 𝑟, and which is empirically dominating against tuples: for every sample 𝑠 ∈ Z 𝑁 , its output b 𝜆 satisfies ℓ ℓ b 𝐿𝑠 𝜇 ( b 𝐿𝑠 𝜇 (Λℎ® ). 𝜆) ≤ min b ® 𝑟 ℎ∈H

(C.4)

Proof. Write 𝐵 = LSCS(𝜇, H, 𝑝) for the single-hypothesis scheme of Lemma A.5, with size function 𝑘𝜇 (·), and let 𝜌𝐵 be its reconstruction. Define the decoder first: on an 𝑟-tuple (𝑡 1 , . . . , 𝑡 𝑟 ) of messages, set 𝜌(𝑡1 , . . . , 𝑡𝑟 )(𝑥) = {𝜌𝐵 (𝑡 1 )(𝑥), . . . , 𝜌𝐵 (𝑡 𝑟 )(𝑥)}, 39

a list of size at most 𝑟. Define the selector 𝜅(𝑠) to be the first, in a fixed enumeration of the finitely many 𝑟-tuples of ordered sequences of at most 𝐿 elements of 𝑠, tuple 𝑡 whose reconstruction satisfies (C.4); measurability is Assumption 2.1 together with finiteness of the search space. It remains to prove that a valid tuple exists. ℓ The empirical loss b 𝐿𝑠 𝜇 (Λℎ® ) takes values in {0, 𝑁1 , . . . , 1}, so its infimum over ℎ® ∈ H𝑟 is attained; fix a minimizer ℎ®∗ = (ℎ∗1 , . . . , ℎ∗𝑟 ). Let  𝑠∗ = 𝑖 ≤ 𝑁 : 𝑦𝑖 ∈ 𝜇(𝑥𝑖 ), 𝑦𝑖 ∈ Λℎ®∗ (𝑥𝑖 ) , the observations on which the minimizing tuple is inside-menu correct, and partition 𝑠∗ into 𝑠∗1 , . . . , 𝑠∗𝑟 by assigning 𝑖 to the smallest 𝑗 with ℎ∗𝑗 (𝑥𝑖 ) = 𝑦𝑖 . Each 𝑠𝑗∗ , viewed as a sample in the order inherited from 𝑠, is handed to 𝐵: let 𝑡𝑗 = 𝜅𝐵 (𝑠∗𝑗 ) and 𝑔𝑗 = 𝜌𝐵 (𝑡 𝑗 ), with the empty-part convention of Lemma A.2 when 𝑠∗𝑗 = ∅. Since ℎ∗𝑗 is inside-menu correct on every observation of 𝑠∗𝑗 , empirical domination of 𝐵 on the sample 𝑠∗𝑗 gives ℓ ℓ b 𝐿𝑠∗𝜇 (𝑔𝑗 ) ≤ b 𝐿𝑠∗𝜇 (ℎ∗𝑗 ) = 0, 𝑗

𝑗

so 𝑔𝑗 is inside-menu correct on all of 𝑠∗𝑗 . Consequently the list 𝜆0 (𝑥) = {𝑔1 (𝑥), . . . , 𝑔𝑟 (𝑥)} has ℓ𝜇 (𝜆0 , (𝑥𝑖 , 𝑦𝑖 )) = 0 for every 𝑖 ∈ 𝑠∗ , and for 𝑖 ∉ 𝑠∗ either 𝑦𝑖 ∉ 𝜇(𝑥𝑖 ), where every list has zero loss, or 𝑦𝑖 ∈ 𝜇(𝑥𝑖 ) and ℎ®∗ also errs. Hence ∗

|{𝑖 : 𝑦𝑖 ∈ 𝜇(𝑥𝑖 )} \ 𝑠 | bℓ𝜇 ℓ b 𝐿𝑠 𝜇 (𝜆0 ) ≤ = 𝐿𝑠 (Λℎ®∗ ), 𝑁 and (𝑡 1 , . . . , 𝑡 𝑟 ) is a valid tuple: each 𝑡 𝑗 is an ordered sequence of at most 𝑘𝜇 (|𝑠∗𝑗 |) ≤ 𝑘𝜇 (𝑁) = 𝐿 elements of 𝑠∗𝑗 ⊆ 𝑠. The size bound on 𝐿 is (S.4). □ As in Lemma A.6, menus with 𝑇 ≤ 2 admit a size-zero branch: the singleton rule 𝑔𝜇 of that lemma, viewed as a 1-list, already has zero inside-menu loss pointwise, and we use it for every 𝑟. (𝑟) for the resulting scheme (Lemma C.3 with 𝑝 = 𝑇 − 1 when 𝑇 ≥ 3). Write 𝐵𝜇,𝑇

C.4

Proof of Theorem 5.1

Theorem 5.1 (Optimistic rates for list learners). Suppose Assumption 2.1 holds, H has 1 ≤ 𝑑N ≤ 𝑑DS < ∞, and 𝑟 ≥ 1. There is a universal constant 𝐶 > 0 and a learner RMC𝑟 , outputting lists of size at most 𝑟, such that for every distribution D, every 𝑛 ≥ 3, and every 𝛿 ∈ (0, 1), with probability at least 1 − 𝛿, s

! 3 2 ★ 𝑟 𝑑 log3 (𝑒𝑛) + log(1/𝛿)
𝐿 𝑟 𝑑 log (𝑒𝑛) + 𝑑 log (𝑒𝑛) + log(𝑒𝑟/𝛿) N N DS 𝑟 list 𝐿D RMC𝑟 (𝑆) ≤ 𝐿𝑟★ +𝐶 + . 𝑛 𝑛 (5.1) The learner is independent of 𝐿𝑟★ and 𝛿. At 𝑟 = 1 the statement is Theorem 3.1. Proof. Run Algorithm 1 unchanged through its first two blocks, and replace the third-block final(𝑟) (𝑟) izer by 𝐵𝜇,𝑇 ; the output is b 𝜆 = 𝐵𝜇,𝑇 (𝑆3 ), a list of size at most 𝑟. The block sizes again satisfy 𝑛𝑖 ≥ 𝑛/5. ★ 𝑟 list (Λ ) ≤ 𝐿★ + 𝜖. For each component define the canon® Fix 𝜖 > 0 and a tuple ℎ ∈ H with 𝐿D 𝑟 ℎ®★ ★ ★𝑗 b ical witness 𝑓 = 𝐴1 (𝑆1 [ℎ ]) ∈ F. Apply Lemma A.3 to each component with 𝜂 = 𝛿/(3𝑟), and 𝑗

Lemma A.4 to each witness with 𝜂 = 𝛿/(3𝑟); the 𝜎-field bookkeeping is verbatim that of Section A.3, 40

applied 𝑟 times, and the tower property is used component by component. On the intersection E1 ∩ E2 of the resulting events, which fails with probability at most 2𝛿/3, (C.3) gives

𝑟 𝑑DS log2 (𝑒𝑛) + log(𝑒𝑟/𝛿) (𝑟) 𝛼𝜇 := P 𝑌 ∈ Λℎ®★ (𝑋), 𝑌 ∉ 𝜇(𝑋) ≤ 𝐶 . (C.5) 𝑛 (𝑟) is Conditional on G2 = 𝜎(𝑆1 , 𝑆2 , 𝑅𝜇 ), the menu is fixed, 𝑆3 is iid and independent, and 𝐵𝜇,𝑇 an empirically dominating scheme against tuples by Lemma C.3, with product messages of block length 𝐿 = 𝑘𝜇 (𝑛3 ) ≤ 𝐶𝑑N log(𝑇 − 1) log(𝑒𝑛3 ) (zero if 𝑇 ≤ 2). Apply Lemma C.2 conditionally, with comparator class {Λℎ® : ℎ® ∈ H𝑟 }, the fixed comparator Λℎ®★ , and failure probability 𝛿/3; the premise (3.3) is (C.4). Its Γ satisfies, in either branch,

Γ=

𝑟(𝐿 + 1) log(𝑛3 + 1) + log(12/𝛿) 𝑟𝑑N log3 (𝑒𝑛) + log(1/𝛿) ≤𝐶 . 𝑛3 𝑛

(C.6)

On the resulting event E3 , q 𝐿𝜇 (b 𝜆) − 𝐿𝜇 (Λℎ®★ ) ≤ 12 𝐿𝜇 (Λℎ®★ ) Γ + 20 Γ.

(C.7)

list (Λ ) ≤ 𝐿★ + 𝜖, and By Lemma C.1, 𝐿𝜇 (Λℎ®★ ) ≤ 𝐿D 𝑟 ℎ®★ list b list ( 𝜆) − 𝐿D (Λℎ®★ ) ≤ 𝐿𝜇 (b 𝐿D 𝜆) − 𝐿𝜇 (Λℎ®★ ) + 𝛼𝜇(𝑟)

holds deterministically. Substituting (C.5), (C.6), and (C.7), and summing the three failure probabilities, proves the bound with 𝐿𝑟★ + 𝜖 in place of 𝐿𝑟★ with probability at least 1 − 𝛿. The learner does not depend on 𝜖, so letting 𝜖 ↓ 0 along a sequence and using continuity from above, exactly as at the end of Section A.3, completes the proof. At 𝑟 = 1 the construction and the bound coincide with those of Theorem 3.1. □

C.5

The (𝑟 + 1)-ary Assouad lemma

Lemma C.4 (Localized 𝑟-Natarajan lower bound). Let 𝑑 ≥ 1, let 𝑥0 , 𝑥1 , . . . , 𝑥𝑑 ∈ X be distinct points, let 𝑎 1 , . . . , 𝑎 𝑟+1 be distinct labels and 𝑦0 an anchor label, and let H be a class whose restrictions to {𝑥0 , . . . , 𝑥𝑑 } ¯ ∈ [𝑑/𝑛, 1 ], are exactly the cube family {𝑔𝑐 : 𝑐 ∈ [𝑟 + 1] 𝑑 }, 𝑔𝑐 (𝑥0 ) = 𝑦0 , 𝑔𝑐 (𝑥𝑖 ) = 𝑎 𝑐𝑖 . Fix 𝑛 ≥ 1 and 𝐿 6(𝑟+1) and set r  i ¯ 1 𝑑 𝐿 1 ¯≤ 4. 𝛾= ∈ 0, 8(𝑟+1) , 𝜏= 𝑑𝜏 ≤ 87 (𝑟 + 1) 𝐿
, 21 1 ¯ 8(𝑟 + 1) 𝑛𝐿 𝑑 −𝛾 𝑟+1

e𝜎 place mass 1 − 𝑑𝜏 on (𝑥0 , 𝑦0 ) and mass 𝜏 on each 𝑥𝑖 , with label 𝑎 𝜎𝑖 having conditional For 𝜎 ∈ [𝑟 + 1] 𝑑 let D 𝛾 1 1 probability 𝑟+1 − 𝛾 and each other candidate 𝑎 𝑐 , 𝑐 ≠ 𝜎𝑖 , having conditional probability 𝑟+1 + 𝑟 . Then: 1 ¯ with equality attained by the tuple (i) every list 𝜆 of size at most 𝑟 has 𝐿list (𝜆) ≥ 𝑑𝜏( 𝑟+1 − 𝛾) = 𝐿, e𝜎 D (𝑔𝜎+1 , . . . , 𝑔𝜎+𝑟 ), where (𝜎 + 𝑘)𝑖 ≡ 𝜎𝑖 + 𝑘 (mod 𝑟 + 1); (ii) for every learner 𝐴 outputting lists of size at most 𝑟, with 𝜎 uniform on [𝑟 + 1] 𝑑 , s ¯  list  1 𝐿𝑑 ¯ ≥ E𝜎 E𝑆∼De𝑛 𝐿 e (𝐴(𝑆)) − 𝐿 . D𝜎 𝜎 40 𝑛

41

e𝜎 decomposes over the atoms: Proof. Risk identity and (i). For any list 𝜆, the risk under D 𝐿list e𝜎 (𝜆) = (1 − 𝑑𝜏) 1{𝑦0 ∉ 𝜆(𝑥0 )} + D

𝑑 Õ 𝑖=1

𝜏

Õ

𝜋𝜎𝑖 (𝑐),

(C.8)

𝑐: 𝑎 𝑐 ∉𝜆(𝑥𝑖 )

where 𝜋𝜎𝑖 (𝑐) is the conditional label law at 𝑥𝑖 . Since |𝜆(𝑥𝑖 )| ≤ 𝑟 < 𝑟 + 1, at least one candidate is 1 excluded at each 𝑥𝑖 , and every candidate has mass at least 𝑟+1 − 𝛾; this proves the infimum claim. The displayed tuple excludes exactly 𝑎 𝜎𝑖 at 𝑥𝑖 and contains 𝑦0 at 𝑥0 (every 𝑔𝑐 (𝑥0 ) = 𝑦0 ), attaining equality. Moreover, whenever the excluded set at 𝑥𝑖 is not exactly {𝑎 𝜎𝑖 }, some candidate of mass 𝛾 1 𝑟+1 + 𝑟 is excluded, so 𝑑   Õ  ¯ ≥ 𝛾 1+ 1 𝜏 𝐿list (𝜆) − 𝐿 1 Ψ𝑖 (𝜆) ≠ 𝜎𝑖 , (C.9) e 𝑟 D𝜎

𝑖=1

where Ψ𝑖 (𝜆) ∈ [𝑟 + 1] denotes the smallest index of a candidate excluded by 𝜆 at 𝑥𝑖 . e𝜎 differ only by Per-coordinate testing. Fix 𝑖, fix 𝜎−𝑖 , and fix two values 𝑐 ≠ 𝑐0 of 𝜎𝑖 . The two laws D 𝛾 1 1 exchanging the masses of the two atoms (𝑥𝑖 , 𝑎 𝑐 ) and (𝑥𝑖 , 𝑎 𝑐0 ), which are 𝜏( 𝑟+1 − 𝛾) and 𝜏( 𝑟+1 + 𝑟 ). 7 1 Writing 𝑞 = 𝑟+1 − 𝛾 ≥ 8(𝑟+1) and 𝑞0 = 𝑞 + 𝛾 (1 + 1𝑟 ), the per-observation divergence is 0 2 0
e𝜎 𝑖,𝑐 D e 𝑖,𝑐0 = 𝜏 (𝑞0 − 𝑞) log 𝑞 ≤ 𝜏 (𝑞 − 𝑞) ≤ 5(𝑟 + 1)𝜏𝛾 2 , kl D 𝜎 𝑞 𝑞

(C.10)

using log(1 + 𝑡) ≤ 𝑡 and (1 + 1𝑟 ) 2 ≤ 4. By the chain rule and Pinsker’s inequality, and then the definitions of 𝛾 and 𝜏, q q 1 𝑛 𝑛
5 1 2 e e TV D𝜎 𝑖,𝑐 , D𝜎 𝑖,𝑐0 ≤ 2 𝑛(𝑟 + 1)𝜏𝛾 ≤ 52 · 56 (C.11) ≤√ . 3 Let Ψ = Ψ𝑖 (𝐴(𝑆)). For each unordered pair {𝑐, 𝑐0 }, the Neyman–Pearson two-point bound gives √
P(Ψ ≠ 𝑐 | 𝜎𝑖 = 𝑐) + P(Ψ ≠ 𝑐0 | 𝜎𝑖 = 𝑐0) ≥ 1 − TV ≥ 1 − 1/ 3. Summing over the 𝑟+1 2 pairs, each conditional appears 𝑟 times, so for 𝜎𝑖 uniform, √ 1 − 1/ 3 1 E𝜎𝑖 P(Ψ ≠ 𝜎𝑖 ) ≥ ≥ . (C.12) 2 5 Combining. Averaging (C.12) over 𝜎−𝑖 , summing over 𝑖, and inserting into (C.9): s   𝑑 ¯ ¯  list  𝛾 (𝑟 + 1) 𝐿 1 𝐿𝑑 ¯ ≥ 𝛾 1+ 1 𝜏· E𝜎 E 𝐿 e (𝐴(𝑆)) − 𝐿 ≥ = , 𝑟 D𝜎 5 5 40 𝑛 ¯ in the middle step. using 𝜏𝑑 ≥ (𝑟 + 1) 𝐿

C.6

□

The list leave-one-out bound

Lemma C.5 (Padded leave-one-out bound, list version). Let 𝑉 ⊆ [𝐾] 𝐷 be realized by hypotheses of H on distinct points 𝑧1 , . . . , 𝑧𝐷 , and suppose every 𝑣 ∈ 𝑉 has, in every coordinate 𝑖, at least 2𝑟 − 1 neighbors in 𝑉 differing from it exactly at 𝑖. Fix 𝜈 ∈ (0, 12 ] and let D𝑣 = (1 − 𝜈)Q + 𝜈 U𝑣 be as in Lemma B.2. Then for every learner 𝐴 outputting lists of size at most 𝑟, with 𝑣 uniform on 𝑉, " # 𝐷 𝜈 Õ 𝜈 𝑛 𝜈 E𝑣 E𝑆∼D𝑣𝑛 1− 1{𝑣𝑖 ∉ 𝐴(𝑆)(𝑧𝑖 )} ≥ . 𝐷 𝑖=1 2 𝐷 42

Proof. The proof of Lemma B.2 applies verbatim up to the fiber step: conditionally on the sample, the posterior of 𝑣 is uniform on the cloud 𝐶 = {𝑢 ∈ 𝑉 : 𝑢𝑗 = 𝑣𝑗 ∀𝑗 ∉ 𝐽}, and for an unseen index 𝑖 ∈ 𝐽 the list 𝐴(𝑆) (𝑧𝑖 ) is fixed given the sample. Partition 𝐶 into fibers by the values off 𝑖. If 𝑢 ∈ 𝐶, its 2𝑟 − 1 neighbors at coordinate 𝑖 agree with 𝑢 off 𝑖, hence lie in the same fiber and in 𝐶 (the cloud constraint involves only coordinates outside 𝐽); distinct elements of a fiber differ exactly at 𝑖, so each fiber contains at least 2𝑟 elements with pairwise distinct 𝑖-values. A list of size 𝑟 therefore contains the 𝑖-value of at most half of each fiber, and the conditional probability that 𝑣𝑖 ∉ 𝐴(𝑆) (𝑧𝑖 ) is at least 1 𝑛 □ 2 . The remainder of the proof, including E|𝐽 | = 𝐷(1 − 𝜈/𝐷) , is unchanged.

C.7

The band family and 𝑟-ary dimension calculus

Lemma C.6 (Width-2𝑟 band). Let 𝑚 = 4𝑟 + 2, 𝐾2 = Z𝑚 , and  𝑉𝑟 = (𝑖, 𝑗) ∈ Z𝑚 × Z𝑚 : 𝑗 − 𝑖 ∈ {0, 1, . . . , 2𝑟 − 1} , viewed as functions on two points. Then (a) every 𝑣 ∈ 𝑉𝑟 has exactly 2𝑟 − 1 neighbors in each coordinate; (b) the class 𝑉𝑟 has 𝑟-Natarajan dimension exactly 1; (c) for every 𝑡 ≥ 1 the product 𝑉𝑟⊗𝑡 , on 𝐷 = 2𝑡 points, 𝑟 (𝑉 ⊗𝑡 ) ≤ 𝑡, and is 𝑟-DS shattered on all 𝐷 coordinates. retains property (a), satisfies 𝑑N 𝑟 Proof. (a) Fixing 𝑗, the first coordinate ranges over the 2𝑟 values 𝑗 − 2𝑟 + 1, . . . , 𝑗; fixing 𝑖, the second ranges over 𝑖, . . . , 𝑖 + 2𝑟 − 1. In each case the 2𝑟 − 1 other admissible values give neighbors differing in exactly that coordinate. (b) One point is 𝑟-Natarajan shattered: each coordinate takes 2𝑟 ≥ 𝑟 + 1 values. Suppose the pair of points were shattered with witness sets 𝑆1 , 𝑆2 ⊆ Z𝑚 , |𝑆1 | = |𝑆2 | = 𝑟 + 1, so that 𝑆1 × 𝑆2 ⊆ 𝑉𝑟 . Fix 𝑖0 ∈ 𝑆1 ; every 𝑗 ∈ 𝑆2 satisfies 𝑗 − 𝑖0 ∈ {0, . . . , 2𝑟 − 1}, so 𝑆2 lies in a cyclic window of length 2𝑟 < 𝑚/2, and likewise 𝑆1 ; lifting both windows to integer representatives, all differences 𝑗 − 𝑖, 𝑖 ∈ 𝑆1 , 𝑗 ∈ 𝑆2 , must lie in [0, 2𝑟 − 1]. In particular max 𝑆2 − min 𝑆1 ≤ 2𝑟 − 1 and min 𝑆2 − max 𝑆1 ≥ 0; subtracting, (max 𝑆2 − min 𝑆2 ) + (max 𝑆1 − min 𝑆1 ) ≤ 2𝑟 − 1, while each spread is at least |𝑆𝑖 | − 1 = 𝑟, a contradiction. (c) The dimension calculus of Lemma 4.4 applies verbatim at arity 𝑟: a product of structures with property (a) has property (a), since a single-coordinate neighbor changes one factor; restricting an (𝑟 + 1)-ary product pattern to a subset of coordinates yields the full pattern on that subset, so the 𝑟 (H ⊕H ) ≤ 𝑑 𝑟 (H )+𝑑 𝑟 (H ) and its DS analogue hold with the same proofs; and the sum bound 𝑑N 1 2 1 2 N N 𝑟-DS shattering of all 2𝑡 coordinates is witnessed by 𝑉𝑟⊗𝑡 itself. Finally, the counting bound behind the caps generalizes: if 𝑊 ⊆ [𝐾] 𝑘 gives every element at least 𝑟 neighbors in every coordinate, then projecting off the last coordinate and using the fact that each fiber has at least 𝑟 + 1 elements yields |𝑊 | ≥ (𝑟 + 1) 𝑘 by induction on 𝑘. □

C.8

Proof of Theorem 5.2

Theorem 5.2 (Lower bound for list learners). Let 𝑟 ≥ 1. For all integers 𝑑 ≥ 1 and even 𝐷 with 2 ≤ 𝐷 ≤ 2𝑑 there are a finite label set [𝐾] and a finite class H ⊆ [𝐾] X with 𝑟 𝑑 ≤ 𝑑N (H) ≤ 𝑑 + 𝐷2 ,

43

𝑟 𝑑DS (H) = 𝑑 + 𝐷,

1 such that for every 𝑛 ≥ 1, every 𝐿𝑟★ ∈ [0, 8(𝑟+1) ], and every learner 𝐴 outputting lists of size at most 𝑟, list ★ possibly randomized, there is a distribution D on X × [𝐾] with inf ℎ∈H ® 𝑟 𝐿D (Λℎ® ) = 𝐿𝑟 exactly, under which r n𝐷 1o  list  1 𝐿𝑟★ 𝑑 1 E 𝐿D (𝐴(𝑆)) − 𝐿𝑟★ ≥ 1{𝐿𝑟★ ≥ 𝑑/𝑛} + min , . (5.2) 48 𝑛 15 𝑛 4 Both terms are forced by the same distribution, and the calibration is Bayes-exact: every list of size 𝑟, from any class, has risk at least 𝐿𝑟★ under every member of the family.

Proof. The class. Let 𝑡 = 𝐷/2 and let W = 𝑉𝑟⊗𝑡 be the band power of Lemma C.6, realized on points 𝑧1 , . . . , 𝑧𝐷 with label set Z4𝑟+2 , disjoint from the side-1 labels. Let Hcube = {𝑔𝑐 : 𝑐 ∈ [𝑟 + 1] 𝑑 } be the cube family of Lemma C.4 on 𝑥0 , . . . , 𝑥𝑑 , and let H = Hcube ⊕W on the disjoint union of the domains. 𝑟 (H) ≥ 𝑑, and it gives every The trace of Hcube on 𝑥1 , . . . , 𝑥𝑑 is the full product {𝑎 1 , . . . , 𝑎 𝑟+1 }𝑑 , so 𝑑N 𝑟 (H) ≥ 𝑑 + 𝐷. For the caps: member 𝑟 neighbors per coordinate, so together with Lemma C.6(c), 𝑑DS an 𝑟-Natarajan shattering of 𝑘 cube coordinates forces (𝑟 + 1) 𝑘 ≤ |Hcube | = (𝑟 + 1) 𝑑 , the anchor cannot appear in any shattered sequence, the band power contributes at most 𝑡 by Lemma C.6(c), 𝑟 (H) ≤ 𝑑 + 𝑡 = 𝑑 + 𝐷 . Likewise an 𝑟-DS shattering of 𝑘 cube coordinates and the sum bound gives 𝑑N 2 forces (𝑟 + 1) 𝑘 ≤ (𝑟 + 1) 𝑑 by the counting bound of Lemma C.6(c), a shattering of side-2 coordinates 𝑟 (H) ≤ 𝑑 + 𝐷, so 𝑑 𝑟 (H) = 𝑑 + 𝐷. is injective on {𝑧1 , . . . , 𝑧𝐷 }, and the sum bound yields 𝑑DS DS 1 The family. Fix 𝑛 ≥ 1 and 𝐿𝑟★ ∈ [0, 8(𝑟+1) ], and set 𝜈 = min

n𝐷 1o , , 𝑛 4

h i h i ★ ¯ = 𝐿𝑟 ∈ 𝐿𝑟★ , 4 𝐿𝑟★ ⊆ 0, 1 . 𝐿 3 6(𝑟+1) 1−𝜈

e𝜎 be as in Lemma C.4 with parameters (𝑑, 𝐿); ¯ this is admissible since 𝐿 ¯ ≥ 𝐿𝑟★ ≥ 𝑑/𝑛. If 𝐿𝑟★ ≥ 𝑑/𝑛, let D ¯ + 1)/𝑑 on each 𝑥𝑖 with the label uniform If 𝐿𝑟★ < 𝑑/𝑛, use the same family with 𝛾 = 0: mass 𝜏0 = 𝐿(𝑟 on the 𝑟 + 1 candidates (independent of 𝜎), and the remaining mass on (𝑥0 , 𝑦0 ); every 𝑟-list then 1 ¯ with equality for the same cube tuples, which calibrates the has side-1 risk at least 𝑑𝜏0 · 𝑟+1 = 𝐿, oracle list risk without any hardness claim, and the case 𝐿𝑟★ = 0 is the degenerate instance 𝜏0 = 0. In all cases define, for (𝜎, 𝑣) ∈ [𝑟 + 1] 𝑑 × W, e𝜎 + 𝜈 U𝑣 , D𝜎,𝑣 = (1 − 𝜈) D

(C.13)

with U𝑣 uniform on {(𝑧𝑖 , 𝑣𝑖 ) : 𝑖 ∈ [𝐷]}. Because the two supports are disjoint and the tuple
(𝑔𝜎+1 , 𝑤𝑣 ), . . . , (𝑔𝜎+𝑟 , 𝑤𝑣 ) , with 𝑤𝑣 ∈ W the member realizing 𝑣, has side-2 list error zero, list ¯ = 𝐿𝑟★ inf 𝐿D (Λℎ® ) = (1 − 𝜈) 𝐿 𝜎,𝑣

® 𝑟 ℎ∈H

(C.14)

exactly, for every (𝜎, 𝑣); by Lemma C.4(i) the infimum in (C.14) extends to all lists of size 𝑟 from any class, which is the Bayes-exactness claim. The excess of any 𝑟-list 𝜆 splits as 𝐷
𝜈 Õ list ★ list ¯ 1{𝑣𝑖 ∉ 𝜆(𝑧𝑖 )}, 𝐿D (𝜆) − 𝐿 = (1 − 𝜈) 𝐿 (𝜆) − 𝐿 + 𝑟 e𝜎 𝜎,𝑣 D 𝐷 𝑖=1

(C.15)

with a nonnegative first term. e𝜎 for each fixed 𝜎, by Lemma C.6(a) for W. Averaging Side-2 term. Lemma C.5 applies with Q = D over 𝜎 as well, and repeating the two-regime computation of (B.10) verbatim, " # 𝐷 n𝐷 1o 𝜈 Õ 𝜈 𝑛 𝜈 1 E𝜎,𝑣 E 1− min , . (C.16) 1{𝑣𝑖 ∉ 𝐴(𝑆)(𝑧𝑖 )} ≥ ≥ 𝐷 𝑖=1 2 𝐷 15 𝑛 4 44

Side-1 term. Suppose 𝐿𝑟★ ≥ 𝑑/𝑛. The argument of Lemma C.4(ii) applies to the padded family with 𝑣 fixed: the two tested laws differ only in the two swapped atom masses, now carrying the factor (1 − 𝜈)𝜏 ≤ 𝜏, so (C.10)–(C.12) are unchanged, and the side-2 part of the sample is shared by the two√laws and enters as ancillary information. The split (C.15) carries the factor (1 − 𝜈), and with p p p ¯ ≥ 3/4 𝐿𝑟★ ≥ 5 𝐿𝑟★ , (1 − 𝜈) 𝐿 6 h

¯ E𝜎,𝑣 E (1 − 𝜈) 𝐿list e𝜎 (𝐴(𝑆)) − 𝐿 D

i

s 1 ≥ (1 − 𝜈) · 40

¯ 𝐿𝑑 1 ≥ 𝑛 48

r

𝐿𝑟★ 𝑑 . 𝑛

(C.17)

For 𝐿𝑟★ < 𝑑/𝑛 no side-1 claim is made and the first term of (5.2) is zero. Conclusion. Summing (C.17) and (C.16) inside (C.15), some (𝜎, 𝑣) attains at least the average, which is (5.2); the family (C.13) depends only on (H, 𝐿𝑟★ , 𝑛), so the same averaging covers randomized learners. □ Proof of Corollary 5.3. Let the domain be {𝑥0 , 𝑧1 , . . . , 𝑧𝐷 }, let 𝑦0 be a label outside [2𝑟], and let H = {𝑤𝑣 : 𝑣 ∈ [2𝑟] 𝐷 } with 𝑤𝑣 (𝑧𝑖 ) = 𝑣𝑖 and 𝑤𝑣 (𝑥0 ) = 𝑦0 . Every 𝑣 has exactly 2𝑟 − 1 neighbors in every 𝑟 (H) ≥ 𝐷; conversely a shattered sequence is injective and coordinate, so 𝑉 = [2𝑟] 𝐷 witnesses 𝑑DS 𝑟 (H) = 𝐷. For 𝑣 ∈ [2𝑟] 𝐷 set 𝜈 = min{𝐷/𝑛, 1 } cannot contain 𝑥0 , on which all members agree, so 𝑑DS 4 Q = 𝛿 and D𝑣 = (1 − 𝜈) 𝛿 (𝑥0 ,𝑦0 ) + 𝜈 U𝑣 ; each D𝑣 is realizable by 𝑤𝑣 . Lemma C.5 applies with (𝑥 ,𝑦 0 0 ) ,  list (𝜆) ≥ 𝜈 Í 1{𝑣 ∉ 𝜆(𝑧 )} pointwise, so for 𝑣 uniform every learner has E E 𝐿list (𝐴(𝑆)) ≥ and 𝐿D 𝑖 𝑖 𝑣 𝑖 𝐷 D𝑣 𝑣 𝜈 𝑛 , which the numeric chain of (B.10) bounds below by 1 min{𝐷/𝑛, 1 }. Some 𝑣 attains (1 − 𝜈/𝐷) 2 15 4 the average, and the family does not depend on the learner, which covers randomized learners. □ Remark C.7 (Interface for the general range). Call 𝑉 ⊆ [𝐾2 ] 𝐷 an (𝑟, 𝐷)-separation family if every element has at least 2𝑟 − 1 neighbors in every coordinate and the induced class has 𝑟-Natarajan dimension at most 1. Replacing W by such a family in the proof above extends Theorem 5.2 to 𝑟 (H) ≤ 𝑑 + 1. Lemma C.6 provides the case 𝐷 = 2 for every 𝑟, and [BCD+ 22] every 𝐷 ≥ 1, with 𝑑 ≤ 𝑑N the case 𝑟 = 1 for every 𝐷; constructing (𝑟, 𝐷)-separation families for all (𝑟, 𝐷), plausibly by the methods of [CP23], is left open.

D

Machine-checked formalization

Both directions of the paper have been formalized in Lean 4 over Mathlib: the relative compression theorem together with the three-block assembly behind Theorem 3.1, and the lower bound Theorem 4.1 in full. The development is about 4,500 lines, contains no sorry, declares no axioms of its own, and every headline statement passes the kernel’s axiom audit depending only on propext, Classical.choice, and Quot.sound. This section records what is checked, in which form, and where the formal statements differ from the prose. The list extension of Section 5 and Section C postdates the formalization and is not covered by it. Upper bound. Theorem 3.3 is checked in full generality and in measure-theoretic form: an arbitrary probability space, product samples via Measure.pi, losses valued in [0, 1] (slightly more general than {0, 1}), and a possibly non-measurable bad event handled by outer measure and a measurable cover, so no stability or measurability of the selection is assumed beyond Assumption 2.1. The constants are thepones displayed in (3.4): the theorem relative_compression concludes 𝐿D (𝐴(𝑆)) ≤ 𝐿D (ℎ) + 12 𝐿D (ℎ)Γ + 20Γ with Γ literally the expression (3.2). The one-sided 45

Bernoulli–Bernstein inequality (Lemma A.7) is proved from first principles rather than imported, and the selective-menu calculus of Lemma 2.4 is checked in integrated form. The assembly of Theorem 3.1 p is checked as two theorems: rmc_master, the fixed-comparator bound 𝐿D (RMC) ≤ ∗ 𝐿D (ℎ ) +12 𝐿D (ℎ∗ )Γ+20Γ+𝑎 1 +𝑎 2 on the explicit three-block product sample space, and rmc_main, which replaces the fixed comparator by inf ℎ∈H 𝐿D (ℎ) through the 𝜖 ↓ 0 argument (an antitone sequence of good events and continuity from above). The imported modules of Section A.1 enter rmc_master as per-block hypotheses in exactly the form stated there: the correct-region guarantee of Lemma A.3 as the block-1 hypothesis, the conditional menu coverage of Lemma A.4 as the block2 hypothesis, and the ordered-compression structure of Lemmas A.5 and A.6 as the structural description of block 3. What is not formalized is the content of the imported modules themselves and the final bookkeeping from (𝑎 1 , 𝑎 2 , Γ) to the displayed rate (3.1), i.e. the instantiation of Remark 3.2. Lower bound. Theorem 4.1 is checked end to end. Probability is formalized by finitely supported distributions (weight functions on finite types, with expectations as finite sums), which is all the construction of Section 4 uses; samples are product laws on the finite atom space, and learners are arbitrary functions from 𝑛-samples to classifiers, with a separate statement for randomized learners averaging over a finite seed space. The formal theorem, lower_bound_main, produces for every 𝑛, 𝑑N , 𝑑DS ≥ 1, every 𝐿★ ∈ [0, 1/8], and every learner a member of the explicit family (B.7) whose excess risk is at least r n𝑑 o 1 1 𝐿★ 𝑑N DS 1 1{𝐿★ ≥ 𝑑N /𝑛} + min , , 12 𝑛 15 𝑛 4 with the same absolute constants as (4.1); calibration is checked in a slightly stronger form than stated, namely 𝐿★ ≤ 𝐿D𝜎,𝑣 (𝑔) for every classifier 𝑔 together with a member of H attaining 𝐿★ exactly. The four dimension claims 𝑑N ≤ Nat(H) ≤ 𝑑N + 1 and DS(H) = 𝑑N + 𝑑DS are checked in both directions (shattered witnesses below, caps above, via the dimension calculus of Lemma 4.4). The only import, Lemma 4.2, is isolated as an interface structure carrying exactly the data used in the proof: a pseudo-cube on 𝐷 points whose class has Natarajan dimension at most 1. The six-cycle of Example 4.3 is verified by the kernel’s decision procedure and discharges the interface at 𝐷 = 2, so at that parameter the formal theorem has no unproved input at all. Four findings. The formal proof routes were chosen for economy inside the proof assistant, and none of the divergences from the prose affects a statement. Four of them, however, carry content of their own. (1) Calibration is Bayes-exact. The formal statement proves 𝐿★ ≤ 𝐿D𝜎,𝑣 (𝑔) for every classifier 𝑔, not only for members of H, with a member of H attaining 𝐿★ . Thus 𝐿★ is the Bayes risk of every member of the family (B.7), and H contains a Bayes-optimal rule for each; the two lower-bound terms are paid even by a learner told that a Bayes rule lies in H, so the bound is in no sense an artifact of comparing to the class. The strengthening is free: the risk identity (B.1) bounds every classifier pointwise (𝑟𝑖 ≥ 12 − 𝛾), and the side-2 error is nonnegative. (2) The posterior in Lemma B.2 can be eliminated. Formally, all members of the family are coupled through a common atom law: an atom sequence is drawn once, and the sample seen by the learner is a deterministic function of the atom sequence and 𝑣, the 𝑥-part being 𝑣-independent by construction. Fixing the atom sequence and grouping 𝑉 by the restriction of 𝑣 to the seen coordinates, the sample is constant on each group, hence so is the learner’s prediction at an 46

unseen 𝑧𝑗 ; by Lemma 4.5 that prediction agrees with 𝑣𝑗 on at most half of each group. Summing over groups gives (B.6) as a deterministic double count: the posterior computation of the prose proof (the conditional law of 𝑣 is uniform on the cloud) disappears, and randomness survives only in E|𝐽 | = 𝐷(1 − 𝜈/𝐷) 𝑛 . (3) The two-point step needs no entropy. The testing step (B.3)–(B.4) is carried out with the Hellinger Í p affinity 𝜌(𝑃, 𝑄) := 𝑧 𝑃(𝑧)𝑄(𝑧) in place of the KL chain rule and Pinsker’s inequality. For the two swapped-pair laws, 1 − 𝜌 ≤ 4(1 − 𝜈)𝜏𝛾 2 by direct computation; affinity tensorizes exactly under products, and Cauchy–Schwarz gives p p p TV ≤ 1 − 𝜌2𝑛 ≤ 2𝑛(1 − 𝜌) ≤ 8𝑛𝜏𝛾 2 , the bound of (B.4) with the same constant. Combined with the finite-support Neyman– Pearson bound (for any test, err𝑃 + err𝑄 ≥ 1 − TV(𝑃, 𝑄), one line), the chain (B.3)–(B.5) uses no logarithms and no imported inequalities, so the probabilistic core of Section B is self-contained in the literal sense. (4) Counting replaces connectivity. The dimension caps for the cube class follow from cardinality alone: shattering 𝑘 points forces 2𝑘 ≤ |Hcube | = 2𝑑N , for DS via the pseudo-cube cardinality bound 2𝑘 ≤ |𝑉 |. Together with the explicit shattered witnesses this recovers Nat(Hcube ) = DS(Hcube ) = 𝑑N and all four dimension claims of Theorem 4.1. The connectivity observation in the prose proof, that the only pseudo-cube inside a sign cube is the full cube, is a stronger structural statement than the argument needs, and it is the one step of the appendix the formalization simply never had to prove. Remaining deviations. The two small-𝐿★ calibration cases of (B.8) are merged into a single choice ¯ uniformly over the 𝑑N pair points with fair labels; the side-1 infimum is that spreads the mass 2𝐿 ¯ and the case 𝐿★ = 0 is the degenerate instance. Randomized learners are modeled again exactly 𝐿, by a finite seed space. The numeric facts of (B.10) and (B.11) (1 − 𝑡 ≥ 𝑒−2𝑡 on [0, 12 ], 𝑒2 ≤ 7.5, and the p 3/4 step, formalized as the rational certificate 25/36 ≤ 1 − 𝜈) are checked as stated. Audit summary. Table 4 lists the correspondence between the prose and the formal development. Everything named there is proved; the imported modules of Section A.1 enter the assembly as hypotheses in their stated forms, and Lemma 4.2 is an interface discharged at 𝐷 = 2 by Example 4.3. Every listed declaration depends on no axioms beyond propext, Classical.choice, and Quot.sound, and the repository builds with zero sorry. Library status. The development sits on Mathlib, but its learning-theoretic layer is built from scratch: at the time of writing, Mathlib contains no Bernstein-type inequality (the one-sided Bernoulli bounds behind Lemma A.7 are self-contained and could be contributed), no totalvariation or Hellinger-affinity toolkit for finitely supported distributions, and no shattering theory in any of its guises (VC, Natarajan, or DS). We are not aware of a prior machine-checked minimax lower bound for a learning problem of this kind, and the atom-space coupling and interface patterns described above are offered as reusable templates for formalizing such arguments.

47

Table 4: Paper-to-Lean correspondence. File names are relative to the repository root; the lower-bound files live under Lower/. Paper

Lean declaration (file)

Theorem 3.3; Γ of (3.2) Lemma A.7 Lemma 2.4

relative_compression, Gamma (Main.lean) bernstein_upper, bernstein_lower (Bernstein.lean) integral_risk_algebra, integral_alpha_transfer, integral_menuLoss_le (Menu.lean) rmc_master; rmc_main (Assembly.lean)

Theorem 3.1, fixed comparator; infimum form Theorem 4.1, deterministic; randomized family-summed form (B.9) Lemma B.1 (B.3)–(B.5) Lemma B.2 Lemma 4.5; Lemma 4.4 dimension claims of Theorem 4.1 Lemma 4.2; Example 4.3 (B.8) parameters and numerics axiom audit

lower_bound_main; lower_bound_randomized (Main.lean) lower_bound_core, lower_bound_avg (Main.lean) assouad_bound; risk_ge, risk_gStar (Engines.lean, Master.lean) tv_flip_le, np_pair; affinity toolkit (Engines.lean, Dist.lean) loo_bound; cloud_bound, unseen_prob (Engines.lean) fiber_lemma; natShatters_sum_le, dsShatters_sum_le (Comb.lean) bigClass_natShatters, bigClass_nat_le, bigClass_dsShatters, bigClass_ds_le (Main.lean) SeparationFamily; sixCycle (Main.lean) regimeA_params, regimeB_params, second_term_bound (Main.lean) Axioms.lean

48

Related documents

• Biomedical informatics training at Stanford in the 21st century#423213
• Online learning of neural computations from sparse temporal feedback#308499
• UniEP: Unified Expert-Parallel MoE MegaKernel for LLM Training#124027
• How convolutional neural network architecture biases learned opponency and colour tuning#389981
• Computable Representation Theory: The Hierarchical Representational Machine#75310