On Learning with Ambiguous Labels

We study learning in the situation where each training example comes with a set of at most $\ell$ possible labels containing the correct one. The learner may also predict up to $L\ge \ell$ labels for each new input, and makes an "error” if its prediction omits the correct label. For countable input and label spaces and any fixed $\ell \ge 2$, we identify a combinatorial "dimension” whose finiteness guarantees that such learning is possible. We then obtain upper and lower bounds on sample complexity that match up to logarithmic factors in the worst case for every fixed finite $L\ge \ell$. At a fixed sufficiently high success probability and for sufficiently small $ϵ$, the required number of examples grows, up to logarithmic factors, linearly with this "dimension” and with $1/{ϵ}^{\ell }$, where $ϵ$ is the desired error. We also obtain a separation between exact and ambiguous labels, by exhibiting a single class for which exact training labels allow learning from $O_{\ell }(1/ϵ)$ examples, while ambiguous labels require ${\Omega }_{\ell ,L}(1/{ϵ}^{\ell })$ examples. Finally, when training label sets omit the correct label with probability $\rho$, we achieve error at most $\rho +ϵ$ with high probability, without knowing $\rho$, by allowing prediction width $O({\ell }^2/ϵ)$ and using a sample size nearly linear in $1/ϵ$ at fixed dimension and confidence. Under the weaker assumption of finite $\ell$-list DS dimension alone, the worst-case necessary and sufficient prediction width is $\Theta ({\ell }^2/ϵ)$, with absolute constants, for sufficiently small error and sufficiently high fixed success probability.