Multitask Learning via Shared Features: Algorithms and Hardness. (arXiv:2209.03112v1 [cs.LG])

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 $\gamma$, which is based on a simultaneous boosting
technique and requires only $\textrm{poly}(k/\gamma)$ samples-per-task and
$\textrm{poly}(k\log(d)/\gamma)$ samples in total.

In addition, we prove a computational separation, showing that assuming there
exists …

algorithms arxiv features multitask learning