A Characterization of Multioutput Learnability
Authors: Vinod Raman, Unique Subedi, Ambuj Tewari
JMLR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. Our proof techniques, however, do not extend naturally to the case when K is infinite. So, characterizing learnability for an infinite-dimensional target space is an interesting open problem. Moreover, our reductions are computationally inefficient and lead to sub-optimal sample complexities and regret bounds. As such, we leave the construction of efficient and optimal multioutput learning algorithms as an interesting direction for the future work. |
| Researcher Affiliation | Academia | Vinod Raman EMAIL Department of Statistics University of Michigan Ann-Arbor, MI 48109, USA Unique Subedi EMAIL Department of Statistics University of Michigan Ann-Arbor, MI 48109, USA Ambuj Tewari EMAIL Department of Statistics Department of Electrical Engineering and Computer Science University of Michigan Ann-Arbor, MI 48109, USA |
| Pseudocode | Yes | Algorithm 1 Agnostic learner for F with respect to ℓ, Algorithm 2 Agnostic learner for F1 with respect to ψ1 d1, Algorithm 3 Expert(b, φ), Algorithm 4 Agnostic online learner Q for F with respect to ℓ, Algorithm 5 Expert(b, φ), Algorithm 6 Online learner Q for F1 with respect to ψ1 d1, Algorithm 7 Agnostic PAC learner for H, Algorithm 8 Expert(b, φ), Algorithm 9 Online learner Q for H with respect to 0-1 loss |
| Open Source Code | No | The paper does not contain any statements about releasing code or links to source code repositories. It mentions leaving the construction of efficient and optimal multioutput learning algorithms as an interesting direction for future work, implying current algorithms are conceptual. |
| Open Datasets | No | The paper is theoretical and does not refer to any specific datasets, nor does it provide any links or citations for data access. |
| Dataset Splits | No | The paper is theoretical and does not refer to any specific datasets or their splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide specific details about experimental setup, hyperparameters, or training configurations. |