← All papers

Select, Do Not Vote: Optimal List PAC Learning and Exact Transduction

Abstract

List learning permits a classifier to return $\ell$ labels and counts a prediction as correct when the target appears anywhere in the list. Its realizable sample complexity is characterized qualitatively by the $\ell$-DS dimension $d$, but every known quantitative bound carries list-size dependence beyond $d$. We remove it. For every class of finite $\ell$-DS dimension $d$, a randomized learner uses $O \left(\frac{d+\log(1/\delta)}{\varepsilon}\right)$ samples. The algorithm does not aggregate lists. It samples a logarithmic number of prefix one-inclusion predictors and uses a fresh validation block to select one. This turns a high-probability average-risk inequality into a single list predictor without the $\ell+1$ loss of Top-$\ell$ voting. The rate is minimax sharp, uniformly in $\ell$. The lower bound uses functions with at most $d$ nondefault coordinates over $2\ell+1$ labels. We also solve fixed-design list transduction exactly. If $\mu_\ell$ is maximum excess hyperedge density, optimal randomized risk is $\mu_\ell/m$, while optimal deterministic risk is $\lceil\mu_\ell\rceil/m$. A one-coordinate class separates them by the sharp factor $\ell+1$. This is the list-valued extension of the Hall-complexity characterization for ordinary multiclass transduction. The same excess calculation strengthens the known i.i.d. transductive lower bound by $\ell+1$. List length can still reduce $d$, sometimes dramatically, but it creates no additional polynomial price once $d$ is fixed.

Keywords: list learning, PAC learning, DS dimension, transductive learning, one-inclusion graph, sample complexity

Full text (PDF) · source repository · doi:10.5281/zenodo.21885814