Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning

arXiv:2605.07155v1 Announce Type: new Abstract: Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the SOA is computationally intractable to execute even for a single round. To overcome this barrier, recent work in oracle-efficient online learning replaces the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization (ERM) oracle. While such agnostic learners achieve near-optimal expected regret, they suffer from a doubly-exponential oracle complexity of Oig(T^{2^{O(d_LD)}}ig), where d_LD is the Littlestone dimension and T is the number of rounds. In this work, we significantly improve this oracle complexity while relying on an even weaker primitive: a weak-consistency oracle, which merely decides whether a given labeled dataset is realizable. At the core of our approach is an adaptive and dynamic agnostic-to-realizable reduction that actively prunes non-realizable label sequences on the fly. By using the VC dimension (d_VC) to bound the number of dynamically maintained active paths, our algorithm reduces the total query complexity down to O(T^{d_VC+1}) while perfectly preserving near-optimal expected regret. Crucially, this dynamic pruning also yields a memory reduction over the standard reduction. Furthermore, we formally quantify the regret--oracle complexity tradeoff, providing upper bounds that smoothly interpolate between restricted query budgets and attainable expected regret. We complement these with lower bounds proving that any learner restricted to Q = o(sqrt{T}) queries must suffer an expected regret of Omega(T/Q).

Source: arXiv cs.LG | 2026-05-11