- Rating
- 1
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper claims that it proves an exponential separation between random algorithms and deterministic algorithms in the transductive online learning of threshold with an ERM oracle. In other words, if we want to get a sublinear mistake bound, any deterministic algorithm needs to call the ERM oracle times. In the previous work, Attias, Hanneke, and Ramaswami showed that a randomized algorithm can achieve an mistake bound with queries in expectation. Therefore, there is an exponential separation between deterministic and randomized algorithms.
Critical strengths
None.
Critical weaknesses
The main contribution claimed by this paper has been proven in [AHR'25] as Theorem 4.4. The statement differs, but the main information is the same: the number of queries made by the deterministic algorithm must be linear in T to achieve a sublinear mistake bound.
Their theorem is even stronger, as it holds for any class with Littlestone dimension instead of just for threshold.
[AHR'25] Idan Attias, Steve Hanneke, and Arvind Ramaswami. Tradeoffs between mistakes and ERM oracle calls in online and transductive online learning. NeurIPS'25.
Questions for authors
Do you even carefully read the paper that you claim you solved an open question in?
We thank the reviewer for carefully examining the relationship between our results and AHR25 and for asking us to clarify the novelty of the separation.
Our main result is not implied by Theorem 4.4 of AHR25: we establish a deterministic lower bound for the same unknown-order threshold family on which their randomized upper bound holds. We have made it explicit in Section 1.
Why Theorem 4.4 does not give this lower bound. The theorem concerns the family of all classes of Littlestone dimension d and assumes T≥2d+1. A lower bound for that family provides a hard class within it; it does not imply a lower bound for each subfamily. For the complete threshold classes considered here, d=⌊log2(T+1−ε)⌋, so T<2d+1 under both conventions. Thus the theorem cannot be applied as stated. The O(logT) expected-query upper bound in AHR25's Theorem 4.5(4) is for the threshold family, not for the larger family used in Theorem 4.4; combining those two results therefore does not establish a separation.
Why the block construction is not already the threshold construction. The proof of Theorem 4.4 uses equivalence blocks whose members receive identical labels under every concept. For two distinct points u,v in one block, both queries {(u,1),(v,0)} and {(v,1),(u,0)} are unrealizable. In a complete threshold class on a strict total order, exactly one is realizable. Breaking ties inside a block adds concepts and changes the legal oracle responses. Consequently, the block lower bound does not automatically transfer; a reduction would need to preserve the query interaction.
What our proof adds. Under the minimal-prefix rule announced before the learner, fixing the position of at most one point per call suffices to give the same oracle answer, either ⊥ or one full label vector, for every order kept possible by the construction (Lemma A.2). Counting these commitments and realizing the interaction on one fixed order and target gives the sharp bound M+Q≥T−ε (Theorem 3.1). This supplies the missing deterministic half of the separation. The independent randomized lower bound in Theorem 3.2 shows that Ω(logT) worst-instance expected calls are necessary for O(logT) expected mistakes. Finally, Theorem 3.4 shows that the deterministic obstruction depends on selection: a legal feasible-median rule allows logarithmic calls and mistakes.
AHR25 describe their randomized threshold algorithm as an “exponential improvement” in Section 1.1. The comparison there is between their deterministic O(T)-query algorithm and randomized O(logT)-expected-query algorithm in Theorem 4.5(3–4): both are upper bounds. It does not establish that every deterministic learner needs linearly many calls for logarithmic mistakes. Table 2 likewise records the deterministic upper bound. Their discussion treats the necessity of randomization as unresolved, and Section 5 retains the question of provable superiority. Our lower bound supplies the missing necessity result for the same threshold family.
The cited locations in the published version of [AHR25] are PDF pages: the Section 1.1 comparison and Table 2 on p. 4, Theorems 4.4–4.5 on p. 8, the proof of Theorem 4.4 on pp. 33–34, and Section 5's discussion question on p. 10. Section 1 of our revision explains the two-point distinction, and Appendix B retains the theorem comparison.
Reference
[AHR25] Idan Attias, Steve Hanneke, and Arvind Ramaswami. “Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning.” In Advances in Neural Information Processing Systems, vol. 38, pp. 75639–75680. Curran Associates, Inc., 2025.