Multitask Learning via Shared Features: Algorithms and Hardness

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 textrmpoly(k/γ) samples-per-task and textrmpoly(klog(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.