Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

• The motivating question is whether i.i.d. contexts from an unknown distribution make adversarial online learning computationally as easy as statistical learning.The adversary chooses losses after seeing the current context and past history, and the learner competes with the best expert in hindsight.Source: §1 · p. 1
• Classical expert algorithms obtain O(√T log N) regret for an explicitly enumerated finite class, but their computational cost scales with N.Statistical learning instead accesses large hypothesis classes through an empirical risk minimization oracle.Source: §1 · p. 1
• Prior oracle-efficient work for unrestricted adaptive losses had not matched the statistically optimal rate, leaving the central computational question open.Wu et al. (2024) obtained eO(T^3/4) regret for finite-VC classes; Okoroafor et al. (2026) obtained optimal rates under a known-function-class restriction on the adversary.Source: §1 · p. 1
• The paper closes the oracle-efficiency gap for finite binary classes against arbitrary adaptive losses.The learner uses at most one ERM call per round and needs neither knowledge of nor auxiliary samples from the context distribution.Source: §1 · p. 2
• The section also announces an Algorithm 1 guarantee for infinite binary classes, with VC dimension identifying the corresponding information-theoretic rate.The supplied result statement does not give the algorithm's rate explicitly.Source: §1 · pp. 1–2

T VC(H) log(1 + T/ VC(H)) log2 T

• Uniform exploration reduces contextual bandits with K actions to classification and yields a new oracle-efficient guarantee for finite policy classes.The approach uses K value-oracle calls per round and does not require access to the context distribution.Source: T VC(H) log(1 + T/ VC(H)) log2 T · p. 2

1.1 Related work

• The related-work discussion distinguishes this hybrid model from fully adversarial online learning, where complexity is characterized by Littlestone dimension and its sequential generalizations.Statistical binary classification is instead characterized by VC dimension.Source: §1.1 · p. 2
• Prior oracle-efficient contextual-bandit methods for i.i.d. contexts and adversarial losses assumed a known context distribution or auxiliary samples from it.This work instead considers an unknown distribution with no additional contexts available and adaptively adversarial losses.Source: §1.1 · p. 3
• Earlier oracle-efficient work obtained eO(T^3/4) regret for finite-VC classes against adaptive losses, while the present approach allows unrestricted adaptive losses with nearly optimal guarantees.Okoroafor et al. (2026) obtain oracle-efficient rates when the adversary is restricted to a known function class.Source: §1.1 · p. 3
• The analysis uses FTPL stability to reduce regret to disagreement among nearly leading hypotheses, then bounds population disagreement using a Gaussian change of measure.The generalization step addresses that the nearly leading set depends on observed contexts through the adaptive losses.Source: §1.1 · pp. 3–4

• Each round reveals a fresh context drawn from an unknown distribution, after which the adversary chooses a loss vector based on the context and realized history.The learner then predicts, incurs the corresponding loss, and observes the full loss vector.Source: §2 · p. 4
• Regret compares the learner's online predictions with the best hypothesis in hindsight.Source: §2 · p. 4
• The ERM oracle receives context-label pairs with real-valued labels and implements arbitrary weighted minimization over the binary class.The oracle uses absolute loss; the setup also fixes deterministic tie-breaking and a default hypothesis for empty input.Source: §2 · p. 4

3 Algorithms and results

• Algorithm 1 resamples Gaussian perturbations on observed contexts and follows the perturbed leader.Each round requires one absolute-loss ERM oracle call.Source: §3 · pp. 4–5
• Algorithm 1's finite-class theorem establishes a regret guarantee for a binary class of size N.The supplied theorem statement specifies σ = 4√log T but does not include the full bound.Source: §3 · p. 5

3.1 VC dimension result

• The paper presents VC dimension as the measure of efficient learnability for infinite classes in this hybrid setting, alongside its role in statistical learnability.Source: §3.1 · p. 5
• Theorem 2 states a guarantee for Algorithm 1 when the class has VC dimension between 1 and T.The supplied theorem statement specifies σ = 4√log T but omits the bound itself.Source: §3.1 · p. 5

3.2 Contextual bandits

• Uniform exploration reduces policies to binary hypotheses that indicate whether a policy selects the sampled action.The augmented exploration contexts are i.i.d. from D × Unif([K]).Source: §3.2 · p. 5
• Algorithm 2 makes at most K cost-sensitive value-oracle calls per round and requires neither knowledge of the context distribution nor auxiliary samples from it.The paper attributes this distribution-access removal to uniform exploration, which supplies i.i.d. augmented contexts on exploration rounds.Source: §3.2 · p. 6
• The cited passages state K^(2/3) T^(2/3) (log N)^(1/3) log^(4/3) T and specify Theorem 3 with K, T, N ≥ 2 and a policy class H ⊆ [K]^X of size N.Source: §3.2 · p. 6
• The guarantee improves on prior oracle-efficient results without distribution access, including against an adversary that adapts to sampled contexts and realized past.The cited comparison suppresses logarithmic factors in N and T.Source: Table 1 · p. 6, §3.2 · p. 6

4.1 Proof ideas

• The standard FTPL potential decomposition reduces regret to stability, while context-attached perturbations make the stability terms correlated across hypotheses.The analysis controls their sum through the volume of contexts where nearly leading hypotheses disagree.Source: §4.1 · p. 7

4.2 Defining disagreement on nearly leading hypotheses

• DIS(H) contains contexts where hypotheses in H disagree, and the analysis reduces regret to the population mass of this region for nearly leading hypotheses.A binary stability argument relates the perturbed-loss gap between the two predictions to both leader changes and disagreement.Source: §4.2 · p. 8, §4.3 · p. 8

4.3 Reducing stability to disagreement

• The potential decomposition and binary stability argument yield the reduction from regret to population disagreement.At each context, the gap between the best perturbed losses for the two predictions controls whether a fresh Gaussian perturbation changes the leader and whether nearly leading hypotheses disagree.Source: §4.3 · p. 8

4.4 Disagreement analysis

• Gaussian symmetry and Massart’s lemma bound empirical disagreement, while a change-of-measure argument extends control to population disagreement despite adaptive losses.The argument constructs a surrogate set from contexts where nearly leading hypotheses agree and perturbations are large; remaining contexts estimate its population mass.Source: §4.4 · pp. 8–9

4.5 VC dimension analysis

• For infinite classes, the analysis counts labelings realized on observed contexts, replacing finite class size with the growth function to obtain a VC-based result.The growth function is controlled by VC dimension, and the extension requires choosing which observed-context labelings to count.Source: §4.5 · p. 9

4.6 Contextual bandits reduction

• On exploration rounds, augmented context-action pairs are i.i.d.; the exploitation update becomes FTPL on the binary class indicating whether a policy selects the sampled action.A lemma converts regret on importance-weighted exploration losses into regret on the full bandit sequence.Source: §4.6 · p. 9

5.1 Stability via disagreement

• If every h in H predicts the same label b at X, then the left-hand side of Lemma 13 is zero and X is not in DIS(A_{s+1}) for every s ≥ 0.Source: §5.1 · p. 12

5.2 Disagreement analysis

• The disagreement proof bounds observed-context disagreement using Gaussian symmetry and a Rademacher-process argument, then uses a change of measure to control population mass.The surrogate set is fixed independently of held-out contexts, allowing those contexts to estimate its population mass.Source: §5.2 · pp. 13–16

5.3 VC dimension proofs

• The VC proof counts realized context labelings instead of taking a union bound over an infinite class, with the growth function replacing finite cardinality.Agreement with a leading hypothesis on selected coordinates is used to avoid a circular choice of held-out contexts.Source: §5.3 · pp. 17, 19

5.4 Contextual bandits proofs

• Conditioned on the exploration-round set E_T, the sampled context-action pairs are i.i.d. from D × Unif([K]); the analysis reduces Algorithm 2 to Algorithm 1 on exploration rounds.The bound is C K^(2/3) T^(2/3) (log N)^(1/3) log^(4/3) T.Source: §5.4 · pp. 19–20

6 Discussion

• The FTPL algorithm gives the first nearly optimal expected-regret guarantee using a single ERM call per round.The discussion describes the analysis as applying to sequential binary prediction with stochastic contexts and adversarial losses.Source: §6 · p. 24
• The same guarantee yields a contextual-bandit regret bound without sampling access to the context distribution.The stated bound is eO(K^2/3 T^2/3(log N)^1/3).Source: §6 · p. 24
• Extending Theorem 1 to real-valued hypothesis classes remains open and may require changes to the algorithm, oracle model, or both.Source: §6 · p. 24

Use of AI

• The authors credit GPT Astra with an early disagreement-analysis proof idea, then say the final proof was substantially reworked and human-checked.The original note used a more complicated counting argument that incurred extra logarithmic factors and did not extend to VC classes; the authors wrote nearly all final exposition and take responsibility for the results.Source: Use of AI · p. 24