ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.