PaperlayerView exact revision on arXiv

Source-linked AI summary

An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order

Xuan Li

arXiv:2609.10196v1cs.LGstat.ML

TL;DR

The paper asks whether randomization reduces oracle calls for online learning when the class is accessible only through an oracle, focusing on transductive thresholds on an unknown order. It analyzes fixed and adversarially frozen consistency-type ERM rules, proving a deterministic–randomized separation and showing that the gap depends on oracle selection. The results are bounded to the stated threshold, transductive setting and include convention and proof-technique limitations.

  • Problem

    The work addresses whether randomization can reduce oracle calls for online learning with oracle access, a question posed for thresholds on an unknown order.

  • Method

    The paper studies extremal, median, and adversarially frozen consistency-type ERM selection rules using deterministic charging and randomized hard-distribution potential arguments.

  • Results

    Deterministic learners require Θ(T) calls for O(log T) mistakes under extremal rules, while randomized learners require Θ(log T), and feasible-median permits deterministic O(log T) calls and mistakes.

  • Takeaways & Limitations

    Oracle selection behavior is a complexity parameter: randomization is advantageous against unfavorable extremal or adversarial selection but not necessary under feasible-median selection.

  • Takeaways & Limitations

    The results are restricted to the transductive threshold setting with finite domains and do not settle arbitrary classes or the non-transductive setting; convention N treatment is confined to appendices.

Abstract

from arXiv · show

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. 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). Our main result is a separation for a fixed natural oracle. When the oracle is the minimal-prefix rule (or the maximal-prefix rule), every deterministic learner makes M mistakes and Q calls with $M+Q\ge T-\varepsilon$ on some instance ($\varepsilon\in\{0,1\}$, according to whether the empty prefix is a concept), and the constant is exact; hence $O(\log T)$ mistakes cost $T-\varepsilon-O(\log T)$ calls, whereas that paper's randomized learner achieves $O(\log T)$ expected calls and mistakes under the same rule. The randomized order is optimal: on an explicit hard distribution under the minimal-prefix rule, every learner has expected mistakes at least $((T+1-\varepsilon)\,128^{-\mathbb{E}[Q]}-1)/2$, so $Ω(\log T)$ expected calls are necessary for polylogarithmic mistakes. The separation is governed by the oracle's selection rule, not by the class alone: for a legal feasible-median ERM rule a deterministic learner achieves $O(\log T)$ calls and mistakes, while a global-median rule again forces linear total cost. The same linear bound holds when the oracle's answers are chosen adversarially and then frozen into a memoryless oracle. We add partial tradeoff results for fixed query budgets (the middle regime is open) and an interface contrast: with only a weak consistency oracle, returning a realizability bit, both deterministic and randomized learners need $Θ(T)$ calls.

1 Introduction

The paper establishes a deterministic–randomized separation for thresholds on an unknown order under a fixed natural ERM oracle, while showing that oracle selection rules determine the complexity. It also develops matching randomized lower bounds and extensions to adversarially frozen oracles.

  • Motivation: Oracle-based online learning separates mistake cost from oracle-call cost, making the oracle interface and selection rule part of the problem specification.A class can have few mistakes but still require many calls.
  • Deterministic separation: A fixed minimal-prefix or maximal-prefix rule forces every deterministic learner to satisfy M+Q≥T−ε, with the constant exact.This yields T−ε−O(log T) calls for an O(log T)-mistake guarantee.
  • Randomized lower bound: Every randomized learner under the minimal-prefix rule satisfies E[M]≥((T+1−ε)128^(-E[Q])−1)/2, making Ω(log T) expected calls necessary for polylogarithmic mistakes.Together with AHR25, the randomized query complexity is Θ(log T).
  • Selection-rule dependence: The separation depends on the oracle’s selection rule: feasible-median permits deterministic O(log T) calls and mistakes, whereas global-median again forces linear total cost.Thus the threshold class alone does not determine deterministic oracle complexity.
  • Extensions and techniques: The deterministic lower bound also holds when answers are chosen adversarially and then frozen into a memoryless oracle, while fixed-budget tradeoffs remain partly unresolved.The paper’s techniques use common-value charging for deterministic bounds and a hidden-center potential argument for randomized bounds.
  • Scope and context: The paper contrasts its consistency-type full-vector oracle with weak consistency interfaces and places the result within prior oracle-efficient online-learning work.Its conclusion is specific to the transductive threshold setting and does not settle arbitrary classes or non-transductive learning.

2 Model and conventions

The model is transductive threshold prediction on a hidden total order, where learners access the threshold class through consistency oracles with different answer-selection rules. The paper distinguishes fixed-rule, adversarial-then-frozen, and randomized quantifier settings, with convention-dependent bookkeeping.

  • Model: The learner predicts threshold labels for announced instances under an unknown total order and unknown target cutoff; restricted concepts are indicators of order prefixes.The threshold family consists of all such order-dependent concept classes.
  • Conventions: Convention E adds a sentinel and includes the empty prefix, while convention N omits it; the difference is recorded by ε∈{0,1}.The two conventions differ by one concept and affect the lower-bound constants.
  • Oracle interface: A consistency-type ERM oracle returns a full consistent concept or ⊥, whereas a weak consistency oracle returns only realizability; every call costs one.The learner knows the instance sequence and domain but not the order or target.
  • Quantifiers: Under a fixed rule, the rule is announced before the learner and the adversary then chooses the order and target; under adversarial-then-frozen quantifiers, the oracle is produced after the learner and then frozen.Randomized lower bounds instead fix the instance, target, sequence, and rule before private randomness.
  • Interpretation: The fixed-rule formulation matches the literal ERM-oracle interpretation, while AHR25’s randomized learner works for every legal oracle.This makes a fixed natural rule sufficient for the claimed separation.

3 Main results

The main theorems establish exact linear deterministic cost for extremal rules, a matching logarithmic randomized tradeoff, and strong dependence on the oracle’s selection rule. Feasible-median is easy for deterministic learners, while global-median remains hard.

  • Theorem 3.1: M+Q=T−ε is achievable without calls and is forced on some instance for deterministic learners under the extremal rules.Therefore an O(log T)-mistake guarantee requires at least T−ε−O(log T) calls.
  • Theorem 3.2: E[M]≥max{0,((T+1−ε)128^(-q)−1)/2} when expected calls are at most q, implying Ω(log T) calls for polylogarithmic mistakes.Combined with AHR25, randomized ERM query complexity is Θ(log T), versus Θ(T) deterministically under extremal rules.
  • Theorem 3.4: The feasible-median rule admits a deterministic learner with Q≤⌈log2 T⌉ and M≤⌈log2 T⌉ for T≥2.This shows the deterministic lower bound is not uniform over all legal predeclared rules.
  • Theorem 3.4: The global-median rule forces M+Q≥T−m on some instance, so deterministic learners cannot achieve both O(log T) mistakes and O(log T) calls under that rule.The stated bounds are upper and lower bounds, not exact minimax values for these rules.
  • Summary: Table 1 organizes the O(log T)-mistake query complexity by interface and oracle quantifier.The comparison includes fixed-rule, worst-case legal-oracle, and weak-consistency settings.

4 The deterministic separation

For minimal-prefix and related extremal rules, deterministic learners face an exact linear tradeoff between mistakes and oracle calls, including against adversarial answers later frozen into a memoryless oracle.

  • Fixed-rule lower bound: M+Q≥T−ε holds for every deterministic learner under the fixed minimal-prefix rule, and the constant is exact.The proof uses anchored states and a one-pin common-value property; maximal-prefix and related rules follow by duality or the same property.
  • Proof mechanism: Each query can eliminate at most one free point in the adversary’s residual block, despite returning a full label vector.Predictions on free points are charged through a potential that decreases by at most one per call.
  • Robustness: The same linear bound persists when answers are chosen adaptively and then frozen into a legal memoryless oracle.This robustness theorem has quantifier form ∀A ∃(⪯, z, O), unlike the fixed-oracle theorem, which uses one oracle announced before all learners.
  • Consequence: T−ε−m(T) calls are necessary for any deterministic learner guaranteeing at most m(T) mistakes against legal memoryless ERM oracles.Thus O(log T) mistakes require T−ε−O(log T) calls, while the randomized learner achieves O(log T) expected calls and mistakes.

5 The randomized lower bound

A hard distribution shows that randomized learners also need logarithmically many expected calls to obtain polylogarithmic mistakes under the minimal-prefix rule.

  • Hard distribution: The hard distribution places a uniformly hidden center in a balanced interval tree and makes the labels independent fair bits.The total order is constructed from the center-dependent priority order, so the labels remain threshold-realizable while the geometry controls oracle revelations.
  • Proof mechanism: One call may reveal many labels, so the proof tracks paid predictions and remaining hidden points with a logarithmic potential.Each call decreases the potential by at most 7 ln 2 in expectation, yielding the exponential factor 128^−E[Q].
  • Lower bound: E[M]≥((T+1−ε)128^−E[Q]−1)/2 for every randomized learner on the explicit hard distribution.The distribution uses a hidden center and fair labels embedded in a genuine total-order threshold class.
  • Lower bound: Ω(log T) expected calls are necessary for polylogarithmic expected mistakes.This matches the order of the previously known randomized upper bound.

6 Oracle selection matters

Deterministic complexity depends on the ERM oracle’s selection rule, not only on the threshold class and interface.

  • Feasible median: ⌈log2 T⌉ calls and ⌈log2 T⌉ mistakes suffice deterministically under the legal feasible-median rule.The rule returns the midpoint of the feasible cutoff interval, enabling binary shrinkage of the uncertain region.
  • Global median: The global-median rule forces M+Q≥⌊T/2⌋ on some instance, although one empty query can yield Q=1 and M≤⌈T/2⌉.Its calls can be simulated by anchored minimal-prefix calls on the uncertain block.
  • Interpretation: Three legal memoryless rules therefore have different deterministic complexities: exact T−ε for extremal rules, linear total cost for global median, and logarithmic calls and mistakes for feasible median.The randomized learner is described as indifferent to the oracle’s selection rule.

7 Consequences: fixed budgets and the weak consistency interface

Fixed-budget tradeoffs are only partially characterized, while replacing full ERM concepts with a realizability bit removes the randomized query advantage.

  • Fixed budgets: For a fixed query budget, the paper gives bounds and exact small- and large-budget regimes, but the middle regime remains open.The minimax quantity is defined for deterministic learners making at most Q ERM calls against an adversarial oracle.
  • Fixed budgets: N(T,Q)≤min{T−1,max{T−Q,⌈T/2⌉}} for the stated fixed-budget setting.The T−Q component is a budget statement derived by recurrence and induction, not a general pathwise assertion.
  • Weak consistency interface: With only a weak consistency oracle, both deterministic and randomized learners need Θ(T) calls for O(log T) mistakes.The deterministic upper bounds use at most 66T calls under E and 67(T−1) under N, while the lower bound applies to either learner type.
  • Weak consistency interface: The weak-interface deterministic upper bound improves the prior O(T log T) algorithmic bound to linear order with explicit constants.The cited remark limits this claim to the specific selection procedure, rather than arbitrary derandomization.

8 Discussion and open problems

The paper establishes a threshold-specific deterministic–randomized separation while identifying oracle selection, broader settings, and intermediate tradeoffs as open directions.

  • Main conclusions: The fixed-oracle separation gives deterministic query complexity Θ(T) for O(log T) mistakes, versus randomized complexity Θ(log T), with the gap governed by oracle selection.The same linear bound also holds against adversarial memoryless oracles.
  • Open problems: A parameter measuring how much an ERM rule shrinks the feasible set in one call could unify the three demonstrated selection-rule behaviors.The paper notes that endpoint versus non-endpoint selection alone is insufficient.
  • Open problems: The exact minimax mistake–query tradeoff remains open for ⌊T/2⌋ < Q < 2(T−1).The value is not max(T−Q, ⌊log2(T+1)⌋).
  • Open problems: Improving the constant 128 in the randomized lower bound is another stated open problem.
  • Open problems: Extending the separation to arbitrary Littlestone classes and the non-transductive setting remains unresolved.The charging and fixation steps are not threshold-specific, but the one-pin lemma and interval-tree distribution are.

A Proof of Theorem 3.1 and Theorem 3.4

The proof fixes the consistency-ERM interface and defines extremal prefix oracles under two domain conventions, including their behavior on realizable and non-realizable samples.

  • Interface and conventions: The analysis uses full-vector consistency-ERM returns for unrestricted finite query samples, not the weak consistency interface.The weak interface returns only a realizability bit and is not used here.
  • Interface and conventions: Omin returns the smallest consistent prefix or ⊥, while Omax returns the largest consistent prefix or ⊥ when no consistent prefix exists.
  • Interface and conventions: Under convention E, the domain includes an always-positive anchor s, so the smallest prefix is the singleton {s}.
  • Interface and conventions: Under convention N, the domain excludes the anchor and prefixes are nonempty, so Omin returns the order-minimum singleton when consistent.

Statement of Theorem 3.1 (fixed extremal ERM rules)

The proof constructs a fixed order and target against a publicly declared extremal oracle by preserving a family of compatible order–target pairs and stabilizing each oracle answer with at most one endpoint pin.

  • Theorem statement: For Omin or Omax, every deterministic learner faces an order and target with total cost M+Q at least T−ε, where ε=0 under E and ε=1 under N.The oracle is fixed before the learner and instance, and ε records whether the empty prefix is available.
  • Invariant: The construction retains orders by fixing L and R while freely permuting the middle block F, with targets allowed to cut through F.
  • One-pin mechanism: Each query can be answered with a common full vector after at most one endpoint pin of a free point.The remaining free points retain no imposed relative order.
  • Prediction step: Predictions on free points can be forced to be mistakes while preserving a nonempty compatible family and removing the predicted point from F.
  • Cost accounting: A potential argument charges each query with at most one removed free point and each remaining free point with a prediction mistake, yielding the total-cost lower bound.At completion the potential is zero, and the construction produces one fixed order, target, and memoryless oracle.
  • Fixation: The fixed-instance replay preserves every recorded query, answer, and prediction through the stopping event, making the adaptive construction an oblivious adversarial instance.

7. Sharpness and relation to AHR25

The extremal lower bound is exact and matches the randomized separation, while alternative feasible-prefix selection rules show that deterministic logarithmic learning depends on the oracle rule.

  • Sharpness: The extremal total-cost lower bound is exact, with matching no-query upper bounds under both domain conventions.
  • Relation to AHR25: The deterministic lower bound for the fixed extremal rule implies that O(log T) worst-case errors require T−ε−O(log T) queries on some instance.AHR25 supplies the matching randomized O(log T)-error, O(log T)-expected-query upper bound under the same fixed rule.
  • Selection rules: The feasible-median rule selects the feasible cutoff closest to the interval median, whereas the global-median rule selects the feasible cutoff closest to a fixed global median.
  • Selection rules: A deterministic learner using a feasible-median rule achieves at most ⌈log2 T⌉ mistakes and ⌈log2 T⌉ queries for T≥2.Each error halves the active feasible interval up to rounding.
  • Selection rules: The global-median rule still prevents simultaneous O(log T) mistakes and O(log T) queries, despite refuting the full extremal inequality.For T=8, an upper bound M+Q≤5 refutes that inequality under both conventions.

B Proof of Theorem 4.1

The proof constructs one fixed order, target, sequence, and memoryless ERM oracle that force every deterministic learner to pay nearly one unit of mistakes or calls per instance. The construction preserves a freely permutable block while ensuring each fresh query removes at most one free point.

  • Theorem statement: For every deterministic learner, one fixed oblivious instance and legal memoryless ERM oracle yield a linear lower bound with additive constant determined by the prefix convention.The empty-prefix convention has ε=0, while the nonempty-prefix convention has ε=1.
  • State invariant: The adversary maintains committed-left, free-middle, and committed-right blocks, with free points unconstrained in their internal order.The state representation preserves all total orders extending the partial order L≺F≺R.
  • Oracle construction: Each fresh query receives a legal answer while removing at most one point from the free block; cached queries leave the state unchanged.The cache makes the oracle a well-defined function of the entire sample set and preserves prior answers.
  • Oracle construction: The three query cases handle contradictions, forced inversions, and consistent prefix answers while preserving legality for every retained order.When both positive and negative sample points lie in the free block, the construction pins one free negative point and removes it from the free set.
  • Quantifiers and exactness: The resulting fixed oracle and instance satisfy the transductive obliviousness requirements, and the additive constants are exact at T=1.The order, target, sequence, and oracle are fixed before replay; the two conventions rule out smaller universal constants.
  • Consequence: Consequently, deterministic learners guaranteeing m(T) mistakes require at least T−ε−m(T) calls, whereas randomized learning can use O(log T) calls and mistakes.For m(T)=O(log T), the deterministic call requirement is T−ε−O(log T).

C Proof of Theorem 3.2

The proof establishes a randomized lower bound by replacing the actual oracle with a stronger one-query information source and analyzing a hidden interval whose unresolved labels remain random. A logarithmic potential then shows that polylogarithmic expected mistakes require logarithmically many expected calls.

  • Hard distribution: The hard distribution builds a binary interval tree and orders points by the sibling blocks encountered along the hidden target index.The target threshold is determined by the last positive point in the induced priority order.
  • Oracle reduction: The minimum-prefix oracle depends only on the sample and order, and each response can be simulated with one call to a stronger prefix-max oracle.The stronger response determines whether the original oracle returns a full prefix or ⊥, regardless of sample size or arrival status.
  • Auxiliary information: The auxiliary oracle reveals additional priority and label information while using only one query, so any lower bound for it also applies to the actual memoryless oracle.The simulated learner can ignore the extra information and retain the same query count and prediction distribution.
  • Conditional randomness: Conditioned on the auxiliary history, labels in the remaining hidden interval are independent fair bits and remain independent of the hidden target index.The hidden interval shrinks through child selection, with each early refinement continuing with conditional probability at most 5/6.
  • Consequences: The resulting lower bound applies to every learner, including randomized learners, and makes O(log T) expected calls optimal for polylogarithmic expected mistakes.The corollary combines the theorem with AHR25’s randomized upper bound and gives deterministic Θ(T) query complexity under extremal rules.
  • Proof limitation: The potential argument cannot be extended by assuming a fresh uniform posterior after every query, because the posterior within the unresolved set is generally not fresh uniform.The failure persists after +1 regularization and is not caused by taking a logarithm of zero.

D Proof of Theorem 7.1

The fixed-budget analysis combines protection-based upper bounds with adversarial lower bounds that preserve unresolved antichains and reduce the nonempty-prefix case to small first-action games. It also identifies exact counterexamples showing that proposed closed forms can fail.

  • Upper-bound accounting: The protection algorithm queries undetermined arrivals while budget remains, and each mistaken query protects a distinct future point.If the budget is not exhausted, at most one undetermined arrival can occur without a query.
  • No-query lower bound: With no queries remaining, an unresolved antichain of size r permits the adversary to force r mistakes.Every subset of the antichain can be realized as the positive part of a threshold in some linear extension.
  • Small-game lower bounds: A five-point first-action game under the empty-prefix convention can force at least three mistakes with at most one further query.The adversary chooses a current point’s label opposite the prediction and constructs three future points that preserve additional ambiguity.
  • Exact counterexample: The analysis proves N(6,4)=3, so any proposed formula assigning value 2 at (T,Q)=(6,4) is false.The matching lower and upper bounds establish the exact value.

E Proof of Theorem 7.2

The weak consistency interface returns only realizability information, yet deterministic algorithms can still locate order statistics and maintain certified labels with linear query bounds and logarithmic mistakes. These pathwise guarantees extend across the two domain conventions, while the resulting interface has fundamentally different query complexity from concept-returning ERM.

  • Setting: The learner accesses only a Boolean realizability oracle and never receives or evaluates a returned concept.The analysis covers transductive threshold learning on T instances under an unknown total order, with conventions E and N differing in whether the empty prefix is available.
  • Complexity bounds: Under convention E, Q≤66T and M≤⌊log2(T+1)⌋; under convention N, Q≤67(T−1) and M≤⌊log2 T⌋.These are pathwise deterministic bounds, with no randomization or averaging over oracle answers.
  • Comparison primitive: A weak-consistency query comparing (u,1) and (v,0) is realizable exactly when u≺v, thereby implementing an order comparison.The query concerns existence of a consistent concept, not consistency with the actual target labels.
  • Order-statistic subroutine: 32n weak-consistency queries suffice to find an element of any requested rank, after which partitioning the remaining elements costs at most n−1 additional queries.The rank-selection procedure is deterministic and remains correct against adaptively supplied answers consistent with a total order.
  • Phase invariant: Each learning phase contains at most one mistake because certified labels remain correct and the phase ends when its unresolved region satisfies the stated stopping condition.The unresolved set may be conservative and need not form an interval in the unknown order.
  • Interface contrast: With only a realizability bit, both deterministic and randomized learners require Θ(T) expected queries for logarithmic expected mistakes.This contrasts with concept-returning ERM, where randomized learners achieve Θ(log T) query complexity and deterministic learners have linear complexity against the stated worst-case oracle settings.
Loading 2609.10196v1…