Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning

We thank the reviewer for their knowledgeable review and interesting questions.

Q: "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?"

A: 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. On the other hand, it is possible that a matching lower bound will show that the doubly‑exponential dependence is indeed unavoidable.

Q: Is it clear if the multiplicative $O(T)$ factor in oracle calls for reducing weak consistency model to restricted ERM model necessary?

A: 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. In 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'?"). We 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$.

You 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.

We thank the reviewer for their thoughtful review and constructive feedback, and we are happy to implement the suggestions for improving our presentation.

1. Connecting with broader literature: We 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.

2. "Justifying and motivating the study of such generality under strong adversarial assumptions":

• 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. Our approach is aligned with prior work [HK16, AAD+23, KS24], and it resolves open questions under this minimal set of assumptions.
• 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. We 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.

We also thank you for catching the typo on line 190, and we will fix it accordingly.

We are happy to answer any further questions and hope our response supports your strong recommendation for acceptance

• 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:

Theoretical 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 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.

Additionally, 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.

Several 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.

We thank the reviewer for their thoughtful review and positive assessment of our work.

Other routes to bypass the fully adversarial online setting: This 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.

We thank the reviewer for their positive assessment of our paper.