MathDB

Attias–Hanneke–Ramaswami question on randomized oracle complexity

Let XX be a set of TT instances equipped with an unknown total order ≺\prec, and let C≺\mathcal{C}_{\prec} be the class of threshold concepts whose positive sets are prefixes of ≺\prec (with the empty prefix included or excluded according to the model). In transductive online learning, a learner predicts labels of the TT instances and may query a consistency-type ERM oracle on a labeled set S⊆X×{0,1}S\subseteq X\times\{0,1\}. If SS is realizable by some C∈C≺C\in\mathcal{C}_{\prec}, the oracle returns a concept in C≺\mathcal{C}_{\prec} consistent with SS; otherwise it reports non-realizability. Determine the optimal tradeoff between the number of mistakes MM and the number of oracle calls QQ for deterministic and randomized learners, including whether randomization yields an asymptotic separation, and how the answer depends on the oracle's valid selection rule, such as the minimal-prefix, maximal-prefix, or feasible-median rule. In particular, determine the unresolved intermediate tradeoff between MM and QQ beyond the established extreme regimes.

References

Primary source

arXiv

Additional references

computational-complexitylearning-theory
Posted · edited

Progress summary

Refreshed
Claimed progress

A new paper claims a sharp gap between deterministic and randomized costs, but the intermediate tradeoff remains open.

The question asks how randomized access to an oracle compares with deterministic access, including how the oracle itself is selected. The latest reports settle the extreme minimal- and maximal-prefix cases for the highlighted instance, not the full tradeoff.

Known results

  • AHR 25 gives a lower bound beyond the low-query regime for randomized online learners.
  • A 2026 follow-up proves a lower bound of T2min⁡{1,dQ+1}−Q2\frac{T}{2}\min\left\{1,\frac{d}{Q+1}\right\}-\frac{Q}{2}, yielding Ω(T/Q)\Omega(T/Q) when d=1d=1 and Q=o(T)Q=o(\sqrt{T}).
  • The same work gives an interpolation algorithm, but explicitly leaves the full tradeoff open.

September 9, 2026 separation

The paper An Exponential Deterministic--Randomized Gap in ERM-Oracle Complexity for Thresholds on an Unknown Order reports linear deterministic cost versus logarithmic expected randomized cost under minimal- and maximal-prefix rules, and says the middle regime remains open. This is a claimed advance; its correctness and precise relation to the full question are unverified.

Current status (as of September 2026): The extreme prefix-selection cases are claimed to exhibit a linear-versus-logarithmic separation, while the intermediate tradeoff remains open and the new claim is unverified.

Sources

Solutions 0

No solutions have been posted yet.