Multitask Learning via Shared Features: Algorithms and Hardness
This addresses the problem of efficient learning in multitask settings for researchers in computational learning theory, but it is incremental as it builds on existing attribute-efficient learning models.
The paper tackles the computational efficiency of multitask learning for Boolean functions with shared features, presenting a polynomial-time algorithm for halfspaces with margin that requires poly(k/γ) samples per task and poly(k log(d)/γ) total samples, and proves a computational separation showing that some concept classes cannot be multitask learned efficiently without super-polynomial time or more samples.
We investigate the computational efficiency of multitask learning of Boolean functions over the $d$-dimensional hypercube, that are related by means of a feature representation of size $k \ll d$ shared across all tasks. We present a polynomial time multitask learning algorithm for the concept class of halfspaces with margin $γ$, which is based on a simultaneous boosting technique and requires only $\textrm{poly}(k/γ)$ samples-per-task and $\textrm{poly}(k\log(d)/γ)$ samples in total. In addition, we prove a computational separation, showing that assuming there exists a concept class that cannot be learned in the attribute-efficient model, we can construct another concept class such that can be learned in the attribute-efficient model, but cannot be multitask learned efficiently -- multitask learning this concept class either requires super-polynomial time complexity or a much larger total number of samples.