acceptodds
Under review as a conference paper at ICLR 2027

An Exponential Deterministic-Randomized Separation in Oracle-Based Online Learning

Abstract

Randomization is known to improve oracle efficiency in online learning, but whether it can provide a provable advantage over deterministic algorithms has remained open. We resolve this question for transductive online learning of thresholds on an unknown total order with a consistency-type empirical risk minimization (ERM) oracle. For natural extremal ERM rules, including minimal-prefix and maximal-prefix selection, every deterministic learner incurs linear total cost: on some instance, the number of mistakes and oracle calls satisfy . Consequently, any deterministic learner achieving mistakes requires oracle calls. In contrast, the randomized learner of AHR25 achieves expected mistakes and expected oracle calls under the same fixed rule. We prove a matching expected-query lower bound, establishing the optimal randomized query complexity. We further show that the separation depends on the oracle's selection rule: a legal feasible-median rule admits deterministic complexity, while extremal and global-median rules force linear cost. Thus, randomization yields an exponential separation in oracle complexity, while oracle selection emerges as a fundamental complexity axis.

Primary area:
learning theory
Keywords:
Online learning, Transductive learning, ERM oracle complexity, Randomized algorithms, Mistake bounds

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_MCZWOpenReview ↗
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 Ω(T)\Omega(T) times. In the previous work, Attias, Hanneke, and Ramaswami showed that a randomized algorithm can achieve an O(log⁡T)O(\log T) mistake bound with O(log⁡T)O(\log T) 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 dLDd_{\mathrm{LD}} 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?

1 comment

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 dd and assumes T≥2d+1T\ge 2^{d+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=⌊log⁡2(T+1−ε)⌋d=\lfloor\log_2(T+1-\varepsilon)\rfloor, so T<2d+1T<2^{d+1} under both conventions. Thus the theorem cannot be applied as stated. The O(log⁡T)O(\log T) 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,vu,v in one block, both queries {(u,1),(v,0)}\{(u,1),(v,0)\} and {(v,1),(u,0)}\{(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 ⊥\bot 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−εM+Q\ge T-\varepsilon (Theorem 3.1). This supplies the missing deterministic half of the separation. The independent randomized lower bound in Theorem 3.2 shows that Ω(log⁡T)\Omega(\log T) worst-instance expected calls are necessary for O(log⁡T)O(\log T) 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)O(T)-query algorithm and randomized O(log⁡T)O(\log T)-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.

Reviewer_5EjsOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers online learning in an oracle model. Following the work of AHR25, the authors consider a model in which there is an unknown ordering of a collection of inputs, an unknown threshold function, and the learner must predict the labels of the points at each time. The learner has access to a "consistency" oracle; one concrete instantiation of the oracle is one that returns the hypothesis that is consistent with the query, and has the "minimal prefix" property.

In this setting, the paper proves that the number of queries + number of mistakes must essentially be at least T, for any deterministic algorithm. This supplements the work of AHR25, who show that if randomization is allowed, mistakes and queries can be made O(log⁡T)O(\log T).

Critical strengths

The paper is an interesting contribution to the literature on online learning with oracle access models. The proof seems to follow the overall approach of AHR25, but also involves several technical steps. While such a lower bound may not be too surprising (it parallels the deterministic/randomized differences in say Quicksort), it is nonetheless interesting to be proved formally.

Critical weaknesses

I am reluctant to recommend acceptance to a broad ML venue:

  • The result is ultimately a lower bound on deterministic algorithms, which may not be too surprising in this context.
  • The scope of the result seems really narrow: it applies to hypotheses defined using orderings, I am not sure if there are more general interesting classes for which this deterministic/randomized gap applies
  • The paper is reads as if it is highly AI generated; I thought the exposition is very weak. I could not understand the setting without spending a decent amount of time on AHR25. Most of the introduction (after the first two paragraphs), including the paragraphs "The separation", "Why fixing the rule matters", etc. reek of AI written text.
  • Section 2 is overly terse and does not give any motivation for why they study this.

I feel the paper in its current form, irrespective of the strength of result, is not acceptable to a broad-audience conference like ICLR.

Questions for authors
  • The authors discuss briefly why the deterministic lower bounds in AHR25 are not directly applicable; but this paragraph seems overly terse. Can they explain (in human words) a bit more? Is it only a technical reason?
1 comment

We thank the reviewer for the detailed feedback on the contribution, scope, and presentation, and for emphasizing the need to make the paper self-contained.

The contribution is a separation for all deterministic learners under the same oracle rule used by the randomized learner, rather than a bad case for one deterministic algorithm. The threshold scope is deliberate and remains a limitation. We have revised the exposition to make both points clear without requiring the reader to first study AHR25.

Why AHR25's deterministic lower bound does not apply: more than a technical hypothesis. Their Theorem 4.4 constructs hard classes inside the family of all classes of a given Littlestone dimension. Its classes are thresholds over equivalence blocks, whereas ours contain every prefix of a strict order on distinct points. This changes what a query can reveal: if u,vu,v belong to one block, neither {(u,1),(v,0)}\{(u,1),(v,0)\} nor its label-reversed version is realizable; in a strict-order threshold class, exactly one is. Thus simply breaking ties changes the oracle responses and does not preserve the lower-bound argument. There is also a direct hypothesis mismatch: for our classes d=⌊log⁡2(T+1−ε)⌋d=\lfloor\log_2(T+1-\varepsilon)\rfloor, hence T<2d+1T<2^{d+1}, whereas Theorem 4.4 requires the reverse inequality. Our Lemma A.2 supplies the rule-specific argument for full threshold classes. Section 1 now explains this with the two-point query, rather than relying only on the dimension calculation.

Why this is stronger than the Quicksort analogy. A bad input for deterministic Quicksort shows a limitation of its pivot policy; deterministic sorting can still achieve O(nlog⁡n)O(n\log n) comparisons. Here the bound M+Q≥T−εM+Q\ge T-\varepsilon holds for every deterministic learner under the fixed minimal-prefix rule. Moreover, the same linear obstruction fails for a different legal rule, feasible-median selection. Its answer provides a balanced split, and a subsequent prediction mistake identifies which side can be discarded. The independent randomized lower bound also establishes optimality of the logarithmic expected-query order. These are the problem-level and rule-specific conclusions, beyond an analysis of one randomized algorithm.

Scope and broader relevance. We do not establish the same separation for a broader non-threshold family. The one-pin criterion in Proposition A.8 abstracts the deterministic proof over selection rules within the anchored-threshold construction; it is not a theorem for arbitrary concept classes. A lower bound transfers to a larger family containing these complete threshold classes under the same domain, protocol and oracle interface, but the randomized upper bound does not follow by inclusion. We now state this distinction in Section 8. The broader design question supported by the results is whether the choice among equally valid oracle answers changes access complexity when the class and feedback interface are held fixed. Extending the separation itself requires another construction or reduction.

Writing and AI assistance. The model and proof dependencies should be readable without first consulting AHR25. We used AI assistance as specified in the AI use statement, which also records the human verification performed; we take responsibility for the exposition. We have revised Sections 1–2 to explain what the learner knows, what a query returns and how this differs from observing a target label; replaced the headings in Sections 4–7 with descriptive titles; consolidated the repeated AHR25 comparison in Appendix B; and merged the overlapping related-work passages. Example 2.1 works through three points and states exactly when the returned answers identify the order. The original main theorem statements and proof arguments are retained. Existing examples and explanations in Appendices A–C remain; new explanations are marked in blue, and Proposition G.1 is a separate result. The proof-route table and the supporting lemma references identify the dependencies. The revised main text remains nine pages.

Reviewer_qwEzOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies whether randomization can reduce the number of oracle calls needed for online learning. The setting is threshold classification on an unknown ordering of the points. The learner knows the sequence of points in advance and can query an oracle that returns a classifier consistent with a supplied labeled sample, or reports that no such classifier exists. The main result shows that, for simple oracle rules such as returning the smallest consistent prefix, every deterministic learner must incur roughly (T) mistakes and oracle calls combined. Therefore, achieving O(log T) mistakes requires Theta(T) oracle calls. In comparison, the randomized algorithm from previous work achieves O(log T) mistakes with O(log T) expected calls. The paper also proves a matching randomized lower bound.

Critical strengths
  • The paper for the first time shows a gap between the randomized and the deterministic algorithms for the online learning setting although for a very particular setting.
Critical weaknesses
  • The separation between the randomized vs. deterministic setting remains limited to the a very specific setting of threshold learning and not clear if any of the ideas/methods would generalize to other settings.
  • The presentation of the paper is a bit dense and it is hard to follow everything. It would be nice if the problem is introduced with small examples clearly explaining all the different terminology used in the paper since the setting considered in this paper is very specific and is not well known in the online learning literature.
Questions for authors
  • How much does the randomized advantage depend on allowing the learner to submit artificially labeled samples?
1 comment

We thank the reviewer for the thoughtful questions about hypothetical-label queries and the scope of the separation.

We use the ERM interface of AHR25 (Definition 2.1), which accepts arbitrarily labeled samples. Their Section 1.1 explicitly distinguishes it from restricted ERM, which accepts only observed pairs. Both deterministic and randomized learners therefore have the same permission to query hypothetical labels. The logarithmic-mistake separation nevertheless depends on access beyond observed pairs, as Proposition G.1 makes precise.

A precise answer to the hypothetical-label question. Proposition G.1 considers the concrete restriction that every queried pair must already have been revealed by the online interaction (also allowing the known positive sentinel under convention E). It proves that every such learner, deterministic or randomized, that completes all TT rounds after finitely many calls almost surely on every instance has a fixed instance on which its expected mistakes are at least (T−ε)/2(T-\varepsilon)/2. No deterministic or expected bound on the number of calls is assumed. This rules out sublinear worst-case expected mistakes under the minimal-prefix rule. It does not characterize every intermediate restriction on admissible queries.

The proof chooses independent fair labels for the non-anchor instances, places the positive points first in arrival order after the positive anchor, and fixes the threshold after them. On this distribution, every observed-sample minimal-prefix answer is determined by labels already revealed, so each remaining hard-point label still costs one-half expected mistake. This information-free property is specific to the hard distribution: observed queries can be useful on other instances. Appendix G gives an explicit counterexample to the broader interpretation.

Both upper bounds being compared use the unrestricted interface. The deterministic learner of AHR25 sorts using hypothetical pair labels; the randomized learner also queries pairs with opposite labels. Such a query asks about consistency with the hidden class, not for the target's label. The original Theorems 3.1–3.2 already allow arbitrary queried samples. Proposition G.1 therefore clarifies the access assumption.

Generalization. We have not established an analogous separation for a different, broader family. Proposition A.8 isolates a sufficient condition on selection rules within the threshold construction. The lower bound also transfers to superfamilies containing these complete threshold classes with the same domain and oracle interface, but this does not transfer the randomized upper bound. Section 8 now distinguishes these one-sided observations from a genuine extension of the separation.

Examples and readability. The revised Sections 1–2 introduce the hidden order, target cutoff, oracle and selection rule before the proof machinery. Example 2.1 works through three explicit queries and their responses, including a hypothetical-label comparison. It also distinguishes a response that is forced for the actual order from information the learner can infer: the two-query recovery of the order is asserted only when the announced rule is minimal-prefix. The longer worked examples remain in Appendices A and C. Proposition G.1 is proved in Appendix G.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.