Attias–Hanneke–Ramaswami question on randomized oracle complexity
Statement
Let be a set of instances equipped with an unknown total order , and let be the class of threshold concepts whose positive sets are prefixes of (with the empty prefix included or excluded according to the model). In transductive online learning, a learner predicts labels of the instances and may query a consistency-type ERM oracle on a labeled set . If is realizable by some , the oracle returns a concept in consistent with ; otherwise it reports non-realizability. Determine the optimal tradeoff between the number of mistakes and the number of oracle calls 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 and beyond the established extreme regimes.
Record
- Added
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.