Multitask Learning via Shared Features: Algorithms and Hardness

Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan Ullman, Lydia Zakynthinou
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:747-772, 2023.

Abstract

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 $\mathrm{poly}(k/\gamma)$ samples-per-task and $\mathrm{poly}(k\log(d)/\gamma)$ 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-bairaktari23a, title = {Multitask Learning via Shared Features: Algorithms and Hardness}, author = {Bairaktari, Konstantina and Blanc, Guy and Tan, Li-Yang and Ullman, Jonathan and Zakynthinou, Lydia}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {747--772}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/bairaktari23a/bairaktari23a.pdf}, url = {https://proceedings.mlr.press/v195/bairaktari23a.html}, abstract = {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 $\mathrm{poly}(k/\gamma)$ samples-per-task and $\mathrm{poly}(k\log(d)/\gamma)$ 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.} }
Endnote
%0 Conference Paper %T Multitask Learning via Shared Features: Algorithms and Hardness %A Konstantina Bairaktari %A Guy Blanc %A Li-Yang Tan %A Jonathan Ullman %A Lydia Zakynthinou %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-bairaktari23a %I PMLR %P 747--772 %U https://proceedings.mlr.press/v195/bairaktari23a.html %V 195 %X 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 $\mathrm{poly}(k/\gamma)$ samples-per-task and $\mathrm{poly}(k\log(d)/\gamma)$ 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.
APA
Bairaktari, K., Blanc, G., Tan, L., Ullman, J. & Zakynthinou, L.. (2023). Multitask Learning via Shared Features: Algorithms and Hardness. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:747-772 Available from https://proceedings.mlr.press/v195/bairaktari23a.html.

Related Material