REVIEW 2 major objections 5 minor 36 references
Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Online learners restricted to an ERM oracle pay an exponential price in the Littlestone dimension—at least 2^d mistakes—but transductive online learning, where the instance sequence is known ahead of time, can be solved optimally with a…
desk verdict A serious paper with a real hole in the headline agnostic lower bound; the transductive and special-class results are worth engaging, but Theorem 3.2 needs a fix or a rewrite. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The lower bounds rest on a construction of threshold classes over nested hyperrectangles in $[0,1]^{T-1}$: random thresholds $z_1,\dots,z_{T-1}$ partition the space into cells $C_1,\dots,C_T$, and the concept class labels each cell by a threshold pattern. Because the $z_i$ are drawn uniformly, any finite set of ERM queries hits cells beyond the current one with probability zero, so the oracle returns no information about future labels and the learner errs with probability $1/2$ at each step. The transductive upper bound is carried by a labeling-enumeration procedure that uses $O(T^{d_{\mathrm{VC}}+1})$ weak-consistency queries to recover all realizable labelings on the known instance set (via Sauer's lemma), after which standard algorithms such as SOA or the halving algorithm achieve optimal mistakes. Randomized improvements for thresholds use a balanced-partition trick: two randomly sampled points, queried with opposite labels, split the uncertainty region so that a mistake shrinks it by a constant factor.
What would settle it
Take the class $\mathcal{C}_{z,b}$ from Appendix D.1 with $T' = 2^{d_{\mathrm{LD}}}$ phases of $S$ copies each, sample labels i.i.d. uniformly, and compute the true infimum error $\inf_{c\in\mathcal{C}_{z,b}} \sum_t \mathbf{1}[c(x_t)\neq y_t]$ directly by enumerating all concepts. If that infimum exceeds $T/2 - c\sqrt{T\,2^{d_{\mathrm{LD}}}}$ for the relevant constant $c$, then the benchmark used in the proof of Theorem 3.2 is not the class's best error, and the regret lower bound as stated does not follow from the construction.
Extended reading notes
Core claim
The paper establishes that in standard online learning, access to a general (even agnostic) ERM oracle does not circumvent the exponential cost of the Littlestone dimension: Theorem 3.1 gives $\Omega(2^{d_{\mathrm{LD}}})$ expected mistakes for any randomized algorithm that makes finitely many oracle queries, and Theorem 3.2 gives $\Omega(\sqrt{T\,2^{d_{\mathrm{LD}}}})$ expected regret. In the transductive online model, where the full instance sequence is revealed in advance, the paper shows that $O(T^{d_{\mathrm{VC}}+1})$ weak-consistency queries suffice to recover all realizable labelings and thereby match the optimal mistake and regret bounds of the full-information setting; two lower bounds show that $\Omega(T)$ weak-consistency queries, or $\Omega(T)$ ERM queries, are generally necessary. For special classes, randomized algorithms achieve much better oracle complexity: thresholds on an unknown ordering are learnable with $O(\log T)$ ERM queries in expectation, and $k$-intervals with $O(T^3 2^{2k})$ weak-consistency queries.
Load-bearing premise
The agnostic lower bound depends on the premise that the best concept in the constructed class can label each block of identical instances with that block's majority label independently; if the class's threshold structure prevents such a labeling, the regret benchmark used in the proof is not the true best-in-class error.
Editorial extensions
If this is right
- In the realizable online setting, no finite-query ERM algorithm can beat $\Omega(2^{d_{\mathrm{LD}}})$ expected mistakes, so the exponential upper bounds of prior work are tight for the general ERM oracle.
- The $\Omega(\sqrt{T\,2^{d_{\mathrm{LD}}}})$ agnostic regret lower bound shows that regret also inherits the exponential dependence, closing the gap with the $T\,2^{O(d_{\mathrm{LD}})}$-query upper bound up to logarithmic factors.
- Any deterministic restricted-ERM algorithm can be simulated with a weak-consistency oracle at only $O(T)$ extra queries, so the realizability decision problem carries essentially the same online learning power as the optimization oracle.
- In the transductive setting, $O(T^{d_{\mathrm{VC}}+1})$ weak-consistency queries recover all realizable labelings, making the exponential-in-$d_{\mathrm{LD}}$ lower bound disappear even though $\Omega(T)$ queries are still needed for general classes.
- For thresholds on an unknown ordering, a randomized algorithm achieves the optimal $O(\log T)$ mistake bound with only $O(\log T)$ expected ERM queries, an exponential improvement over deterministic algorithms.
Reading between the lines
- If the nested-hyperrectangle mechanism is the true source of hardness, then any oracle that returns meaningful information only on queried points—and cannot be forced to reveal labels of points the learner has not identified—will face the same exponential barrier in online learning; an oracle that lets the learner propose arbitrary points to label might behave differently, though the paper's lower
- The transductive enumeration strategy suggests a general recipe: oracle complexity can be charged to the number of distinct labelings the class induces on the known instance set, which for classes with finite VC dimension is polynomial; extending this recipe to multiclass or real-valued settings would require a dimension notion that bounds the number of labelings.
- The balanced-partition proof for thresholds hints that the relevant quantity for randomized oracle efficiency may be the ability to find a 'balanced' split of the version space with few queries; testing whether other Littlestone classes admit such splits with $O(\mathrm{poly}(d_{\mathrm{LD}})\log T)$ queries would directly address the open problem the paper poses.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies online and transductive online learning when the learner does not know the concept class directly but can access it through ERM or weak-consistency oracles. The main claims are: (i) in the realizable online setting, any algorithm making finitely many ERM queries incurs Ω(2^{d_LD}) mistakes; (ii) in the agnostic online setting, such algorithms incur Ω(√(T 2^{d_LD})) regret; (iii) restricted-ERM algorithms can be simulated by weak-consistency oracles with an O(T) blow-up in calls; (iv) in the transductive online setting, general Littlestone classes can be learned optimally with O(T^{d_VC+1}) weak-consistency calls, while Ω(T) weak-consistency or ERM queries are necessary in certain regimes; and (v) specialized randomized algorithms for thresholds, k-intervals, and d-Hamming balls reduce oracle complexity. The paper also contains a lower bound for partial concepts and a claimed Pareto frontier. The realizable lower-bound construction and several transductive results appear plausible, but the central agnostic lower bound is not established by the proof given.
Significance. If the results were correct, the paper would make a strong contribution: it would show that general ERM access does not remove the exponential dependence on the Littlestone dimension in online mistake bounds and regret, and it would give the first oracle-complexity lower bounds in transductive online learning. The transductive algorithms, especially the threshold and k-interval results, are concrete and interesting. However, Theorem 3.2 is one of the two headline results, and its proof in Appendix D.2 contains a load-bearing error: the benchmark regret is computed for a class that is not the one constructed. Because the advertised agnostic lower bound is unsupported, the paper's main message is not currently defensible.
major comments (2)
- [Appendix D.2, Theorem 3.2] The proof of the agnostic lower bound relies on a false premise about the constructed concept class. It refers to 'the concept class C_z as defined earlier', but Section D.1 defines C_{z,b} as a threshold class over T'=2^{d_LD} cells: every concept labels the cells monotonically with respect to an ordering determined by b. The proof then asserts that 'This hypothesis can assign an optimal label to each cell C_i based on the majority of labels seen in phase i.' This is impossible for a threshold class: the optimal hypothesis is a single threshold, so it cannot choose the per-cell majority labels independently. For i.i.d. uniform labels in each of T' phases of length S=T/T', the expected error of the best threshold is T/2 - Θ(√T), not T/2 - c√(T 2^{d_LD}); the saving is the maximum of a random walk over T' thresholds and is O(T^{1/2}) up to constants depending only on d. Consequently, a learner that predicts uniformly at random has expected regret O(√T) on this instance, which is incompatible with the claimed Ω(√(T 2^{d_LD})) lower bound. The construction in D.2 therefore cannot support Theorem 3.2.
- [Theorems 3.1 and 3.2, Section 3] The quantification 'makes a finite number of queries' is not precise, and under the literal reading it makes the lower-bound claims false. For the threshold classes used in D.1, a learner can wait for the T'=2^{d_LD} distinct representatives, determine their total order with O(T'^2) ERM queries (a pair query with labels (0,1) is realizable in exactly one of the two orientations), and then run the standard full-information agnostic online algorithm for the now-known threshold class, obtaining regret O(√(T log T')) rather than Ω(√(T 2^{d_LD})). In the realizable case the same strategy gives O(2^{d_LD}) mistakes, which is consistent with Theorem 3.1, but the agnostic claim is not: the exponential dependence in d is contradicted for all sufficiently large d. The authors need to state explicitly what query budget is allowed; as written, the lower bounds are not well-defined claims.
minor comments (5)
- [Table 1, Section 1] The row labeled 'Randomized Agnostic ERM Finite Ω(2^{d_LD}) Theorem 3.1' appears to misattribute Theorem 3.1, which is the realizable mistake lower bound; the agnostic regret lower bound is Theorem 3.2.
- [Lemma 4.1, Section 4] The lemma states a query bound of O(|X|^{d_VC+1}) for recovering all concepts, but this is only meaningful when X is finite. In Theorem 4.2 it is applied to the T-point set {x_1,...,x_T}; the statement should explicitly say O(T^{d_VC+1}) for that finite set.
- [Appendix C] Appendix C appears as headings only ('Mistakes-Oracle Calls Pareto Frontier' with subsections C.1 and C.2) and contains no statements, proofs, or references; if this material is intended to be part of the contribution, it is missing.
- [Appendix D.2] The notation 'C_z' is used without a definition; Section D.1 defines C_{z,b}, and it is unclear whether C_z is a threshold class over the index order, a union over b, or something else.
- [Theorem 4.5, proof of Part 2] The proof accounts for points sampled outside the uncertainty region by saying they are discarded and contribute at most O(T) queries, but the accounting is informal; a formal bound on the number of times a point can be sampled and discarded should be supplied.
Circularity Check
No significant circularity: the new lower bounds and algorithms are self-contained; prior-work citations are comparative, not load-bearing.
full rationale
The paper's central lower bounds (Theorems 3.1 and 3.2) are proved by explicit adversary constructions against the ERM oracle, and the oracle lower bounds do not assume the theorems' conclusions. The weak-consistency simulation (Theorem 3.3) and the transductive upper/lower bounds (Theorems 4.2-4.6, H.4, H.6) are self-contained reductions or direct constructions, using only standard facts such as Sauer's lemma, SOA, and entropy arguments. Citations to AAD+23 and KS24 are used to state matching upper bounds and for comparison, not as premises for the new lower bounds; the fact that one prior upper-bound paper shares an author is therefore not circular. Appendix D.2 contains an apparent technical gap: the regret benchmark is computed as if the best hypothesis could choose each cell's majority label independently, whereas the constructed class is a threshold class over the cells, so the threshold is monotone. That is a correctness concern, not a circularity: the claimed lower bound is not reduced to its own inputs by definition or by self-citation. Hence no circular step is identified and the score is minimal.
Assumptions & free parameters
assumptions (6)
- domain assumption The ERM oracle may be implemented adversarially among all minimizers; Definition 2.1 says it returns 'some' hypothesis, and the lower bounds rely on the adversary choosing an uninformative minimizer.
- domain assumption Finite queries on a continuous domain hit the randomly chosen cell boundaries z_i with probability zero.
- standard math Sauer's lemma: a class of VC dimension d on N points has O(N^d) distinct labelings.
- standard math Littlestone's characterization: the optimal online mistake bound is the Littlestone dimension, achieved by the Standard Optimal Algorithm.
- standard math Entropy chain rule and the binary entropy function in the decision-tree cost lower bound.
- standard math Hoeffding's inequality in the randomized threshold algorithms.
Cite this review
Pith. "Pith review of Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning." pith.science (2026). https://pith.science/paper/KB3LEPHJ
@misc{pith2026250600135,
author = {Pith},
title = {Pith review of: Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/KB3LEPHJ}},
note = {Machine review of arXiv:2506.00135}
}
abstract
We study online and transductive online learning when the learner interacts with the concept class only via Empirical Risk Minimization (ERM) or weak consistency oracles on arbitrary instance subsets. This contrasts with standard online models, where the learner knows the entire class. The ERM oracle returns a hypothesis minimizing loss on a given subset, while the weak consistency oracle returns a binary signal indicating whether the subset is realizable by some concept. The learner is evaluated by the number of mistakes and oracle calls. In the standard online setting with ERM access, we prove tight lower bounds in both realizable and agnostic cases: $\Omega(2^{d_{VC}})$ mistakes and $\Omega(\sqrt{T 2^{d_{LD}}})$ regret, where $T$ is the number of timesteps and $d_{LD}$ is the Littlestone dimension. We further show that existing online learning results with ERM access carry over to the weak consistency setting, incurring an additional $O(T)$ in oracle calls. We then consider the transductive online model, where the instance sequence is known but labels are revealed sequentially. For general Littlestone classes, we show that optimal realizable and agnostic mistake bounds can be achieved using $O(T^{d_{VC}+1})$ weak consistency oracle calls. On the negative side, we show that limiting the learner to $\Omega(T)$ weak consistency queries is necessary for transductive online learnability, and that restricting the learner to $\Omega(T)$ ERM queries is necessary to avoid exponential dependence on the Littlestone dimension. Finally, for certain concept classes, we reduce oracle calls via randomized algorithms while maintaining similar mistake bounds. In particular, for Thresholds on an unknown ordering, $O(\log T)$ ERM queries suffice; for $k$-Intervals, $O(T^3 2^{2k})$ weak consistency queries suffice.
Reference graph
Works this paper leans on
-
[1]
The learner selects a distribution∆ t ∈∆({0,1}), and predictsˆy t ∼∆ t
-
[2]
The adversary revealsy t ∈ {0,1}and the learner suffers a lossI[ˆyt ̸=y t]. We define y1:T ∈ {0,1}T as the sequence of labels chosen by the adversary corresponding to x1:T . In therealizable setting, the adversary is subject to the constraint that the sequence (x1, y1), . . . ,(xt, yt) is realizable by C, meaning that there exists c∈ Csatisfying c(xi) =y ...
-
[3]
Set the target conceptcsuch thatc(x i) =b i for alli
-
[4]
Label all points in the same cell consistently
-
[5]
b determines an ordering over the points x1,
Assign labels to cells according to a threshold function determined byb The threshold function determined by b is determined as follows. b determines an ordering over the points x1, . . . , xT in the following sense. If b1 = 0, then x1 is the leftmost point in the ordering, and if b1 = 1, then x1 is the rightmost point in the ordering. Keep repeating for ...
-
[6]
Choosezuniformly at random from[0,1] T−1 , and constructx 1, x2, . . . , xT fromz
-
[7]
Choosebuniformly at random from{0,1} T
-
[9]
Present instancesx 1, x2, . . . , xT in order It’s sufficient to show that any algorithm incursΩ(T) expected mistakes – by the probabilisic method, this will imply that any algorithm incursΩ(T /2)expected mistakes on at least one instance of (concept class, target concept, first T instances). In the first timestep, the learner is given x1, which is in C1....
Show all 36 references
-
[10]
Choosezuniformly at random from[0,1] T ′−1, and constructˆx1,ˆx2, . . . ,ˆxT ′
-
[11]
, T′ andj= 1,
For eachi= 1, . . . , T′ andj= 1, . . . , S, present instancex(i−1)S+j = ˆxi
-
[12]
Re- stricted
Generate labelsy 1, y2, . . . , yT i.i.d. uniformly from{0,1}. Now consider the performance of the best hypothesis in Cz. This hypothesis can assign an optimal label to each cell Ci based on the majority of labels seen in phase i. For each phase i consisting of S 20 copies of ...
-
[13]
For anyj < t, bothct andc t+1 agree onz j (both outputb j)
-
[14]
preprocessing
Forz t itself,c t outputs1−b t whilec t+1 outputsb t. Since this is the case, the learner won’t gain any information about bt, so the adversary will make a mistake with probability 1/2 at each timestep since bt is chosen uniformly at random from {0,1} , independently of the le...
-
[15]
Both edges are colored red to represent oracle queries
At a query node: The algorithm queries the weak consistency oracle, creating two children corresponding to the possible responses (yes/no). Both edges are colored red to represent oracle queries
-
[16]
not realizable
At a prediction node: The algorithm makes a prediction for some example. To minimize mistakes, the optimal strategy is to predict the majority label among remaining concepts. When a mistake occurs (prediction differs from the true concept’s label), we draw a blue edge to the c...
-
[17]
There exists a deterministic algorithm that makes O(TlogT) calls to the weak consistency oracle and incurs at mostO(logT)mistakes
-
[18]
There exists a randomized algorithm that makes O(T) calls in expectation to the weak consistency oracle and incurs at mostO(logT)mistakes
-
[19]
There exists a deterministic algorithm that makes O(T) calls to the ERM oracle and incurs at most O(logT)mistakes
-
[20]
There exists a randomized algorithm that makes at most O(logT) calls to the ERM oracle in expecta- tion and makes at mostO(logT)mistakes. Proof Deterministic + weak consistency oracle (Part 1):The key insight is that for any two points xi, xj, we can determine their relative o...
-
[21]
Select two arbitrary pointsz 1 andz 2 from the current set
-
[22]
Make two ERM oracle queries: one with the labeled set {(z1,0),(z 2,1)} and another with {(z1,1),(z 2,0)}. 29
-
[23]
If {(z1,0),(z 2,1)} is realizable, thenz 1 ⪯z 2; otherwise,z 2 ⪯z 1
Exactly one of these queries will be realizable by the threshold class. If {(z1,0),(z 2,1)} is realizable, thenz 1 ⪯z 2; otherwise,z 2 ⪯z 1
-
[24]
This concept partitions the points into two sets:S 0 ={x:c(x) = 0}andS 1 ={x:c(x) = 1}
Consider the concept c defined by the ERM oracle query that is realizable. This concept partitions the points into two sets:S 0 ={x:c(x) = 0}andS 1 ={x:c(x) = 1}
-
[25]
Recursively sortS 0 andS 1 using the same approach
By the nature of threshold functions, all points in S0 must precede all points in S1 in the underlying total order. Recursively sortS 0 andS 1 using the same approach. For the base case (when a subset has size 1 or 0), no sorting is needed. Let T(n) be the number of ERM oracle...
-
[26]
Base Case:If |Ut| ≤5, we determine the exact ordering of the remaining points with a constant number of ERM oracle calls using a simple sorting algorithm, and predict accordingly
-
[27]
left half
Partitioning Step:If |Ut|>5 and we haven’t already computed a partition (UL,t, UR,t) of Ut, we compute one as follows: (a) Sample two pointsz 1, z2 uniformly at random fromU t (b) Call the ERM oracle with the labeled pair{(z 1,0),(z 2,1)} (c) If this labeling is realizable, th...
-
[28]
Randomly sample2kpoints fromU\ {z}without replacement
-
[29]
Consider the setSconsisting of these2ksampled points together withz
-
[30]
Using the weak consistency oracle, test all 22k+1 possible labelings of S to identify the unique unrealizable labeling
-
[31]
Observe the label assigned tozin this unrealizable labeling. The key insight is that in the unique unrealizable labeling (the alternating pattern), the position of z in the ordering determines its label: • If z is the minimum element in S (i.e., z≺z ′ for all z′ ∈S\ {z}), it w...
-
[32]
, xT }and an empty sequenceS
InitializeU={x 1, . . . , xT }and an empty sequenceS
-
[33]
• If it’s the first iteration (i.e
While|U|>2k+ 1: (a) Identify extreme pointsz 1, z2 using Lemma H.2 by iterating over allTpoints. • If it’s the first iteration (i.e. |U|=T ), designate z2 as z∗. z∗ will be the same fixed point for the remaining iterations. 33 • For whicheveri∈ {1,2}such thatz i ̸=z ∗, appendz...
-
[34]
This procedure yields a sequence S= (z 1, z2,
The remaining points inU(at most2k+ 1) can be placed in any order at the end ofS. This procedure yields a sequence S= (z 1, z2, . . . , zT−|U| , . . .)which, with high probability, repre- sents either the correct ordering ⪯ or its reverse. Since the definition of the interval ...
-
[35]
There exists a deterministic algorithm that makes O(1) calls to the ERM oracle and incurs at most O(d)mistakes
-
[36]
not realizable
There exists a deterministic algorithm that makes O(T) calls to the weak consistency oracle and incurs at mostO(d)mistakes. Before proving the theorem, we comment that in the transductive online learning setting, one can make a reduction from the weak consistency oracle to ERM...
-
[2024]
offline learning
2, 3, 4, 6, 7, 15 [KVK22] Alkis Kalavasis, Grigoris Velegkas, and Amin Karbasi. Multiclass learnability beyond the pac framework: Universal rates and partial concept classes.Advances in Neural Information Processing Systems, 35:20809–20822, 2022. 22 [Lit88] Nick Littlestone. L...
2022 arXiv
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.