Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning

• URL: http://arxiv.org/abs/2605.07155v1
• Date: Fri, 08 May 2026 02:41:23 GMT
• Title: Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
• Abstract summary: Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner.<n>We replace the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization oracle.<n>We show that our algorithm reduces the total query complexity down to $O(Td_mathrmVC+1)$ while perfectly preserving near-optimal expected regret.
• Score: 37.15283418677639
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $O\big(T^{2^{O(d_\mathrm{LD})}}\big)$, where $d_\mathrm{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_\mathrm{VC}$) to bound the number of dynamically maintained active paths, our algorithm reduces the total query complexity down to $O(T^{d_\mathrm{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 $Ω(T/Q)$.

Related papers

• An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order [6.657272312990604]
  Attias, Hanneke and Ramaswami (NeurIPS 2025) asked whether randomization provably reduces the oracle calls needed for online learning when the class is accessible only through an oracle.<n>We study the instance they singled out: transductive online learning of thresholds on an unknown total order of T instances, with a consistency-type ERM oracle that returns a full concept consistent with a queried labeled set or reports non-realizability.
  arXiv  Detail & Related papers  (2026-09-09T14:02:47Z)
• SGHA: A Single-Loop Fully First-Order Algorithm for Nonconvex-Strongly-Convex Bilevel Optimization [9.118433290504035]
  We show that Stoc-SGHA achieves an oracle complexity of $Oleft(bar_y-4)$ with at least $1$ for any $in(1)$, and an complexity of $Oleft(bar_y-4)$ under an additional assumption.<n>In a deterministic setting, Stoc-SGHA achieves an oracle complexity of $Oleft(bar_y)$ with at least $1$ for any $in(1)$, and an complexity of $Oleft(bar_y)$ under
  arXiv  Detail & Related papers  (2026-08-24T13:00:40Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation [21.36054923028733]
  Reinforcement learning (RL) in large environments often suffers from severe computational bottlenecks.<n>We propose a novel algorithm that achieves the optimal $tildeO(sqrtT)$ regret bound while requiring only $O(Hloglog T)$ calls.<n>This oracle complexity is entirely independent of the size of the state and action spaces.
  arXiv  Detail & Related papers  (2026-05-01T04:32:23Z)
• Swap Regret Minimization Through Response-Based Approachability [66.39400409563976]
  We consider the problem of minimizing different notions of swap regret in online optimization.<n>We develop a significantly simpler, computationally efficient algorithm that guarantees $O(d3/2 sqrtT)$ linear swap regret for a general convex set and $O(d sqrtT)$ when the set is centrally symmetric.
  arXiv  Detail & Related papers  (2026-02-05T23:43:25Z)
• Oracle-Efficient Combinatorial Semi-Bandits [38.838934613131535]
  We study the semi-bandit problem where an agent selects a subset of base arms and receives individual feedback.<n>We propose oracle-efficient frameworks that significantly reduce oracle calls while maintaining tight regret guarantees.
  arXiv  Detail & Related papers  (2025-10-24T13:07:08Z)
• Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning [17.389446817000945]
  We study online and transductive online learning when the learner interacts with the concept class only via Empirical Risk Minimization (ERM) or weak consistency oracles.
  arXiv  Detail & Related papers  (2025-05-30T18:11:58Z)
• Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning [28.184175745050474]
  We study the impact of the choice of supervised learning oracle on the computational complexity of reinforcement learning algorithms.<n>First, we identify two-context regression as a minimal oracle in the standard episodic access model.<n>Second, we identify one-context regression as a near-minimal oracle in the stronger reset access model.<n>Third, we broaden our focus to Low-Rank MDPs, where we give cryptographic evidence that the analogous oracle from the Block MDP setting is insufficient.
  arXiv  Detail & Related papers  (2025-02-12T18:47:13Z)
• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  We provide evidence that existing learning algorithms, such as multiplicative weights update, are close to optimal. Our results are obtained in the algorithmic framework put forward by Kothari and Mehta.
  arXiv  Detail & Related papers  (2024-11-04T00:39:52Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Simple online learning with consistent oracle [55.43220407902113]
  We consider online learning in the model where a learning algorithm can access the class only via the emphconsistent oracle -- an oracle, that, at any moment, can give a function from the class that agrees with all examples seen so far.
  arXiv  Detail & Related papers  (2023-08-15T21:50:40Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  We study the problem of regret minimization for episodic Reinforcement Learning (RL) We focus on learning with general function classes and general model classes. We show that a logarithmic regret bound is realizable by algorithms with $O(log T)$ switching cost.
  arXiv  Detail & Related papers  (2022-03-03T02:55:55Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  A novel model-free algorithm is proposed to minimize regret in episodic reinforcement learning. The proposed algorithm employs an em early-settled reference update rule, with the aid of two Q-learning sequences. The design principle of our early-settled variance reduction method might be of independent interest to other RL settings.
  arXiv  Detail & Related papers  (2021-10-09T21:13:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.