An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order

1 Introduction

• Under the public minimal- or maximal-prefix rule, every deterministic learner satisfies M+Q≥T−ε exactly on some instance, while AHR25’s randomized learner uses O(log T) expected calls and mistakes under the same rule.This yields a deterministic cost of T−ε−O(log T) calls for O(log T) mistakes, versus the randomized O(log T) bound.Source: §1 · pp. 2–3
• The deterministic lower bound holds because each extremal-oracle query can pin at most one still-free point, forcing every prediction on another free point to be wrong despite the oracle returning a full label vector.A fixation step converts the adaptive construction into one fixed order, target, and memoryless oracle.Source: §1 · p. 2
• Every randomized learner has E[M]≥((T+1−ε)128^(-E[Q])−1)/2 under an explicit hard distribution, so O(log T) expected mistakes require Ω(log T) expected calls.The proof uses a logarithmic potential because one call may reveal linearly many labels.Source: §1 · pp. 2–3
• The separation depends on oracle selection: a feasible-median rule permits deterministic ⌈log2 T⌉ calls and mistakes, whereas a global-median rule forces linear total cost.Thus selection behavior is a complexity parameter alongside the interface and concept class.Source: §1 · p. 3
• Further results extend the linear bound to adversarially chosen and frozen memoryless answers, characterize fixed-budget tradeoffs only partially, and show that weak consistency oracles require Θ(T) calls for O(log T) mistakes.The weak-oracle contrast ties the randomized advantage to receiving an evaluable concept rather than only a realizability bit.Source: §1 · p. 3

1.1 Related work

• Prior work bounds mistakes using Littlestone dimension or studies oracle efficiency without charging calls, while AHR25 [1] makes calls a resource and proves O(log T) randomized calls for thresholds on an unknown order.Related models study regret–query tradeoffs, learning unknown orders, or target-query interfaces, but differ in class, protocol, or oracle semantics.Source: §1.1 · p. 4

• Instances are announced in advance, labels follow an unknown threshold c_z on an adversarial total order, and every restricted concept is an order-prefix indicator.The learner predicts before observing each label and knows the domain, horizon, family, and sequence but not the order or threshold.Source: §2 · p. 4
• Convention E adds a sentinel, yielding T+1 concepts and Littlestone dimension floor(log2(T+1)), while convention N has T concepts; both are unified by ε∈{0,1}.The paper writes d = floor(log2(T+1−ε)) and notes that lower bounds hold under both conventions, with the difference confined to bookkeeping constants.Source: §2 · p. 5
• A consistency-type ERM oracle returns a full consistent threshold or ⊥ at unit cost, whereas a weak oracle returns only realizability; legal selection rules include minimal- and maximal-prefix rules.Queries may contain any finite labeled set and may be issued at any time, regardless of its size.Source: §2 · p. 5
• Lower bounds distinguish fixed-rule quantifiers, adversarial-then-frozen legal oracles, and oblivious randomized instances, with the fixed-rule form placing the oracle before the learner.For deterministic learners these forms respectively quantify over an announced rule, a learner-dependent frozen memoryless oracle, and (for randomized learners) worst-instance expectations over private randomness; AHR25's randomized learner works for every legal oracle.Source: §2 · p. 5

Theorem 3.1

• M+Q≥T−ε is tight for every deterministic learner under pre-declared minimal- or maximal-prefix rules, so O(log T) mistakes require T−ε−O(log T) calls.The randomized learner of AHR25 (Thm. 4.5(4)) achieves O(log T) expected calls and O(log T) mistakes on this instance.Source: §3 · pp. 5–6

Theorem 3.2 and Corollary 3.3

• The explicit hard distribution forces E[M]≥max{0,((T+1−ε)128^−q−1)/2} whenever E[Q]≤q under the minimal-prefix oracle.Consequently, logarithmic expected mistakes require Ω(log T) expected calls, matching AHR25’s O(log T) upper bound up to constants.Source: §3 · p. 6

Theorem 3.4

• The feasible-median rule admits a deterministic learner with Q≤⌈log2 T⌉ and M≤⌈log2 T⌉, demonstrating that the separation depends on oracle selection.For T=1, no query is needed; under E one mistake may be necessary because two targets are legal.Source: §3 · p. 6
• The global-median rule instead has M+Q≥T−m for deterministic learners, ruling out simultaneous O(log T) calls and mistakes despite being a legal memoryless ERM oracle.One query and ⌈T/2⌉ mistakes suffice; these are upper and lower bounds rather than exact minimax values.Source: §3 · p. 6

4 The deterministic separation

• The adversary maintains anchored states with committed left and right blocks plus a free block, pinning at most one endpoint so each oracle answer remains valid on all retained orders.The one-pin common-value lemma exhausts contradictory, fixed-prefix, and one-pin cases for the minimal-prefix rule.Source: §4 · p. 7
• M+Q≥T−ε for every deterministic learner under Omin, with the constant exact; Omax and Rη follow by duality and order-independent tie-breaking.The argument also applies to any fixed legal rule satisfying the one-pin common-value property, which is sufficient but not characterized.Source: §4 · pp. 7–8

4.1 Robustness: adversarial then frozen oracles

• The same lower bound holds when answers are chosen adaptively and then frozen into a legal memoryless oracle for the learner’s fixed order and target.The freezing step caches the first answer to each previously queried sample and uses the minimal consistent prefix otherwise; the quantifiers are ∀A ∃(⪯,z,O).Source: §4.1 · p. 8
• The lower-bound constant cannot be improved uniformly over T≥1.This establishes sharpness of the theorem’s constant across all problem sizes and either convention.Source: §4.1 · p. 8
• T−ε−m(T) calls are necessary for any deterministic learner guaranteeing m(T) mistakes; thus O(log T) mistakes require T−ε−O(log T) calls, versus AHR25’s O(log T) expected calls and mistakes.Writing d=⌊log2(T+1−ε)⌋, deterministic worst-case total cost is at least 2^d−1, while randomized expected total cost is O(d+1).Source: §4.1 · p. 8
• The proofs do not invoke AHR25’s general Littlestone-dimension lower bound, whose hypotheses and equivalence-class construction do not match these threshold instances or full-vector answers.Here the charge is to one residual free point per query, rather than an assertion that each full-vector answer contains only one bit of information.Source: §4 · p. 7, §4.1 · p. 8

Hard distribution

• The hard distribution hides a uniformly random center in a balanced interval tree, assigns independent fair labels, and orders points so minimal-prefix answers reveal geometric information.The construction is a genuine total-order threshold class, with a memoryless minimal-prefix oracle and all random choices made before interaction.Source: §5 · p. 9

Proof mechanism

• A stronger revelation oracle simulates each minimal-prefix call, while posterior invariance makes every unrevealed prediction cost 1/2 expected mistakes and bounds each call’s expected potential decrease by O(1).This avoids a one-point charging argument because one call may reveal linearly many labels; conditioning on the learner’s random seed preserves the invariance.Source: §5 · p. 9

Theorem 3.2

• E[M] ≥ ((T+1-ε)128^-E[Q]−1)/2, so polylogarithmic expected mistakes require Ω(log T) expected oracle calls.The proof converts bounded expected potential decrease per call into a lower bound on unrevealed predictions, then uses Jensen’s inequality; the fixed-instance result follows from finite support.Source: §5 · p. 9

Why uniform randomness fails

• A uniformly random order fails as a hard distribution: one call after observing m labels can achieve E[M] ≤ F(m)+2(T−m)/(m+2), preventing a Tρ^Q bound for Q=1.The hidden-center distribution instead ensures that each call decreases the paid potential by only O(1) in expectation, regardless of how many tree levels it descends.Source: §5 · p. 10

Feasible-median rule

• O(log T) calls and mistakes suffice under the feasible-median rule, with each error halving the uncertain interval; at T=8, M+Q≤6<T−ε.The learner makes at most ⌈log2 T⌉ errors and calls, using arbitrary queried samples and a returned concept that splits the uncertain interval nearly evenly.Source: §6 · p. 10

Global-median rule

• The global-median rule has a one-call strategy with M≤⌈T/2⌉, yet some instance forces M+Q≥⌊T/2⌋, ruling out simultaneous logarithmic calls and mistakes.Its lower bound simulates each global-median call with at most one anchored minimal-prefix call on the unknown block.Source: §6 · p. 10

Interpretation

• Across three legal memoryless rules, extremal rules have exact cost T−ε, global-median has linear cost without that constant, and feasible-median has logarithmic calls and mistakes.The randomized learner of AHR25 is oblivious to the rule, so randomization can substitute for a favorable selection rule.Source: §6 · p. 10

Deterministic tradeoffs at a fixed query budget

• N(T,Q) ≤ min{T−1, max{T−Q, ⌈T/2⌉}} gives a deterministic upper bound for Q≥1, while the middle-budget regime remains open.The analysis also provides exact values in small- and large-budget regimes and finite counterexamples to the conjecture that the lower bound is always exact.Source: §7 · p. 11
• The fixed-budget bounds combine Theorem 4.1 with known-order lower bounds, protection-based upper bounds, and sorting using 2(T−1) calls.Finite counterexamples are established analytically through a five-point game and a first-action recurrence reducing the N case to it.Source: §7 · p. 11

Interface contrast

• At the weak consistency interface, Θ(T) calls are necessary and sufficient for O(log T) mistakes for both deterministic and randomized learners.Theorem 7.2 gives deterministic upper bounds of 66T calls under E and 67(T−1) under N, with logarithmic mistake bounds; its lower bounds apply under hard caps and expected budgets.Source: §7 · p. 11
• The randomized weak-interface result restates AHR25 (Thm. 4.5(2) and 4.3), while the deterministic bound improves AHR25’s O(Tlog T) algorithmic guarantee.The improvement concerns this specific algorithm and supplies explicit constants and exact integer mistake bounds, not free derandomization of arbitrary randomized algorithms.Source: §7 · p. 11

• For thresholds on an unknown order, deterministic O(log T)-mistake learning needs Θ(T) queries, whereas randomized learning needs Θ(log T), and the linear bound survives adversarial memoryless oracles.The gap is governed by the oracle’s selection rule; the general question for arbitrary classes and non-transductive learning remains open.Source: §8 · p. 12

Favourable selection rules

• Which pre-declared ERM selection rules permit deterministic O(log T)-query and O(log T)-mistake learning remains open.The feasible-median rule permits this behavior, whereas extremal and global-median rules force linear total cost; endpoint selection alone does not characterize complexity.Source: §8 · p. 12

The middle regime

• The middle regime ⌊T/2⌋ < Q < 2(T−1) remains unresolved, and M*_E(T,Q) is not max(T−Q, ⌊log2(T+1)⌋).Source: §8 · p. 12

Constants

• Improving the constant 128 in Theorem 3.2 remains an open problem.Source: §8 · p. 12

Beyond thresholds

• Extending the separation to arbitrary Littlestone classes and non-transductive learning remains open, although the charging, fixation, and paid-potential techniques are not threshold-specific.The one-pin lemma and interval-tree distribution are threshold-specific.Source: §8 · p. 12

1. Statement and conventions

• The proof assumes full-vector consistency-ERM returns and unrestricted finite query samples, rather than the weak-consistency interface.Source: §1 · p. 13
• Omin returns the smallest consistent prefix, or ⊥ when no consistent prefix exists.Source: §1 · p. 13
• Omax returns the largest consistent prefix, or ⊥ when no consistent prefix exists.Source: §1 · p. 13
• Under convention E, X = {s, x1, . . . , xT} with s ≺ x for every x ≠ s.Source: §1 · p. 13
• Because every concept labels s by 1, the smallest prefix is {s}, fixing the rule used in Theorem 3.1.Source: §1 · p. 13
• Under convention N, prefixes are nonempty, so Omin returns the order-minimum singleton when consistent after a query with no positive labels, and otherwise returns ⊥.Source: §1 · p. 13

2. Anchored states

• The anchored state retains orders of the form σ·L·π(F)·R, with free points permutable and the target cut allowed anywhere through F.The anchor is the order-minimum and always has target label 1; endpoint pins move one free point into L or R without ordering the remainder.Source: §2 · p. 14, Endpoint refinements · p. 14

3. Prefix realizability and the common-value query lemma

• For anchored samples, realizability is characterized by the absence of a negative b preceding a positive a; the smallest consistent prefix then supplies the minimum-rule answer.Contradictory samples and samples containing (σ, 0) are rejected immediately.Source: Lemma A.1 — Prefix criterion · p. 15

Lemma A.2 — One-pin common-value query lemma

• Every query can be answered with a full vector constant over retained orders after zero or one endpoint pin, including the exhaustive remaining cases.The construction pins at most one free point, and the resulting retained family remains nonempty.Source: Lemma A.2 — One-pin common-value query… · pp. 15–16

4. Labels, invariants, and charging

• The strong invariant preserves committed labels, prior predeclared oracle answers, and unpredicted free points while each prediction can force an error through an endpoint refinement.The refinement leaves a nonempty subset of retained order–target pairs consistent with the newly committed label.Source: Lemma A.3 — Strong transcript invariant · p. 17

Lemma A.4 — Additive charging

• Queries remove at most one free point, while every other free point is removed at prediction and causes an error, yielding the additive charging relation.Equivalently, the initial potential is |F| = n, queries decrease it by at most one, and predictions decrease it only on errors.Source: Lemma A.4 — Additive charging · p. 17

5. Oblivious fixation and memorylessness

• A fixed, originally declared memoryless oracle suffices: the construction produces one fixed order and target rather than choosing return values after the instance.Finite fixation and replay make the adversary oblivious, while the oracle remains legal on every sample.Source: Lemma A.5 — Finite fixation and replay · p. 18

Lemma A.5 — Finite fixation and replay

• Replay of the finite simulated transcript on the selected fixed order, target, and oracle reproduces every query, prediction, label, and returned vector through the stopping event.Stopping occurs after completion of all predictions or after n query events, covering learners that would query indefinitely.Source: Lemma A.5 — Finite fixation and replay · p. 18

Lemma A.6 — Anchored reversal-complement duality

• Anchored reversal-complement maps largest consistent prefixes to smallest consistent prefixes, preserving queries and errors and proving the maximum-rule case from the minimum-rule theorem.The same one-pin property applies to the maximum rule and to fixed legal selectors satisfying the stated sufficient condition, which is not a characterization.Source: Lemma A.6 — Anchored… · p. 19

7. Sharpness and relation to AHR25

• The total-cost lower bound is exact for either extremal rule, with matching upper bounds achieved without oracle calls.Under the minimal-prefix convention, always predicting 1 makes at most T−1 errors.Source: §7 · pp. 19–20
• Theorem 3.1 forces deterministic learners with O(log T) errors under Omin to make linear-scale queries, while AHR25 (Thm. 4.5(4)) gives randomized O(log T) errors and O(log T) expected queries under the same rule.The randomized guarantee applies to arbitrary legal ERM returns, so the separation does not require adversarial tie-breaking.Source: §7 · p. 20

8.1 Median of the feasible prefixes

• The feasible-prefix median rule is predeclared from the sample and order alone, without access to the learner’s state or free block.Feasible cutoff indices form an integer interval whenever the sample is realizable.Source: §8.1 · p. 20

Proposition A.7 — Deterministic logarithmic learning under (A.18)

• Under either convention, a deterministic learner achieves at most ⌈log2 T⌉ errors and queries for every order and target.Each error halves the active uncertainty interval, rounded up; for T=1, no queries suffice.Source: Proposition A.7 — Deterministic… · p. 21
• The logarithmic guarantee is rule-specific: arbitrary consistency-ERM returns need not be balanced, so the all-rules extension is refuted.The proof maintains known positive and negative blocks around an active interval and queries only after an error unless the interval is resolved.Source: Proposition A.7 — Deterministic… · p. 21

8.2 The different “closest to the global median” rule

• The fixed global-median rule differs from feasible-prefix median selection and does not admit simultaneous O(log T) mistakes and queries.For T=8, its empty-sample behavior gives M+Q≤5, refuting the full Theorem 3.1(a) bound.Source: §8.2 · p. 22
• Every deterministic learner under the global-median rule faces a linear total-cost lower bound, since T−m≥⌊T/2⌋ prevents O(log T) mistakes and queries simultaneously.The lower bound is obtained by simulating global-median interactions with an anchored minimum-prefix oracle on an unknown block.Source: §8.2 · pp. 22–23
• Thus oracle selection is decisive: extremal selectors have linear deterministic cost, feasible-prefix medians permit deterministic O(log T) learning, and global-median selection restores the linear lower bound.These counterexamples change the publicly declared oracle rule rather than refuting Theorem 4.1 or Theorem 3.1.Source: §8.2 · p. 23

Theorem 4.1: an additive deterministic lower bound with a fixed memoryless ERM oracle

• For every deterministic learner, a fixed order, target, and memoryless ERM oracle force the additive lower bound M+Q≥T−ε, with ε determined by the prefix convention.The construction fixes the order, target, instance sequence, and oracle before interaction; the additive constant is 0 for the empty-prefix convention and 1 for the nonempty-prefix convention.Source: Theorem 4.1: an additive deterministic… · pp. 23–24

Lemma B.1 — Prefix consistency criterion

• The prefix-consistency criterion characterizes realizability through anchor feasibility and positive–negative inversions in the ordered sample.A negative anchor label or contradictory labels are impossible, while absent inversions permit a consistent prefix.Source: Lemma B.1 — Prefix consistency criterion · pp. 24–25

Lemma B.2 — Exhaustive query handling with at most one pin

• The query rule exhaustively handles fresh and cached samples, returning legal answers while removing at most one point from the free block.Contradictions and forced inversions return ⊥; mixed labels in the free block pin one negative point, while otherwise the rule returns a compatible prefix and caches it.Source: Lemma B.2 — Exhaustive query handling… · p. 25, (ii) Both labels occur in the free block · p. 26, (iii) No forced inversion and no… · p. 26

Lemma B.3 — Strong invariant, including all recorded answers

• The invariant preserves legal recorded answers, a nonempty compatible-order set, and feasibility of every binary labeling of the current free points.State changes refine compatible orders, while the invariant maintains jointly feasible orders and target cuts; thus a consistent order and target always exist.Source: Lemma B.3 — Strong invariant,… · pp. 27–28

Lemma B.4 — Query pins pay for every possibly avoided free-point mistake

• Each query pin pays for at most one avoided free-point mistake, while every prediction on a still-free instance is wrong, yielding the additive accounting.If p points are removed by queries and f by predictions, then p≤Q and f≤M; the anchor can add one uncharged mistake under the nonempty-prefix convention.Source: Lemma B.4 — Query pins pay for every… · p. 28

Lemma B.5 — Memoryless freezing and exact deterministic replay

• The completed adaptive transcript can be frozen into an immutable memoryless oracle that reproduces every recorded answer and is legal on every sample.The frozen function searches the final order’s prefix concepts for a consistent answer, returning one exactly when realizable; its value depends only on the sample.Source: Lemma B.5 — Memoryless freezing and… · p. 29, Legality on every sample · p. 29

Target legality

• The frozen target is a genuine concept agreeing with all revealed labels, including the case where no committed left points remain.When L=∅, the target’s positive set is the anchor alone.Source: Target legality · p. 29

Replay

• Running the same deterministic learner on the frozen instance replays the constructed interaction by induction over queries and label revelations.Determinism preserves the next operation, the frozen oracle returns each recorded query answer including repetitions, and the target returns each constructed label.Source: Replay · p. 30
• Replay constructs one fixed triple whose returned vectors and histories remain identical, with labels fixed before each transductive prediction.The construction also handles finite transcript prefixes and freezes them into a finite replay when needed.Source: Replay · p. 30

Completion of Theorem 4.1 and sharpness of the constants

• Theorem 4.1’s additive constants are sharp: no smaller universal constant works under either the empty-prefix or nonempty-prefix convention.At T=1, the respective witnesses rule out constants smaller than 0 and 1; these witnesses do not establish a general error–query tradeoff.Source: Completion of Theorem 4.1 and… · p. 30

6. Separation and relation to AHR25

• Deterministic learners guaranteeing m(T) mistakes require at least T−ε−m(T) oracle calls, whereas AHR25’s randomized theorem achieves O(log T) expected mistakes and calls.With d = Θ(log T), this is an exponential gap: O(d + 1) versus 2^Ω(d), establishing AHR25’s open randomization question in this setting.Source: §6 · p. 31

Why Theorem 4.4 of AHR25 is not the proof of this result

• AHR25’s Theorem 4.4 is not invoked because it concerns threshold classes on equivalence classes, while this proof uses distinct totally ordered points and fails its T≥2^d+1 condition.The present construction instead uses a related one-point charging principle, answers forced-realizable queries with proper full concepts, and freezes replies into one memoryless oracle.Source: Why Theorem 4.4 of AHR25 is not the… · p. 31

Why the construction does not contradict Theorem 4.5(4) of AHR25

• The deterministic replay cannot be extended to refute AHR25’s randomized theorem because constructing separately for each random tape yields an instance depending on that tape.That would incorrectly exchange ∀ω∃I_ω for ∃I with the same expected lower bound over ω; determinism supports only one learner execution.Source: Why the construction does not… · p. 31

Theorem 3.2 — expected-query and worst-case-query lower bounds

• For every T≥1, an explicit deterministic, memoryless consistency-type ERM oracle and hard distribution yield the stated lower bounds for every randomized learner.The oracle depends only on the sample and total order, and the expected-query condition may be required only on average over the hard distribution.Source: Theorem 3.2 — expected-query and… · p. 32

2.1 A balanced interval tree

• A balanced interval tree orders sibling blocks outside the target-containing interval before the interval itself, producing a genuine total-order threshold instance with distinct point positions.The target threshold ends at the last positive point in the first priority list, or at the sentinel a when that list is empty.Source: §2.1 · p. 33, §2.2 · p. 33

2.3 The actual, memoryless oracle

• The actual oracle is the minimum consistent prefix rule: it depends only on the sample and total order, is legal for every finite ordered domain, and correctly rejects inconsistent samples.Its behavior is independent of the target, history, and learner randomness.Source: §2.3 · pp. 33–34

Lemma C.1 — prefix-max domination

• One stronger prefix-max call reconstructs every original oracle response, including ⊥, regardless of sample size or point-arrival status.The auxiliary revelation oracle additionally exposes the active interval and outside priorities or labels, but this extra information is used only for analysis and costs one query.Source: Lemma C.1 — prefix-max domination · p. 34, The auxiliary revelation oracle · p. 35, Lemma C.2 — the auxiliary oracle… · p. 35

Lemma C.3 — conditional independence inside the active interval

• Conditioned on the complete auxiliary history, labels of unarrived points in the active interval remain independent fair bits and independent of the target location, even for randomized learners.This invariant explicitly replaces any exchangeability assumption after failure answers.Source: Lemma C.3 — conditional independence… · p. 36

Early states

• After each early-state refinement, the conditional probability of continuing to another early-state refinement is at most 5/6.Unrevealed predictions therefore face fair target bits, while the potential decreases by at most ln 2 per binary refinement, supporting the query-versus-mistake charging argument.Source: Lemma C.4 — mistake charge and the… · p. 37, Late states · p. 38, Early states · p. 38

7. Proof of Theorem 3.2

• Theorem 3.2’s lower bound applies to every learner using the actual memoryless oracle, including adaptive learners with random query counts.The argument does not condition the hard distribution on a low-query event and therefore also supports the fixed-instance consequence.Source: §7 · p. 39

Corollary C.9

• Together with AHR25, Thm. 4.5(4), the result makes O(log T) expected oracle calls optimal in order for polylogarithmic expected mistakes.Source: Corollary C.9 · p. 40
• At O(log T) mistakes, deterministic query complexity is Θ(T) against worst-case legal oracles and under Theorem 3.1’s extremal rules, but not every legal pre-declared rule.Source: Corollary C.9 · p. 40

Relation to the one-point property

• The proof replaces AHR25’s one-point property, which can fail for full-vector ERM, with a lemma bounding each query’s expected decrease of a paid logarithmic potential by a constant.A query may reveal a whole sibling interval containing linearly many labels.Source: Relation to the one-point property · p. 40

Proposition C.6 — exact zero-query optimum

• With zero queries under the uniform distribution, posterior-majority prediction is exactly optimal for both deterministic and randomized learners, and under convention (N) the optimum satisfies F_N(T) ≥ T/4 − 1.Randomization cannot improve the posterior-majority decision because conditional loss is affine in the prediction probability.Source: Proposition C.6 — exact zero-query… · pp. 41–42

Proposition C.7 — a one-query learner for the uniform distribution

• A one-query learner under the minimum-prefix rule achieves the stated exact uniform-distribution bound after predicting m labels by posterior majority and querying those labels.The bound also holds for every consistent returned threshold, but it is distribution-specific rather than worst-case over orders.Source: Proposition C.7 — a one-query learner… · p. 42

Proposition C.8 — no history-uniform constant contraction bound for the uniform distribution

• No universal constant bounds one-query logarithmic contraction uniformly over all positive-probability histories, even with +1 regularization.The failure persists because the posterior within the remaining undetermined set is not the fresh uniform posterior assumed by a naive potential argument.Source: Proposition C.8 — no history-uniform… · p. 43

Theorem D.1 — The conjectured formula is false (conventions E and N)

• Theorem D.1 shows that the proposed E formula is false, so no formula assigning M*=2 can be valid in the stated model.The analysis applies to conventions E and N with complete label-vector oracle answers and no endpoint-name information.Source: Theorem D.1 — The conjectured formula… · p. 44, §1 · p. 44

Lemma D.2 — Computable knowledge and sound protection

• The protection algorithm computes retained-order knowledge through a partial order and feasible ideals, with realizability ensuring a nonempty retained version space.Under E, the version space has reachability descriptions; under N, enumerating nonempty ideals also captures nonemptiness information.Source: Lemma D.2 — Computable knowledge and… · pp. 44–45

Lemma D.3 — Correct accounting, including early termination

• The accounting lemma gives a valid general upper bound for a protection algorithm with query cap k, including early termination when fewer than k calls are made.Mistaken query rounds protect distinct future points, while an unqueried undetermined arrival can remain only as the sole unresolved point.Source: Lemma D.3 — Correct accounting,… · pp. 45–46

Lemma D.4 — Antichain cube

• With no queries remaining, an antichain of size r lets the adversary independently choose labels to force r mistakes while preserving realizability.Every subset of the antichain extends the positive ideal in some linear extension.Source: Lemma D.4 — Antichain cube · p. 46

Lemma D.5 — Extreme-point padding

• Under E, fixing one extreme point leaves an embedded four-point problem in which at most one further query still permits at least three forced mistakes.The construction uses legal deterministic memoryless simulations, including direct handling of padding-point queries.Source: Lemma D.5 — Extreme-point padding · p. 47

Lemma D.6 — Predicting before resolving a matching costs three mistakes

• Predicting before resolving a matching can cost three mistakes, even if the full order is subsequently disclosed, because the ERM answer reveals the class rather than the target.The conclusion remains valid with zero or one retained comparison.Source: Lemma D.6 — Predicting before… · pp. 47–48

Lemma D.7 — The second-query alternatives

• After one retained comparison, every second query can be answered to leave either an extreme-point/fork configuration or two disjoint comparisons, supporting the lower-bound case analysis.In the nontrivial mixed-query case, the requested positive or negative set must collapse to a singleton endpoint.Source: Lemma D.7 — The second-query… · pp. 48–49

Lemma D.8 — One query cannot eliminate a three-point antichain from the matching

• For deterministic learners using at most three calls, the adversary preserves a three-point antichain, forces three mistakes, and solidifies all answers into a legal oblivious memoryless oracle.Together with Lemma D.3, this yields the matching lower and upper bounds; the proof also covers fewer than three calls.Source: Lemma D.8 — One query cannot eliminate… · pp. 49–50

Lemma D.10 — Known-order lower bounds

• With the full order disclosed, least-consistent-threshold oracle answers are simulatable and reveal no information about the target cut, enabling a worst-sequence known-order lower bound.The construction adaptively selects the final surviving target and replays the deterministic interaction; it does not claim every known-order permutation is hard.Source: Lemma D.10 — Known-order lower bounds · pp. 50–51

Lemma D.11 — First-action lower recurrence under N

• For n≥2 and q≥1, the first-action recurrence (D.3) reduces the N problem after a query or prediction to an E or N problem on n−1 points.Queries can preserve a globally least point, while prediction 0 makes the point least and prediction 1 makes it greatest.Source: Lemma D.11 — First-action lower… · p. 51
• N(6, 4) = 3, so any proposed formula assigning value 2 at (T, Q) = (6, 4) is false.The lower bound N(6, 4) ≥ 3 and the matching reverse inequality are supplied explicitly.Source: Lemma D.11 — First-action lower… · p. 51

Further N conclusions

• For Q≥1, induction from (D.3) and Theorem 4.1 under E yields the strengthened budget lower bound M*_N(T, Q) ≥ T−Q.This is a budget statement, not a pathwise assertion when the actual query count may be zero.Source: Further N conclusions · p. 52

6. Valid bounds after rejecting the claimed exact curve

• After sorting with at most 2(T−1) calls, majority prediction over consistent prefixes makes at most floor(log2 |V_0|) mistakes, with |V_0| = T+1 under E and |V_0| = T under N.Each successful pair query creates an internal split, and every mistake halves the surviving consistent-concept set.Source: §6 · p. 52
• The finite counterexamples show that (D.6)–(D.7) are valid bounds rather than an exact characterization assembled from Theorem 4.1 and known-class Halving.Theorem 4.4 of AHR25 is not used here because its hypothesis fails for the threshold family; the deterministic/randomized separation is unaffected.Source: §6 · p. 52

Theorem 7.2 — explicit bounds

• Deterministic weak-consistency learners use at most 66T queries and floor(log2(T + 1)) mistakes under E, or 67(T−1) queries and floor(log2 T) mistakes under N.The bounds hold for every admissible domain, unknown total order, target, and transductive sequence, pathwise without randomization or averaging.Source: Theorem 7.2 — explicit bounds · p. 53

Lemma E.1 — comparison interface and adaptive consistency

• The weak oracle implements order comparisons because the query {(u,1),(v,0)} is realizable exactly when u≺v, enabling exact median selection with at most 32n queries plus n−1 partition queries.The comparison procedure remains valid for adaptively supplied answers consistent with a total order, by extending each finite partial order to a total order.Source: Lemma E.1 — comparison interface and… · pp. 53–54

Lemma E.3 — a phase contains at most one mistake

• Each phase certifies every inferred label correctly and contains at most one mistake, using a median pivot to certify one side after the first error.Certified points cannot cause mistakes, and the threshold implications preserve consistency with earlier certifications.Source: Lemma E.3 — a phase contains at most… · p. 56

Convention E

• Under E, repeatedly applying the phase procedure from an initially empty certification map yields the stated logarithmic mistake bound over phase-start sizes.Under N, a minimum scan certifies the first actual instance as positive using T−1 comparisons, after which the phase algorithm runs on T−1 points.Source: Convention E · p. 57, Convention N · p. 57

Convention N

• The N correction replaces T + 1 by T in the mistake bound, changing it by at most one while preserving the E algorithm’s 66T-query guarantee.For T=1, N requires zero queries and mistakes, whereas E permits at most one mistake with zero queries.Source: Convention N · pp. 57–58

The quoted lower bound

• AHR25’s Theorem 4.3 states that for T≥100, any learner capped at T/20 weak-consistency queries incurs at least T/20 expected mistakes when all binary labelings are realizable.The result applies to deterministic learners as a special case and includes thresholds among the covered classes.Source: The quoted lower bound · p. 58, Applicability under E · p. 58

Applicability under N: the necessary one-point correction

• Under E, every labeling is realizable, while under N the theorem requires a one-point correction and yields, for T≥101, at least (T−1)/20 expected mistakes under a (T−1)/20-query cap.The designated minimum is an actual instance, and the simulation supplies its known positive label without changing the learner’s queries.Source: Applicability under E · p. 58, Applicability under N: the necessary… · pp. 58–59

The oracle is fixed and memoryless

• The lower bound uses a fixed deterministic memoryless Boolean oracle, and if worst-instance expected mistakes and queries are m and q, then q≥h/400−m/20.Thus logarithmic expected mistakes require linear expected queries, even when query usage is bounded only in expectation.Source: The oracle is fixed and memoryless · p. 59, Lemma E.4 — expected-query budgets… · pp. 59–60

Lemma E.4 — expected-query budgets also require linear queries

• Ω(T) expected queries remain necessary under the hard-cap reading, and therefore under an expected-query interpretation, for logarithmic mistakes.This establishes the linear lower bound without relying on how AHR25’s unqualified query budget is interpreted.Source: Lemma E.4 — expected-query budgets… · p. 60

Corollary E.5 — tight weak-consistency query order

• Θ(T) queries are necessary for both deterministic and randomized learners under weak consistency, even when randomized budgets are worst-instance expectations.The matching upper bound follows from AHR25, Theorem 4.5(2), or more strongly from the deterministic algorithm of Theorem 7.2.Source: Corollary E.5 — tight weak-consistency… · p. 60

Interface comparison and the precise separation statement

• Deterministic complexity is Θ(T) for worst-case legal oracles and Theorem 3.1’s extremal rules, while randomized complexity is Θ(log T), with AHR25 providing the O(log T) upper bound.The deterministic lower bound is Q≥T−ε−O(log T), and AHR25’s sorting algorithm gives an O(T) upper bound.Source: Interface comparison and the precise… · p. 61

Interpretive proposition — scope of the interface separation

• The separation is interface- and rule-dependent: feasible-median ERM permits deterministic O(log T) queries and mistakes, but weak consistency still requires Ω(T) expected queries.The conclusion applies to this threshold family and logarithmic-mistake regime; it does not rule out improvements in constants or other weak-oracle tradeoffs, and the exponential form uses d=Θ(log T).Source: Interpretive proposition — scope of… · p. 61