New parameter defines sample needs for multiclass learning with query feedback
PAC Learning with Query Feedback
Machine Learning
Summary
This paper looks at how computers can learn to label things correctly when they only get yes-or-no answers about groups of possible labels instead of the exact label. The authors introduce the "query dimension," a new way to measure how hard this learning problem is based on both the possible labels and the questions asked. They show that the number of examples needed to learn well depends on this query dimension, giving both lower and upper bounds on the amount of data required. Their results also improve when the questions can split the set of possible labels into fairly even halves, making learning more efficient.
What this means in practice
- •For machine learning engineers: Determine minimum training data size when learning classifiers using yes/no feedback about label subsets during model design.
- •For interactive system developers: Design systems that learn effectively from binary responses to flexible queries about labels, improving user-driven training.
A theory result. No direct application yet.
Authors
Chase Hutton, Adam Melrod, Han Shao
Abstract
We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen subset from a fixed query family. Our main contribution is the query dimension, a combinatorial parameter that captures both the structure of the hypothesis class and the ability of the available queries to distinguish labels. This parameter generalizes the bandit DS dimension, which it recovers under singleton queries. We establish a sample-complexity lower bound of $Ω(D/\varepsilon)$ and an upper bound of $\widetilde{O}(D^2/\varepsilon)$, suppressing factors polylogarithmic in the number of labels and the failure probability. When the available queries can split every candidate set into two parts of comparable size, we improve the upper bound to $\widetilde{O}(D/\varepsilon)$, yielding a characterization up to logarithmic factors.