Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
Authors: Idan Attias
Steve Hanneke
Arvind Ramaswami
Venue: NeurIPS 2025 spotlight ()
Keywords: Online Learning
Transductive Online Learning
Oracles
Primary area: theory
TL;DR: We study tradeoffs between mistakes and oracle calls in online and transductive online learning, proving tight mistake bounds for the online setting and showing that transductive learning admits improved bounds, with further gains from randomization.

Abstract: We study online and transductive online learning in settings where the learner can interact with the concept class only via Empirical Risk Minimization (ERM) or weak consistency oracles on arbitrary subsets of the instance domain. This contrasts with standard online models, where the learner has full knowledge of the concept class. The ERM oracle returns a hypothesis that minimizes the loss on a given subset, while the weak consistency oracle returns only a binary signal indicating whether the subset is realizable by a concept in the class. The learner's performance is measured by the number of mistakes and oracle calls.

In the standard online setting with ERM access, we establish tight lower bounds in both the realizable and agnostic cases: $\Omega(2^{d_\mathrm{LD}})$ mistakes and $\Omega(\sqrt{T 2^{d_\mathrm{LD}}})$ regret, respectively, where $T$ is the number of timesteps and $d_\mathrm{LD}$ is the Littlestone dimension of the class. We further show how existing results for online learning with ERM access translate to the setting with a weak consistency oracle, at the cost of increasing the number of oracle calls by $O(T)$.

We then consider the transductive online model, where the instance sequence is known in advance but labels are revealed sequentially. For general Littlestone classes, we show that the optimal mistake bound in the realizable case and in the agnostic case can be achieved using $O(T^{d_\mathrm{VC}+1})$ weak consistency oracle calls, where $d_\mathrm{VC}$ is the VC dimension of the class. 
On the negative side, we show that $\Omega(T)$ weak consistency queries are necessary for transductive online learnability, and that $\Omega(T)$ ERM queries are necessary to avoid exponential dependence on the Littlestone dimension.
%
Finally, for special families of concept classes, we demonstrate how to reduce the number of oracle calls using randomized algorithms while maintaining similar mistake bounds. In particular, for Thresholds on an unknown ordering, $O(\log T)$ ERM queries suffice, and for $k$-Intervals, $O(T^3 2^{2k})$ weak consistency queries suffice.

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
Idan Attias
Steve Hanneke
Arvind Ramaswami
Abstract
We study online and transductive online learning in settings where the learner can interact with the concept class only via Empirical Risk Minimization (ERM) weak consistency oracles arbitrary subsets of the instance domain. This contrasts with standard online models, where the learner has full knowledge the concept class. The ERM oracle returns hypothesis that minimizes the loss on a given subset, while the weak consistency oracle returns only a binary signal indicating whether the subset realizable by concept in the class. The learner's performance is measured by the number of mistakes and oracle calls.
In the standard online setting with ERM access, we establish tight lower bounds in both the realizable and agnostic cases: !(22mn)) mistakes and 92( (T24))) regret, respectively, where the number of timesteps and DLD the Littlestone dimension of the class. We further show how existing results for online learning with ERM access translate to the setting with a weak consistency oracle, at the cost of increasing the number of oracle calls by OTT).
We then consider the transductive online model, where the instance sequence is known in advance but labels are revealed sequentially. For general Littlestone classes, show that the optimal mistake bound in the realizable case and in the agnostic case can be achieved using O(Táve-1) weak consistency oracle calls, where dve is the VC dimension of the class. On the negative side, show that I(T)) weak consistency queries are necessary for transductive online learnability, and that S2(T) ERM queries are necessary to avoid exponential dependence on the Littlestone dimension. Finally, for special families of concept classes, we demonstrate how reduce the number of oracle calls using randomized algorithms while maintaining similar mistake bounds. In particular, for Thresholds on an unknown ordering, Olog T') ERM queries suffice, and for k-Intervals, (T weak consistency queries suffice.
Introduction
Online learning is fundamental sequential prediction framework in which a learner receives stream of instances and must predict their labels one at time, observing the true label after each prediction [CBL06, SS 12, MRT12, SSBD14). The goal is to minimize the number of mistakes compared to the best concept in a fixed concept class. A closely related framework is transductive online learning, where the entire sequence of instances is revealed in advance, removing instance uncertainty and isolating the challenge of predicting the labels [BDKM97, KK05, CBS13, HMS23, HRSS24). This intermediate model retains the sequential nature of online learning while allowing the learner to prepare for the specific instances will encounter.
"Institute for Data, Econometrics, Algorithms, and Learning (IDEAL), hosted by UIC and TTIC; idanatt wastettiiiseeeee gewal.mm.l..... com.
DDepartment of Computer Science, Purdue University; steve. aiaiessiyy..ttee...aaeeeeeeeee. www.hheannnneaill...... com. I Department Computer Science, Purdue University; r wwwpaaseswwwepuuueeeeeeeeeee
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Both the online and transductive online settings have been studied extensively. The seminal work of Littlestone [Lit88] characterizes the optimal mistake bound attainable in the online binary clas- sification setting in the realizable case, that is, when there exists a concept in the class that labels all instances correctly. This bound is expressed in terms of a complexity measure of the concept class C. known as the Littlesonne dimension (denoted by dLD). In particular, the optimal mistake bound is d (C) and is achieved by the Standard Optimal Algorithm (SOA). In the agnostic setting, where labels may be arbitrary and the learner aims to minimize regret (the difference between the learner's s cumulative mistakes and that of the best concept in the class), Ben DavidDvvd et al. [BDPSS09] and Alon et al. [ABED* * 21] showed that the Littlestone dimension also characterizes the optimal regret. These results also hold trivially in the transductive online setting, since the learner has more information than in the standard online setting. However, since the instances are known in advance, a sequence-des dependeett bound of O (C) log T) on the number of mistakes can be obtained [KK05] by counting the number of shattered sets and applying the Halving algorithm, where dyc is the VC dimension [VC71, VC*74 of the class and T is the length of the instance stream. Most recently, it has been shown that for some classes, a mistake bound of O diD) is achievable in the transductive setting, and that this rate is optimal [CHMS25].
While the SOA achieves the optimal mistake bound and has been used as an algorithmic primitive in many settings, implementing it efficiently poses significant computational challenges. The al- gorithm involves computing the Littlestone dimension multiple times during its online interaction, but even approximating the Littlestone dimension within any constant factor is computationally intractable [FL.9,, MR17, Man22]. Additionally, Hasrati and Ben-David [HBD23] showed that there exist recursively enumerable representable classes with finite Littlestone dimension that admit no computable SOA. As a result, Assos et al. [AAD+ 23] and Kozachinskiy and Steifer [KS24] proposed more realistic computational model for online learning based on oracle access to Empirical Risk Minimization (ERM). Given a labeled dataset, the ERM oracle returns a concept in the class that minimizes the error on the dataset. This oracle performs simple and well-studied task, known to be sufficient in stochastic batch settings such as PAC learning. The central question, then, is: what is the mistake bound (or regret) when the online learning algorithm is restricted to using only the ERM oracle? A mistake bound that is exponential in the Litrlestone dimension is attainable, as shown by [AAD*23, 23, KS22],, At the same time, an exponential mistake bound is also unavoidable [KS24] when the algorithm has access only to a "restricted" ERM oracle, one that can query only instance-label pairs generated by the adversary.
The goal of this paper is to study the power and limitations of various oracles in the online and transductive online learning settings. Crucially, unlike in standard settings where the learner has full access to the concept class, here the learner interacts with the class only through an oracle. The performance of the learning algorithm is measured by two parameters: the number of mistakes (or regret in the agnostic setting) and the number of oracle queries made, with the goal of achieving efficient oracle complexity, where only polynomially many oracle calls are made.
We begin by considering a general ERM oracle that, given any finite subset of the instance domain along with any labeling, returns an empirical risk minimizer. This contrasts with the more restricted ERM oracle used in prior work [AAD*23, KS24], which allows queries only on instances and labels provided by the adversary during the interaction. For this more powerful oracle, we investigate two main questions:
In online learning, can we circumvent the exponential dependence on the Littlestone dimension in the mistake bound using the general ERM oracle?
In the transductive online setting, where the learner has access to the full sequence of instances in advance, can this additional information lead to improved learning guarantees?
Additionally, we consider weaker oracle, the weak consistency oracle, which, given a labeled dataset, returns only a binary signal indicating whether the dataset is realizable by some concept in the class. This oracle can be viewed as solving the decision problem of realizability, in contrast to the ERM oracle, which solves the corresponding optimization problem. Surprisingly. Daskalakis and Golowich [DG24] recently showed that access to such an oracle can be used to construct a randomized PAC learning algorithm for binary and multiclass classification, regression, and learning partial concepts, with only a mild blowup in sample complexity and polynomial number of oracle calls. In this paper, explore the role of this oracle in online learning:

---

Can we construct algorithms for online and transductive online learning that make only polyno- mial number of calls to the weak consistency oracle?
For comprehensive literature review, see Appendix
1.1 Our Contribution
We first study online learning with access to an ERM oracle that can query any subset of the domain, in contrast to the "restricted ERM" studied by [AAD+23, KS24], which can query only pairs of instances and labels generated by the adversary throughout the interaction. We then consider learning with weak consistency oracle, recently introduced by [DG24] in the context of PAC learning.
Results for Online Learning (Section 3). See summary of the results in Table 1.
We first prove a lower bound of (((2ku) mistakes in the realizable setting (where dLD is the Littlestone dimension), which holds for any learning algorithm that makes finite number of ERM oracle calls. While [KS24] proved a stronger lower bound of 12(3LL)) ), their result applies to the restricted ERM. In contrast, our lower bound holds for the general ERM and introduces several
new challenges. We also prove lower bound of Ω ((VT2 on the regret in the agnostic setting, which is the first lower bound of its kind. These two lower bounds match the known upper bounds of [AAD* 233, KS24] in their exponential dependence on the Littlestone dimension (differing only by a constant factor in the exponent). This demonstrates that even with access to the general ERM, the mistake bound grows exponentially with the Littlestone dimension, unlike in standard online learning, where the learner has full access to the concept class and the mistake bound is dLD--
We show that any deterministic online learning algorithm using the restricted ERM be simulated using the weak consistency oracle, at the cost of increasing the number of oracle calls by O(T). Consequently, the mistake bounds in existing results [AAD $23, KS24] can be achieved with an O(T) blow-up when using the weak consistency oracle.
We show a negative result for online learning of partial concept classes (concepts that may be undefined on certain parts of the domain) with access an ERM oracle. Specifically, we construct family of partial concept classes with d'DD = for which any algorithm must make S?(T) mistakes. This stands sharp contrast to the offline PAC setting, where learning partial concepts with weak consistency oracle is feasible [DG24].
ONLINE LEARNING: ORACLE COMPLEXITY REGRET TRADEOFFS LITTLESTONE CLASSES
Dederministi/Ranlloniin
Realizability
Oracle Type
Oracle Calls
Regret/Mistakes
Reference
Algorithm
Deterministic
Restricted
20(n)))
20(4)D)
[AAD KS24]
Deterministic
Weak Consistency
20(LD
20("LD)
Theorem 3.3
Realizable
Deterministic
Restricted ERM
Finite
0(34LD)
[KS24]
Randornized
Agnostic
Finite
D(24LD)
Deterministic
Agnostic FRM
T2
(V220LLD)
[AAD 23]
Agnostic
Randemized
Agnostic ERM
Finite
Q(VT2<LD)
Theorem
Table I:
The learning model and oracles are defined in Section 2. The weak consistency oracle outputs whether a labeled sequence is realizable. We define three ERM oracles, ordered from weakest to strongest: the restricted ERM oracle, the ERM oracle, and the agnostic ERM oracle. T is the number of timesteps, dLD is the Littlestone dimension and dyc is the VC dimension of the underlying concept class.
Given the negative results the online setting, particularly the exponential growth in the number of mistakes, we consider the transductive online learning model, in which the instance sequence is known at the beginning of the interaction, but the labels are revealed sequentially by the adversary.
Results for Transductive Online Learning (Section 4). See summary of the results Table 2. We start with results for general concept classes.
3

---

We show how discover all labelings of the concept class a given set of instances ing O(Táve+I) weak consistency oracle calls. With this preprocessing step, we can recover the optimal mistake bound and regret, which are currently known be upper bounded by O (min dvc log 7)) and Ô [T d log T)) respectively. This shows that the exponential dependence on the Littlestone dimension can be circumvented in the transductive setting using only polynomial number of weak consistency oracle calls.
On the other hand, establish the following two lower bounds. We show that limiting the learner to (2(T)) weak consistency queries is necessary for transductive online learnability, and that restricting the learner to Q(T)) ERM queries is necessary avoid exponential dependence on the Littlestone dimension.
We proceed to studying special families of concept classes, showing improved results, which highlight that randomization seems to be crucial for the improvements.
Thresholds: We prove various upper bounds for deterministic and randomized algorithms using both oracles. The main result a randomized algorithm with the ERM oracle that achieves an Ollog 7) mistake bound and Ollog 7') expected queries on the class of thresholds with unknown ordering. This represents an exponential improvement over deterministic algorithms.
k-Intervals: We show there exists randomized algorithm with the weak consistency oracle that achieves optimal mistake bound (upper bounded by O log T)) with O(T320k) expected number of queries.
d-Hamming Balls: For the ERM oracle with d- d-Hamming balls, we show a mistake bound of 2d using single query. We also show a mistake bound of with 2d+1 queries.
In Section 5 pose the main open problems for future work.
TRANSDUCTIVE ONLINE LEARNING: ORACLE COMPLEXITY REGRET TRADEOFFS
Det. / Rand.
Concept Class
Realizability
Oracle Type
Oracle Calls
Regrot/Mistakes
Reference
Algorithm
Deterinnittc
Realizable
ERM
2004,
20dnn)
[AAD*22, KS24]
Determnnisti
Realizable/Agnosti
Weak Consistency
O
Optimal
Theorem 4.2
Lintestone Classes
Deterministic
Realizable
ERM
O(T)
12(2
Theurem
Randemized
Realizable
Weak Consistency
O(T)
((())
Theurem 4.3
Deterministic
Realizable
ERM
O(T)
O(log T)
Randomized
Realizable
ERM
Ollog T)
O(log T)
Thresholds
Determnnittic
Realizable
Weak Consistency
O(T log T)
O T)
Randomized
Realizable
Consistency
O(T)
O(log T)
k-Intervals
Randomized
Realizable
Weak Consistency 0(T
O(k log(T))
Theorem 4.6
Deterministic
Realizable
ERM
O(1)
O(d)
d HaHaming Balls
Theorem 11.4
Deterministic
Realizable
Weak Consistency
O(T)
O(d)
Table 2:
The lower bound for the weak consistency oracle from Theorem 4.3 applies all three families of concept classes: thresholds, k-intervals, and d-Hamming balls, and stronger than the bound for arbitrary Littlestone classes. We use the term "optimal" to indicate that the mistake bounds match those from standard transductive learning (where the concept class is known). In particular, the best known bounds depend linearly on the Littlestone or VC dimensions.
2 The Learning Models: Online and Transductive Online Learning with Oracle Access
We start with a definition of the online learning model where the interaction of the learner with the concept class is done only through an oracle. This is in contrast to the standard online model, where the learner knows the concept class in advance. The learning protocol is sequential game between a learner and an adversary. Let C (0, 1)* be concept class, where X' the instance space and {0, 1} is the label space. Let JF be family of concept classes, known to the learner (c.g., classes

---

with finite Littlestone dimension dI.D), such that C is unknown concept class from F chosen by the adversary. Suppose the learner only has oracle access to via an oracle O. Thee sequential game proceeds for T' rounds, as follows. For each [T]:
1. The adversary chooses (It, (t) X {0,
2. The learner observes Zt. picks distribution A, A((O, and predicts A..
3. The adversary reveals y/: E [0, and the learner suffers a loss 1l/rr + yr)-
X the sequence of instances and V1.T (11, .e....,.T)) E {0, 1) as the sequence of corresponding labels chosen by the adversary. In the realizable setting, the adversary is subject to the constraint that the sequence (21:7, (1.r) is real- izable by C, meaning that there exists c E satisfying c(z,) y/s for all i [T]. The performance of learning algorithm A is measured two metrics, the number of mistakes (or regret, in the agnostic setting) and the number of oracle queries. The mistakes are defined as follows:
We define U1.T (x) 22..... .T)
((A, E. U + c(xx))-
The worst case number of mistakes of learning algorithm A is defined as
M(A,T) = sup sup sup (AM O(C), æ1.r,)) CEF eEC #LTEXT
Similarly, Q(A, (C),, 31.r, c) is the total number of queries, defined as O(Q(A,
Q(A, = sup sup sup CE aEC SITEXT
Here, the expectation over the randomness of the algorithm.
We assume that the adversary is oblivious with respect to the choice of concept class C, target concept and instance sequence x. meaning that these fixed in advance and do not depend the learner's predictions or queries. Note that for deterministic algorithms, an oblivious adversary is as powerful adaptive adversary.
In the agnostic case, the sequence (I1.T, V1.r) is no longer constrained to be realizable by C, and the measure of performance is the regret, defined as
T inf CEC
Reg(A, O(C), (ZIrT (irr))):))))))))
Σ Tiu +
vel
Σ Me(xs) + vel
Define the worst case regret the algorithm A as
Reg(A, 7) sup sup Cel' (x,))
E[ee(A O(C), (x,,))),
and Q(A,T) in the agnostic case defined the worst-case total number of queries, over C E F and (x,z) (X' x 1))
Crucially, the learner knows the family of concept classes F but not C F. The learner's only access to the concept class C is through oracles defined below. We start with a few variants of the ERM oracle.
Definition 2.1 (Variants of ERM Oracle) We define the oracles in order of expressive strength. Let C be the concept class have access
"Restricted ERM": At round 4, given a subsequence of the pairs generated by the adversary, (I1::-1, 11:t-1), if S is realizable by C, then the ERM oracle returns some C consistent with S. Otherwise, returns "not realizable." This oracle was used for the upper bounds in 23, KS24] and for the lower bound in [KS24]. Here, it is used primarily for comparison to our results, as well as in the upper bound in Theorem 3.3.
Given any subset S (0, 1). if S realizable by C, then ERM oracle returns some e.E C consistent with S. Otherwise, it returns "not realizable". This oracle can be thought of as "realizable" " ERM or consistency oracle. For simplicity, we refer to it as ERM. This is the main variant used in this paper.
ERM:
5

---

"Agnostic" ERM: Given any subset @ X (0,1), returns a concept with the minimal error: argmingge (asy)s [[((x) w]. This oracle is used for the lower bounds in Theorems 3.1 and 3.2.
Additionally, we consider the following weaker oracle, studied by [DG24] in the context of PAC learning.
Definition 2.2 (Weak Consistency Oracle) Given a concept class C S (0. 1) and any sequence S = (I1, 11); (En, ), ), the Weak Consistency Oracle returns "realizable" if there exists some e E consistent with S. Otherwise, returns "not realizable".
We also study the transductive online setting with oracle access, where the only difference is that the adversary first selects sequence x (#1, , E XT, which revealed to the learner in advance Then, the sequential interaction begins, with the adversary revealing the labels one by one. Formally, for each t [7]
1. The adversary chooses y {0, 1}.
2. The learner picks distribution A, A(10, 1}), and predicts ý A.-
3. The adversary reveals y/ and suffers loss I[y # 9t)-
The notions of mistakes and regret are defined similarly and are formalized in Appendix B. The standard transductive online learning model, in which the learner has access to the concept class in advance, was studied by [BDKM97, HMS23].
3 Online Learning
In this section, we consider the problem of online learning with oracle access. First, we present lower bounds on the number of mistakes in the realizable setting and lower bound on the regret in the agnostic setting with access to an ERM oracle. For the realizable case, lower bound of ((34LD) was proved by [KS24], but only for an ERM restricted to querying instances and labels generated by the adversary throughout the interaction. Here, we make no assumptions about the ERM (our result holds for the strongest "agnostic" ERM variant, see Definition 2.1), which introduces several challenges, and we show that the exponential dependence the first lower bound of its kind. matches the upper bound [AAD 23] up to a constant factor in the exponential dependence the Littlestone dimension, and up to log(T)) factor.
dLDD is unavoidable. For the agnostic case, this is
Theorem 3.1 (Lower Bound for Online Learning with "Agnostic" ERM Oracle) Let F be the family of classes with Litlestone dimension dr.D. Then, any randomized algorithm that makes a finite number of queries to the ERM oracle incurs Q(20LD) expected mistakes.
Proof sketch We construct a threshold function over 2 points embedded in [0, 1]7 partitioning the space into T nested hyperrectangles using uniform random values 21. 2T-1- 2T- The first point #1 corresponds to the entire hypercube [0, 1-711 except for a specific hyperplane, while subsequent points x; correspond to increasingly smaller nested hyperrectangles, each defined by matching more coordinates with the random values 2j.
The concept class consists of random threshold functions where all concepts agree within each hyper- rectangle equivalence class. When the adversary presents point 2,, the learner cannot query points from future equivalence classes with non-zero probability, these classes are defined by randomly chosen values žt, 2T-1 that won't be hit by finite queries. Thus, the "agnostic" ERM oracle provides labels for the current hyperrectangle but gives no information about nested hyperrectangles corresponding to future points. This geometric structure forces the learner to make predictions about points in nested regions without prior information, resulting in mistake with probability 1/2 at each step. This yields ((T/2) (2(2)L)) expected mistakes.
'A common version of the transductive online learning setting considers x as a set I' points rather than a sequence (e.g.. [SKS16]). We focus on the version where is sequence, though our results could extend to the based formulation.

---

Theorem 3.2 (Lower Bound for Agnostic Online Learning with "Agnostic" ERM Oracle) Let FF be the family of classes with Littlestone dimension dL.D. Then, any randomized algorithmn that makes a finite number of queries the ERM oracle incurs 52 (T2)))) expected regret.
The full proofs for the lower bounds can be found in Appendix D.
We now show how any deterministic online learning algorithm using the restricted ERM can be simulated using the weak consistency oracle, at the cost of increasing the number of oracle calls by O In particular, this applies to the ERM-based algorithms of [AAD*23 23, KS24].
Theorem 3.3 (Reducing Online Learning with Weak Consistency to Online Learning with "Restricted" ERM) Consider any deterministic online learning algorithm that only has access to the restricted ERM oracle. Furthermore, suppose that at each timestep t, for any function f returned by the oracle, the algorithm evaluates f only on the points T2,422.....2 If this algorithm makes at most f(T) mistakes and uses at most g(T) oracle queries over T rounds, then there exists an algorithu that uses the weak consistency oracle and makes most f(T mistakes using at most T g(T) queries.
The proof is provided in Appendix E. As consequence, we obtain the following result via the results in [AAD*23 KS24J.
Corollary 3.4 There exists a learning algorithm that makes T 20(du)) weak consistency oracle calls with 20(1r)) mistakes in the realizable setting.
Finally, we study online learning of partial concept classes. Partial concepts [AHHM22] are concepts that may be undefined on certain parts of the domain. These concepts are particularly useful for modeling data-dependent assumptions, such as the margin of the decision boundary. Recently, [DG24] showed that partial concepts can be learned in the (offline) PAC setting with the weak consistency oracle. Here, we show that such a result is impossible in the online setting, even with the ERM oracle, let alone with the weak consistency oracle. The proof provided in Appendix
Theorem 3.5 (Lower Bounds for Online Learning of Partial Concepts with ERM Oracle) There exists a family F of partial concept classes of Littlestone dimension 1, where any algorithm that makes a finite number of queries will have S!(T) mistakes.
4 Transductive Online Learning
In this section, we study the transductive online setting with oracle access, where the main goal is to
leverage the additional information given to the learner, the set of instances ø1, ......,.2 Fr at the start of the interaction, in order to reduce the number of mistakes or regret. The proofs for this section are provided in Appendix G.
First, we show that it is possible to recover labelings consistent with the concept class on the given achieve the optimal
instances " Ey using the weak consistency oracle. With this step, number of mistakes in the realizable setting and optimal regret in the agnostic setting.
Lemma 4.1 (Identify Labeling with Weak Consistency Calls) For class C C {0, 1}x, X let dvc be the VC dimension of C. Using the weak consistency oracle, one can recover all the concepts queries.
using O ((22]vve+)
Theorem 4.2 (Upper Bounds for Transductive Online Learning with Weak Consistency Oracle) Consider any family F of concept classes with VC dimension dyc- There exists an algorithm that uses at most O(Idve+1) weak consistency queries and obtains optimal mistake bounds for transductive online learning (known to be upper bounded by min dr.,, dvc log T T)), and also obtains optimal regret (known be upper bounded by Ö(vT min(dr.D, dyc log T)))
On the other hand, we establish the following two lower bounds. The first shows that limiting the learner to O(T) weak consistency queries is not sufficient for transductive online learnability, and the second shows that restricting O(T) ERM queries results in a mistake bound that exponential in the Littlestone dimension.
7

---

Theorem 4.3 (Lower Bound for Transductive Online Learning with Weak Consistency Oracle Randomized Algorithms) Consider any family F of concept classes of the form C C (0. 10.1)* where the family F has the property that for every labeling function f: {01, ,,,,,,,,,.....................,, there exists some concept class C E F and some concept E C such that c(ze) = f(z)) for all t E [T' (i.e., all 2 possible binary labelings of the sequence x are captured by the family F). For T 2 100, any (possibly randomized) algorithm that makes at most T/20 queries to the weak consistency oracle will incur an expected mistake bound of least T /200.
{0, 1}.
In particular, this theorem holds for general classes like Littlestone classes, and also for special families of classes, including thresholds, k-intervals, and d-Hamming balls (see the next section).
Proof sketch To establish the lower bound, we consider the uniform distribution over all 2 possible concept-class pairs permitted by family F. For any deterministic algorithm making at most 2/20 queries, we represent its execution as binary decision tree where: (i) the root contains all 2 possible concepts, (ii) internal nodes represent either oracle queries or predictions, and (iii) prediction nodes use the majority label strategy.
The expected number of mistakes plus queries equals the expected number of oracle splits and prediction mistakes on a random path from root to leaf. Transforming our tree to have a single "cost edge" to the smaller subtree at each node. We analyze the expected cost using entropy arguments. With entropy (() = ' bits, and applying the chain rule, the entropy can be expressed as the expected sum of binary entropy values h(p(v)) along paths from leaves root, where p(v) is the fraction of leaves below node's 's smaller child, and h(x) = -x logg (z) (1 z) log2(1 x). Defining a node as "balanced" if least 0.2 of its leaves fall under its smaller child, entropy analysis
shows there must be (?(T) balanced nodes in expectation along random path. Each balanced node
contributes a constant fraction to the expected cost, yielding a lower bound of S?(T), which gives us the claimed T/20 222 lower bound.
Theorem 4.4 (Lower Bound for Transductive Online Learning with ERM Oracles Determinis- tic Algorithms) Let F be the family of all classes with Littlestone dimension dLD- For T 2dD++1 when having access to the ERM oracle, if fewer than 2/2 queries are made, at least 2dLD - mistakes will be made.
We next study specific families of concept classes, achieving stronger results than in the general case, especially using randomized algorithms.
4.1 Thresholds, Intervals, and Hamming Balls
We start with the family of thresholds. For set X, we consider the family of classes
F = [C=] < is a total ordering over X), where each C- is the threshold class corresponding to the ordering <. Specifically, C- = fcz= : E X), where (x) = I[x 3 2]. When restricted to T points I1, .Z...... Fr,, the class C=1f21, 22, ..... Fr forms a threshold class over these T points, which
has Littlestone dimension [T)] ]. Our analysis focuses on both deterministic and randomized algorithms with weak consistency and ERM oracles.
Theorem 4.5 (Upper Bounds on Transductive Online Learning of Thresholds) Consider trans- ductive online learning where F is the family of threshold classes. The following results hold:
1. There exists deterministic algorithm that makes O(T log T) calls the weak consistency oracle and incurs at most Oloog T) mistakes.
2. There exists randomized algorithm that makes O(T) calls in expectation to the weak consistency orucle and incurs at most Oloog T') mistakes.
3. There exists a deterministic algorithm that makes O(T) calls to the ERM oracle and incurs at most Olog T') mistakes.
4. There exists a randomized algorithum that makes at most Ollog T) calls to the ERM oracle in expectation and makes most Ollog T) mistakes.
We outline the proof of the last case, the full proof is in Appendix H.I.
8

---

Proof sketch The key observation is that when randomly sampling two points from the uncertainty region and running ERM (with one point labeled 0 and the other labeled 1), with constant probability, the oracle assigns label 0 to least 1/3 of the points and label algorithm predicts according to this labeling. When a mistake occurs, the uncertainty region shrinks by constant factor, and we resample to generate new labeling for the reduced region. Since the uncertainty region shrinks by a constant factor (at least 1/3) with each mistake, we need at most (log T') mistakes to reduce the uncertainty region to a single point. Each mistake requires only constant number of queries in expectation (to get "balanced" partition), leading to a total of (log T) ERM oracle calls in expectation.
at least another 1/3. The
We proceed to analyze another canonical family of concept classes: k-Intervals. For a set X, we consider the family of classes Fin,k = =. 3 is total ordering over X),, where each Cin. contains concepts defined by at most k intervals under the ordering 3. Formally, for any total ordering I on X, and any collection of at most &o disjoint intervals Z1, 22:.... . Zmo where m S & and each Zi {x X a; 3 x 3 b.}
for some a;, b, E X, we define the concept as follows:
{
if E Z; for some E (1,2,...,m),
V7......... 2m
(x) 7m
otherwise.
This class has VC dimension 2k and Littlestone dimension Ol log T). is known that this class has VC dimension 2k; and the class defined on 7 points has Littlestone dimension at most T.
Theorem 4.6 (Upper Bound on Transductive Online Learning of k-Intervals with Weak Con- sistency Oracle Randomized Algorithm) Consider transductive online learning with the family Fin,k- There exists randomized algorithm that makes O(TS. 22k) calls to the weak consistency oracle expectation and makes at most O log T) mistakes.
Proof sketch One key observation is that for any 2 points 21 22 exists exactly one non-realizable labeling, corresponding to assigning label (i mod 2) to 2,. This fact can be used to test with high probability whether point 2 is an extreme point of the ordering- repeatedly sample 2k other points, and if the label of z is consistently 1 for the non-realizable labeling across all samplings, then it lies on an extreme end of the threshold with high probability (after O(T) samplings and 226++1 weak consistency oracle queries).
22k+1 X, there
We apply this test to all points to identify the two endpoints of the threshold (requiring at most O 22k+11 queries). We then designate one extreme as the "minimum" and recurse (at most T times), yielding an upper bound of O 22k) for the total number of queries. Since the Littlestone dimension is Ok log F) (and the VC dimension is (k))), we can run either SOA or the halving algorithm to achieve the Oog T) mistake bound.
We also study the class of d- d-Hamming Balls, which has Littlestone and VC dimensions equal to d. We show that an algorithm can make at most 2d mistakes using just single ERM query. Furthermore, we show that the optimal mistake bound of d can be achieved with 2d+1 queries. Combined with the result in Theorem 4.6, this suggests that the optimal mistake bound can be achieved for general transductive online learning using ((ddv))) queries, where C is a constant independent of the class, possibly by a randomized algorithm. See Appendix H.3 for more details.
5 Discussion
In this paper, we studied the power and limitations of various oracles in online learning settings. In the transductive setting, there remains gap between our general upper bound using deterministic algorithms (Theorem 4.2) and the improved performance of our randomized algorithms for special cases (Theorems 4.5 and 4.6). This motivates the following open problems:
Given a family of classes F with Littlestone dimension dLD and VC dimension dyc, does there exist a randomized algorithm that uses at most (0(dvc)) queries and achieves (dI.)) or Oldvc log expected mistakes, for some constant C independent of the class?

---

Are randomized algorithms provably more powerful than deterministic ones for online learning with oracles?
An additional interesting direction is to extend our oracle-based framework to more general tasks, such as online multiclass classification and regression. In particular, it would be natural design oracle-efficient algorithms for these settings, analogous to our results for the binary case. Another open question is whether the current oracle complexity bound of 722 for agnostic online learning with an ERM oracle can be improved, potentially yielding more efficient algorithms in the worst-case scenario.
Our analysis thus far assumed a worst-case adversary. A relevant extension is to consider smoothed adversaries adversaries with restricted power achieved by slight randomization in their choices. For example, Haghtalab et al. (2022) [HHSY22] developed the first oracle-efficient algorithm for online learning under smoothed-ad adversary model, which constrains the adversary draw each instance from a distribution of bounded density (thereby interpolating between stochastic and adversarial regimes). Block et al. (2024) [BRS24] further showed that, in such a smoothed setting, can attain regret the order of Ō ((/comm(FFF
T) (with matching upper and lower bounds) using an ERM oracle. Here comp(F) denotes the standard PAC-learning complexity of the class F (e.g. VC dimension). Notably, Block et al.'s result is limited to the squared loss; extending their analysis to other loss functions (e.g. general convex losses) remains an interesting direction for future work. Finally, another avenue worth exploring is the of weaker oracle models in conjunction with smoother adversaries. For instance, one could investigate whether a weaker consistency-based oracle (as opposed full ERM oracle) is sufficient to achieve low regret under smoothed adversarial conditions, potentially reducing the oracle complexity while still leveraging the adversary' 's restricted power.
Acknowledgments
Idan Attias is supported by the National Science Foundation under Grant ECCS-2217023, through the Institute for Data, Econometrics, Algorithms, and Learning (IDEAL).
References
[AAD* *23] Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, and Maxwell K Fishelson. Online learning and solving infinite games with an erm oracle. In The Thirty Sixth Annual Conference on Learning Theory, pages 274-324. PMLR, 2023. 2, 3, 5, 6, 7, 21, 28
[ABED+21] Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. In Proceedings of the 53rd annual ACM SIGACT symposium theory of computing. pages 447-455, 2021. 2
[AHHM22] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. theory of pac learnabil- ity of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658-671. IEEE, 2022. 7, 2,21,25 28
[AHM22] Idan Attias, Steve Hanneke, and Yishay Mansour. A characterization of semi-supervised adversarially robust pac learnability. Advances in Neural Information Processing Systems, 35:23646-23659 2022. 29
[AKM22] Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for adversarially robust learning. Journal of Machine Learning Research, 23(15)):1-31, 2022. 29
[Ang88] Dana Angluin. Queries and concept learning. Machine learning, 2:319-342, 1988. 22
[BDKM97] Shai Ben-David, Eyal Kushilevitz, and Yishay Mansour. Online learning versus offline learning. Machine Learning, 29:45-63, 1997. 1, 6, 22
10

---

[BDPSS09] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In COLT, volume 3, page 1, 2009. 2
[BL98] Peter L Bartlett and Philip M Long. Prediction, learning, uniform convergence, and scale-sensitive dimensions. Journal of Computer and System Sciences, 56(2):174-190, 1998. 29
[BRS24] Adam Block, Alexander Rakhlin, and Abhishek Shetty. On the performance of empiri- cal risk minimization with smoothed data. In The Thirty Seventh Annual Conference on Learning Theory, pages 596-629, PMIR, 2024. 10, 21
[CBL06] Nicolo university press, 2006.
and Gábor Lugosi. Prediction, learning, and games. Cambridge
[CBS13] Nicolo Cesa-Bianchi and Ohad Shamir. Efficient transductive online learning via randomized rounding. Empirical Inference: Festschrift in Honor of Vladimir N. Vapnik, pages 177-194, 2013. 1, 22
[CHHH23] Tsun-Minn Moun-Ming Cheung, Hamed Hatami, Pooya Hatami, and Kaave Hosseini. Online learn- ing and disambiguations of partial concept classes. arXiv preprint arXiv:2303. 17578, 2023. 29
[CHMS25] Zachary Chase, Steve Hanneke, Shay Moran, and Jonathan Shafer. Optimal mistake bounds for transductive online learning. arXiv preprinl arXiv:2512. 2025. 2, 22
[DG24] Constantinos Daskalakis and Noah Golowich. Is efficient pac learning possible with an oracle that responds. In The Thirty Seventh Annual Conference on Learning Theory, pages 1263-1307. PMLR, 2024. 2, 3, 6, 21
[DH++20] +20] Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan. Oracle-efficient online learning and auction design. Journal of the ACM (JACM), 67(5):1-57, 2020. 21
[FL98] Moti Frances and Ami Litman. Optimal mistake bound learning is hard. Information and Computation, 144(1):66-2,, 1998. 2, 21
[FR20] Dylan Foster and Alexander Rakhlin. Beyond ueb: Optimal and efficient contextual bandits with regression oracles. In International conference machine learning. pages 3199-3210. PMLR, 2020. 21
[HBD23] Niki Hasrati and Shai Bev-David. On computable online learning. In International Conference on Algorithmic Learning Theory, pages 707-725. PMLR, 2023. 2, 21
[HHSY22] Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang. Oracle-efficient online learning for beyond worst-case adversaries. arXiv preprint arX1v:2202.08549, 2022. 10, 21
[HK16] Elad Hazan and Tomer Koren. The computational power of optimization in online learning. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 128- 141, 2016. 21
[HMS23] Steve Hanneke, Shay Moran, and Jonathan Shafer. trichotomy for transductive online learning, Advances in Neural Information Processing Systems, 19502-9999999 2023. 6, 22
[HP22] Lunjia Hu and Charlotte Peale. Comparative learning: A sample complexity theory for two hypothesis classes. arXiv preprint arXiv:2211.09101, 2022. 29
[HRS24] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adversaries. Journal of the ACM, 71(3):1-34, 2024. 21
[HRSS24) Steve Hanneke, Vinod Raman, Amirreza Shaeiri, and Unique Subedi. Multiclass transductive online learning. arXiv preprint arXiv:2411.01634 2024. 1, 22
11

---

[JSI+15] Michael A Jackson, Doug Smith, Peter Jantsch, Christina Scurlock, Chelsea Snyder, Eric Fairchild, Robin Mabe, and Emma Polaski. Rectified simplex polytope numbers. arXiv preprint 1.X.v:1507.01644 2015. 39
[KK05] Sham Kakade and Adam T Kalai. From batch to transductive online learning. Advances in Neural Information Processing Systems, 18, 2005. 1, 22, 30
[KS24] Alexander Kozachinskiy and Tomasz Steifer. Simple online learning with consistent oracle. In The Thirty Seventh Annual Conference on Learning Theory, pages 3241- 3256. PMLR, 2024. 2, 3, 4, 6, 7,
[KV05] Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, (13):291-307) 2005. 21
[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, 1--20899-20822 2022. 29
[Lit88] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear- threshold algorithm. Machine learning, 2:285-315 1988. 2, 22, 30
[Lon01] Philip M Long. On agnostic learning with (0,*, 1)-valued and real-valued hypotheses. In Computational Learning Theory: 14th Annual Conference on Computational Learn- ing Theory, COLT 2001 and 5th European Conference on Computational Learning Theory, EuroCOLT 2001 Amsterdam, The Netherlands, July 16-19, 2001 Proceedings 14, pages 289-302. Springer, 2001. 21, 29
[Man22] Pasin Manurangsi. Improved inapproximability of ve dimension and littlestone's dimension via (unbalanced) biclique. arXiv preprint 4rX1v:221 2022. 2
[MR17] Pasin Manurangsi and Aviad Rubinstein. Inapproximability of ve dimension and littlestone's dimension. Conference on Learning Theory, pages 1432-1460. PMLR, 2017. 2
[MRT12] Mehryar Mohri, A Rostamizadeh, and Talwalkar. Foundations of machine learning, ser. adaptive computation and machine learning, 2012.
[SKS16] Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire. Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning, pages 2159-22 209--1100 268. PMLR, 2016. 6, 21, 22
[SLX22] David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability. Mathematics of Operations Research, 1703):1904-199) 2022. 21
[SS+ 12] Shai Shalev-Shwartzee al. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 4(2):107-194, 2012. 1
[SSBD14] Shai theory to algorithms. Cambridge university press, 2014. 1, 30
and Shai Ben-David. Understanding machine learning: From
[Vap82] Vladimir Vapnik. Estimation of dependences based on empirical data: Springer series in statistics (springer series in statistics), 1982. 22
[VC71] VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264, 1971. 2, 22
[VC+74] Vladimir Vapnik, Alexey Chervonenkis, et al. Theory of pattern recognition, 1974. 2, 22
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and in Section 1.1 of the introduction, we give a detailed description of the claims and results we prove in the paper as a technical overview.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper mentions that the ERM oracle that is defined, which is considered in several of the upper and lower bounds this paper, is weaker than the "agnostic" ERM oracle. Additionally, we present open problems to strengthen some of our gaps, for example, upper and lower bounds for transductive online learning with oracles.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In every theoretical statement, we characterize the assumptions and conditions of the statement and then we give a proof.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is completely theoretical paper so there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
specific model and empirical evaluation, may
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

5. Open access to data and code
Question: Does the paper provide open to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This is completely theoretical paper so there are no experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines battps://nige cc/
publ icc gu des Sulem s.s LonPolicy for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (ht //nips. cc/ httpp//blcccccc//ppp//pp/cccacct ceooliccguiiie /t///uuiissss des Code Submi as ooooonooiooo oomPllccy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
This is completely theoretical paper so there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
This is completely theoretical paper so there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is completely theoretical paper so there are no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 'tttt make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /neurips.....// cc wwtppbcccc/cccccccaiiiiicicccaaa
Answer: [Yes]
Justification:
The research in this paper conforms to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Since this a learning theory paper focused on characterizing learnability and complexity of learning problems, we do not see any immediate negative social impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: This is completely theoretical paper there are no datasets experimental models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This is completely theoretical paper don't have any code, data, models.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
17

---

If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, papersw swwi thcode. com / da a setss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This is a completely theoretical paper so we don't 't have any code, data, or models.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not conduct any crowdsourcing experiments or research with human
subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: We do not conduct any crowdsourcing experiments research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
18

---

Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification: The paper does not any large language models as part of its research methodology or core methods.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //neuripsss cttpripeeccccctteeecsess/// 2025/ LLM) for what should should not described.
19

---

Appendices
Additional Related Work
B Preliminaries
22
Mistakes-Oracle Calls Pareto Frontier
24
C.1 Pareto Frontier for Online Learning with ERM for Littlestone Classes
24
C.2 Pareto Frontier for Transductive Online Learning with ERM for Littlestone Classes
25
Online Learning with ERM Oracle: Lower Bounds for Realizable and Agnostic Settings
25
D.I ERM Oracle Lower Bound for the Realizable Case
25
D.2 ERM Oracle Lower Bound for the Agnostic Case
27
Online Learning with Weak Consistency Oracle: Upper Bounds
28
F Online Learning with ERM Oracle: Lower Bounds for Partial Concepts
28
Transductive Online Learning: General Concept Classes
30
G.1 Upper Bounds with the Weak Consistency Oracle
30
G.2 A Lower Bound with the Weak Consistency Oracle
30
G.3 A Lower Bound with the ERM Oracle
33
H Transductive Online Learning: Thresholds, Intervals, and Hamming Balls
35
H.I Thresholds
35
H.2 Intervals
38
H.3 Hamming Balls
40
20

---

A Additional Related Work
Fracle-Efficiet Online Learning. Oracle-efficient methods establish a powerful framework for addressing the computational challenges of online learning. This provides an alternative to the fact that standard online learning can be computationally intractable [FL98, HBD23]. Assos et al. [AAD* 23] and Kozachinskiy et al. [KS24] studied the online learnability of concept classes with finite Littlestone dimension using the ERM oracle. In addition, the partial-information setting, specificalll contextual bandits, has been explored using regression oracles [FR20, SLX22] and the ERM oracle [SKS16].
Theoretical limitations of this approach have also been investigated. Hazan and Koren [HK16] showed that, for certain finite concept classes C, any oracle-efficient online learner must make at least 22( [C]) calls powerful optimization oracle (an agnostic ERM oracle) achieve sublinear regret in the fully adversarial proper-leaming setting; they also give a matching Ö( O(VIC)) upper bound. Since the Littlestone dimension satisfies Ldim(C) V logg [C] for finite classes, this implies an exponential dependence of total runtime on the Littlestone dimension. Our results sharpen and generalize this picture: we give lower bounds in both the realizable and agnostic regimes, and for more general classes parameterized by VC / Littlestone dimension. Rather than targeting mere sublinear regret, we identify conditions under which stronger, dimension-dependee for any oracle-efficient learner-e.g. g., (((2LD) (realizable) and 2(VVT 2 (agnostic). When specialized to finite classes with |C| = 2duD, both lines of work exhibit exponential dependence on dI.D (since VCJ = 2d.a/22, while our results additionally showed that even in the realizable case the required computation is exponential in dLD (and in fact cannot be done in finite number of queries). Altogether, these findings underscore that optimization oracles remove optimization difficulty but not the information-theoree hardness of fully adversarial online learning.
rates are unattainable
Additionally, Kalai and Vempala [KV) and Dudík et al. [DHL++20] developed oracle-efficient algorithms for various online learning problems (e.g., combinatorial decisions and auctions) by leveraging structure or randomness (perturbed-leader methods), but their techniques assume an efficient oracle for the specific problem at hand and do not apply to arbitrary concept classes.
Several works have identified structural conditions that enable oracle-efficient online learning despite the general lower bounds. Dudík et al.[DHL.22)) 20] studied the conditions under which oracle-efficient algorithms can succeed, and Haghtalab et al. [HHSY22] provided such algorithms for online learning with smoothed adversaries, introduced in Haghtalab et al. [HRS24]. Haghtalab et al. (2022) gave the first oraclc-efficient online learner in the smoothed adversary model, achieving regret bounds O(VTT d/o) that depend only on the hypothesis class's VC dimension d and the smoothness parameter a. Their result shows that when the adversary is constrained to draw instances from o-smooth distribution (i.e., no individual example can have too large a probability mass), online learning becomes computationally as easy offline learning for any VC class. More recently, Block et al. [BRS24] considered the realizable case under smooth adversaries and show that even a simple repeated-ERR strategy can attain no-regret. In particular, they proved that if the marginal distribution is o-smohhh, then empirical risk minimization achieves sublinear error on the order of (C//ompp)) -)), where comp(F) is the standard PAC-Icarning complexity of the class. These works underscore that smoothness assumptions, now widely used as a testbed for the robustness of impossibility results can circumvent the brittle worst-case constructions, enabling efficient online learning of VC classes in practice. However, studying the models for general VC Littlestone classes is necessary for gaining more fundamental insights into the computational- -tatisssiia tradeoffs that govern all concept classes. Studying general classes reveals which properties are universal versus which depend on special structure. While [HHSY22] and [HRS24] establish oracle-efficient algorithms under smoothness assumptions, oracle efficiency in the fully adversarial setting has yet to be resolved.
PAC Learning with Weak Oracles. ERM has long been a foundational principle in PAC learning. particularly for binary classification, where the sample complexity is characterized by the VC dimension. However, in settings like learning partial concepts, while PAC learning is possible, it can be shown that uniform convergence, which analysis of ERM depends on, does not hold [AHHM22, LonO1]. Recently, Daskalakis et al. [DG24] introduced a weaker form of oracle, the weak consistency oracle, that suffices for learning any binary concept class with a sample complexity
21

---

that scales polynomially (roughty eubically) in dyc. where dvc is the VC dimension. They also extend this framework to multiclass classification, regression, and partial concept classes. Their work suggests that such weak oracles could be a powerful abstraction in PAC learning, and raises the question of whether similar approach can succeed in online learning, a question we explore in this paper.
Online and Transductive Online Learning. Online learning, as introduced by Littlestone [Lit88] and studied in related query models by Angluin [Ang88], is characterized by worst-case mistake bounds determined by the Littlestone dimension. The Standard Optimal Algorithm (SOA), also due to Littlestone [Lit88], achieves minimax-optimal guarantees in this model and, such, plays central role in the theory of online binary classification.
A related but distinct model is transductive online learning, where all unlabeled instances are revealed in advance, but labels are queried sequentially. This setting was implicitly studied in earlier work on "offline learning" [BDKM97]. The transductive online model [HMS23, HRSS24] lies between batch PAC learning and traditional online learning, and often admits more favorable learning guarantees than the latter due to the known instance sequence. Hanneke et al. [HMS23, HRSS24] provided a trichotomy characterization and multiclass extensions for this setting. Additionally, Chase et al. [CHMS25] provided a lower bound of 52( ((Vddr VdI.)) mistakes for transductive online learning, which holds for all concept classes, and is tight (in the sense that for every integer d, there exists class with Littlestone dimension for which some algorithm can achieve O(vd) mistakes).
Batch Transductive Learning. Batch Transductive Learning is the foundational setting introduced by Vapnik [VC+74, Vap82], where both labeled training data and unlabeled test instances are available at training time, and the goal is to predict labels only for the given test set rather than learn a general hypothesis. Kakade and Kalai [KK05] established connections between batch and transductive online learning, showing how efficient batch learning algorithms can be converted to efficient transductive online algorithms with regret scaling as (TT3/4) over T rounds. Besa-Bianchi and Shamir [CBS13) 13] improved upon this result, achieving the optimal O(vT) regret rate for wide class of losses using a novel randomized rounding approach.
B Preliminaries
Definition B.1 (Littlestone Dimension [Lit88) Given a concept class C, a d-depth Littlestone tree is a set of (Jyy y E d0,d-11 1d] C X (interpreting yd = {0), where for all y/: -2.-.... Ud E Y, there's E C such that (c(=)), c( ), c(Mgua), ... c( (( )) (31- 1/..... Vd). The Littlestone dimension of is the maximum n such that there exists a Littlestone tree of depth n.
Definition B.2 (VC Dimension [VC71] Given a concept class C, a set of n points T1, In C X c C} = 10. The VC dimension of C is the largest n such that there exist n shattered points in X.
is shattered if ((c(z))....,co
Transductive Online Learning with Oracle Access. The learning protocol is a sequential game between a learner and an adversary. Let C c {0. 1)x* be concept class, where X' is the instance space and f0, 1} is the label space. Let be family of concept classes (e.g., classes with finite Littlestone dimension) such that C is an unknown concept class from F chosen by the adversary. Suppose the learner only has oracle access to C via an oracle O. First, the adversary selects a concept class C E F and a sequence of instances æ1.7 = (I1, , (2,.....777 IT) E XT, The sequence x is revealed to the learner and the sequential game proceeds for T rounds, as follows. For each & E [T]:
1. The learner selects distribution A, E A((O, 13), and predicts d1. ~ A.-
2. The adversary reveals y: E {0, 1) and the learner suffers a loss T[e. + vel.
We define Vı.r E {0, 1)T the realizable setting, the adversary is subject to the constraint that the sequence (I1, y1),.... .., (Zt, Ve)
T as the sequence of labels chosen by the adversary corresponding to 21:7. In
'There exist variants of this setting. One variant involves the adversary revealing a set to the learner opposed sequence see [SKS16]. Our results hold for that setting well.
22

---

Similarly, Q(A, O(C), 21.r, c) is the total number of queries, defined as is realizable by C, meaning that there exists C satisfying c(xa) ys for all [T]. The performance of a learning algorithm A is measured by two metrics, the number of mistakes and the number of oracle queries. The mistakes are defined follows:
O(C), Σ T(u + c(xx))-
The worst case number mistakes of learning algorithm A defined as
(AA sup sup sup O(C) CEF aEC mTTETT
Q(A,T) T) = sup sup sup B(Q(4,0(C), CEF aEC F.TEXT
Here, the expectation is over the randomness of the algorithm.
We assume that the adversary is oblivious with respect to the choice of concept class C, target concept c, and instance sequence æ, meaning that these are fixed advance and do not depend on the learner's predictions or queries.
In the agnostic case, the sequence (æ1:7, y1:r) is no longer constrained be realizable by C, and the measure of performance is the regret, defined as
T inf CEC t=1
Reg(A, (2IT, =
Σ Ii
+ vil
Σ
[[((x)) # vol
Define the worst case regret of the algorithm A as
(eg(A,T)
sup sup CE (1
E(Re(AA,
and Q(A, 7) the agnostic case defined as the worst-case total number of queries, over C E F and (z,z) (X x 10..)
23

---

C
Mistakes-Oracle Calls Pareto Frontier
C.1 Pareto Frontier for Online Learning with ERM for Littlestone Classes
MistakessOracce Calls Pareto Frontier: Online Learning with ERM
Oracle Calls
Yes
No
Unlenwnn
2/u
2?Vaal
Regret-Oracle Calls Parcto Frontier: Agnostic Online Learning with ERM
Orocle Calls
No
Unknown
Regret
( (Teglryan
24

---

C.2 Pareto Frontier for Transductive Online Learning with ERM for Littlestone Classes
Mistakes-Oracke Calls Pureto Frontier: Transductive Online Learning with ERM
Orocle Colls
2
Yes
Unknown
((3))
g0itun
No
Mistokes
Optimal
24L0
min(dnn. dvc log(2")
Regret-Oracle Calls Parelo Frontier: Agnostic Transductive Online Learning with ERM/Weak Consistency
Oracle Colls
Yes
Unkoowwn
Regnet
Optiall
$ miin// diye lggT))
D Online Learning with ERM Oracle: Lower Bounds for Realizable and Agnostic Settings
D.1 ERM Oracle Lower Bound for the Realizable Case
We now cover the details for proving Theorem 3.1, the lower bound 2 mistakes for online learning in the realizable setting.
Theorem 3.1 (Lower Bound for Online Learning with "Agnostic" ERM Oracle) Let F. be the family of classes with Linlestone dimension d1, Then, any randomized algorithm that makes a finite number queries to the ERM oracle incurs ((20LD) expected mistakes.
25

---

Proof We prove this by constructing hard instance where any algorithm using finite number of ERM queries must make (2(24L) expected mistakes.
First, let T 2dh and set = [0, 1|T-!. We'll define family of concept classes parameterized by two vectors:
2 (21 (21....; 21-1) [0, _]T_1, which defines the geometry of our construction
(bi....,byy by) {0, 13", which defines the labeling pattern
For each (z, b), we define T" special points in A::
31 (0, 0, .0)
(=1, O, 0) 33 (31, 22, .,...:0)
FT (21, 22: ....... 24
These points partition X' into "cells" Cl.... Cr. where:
C₁ contains all points (W1, WT-1) where w1 # 21
C2 contains all points where w1 but W2 +
C₁ contains all points matching the first i - 1 coordinates of but differing at the i-th coordinate
Cr contains only the point zT
Now we define our concept class C. as the set of all functions that:
1. Label all points in the same cell consistently
2. Assign labels cells according threshold function determined by
The threshold function determined by b is determined as follows. b determines an ordering over the points Ti..... .T in the following sense. If 61 O, then æ the leftmost point in the ordering, and if b = 1. then is the rightmost point in the ordering. Keep repeating for b2...., by to construct the rest of the ordering.
The adversary works as follows:
1. Choose uniformly random from [0, 1|T-1, and construct #1, 22,42.... ......,ry from 2.
.2....,
2. Choose b uniformly random from {0, 1)
3. Set the target concept such that c(x;) = b, for all i.
4. Present instances æ1, 22, in order
It's sufficient to show that any algorithm ineurs 2(T) expected mistakes by the probabilistic method, this will imply that any algorithm incurs Q(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 æ1, which is in C₁. After finitely many ERM queries, the probability that any queries of the learner will be some point C, for some 1 will be zero this is because 2; values are chosen uniformly at random from [0. 1], so the probability of querying any specific real value is zero. Thus, with probability all the points in all the queries of the learner will be in C1. The "agnostic" ERM oracle will return concept that minimizes the error over the query points. Since the ERM oracle can return any function that minimizes this error, the adversary can choose which of these error-minimizing functions to return. Specifically, the adversary will select an error-minimizing function that provides no information about the labels of points not yet queried, especially about Z1. Thus, the adversary choose the ERM to label all points in X' as
26

---

majority vote over the labels of the points in the query. Since by is chosen uniformly random from {0, 1 and the learner has gained no information about this choice, the learner incurs mistake with probability 1/2.
For the tth timestep, the learner is given 2t, which in C.. After finitely many ERM queries, the probability that any queries of the learner will be some point C2 for some will be zero. The agnostic ERM could return any function that minimizes the error over the points in the query. Since the points in the query were only among C1. C....., Ct, the adversary to label all points in Ct...., Cr the same, giving the learner no information about the locations of Ce+1.-.., Cr, about by Thus, the learner incurs mistake with probability 1/2 the /th timestep.
choose the ERM
Thus, over T timesteps, the expected number of mistakes is 7/2, giving the desired lower bound of ((24,)) expected mistakes.
D.2 ERM Oracle Lower Bound for the Agnostic Case
The lower bound for the realizable case in Theorem 3.1 can be extended to the agnostic case, with regret that scales with VT.
Theorem 3.2 (Lower Bound for Agnostic Online Learning with "Agnostic" ERM Oracle) Let F be the family of classes with Littlestone dimension dLD. Then, any randomized algorithm that makes finite number of queries to the ERM oracle incurs (VVTA expected regret.
Proof We extend the construction from Theorem 3.1 to the agnostic setting.
Let T' 20LD and set [0, 1 Choose a parameter S such that T ST', where S is
sufficiently large for concentration bounds to apply.
We define the same special points as in the previous proof:
i (0, 0, 0)
f2 (=1, 0, ...,..... 0)
83 = (21, 22, 0,. .,....0)
3T (31, 22. 2T
E [0, 1] chosen uniformly at random. These points partition X' into T' cells CI,...,CC Cr as defined earlier.
where :
The adversary works follows:
1. Choose z uniformly at random from [0, 1 and construct f .2......................... ST.
2. For each 1..... and j 1,..., .....,,,,,, present instance Z(i- ()S+) 2z.
3. Generate labels y1, 1/2 yr i.i.d. uniformly from {0, 1).
Let b,, b. by be the majority of the labels in each phase (without loss of generality, break ties to favor 1s), and let the concept class be C..b defined in the last section.
Any algorithm will have expected error T/2 on this distribution (since it will make mistake on random label with probability 1/2).
Now consider the performance of the best hypothesis in C2.b- This hypothesis assign optimal label to each cell C; based on the majority of labels seen in phase i. For each phase consisting of S copies of ã.. let m, denote the number of mistakes made by the best hypothesis. By standard concentration bounds for the binomial distribution, we have R[m,,] Sus ev/S for some constant
<> O)
Summing over all 7" phases, the expected total error of the best hypothesis is at most
T
T
T
T
cT'
T22....
2
20L0
2
27

---

Therefore, the expected regret of any algorithm that makes finite number of queries the ERM oracle over this distribution of sequences and concept classes least eVT2á.,, which is 52( ( T2 By the probabilistic method, for any algorithm makes a finite number of queries to the ERM oracle, there exists a fixed concept class and sequence (I1. y1)..... (Fr, Mr) such that the expected regret O( (T2())) ) as desired.
E Online Learning with Weak Consistency Oracle: Upper Bounds
The following theorem enables proving upper bounds for online learning with the weak consistency oracle, assuming the existence of an ERM-based algorithm satisfying certain assumptions.
Theorem 3.3 (Reducing Online Learning with Weak Consistency to Online Learning with "Restricted" ERM) Consider any deterministic online learning algorithm that only has access to the restricted ERM oracle. Furthermore, suppose that at each timestep t, for any function f returned If this algorithu makes
by the oracle, the algorithm evaluates f only on the points 21,22, at most f(T" mistakes and uses at most g(T') oracle queries over Ti' rounds, then there exists an algorithm that uses the weak consistency oracle and makes most f(I) mistakes using at most T g(T) queries.
Proof Let A be a deterministic online learning algorithm that uses restricted ERM oracle, makes at most f(T) mistakes, and uses at most g(T) oracle queries over T rounds. We will construct an algorithm A' that uses the weak consistency oracle and maintains the same mistake bound.
At each timestep i, algorithm A may make a query to the ERM oracle using the set { y1), (22) ..., (Zr-1, 1, 1). Let's denote by fa the function that would be returned by this ERM query. By assumption, A only evaluates fi points 21, 22,
Algorithm A' will simulate A as follows:
Let He be the set of functions returned by the ERM oracle in algorithm A up to timestep f.
For each function f E H:-1 that A would evaluate at point I;, algorithm A' needs to determine (xxx). To do this, A' will make one query to the weak consistency oracle: {(21, V1). (I2, ...,.... (It-1, 9t 9t-1), ). (z,, 0)}. }. If it returns "realizable", extend the function have value 0 2, and add have value 1 at and add it to He.
H.. If it returns "not realizable" extend the function to
For any new ERM query that A would make at timestep 6, A' needs to simulate this by finding function consistent with {(11 31), (22, 12), (11-1, 1)-1)) This can be done by using the weak consistency oracle to check all possible labelings of future points that A might evaluate.
The key insight is that algorithm A is deterministic and, by assumption, only evaluates functions points æ1, .,,..., I2 at timestep t. This means that the behavior of A depends only on the values of these functions these specific points, not their values for unseen points T2+1, ....,...--......... .y. -T.. Therefore, A' makes at most f(T) mistakes, just as A does. Furthermore, for each ERM query in A, A' makes most T weak consistency queries, A' makes at most T gT() weak consistency queries.
We can apply the above Theorem with the algorithm by [AAD+23] to get the following.
Corollary 3.4 There exists a learning algorithm that makes T 20(dLD) weak consistency oracle calls with 20(LD) mistakes in the realizable setting.
F
Online Learning with ERM Oracle: Lower Bounds for Partial Concepts
The idea of learning partial concept classes was formalized recently by Alon, Hanneke, Holzman, and Moran [AHHM22], who demonstrated fundamental differences from the learning of total concept
28

---

classes, for example, that ERM fails to learn partial concepts, even though the VC dimension still characterizes learnability. learning with partial concepts provides a natural framework for modeling data-dependent assumptions, such margin conditions or cases where the target function is only defined on subset of the input space.
Some of these ideas were previously studied implicitly in the context of regression [Lon01, BL98]. Partial concept classes have many applications, including adversarially robust learning [A M22, AHM22J, learning with fairesss constraints [HP22], multiclass classification [KVK22], and online learning [CHHH23].
Let a partial concept class C S {0, 1,* For E C and input x such that c(x) = *, we say that c is
undefined on z. The support of a partial concept X - {0. x) is supp(c) = {ar X c(z) + x). A sequence $ = ((x1, 311 ....., (Tim Dm)) )) is realizable by C if there exists E C such that c(T,) yi for all E [m] and x; E supp(c) for all E [m].
The Littlestone dimension of a partial class C is the maximum depth d such that there exists a d-depth Littlestone tree where for each path from root leaf, there exists some concept E C that realizes the path and is defined on all points along that path (see Definition B. for the definition of a Littlestone tree). The VC dimension of a partial class is defined as the maximum size of a shattered set S S N. where S is shattered by C if the projection of C on S contains all possible binary patterns: {0. 1)$ Cls.
Theorem 3.5 (Lower Bounds for Online Learning of Partial Concepts with ERM Oracle) There exists family FF of partial concept classes of Littlestone dimension where any algorithm that makes a finite number of queries will have ST(T) mistakes.
Proof Let X' [0, 1), Construct a family of partial concept classes F follows:
Letting z (=1, .2,...,,71. and {0, 13", define Cz,b as a collection of the functions C1 ......... CT where
(222)) = bj if <i (2(2)) bj
if =
cx(x== =
i & {21. 22 ,,.,,
The Littlestone dimension of C2,b is
The strategy the adversary as follows:
Choose and b (sample 2; uniformly from [0, 1] and uniformly from {0, 13 for all i).
At each timestep I, present point 2; = z, to the algorithm
At timestep f, when the learner makes a query to the ERM oracle, the learner won't discover any of the points among I++1 Zt+2. IT with probability 1, and thus, the queries will only be among points in X' - T142, (T.) J. If any points outside of (Iı,...,,TT) FT) the ERM oracle will return "not realizable" (since any target concept will return * on such points).
Thus, suppose the queries are all among points in {I1...., TT}. When the learner makes ERM queries on any subset of points from {21, .2,.... }1 there are always two valid extensions of the concept one where by = 0 and one where b = 1. This is because:
1. For any both e and c++1 agree 2y (both output by).
2. For 21 itself, e outputs 1 - b, while c++1 outputs b..
Since this is the case, the learner won't gain any information about by so the adversary will make mistake with probability 1/2 at each timestep since b, is chosen uniformly at random from (0, 1}. independently of the learner's 's prediction. Thus, over T timesteps, the expected number of mistakes is T/2, giving the desired lower bound of Q(T)) expected mistakes.
29

---

G
Transductive Online Learning: General Concept Classes
Here we present the details for upper bounds and lower bounds for transductive online learning on general concept classes.
G.1 Upper Bounds with the Weak Consistency Oracle
We first start with lemma which discusses a "preprocessing" step that the learner can choose to perform to gain knowledge of the concept class.
Lemma 4.1 (Identify Labeling with Weak Consistency Calls) For a class C C 10.1 let dvc be the VC dimension of C. Using the weak consistency oracle, one can recover all the concepts in C using O ((1)vce+)) queries.
Proof Let N |x Let X' be expressed as 21, .2. NN. Since C has VC dimension dyc, the number of distinct labelings it can realize on N points is O(Nvve) by Sauer's Lemma [SSBD14). far.
For each point 2i, where E [N]. check which lahelings consistent with the data Specifically, for each prefix (I1, B1)..... (ZL-1, 91-1) that has been determined to be realizable, we query the weak consistency oracle twice: once with the additional labeled example (z;, 0) and once with (zt, 1). We maintain a tree of realizable labeled prefixes, expanding it level by level.
At each level, each realizable prefix may branch into two new prefixes, depending on whether labeling I; with or is consistent. Since the total number of distinct full labelings is ((Náve), there are at most O(N Ndve) possible prefixes. Since each step involves up to two queries per prefix, the total number of oracle calls is at most ([Niv++1).
Theorem 4.2 (Upper Bounds for Transductive Online Learning with Weak Consistency Oracle) Consider any family F of concept classes with VC dimension dyc. There exists an algorithm that uses at most O(T weak consistency queries and obtains optimal mistake bounds for transductive online learning (known to be upper bounded by min dd.D, dvc log T)), and also obtains optimal regret (known to be upper bounded by Ö(vT min(deD; dvc T))).
Proof Let C be the unknown concept class. Consider CH (TT) [T]]. the class of C restricted to {x1..... TTr.. This class has VC dimension at most dyc. Apply this to Lemma 4.1 to get all realizable labelings using O(T weak consistency queries.
Once we have identified all realizable labelings on (TT online learning setting where the class is known. Thus, one can use any standard (non-oracle) transductive online learning algorithm to get a mistake bound equivalent to in the non-oracle setting, for example by using the SOA algorithm [Lit88] (to get an O(LLD) mistake bound) or a halving algorithm on the number of shattered sets [KK05] (to get an Oddyc log T") mistake bound).
}. we now in the transductive
G.2 A Lower Bound with the Weak Consistency Oracle
We prove a general randomized lower bound of ?(T') queries needed to attain o(T) regret for the setting with the weak consistency oracle. We express it via the following lemma.
Theorem 4.3 (Lower Bound for Transductive Online Learning with Weak Consistency Oracle Randomized Algorithms) Consider any family F of concept classes of the form C {0, 1
where the family F has the property that for every labeling function f {I1, B2...., + {0. 1}. there exists some concept class C E F and some concept
C such that c(xx) f(xx) for all
I. E [T] (i.e., all 2f possible binary labelings of the sequence x are captured by the family F). For T > 100, any (possibly randomized) algorithm that makes most T/20 queries the weak consistency oracle will incur an expected mistake bound of at least T/20.
Informally, with the weak consistency oracle, O(T) queries correspond to 2(T) mistakes for any concept class for any family of classes that capture all 2 labelings. Notice here that this allows us to have lower bound for general families of classes, including general Littlestone classes and
30

---

general VC classes. Additionally, by the conditions in the theorem, this lower bound holds for settings including those in Appendix H. (thresholds, k-intervals) and Appendix H.3 (d-Hamming balls).
To prove Theorem 4.3, make use of the following lower bound.
Lemma G.1 (Lower Bound for Binary Tree Costs) There exists a universal constant C such that the following is true. Given integer 10, construct any binary free, with labeled nodes such that the following conditions are satisfied:
The root node has value
For any node with value x strictly greater than 1, its two children have positive integer values y and z such that x = y + 2.
The depth of the tree is at most 1.05 (n)
For an internal node with children y and z, define the cost of the node be min(y, 2). Define the cost of the tree as the sum of the costs of the internal nodes. Then, the tree has cost 2 C (n).(n).
Proof Consider the random variable X, which is taken uniformly at random over all the leaves. The idea is to relate the entropy (X) the cost.
For each internal node v, define p(v) to be the fraction of leaves in its subtree that in the subtree of the smaller child:
p(e) mwn(me.. (cz)//
where ez and un are the left and right children of v. Additionally, let h(x) be the binary-entropy function (h(x)) - log, (1 2) log, z)).
By the chain rule of entropy, we can decompose (X) as follows. For the root node r, let X, be the random variable corresponding which side of the root X will lie (X, 0 if lies the subtree of the smaller child, and X, otherwise). The chain rule (H, 22) = H(2) + H (1)) gives that:
((X) H(X,) (XXXx)) h(((r) Bexx, [X =c]
= h(p(r) + ((r) 0) (X-
We can continue this decomposition recursively through the tree. At each internal node we get term h(p(o)) weighted by the probability that reaches node v, which is |o] Thus, we have:
|u| h(p(v))
H(X) Σ
internal
Equivalently, we can view this summation from the perspective of randomly chosen leaf. For each leaf I, let path(!) be the set of internal nodes on the path from the root to I. Then:
H(X) E
h(p(v)) (Epath()
Σ
Since X is uniformly distributed over the leaves, each leaf contributes equally to this expectation. Also the cost of the (divided by n)) is equal to
Σ v p(e) = Exxx
Σ p(u)
eEpath(1)
Consider a threshold and define node w to be unbalanced if p(w) < I, and balanced otherwise. For balanced nodes, we have h(p(v)) < 1, and for unbalanced nodes, we have h(p(v)) h(t). Let
31

---

b(T) and u(l) be the number of balanced and unbalanced nodes, respectively, the path from the root to leaf I.
Since 6(1) + (() - 1.05 (o) by the depth constraint, the above is at most:
xx~x(6(1) + (1.05 log2 ( b()))((t)
Setting logg n this and rearranging gives:
log, r0 - 1.05h(()) S Ei ((0)(1 1((1))
Ex_x [oxx)(([]]= 2 log2(n) (.05h(()
h(t)
Additionally, the cost divided by n is at least:
cost
E [t b(])
This is because each balanced node contributes at least to the cost ratio (by definition of being
balanced).
Combining these results gives that the cost is least:
cost 2 n loga 8(1 1.05/(t))
h(t)
Setting t 0.2 gives that the cost is at least 0.1m logg n, which establishes our claim with constant C' = 0.1.
Proof of Theorem 4.3 Consider all 2 concepts over {xI,..., Tr). each paired with concept class that contains it, permitted by the family F. Consider the uniform distribution over all these 2 (concept, concept class) pairs. Consider any deterministic algorithm that makes at most 2' 7'200 queries on any input. For any deterministic algorithm that makes most /20 queries on any input, we will show that the expected number of mistakes plus queries is at least T/10.
We represent the algorithm's 's execution binary decision tree. The root node contains all 2 possible (concept, concept class) pairs. The tree branches in one of two ways:
1. At 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.
2. At prediction node: The algorithm makes prediction for some example. To minimize mistakes, the optimal strategy is to predict the majority label among remaining concepts. When mistake occurs (prediction differs from the concept's label), we draw a blue edge to the corresponding child node. This child will contain fewer leaves than its sibling, as represents the minority prediction.
The leaf nodes each correspond to single (concept, concept class) pair, uniquely identified through algorithm's 's execution path.
The expected cost (mistakes plus queries) equals the expected number of red and blue edges encoun- tered a random path from root to leaf, where the randomness comes from uniformly selecting among all possible concepts. This cost can be lower-bounded by considering a modified tree where each query node has only one red edge pointing to the child with fewer leaves (rather than two red edges to both children).
By applying Lemma G.1 to this modified tree, with each node labeled by the number of leaves in its subtree, we obtain a lower bound of 2(T)) on the expected cost. Specifically, with the constant derived in Lemma G. the expected number of mistakes plus queries least T/10.
Since randomized algorithm simply a distribution over deterministic algorithms, by Yao's minimax principle, the expected cost of any randomized algorithm against our uniform distribution
32

---

time, with each mistake forcing the learner to move to new concepts is also at least 7/10. Therefore, any algorithm making most 7/20 queries must incur at least 2/20 expected mistakes.
G.3 A Lower Bound with the ERM Oracle
A lower bound for mistakes that is exponential in the Littlestone dimension can additionally be shown for the ERM Oracle the transductive online setting. The following theorem complements Theorem 3.1 from the online setting, but is a lower bound on deterministic algorithms, with an assumption on the number of queries made (o(T)).
Theorem 4.4 (Lower Bound for Transductive Online Learning with ERM Oracles Determinis- tic Algorithms) Let F be the family of all classes with Littlestone dimension dLD- For I' 2 2du++1, when having access to the ERM oracle, fewer than T 2 queries are made, at least 2 mistakes will be made.
Proof We consider the family of classes Firk, which consists of threshold functions partitioned into l equivalence classes, defined as follows:
For every partition of X' into X L 22 U... .... Ak, we construct class C containing k - concepts Co, C Ck, where:
[0
if z 22 for some j S otherwise
(())
We specifically consider 2 All concepts this family have Littlestone dimension at most dLD- so Fu,2
F. Therefore, proving a lower bound for Fı,24LD will establish lower bound for F.
The key property is that classes in this family be viewed thresholds on 2dDD points, where the points are divided into 2dLD equivalence classes. Our adversarial strategy will reveal information about these equivalence classes equivalence class.
For each timestep / = 1, 1,..., T, after q queries have been processed during timestep I, we maintain three sets:
Old threshold points whose labels are definitively known
cla), Copies of the current threshold point (all having the same known label)
U((): Uncertainty region (points whose labels are unknown)
We initialize 0 = 0, C
_ = 0, 0,u (I1, ,2, TT)
Let K be an integer denoting how many equivalence classes of the threshold have been currently observed. Initially, K O.
At the beginning of timestep 1, the learning algorithm will either make a prediction or a query:
If a query made: The learner cannot gain information by assigning the same label to all points in the query. Thus, the query must contain both point labeled and point labeled 1. Let be the earliest indexed point in the query labeled 0, and let be the earliest indexed point labeled 1.
The adversary returns "not realizable" and designates 21 as the first point the first equivalence class with label one the extreme right end of the threshold (increment K to 1 and set ye 1). Update c(1) = {21]. of1) == 0, and U:(1) (z(0) {21).
If a prediction ý1 is made for æ The adversary makes this prediction incorrect by setting V1 1 - 91. and designates ø1 as the first point of the first equivalence class, and places ø
33

---

the extreme end of the threshold corresponding yn (increment K to and ye y )
Update cf = { o == 0. and U,") = -, {a1}-
Let K be an integer, which denotes how many equivalence classes of the threshold have been currently seen. After the above, only (part of) one equivalence class has been seen, so set K 1.
For subsequent operations, suppose we are at timestep t, having made queries in this timestep. This corresponds to sets 0,%) Cla), U(O), where points in clO) have label Be and belong to the K-th cquivalence class. The algorithm proceeds as follows:
If the learner makes a query:
Including points from O.9) in queries provides no additional information. This is because points in O have fixed, known labels that constrain the possible labelings of U(9), but do not provide new information beyond what is already known.
Suppose the query includes points from c/a) and U(1) The query points from c( must always have label equal to ye (otherwise, all points in U:(") will be forced to have label ye. in which case the queries will give no information). Furthermore, for the query to provide new information, there must exist some point = E U(() assigned label 1 We in the query.
The adversary returns "not realizable" and selects = to be the earliest indexed point in U²(") labeled 1 Ye in the query. The adversary then designates as another point in the current equivalence class: cf c( = c( u fz]. [.).. v( == -((1) \ {z].
If the query includes only points from U((); If all labels in the query are identical, the FRM can satisfy the query without providing useful information (by labeling all elements in (7(%) the same. Therefore, the query must include both point labeled 0 and a point labeled 1.
Let 2o be the earliest indexed element of U.()) labeled 0 in the query, and let z be the earliest indexed element labeled 1. The adversary returns "not realizable" and
designates 21-yo copy of the elements in cl cl = =c(²) U f21-w.h. J.
U((+11) == U.!0) (=122) 0(9+1) := 0
If the learner makes a prediction for wy:
If of U c(o), then the learner already knows the correct label. Update 0 0 c( c( -- If vr E U, and the learner predicts S:: The adversary sets y, 1 År. forcing mistake, and increments K by 1 (moving to a new equivalence class, and placing x, on an extreme end of U(1)) in the ordering corresponding yt). The point 2, becomes the first representative of this new class.
If K 24.0 , update c(u) set Ve = for the new equivalence class.
{ax) U v. \ (1x), 100 = o.9) u uc!") and
K 2dU, then all remaining points in 07(9) belong the same final equivalence class with label yt. Update 0 { Jr ++1 = 0, 2+1 0.
An essential property is that each query provides information about at most one point. Since the learner makes fewer than T/2 queries, there are at least [T/2] points about which no information is gained through queries. Let these points, in order of their indices, be 21, - 2[T/2]-
Given that T 7/2 > 2d0 the adversary can force mistakes on at least the first 2dD 1 of these points, with each mistake corresponding to the discovery of a new equivalence class. Therefore, the learner makes at least 2010 1 mistakes.
34

---

H Transductive Online Learning: Thresholds, Intervals, and Hamming Balls
To gain deeper insight into learning Littlestone classes using ERM oracle queries, we analyze two characteristic examples of Littlestone classes: d-Hamming Balls and thresholds. We additionally study unions of k intervals.
H.1 Thresholds
We restate results for transductive online learning with thresholds.
Theorem 4.5 (Upper Bounds on Transductive Online Learning of Thresholdss Consider trans- ductive online learning where F is the family of threshold classes. The following results hold:
1. There exists deterministic algorithm that makes O(T log T) calls the weak consistency oracle and incurs at most Oooo T) mistakes.
2. There exists randomized algorithm that makes (T) calls in expectation to the weak consistency oracle and incurs at most Ollog I') mistakes.
3. There exists deterministic algorithm that makes (TT) calls the ERM oracle and incurs at most Ollog T) mistakes.
4. There exists randomized algoritlum that makes at most O(log T) calls to the ERM oracle in expectation and makes most Oloog T) mistakes.
Proof Deterministic weak consistency oracle (Part 1): The key insight is that for any points Ty, we can determine their relative ordering in < using single query to the weak consistency oracle. Specifically, we check if the dataset {2,,, 0), (Iy, 1)) realizable by Cg. If it is realizable, then 2, I zy; otherwise, I; = Zz.
To determine the complete ordering of all T points, employ comparison-based sorting algorithm requiring O T) oracle calls. Once the points are sorted according to I, we can run standard online learning algorithms (such the Standard Optimal Algorithm the Halving Algorithm) the sorted sequence, incurring at most O(log T) mistakes, which matches the Littlestone dimension of the class.
Randomized + weak consistency oracle (Part 2): present randomized algorithm that efficiently learns the threshold by maintaining boundary points and strategically sampling points with unknown labels.
For each time step t, we maintain two boundary points:
Tr: the rightmost point in (I1, ....,......................... Wt-1 labeled
by the leftmost point in {x1, 22 ...., - labeled
Initially, we set F1 = oo and & = sentinel values to represent the entire range.
When presented with new point 2e, we first determine its position relative to our current boundaries using two weak consistency oracle queries:
Query labeled 0.
{(x,, 1), (re, 0)} realizable? not realizable, then v, < Tt, so Iy must be
Query 2: Is {(ee, 1), (Zz, 0)} realizable? If not realizable, then & 3 Zt. so Fy, must be labeled
If either query resolves the label, predict accordingly. Otherwise, 2, falls in the uncertainty region U, = (re. &.) To predict efficiently, we estimate x relative position within U, as follows:
In the initial case when first few points until both boundary points are properly established, we employ a simple strategy: predict 0 until observing the first 1, then predict until observing the first 0 (if ever). This approach guarantees at most mistakes during this initialization phase, after which our boundary points become well-defined and the main algorithm takes over.
-o and & cc, these comparisons are not well-defined. For the
35

---

We sample |36 [1)) points uniformly random from U2 where ó is small constant probability of error. For each sampled point 2,, we query whether 2; I 22 and record the indicator B, 1[ 3 ær]. Let p J Ei=1 B3 be our estimate of the true fraction p I" Pa-Ule 2t). which represents 2t 's relative position in Uz.
m
By Hoeflding's inequality:
PIβ pl 1/6] S 2eep(-22m(166)) 5
Therefore, with probability at least 1 - 5, we have one of the following cases:
If p S 1/3: 2t likely lies in the first third of Ut, predict label 0
If 2 2/3: 24 likely lies in the last third of Us. so we predict label 1
Otherwise: We can predict either label (for concreteness, predict 0)
If our prediction is incorrect, the threshold must lie in at most 2/3 of the original interval U,. After each mistake, we update 7t or & based on the observed label, further constraining the uncertainty region. Since each mistake reduces the length of the uncertainty region by factor of at least 3/2, the total number mistakes bounded by [logs/2 T = Ollo T). Once the true label ye is known, one can perform a constant number of queries to update T++1 and f based on the value of yt.
In practice, we cannot directly sample from U, since we don't know which unlabeled points lie within it. Instead, we sample from all unlabeled points and test each sampled point using the weak consistency oracle:
Query if re: If true, is to the left of U, (and label æ as 1 and discard it from the set of unlabeled points)
Query if & 3 2: true, z to the right of U, (and label a as and discard it from the set of unlabeled points)
Otherwise, & Ug and can be used in our estimation
Samplings of the first and second types will happen at most once, since it can only be discarded at most once from the set unlabeled points. Thus, the first and second types of samples contribute O(T) calls the weak consistency oracle. The analysis for the third type carries from earlier. Thus, the total number of oracle calls is O(T), with O(log 7) mistakes.
Deterministic + ERM Oracle (Part 3): We present a deterministic algorithm that uses the ERM oracle to efficiently learn the total ordering of all points, then applies a standard online learning algorithm.
First, we employ a divide-and -al-aannd-courur approach to sort all points:
1. Select two arbitrary points 2 and 22 from the current set.
2. Make two ERM oracle queries: one with the labeled set {(21,)) (22, 1)} and another with [(=1, (z2, 0)).
3. Exactly one of these queries will be realizable by the threshold class. If [ 0), (#2, 1)} is realizable, then 21 3 22; otherwise, 22 = 21.
4. Consider the concept defined by the ERM oracle query that is realizable. This concept partitions the points into two sets: So = {x : c(x) = 0} and S = (a c(z) = 1}.
5. By the nature of threshold functions, all points in Sy must precede all points in S in the underlying total order. Recursively sort Sy and S₁ 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 calls needed to sort n points. We have: T(n) = T(()))) +
T(IS) + where |So| |S|| n
In the worst case, this recurrence solves T(n) (n), meaning our algorithm makes O(T) calls to the ERM oracle.
36

---

Once the points sorted,
standard online algorithm just done in the (determin- istic weak consistency oracle) case, incurring at most Ollog 7) mistakes.
Randomized ERM Oracle (Part 4): We present randomized algorithm that efficiently learns the threshold by maintaining and updating a partitioning the imput space.
We maintain three disjoint sets throughout the algorithm:
Ly: Points known to to the left of the threshold (labeled 0)
R Points known to be the right of the threshold (labeled
U, Points with unknown labels (i.e., points between L, and R₂)
Initially, we set L1 = 0, Rı = 0, and U1 = {#1 .2, Frr)
At the beginning of each time step i, if we need make prediction for point 2r, first check if we already know label:
If E Le, predict U: 0
If dy E RG, predict Út- =
xr E U, we need make prediction based on our current understanding of the threshold location. We proceed as follows:
1. Base Case: If JUp1 < 5, we determine the exact ordering of the remaining points with constant number of ERM oracle calls using a simple sorting algorithm, and predict accordingly.
2. Partitioning Step: If |U, > 5 and we haven't already computed a partition LU UR.) of Us, we compute one as follows:
(a) Sample two points 21, 22 uniformly at random from U,
(b) Call the ERM oracle with the labeled pair {(11, 0), (z2, 1)}
(c) this labeling realizable, the oracle returns concept c2 E with a threshold between and 22. We define:
UL.t {z U, cx(x) 0} (points labeled 0 by concept cz)
URR (o E U, (z) 1} (points labeled by concept c.)
(d) minn[UUZ,.l] (.. < U (i.c., the partition is too imbalanced), we repeat sam- pling and partitioning
(e) By random sampling properties, after (llo(116)) attempts, we find balanced parti- tion with probability at least 8
3. Prediction using Partition: Once we have a valid partition (UL,1, Un.)):
If It E: UL predict d:
II E Un,6, predict D:
4. Update Rule: After receiving the true label ye:
our prediction was correct, we maintain the current partitioning
we predicted 9. = for F, E UL,, but received y: (a mistake), then:
All points in UR, must have label
Update: R++1 = R, U
Update: T.411 = T.
Update: U1+1 UL.
Invalidate the current partition for the next time step
If we predicted ÿr for xa Un, e but received ye 0 (a mistake), then:
All points in UL. must have label
Update: L L, Ur.t
Update: R,41 R,
37

---

Update: U4+1
Un,
Invalidate the current partition for the next time step
For mistake analysis, each mistake reduces the size of the unknown region U, by a factor of at least 2/3, since ensure that min(IUz,,1, (UR,()) 2 [U,]] and least one of these regions is moved to either L1+1 or R&+1 after mistake. Since |U1 'I' and each mistake reduces |Ug by a factor of at least 2/3, after Ologg3/2 T) Olog 7') mistakes, we have [U,] S 5, which point we can determine the exact threshold with constant number of additional mistakes.
For oracle complexity, we make 0(log(1/)) ERM oracle calls per mistake to find a balanced partition, where 5 is small constant. With Ollog 7') mistakes, this results in a total of O(log T log(1/6) = Ollog 77) ERM oracle calls in expectation.
Therefore, our randomized algorithm makes (llo T) mistakes and requires Oolog T') ERM oracle calls in expectation.
H.2 Intervals
We now go into the results for k-Intervals (Fint,k)
Proposition H.1 (VC Dimension of k-Intervals) Given an instance space with |x] 2 2k 1, for any C F, the VC Dimension of C is equal to 2k + 1.
Proof For the lower bound of 2k, consider any 2k points 21 < 22 ... < 22k under the ordering X. Any labeling of these points is realizable because it requires most intervals separate regions labeled I, as each maximal contiguous sequence of Is forms one interval.
For the upper bound, observe that any set of 2k + 1 points cannot be shattered. Specifically, for points 21 < 22 < < 22k+11, the alternating labeling c(z;) = mod 2 would require intervals to realize, which exceeds the capacity of the class.
Theorem 4.6 (Upper Bound on Transductive Online Learning of k-Intervals with Weak Con- sistency Oracle Randomized Algorithm) Consider transductive online learning with the family Fin,k- There exists a randomized algorithm that makes O -22h) calls to the weak consistency oracle in expectation and makes at most O(k T) mistakes.
Our approach to proving this theorem consists of two phases: (1) determining the unknown ordering 3 that defines the concept class, and (2) applying standard online learning algorithms once the concept class is identified. The key insight is that points by testing which points are at the extremes of the ordering.
efficiently identify the relative ordering of
Lemma H.2 (Testing for extreme points) Let C E Fin k be an unknown concept class, and consider a set U C. X with |U| > 2k + 2. For any z E U, it requires O(UU)- 22k) weak consistency oracle queries determine, with high probability, whether z is one of the two endpoints (minimum or maximum) in U with respect to the ordering 3 corresponding to C.
To prove the lemma, we also make use of the following lemma:
Lemma H.3 (Lower bound on mis-labeling probability for non-endpoints) Lei z E U be point that is not an endpoint in the ordering = over U. where [U] > 2k 2 When 2k points are sampled uniformly at random from U {2) without replacement and construct the unique unrealizable alternating labeling over the resulting set of points, the probability that z receives label is at least TUT.
Proof of Lemma H.3 Let n == U and = 2k. Since z is not an endpoint, its rank the total ordering on U is some E {2...., n }}. This means there are A == 7-1 1 points below and B = n r 2 points above z. Since both endpoints in the ordering are in the odd position, let's assume without loss of generality that < 2
n+1 i.c. is on the "left half" of the ordering.
38

---

After sampling s points without replacement from U \ (=), let I. denote the number of sampled points that lie below z in the ordering. Then I. follows a hypergeometric distribution:
PIL - 8
In the alternating labeling pattern of the 2k: + 1 points, receives label 0 if and only if it occupies an even position in the sorted order, which occurs precisely when odd.
Define Peven = Ei oda IP[L. f] and Poda = Ee P(r. f.. By the alternating Vandermonde identity [JSJ+ 15], we have:
(-1)a(B-A-) B-A-1
P Peven
Poil
Since A, B 2 1. we have BB A - 11 S - 33 which gives
n--
(n - 8) - 8)
8
Peven
Poda
I
(n [ 2) S
1
Therefore:
1 (1 (1+ + (Peven -Pdaa) 2 7]( PPoven Podal
Peven
1 1 n -1====== 2(n - 1)
s
2
n
Since n [U] 2 2k + 2 and k 2 1, we conclude that Peven
1
-
107
We prove Lemma H.2 below.
Proof of Lemma H.2 We first establish a critical property of k-interval concept classes: For any sequence of 2k points 21 < 22 ... < 22k+1 arranged according to the underlying ordering 3. the alternating labeling c(z; = =i mod 2 is the unique labeling that cannot be realized by any concept in the class. This is because any k--interval concept can create most label transitions when moving from one point to the next in the ordered sequence, but the alternating labeling requires 2k transitions.
Now, consider performing the following process:
1. Randomly sample 2k points from U \\ (z) without replacement.
2. Consider the set S consisting of these 2k sampled points together with z.
3. Using the weak consistency oracle, test all 22k+1 possible labelings of S to identify the unique unrealizable labeling.
4. Observe the label assigned in this unrealizable labeling.
The key insight is that in the unique unrealizable labeling (the alternating pattern), the position of in the ordering determines its label:
If 2 is the minimum element in S (i.e., 2 x z' for all o' e S {z})) it will be labeled 1 in the unrealizable labeling.
If 2 the maximum element in S (i.e., 2' for all z' E (=}), will be labeled in the unrealizable labeling.
If is neither the minimum nor maximum in S, its label in the unrealizable labeling depends on position in the sequence and will be either 1, depending on whether the position is odd or even.
39

---

We now analyze the probability of correctly identifying whether is endpoint:
If is truly endpoint (minimum maximum) in U, then in every sample S, 2 will be the same extreme position in the ordering of S. Consequently, 2 will receive the same label (either consistently for the minimum, consistently for the maximum since |S| 2k is odd) in the unrealizable labeling across all samples.
If z is not an endpoint in U, then in different random samples, the probability that = is laheled in realizable labeling, by Lemma H.3, is at least [0]
To ensure correctness with high probability (at least 1 - 8 for some small constant 6), we repeat this sampling process O(U)- log })) times. By the properties of independent trials, 2 an endpoint, we will observe a contradictory label with high probability after these repetitions.
The total number of weak consistency oracle queries required is:
OQUI log 1
12 - O(U0) -(U1)2224)
when setting to be small constant.
Now prove the theorem.
Proof of Theorem 4.6 Our approach consists of two phases: (1) determining the unknown ordering 3 that defines the concept class with high probability, and (2) applying a standard online learning algorithm once the concept class is identified.
Phase 1: Determining the ordering. We will identify the ordering of the input points (a1,..., ØT) by successively identifying extreme points:
1. Initialize U +x11,.... ØT} and empty sequence S.
2. While U 2k + 1:
(a) Identify extreme points 21, 22 using Lemma H.2 by iterating over all T points.
If it's the first iteration (i.e. [U] = 7"), designate z2 as a*, x" will be the same fixed point for the remaining iterations.
For whichever E {1, 2} such that 2, * 2", append a to S and remove it from U.
3. The remaining points U (at most 21 + 1) can be placed in any order at the end of S.
This procedure yields a sequence sents either the correct ordering 3 or its reverse. Since the definition of the interval concept class is symmetric with respect to ordering direction, we can arbitrarily choose one direction.
(21, :2, žT - which, with high probability, repre-
To analyze the number of queries, when identifying the extreme points and using Lemma H.2, most points are tested, which involves (T222k) queries. There are iterations in the algorithm, giving that there are 322k) queries.
Learning with the determined ordering, Once we have determined the ordering = with high probability, we know that the target concept belongs the class Cint. This class has VC dimension 24 and Littlestone dimension O log T). We thus know the concept class for all but at most 2k points. We can now apply the Standard Optimal Algorithm (SOA) or the halving algorithm for this concept class. When seeing one of the 2k points for where the ordering is uncertain, predict arbitrarily. These algorithms guarantee mistake bound of O log T) in the realizable case, and the 2k uncertain points contribute at most 2k points, resulting in an O log T) mistake bound.
Phase 2:
H.3 Hamming Balls
For set X, we define the family concept classes Fa = (Cr.a I + 13), where each Cy,a represents the set of concepts that differ from on most d points:
40

---

most TQ weak consistency oracle calls and - (0.1) (x Ex: g(x) + [(x))1 sd}
These classes have several important properties. First, each Cj. has Littlestone dimension exactly d. To establish the lower bound, we can select any d distinct points 21, .2.....,.,. Ft E X' and construct Littlestone tree of depth d by placing x; level i. By definition of C,, all 2d possible labelings of these points are achievable by some concept in the class, thus confirming that the Littlestone dimension is at least d.
For the upper bound, suppose for contradiction that there exists a Littlestone tree of depth d + 1 that is shattered by Cj.d- Let 21 be the root node of this tree. For each {1,2, d]. define 2++1 recursively as follows: if (2)) = O, let 2++1 be the right child of 2; otherwise, let 2,41 be the left child of 24. This construction yields concept e Caa that must satisfy c(zi) # f(2)) for all
i E (1,2,... definition of Cz,a- Therefore, the Littlestone dimension is exactly d.
13. But this implies that c disagrees with f on d + points, contradicting the
Theorem H.4 (Transductive Online Learning Bounds for d-Hamming Balls) Let Fa be the family of d- d-Hamming Balls as defined above. Then:
1. There exists deterministic algorithm that makes O(1) calls to the ERM orucle and incurs at most (d) mistakes.
2. There exists deterministic algorithm that makes O(T) calls to the weak consistency oracle and incurs at most (d) mistakes.
Before proving the theorem, comment that in the transductive online learning setting, one can make a reduction from the weak consistency oracle to ERM, achieving the same mistake bound, but with additional O(T) factor. This comes from the observation that ERM solves search problem (it searches for concept), while the weak consistency oracle solves a decision problem (it determines whether or a dataset is realizable), and ERM return a function restricted T points can be solved by running our decision problem I' times. This is captured via the following lemma.
Lemma H.5 (Reducing ERM Oracle to Weak Consistency Oracle) Consider a transductive online learning algorithm that makes at most Q ERM oracle calls where each call only uses points from the set {Z1....; ......Wy Ør} as inputs, only evaluates the returned concepts on these points, and makes at most M mistakes. Then there exists algorithm that makes at most M mistakes.
Proof We simulate each ERM call using most T weak consistency calls. For each ERM query on set S = {(Ti,, Vi. =ix ...)...., (Fi,, 36,)] with & < T and all Pı, E {#11..., .T.), we construct concept e as follows:
First, we check if S is realizable by making a weak consistency call on S. If is not realizable, we return "not realizable" as the ERM oracle would.
realizable, we construct concept e E C consistent with by determining the values of e on each point in {I1....,
For points already S, we set c(xi,) = 1/s, for all j E [k)]
For each æj E f _T} { Tigh. J. we query the weak consistency oracle with SU ( 1)). If the result is true, we set c(x,) = otherwise, we set c(x, = 0 (as there must exist concept in C consistent with S that assigns 0 to 2,)).
This procedure uses at most T weak consistency calls per ERM query (one initial call check realizability, and at most T - l additional calls for the remaining points). Since the original algorithm makes most Q ERM calls, the total number of weak consistency calls is at most TQ.
Furthermore, since we accurately simulate each ERM call by returning a concept consistent with the query set whenever such concept exists, and the original algorithm only evaluates the returned concepts on points in (#1,..., Fr the mistake bound M the original algorithm is preserved.
Now prove the theorem.
41

---

Proof of Theorem H.4 For the HRM oracle bound, the algorithm begins by querying the oracle with the empty set to obtain a function E C.a. By definition, both c and the target concept are at most away from the center function f. so by the triangle inequality, they can disagree on most 2d points. The algorithm simply uses to make all its predictions, resulting in at most 2d mistakes with just single ERM oracle query.
For the weak consistency oracle bound, we apply Lemma H.5. Since our ERM- bbssed algorithm only evaluates the returned concept on the points 21..... 22 and makes (11) ERM calls, we simulate it using (T)) weak consistency oracle calls while maintaining the same mistake bound of (dd).
Furthermore, it is possible to get the optimal transductive mistake bound, if one relaxes the number of queries needed.
Theorem H.6 (d-Hamming Balls, Optimal Mistake Bound) Consider transductive online learning with Fs, the family of d- d-Hamming balls. Then, optimal mistake bounds can be achieved using at most 2d+1 queries using the ERM oracle.
Proof Consider 31, I22 T. and let the unknown concept class be Cf.a There is exactly one non-realizable labeling of these + 1 points (since every other labeling disagrees with f by at most points). Then, one can recover f f (xz),.... ..... f(za-1) via flipping the labels in the realizable labeling. Perform an ERM query with inputs {( 1 - f(z1))... ... (Za. - f(za))} }. The oracle will output the value of for Id+1s...., ZT. allowing the learner gain knowledge of the concept class. from which they can perform standard transductive online learning.
42


Reviews:
[{"review_id": "pTRlgz5i7r", "reviewer": "Reviewer_uFrM", "summary": "This paper studies the number of mistakes and regret achievable when a learner can only interact with the concept class via Empirical Risk Minimization Oracle or weak consistency oracles. \nUnlike standard online models where the learner has full knowledge of the concept class, as here, the learner interacts with the concept class solely through various oracles. The main motivation comes from the computational intractability of implementing algorithms like the Standard Optimal Algorithm (SOA), which, despite being optimal, involves computing Littlestone dimension multiple times even though it is APX-hard. As a result they work with an ERM oracle which given a labeled dataset returns a concept class which minimizes the error on the dataset.  This oracle is known to be sufficient in PAC learning settings. They also consider a weak-consistancy oracle which only returns a binary signal whether the dataset is realizable by some concept in the class. \n\nTheir results are as follows:\nA $\\Omega(2^{d_L})$ mistake lower bound in the realizable setting. They also show a $\\Omega\\sqrt{T 2^{d_L}})$ on the regret in teh agnostic setting. Their result establishes that an exponential dependence on the little-stone dimension is essential.  The proof  for this lower bound involves constructing a concept class of random threshold functions over $T = 2^{d_L}$ points embedded in a high-dimensional space. The adversary carefully defines nested hyper-rectangles using random values that are unknown to the learner. Since the (agnostic) ERM oracle does not know the future nested regions  the learner is forced to make predictions with only 1/2 probability of being correct at each step. \n\nThey also show that any deterministic online learning algorithm that uses the restricted ERM oracle can be simulated using the weaker consistency oracle. The cost is an increase in the number of oracle calls by a factor of O(T), while maintaining the same mistake bounds. This implies that existing ERM-based algorithms can be adapted for the weak consistency setting.\n\nThey also show a number of results for transductive learning, which effectively shows that the negative results in the online setting can be circumvented here. They also show several new results for specific concept classes (all of which are  summarized in Table 2). Unfortunately, I am not as familiar with this part of the literature and am not sure I can judge their novelty.", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "I feel the authors establish an important lowerbound for ERM oracles in online learning. This is in line with recent works that have tried to understand better algorithms and oracles that circumvent known hardness results. I found the paper to be well written and the results clear. The proofs are mostly in the appendix but they seemed correct.\n\nI am not an expert in the area and have little background knowledge. Nonetheless, I think the paper would be of interest to the NeurIPS community.", "was_revised": true, "final_justification": "I am happy with the response the authors provide regarding the novelty of their work. I am happy to keep my review as is.", "rebuttal": "We thank the reviewer for their positive assessment of our paper."}, {"review_id": "ilm9TRAS1m", "reviewer": "Reviewer_8aS9", "summary": "This paper investigates online and transductive online learning scenarios where the learner interacts with the concept class solely through ERM or weak consistency oracles. The authors establish tight lower bounds for the number of mistakes and oracle calls in both realizable and agnostic settings, demonstrating an exponential dependence on the Littlestone dimension. They also explore the transductive setting, where instance sequences are known in advance, and show that polynomial oracle calls can achieve optimal mistake bounds. Special cases like thresholds and k-intervals are analyzed, revealing improved performance with randomized algorithms.", "questions": "The transductive setup is a good bypass for the hardness of online learning. Out of curiosity, have you considered other routes to bypass, e.g., i.i.d. assumptions on the covariates, margin assumptions for linear separators, and smoothed online learning?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. The paper provides rigorous lower and upper bounds, clearly delineating the trade-offs between mistakes and oracle calls. The proofs are well-structured and detailed, with key insights highlighted.\n2. The exploration of weak consistency oracles in online learning is novel, bridging gaps between PAC learning and online settings. The results for specific concept classes (e.g., thresholds, k-intervals) offer insights.\n\nWeaknesses:\nNo specific one.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review and positive assessment of our work. \n\nOther routes to bypass the fully adversarial online setting:\nThis is a great suggestion, and we agree that it points to a natural and important direction for future work. In our revision, we will expand the discussion to include potential relaxations of the model, such as making assumptions on the data-generating process or limiting the power of the adversary. For example, one could assume structure on the covariates or consider a smoothed analysis setting as you suggested."}, {"review_id": "DLazIMT9BA", "reviewer": "Reviewer_1WTD", "summary": "This paper studies online and transductive learning in settings where the learner can only interact with the hypothesis class through ERM or optimization oracles of varying power. Statistically optimal algorithms in the online setting (such as SOA) and the transductive setting typically require direct knowledge of and access to the hypothesis class. This paper asks whether optimal regret/mistake bounds are achievable when the learner can only access the concept class using ERM or other types of optimization and consistency oracles. Foreshadowing that the optimal regret is too much to hope for, the paper aims to understand the tradeoff between the number of oracle calls and the regret/mistake bound broadly.\n\nFor the online setting, the paper shows that the mistake bound is lower bounded by $\\Omega(2^{LD})$ or $\\Omega(3^{LD})$ for randomized and deterministic algorithms, respectively, regardless of the number of oracle calls. In the agnostic case, the regret is lower bounded by $\\Omega(\\sqrt{T 2^{LD}})$. The authors also provide upper bounds that demonstrate exponential dependence on the Littlestone dimension (LD). For the transductive setting, they show that achieving optimal regret/mistake bounds is possible in $O(T^{VC})$ even using a weaker oracle model. While some bounds improve in this setting, it appears that even in the transductive setting, a no-regret algorithm still requires exponential dependence on LD unless a linear number of oracle calls is allowed.\nI find the paper overall interesting. The study of oracle efficiency is of long-standing interest to the COLT community --- which has a good presence within NeurIPS --- and is motivated by real concerns about the practical efficiency of learning algorithms. I find this to be a solid contribution for the theoretically minded NeurIPS audience and I lean towards acceptance.", "questions": "See above two points on explicit comparison to Hazan and Koren and motivation given the broader context.", "limitations": "yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "That being said, I would have felt much more inclined to recommending acceptance more strongly if the paper went the additional mile of 1) connecting with the broader literature a but better, 2) justifying and motivating the study of their work in such generality under such strong adversarial assumptions. Detailed comments below:\n\nI found it difficult to fully connect and compare the findings of this paper to the broader literature on oracle efficiency in online learning, e.g.:\n1. Hazan and Koren, The computational power of optimization in online learning, STOC 2016\n2. Kalai and Vempala, Efficient algorithms for online decision problems, JCSS 2005\n3. Dudík et al., Oracle-efficient Online Learning and Auction Design, FOCS 2017\n\nFor example, [1] provides upper and lower bounds on the number of oracle calls required for achieving vanishing regret, though the dependence on $\\mathrm{LD}$ or $\\mathrm{VC}$ isn't explicitly considered in their work. Are those results subsumed by yours, or do they highlight tradeoffs that are qualitatively different? The techniques shown in [2–3] do not apply to general VC or LD classes (as [1] already establishes), but given the relevance of your work to the oracle-efficient online learning literature, I would have expected a discussion of all of these works.\n\nThe paper would also benefit from a clearer motivation for studying this particular model at the generality of VC or LD classes. I appreciated the improved bounds for certain classes in the transductive setting, but my concern is not a lack of results, but rather a lack of context for paper broadly. There are some minimal attempts at this (e.g., lines 56 on computability issues) but I find the discussion severely lacking.\n\nSince this paper is being submitted to NeurIPS and not COLT, the authors should embrace the additional responsibility of communicating to a broader audience beyond the TCS community.\n\nThis is especially important given that in both theory and practice, a number of works have demonstrated that oracles are quite powerful in many practical online learning settings. For example, [2,3] demonstrate that oracle efficiency and no-regret guarantees can be achieved in settings that are broadly of interest to the community. Moreover, for general VC classes, oracles have also been shown to be quite powerful outside brittle counter examples. For instance:\n\n4. Haghtalab et al., Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries, NeurIPS 2022\n5. Block et al., On the Performance of Empirical Risk Minimization with Smoothed Data, COLT 2024\n\nIn particular, [5] shows that repeated “restricted ERM” suffices for achieving no-regret in realizable online learning if the marginal distribution is smooth. Similarly, [4] studies the agnostic setting under smoothness and also shows that ERM oracle calls suffice for online learning of VC classes. This smoothness condition has come to be widely accepted by the community as a useful test for whether impossibility results against adversaries hold beyond brittle counter examples and demonstrate practical concerns.  Looking at your lower bounds, the constructions also demonstrate quite a lot of brittleness because they are based on requiring exact identification of randomly chosen real values which cannot be done with finite number of oracle calls.\n\nIn light of these results—and the broader NeurIPS audience—I would have liked to see a more rigorous discussion of why the fully adversarial setting in your model is worth studying and why should it be interesting to the broader NeurIPS community. What should be the takeaways from reading your paper in terms of practical tradeoffs in online environments?\n\n\nMinor:\n•\tLine 190: “a a concept” → “a concept”", "was_revised": true, "final_justification": "Good paper, as I stated in my review. It addresses an interesting and important problem on oracle efficiency — a core question in the ML theory community — and provides compelling bounds. As discussed in the review, more of the related works should move to the main body, which is currently a bit sparse on the discussion of related works. I recommend acceptance weakly, and given where the scores are, I expect the paper will be accepted.\n\nMy only hesitation in recommending acceptance more strongly is that the paper’s message may be limited to the COLT/ALT subcommunity within NeurIPS. I do like that the paper takes a very general and adversarial perspective. But, because we know that many of the known technical impossibilities and challenges in dealing with oracles resolve once we consider models where the adversary is a bit more realistic (e.g., smoothed analysis, as mentioned in my review), I think the paper’s broader appeal beyond the COLT/ALT community may be limited.", "rebuttal": "We thank the reviewer for their thoughtful review and constructive feedback, and we are happy to implement the suggestions for improving our presentation. \n\n1. Connecting with broader literature:\nWe already discuss most of the papers you mentioned in the \"Additional Related Work\" section (specifically, the two paragraphs in the Oracle-Efficient Online Learning part of the appendix). However, we will expand on this discussion in more detail and move it into the main body of the paper to provide better context for our contributions. See the new related work section on oracle-efficient online learning at the end of our response.\n\n2. \"Justifying and motivating the study of such generality under strong adversarial assumptions\":\n- Our setting is both highly generic and strongly adversarial, which we view as a strength. Studying learning under such restrictive conditions helps us understand the fundamental barriers, so that any additional assumptions introduced later are clearly motivated and justified. We adopt only the minimal assumptions necessary for learning in this setting: that the (possibly infinite) concept classes have bounded combinatorial dimension, a standard requirement in general online learning, and that the instance sequence is adversarial.\nOur approach is aligned with prior work [HK16, AAD+23, KS24], and it resolves open questions under this minimal set of assumptions. \n- By illuminating this general setting, our work opens the door to studying richer regimes. In particular, we view it as a natural next step to explore “beyond worst-case” models by introducing assumptions on the data-generating process or limiting the adversary’s power, as you suggest. For instance, the smoothed analysis framework proposed by Spielman and Teng was developed only after decades of studying the Simplex algorithm (and other linear programming methods) in their most general form.\nWe will add a paragraph to the discussion section proposing future directions that incorporate such assumptions, and we will cite the works by Haghtalab et al. (2022) and Block et al. (2024). We will also include a discussion of these papers in the revised related work section.\n\nWe also thank you for catching the typo on line 190, and we will fix it accordingly. \n\nWe are happy to answer any further questions and hope our response supports your strong recommendation for acceptance\n\n- Below are the paragraphs that we plan to add to the related work in the \"Oracle-Efficient Online Learning\" section. Specifically, we expand the second paragraph with the following:\n\nTheoretical limitations of this approach have also been investigated. Hazan and Koren [HK16] showed that, for certain finite concept classes $\\mathcal{C}$, any oracle-efficient online learner must make at least $\\tilde{\\Omega}(\\sqrt{|\\mathcal{C}|})$ calls to a powerful optimization oracle (an agnostic ERM oracle) to achieve sublinear regret in the fully adversarial proper-learning setting; they also give a matching $\\widetilde{O}(\\sqrt{|\\mathcal{C}|})$ upper bound. Since the Littlestone dimension satisfies $\\operatorname{Ldim}(\\mathcal{C}) \\le \\log_2 |\\mathcal{C}|$ for finite classes, this implies an exponential dependence of total runtime on the Littlestone dimension. Our results sharpen and generalize this picture: we give lower bounds in \\emph{both} the realizable and agnostic regimes, and for general (possibly infinite) classes parameterized by VC / Littlestone dimension. Rather than targeting mere sublinear regret, we identify conditions under which stronger, dimension-dependent rates are unattainable for any oracle-efficient learner—e.g., $\\Omega(2^{d_{\\mathrm{LD}}})$ (realizable) and $\\Omega\\big(\\sqrt{T\\,2^{d_{\\mathrm{LD}}}}\\big)$ (agnostic). When specialized to finite classes with $|\\mathcal{C}| \\approx 2^{d_{\\mathrm{LD}}}$, both lines of work exhibit exponential dependence on $d_{\\mathrm{LD}}$ (since $\\sqrt{|\\mathcal{C}|} = 2^{d_{\\mathrm{LD}}/2}$), while our results additionally showed that even in the realizable case the required computation is exponential in $d_{\\mathrm{LD}}$ (and in fact cannot be done in a finite number of queries). Altogether, these findings underscore that optimization oracles remove optimization difficulty but not the information-theoretic hardness of fully adversarial online learning.\n\nAdditionally, Kalai and Vempala [KV05] and Dudík et al. [DHL+20] developed oracle-efficient algorithms for various online learning problems (e.g., combinatorial decisions and auctions) by leveraging structure or randomness (perturbed-leader methods), but their techniques assume an efficient oracle for the specific problem at hand and do not apply to arbitrary concept classes.\n\nSeveral works have identified structural conditions that enable oracle-efficient online learning despite the general lower bounds. Dudík et al. [DHL+20] studied the conditions under which oracle-efficient algorithms can succeed, and Haghtalab et al. [HHSY22] provided such algorithms for online learning with smoothed adversaries, introduced in Haghtalab et al. [HRS24]. Haghtalab et al. (2022) gave the first oracle-efficient online learner in the smoothed adversary model, achieving regret bounds $O(\\sqrt{T,d/\\sigma})$ that depend only on the hypothesis class’s VC dimension $d$ and the smoothness parameter $\\sigma$. Their result shows that when the adversary is constrained to draw instances from a $\\sigma$-smooth distribution (i.e., no individual example can have too large a probability mass), online learning becomes computationally as easy as offline learning for any VC class. More recently, Block et al. [BRS24] considered the realizable case under smooth adversaries and show that even a simple repeated-ERM strategy can attain no-regret. In particular, they proved that if the marginal distribution is $\\sigma$-smooth, then empirical risk minimization achieves sublinear error on the order of $\\tilde O(\\sqrt{\\mathrm{comp}(\\mathcal{F}) \\cdot T})$, where $\\mathrm{comp}(\\mathcal{F})$ is the standard PAC-learning complexity of the class. These works underscore that smoothness assumptions, now widely used as a testbed for the robustness of impossibility results – can circumvent the brittle worst-case constructions, enabling efficient online learning of VC classes in practice. However, studying the models for general VC / Littlestone classes is necessary for gaining more fundamental insights into the computational-statistical tradeoffs that govern all concept classes. Studying general classes reveals which properties are universal versus which depend on special structure. While [HHSY22] and [HRS24] establish oracle-efficient algorithms under smoothness assumptions, oracle efficiency in the fully adversarial setting has yet to be resolved."}, {"review_id": "z6jLY0tRhQ", "reviewer": "Reviewer_SSWL", "summary": "The paper continues the study of online learning (and transductive online learning) in restricted access models. While the problem of online is very well understood, most results are based on algorithms that require the knowledge of the hypothesis class and perform some intractable computations. This paper considers restricted setting where the algorithm has either access to an ERM oracle, a restricted ERM oracle that can only query the ERM on points seen so far, and a weak consistency oracle that only identifies if the sample is realizable or not.\n\nThe authors prove several interesting results in these settings. One of the results shows a strong exponential in terms of the Littleston dimesnion lower bound on the mistake of any learner that uses ERM oracles, which matches the known upper bound. Another interesting result is the connection between weak consistency oracles and restricted ERMs. They show that any algorithm that uses restricted ERMs can be simulated by an algorithm that uses weak consistency oracle with a multiplicative O(T) factor in the query complexity.\n\nIn the transductive setting, a significant result is showing that with $O(T^{d_{VC}}$ many oracle calls, it is possible to obtain the optimal mistake bound even in the weak consistency oracle setting. It is further showed that $O(T)$ oracle calls is not sufficient even for the ERM oracle. Moreover, mistake and oracle bounds are derived for specific classes of interest.", "questions": "Is it clear whether the doubly exponential calls for ERM oracle is necessary and is the oracle calls for randomized algorithms of the same order?\n\nIs it clear if the multiplicative $O(T)$ factor in oracle calls for reducing weak consistency model to restricted ERM model necessary? Moreover, it makes sense from the lower bound in the transductive setting that a lower bound for restricted ERM will imply a lower bound for the weak consistency model too. But in the online learning, there are only lower bounds for the restricted ERM model. I think that this should also imply some lower bounds for consistency model but it is not completely clear to me. The reason is that the weak consistency oracle can query the realizability of samples that are not already observed too.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I guess the question of what is achievable in models where the computation is more restricted is an important question in learning theory and the authors seem to make significant steps in the online learning direction. I also believe showing that learning in such restricted models with respect to partial concepts is impossible is an interesting result, which makes point to the challenge of learning with respect to such complicated models that are hoped to capture to some extent the data assumptions. \n\nI think one important part, which is also mentioned in the paper, is that it is not clear how powerful are randomized algorithms and what mistake bounds is attainable if we are allowed polynomially (in $T$) many oracle calls, independent of VC dim. The only negative result in the paper shows insufficiency of linear number of oracle calls for the weak consistency oracle. If I am not mistaken, it is not even clear what happens to the randomized learners with ERM oracles for polynomially many oracle calls. I think this can be an important future direction for this", "was_revised": true, "final_justification": "My initial assessment of the paper was positive. After reading rebuttals, I still keep my score. The authors explained well my questions and I agree that some of the questions are for future work. I raised them because the paper provokes them, which makes me believe the problem studied is an interesting research direction.", "rebuttal": "We thank the reviewer for their knowledgeable review and interesting questions.\n\nQ: \"Is it clear whether the doubly exponential calls for ERM oracle is necessary and is the oracle calls for randomized algorithms of the same order?\"\n\nA: The picture is still unclear, and whether a merely exponential number of calls suffices remains an interesting open question. The best known upper bound, due to [AAD+23], comes from applying an agnostic‑to‑realizable reduction, which already yields a number of calls exponential in the number of mistakes (itself exponential in their analysis). A more sophisticated algorithm (possibly randomized) might improve this bound, but any such approach would likely be quite involved and far from straightforward. \nOn the other hand, it is possible that a matching lower bound will show that the doubly‑exponential dependence is indeed unavoidable.\n\nQ: Is it clear if the multiplicative $O(T)$\n factor in oracle calls for reducing weak consistency model to restricted ERM model necessary? \n \n \nA: In general, we expect a blowup in the number of oracle calls to the decision problem oracle (weak consistency) compared to a variant of the optimization problem (ERM), as is typically the case in computational settings.\nIn the offline (PAC) setting, there is also a polynomial blowup in the number of weak consistency calls compared to a single ERM call (see the paper \"Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?\").\nWe similarly expect an additional cost in oracle calls in the online model (depending on $T$), though it is possible that a better bound could be achieved, perhaps with only additive or otherwise improved dependence on $T$. \n\nYou raise an excellent point about lower bounds. Our restricted ERM lower bounds do not immediately carry over to the weak consistency setting, since weak consistency oracles can query arbitrary datasets, potentially making them more powerful. It is an interesting question whether the weak consistency oracle can ever be strictly stronger than the restricted ERM oracle. All we currently know is that the query complexity of the weak consistency oracle is at least that of the realizable ERM oracle, and at most $T$ times that of the restricted ERM oracle."}]

Author rebuttal:

Meta-review: This paper presents a solid theoretical contribution to the study of online and transductive learning,. The authors establish tight lower bounds on mistakes and regret in the online setting, showing that even with powerful oracles, the performance is fundamentally limited by the Littlestone dimension. All reviewers agreed that it is a strong candidate for acceptance.
Decision: Accept (spotlight)