A Characterization of Multioutput Learnability
This provides a foundational theoretical result for researchers in machine learning theory, addressing learnability in multioutput settings, but it is incremental as it extends existing single-output characterizations.
The paper tackles the problem of characterizing learnability for multioutput function classes in batch, online, and bandit feedback settings, showing that learnability is equivalent to each single-output restriction being learnable, providing a complete characterization for multilabel classification and multioutput regression.
We consider the problem of learning multioutput function classes in the batch and online settings. In both settings, we show that a multioutput function class is learnable if and only if each single-output restriction of the function class is learnable. This provides a complete characterization of the learnability of multilabel classification and multioutput regression in both batch and online settings. As an extension, we also consider multilabel learnability in the bandit feedback setting and show a similar characterization as in the full-feedback setting.