Research map / Bandits and online learning / Online convex optimization and games

Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Online learning with feedback graphs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes ADEPT, an agnostic-to-realizable online reduction that prunes unrealizable label prefixes with a weak-consistency oracle, cutting oracle complexity from T^{2^O(d_LD)} to T^{d_VC+1} while keeping near-optimal expected regret, plus a regret–query tradeoff and an Omega(T/Q) lower bound.

Problem

Agnostic online binary classification with only offline oracle access (ERM or weak consistency) to the concept class; prior oracle-efficient reductions need doubly-exponential oracle calls.

Approach

Replace the explicit tracking of all O(T^M) mistake-schedule experts with a dynamically pruned tree of realizable label prefixes: weak-consistency queries discard unrealizable prefixes, and combinatorial future-capacity weights keep the Hedge distribution identical to the full expert ensemble. Sauer's lemma bounds active prefixes by O(t^{d_VC}).

Key results

• ADEPT achieves expected regret O(sqrt(T M log T)) with at most O(t^{d_VC}) active paths per round, and total weak-consistency queries O(T^{d_VC+1}) when instantiated with an oracle-efficient base learner (M = 2^{O(d_LD)}), versus T^{2^{O(d_LD)}} for prior reductions.
• Oracle-regret tradeoff: for c in (0,1), O(T^{1+c d_VC}) queries yield expected regret O(T^{1-c/2} sqrt(d_LD + M log T)).
• Lower bound: for d_LD = 1, any learner with Q = o(sqrt T) ERM queries suffers expected regret Omega(T/Q).

Surprising findings

• With a bounded number of ERM queries, regret must be linear in T, even for Littlestone dimension 1 classes.

Limitations

• Query complexity bound T^{d_VC+1} still polynomial but can be large; depends on the base learner's per-round queries Q_A(t).
• Lower bound is stated for ERM oracle, while upper bounds use weak consistency oracle; open gap in the yellow region of the tradeoff.
• Proof sketches contain informal steps (e.g., regret preservation argument), and the paper is theoretical with no experiments.

Experimental setup

Metrics: expected regret oracle query complexity memory

Baselines: Ben-David et al. reduction Attias et al. ERM-based learner Standard Optimal Algorithm

Builds on: Standard Optimal Algorithm Ben-David et al. agnostic-to-realizable reduction Alon et al. optimal agnostic regret Attias et al. oracle-efficient online learning Daskalakis et al. weak consistency oracle

Closest papers by meaning

• Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning (NeurIPS 2025 · similarity 0.89)
• Online Learning with Unknown Constraints (ICML 2025 · similarity 0.88)
• From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.87)
• Non-stationary Projection-Free Online Learning with Dynamic and Adaptive Regret Guarantees (AAAI 2024 · similarity 0.86)
• Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint (AAAI 2025 · similarity 0.86)
• Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.85)