Thank you for taking the time to review and for the positive feedback. Hopefully, the following will help answer your questions and provide additional context to address any lingering concerns you might have.

Summary of contributions

First, on a high level, we would like to clarify the goal of this paper: our results shed light on the fundamental differences between single-objective and multi-objective learning (MOL), rather than proposing an algorithm to be used for MOL in practice. The results and proofs should help us gain valuable intuition for leveraging “structure” in multi-objective learning and connect it explicitly to common intuition in single-objective learning - something that has not yet been clearly established in previous works. While we agree that it would be very interesting to empirically and theoretically explore more general settings - including deep learning and larger scale data and experiments - we argue that our results under the current assumptions (standard in classical statistical learning theory) are a valuable first step in building missing intuition on MOL.

In particular, we are able to gain first insights on the following questions: how many (unlabeled or labeled) samples are needed when we aim to simultaneously minimize risks on multiple distributions, and how do unlabeled samples help? How do the sample complexities depend on the function classes that “solve” individual learning problems (in our paper $\mathcal{H}_k$) and the function class that is “necessary” for achieving good trade-offs (in our paper $\mathcal{G}$), and how do they depend on the loss functions? We’d be happy to explore in future work whether the insights may carry over in a similar way to neural network training and large-scale experiments.

Implications for real-world settings.

A significant limitation of existing theory is that it doesn’t really help practitioners decide which architecture/model class to use (beyond the usual consideration that more complex model classes may require more data). For single-objective learning, the choice of architecture in practice often incorporates strong priors hard-earned from experience (e.g., specific domain knowledge, or more general knowledge that certain architectures work well for certain types of data). But which model class should the practitioner choose in the multi-objective setting, especially if there are distinct priors for each task? This might be one of the first questions a practitioner faces, yet existing theory cannot answer this.

The simple, but important, point that we make is that in MOL, the choice of model class no longer only serves to incorporate our prior knowledge about individual learning tasks, but it must also enable good trade-offs across those tasks. This dual role is elided in the earlier formulations of MOL, and so these questions about which model classes should be used cannot be answered there. Thus, our work reopens, or at least refines, the MOL problem in a way that is crucial for practice. It enables us to ask whether and how prior/domain knowledge about the individual tasks can be leveraged for learning good trade-offs across all tasks.

Testing assumptions and additional experiments.

Most of the assumptions made in our work are easily verified in practice: Assumptions 1, 2, 4, 5, and 6 are completely verifiable through the design choices of the practitioner. However, testing the distributional assumptions (including Assumption 3) under which the pseudolabeling algorithm enjoys its guarantees is hard: even the most basic assumptions, such as independence and identical distribution of the data, are essentially impossible to test on real-world data (or, such tests require assumptions themselves). This is a caveat most learning theory faces, and indeed has sparked the whole field of testable learning.

At the same time, we would like to mention that we have also performed additional experiments on classification and non-parametric regression problems that confirm our findings. Unfortunately, we may not post any anonymized links or figures here.

Impact of label noise.

The problem of label noise is central to our work, and incorporating the error of having imperfect labels constitutes one of the main technical contributions of our work. The algorithm that we analyze consists of two stages: first, learning a separate model per task, and then using these models to pseudolabel the unlabeled data, on which the models that trade-off the different tasks are trained. Because the models from the first stage are imperfect, its labels indeed introduce a label shift. One of the main contributions of the proofs of Theorems 1 and 2 is to show how this label shift affects the models trained in the second stage, which requires non-standard tools. In our final bounds, the effect of this label shift is represented by the Rademacher complexity of $\mathcal{H}_k$: the larger the complexity, the larger the (expected) label shift, and the worse the bound. Consequently, to be able to learn with vanishing trade-off errors, the prediction error of the task-specific models, and hence also of the label shift, needs to vanish - otherwise there will remain an irreducible error even with infinite unlabeled data.

Effect on the Pareto front as a function of unlabeled data.

In general, having more unlabeled data allows the model class to be larger, because it reduces the variance of the MOL problem. Hence, the Pareto front will move more towards the optimal solutions. And in the limit, we recover what is known as the ideal semi-supervised setting. The effect of unlabeled data over purely supervised methods can be observed empirically, for example, in Figure 3. Moreover, we plan to include a new experiment in the updated manuscript where we keep the number of labeled datapoints fixed and vary the number of unlabeled datapoints, and plot the varying Pareto fronts of the pseudolabeling algorithm. Again, unfortunately, we may not post any anonymized links or figures here.

As we were somewhat unsure whether the reviewer’s question was aimed in this direction, we would kindly ask the reviewer to clarify their question if any unclear points remain.

We thank reviewer n4Vo for the thoughtful review. We appreciate that the reviewer thought that our work makes a solid theoretical contribution to a novel problem that is of interest to the learning theory community.

Summary of contributions

First, on a high level, we would like to clarify the goal of this paper: our results shed light on the fundamental differences between single-objective and multi-objective learning (MOL), rather than proposing an algorithm to be used for MOL in practice. The results and proofs should help us gain valuable intuition for leveraging “structure” in multi-objective learning and connect it explicitly to common intuition in single-objective learning - something that has not yet been clearly established in previous works. While we agree that it would be very interesting to empirically and theoretically explore more general settings - including deep learning and larger scale data and experiments - we argue that our results under the current assumptions (standard in classical statistical learning theory) are a valuable first step in building missing intuition on MOL.

In particular, we are able to gain first insights on the following questions: how many (unlabeled or labeled) samples are needed when we aim to simultaneously minimize risks on multiple distributions, and how do unlabeled samples help? How do the sample complexities depend on the function classes that “solve” individual learning problems (in our paper $\mathcal{H}_k$) and the function class that is “necessary” for achieving good trade-offs (in our paper $\mathcal{G}$), and how do they depend on the loss functions? We’d be happy to explore in future work whether the insights may carry over in a similar way to neural network training and large-scale experiments.

Beyond Rademacher complexities

We acknowledge the reviewer’s main reservation: indeed, as our analysis is developed using tools from classical learning, it necessarily inherits their limitations. Namely, current learning theory significantly lags behind and does not satisfactorily explain the practical successes of modern, over-parametrized models.

We’d like to emphasize again that we are very careful in the paper not to claim that our results show that the pseudo-learning algorithm is effective in practice (where the assumptions may indeed be too restrictive). In particular, we deliberately opted not to include any neural network experiments, since our theory is not aimed at informing deep learning settings (for which bounds with Rademacher complexities can indeed be insufficient).

We agree that it would be of great practical significance to obtain generalization bounds that meaningfully apply to these modern ML models, and particularly for the multi-objective learning setting. Even more modestly, from just a theoretical perspective, we think that the suggested direction is definitely worth pursuing: to develop our results based on alternative complexity measures, such as the all-layer margin from [D] and the suggested work [E]. We suspect it would lead to quite different tools and bring additional insight about the nature of MOL. On the other hand, we feel that not only is this alternate approach substantial enough to merit its own paper, but that our work as is already makes a significant and fundamental contribution to MOL.

Practial implications of our work

In our view, one important contribution is the following simple, almost obvious, insight: the choice of model class needs to play a dual role of fitting individual tasks and enabling trade-offs across tasks. However, as discussed within our paper’s introduction, this distinction is not captured in existing theoretical frameworks. And so, under the frameworks of earlier works, it is not possible to ask how can priors for individual tasks be incorporated into the multi-objective learning problem. This is a practically-motivated question; after all, we often have strong priors about which models work well for specific learning tasks in practice.

Another important contribution is our two-fold discovery that (a) having strong priors for the individual tasks does not automatically imply benefits for MOL, even with infinite unlabeled data, but that nonetheless, (b) this fundamental barrier can be overcome if we measure performance via more “informative” losses. From here, we established the first results showing how to incorporate priors about individual tasks into the learning problem (via simpler model classes $\mathcal{H}_k$), and when/how these priors can significantly reduce labeled sample complexity in MOL.

Relationship to SSL and MTL.

Thank you for the question about related work on semi-supervised learning (SSL) and multi-task learning (MTL). Some of this is presented with a fair amount of detail in Appendix A.1, which provides a discussion and comparison of both lines of research. Please let us know if you see any blind spots or gaps we may have in covering related literature. The overview of different sample complexities in our response to reviewer eRZf may also be helpful. Let us also summarize the main differences between the SSL and multi-task learning settings and our multi-objective setting here.

Whether unlabeled data can help in the single-objective semi-supervised learning setting is quite nuanced, and usually requires some notions of “clusterability” or “compatibility”, see for example [9,15,45]. Roughly speaking, when the marginal does not carry any information about the conditional labels, unlabeled data cannot help. Our results, on the other hand, hold regardless of whether such clusterability or compatibility conditions hold: in MOL, unlabeled data enables estimating the likelihood of a given sample under each task, helping the model to make desired trade-offs corresponding to the task preferences/weights, even when the covariate does not inform the labels at all. If the likelihood of a sample is higher under one task than another, a model with a good trade-off prioritizes that task.

As discussed in Appendix A.1, the goal of MTL is fundamentally different from the multi-objective learning setting (albeit the names being misleadingly similar). MTL aims to learn multiple models, one model per task, and in doing so, exploit relatedness between tasks to improve sample complexity. Specifically, at inference time in MTL, we are allowed to predict a different label per task, whereas in MOL, we have to commit to one label for all tasks. This is related to the collaborative learning setting.

Because of these fundamental differences, the sample complexities of MTL and SSL are incomparable to our $\mathcal{S}$-MOL problem setting. Nevertheless, from a methodological point of view, our pseudolabeling algorithm is inspired by the standard SSL pseudolabeling approach, and linked to other methods such as mixture-of-experts, discussed in more detail in Appendix A.1.

Assumption 6.

We would like to clarify that the assumption that the function class is star-shaped/convex does not imply a linear function class. For example, the class of Lipschitz continuous functions on $[0,1]$ discussed in Appendix B.2 is convex (and hence star-shaped around every element), but Lipschitz continuous functions need not be linear. It is also standard to assume in learning theory to obtain localization results (e.g. Section 13.2 in [46]).

Negative result.

In some sense, we want the negative result given by Proposition 1 to have as little relevance as possible in the real world: that would mean that we can hope to practically achieve MOL. The role of this lower bound (and probably of most lower bounds in general) is to illuminate where the fundamental barriers are, in this case, to multi-objective learning. In particular, Proposition 1 reveals the importance of the choice of loss function in MOL. If the loss is “uninformative” like the zero-one loss, then it can be impossible to leverage strong priors for the individual tasks for the multi-objective goal of making good trade-offs. This motivated our consideration of more “structured” losses, where we discovered that Bregman losses sidestep this barrier. Happily, and as the reviewer notes, this is a general class of losses, broadly used in practice. Note that this is only one way that additional “structure” in MOL allows us to leverage the benefits of unlabeled data. Such lower bounds help us know where to look for other types of structure for future research directions.

We hope these discussions clarify any remaining concerns and encourage the reviewer to ask any further clarifying questions if necessary.

[D] Wei, C., & Ma, T. (2019). Improved sample complexities for deep networks and robust classification via an all-layer margin.

[E] Wei, C., Shen, K., Chen, Y., & Ma, T. (2020). Theoretical analysis of self-training with deep networks on unlabeled data.

Thank the authors for their comprehensive rebuttal, my previous concerns are mostly satisfied. Nevertheless, as authors have acknowledged - currently the theoretical contributions from this paper might have limited impacts to cutting-edge research - that being said, this is perhaps a common drawback.

I will maintain my evaluation as positive and not consider further increase the score.

We thank reviewer eRZf for the detailed, positive review and the valuable feedback. Thank you also for the suggestions on how to improve clarity; we will continue to work on improving our exposition. We’d like to address the questions and clarify our contributions.

Summary of our contributions.

First, on a high level, we would like to clarify the goal of this paper: our results shed light on the fundamental differences between single-objective and multi-objective learning (MOL), rather than proposing an algorithm to be used for MOL in practice. The results and proofs should help us gain valuable intuition for leveraging “structure” in multi-objective learning and connect it explicitly to common intuition in single-objective learning - something that has not yet been clearly established in previous works. While we agree that it would be very interesting to empirically and theoretically explore more general settings - including deep learning and larger scale data and experiments - we argue that our results under the current assumptions (standard in classical statistical learning theory) are a valuable first step in building missing intuition on MOL.

In particular, we are able to gain first insights on the following questions: how many (unlabeled or labeled) samples are needed when we aim to simultaneously minimize risks on multiple distributions, and how do unlabeled samples help? How do the sample complexities depend on the function classes that “solve” individual learning problems (in our paper $\mathcal{H}_k$) and the function class that is “necessary” for achieving good trade-offs (in our paper $\mathcal{G}$), and how do they depend on the loss functions? We’d be happy to explore in future work whether the insights may carry over in a similar way to neural network training and large-scale experiments.

On our assumptions.

Let us clarify our assumptions and how they might be extended. In general, we tried to formulate our results as general as possible, and our assumptions each play an important role.

• Assumption 1: The focus of our paper is the juxtaposition of easy individual tasks and potentially hard to learn trade-offs. We argue that Assumption 1 is a natural way to model this setting, and can also be viewed the other way around: given the classes $\mathcal{H}_1,\dots,\mathcal{H}_K$, how large can we choose $\mathcal{G}$? Moreover, the assumption can easily be extended to a misspecified setting using irreducible approximation errors.

• Assumption 2, strong convexity and KL divergence: The assumption that the potentials are strongly convex immediately holds for “generalized” strong convexity (w.r.t. other norms besides $\ell_2$) whenever they are norm-equivalent to $\ell_2$ (and from functional analysis, all norms are indeed equivalent in finite-dimensional space). For example, the potential associated with the KL divergence $\phi(y) = \sum y_i \log y_i$ is not only strongly convex with respect to the $\ell_1$-norm, but also the $\ell_2$-norm on the simplex (this follows, for instance, from Pinsker’s inequality [B]). Perhaps the more subtle issue is that for other potentials, the norm equivalence constant may depend on the dimension of the label space, and so an interesting question is whether it is possible to prove bounds that are independent of the label space dimension for strongly convex potentials under such norms.

• Assumptions 4-6: These assumptions are standard and (essentially) necessary for localization, see, for instance, Section 14.3 in [46]. If they do not hold, usually, other assumptions need to replace them to achieve fast rates, e.g. [21].

We’ll add a discussion on which losses satisfy these assumptions to clarify the full extent of our results.

Scalarizations.

We’d like to stress that, while our second main result, Theorem 2 (fast rates under stronger assumptions), is restricted to linear scalarization, our first main result, Theorem 1 (slow rate but more general), applies to broad classes of scalarizations, importantly including the Tchebycheff scalarization. It would be extremely interesting, but quite non-trivial, to extend Theorem 2 to general, non-linear scalarizations.

Beyond Bregman losses.

While Bregman losses encompass a large family of important losses, we agree that an important and very interesting next direction is to study non-Bregman losses; especially losses, such as the hinge loss, that are commonly used in practice. And indeed, we have discovered settings where there are potential benefits to semi-supervision for non-Bregman losses, but so far they’ve required substantially stronger assumptions and more specialized algorithms. In fact, in some sense, Algorithm 1 works if and only if the losses are Bregman, due to Theorem 12 in [C].

Overview of sample complexities and existing works.

For readability, let us summarize the label complexities from prior work and derived in our work for VC (subgraph)-classes with dimensions $d_{\mathcal{G}},d_{\mathcal{H}}$ of $\mathcal{G}$ and $\mathcal{H}_k=\mathcal{H}$. But note that our results are much more general.

In the supervised MDL setting, the sample complexity is of order $(d_{\mathcal{G}}+K)/\epsilon^2$ under adaptive sampling (see related works). For non-adaptive sampling, however, it is $Kd_{\mathcal{G}}/\epsilon^2$, see [52]. In the supervised $\mathcal{S}$-MOL setting the sample complexity also is $Kd_{\mathcal{G}}/\epsilon^2$ (see discussion before Prop. 1 and App. A.2).
The single-objective semi-supervised learning setting is more nuanced because the degree to which unlabeled data can improve upon just using the labeled data usually requires some notions of “clusterability” or “compatibility” (e.g., margins, or disagreement in co-training), see [9,15,45] and [A] for an overview. But in the worst case, its label complexity is $d_{\mathcal{G}}/\epsilon^2$ (i.e., unlabeled data cannot help). Similarly, the sample complexity of multi-task learning is lower than that of learning each task separately only under additional assumptions.

Our work establishes that in the semi-supervised $\mathcal{S}$-MOL setting with zero-one loss, the label complexity remains $Kd_{\mathcal{G}}/\epsilon^2$ in the worst case, whereas for Bregman losses it is $Kd_{\mathcal{H}}/\epsilon^4$ or $Kd_{\mathcal{H}}/\epsilon$ depending on the strength of the assumptions. We will include a table of sample complexities in the updated paper.

[A] Balcan, M. F., & Blum, A. (2006). An augmented PAC model for semi-supervised learning.
[B] Yu, Y. L. (2013). The strong convexity of von Neumann’s entropy. Unpublished note, 15.
[C] T. Heskes. Bias-variance decompositions: the exclusive privilege of Bregman divergences.

We thank reviewer McKt for the positive and helpful review. Let us address the question - for a clarification of our contributions, we refer to the summary of contributions section in the rebuttal of reviewer eRZf.

Summary of contributions

First, on a high level, we would like to clarify the goal of this paper: our results shed light on the fundamental differences between single-objective and multi-objective learning (MOL), rather than proposing an algorithm to be used for MOL in practice. The results and proofs should help us gain valuable intuition for leveraging “structure” in multi-objective learning and connect it explicitly to common intuition in single-objective learning - something that has not yet been clearly established in previous works. While we agree that it would be very interesting to empirically and theoretically explore more general settings - including deep learning and larger scale data and experiments - we argue that our results under the current assumptions (standard in classical statistical learning theory) are a valuable first step in building missing intuition on MOL.

In particular, we are able to gain first insights on the following questions: how many (unlabeled or labeled) samples are needed when we aim to simultaneously minimize risks on multiple distributions, and how do unlabeled samples help? How do the sample complexities depend on the function classes that “solve” individual learning problems (in our paper $\mathcal{H}_k$) and the function class that is “necessary” for achieving good trade-offs (in our paper $\mathcal{G}$), and how do they depend on the loss functions? We’d be happy to explore in future work whether the insights may carry over in a similar way to neural network training and large-scale experiments.

Separation of labeled and unlabeled data.

The question of whether the separation of unlabeled and labeled data in Theorems 1 and 2 is fundamental to the problem or part of the PL-MOL algorithm is interesting and a good opportunity to reiterate the main point of our work:

That the label complexity depends only on $\mathcal{H}_k$ and the unlabeled complexity only on $\mathcal{G}$ seems to be fundamental for the setting/assumptions we consider. Because, to recover the entire Pareto front, we need to be able to solve each individual learning task, the labeled sample complexity on $\mathcal{H}_k$ is unremovable (as we’ve assumed $\mathcal{H}_k$ is contained in $\mathcal{G}$). Then, the remaining question is whether we can reduce the dependence of unlabeled sample complexity on $\mathcal{G}$. In general, this is also not possible. For example, consider the case that we are given the Bayes optimal predictors for each task; then no labeled data is necessary, but there is still a need for unlabeled data to learn how to make trade-offs over $\mathcal{G}$. This necessity for unlabeled data was also exemplified in [47] (see Proposition 5).

Also note that one viable approach may be to reuse the labeled data by discarding the labels and pooling it with the unlabeled data. This may help in practice, but it does not change the order of the unlabeled sample complexity.