On the sample complexity of semi-supervised multi-objective learning
Tobias Wegel, Geelon So, Junhyung Park, Fanny Yang
In multi-objective learning, a set of $K$ learning objectives $\mathcal{E}_1,\ldots, \mathcal{E}_K$ must be solved at once by a single model $g \in \mathcal{G}$. Although good trade-offs may only be available in a complex model class, it comes with a statistical cost: we show that, in the worst-case, the amount of _labeled_ data available from each task constrains how complex $\mathcal{G}$ can be, even if the learner has access to the individual Bayes optimal models and infinite amounts of unlabeled data. At the same time, for an important class of problems, we show that the complexity of $\mathcal{G}$ can come into play only in terms of _unlabeled_ data. We establish sample complexity upper bounds, showing when and how unlabeled data can significantly alleviate the need for labeled data. These rates are achieved by a simple, semi-supervised method via pseudo-labeling.