On the sample complexity of semi-supervised multi-objective learning
Authors: Tobias Wegel
Geelon So
Junhyung Park
Fanny Yang
Venue: NeurIPS 2025 spotlight ()
Keywords: multi-objective learning
statistical learning
optimization
Primary area: theory
TL;DR: we theoretically study when and how unlabeled data can help in multi-objective learning

Abstract: In multi-objective learning (MOL), several possibly competing prediction tasks must be solved jointly by a single model. Achieving good trade-offs may require a model class $\mathcal{G}$ with larger capacity than what is necessary for solving the individual tasks. This, in turn, increases the statistical cost, as reflected in known MOL bounds that depend on the complexity of $\mathcal{G}$. We show that this cost is unavoidable for some losses, even in an idealized semi-supervised setting, where the learner has access to the Bayes-optimal solutions for the individual tasks as well as the marginal distributions over the covariates. On the other hand, for objectives defined with Bregman losses, we prove that the complexity of $\mathcal{G}$ may come into play only in terms of unlabeled data. Concretely, we establish sample complexity upper bounds, showing precisely when and how unlabeled data can significantly alleviate the need for labeled data. This is achieved by a simple pseudo-labeling algorithm.

On the sample complexity of semi-supervised multi-objective learning
Tobias Wegel
Geelon So
Junhyung Park
Fanny Yang'
Department of Computer Science, ETH Zurich Department of Computer Science and Engineering, UC San Diego
Abstract
In multi- culti-obbjective learning (MOL), several possibly competing prediction tasks must be solved jointly by single model. Achieving good trade-off' may require a model class 9 with larger capacity than what is necessary for solving the individual tasks. This, in turn, increases the statistical cost, as reflected in known MOL bounds that depend on the complexity of g. We show that this cost is unavoidable for some losses, even in an idealized semi-supervised setting, where the learner has access the Bayes-optimal solutions for the individual tasks as well as the marginal distributions over the covariates. On the other hand, for objectives defined with Bregman losses, we prove that the complexity of may come into play only terms of unlabeled data. Concretely, showing precisely when and how unlabeled data can significantly alleviate the need for labeled data. This is achieved by simple pseudo-labelle algorithm.
establish sample complexity upper bounds,
Introduction
The multi-objective learning (MOL) paradigm has recently emerged to extend the classical problem of risk minimization from statistical learning to settings with multiple notions of risk [32, 19, 59, 27]. Multi-objective learning problems are ubiquitous in practice, it often matters how our models behave with respect to multiple metrics and across different populations. For example, consider designing a policy for self-driving car: the risks could measure different notions of safety (e.g.. safety of passengers or pedestrians), or safety under various conditions (e.g., different locations).
More formally, we study the MOL. setting with K population risk functionals RR,..., Rx. each quantifying an average, possibly different, loss l incurred by a prediction model over the data distribution pk The aim is to learn models from a class G that minimize all K excess risks Eg(g) := Ru (g) inf R& jointly, using only finite-sample access to the distributions. Here, inf R the Bayes risk of the Ath task, which is the smallest achievable risk over all measurable functions. Specifically, we study the sample complexity of learning the set of Pareto optimal models G. Recall that model is Pareto optimal in if any alternative model in & that reduces one risk necessarily increases another (see Definition 1); we often simply say that such model makes an optimal trade-off. Under mild conditions, the set of Pareto optimal models can be recovered by minimizing family of scalarized objectives T, that we call the s-trade-offs:
min T(()) = (g) Exx))..,,xx(()) (()) 9E9
SES
(1)
the s-trade-off achieved by
where the map K R is from some family S of scalarization functions that aggregates the excess risks into a single statistic. Notice that the excess risks were known, the problem in Eq. (1) would reduce family of classical (multi-objective) optimization problems [44, 54, 38). However, because the objectives in Eq. (1) depend on distributional quantities that are unknown, we need to
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

learn the solutions from data. Specifically, we study the sample complexity of achieving Eq. (1) up to errors E, > 0, a problem we call S-multi-objectivv learning. S-MOL for short (see Definition 2).
Two main lines of work have studied the sample complexity of MOL., both predominantly in the supervised framework. In the multi-distribution learning (MDL) literature [27, 4, 51, 73], the goal of the leamer is to recover a solution to Eq. (1) for one specific s-tradc-off induced by the scalarization s(v) m Ug. This yields the familiar min-max formulation of MOL. And in the literature for the general S-MOL setting [19, 59], the learner aims to solve Eq. (1) for multiple scalarizations. Both lines establish sample complexity bounds in terms of capacity measures of G, which can be shown to be tight in the worst case. However, solutions with good trade-offs may only be found in complex model class 9 even when individual tasks are easy to solve in smaller classes Hg. In such cases, previous worst-case results do not address whether it is really necessary to pay the full, supervised statistical cost of S-MOL over G. This motivates our consideration of semi-supervised multi-objective learning, in which the learner has access to both labeled and (cheaper) unlabeled data for each of the K tasks. In the single-objective setting, it well-known that access to unlabeled data can, at times, significantly reduce the amount of labeled data required [17. 70]. But for multi- objective learning, the sample complexity in a semi-supervised setting is largely unexplored, with only few exceptions [5, 65] that rely on additional assumptions for unlabeled data to be helpful (see Appendix A for a discussion of related works). Thus, the question we aim to address in this paper is
Given that each task k E [K] is solvable in a hypothesis class Hk. how much labeled and unlabeled data is needed to achieve trade-offs available in a larger function class G?
In this paper, we give holistic characterization of the conditions when unlabeled data can help and by how much. In terms of sample complexity upper bounds, we show that for a large class of losses, the capacity of G comes into play only in the amount of unlabeled data required, while the amount of labeled data merely depends that of ........ Hg. Moreover, show that these rates are achieved by a simple, pseudo-labelingg labeling-based algorithm. Concretely, our contributions are as follows:
We first show hardness of S-MOL under uninformative losses via a minimax sample complexity lower bound that holds even when the learner knows the Bayes-optimal models for each task and has access to the marginal distributions over unlabeled data, i... infinite unlabeled data (Section 3.1).
We then prove that risks induced by Bregman divergence losses-whice include the square and cross-entropy losses- effeeteefectively disentangle the multi-objective learning problem. For Bregman losses, information about individual risk minimizers significantly reduce labeled sample complexity in the semi- cumi-superiseed setting via a simple pseudo-labeling algorithm (Section 3.2).
Specifically, for S-MOL with Bregman losses, we first provide a uniform bound over the excess s-tradc-offss of the pseudo-labeling algorithm for bounded, Lipschitz losses via uniform convergence (Section 4.1). Our major technical contribution then lies in proving localized rates that distribution-speciffi under stronger assumptions (Section 4.2). Crucially, the labeled sample
complexity in both bounds only depends on the classes (H4 H unlabeled sample complexity.
K
k= while G only appears in the
Our analysis reveals an interesting insight: even though the pseudo-labeling algorithm is reminiscent of singlc-objective semi-supervisee learning procedures, the reason behind the benefits of unlabeled data turns out to be fundamentally different. In single-objective learning, unlabeled data can only help if, roughly speaking, the marginal carries information about the labels [13, 26, 76). Our results, in contrast, hold without any such assumptions. In multi-objective learning, unlabeled data helps the learner determine the relative importance of each test instance to each task: if the likelihood of an input is higher under one task than another, a model can accordingly prioritize the more relevant risk to achieve better trade-offs. This may be completely independent of the labels assigned by each task.
WWe scalarize the excess risks & because they each capture the suboptimality with respect to what is theoretically attainable when optimizing R. without consideration for other risks. Notice however that the Pareto set the excess risks & is the same the Pareto set the risks Rt. as they are equal up to the constants inf Rg.- We further motivate this in Section 2.2 and Fig. la. Contrary to Eq. (1), in the MDL literature, the risks usually directly scalarized.
2

---

2
Semi-supervised multi-objective learning
In this section, we formally introduce the semi-supervised S-multi-ojjective learning problem. For ease of reference, overview of notation is provided in Table 2 of Appendix F.
2.1 Preliminaries and the individual tasks
Let A' be the feature space, and y C Rs the label space. We are interested in K prediction tasks, indexed by k [K] := [I,.... , K over joint distributions pk of (X k y*) on the product space X' x V. We denote the underlying joint probability measure by IP. From each task, we observe i..dd. labeled samples {(X,, Y from Pk and N2 i.i.d. unlabeled samples {X²) Ji=1 from the marginal of pk on X, denoted PK. Let 'D denote the combined dataset of both labeled and unlabeled data. For each task l E [K], we define the population and empirical risks of function f X y as
Rx(1)= [G((",,
and R&(() = ThE
where lu : x y + R is a (not necessarily symmetric) loss function with (y 3) being the loss incurred by predicting ý when the true label is y. Further, we write Fall for the set of all functions f X + y for which all integrals in this paper are well-defined.FF For each & [K]. we assume access function class Hx S Fall that contains a population risk minimizer of Ras that is.
38" E Fall
such that
fū E arg min Rx( SEF
and ft E H4.
The risk that any model f X - y incurs is at least (& so focus attention achieving small excess risk with respect to the Bayes optimal predictor, defined as {f) == R2 (f) - (ft)
2.2 Pareto optimality and scalarization
In multi-objective learning, our aim to learn models g from some function class Ç that, ideally, achieve low excess risk on all tasks simultaneously. Since, by assumption, the individual tasks are optimally solved in Hr, we only consider hypothesis classes G C Fall that satisfy g 2 Ukeex: HA- But even G is very large, minimizing all excess risks may not be possible. In particular, in this work we do not assume that there exists one f X' > y that performs well across objectives (as opposed to the collaborative learning framework [14] or the setting in [5]). Instead, the aim is to recover the set of Pareto optimal solutions in the class G for the K objectives, formally defined as follows.
Definition 1 (Pareto optimality). Let E,....,& & be collection of excess risk functionals. We say that a function g E is Pareto optimal
there no other g' E E such that
and The subset of G containing all Pareto optimal functions is called the Pareto set. The subset of R containing the excess risk vectors of the Pareto set is called the Pareto front, defined as
3k [K] s.t. Ex(g') < (g(g)
Vj E (g) S E,(g).
3(G)= = ( (E) (g) g is in the Pareto set of G} C C
In words, any model in & that reduces one risk over a Pareto optimal model must increase another risk. Every Pareto-optimal model corresponds to distinct "preference" or "trade-off" all of which are equally valid from a decision-theoretic perspective [29]. We can quantify such trade-off's using scalarization functions R-K - R that, for all Fanl map the excess risks into scalar objective
To()) = =((E(())....x((()))
with
Js arg min To())
see also Eq. (1). We call Tf( the s-trade-off achieved by f. It has natural interpretation: recall that Eg(g,) is the cost incurred by the k-th task to make this particular type trade-off over myopically optimizing & Then, Tx(s,) aggregates these costs (see Fig. 1). This interpretation also further motivates scalarizing the excess risks instead of the risks: one task were have much higher Bayes risk than another, scalarizing the risks would not aggregate the additional cost, ef. Fig. la and [1].
3

---

attainable risks:
Ny. Ma
R2
E2
A1
E2
A1
A2
A2
(RAA)
((H()
((9)
(())
3 ((H2)
3(9)
(ff
F
F(
R4
&
(a) The attainable risks in each function (b) The larger G. the smaller (c) The larger G. the larger the ex- s-trade-off on the function class due high "variance".
class and one Tehebycheff scalarization of the minimal o-trade-off within G the risks and of the excess risks.
due low "bias".
(a) All attainable risks for the function classes Fall G. H1, H2. Using scalarizations on the risks directly can be misleading if the Bayes risk of task is much larger than that of another: have equal weight, the Tchebycheff scalarization (5) may inadvertently only solve one task (triangles); cf. [1]. Scalarizing the excess risks avoids this (dots). (b) The Pareto fronts for the classes H1, H2, Fan in the space of excess risks, and two Tehebycheff scalarizations sxxx (5) with different À (gray dashed line). with the corresponding trade-off minimizers (dots), and the gap to the minimizers in Fan (bi-directed red arrows). (c) The population and empirical Pareto fronts (G)) and (G). and the excess s-tradc-off of the estimated Pareto points (bi-directed red arrows) on the same two Tehebycheff scalarizations.
Figure I:
if both tasks
Two popular examples of scalarization families are Tchebycheff and linear scalarizations, defined as max (1) max A
Smax
X AEAK-I) Stin { (v)
Σ KE[K]
ARUR A A K-1
(5)
where A is the (K - -)-robbabylity simplex. They represent the worst-case and averaged notions of excess risks, respectively (see Fig. la for visualization of the Tchebycheff scalarization). Minimizing these families of scalarizations recovers the Pareto set under some conditions (e.g.. convexity for linear scalarization), see the detailed discussions in [47, 23, 44]. But of course, other scalarizations also exist [23]. Our most general result (Section 4. holds for monotonic scalarizations that satisfy the reverse triangle inequality and positive homogeneity, defined
Yo, E o0)
(Ak [K] t2 wx) = s(v) s(w),
Yu, w E RK
((v) s(w) S s(10) w1l
IUK
(6)
Ye E R a>00
s(av) = a s(v).
Both the linear and Tehebycheff scalarizations from Eq. (5) satisfy the properties in Eq. (6).
2.3 Multi-objective learning
Because inf Tg() may arbitrarily large, we evaluate our empirical estimates of gs using the excess s-frude-off, defined, for f E Fall, as T.()) - inf geg T. (g). The S-MOL. problem is then to achieve small excess s-trade-off across scalarizations with high probability.
inf
problem
Definition 2 (S-MOL). Let S be family of scalarizations
RRK IR. (Ex).Es family of positive real numbers, and 8 E (0, 1). Let A be an algorithm that, provided with dataset D and the function classes { and G. returns a family of functions {e. E S} C G. Then A solves the S S-multi-objective learning (S-MOL) problem with parameters ((5))eEs,6).
Vs S T.G..)
inf TT(g) Se, 2
(S-MOL)
SEG
where the probability is taken with respect to draws of the training dataset D.
From the population-level optimization perspective in Eq. (1), better trade-off's become possible as the class G grows. This is visualized in Fig. 1b, showing the Pareto fronts achieved by the function classes Fanl G, Hi, H2 in a two-objective setting. The separation between the Pareto front 3()) and the thcoretical optimum 3(Fan) can be seen as the "multi-objective bias" incurred in S-MOL

---

due to conservative choice of G. For two Tchebycheff scalarizations, the red bi-directed arrows in Fig. lb reflect this point-wise "bias". However, because the Pareto front needs to be learned from finite samples, we would also expect from classical learning theory that as 9 grows, so does the "multi-objeetive variance" of an empirical Pareto front (g). Fig. Ic illustrates this by the gap between (g) and (()), and for the same two Tehebycheff scalarizations, the red bi-directed arrows reflect the excess s-trade-off. In the next section we first address how much excess trade-off any algorithm necessarily incurs when learning F(G) from data.
3 Motivating Bregman losses: A hardness result
To answer this in the context of semi-supervised setting, we now argue that for the unlabeled data to help solve S-MOL, the structure of the loss functions is key.
3.1 A sample complexity lower bound for ideal semi-supervised S-MOL
Let us consider the class of PAC-learners for S-MOL, which are learners that achieve S-MOL for all distributions over X x y. For concreteness, consider multi-objective binary classification with zero-one loss, where S is the entire family of linear scalarizations Sin:
Definition 3 (Binary classification). Let & be a hypothesis class with VC dimension dg E N on a data domain X' x y' where y (0. 1). For each task & E [K], define la (y, D) = 1 # 7)-
For supervised S-MOL with E, = & for all E Sti. prior works achieve a sample complexity upper bound of O ((Kgg/s)) up to logarithmic terms, see [19, 59] and Corollary 1. In fact, matching lower bound of Ω2 Kdgg holds as well: after all, the set of s-trade-offs (T, : E S contains the individual excess risk functionals &,. and hence solving S-MOL requires the learner to solve the K' original tasks as well. The lower bound then follows from standard agnostic PAC-Iearning [57, Theorem 6.8]. In short, previous upper bounds are tight and the sample complexity of supervised S- MOL is O K Kgg/// /E" which also coincides with the sample complexity of MDL under non- aon-adaptvve sampling [73]. In the semi- supervspere S-MOL setting, the question now becomes: can the unlabeled data reduce the label complexity of this problem? Perhaps surprisingly, we now show that the same lower bound holds, even if the learner has additional access to Bayes optimal classifiers fī and the marginal distributions PX.
Proposition 1 (Hardness of semi-supervised multi -ulti-objective binary classification). Fix any K > 1 and any e E (0, 1/12). For a given tuple (P1 .p..... pk) denote by She a labeled dataset consisting of i...d. samples from pk, let f be Bayes optimal classifier of pk, and let P be the marginal distribution on X. Denote by A any algorithm that, given {S fū. Pk |K Hk=1 returns a set of classifiers [+. E G : & E Sin). If A achieves (S-MOL) with e, = E for all linear scalarizations s E Stin- 8 < 1/6, and for all distributions (PI... .P..... pk) ) in the multi-objective binary classification setting (Definition 3), then the total number of labeled samples it requires is at least | + |
d where C > 0 is a universal constant.
See Appendix D.1 for the proof. Proposition 1 shows that the label sample complexity lower bounds for supervised S-MOL cannot be improved for the problem in Definition 3-even in an idealized semi-supervised S-MOL setting where the learner has infinite unlabeled data and can perfectly solve the individual learning tasks. This effect is due to the zero-one loss not being a proper scoring rule, which is necessary for weighing the risks of two different tasks against each other. And indeed, other losses, such as the hinge or absolute deviation loss, suffer from the same problem. See also [62] for a discussion of calibration in multi-objective learning. In our main results, we show that this lower bound can be circumvented in learning settings where the loss functions are proper in this sense.
3.2 Bregman divergence losses and a pseudo-labeling algorithm
In this section, we introduce Bregman losses and their key property that allows us to leverage unlabeled data and alleviate labeled sample complexity via a pseudo-labeling algorithm.
Definition& 4 (Bregman loss). Let ) be convex. A loss é y x y - [0, co] is called a Bregman loss if there is a strictly convex and differentiable potential Φ : y - such that Ely. 7) = Φ(v)= o()) (Vo()) y 0)
5

---

Many standard prediction losses are Bregman losses. For example, the squared loss can be obtained by setting Φ(y) llvlig- the logistic loss by choosing p(v) log + (1 -- v) log(1 y), and the Kullback-Leibee divergence using Φ(v) = Ei= Vj log Vÿ. As we now show, an important fact that we will leverage about learning with Bregman loss is that the associated excess risk functional can be expressed in terms of its minimizer. To state it precisely, we introduce the notions of population and empirical risk discrepancies of function ʃ E Fan from some h E Hi. defined as:
No Ce
de(::))= = NE Σ
1
(7)
We further define for some h1 E Hi.....he hgg E HK and h = (hi,...,,hp ,,k the population and empirical scalarized risk discrepancies of function f E Fall from h as
de(f:h) h) = s(di(f:h)), ...., dx (f: hx)),
de(f:h)= s(āi(f:h1),...... (f.::i))...d((:hhh))) (8)
We now ready state Lemma I, proved in Appendix D.2.
Lemma (Properties of Bregman losses, based on [7]. For each k E [K], let l be Bregman loss with potential Φr. both E[ and [Y* are are finite, then up to almost sure equivalence,
(+)- == arg min R&( = E [Y =.]
and Vf E Fal, Ex( - du;)= (J:
JEFau
Along with Eqs. (4) and (8), Lemma implies T.(J) = ff: for f== (kk) Note that the second part of Lemma decomposes the risk into a task-specific intrinsic noise and a discrepancy term;
Algorithm 1 Pseudo-labeling (PL-MOL)
1: for k E [K] do
2: Compute 7ig = arg min Rr (h)
R&(s) = (ft) + du (f: fi). It turns out that Breg- man divergences are, up to transformation of the label space, the only loss functions that enjoy such a de- composition (see [28] and Appendix B). This decom- position helps justify the following greudo-labeling multi-objective learming algorithm (Algorithm 1).
3: end for
4: for s E S
5: Compute ga arg mingeg do(g; h)
6: end for
7: Return (ū. :
First, we minimize the individual empirical risks R2 over Hr to obtain h = (fi,..., Fxx). the set of empirical risk minimizers; thus, we estimate the task-wise Bayes-optimal models ft (Line 2). Giyen Lemma 1, we can then approximate the excess risks E via the empirical risk discrepancies dg hy) using unlabeled data. And so, the t-rrddc-off (.)-) can accordingly be approximated by dz h). The empirical estimate of the Pareto set in G is then given the minimizer of d, (-: h) in G (Line 5). Note that reusing the covariates of the labeled data in this second step would yield at most a constant gain.
Notice that the second step (Line 5) is equivalent to first pseudo-labeling all unlabeled data using the ERMs, and then passing it to the supervised S-MOL algorithm from [59] ("ERM-MOL", Algorithm discussed in Appendix A. Finally, note that from computational perspective, even if S is not finite, Algorithm can be implemented, e.g., using hypernetworks, see Appendix A.2.
3.3 Characterization of models with optimal trade-offs: A variational inequality
The lseudo-labeling method illustrates how one can estimate the s-trade-off solutions gs E 9 from both labeled and unlabeled data when the losses are Bregman divergences. We now show that Bregman losses also enable characterizing the minimizers Js via variational inequality in some cases. From this inequality, in turn, we can derive conditions for ga to have a particularly simple representation which sheds some light on why unlabeled data can help. Specifically, under linear scalarizations and convexity, we can show the following result.
Lemma 2 (Variational characterization of minimizers). For each & E [K], let lg be a Bregman loss siin is linear with weights X, and ps := Ek PrP Denote by (, the inner product defined as (f. = (x) du.(z). Then for every non-empty, convex and closed set G C Fall and convex g - Tg)
with potential Φs. Suppose
K
dPk
(g(g) = inf To(g') g'ESS
if and only if Vg's E 9:
Σ
N
V - ft) -9) 20
du,
where (g) denotes the function voo(o(z)) IfG is bounded, such a g E G exists.

---

Lemma 2 is a direct consequence of Lemma D.6 and Theorem 46 in [69]. From this lemma, we can derive the s-trade-off solutions 9s analytically in the special case where 9 Fall and all potentials are shared OR Φb In that case, since the set of feasible models is unconstrained, the variational wR (2) = Au dPx
inequality in Lemma holds with equality. In particular, the first argument of (ss')s must vanish, up to nı eugevviiaeeece. Thus, we can deduce that the s-trade-off solution is -a-..S. of the form
(x(2) = Σ (x(x))E(x), kE[R]
where
dps (x)
so that wy (z) is non-negative and ΣnE[K] (x(x)) = 1. In short, the optimal prediction with respect to the s-trade-off the instance E X' is convex combination of the individual Bayes optimal labels, cf. [40]. Additionally, if the marginals are shared P = Px. then each d X/djt=- = 1, so the weights wk are independent of However, these specific settings, and g, does not generally need to take this form. We will later make use of this specific form in Section 4.2.
Sample complexity upper bounds for pseudo-labeling
We now present uniform and localized upper bounds for Algorithm 1 for Bregman losses in terms of Rademacher complexities. Specifically, we use the coordinate-wise Rademacher complexity of a y y--valued function class H S Fall under distribution p with samples, which is defined
R (H)
E
sup kEH
Tighy (X:)
m1 711.-72
Rad
We discuss the choice and properties of this Rademacher complexity in Appendix E.2.
4.1 A uniform learning bound
We start with some assumptions on the loss functions lg that we require for our bounds.
Assumption (Regularity of the losses). For each E [K]. let &g be a Bregman loss satisfying:"
Its associated potential function Φx is pu-Strongly convex in y with respect E--norm, so that for all y. v' E V, it holds that (y v/) = (y) - (x (Von(y'), - 5o) Z t lly y/ 11.-
The loss is L Lipschitt continuous in both arguments with f--norm R2, that is, for all y. y 3" Y' it holds that |e(v. y') E(y, v²) S T. V/v - vl and |e()',v) E(y", v) I T Ill v 1l2-
The loss is bounded by some constant B₁ < la Be.
The boundedness enables the concentration bounds used in our results and a common assumption, and the strong convexity and Lipschitz continuity enable using vector contraction inequality from [41], as well as establishing a uniform approximation of the excess risks. Most Bregman losses satisfy Assumption 1 bounded domains D, while some (like the logistic loss) require careful treatment of Lipschitz continuity if the gradient is unbounded at the boundary of y (cf. Corollary C. and Lemma E) We now state our first main result.
Theorem 1. Suppose that Assumption I holds. Let S be any class of monotone scalarizations that satisfy the reverse triangle inequality and positive homogeneity in Eq. (6), and let {9s : E S} be the class of solutions returned by Algorithm 1. Then (S-MOL) holds for any 8 E (0, and E, s(E1,...,EK) where each ex bounded by
(log(K/0) N₂.
1/2
log (og(K/o) 1/2
5 Cs
3y Rt (9)
+ +V RR. (Hx)
(10)
71k
with C max(4Lk, V2B,, La /24Lx/ pe, LA La L6VBB//MET
strong convexity and Lipschitz continuity in the first argument can replaced by an arbitrary norm in Theorem 1. Replacing the norm of the Lipschitz continuity in the second argument in Theorem I entails using other vector Rademacher complexities, cf. Appendix E.2. They cannot be replaced in Theorem 2. Moreover, for results it sufficient for the Lipschitz property to hold the range of G.
'The norm
7

---

Theorem 1 is proved in Appendix D.3. Using VC bounds on the Rademacher complexity (see Lemma E.6), Theorem 1 implies that for VC (subgraph) classes & and H₂ H. with VC dimensions dg. dH, only ((Kx//=*) labeled and ((Kdg/E²) unlabeled samples are necessary to achieve e-excess -ff uniformly for all scalarizations. Comparing this with the sample complexity ((Kdg from Proposition 1, it is apparent that for Bregman losses, Algorithm can alleviate the label complexity of S-MOL significantly when dg > du, and completely eradicates its dependence on G. It shows that a large complexity of G can be compensated by large amount of unlabeled data NR, long R (g)
for N&= -> xc.
Also notice that, under Assumption 1, the map g + Eg(g) or its domain 9 can be non-convex, in which case non-linear scalarizations are necessary to reach the entire Pareto front. Theorem 1 applies to many such scalarizations, and in particular, the Tchebycheff scalarizations from Eq. (5).
4.2 A localized learning bound
The analysis in Theorem is crude: it estimates the excess risks on all of Hg and G, which why the global Rademacher complexities appear in the bound and the unusual extra square-root appears. Such an analysis can be overly conservative, and a localized bound can provide much tighter statistical guarantees [9, 36]. To facilitate a localized analysis for Algorithm 1, we require some additional assumptions. First of all, we only consider linear scalarizations, that is, S Sin from Eq. (5), mostly for the following norms to be Hilbert norms: for all & E [K], E Sjin, and f E Fan, define
| := E]x((* 112 and | = (I1AIP .l.f........ [(ffl())
We also require the following shape, strong convexity and smoothness assumptions. Assumption (Shape, strong convexity and smoothness). Recall that ft E arg min (x.()).
For all E [K]. the function classes Hd - ft are star-shaped around the origin; for all a E [o, 1]. if h E H₂ - fx. then ah E H2 fī. Moreover, the function class G is convex and closed.
For y 0 and all E S. Hi x ... HK. the map g (g h) > |1911 is convex on G.
For some v E o0), the second and third derivatives of the potentials Φx are bounded on Y' as supgey ( S v and sup,ey V (w)ll2 in the E2-operao norms.
The shape constraints are commonly used local Rademacher complexity proofs [9], and the strong convexity acts as a "multi-objective Bernstein condition" [9, 35]. Moreover, the convexity of G. strong convexity, and smoothness also enable a variational argument that is integral to the bound based on Lemma 2. To operationalize the smoothness, we assume well-specified setting:
Assumption 3. The minimizer of f + (J: f*) over Fan is contained in G for all e Finally, for refined version of our result, we also require the following norm- norm-equivalence assumption that allows relating errors in -noll,-norm to errors in -orm..
Assumption (Norm equivalence). All covariate distributions p are absolutely continuous with respect to the mixture distributions Ek d P for all si E S, and there a constant y) so that
dPk
vk
[K], slin S
sup d I AM
12 co.
Specifically, as proved in Lemma D.7, Assumption is equivalent to imposing Il. S 17 |1. for all k E [K] and s S. Sufficient conditions for Assumption 4 are that all weights of the scalarizations in S are bounded away from zero, or Pk < P and css sup & /dP I 17 for all k,j E [K].
We are now ready to state the localized bound. Recall that ft is the Bayes model for the kth task, cf. Eq. (3), and for any h = (bi...., 1xx) E Hi x... Hx, define 9 == arg mingeg (g; h), so that gs = " cf. Eq. (4). The result depends on the Rademacher complexities of the following sets of functions, defined using the balls Bl--I { E Fan [I/ll, < 1) as
Hr(r) (H,- fk) nr
and
Gu(r:h) = - 9.¹ nrB - Ill
(11)
sES
The excess o-trade-off is bounded in terms of the following critical radii, defined for each k E [K] as 4 = inf fr 2 0:r² Rh. (Ha(r))) and u = inf fr 2 20.r3 Rt. (Gu(r; {')} (12)
8

---

Critical radii like these are the key quantities of localized generalization bounds [9, 36]. They can be bounded using VC dimension (Lemma E.6) or with (generic) chaining [22, 61]. We define the worst- case critical radius in 9 by replacing f in the definition of ue with supremum over ground-truth functions h. 2 == suPnEH xxx inf {r 2 r 2 R%, (Gr(r; h.)]. ]. and then clearly "g S lik- Theorem 2. Let S C Sin be a set of linear scalarizations, and let Assumptions I to 3 hold. Then, if > 0 is sufficiently small, the output {ās E 3} from Algorithm satiisies (S-MOL) with probability 1 - ô and Eg = =sEE,...,,Ex' EK). where
Ek S Ca uug + l + (NE' + n log(4K/6))
(13)
and Ck = (V 0/)7²) max 12/12 7 + Bt/n, R/p2 + Be/pz). 4 If additionally Assumption 4 holds, then for I33 = supses (lp ..... (xx) and ns (sup.es (il//,....,,/mx)) we have
ok S Ck (uî + l3 + (NE + n log log(4K/)))
(14)
with C2 = C (ve/1)² max (Br/ux + 12)
The proof of Theorem 2 can be found in Appendix D.4. By comparing Eq. (10) with Eq. (13), we can see that, under the additional assumptions, Theorem yields much better rates than Theorem 1, whenever the critical radii are (much) smaller than the global Rademacher complexities. Effectively, Theorem 1 provides a "slow rate" analysis, while Theorem 2 provides a "fast rate" analysis. Addition- ally. Theorem avoids the "doubly slow rate" R ng (Ha))/² that appears in Theorem 1, and hence can potentially yield speed-up of power 4 over Theorem 1; e.g., if H. has VC (subgraph) dimension dx. the label complexity reduces order Ö(K dx//) /e) compared to the O(Kdx/=*) from Theorem 1.
In the setting where the algorithm has access to the marginals {P* J called the ideal semi- supervised setting [70], the proof of Theorem 2 also yields a slightly tighter bound than (13) (by combining Eqs. (32) and (36)). Under Assumptions 1 and 2, we obtain E. = s(E1,...,, with + (1 + diami-11, (Bx) + +1/122.
Ex S Che (LE + n log(2K/6)), where Cx
Adaptivity and weakening Assumption 4. While Eq. (13) depends the worst location of the true Pareto set Is in G (through úg), Eq. (14) refines this bound by also showing the adaptivity of the algorithm to the specific location of the true Pareto set 9s in G. Depending on the geometry of G, this set may lie in a "low complexity region" of G. If that is the case, then the radii ug can be smaller than u and the bound adapts to this low complexity. But this comes at cost: to prove Eq. (14), we require the norm equivalence from Assumption 4, and have to replace Ig by [s- Intuitively, the distance of I. to gs can only be controlled in the norm II-II.: in particular, if 0 O, then there no reason that g. should be close to 9s in the norm |1-11p. But ug defined through |1- has to bound the kth coordinate for all scalarizations s E S. making the norm equivalence from Assumption necessary. For finite sets of scalarizations, on the other hand, this can be avoided (but replaced by union bound), see Corollary A.2. Hence, there seems to be an inherent tension between controlling the error for all scalarizations simultaneously and proper adaptivity to the local complexity of the problem. It is interesting to explore this tension further.
5 Example: non-parametric regression with Lipschitz functions
We now exemplify the benefit of Theorem 2 in an example where the localized rates are much faster than unlocalized ones. More examples are presented in Appendix C.
Let X [0. 1 = [0, 1] and let lg be the square loss. Define for 0 < Lx < Lg the function classes
H = (4: [0, + (0, 1]: h is I=x-Lipschhtz) and G = {g- [0, 1] + [o, 1]: is I.g-Lipschiz). Fur-
thermore, let K = 2 and P& have a density pk on [0, 1] with respect to the Lebesgue measure. For Eq. (3) to hold, assume that there exist two functions ff; fā H for which |E| | x] = (x)
for all x E [0, 1]. We now apply Theorem 2 to obtain upper bounds for S-MOL in this setting.
Corollary 1. Let S C Sin be a set of linear scalarizations and assume the functions from Eq. (9) are LipLipschitz. Then the output {ā. : E St of Algorithm I satisfies (S-MOL) with probability 0.99 and E, = s(E1)...,,E,
,KK) where Ex S (Lm/n2)) 2/3 + (Lo/N.) 2/3 for all s E S.
We assume min (Le, pk) //2 2 1 for all l E [K]: otherwise, remove the squares on each ratio.

---

ERMMMOL (22
FL-MLL (ii
ERM-MOL (2g-100
Bayes model in for A (0.05.1)
dencity of fass
Boodd Ni mi m211
fixed may =
fbxed may 22, 22,N3 N)
100
0.75
cussittadll
10-4
10
0.50
06
04
10
10
0.
0.0
0.00
0.25
0.50
0.75
1.00
21
labeled
unlabeted sample m/t
unlabeled sample
Figure 2: On the left: one fit of the methods 5 labeled and 100 unlabeled samples with weights X (1/2, 1/2). the center: excess s-trade-off as function of labeled and unlabeled sample sizes for fixed weights = (1/2, We fix the unlabeled and labeled sample sizes to 2 and 2", respectively. On the right: the excess s-trade-off of PL-MOL as a function of unlabeled sample size N, while n4 = nt = NN₂ = 2 are fixed, and for varying weights. We repeat each experiment 10 times and show median, 20% and 80% quantiles.
The proof of Corollary can be found in Appendix C.3. Note that we recover the familiar minimax rate n 22/3 of Lipschitz regression. In comparison, the crude, unlocalized bound from Theorem 1 would yield the potentially much slower rates Li n4
-1/1 + 1/2 1 1/2 N
We illustrate Corollary in Fig. 2 on the following example: Let H be set of almost constant functions (that is, Lu = 0.2), and let fí = a and f = for two constants a, E [0. 1]. Minimizing (h) for the weights À (1/2, enough Lg. the solution in G becomes g. = (p1 a + p2b)/ + p2). On the left of Fig. 2, we show one data instance and the resulting models from Algorithms 1 and 2 when the densities pi (r) = 0.7 (20r) + 1 and p2 2 pl. In the center and on the right, we show the excess s-trade-off in this setting as function of sample size. We can the rates predicted by Corollary 1: when we fix the unlabeled sample sizes as large enough (N1 = N₂ = 212), PL-MOL achieves a small excess s-trade-off already for small labeled sample sizes. Mcanwhile, ERM-MOL requires labeled sample size to be of the same order 2 before it achieves a similar excess s- s-tradc-off. At the same time, if we fix the labeled sample size sufficiently large to learn the almost constant functions in H. only PL-MOL improves with an increasing number of unlabeled data. In both cases, the familiar n 22/3 -rate from Lipschitz regression is observable, as also predicted by Corollary 1. Finally, on the right of Fig. we see that if we keep all sample sizes fixed-excepp for N1- then the rates eventually bottlenecked by the harder task for all scalarizations; the risks stagnate at \2N2 2 x A2-
over H. yields the solution h, (a + b)/2 while for large
Discussion
This work studics when it is possible to mitigate the statistical cost of multi-objective learning, in which we illuminate the roles of unlabeled data and of the loss functions. This need arises because the function classes that contain models achieving good trade-offs may need to be much larger than those that well-suited for any one task. We show that for general losses, the label complexity of learning multiple trade-offs simultaneously in a class G is determined solely by the complexity of G. when the learner has full access to marginal distributions and the Bayes optimal models for each task (Proposition 1). But for Bregman losses, a simple pseudo-labeling algorithm can significantly reduce the label complexity (Theorem 1), where unlabeled data fully absorb the statistical cost of the expressive model class. Our analysis with local Rademacher complexities further refines these bounds (Theorem 2) and shows adaptivity of the algorithm under some conditions.
The key property that the pscudo-labeling algorithm exploits is the risk decomposition from Lemma I, which is unique to (generalized) Bregman losses [28]. Nevertheless, it is interesting to determine for exactly which losses the semi-supervised setting can improve upon the supervised one beyond Bregman losses. Under stronger assumptions, we provide first result of this kind in Appendix B.
Future work may also investigate the tension between controlling the errors of all scalarizations and adaptive rates, and in this context, whether Assumption 4 is really necessary (see discussion in Section 4.2). Moreover, would be interesting to relax structural assumptions in Theorem 2, e.g., by generalizing it to non-linear scalarizations, and to apply our framework to generative models.
10

---

Acknowledgements
Approximation/Ssimatio.. Transactions on We thank Konstantin Donhauser for helpful discussions. TW was supported by SNSF Grant 204439 and JP by SNSF Grant 218343. GS was partially supported by the NSF award CCF-21 12665 (TILOS), Energy. Office of Science, the Facebook Research from the CDC's Center for Forecasting and Outbreak
DARPA AIE program, the U.S. Department Award, as well as CDC-RFA-FT-23-00E Analytics. This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing.
References
[1] A. Agarwal and Zhang. Minimax regret optimization robust machine learning under distribution shift. In Proceedings of the Conference on Learning Theory (COLT), pages 2704 2729, 2022.
[2] C. D. Aliprantis and K. C. Border. Infinite dimensional analysis: hitchhiker's 's guide. Springer Science Business Mcdia, 2006.
[3] R. K. Ando, T. Zhang, and P. Bartlett. A framework for learning predictive structures from multiple tasks and unlabeled data. Journal of Machine Learning Research (JMLR), 6(11), 2005.
[4] P. Awasthi, N. Haghtalab, and F. Zhao. Open Problem: The Sample Complexity of Multi--Ditribution Learning for VC Classes. Proceedings of the Conference on Learning Theory (COL.T), pages 5943-5949, 2023.
[5] P. Awasthi, Kale, and Pensia. Semi-superrised group DRO: Combating sparsity with unlabeled data.
In Proceedings of the Conference on Algorithmic Learning Theory (ALT), pages 125-160, 2024.
[6] M.-F. Balcan and A. Blum. A discriminative model for semi-supervised learning. Journal of the ACM, 57(3):1-46, 2010.
[7] A. Banerjee, X. Guo, and H. Wang. On the optimality of conditional expectation a Bregman predictor. IEEE Transactions on Information Theory, 51(7):2664-2669, 2005.
[8] A. Banerjee, S. Merugu, S. Dhillon, and Ghosh. Clustering with Bregman divergences. Journal of Machine Learning Research (JMLR), 6:1795-1749, 2005.
[9] P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. Annals of Statistics, 33(4):1497-1537, 2005.
[10] P. I.. Barllett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research (JMLR), 3:463-482. 2002.
[11] P. L. Bartlett and S. Mendelson. Empirical minimization. Probubility theory and related fields, 135(3)3111 334, 2006.
[12] H. H. Bauschke and P. I.. Combettes. Convex Analysis and Monotone Operator Theory Hilbert Spaces. Springer Cham, edition, 2017.
[13] S. Ben-David, T. Lu, and Pál. Does Unlabeled Data Provably Help? Worst-case Analysis of Sample Complexity of Semi-Supervised Learning. In Proceedings of the Conference on Learning Theory (COLT), pages 33 44, 2008.
[14] A. Blum, N. Haghtalab, A. D. Procaccia. and M. Qiao. Collaborative PAC learning. Advances in Neural Information Processing Systems (NeurIPS), 30. 2017.
[15] G. Brown and R. Ali. Bias/Variance is not the Machine Learning Research (TMLR), 2024.
[16] C. Canonne, short note on an inequality between KL TV. arXiv preprint arX19:2202.07198 2022.
[17] O. Chapelle, Schölkopf, and A. Zien. Semi-Supervised Learning. MIT Press, 2006.
[18] L. Chen, H. Fernando, Y. Ying. and T. Chen. Three-way way trade-off in multi-objective learning: Optimization, generalization and conflict-an avoidance. Advances in Neural Information Processing Systems (NeurIPS). 36:70045 70093, 2023.
11

---

[19] C. Cortes, M. Mohri, J. Gonzalvo, and D. Storcheus, Agnostic learning with multiple objectives, Advances in Neural Information Processing Systems (NeurIPS), 33:20485-20495. 2020.
[20] I.. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer New York, edition, 1996.
[21] K. Dowd and D. Blake. After VaR: The theory, estimation, and insurance applications of quantile-based risk measures, Journal of Risk and Insurance, 73(2):193-222) 229, 2006.
[22] R. M. Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Anolysis, 1(3):900-330, 1967.
[23] M. Ehrgott. Multicriteria Optimization, volume 491. Springer Science & Business Media, 2005.
[24] D. J. Foster and Rakhlin. foc Vector Contraction for Rademacher Complexity. arXiv preprint arXiv:I911.06460 2019.
[25] Y. Freund and R. E. Schapire. A Deciisinn-thoortiie generalization of on on-line learning and an application to boosting, Journal of computer and system sciences, 55(1):119- 139, 1997.
[26] C. Göpfert, S. Ben-David, O. Bousquet, S. Gelly, Tolstikhin, and R. Urner. When can unlabeled data improve the learning rate? In Proceedings of the Conference on Learning Theory (COLT), pages 1500-1518, 2019.
[27] N. Haghtalab, M. Jordan, and E. Zhao. On-demand sampling: Learning optimally from multiple distribu- tions. Advances in Neural Information Processing Systems (NeurlPS), 35:406-419, 2022.
[28] T. Heskes. Bias-variance decompositions: The exclusive privilege of Bregman divergences. arXiv preprint arXiv:2501.1858/ 2025.
[29] C.-I.. Hwang and A. S. M. Masud. Multiple objective decision state-of-the-ar survey, volume 164. Springer Science & Business Media, 2012.
and applications: A
[30] T. Hytönen, J. Van Neerven, M. Veraar, and L. Weis. Analysis in Banach spaces, volume 12. Springer, 2016.
[31] K. M. Jablonka, G. M. Jothiappan. S. Wang. B. Smit, and B. Yoo. Bias free multiobjective active learning for materials design and discovery. Nature communications, 12(1):2312, 2021.
[32] Y. Jin. obleti-bjecttve machine learning, volume 16. Springer Science & Business Media, 2007.
[33] D. F. Jones and H. O. Florentino. Multi-objective optimization: Methods and applications. In The Palgrave handbook of Operations Research, pages 181-207. Springer. 2022.
[34] J. D. Kalbfleisch and R. L. Prentice. The statistical analysis of failure time data. John Wiley & Sons, 2002.
[35] V. Kanade, P. Rebeschini, and T. Vaskevicius. Exponential tail local Rademacher complexity risk bounds without the Bernstein condition. Journal of Machine Learning Research (JMLR), 25(388):1 2024.
[36] V. Koltchinskii. Local Rademacher Complexities and Oracle Inequalities in Risk Minimization. Annals of Statisticx, pages 2593-2656, 2006.
[37] Lee. Park. and Shin. Learning bounds sensisene learning. Advances in Neural Information Processing Systems (NeurlPS), 33:1 13137777-3887 2020.
[38] X. Lin, Z. Yang, X. Zhang. and Q Zhang. Pareto set learning for expensive multi-objective optimization. Advances in Neural Information Processing Systems (NeurIPS), 35:19231-112477 2022.
[39] Q. Liu, X. Liao, and L. Carin. Semi-supervised multitask learning. Advances in Neural Information Processing Systems (NeurIPS), 20, 2007.
[40] Y. Mansour, M. Mohri, and A. Rostamizadeh. Domain adaptation with multiple sources. Advances in Neural Information Processing Systems (NeurIPS), 21, 2008.
[41] A. Maurer. Bounds for linear multi-task learning. Journal of Machine Learning Research (JMLR), 7:117-139, 2006.
[42] A. Maurer. A vector-contraction inequality for Rademacher complexities. In Proceedings of the Conference Algorithmic Learning Theory (ALT), pages 3- 2016.
12

---

[43] C. McDiarmid, On the method of bounded differences. Surveys in combinatorics, 141 1989.
[44] K. Miettinen. Nonlinear multiobjectivv optimization, volume 12. Springer Science & Business Media,
1999.
[45] S. Mu and S. Lin. A comprehensive survey of mixture-of-cxpers: Algorithms, theory, and applications. arXiv preprint (XXXx:2503,07133 2025.
[46] A. I. Naimi and I.. B. Balzer. Stacked generalization: An introduction to super learning. European jomnpeannournda journal of epidemiology, 33:459-464, 2018.
[47] H. Nakayama, Y. Yun, and Yoon. Sequential Approxinate Multiobjective Optimization using Computa- tional Intelligence. Springer Science & Business Media, 2009.
[48] A. Navon, A. Shamsian, Chechik, and Fetaya. Learning the Pareto Front with Hypemetworks. In Proceedings of the International Conference on Learning Representations (ICLR), 2021.
[49] K. Nikodem and Pales. Characterizations of inner product spaces by strongly convex functions. Banach Journal of Mathematical Analysis, 5(1):83-87) 2011.
[50] J. Park and K. Muandet. Towards empirical process theory for vector-valued functions: Metric entropy of smooth function classes. Proceedings of the Conference on Algorithmic Learning Theory (ALT), pages 2116-260,, 2023.
[51] B. Peng. The sample complexity of multi-distribution learning. In Proceedings of the Conference on Learning Theory (COLT), pages 4185 4204, 2024.
[52] P. Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research (JMLR), 8(7), 2007.
[53] A. Roy, G. So, and Y.-A. Ma. Optimization Pareto On theory of multi-objective optimization. arXiv preprint arXiv:2308.00 02100000014555. 145, 2023.
[54] M. Ruchte and J. Grabocka. Scalable Pareto front approximation for deep multi-objective learning. In International Conference on Data Mining (ICDM), pages 1306-1311, 2021.
[55] M. Seeger. Learning with labeled and unlabeled data. Technical report, University of Edinburgh, 2001.
[56] B. Sen. A gentle introduction to empirical process theory and applications. Lecture Notes, Columbia University, 2018.
[57] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
[58] J. Snell, T. P. Zollo, Z. Deng. T. Pitassi, and R. Zemel. Quantile risk control: A flexible framework for bounding the probability of high-loss predictions. In Proceedings of the International Conference on Learning Representations (ICLR), 2023.
[59] P. Súkeník and C. Lampert. Generalization in Multi Aulti-Objective Machine Learning. Neural Computing and Applications, pages 1-15, 2024.
[60] M. Talagrand. Sharper bounds for Gaussian and empirical processes. Annals of Probability, pages 28-76.
1994.
[61] M. Talagrand. The generic chaining: Upper and lower bounds of stochastic processes. Springer Science Business Media. 2005.
[62] R. Verma, V. Fischer, and E. Nalisnick. On calibration multi multi-ddistrbbution learning. In Proceedings of the Conference on Fairness, Accountability, and Transparency (FAccT), pages 938 950, 2025.
[63] M. J. Wainwright. High-dimensional statistics: A non non-asymptotie viewpoint, volume 48. Cambridge University Press, 2019.
[64] K. Wang, R. Kidambi, R. Sullivan, A. Agarwal, C. Dann, A. Michi, M. Gelmi, Y. Li, Gupta, A. Dubey, et al. Conditional language policy: A general framework for steerable multi-objective finetuning. arXiv preprint arXi::2407.1576, 2024.
[65] T. Wegel, F. Kovačević, A. Tifrea, and F. Yang. Learning Pareto manifolds in high dimensions: How can regularization help? In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2025.
13

---

[66] D. H. Wolpert. Stacked generalization. Neural networks, 5(2):241-259 1992.
[67] N. Yousefi, Y. Lei, M. Kloft, M. Mollaghasemi, and G. C. Anagnostopoulos. Local Rademacher complexity- based learning guarantees for multi-task learning. Journal of Machine Learning Research (JMLR), 19(38):1-47) 2018.
[68] B. Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam: research papers in probubility and statistics, pages 423-435. Springer, 1997.
[69] F. Zeidler. Nonlinear Functional Analysis and its Applications. Springer New York, edition, 1985.
[70] A. Zhang, L. D. Brown, and T. T. Cai. Semi-supervised inference: General theory and estimation of means. Annals of Statistics, 47(5):2588-2666, 2019.
[71] R. Zhang and D. Golovin. Random hypervolume scalarizations for provable multi-objective black box optimization. In Proceedings of the International Conference on Machine Learning (ICML) 2020.
[72] Y. Zhang and Q. Yang. An overview of multi-task learning. National Science Review, 5(1):30-43, 2018.
[73] Z. Zhang, W. Zhan, Y. Chen, S. S. Du, and D. Lee. Optimal multi-distribution lcarning, In Proceedings of the Conference on Learning Theory (COLT), pages 1220-5223, 2024.
[74] M. Zuluaga, A. Krause, and M. Püschel. e-PAL: An active learning approach to the objei-obeective optimization problem. Journal of Machine Learning Research (JMIR), 17(104):1-22, 2016.
[75] M. Zuluaga, G. Sergent, A. Krause, and M. Püschel. Active learning for multi objetiv optimization. In Proceedings of the International Conference on Machine Learning (ICML), pages 462-470, 470, 2013.
[76] A. Tifrea, G. Yüce, A. Sanyal, and F. Yang. Can semi-supervised learning use all the data effectively? A lower bound perspective. Advances in Neural Information Processing Systems (NeurIPS), 2023.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Each statement in the abstract has corresponding part in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The negative result (Proposition 1) positions the limitations of our approach, together with the discussion of assumptions and results in Section 4 and in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification:
We explicitly state all assumptions, that is, Assumptions 1, and 4
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our work is theoretical, and we only conduct toy experiments that are easily reproducible from the problem setups.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [No]
Justification: The paper is theoretical. The only experiments that we run are detailed in Section and Appendix and do not present main contribution of this work. They can easily be reproduced from the description in these sections.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
wwm.iiiissiiiyiy.oc.coo..mssmiii for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / //nips.co.
guwdes/CCoeeubbmi wwrninsssoooooiooooio for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide full details on the one toy experiments we run in Section and Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The only figure where this is necessary is Fig. 3, where we report the inter- quartile ranges as a measure error.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
17

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We only have have toy experiments (Figs. 2 and 3) which execute within minutes standard laptop, as described in Section 5 and Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpp://neeee /tte:r///neesse/eeeeeeee cc http///bii//tticcccteeeeeeeelell
Answer: [Yes]
Justification:
We reviewed the code of conduct.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: The work is mostly theoretical, and does not have any direct societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
18

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi twwode.cooo.... com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
19

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
20

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: ceteurips..ccCoofeeeeeeeee for what should or should not be described.
21

---

Appendix
Table of Contents
A Related work
22
A.1 A posteriori multi-ohjective learning
23
Adjacent related works
25
A.3 Proofs for ERM-MOL
26
B Beyond Bregman losses: Pseudo-labeling for the zero-one loss
27
B.I Proof of Proposition B.I
28
More examples
29
C.I Binary classification
29
C.2 fz-constrained linear regression
31
C.3 Proofs for the Examples
31
D Proofs main results
34
D.1 Proof of Proposition
................................
34
D.2 Proof of Lemma
37
D.3 Proof of Theorem
38
Proof Theorem
40
D.4.1
Preliminaries
40
D.4.2
Main proof of Theorem 2
41
D.4.3
Proof of preliminary lemmata
45
D.4.4
Proof of Lemma D.8
47
D.4.5
Proof of Lemma D.9
47
D.4.6
Proof of Proposition D.I
49
D.4.7
Proof of Proposition D.2
50
D.4.8
Proof of Proposition D.3
53
E Auxiliary results
54
E.1
Concentration inequalities
54
E.2
Rademacher complexities
55
F Table Notations
Related work
We review related work; for S-MOL in Appendix A. and more adjacent literature in Appendix A.2.
Semi-supervised learning. Semi-supervised single-objective learning is well-established field of research, and the question of when and how unlabeled data can help in a single learning problem rather subtle [17, 26, 76, 6]. Interestingly, the reason that unlabeled data helps in our setting is quite different from how it can help in single-objective learning. Contrary to our setup, results that demonstrate benefit of semi-supervised settings in single-objective learning usually require the marginals to carry some form of information about the labels (such as clusterability, manifold structure, low-density separation, smoothness, compatibility, etc.) [55, 52, 17]. without which semi- supervised learners are no better than ones that discard the unlabeled data altogether [26, 13]. Our results, on the other hand, hold regardless of such assumptions: if the likelihood of a sample higher under one task than another, model with good trade-off prioritizes that task, and unlabeled data enables (implicitly) estimating that likelihood. This is true, even if that likelihood carries no additional information about the labels.
22

---

Algorithm 2 ERM for Multi-objective Learning (ERM-MOL)
Input: Labeled data {(x;, { hypothesis space G, scalarization set S.
1: for k E [K] do
2: Define the empirical risk functional: Rx(g) ==
1 n Σ i=1 lx g(,
3: end for
4: for S do
5: Minimize the empirical s-trade-off: D. - arg min gEg (R), Rx(())
6: end for
7: Return (āe :5::E5 S}.
A priori and a posteriori decision making. In multi-objective optimization, decision makers can be broadly categorized based on whether they have an priori or an posteriori preference over Pareto solutions [29, 33]. An a priori decision maker aims to recover a specific Pareto model, which is the solution to a trade-off T, that is known beforehand. In contrast, an a posteriori decision maker will first recover the whole Pareto set. Recall from Section 2.3 or [23] that, under mild conditions, this entails solving a family of optimization problems Vss E S. mingeg Ta(g). The preference of such a decision maker is then informed by the set of trade-off's that are possible.
The learning version of the problem has been studied for both types of decision makers, where the trade-off functionals need to be estimated from data. This leads two types of algorithms and generalization bounds. The a priori approach has been especially developed in the context of learning with fairness or multi-group constraints [27, 4, 51, 73]. The a posteriori approach, which our work mostly belongs, has been studied by [9].
Multi-distribution learning. In the (supervised) multi dilrriiiittibttoonn learning (MDL) setting, the goal is to learn only one s-trade-off for the scalarization s(v) max Uk. which belongs to the family of priori decision making. Then, for VC-classes of dimension dg, the label complexity to achieve excess s-trade-off > 0 is θ((K + dg)/=²) using an on-demand sampling framework, in which the algorithm is allowed to decide which distribution to sample from sequentially [27, 51, 73]. Importantly, this adaptive sampling improves upon the "trivial" rate (KKdg//²) (see [73] and Appendix 1) by removing the multiplicative dependence on the number of objectives. For non- adaptive sampling, the rate ((dgg/=)) is tight, that is, the fact that the algorithm has to solve only one scalarization does not improve upon the sample complexity of solving all scalarizations, cf. Corollary A. Of course, the statistical complexity under adaptive sampling must fail to hold for S-MOL with multiple scalarizations, because it includes all individual learning tasks. MDL is also related to collaborative (where the tasks are assumed to share a fround-truth), federated, and group DRO frameworks, for which we refer the readers to the discussions in [27, 73, 14].
In [5], the authors propose cunissupervieed framework for group DRO (a problem related to MDL). The underlying assumption in [5] is that for each label-scarce group, there exists a group with sufficiently much labeled data and which is "related enough" for cross- cross-group pseudo- pseudo-labeling to be effective (similar to the collaborative learning setup).
A.1 posteriori multi-objective learning
Empirical risk minimization for S-MOL. Applying empirical risk minimization (ERM) on labeled data to solve S-MOL was analyzed in [19, 59] and in [18] through algorithmic stability. ERM, or perhaps more aptly empirical trade-off minimization, is natural approach to learning all Pareto solutions. The idea is simply to use labeled data sampled for each of the K tasks to empirically estimate the s-trade-off functional T, of any model. The Pareto set can then be found by minimizing the estimated trade-offs. This algorithm, that we call empirical risk minimization for multi-objective learning (ERM-MOL), is formalized in Algorithm 2.
Learning the Pareto set through ERM has been described and analyzed by [19], where S is a family of linear scalarizations. In particular, they provide sample complexity upper bound that depends on the complexity of through a covering number of the weights that appear in S. Later, [59] extended the ERM framework to go beyond the empirical estimator of the risk functionals, allowing
23

---

for any "statistically valid" estimator based on uniform convergence. They further improve the sample complexity upper bound by removing dependency on S in [59, Theorem 2]. Their result can be used to derive bounds for ERM in S-MOI.: we now instantiate their bound in our setting (see Section 2.1) 1),
making the following assumption to enable comparison with our results:
Assumption 5 (Regularity conditions for ERM-MOL). The risk and excess risk functionals equal,
Ak E [K]
inf R&(f)= =0.
JEFa
Proposition A.1 (Sample complexity of ERM-MOL). Suppose that Assumption 5 holds and that the loss Ex(-.-) is bounded by B and La- Li-Lisschitz continuous in the second argument for each k E [ Let S be any class of monotone scalarizations satisfying reverse triangle inequality and positive homogeneity (6). Then, for any 8 E (0, 1), the class of solutions returned by Algorithm {g. 8 E S). satisfies (S-MOL) with probability 8 and E, S(EI..... EK)) where for each k E [K] Eu is given by: 6 = =G (9) + 2B 2 (log((/6) 1/2
(15)
12kk
We demonstrate the implications of this bound for VC class and for linear scalarizations below, using the VC bound on the Rademacher complexity (Lemma E.6), see Appendix A.3 for proofs.
Corollary A.1. Let G be any hypothesis class with VC dimension dg E NN on data domain X x y where y = {0, 13. For each task k E [K], define Eu(y. = 1g # yy} be the zero-one loss (cf. Definition 3). Let (PI, ,..... pk) be any tuple of data distributions over X x.. Then, for any 8, > the output of Algorithm 2 (ōg s E Sna} satisfies (S-MOL) with probability 1 - - and E, = E for all
8 E Stin whenever the number of samples is at least nig = [oo+log(KK8))
for each k E [K].
6²
Dependence on the size of S in results. The authors in [59] noted that the dependence on S in [19] is sub-optimal, in the worst case by a factor of K log ftg, and that such a dependence could be removed. Here, we should add that this only true because in [59] the learning bounds are globally uniform-no localization bounds were derived. Similarly, the bound from our Theorem is also independent of the size of S. Theorem 2, on the other hand, paints a more nuanced picture: the size of the sets G (r: from Eq. (11) depends on the size of S through union: if all local neighborhoods of the 9s are "similar," then does not affect the bound all. However, if the local neighborhoods are very different, then the union may be larger than any of the individual neighborhoods and hence the bound will grow with the size of S; see the right side of Fig. 5. See also the discussion in Section 4.2. Nonetheless, if S is finite, Theorem 2 also yields the following bound.
Corollary A.2. Let S S Stin be finite and let Assumptions and hold. Define
(x(s) == inf (r 2 02 2 Rk, (rB n (G--9)))
Then, i >> is sufficiently small, the output (ā. 8 E 8) from Algorithm I satisfies (S-MOL) with probability 1 - 8 and E. =((1....,EKK) where
Ek Cx (u)(() + 6 (NE + + (4K (S|/8))
with E. = C+((s) from Eq. (14) where n²² = (s() = max (1/Ax k E [K], Au > 0f =
Proof of Corollary A.2. Consider the setting where S = {s } is singleton. Because we only consider this one scalarization, we can make the following case distinction for each & [K]: either
A = 0, so we can ignore index i completely, or d > 0 and so ess sup d.Pk/ (dd(dd(( j= P S 1/Ag. Hence, Assumption
satisfied for = lim) with r (s)) = max (1/>z : EE [ A > 0).
The bound for S [slin] follows from Theorem 2, and the corollary for a finite follows from union bound.
Semi-supervised S-MOL. As far as we are aware, we are the first to study the S-MOL problem in the general semi- remi-supervised setting. The closest work to ours is [65]. where the question of learning Pareto manifolds in high-dimensional Fuclidean space was studied a semi-supervised setting. They
assume that 1) the ground- exhibit a sufficiently sparse structure and 2) the objectives have
24

---

benign parametrization (their Assumptions 1,2, and 3): the paper considers parametric function classes, and the algorithm that achieves the bounds requires knowledge about parameter 8g E R so that RR depends on distribution pk only through Og. Estimating these parameters and then performing standard multi-objective optimization can enable learning in high dimensions. The resulting two-stage estimator is similar to our pseudo-labeling algorithm, and they can coincide, e.g., for linear regression with square loss. Moreover, in [65] the necessity of unlabeled data in high-dimensional linear regression is shown. While we borrow an idea for the stability argument in our Proposition D.I, ,, our results apply to far more general settings.
Comparison of label sample complexities. In order to compare the label sample complexity of our results with prior work, summarize the resulting bounds in Table 1 for VC Gsuhgraph)-classes G and H2 = H. with VC dimensions dg. dx. Recall that in the ideal setting, the marginals are known.
Table 1: Label complexities up to logarithmic factors from this (gray) and prior work for VC (suhgraph) classes. It holds that dy S dg and potentially dx < dg. A definition of de is in Appendix B; both de < dg and de > dg are possible. Note that these results are not strictly comparable, as they depend on varying technical assumptions.
zero-one loss
Bregman loss
problem class
upper bound
lower bound
upper bound
supervised MDL supervised S-MOL
K 22
K
[73, 51]
d
[27]
de
[73]
22
22
Kdg
[59] / Cor, A.l
Kdg
Prop.
Kdg
[59]
Prop. A.1
z²
ideal semi-sup. S-MOL
Kdg
[59] / Cor. A.1
Kilg
Prop.
Kdda Thm. e4
ideal semi-sup. S-MOL
Kde el
Prop. B.1
Kdx Thm.
(with stronger assumptions)
A.2 Adjacent related works
There are many works considering multi-risk settings in different contexts (not to be confused with the multiple competing risks in survival analysis, ef. [34]), for example, in faimess insurance mathematics through the lens of multiple quantile risk measures [21, 37, 58]. Our work specifically related to the fields of ensembling, multi-task learning, and Pareto set learning.
Learning multiple models for one task. Recall that in our Algorithm 1, we first learn multiple models (one per task), and combine them into family of models that trade off the different risks. In comparison, there are many different ways in which combining multiple models can also help on a single task, usually by using some sort of ensembling. For instance:
Stacked generalization combines multiple base models via a meta-model that takes their predictions input features and outputs the final prediction [66, 46).
Mfxture-of- -ffpure-ffEExperts models maintain a collection of expert predictors, and use a routing mechanism to select one more experts based on the new input. This routing is often done through direct soft gating or a weighted combination of the models [45].
Boosting aggregates multiple weak learners form a single strong predictor for one task, typically through sequential training where each model corrects the errors of the previous ensemble [25].
In contrast to any of these methods, our eseudo-labeling algorithm uses the predictions from individual models (in our work ERMs for simplicity) as training targets and fits new model (or family of models) from scratch using the unlabeled inputs. This distinction is essential: unlike the aforementioned methods, our algorithm does not aggregate existing models to solve a single task, but instead leverages them as a supervisory signal to reduce the statistical cost of learning trade-offs in richer function class. In particular, the described methods do not address the core challenge in MOL: the need to reconcile conflicting objectives within single model. Our method explicitly constructs family of joint predictors that trades off competing risks and can-or sometimes even must-deviate significantly from any of the base models.
Learning multiple models for multiple tasks. Multi-task learning (MTL.), including semi- supervised MTL, is problem that is related to MOL in that both are used in settings where multiple
25

---

learning problems need to be solved. However, in MTL, the aim is to learn multiple models, one per task, and exploit relatedness between tasks to improve sample complexity [39, 72]. As such, the problem of striking trade-off, which is at the heart of MOI., is not present in MTI.. For example, suppose a new instance x E X' is observed. MTI., we can make multiple different predictions, one per task, in the hope that each prediction is good for the corresponding task. In MOL, on the other hand, we have to commit to one prediction for all tasks. Aside from these differences, as mentioned, if there is relationship between the different learning problems, we could employ off-the-shel MTL algorithms to adapt our pseudo-labeling algorithm by learning the task-specific models in the first part of the algorithm (Line 2 in Algorithm 1). Finally, from a technical perspective, it is worth mentioning that (localized) Rademacher complexities have been used for MTL in [67, 3, 41, 50].
Learning for multi-objective optimization. A recent line of research has introduced the so- called Pareto set learning (PSL. framework [54, 38, 48], which has found various applications, e.g., in finetuning language models on multiple objectives [64]. PSL is an approach to making learning algorithms such as Algorithms 1 and 2 computationally tractable: instead of producing family of models, one for each trade-off, PSL approximates this family with one fixed function that takes both weights of the objectives and covariates as input (often called hypernetwork [48]). However, importantly, there is no direct connection of PSL to the learning part of the MOL problem: it is actually purely a computational technique. Specifically, if one approximates the outputs of Algorithms and 2 with PSL, then it inherits their statistical guarantees up to the approximation errors. The name Pareto set learning has its origin in the fact that to find such a PSL function, is common to minimize some expected scalarization, where the expectation is taken with respect to weights of the objectives [71]. A standard way to make this tractable is to sample the weights [48]. Generalization is then usually discussed in terms of the number of sampled weights, not the data. See also [65] for a discussion. Finally, beyond hypernetworks, various other learning techniques have been deployed for multi-objective optimization when evaluating the objectives is expensive, such as active learning in [75, 74, 31].
A.3 Proofs for ERM-MOL
Proof of Proposition A. The proof is analogous to the proof of [59, Theorem 2), additionally using Rademacher complexity and McDiarmid's bound to bound the supremum (denoted C'v [59]) and slightly different assumptions on the scalarizations. We repeat the proof here for completeness.
Fix 0 O. By a standard Rademacher bound (also see Appendix D.3), the following generalization guarantee holds for each task & E [K].
P (vgES g: (R((o) - (a(g)) s S
2 1 K"
(16)
For any scalarization 8, let T, denote the empirical s-trade-off
Fo(o) = s (R.()).... (o))))
Then, To is well-approximated by F.. By Assumption 5, Rr = E₁. so that when the event Eq. (16) holds for all ls E [K] and this occurs with probability least 5 by union bound, we obtain that:
sup [f(()) - To(g)) sup 9EG
Rx(x)) (R((()).....
(R)( Rx(9))
gEG
< sup s( s( (g) - (R( Rx (g) - Rx(
gEg
(17)
where the first inequality used the reverse triangle inequality, and the second inequality used the above claim and the monotonicity of the scalarization. In partieular, this will allow us bound the excess s-trade-offf of G. as follows:
(..).) (g.) To(..) To(Ga) + T....) To(g)) + T.(g)) To(ga)
(a)
(6)
(c)
< 2(../2,....5 EK 0k/2) + (51 ..... sK sk/2)
s 8 sE(e,...,
26

---

where the (a) and (c) terms both contribute at most s(cx/2....,Ex/) error from Equation (17), while the (b) term is non-positive, since T. minimizes the empirical s-trade-off Ts. The last inequality follows from the positive homogeneity of the scalarizations.
Proof of Corollary A.I. From Proposition A.1 and the VC bound on Rademacher complexity
(Lemma E.6), there exists constant C such that for each & [K] we have EN S for whenever ng is sufficiently large:
K ny 1220 1 log 8)
The result follows, since we have that for any E Stin:
((I,....,Ek) S s(E......) =
which concludes the proof.
B Beyond Bregman losses: Pseudo-labeling for the zero-one loss
Recall that Proposition a worst-case negative result that rules out any benefit of unlabeled data for MOL,, at least in the absence of any additional structure. Indeed, main results focus overcoming this hardness for more structured losses-namely, Bregman losses. But, there are other natural forms of structure consider; in this section, we take alternative approach.
To help motivate this next approach, let us revisit the reason that Bregman losses are amenable to the semi-supervised approach. As diseuss in Section 3.2, the crux is Lemma 1. It expresses the excess risk functionals & in terms discrepancy operator dy (-:.) and the Bayes-optimal model fū, as follows:
(-)-) (f((=ft)))
(18)
Estimating the discrepancy operator over 9 only makes use of unlabeled data. And even though learning Bayes-optimal model requires labeled data, statistical cost is mitigated by the knowledge that H4 contains the optimal model. Algorithm 1 precisely constructs estimators of & in this way, before solving for the s-trade-offs over the learned approximations. The close relationship between E and fī described by Eq. (18) is specific to Bregman losses, see [62, 15, 28]. Nevertheless, the excess risk functional for other losses may have decompositions that are similar in spirit.
Excess risk decomposition for the zero-one loss. To see another instance of excess-risk decompo- sition, let revisit the setting of the worst-case examples in Proposition 1: the multi-objective binary classification setting with the zero-one loss (Definition 3). In this case, is a standard result that the excess risk can be expressed in terms of the conditional mean of the labels 0x (z) := E|y X* x). as in [20, Section 2. 2. In particular, the excess risks for the zero-one loss is given by
(f) E [120x(x')
1| [((*) (0x (x*) 2 1/2)l
(19)
Thus, for the zero-one loss, the form of its corresponding excess risk functional is En(+) 0/1 (:;0k). where let af/1 (::-) be the "zero-one discrepancy" operator, given by
(J: 0) E [[20(x*) - |5(x*) (11xx)-1(000)) 1(0(x*) 2 1/2][]
where 0 X' + [] is a conditional mean. Notice that the operator d (::-) depends only the the case for Bregman losses (cf.. Eq. (18)). This suggests that
marginal distribution Pt. semi-supervised approach analogous to Algorithm becomes possible the regression problem of learning O% is easy. Note that this is potentially much harder than solving the individual classification tasks, and hence different from the original premise of this work.
We now formalize this intuition. For each & E [K]. let O₃ be class of functions 0 X - [0. 1). In lieu of assuming that ft E Hr, we now assume that the true conditional mean 0g contained in Og (we do not assume that O C G. especially as θ₃ consists of regression functions and G
27

---

consists of classifiers). Define the empirical regression map (.) and empirical zero-one discrepancy dk d (g: 0x) as follows:
1
nh
0x(+) == arg min BEB
(Yr - )(x
Thk:
i=1
N2
(g) NE
Σ - -1/-)))11-0(1)) (0x())))))((0)(
2 1/2
And finally, define the analogous s-scalarization as d 0) = s( // (g: 0)) 2x (g: 0x))
Proposition B.1. In the multi-objectivve binary classification setting (Definition 3), let S be class of scalarizations satisfying the reverse triangle inequality and positive-homogenere (6). Assume that B| = -] E O-. Then, (T= arg min d. (g: 0) S} satisfies (S-MOL) with probability 5 and E. = s(51, Ekk) where
Ek 12 (G)++ +1 log(2K/0) N₁
+ RR (0x) + log(2K/0) 1/2
Ry, (9) +
71g
The proof of Proposition B.1 is in Appendix B.1 and is analogous to that of Theorem 1. Here, we can also give data-indepen lata-inneeendent sample complexity bound. Let de, denote the VC subgraph dimension (a.k.a. pseudo dimension) of O₂ and dg the VC dimension of G. Then, Proposition B.1 implies a label sample complexity on the order of OKde,,/s" and an unlabeled sample complexity of O(Kdg/e*) (see Lemma E.6).
In summary, the hardness result Proposition shows that, in the worst-case, the Bayes classifiers ft are uninformative for making appropriate trade-off's over zero-one losses. Instead, Eq. (19) suggests that the relevant information is actually captured by the Bayes regressors Oz. Proposition B.1 makes this intuition rigorous: if we have additional structure, given here in the form of Ox, we can expect benefits of semi- superviieev even for the zero-one loss, as long as the Rademacher complexity of 2 manageable.
B.1 Proof of Proposition B.1
For this proof, define (0, g) = [20(x:) 11 (0(x) 1 (0(x) 2 1/2)]. Then
(f for (x, 128(x)) - 1| -1-120((ax) - 1||
(20
+ +120'(x) 1| (0))(x) > 1/2) - 1 (0(x)) 2 1/2H
(a) I 2 (z)))) 0 (z)) + (zz) (x)) s 410(z) - (x)])
where in (a) we used that the indicators can only disagree if (0(x) - 0(x) 2 10(x) - 1/2). It follows that for any g E G.
(g: Ex(g) - 20 (g: 0w)l En(g)) - " 0t) + ( 0a) -da (g: 0n)
(g:
E for (x* .9) fa. (x* (xx,9) .0) + |a (g: 0k) - - (g:
4E | oz (X*x]] + 0/1 (gz (n: - -0/1 (g: 0z)
We bound each term separately. First, analogous to Eq. (30) in the proof of Theorem 1, since the square loss is 2-Lipschitz [0, 1J. with probability least 1 5/(2K)
E -xxxx")0x(x')) s $VB ( -
-A()))
2 2log(2K/5) 1/2
2499% (Ok) +2
14k
For the second term, we use that y fo(a, g) is continuuus Let = (0(x)) 2 1/2]: then
(fe(z. - fo(2, < (20(z) 1/ [1((z)
-l
- -x'x c(x)] [0(x) -g' (x))
28

---

Hence, using contraction again, we get the analogous bound to Eq. (29) with probability 1 -
N₂
sup geg
( 0s) d (g: 0x)
= sup gEG
Sö (X++ (X+,g)
g) IR Lo (x* .0)
NA
2 2lg((1/8)
I < (fx + för (I. g 9)) +
Nx
2 2oo /6)
S 699 (9)
N₂
In conclusion, we have proved that with probability 1 - 6, for all lo E [K], we have
2 (log(22/0))
1/2
2 2 2log(2K/0)
sup yeg
[x(g)) 2z (g: - 242R,, (0x) +
+62 (0)+V
N₂
(20)
The rest of the proof then follows analogously to the proof of Theorem I provided in Appendix D.3 by replacing the "claim" with the uniform bound in Equation (20).
C More examples
In this section, we discuss two more examples: classification with logistic loss and another example applying Theorem 2 linear regression.
C.1 Binary classification
Denote for any q E [1, oo] the norm balls By {we E TR.d ||o| 1g S 1}. Suppose that the covariates
lie in the space X = B C Idd, and that the labels in y = [0, 1] for each task follow the Bernoulli distribution
y = x (er(a((x: wf)))
where (xx)
+ exx((=x)) denotes the sigmoid function and we assume that wy E By This is the standard logistic regression setup. The Bayes-optimal models with respect to the logistic loss E(y. () - -y log(ū) + (1- v) log(1 - ú)) are given by fg(+) = ((; wt)) E H = (h(x)- = a(x,,) w)) w E B. However, striking a good trade-off between the tasks within H can be impossible (see Fig. 3 for simple example). To circumvent this issue, we may want to use some feature map Φ- B + B% with p >> d, and then learn in the larger function class G = (g(x) ((((x), w))
E B.). For example, all polynomial features up to degree k. In this setting, Algorithm I effectively exploits unlabeled data to achieve good trade-offs in the larger function class G, as we show in Corollary C.I. This straightforwardly follows from Theorem I; the proof is given in Appendix C.3.
O(d)) and H C G whenever & maps to the set of
Corollary C.1 (Logistic regression). In the setting described above, let S be some class of scalarizations satisfying reverse triangle inequality and positive homogeneity. Suppose that minke]K] No 2 log(p + K) and minke[K] n4 2 log(d + K). Then, the outpul of Algorithm I (ō. E S} satisfies (S-MOL) with probability at least 0.99 and E. =(E,...., where Ee S (logldK)/m.)" + (log(pK)/N..)"
We can also empirically observe the benefits of the semi-supervised method, Algorithm (PL-MOL), over purely supervised approaches- namaallyesanmlly.....m.oa over running Algorithm learn models from either H. (ERM-MOL linear) or G (ERM-MOL polynomial). Fig. 3 visualizes a toy classification problem with linear scalarization, and it compares the resulting decision boundaries, Pareto fronts, and excess --trade-off across the different approaches.
Specifically, consider the data from Fig. 3a: the support of task 2 is completely contained within the support of task 1, and in particular, there is an area where the labels of the two tasks disagree (the bottom left "striped rectangle"). Both tasks are optimally solvable by linear models, but trying to solve both tasks at the same time is impossible, even in Fall. Meanwhile, better trade-off' still become available using, e.g., polynomial features.
29

---

ERM-MOL
ERM-MOL polynomial
PL-MOL polynomiel
olabelo
Jabel 10
teak
Xidull
Labed
C44
labes aisrrnee
ft
Thek 1, Class
Taok Class
Tool Cloort
Taal 2, Llase
(a) data distribution
(b) training data and decision boundaries with logistic loss
EOOM-MOL Imaar
EIMAMOL pelynamnal
PLAKL polyramii
ERM-MOO
ERM
-
Pareto Ironts
eueess stode--off
Pareto fronts
excose -ttude-ff
leginic bos taak jet dan
0.20
101
000.000 www.:rttttell......
10P
0.45
-ttdeell
0.15
0.30
1L335
10"-
0.30
0.28
10
0.00
100
0101
1090
1.00
04
0.25
08900
075
1000
logati best Cate
wright
(c) logistic loss
(d) zero-one loss (large sample sizes)
Figure 3: Learning trade-offss in the classification problem visualized in Fig. 3a. We show 1) supervised linear models, 2) supervised polynomial kernels, and 3) the mixture through the semi-supervised PL.-MOL algorithm. (b) The training data and decision boundaries of the three methods, with score threshold of 1 1/2, for varying trade-off parameters A1. (c) The Pareto fronts for logistic loss and the s s-trade-off off as a function of the parameter A in the linear scalarization. (d) The Pareto fronts for zero-one loss and the s-trade-off function of the parameter λ1. repeat the experiment times and show corresponding interquartile ranges.
We sample 1ı1 = n22 = 25 data points uniformly from the regions Fig. 3a and, in Figs. 3b and 3c, label them according to the linear logistic model y* | = ~ Ber(ft (z)), that is, with noise and in accordance with Eq. (3). Again, we run the three different algorithms on the logistic loss using linear scalarization: ERM-MOL (Algorithm 2) on the function class H of linear models, ERM-MOL on the function class G of linear models on polynomial features up to degree 5, and PL-MOL (Algorithm 1) using H in the first stage for all tasks, and G in the second stage with an additional number of N1 = N2 = 300 unlabeled data points. PL-MOL fits linear models to the labeled data and uses these to predict (soft) pseudo-labels for the unlabeled data, resulting in Fig. 4. Some resulting decision boundaries of each method are shown in Fig. 3b, and the Pareto fronts (on the test data) well as excess s-trade-offt shown in Fig. 3c.
Pseudo-labeled (soft labels)
04
02
(jocuda solt)
X Trok 2 (parnds sot))
Figure Pseudo-labeled data using PL-MOL with the logistic loss.
The expected bias-variance trade-off arises here. In this case, the individual tasks can be perfectly solved over the family of linear classifiers H. However, ERM-MOL over H. necessarily fails to find good trade-offs, as this model class is insufficiently expressive for the multi-objective learning problem-it has large bias. On the other hand, the ERM-MOL over 9 yields large estimation error, since there is not enough labeled data to solve for trade-off's over the much larger family of polynomial classifiers- the learned trade-offs have high variance. In contrast, the PL-MOL algorithm reduces this variance using only additional unlabeled data.
In this experiment, we can also corroborate the importance of the loss function. Fig. 3d shows that PL-MOL can be inconsistent when the losses are not Bregman divergences. While the Pareto front found by PL--OOL dominates the other methods, incorrectly weighs the different objectives per linear scalarization, resulting in sub-optimal excess o-fr To amplify this effect, in Fig. 3d
30

---

we generate the labels in task 1 without any noise, and in task 2 according to this model:
So
is in the "red region" of task 2, (Ber(0.65) is the "blue region" of task 2,
y x
where recall the different regions from Fig. 3a. Merely changing the loss the zero-one loss then breaks Algorithm 1. Specificallyy, in Fig. 3d, we show how the same algorithms perform in large sample regime (n) n2 400). PL-MOLL does not attain the best-possible trade-off within G, even when it recovers the Pareto front of G.
C.2 & constratad linear regression
We now discuss another example where the localization can yield much tighter results than Theorem 1. To that end, we consider the following problem of constrained linear regression with squared loss.
Let X' B8 y [-1, 1], and E be the squared loss. For R E [0. 1]. define the hypothesis spaces H = [h(x)) = (ar, w.) |1lll S RJ and g = [g(x)) (xr, w) : ||w||2 S 1}. We consider
distributions that satisfy E [ | x (wi, x), that is, a (possibly heteroscedastic) zero-mean noise model
Y = (Wk, xx) + 5h
with
E E |
0,
where f (ug. :) E H. C Fall for all k. Suppose that the covariance matrices of X have smallest eigenvalue bounded from below by RR 1] (which is easily satisfied). Theorem 2 then yields the following corollary, proven in Appendix C.3.
Corollary C.2 (fz-constrained linear regression). the setting described above, the output of Algorithm / satisfies (S-MOL) with probability 0.99 and ex s(E1,-..,,6 ,K) for all E Stin (Eq. (5)), where
Ek min {
2R V TTk
2
min
King
KNN
VN
Here 1/ng and 1 1/Ng the localized rates, where Theorem would yield /// and 1/ N/ instead. Notice that if H is very small (i.e., R < 1/(2xm))), then the first term is small due to the smaller complexity of H. while the second term may only become small due larger unlabeled sample size NA.
C.3 Proofs for the Examples
In this section provide the proofs of Corollaries 1, C.1 and C.2.
Proof of Corollary 1. We verify the assumptions of Theorem 2: Eq. (3) holds by definition of the data generating model. Assumption and the smoothness from Assumption 2 hold, because the square loss l is 2-Lipschitz and 1- I-buunded on y = [0, 1), and induced by o(y) = y² which is 1-strongly convex, and max (ő", """ 2. The other parts of Assumption holds because function classes and H convex, and the strong convexity holds with 7 For every slin Sjin quick calculation shows that
d, (g (()(
(c)) (g(x) h2(xx))² >2p2 (xx) dx hn (c))
llall / ((=)(A)p(())+ (2)2(x)) dx
which implies that
d=(g:h)-1l913 (( hz)))
(²(x)) ((o(()) - h22(x)² - - (2p2(x) dx
and hence the strong convexity follows from the convexity of + (g a) n² for any E IR. Assumption 3 holds because the functions from Eq. (9) are assumed be Lipscipt and hence by Lemma 2 the global minimizers contained in G.
31

---

To apply Theorem 2, denote the space of 2Lg 2ig-Lipschitz functions [0, 1] + [-1, 1] as G and note that for any function g E G we have that g g c G. Hence, we can see that
(r(r; h)) = 11I O UG v.²) c c f " 1l9ll sr
#ES
Denote by (L,,, A, II-l1) the covering number of A with norm ||||| radius / 0. see e-g.. 163, Chapter 5] for a definition. It is standard fact [63, Example 5.10] that the metric entropy of {g || S r is bounded
vo <tsr: log N (1 e Illl 5r3.1111e)
8Lg
entropy integral [22], we can bound the Rademacher Hence, using standard bounds with Dudley's entropy complexity of this function class by
At, (fo G: lllll sr))
['" Vlog logN (t. E ã: lllll S sr} 11-11a dt
VNH
(Lg)
N
Lgr
2A
N₁.
and, similarly for Hr)rr we get that
Rtth (H&(T)) $ V
L n
Solving the corresponding inequalities 22
Lae nu
and y2
Ler No
yields
2/3 H
Tk
2/3
and
L N 2/3
Plugging this into Eq. (13) from Theorem 2 and noting that 1) for any fixed confidence 1 (such as 0.99) the confidence term goes to zero faster than the main terms, and 2) the constants C₁ universal constants in this example, yields the result.
Proof of Corollary C.I. We apply Theorem to the setting. First, note that (x) E | x a((,,, wt)) is contained in H. so that Eq. (3) holds. Also note that the loss fly, 1 = - (y log(ū) + +1 y) log(1 - ū)) is Bregman loss (Definition 4) induced by the potential Φ y y (1 y) log(1 v).
Moreover, for all E g we have that (()) C (a(-1), (1)))), since for all w E B and ((x) E B% have that (w, (x))) S [|]] [] 1.
can then check Assumption (using the remark that only the range of G needs to be considered):
1. Because L E 1/(p(1-))) 2 4 for all y [0, 1}. have that di is 4-strongly convex.
2. Making use of the fact that the range of functions in G lies in (o(-1), we get that & is L-Lipschitz in both arguments with L = 2o(-1)o(1) To see that, employ Lemma E. with diamy, and dy ((g)= < -[- on the range of G.
3
3. Similarly, because the range of functions in & lies in (o(-1),a(1)) the loss is bounded by 8 B log(o
Hence, we may apply Theorem 1. Standard bounds on the Rademacher complexities yield
2 2lo 2d
1
2 2log 2p
me (H) <
and Rt, (9) < 4 N
n
32

---

This can be proven using Lipschitz contraction with respect to the sigmoid (which is 1 1/4-Lipschizz continuous). For both bounds, there exist distributions so that the bound tight. Plugging this into Theorem yields (for some fixed high probability, such as 0.99)
logp N₂
1/2
log K
1/2
log d'
log 1/2
24
+
+
Nk
Tik
log dK
1/4
log pK
1/2
24
+
Thk
N&
where the last inequality holds max
log Nx
log
log
log K nik
S 1, which we assumed.
Nv
Proof of Corollary C.2. Denote Ei =E (x*) w, w' Rd
snxn and Iw (:, () G. so that for any
l Iw 11
((w(x - Iw gw (xx)) =E [((w ((w-wi -o'-w",aa xx)) = -w- (w-w') Es(w w'),
and by an identical argument du (Iwi Iwr) (w w/) Ex w') = 11 Iw lb.. It follows that
K d.(gw: = Σ
ds ((w - -wi) T Σn(w
wx))
k=1
K
(w-wwx wx)
Σ delia
wx) - do(owxi (wx)
(21)
where we defined the minimizers
-1
K
9s = 9wx with WA- arg miggidddggn (g(gw: f*)
A
||
This holds because the unconstrained minimizer coincides with the constrained one, ensured by the bounded norms ||wžll2 R S x and bounded smallest eigenvalue pmiia (Ex) 2 note that because || I 1 we have that Mamax (Ex) I 1 -whichh// implies
K Σ
K Ea
Ek=1 Ats//max (aaimmxxEEg (Ex)
|uttle
wk
S1 1.
Eke Aufimin (Ex))
We verify the assumptions of Theorem 2: Eq. (3) holds by definition of the data generating model. Assumption and the smoothness from Assumption 2 hold, because E is 4-Lipschitz and 4-bounded on y = [-, and induced by d(y) = y2 which 1-strongly convex, and max [0".""' < 2. The convexity of d, (g; ft) !| in Assumption 2 holds with constants 1 by inspecting Eq. (21), and G and are clearly convex.
We now bound the critical radius FR := inf {r 2 0: 2 (F((() of the following func- tion class Fr((r) == {(s w) ||w/||2 & 2R, w ΣL S r2 Note that because Mmma (Σ
1/ 1/mimi (Ex) 1/k and X² Bgg holds that
E
Σ
x
E Σ
Σ - = E >
T
(x)
<
and thus we get by Jensen's 's inequality that for any R, r 2
(F((r) <
E
sup SA
X
<
r
E
x
5
r VRn
1=1
r-1
33

---

and, by standard Rademacher complexity bounds (applying Cauchy- Seuuhy-Schwartz and Jensen's 's inequal- ity),
>
2R
R (FR(r)) v T
sup S2R
W im
x;
Vn
[|wll
Hence, we can solve y² 2 s/v/ro Km and p2 2R/ /n get, taking the minimum of the two,
2R
R S min
KTI
We are now ready to apply Theorem 2. Noting that
Hx(r) (r) r ll.
(H+ - ft) ((,w) 1|wl22 S 2R, _ Ex Sr² FR(r)
and that the set G1. (r: f*) is included in (i));;
Gx(r: r BBI|
U(G 9s)
= { (1, w) w E&W S 22] n ( w wx) 11l1l2 - 1,A K-1
C ((:w) w T Eş sr;, ||||| S 2) = Fi(),
apply the previous bound on the critical radius and get that
2R
S
and
u S min
Kn
R.N& VNa
Plugging this into Theorem 2 yields the result.
D Proofs of main results
D.1 Proof of Proposition
To prove a sample complexity lower bound, we show reduction from a statistical estimation problem to the semi-supervised multi-ohjective binary classification problem.
We start by constructing a statistical estimation problem, defining a family of distributions parametrized by the set of Boolean vectors E (0. 1)d. We aim to use samples from distri- bution to estimate its associated parameter; the distributions will be designed so that any estimator given insufficiently many samples will fail to estimate the underlying parameter well for some Then, we show that any learner that solves the multi-objective learning problem (S-MOL) with E, and 8 2 5/6 can be used to solve the parametric estimation problem, implying sample complexity lower bound for S-MOL. For convenience, we reproduce the PAC version of S-MOL here:
geg P P(VSE E Sun, T.(T.) inf T.(g) 56) 2 5/6.
Y(PI, pk) E P
(22)
where P is the set of all distributions over X' x V.
Let's consider the K 2 case first. We show that n 2 d/ d/1024s" samples are necessary.
Defining the statistical estimation problem. Let Xo == ( Fa} C X be a set shattered by g. For each a (0, 1)dd define the distributions P1 and P2 over tributions on X is uniform over the shattered set { za). and (ii) their conditional distributions
y where (i) the marginal dis-
on y = =0, 1} given 2; are Bernoulli distributions. Let c = 4s and define:
p1 1 Σ
6n. s Ber (1 - c(1 ot))
Ea. @ Ber
+ Co
and
p2
7 Σ
7
2
*E|4]
iE|d
Fix a sample size n N. Define the family e= = : a E {0, 1jd), where:
Q - (Pd 8 p2)
on
34

---

Let Zo ~ ~Q consist of n i..d. draws from Pa and Pa each. The statistical estimation problem will be construct an estimator o (Za) for that recovers at least 3/4 of the coordinates of o:
max P | (Zo) 0
1
5
(23)
a
d
4 6
Reduction to multi-objective learning. Suppose that learner can solve the S-MOL problem (22) for 2 using at most n samples. The reduction from estimating a is as follows:
1. Given any instance E {0, 1]4 á of the above statistical estimation problem, have the learner solve the MOL problem over (Pa P2) and linear scalarization Siin using data Zo ~ Qa and zero-one loss.
2. Query the learner for the solution to the linear scalarization $1/2 x with weights À (2) Denote this solution by Zarra ( : Zo) G and construct the estimator ō Moo for a as:
mOL (Za), I51/2 (o;; Zo).
Correctness of reduction.
Before proving correctness, we make few observations:
1. For Pd. the conditional label distribution associated I; Mg is either biased toward 1 uniform over {0, 1.. In either case, under the zero-one loss, the label I is Bayes optimal, and the constant function fī,o is Bayes-optimal classifier for Pl. Likewise, f2.0 is Bayes optimal for P?.
2. A function g : X + y only incurs excess risk from instance v, drawn from PJ when and (xx) = 0. Similarly, accumulates excess risk from instances from P when σ; and g(z,)
The total excess risks of g is given by:
& (g) d
2c Σ ( = 0} and E2(0) d
2c
Σa- = 1}.
EE|d
se|d
For the linear scalarization 81/2, we have:
1 _ (1(1) + 2
c (ggh;) + oz).
Tayz (g)
iEld
3. Since G shatters Ng. it contains a function Jo that satisfies go (x;) for all i E [d]. Thus:
inf Tayya (g) = Ta, (go) 0. gEg
4. Given g : X' V, define the Boolean vector og E {0, 1 نg,i = g(x)). Then, our choice of c, the excess -1/g-trade-off of g is related to the Hamming distance between and a::
|0o
o
Ta (g) inf Ts Ta (g) Se gEg
(24)
d
4
since Ta 22) = d ||o σ a||1
This last point implies the correctness of the reduction. That is, if a learner can solve (22), then we can use to construct moL that achieves (23). In particular, (24) shows that:
| (Zo) orll2 1 4
Tey,a ( Zo)) inf DE8
T (9) SE
d
We now show that this statistical estimation problem requires least n > /1024s² samples across P1 or p2. This holds for any estimator including those that knows that fī.o- and fi.- are Bayes-optimal classifiers and that the marginal distribution over X' for both P] and P2 are uniform over the shattered set. In particular, the lower bound applies to the semi-supervised MOL. learner, which is given access to these Bayes-optimal classifiers and marginal distributions over X.
35

---

Minimax lower bound.
We now show that if n < d/ d/1024=², the following bound holds:
| o
!
5
max min
6
d
where ō (X' y X + {0, 13dd ranges over all estimators using samples from Pa and Pe each.
For every ā and it follows from Markov's inequality that
0111
1
0111
P
$
=
P
_ =4 4
(25)
d
4
d
4
[Z o111
1
1
E
3
4
4
[1|ö (Za) ol12]-
3
3d
We lower bound max EE [[[ (Za) ]|l1] for any estimator ā using Assouad's lemma:
Lemma D.1 (Assouad's lemma, [68]). Let d 2 1 be an integer and let Q = (Qo a E (0, 114) contain 2 probability measures. Given o, {0,1]4 write a a' if they differ only one coordinate. Let ō be any estimator. Then
KL 11Qor) 1 .wd
max E σ
[[Ø
- oll1] 22 min
Z~Qo
where KL(-II-) measures the Kullback-Leibler divergence between two distributions.
When a and o' differ only in one coordinate, the KL divergence between Qo and Qa is bounded:
KL(Qol1Qa.) = n (LPP + KL (L(P2||
Σ
+ co, + t
n
iE(d
1 + c(1 o4) 1
1
Snc²
n
Σ KL
+ c(1 +
S d
2
iEId
where the last inequality holds when c = 4: S 1/3 by Lemma D.2. Indeed, we've assumed < 1/12.
By Assouad's 's lemma (Lemma D.1) and the above bound the KL divergence, in the worst-case setting, any algorithm using n samples will have expected error at least
d (1
4nc²
(
Z~Qo
Plugging into Equation (25), we finally obtain:
oll|
2
4nc
5
max
d
3
6'
where the last inequality holds whenever / Ance /d < 1/4, which holds when n < d/ d/1024=².
Generalization to all K > 1. The MOL, problem with K tasks is at least hard as M = K separate MOL problems each with two tasks. This leads to total sample complexity lower bound M d/1024=2. We obtain the lower bound CKd/e" in the statement of the result by setting = 1/3072 and using Lemma D.3, which shows that [K/2] 2 K/3 for all K 1.
More explicitly, we can reduce M separate copies of the statistical estimation problem for o M into a single MOL problem over the distributions:
p2k- p2k .2.....).
36

---

where l: = , M. Define 1/ to be the linear scalarization that equally divides all weight across the 2k 1 and 2k components:
(122 1 + 12k
2
Then, an estimator 0 for o can be obtained from the by defining as before:
kc Dej (xz).
The analysis from the K 2 setting now holds for each k = ,,...,,. M. This implies that at
least d/1024g² samples must be drawn across each pair of the 2k: and 2kth distributions. This concludes the proof.
Lemma D.2 IKL-divergence bound, e.g. [16]. Let x E (-1/3,1/3) Then:
1
KL x (1))) = 4r.
KL
+ I
4z and
2
Proof. By direct computation, have that whenever [-1/3, 1//3, 1/3].
4x 1/2, which is satisfied when
KT. (1
1
log 1 4x²
S 4x
where the last inequality holds from the fact that log I-: S whenever E 10,1/2].
1
For the second inequality. we show that the function ((x) = KL(1/2 + x 11/2) is L-smooth on (-1/3, 1/3) where L S 8 and has zero derivative at x 0. This implies that upper bounded by _ In particular, the first and second derivatives are:
4
('xx) log(1 2x) log((1 2x)) and
("(x)
4x
so that o² S 8 whenever x²² $ 1/9
Lemma D.3. Let K be a natural number. Then, [K/2] 2 K/3.
Proof. There are two cases:
When K' is even, then [K/2] = K/2 2 K/3.
When K is odd, then K/2] = (K - 1)/2 K/3, where the last inequality is equivalent to 3(K - 1) 2 2K, which is further equivalent to 2
D.2 Proof of Lemma
Let le be a Bregman loss associated with the potential Φx- The first part is proven in [7, Theorem 1]: for any y such that { and (l are finite, it holds that
f arg min (Y [[x*))) = E [y*|x*=
FeF
Then, by definition of Bregman divergences, we have the following generalized Pythagorean identity [8, Equation (26)
()) = (e( - la (2, (y (d)(x) (xbx()))
so that by the tower property (see also [7, Equation (1)])
R+ = (V s(x*))
E (V* E [ + E (E y |x* s(x*)))
Re(
de(F.1()
E y - E y x
Vox(f
Vox E Y x
=0
Rearranging yields that Ef( = Ru(f) - Ro(ft)
de(f: ft), which is the second claim.
37

---

D.3 Proof of Theorem
The proof of Theorem relies on the following lemma on estimating the excess risk functionals Ek with the risk discrepancies d& (f; h1)) under Assumption
Lemma D.4 (Excess risk functional estimation). Suppose that Assumption I holds and that a function hy achieves excess risk Ey (fx) Let C₁ = Lx / pp. Then, the risk discrepancy functional dy hy) defined in Equation (7) approximates Ex(+) uniformly on Fall, that is,
da (J:ha) Ex( S cx En Eha))
sup feJa
Proof. Recall that l E Hg is the minimizer of & over Fall Then for all I E Fall
[d (Tx) Ex(s)] = |dx (s: - ( (((X((
(Lemma 1)
|
I LA E Tio (X+) (x
(Lipschitz continuity from Assumption 1)
s Lx V (x**) - (x
(Jensen's 's inequality)
2 (F( (x*)]]
s L V
us
(strong convexity from Assumption 1)
= -cx =c
(Lemma 1)
which is the claim.
Proof of Theorem 1. For E [K], let hig be the empirical risk minimizer obtained in Line of Algorithm for the ktth objective. Let us recall that we use the empirical risk discrepancy dg ha)) as estimate for the excess risk (-(-) d fī), following the properties of Bregman losses in Lemma 1. We now prove the theorem assuming that the following claim holds.
Claim.
With probability at least 1 - 5, each estimate de hb)) approximates the population excess risk functional & up to error e2/2:
Vk E [K],
sup gEG
[dn hv)) du (g: fit) S Ex/2,
(26)
=Se(g)
where EN is bounded as in Eq. (10).
Then, for any scalarization s that satisfies the reverse triangle inequality, the s-trade-off Te is also well-approximmate by empirical scalarized discrepancy (:: f.). In particular, we obtain
sup |d.(9: h) To(9)] pEg
is (d. ... dx hxx) s(d (9: (t) (9:
sup SEG
s( (T [g; (g: hu)) di (.)....,,,. ..... (dx( dx(r:
< sup
gEs
S /2.
(27)
where the first inequality used the reverse triangle inequality of and the second inequality used the monotonicity of and Eq. (26). In particular, this allows us to bound the excess s-trade-off of 9.. the minimizer of the empirical scalarized discrepancy in G obtained in Line 5 of Algorithm 1, follows:
To.).) To(g.) To..)) J.(0:: h
h.:
ā. h
de(g.: h) Ta(g))
(a)
(6)
(c)
< s ./fi./....,.. sK 0k/2) + (2.
= =s(e,...,,Ek)
38

---

where the (a) and (c) terms both contribute at most /l../2.....Ex. error from Eq. (27), while the (b) term is non-pen non-positive, since 9s minimizes the empirical scalarized discrepancy (-; The last equality follows from positive homogeneity of the scalarization. Then, the result follows for all such scalarizations simultanoussy. It remains to prove Eq. (26).
Proof of claim. samples:
Recall that de hug) is an empirical estimator of d& dx hx) based on the unlabeled
1 dx: No Σ la ((x+)
and dx(g; ha)) ( (2(x(Rx((x)))xxxx)))
where these were defined in Eq. (7). Moreover, da (g: h&)) itself is an estimator of the excess risk functional E (g) = d4 (g: fE), where f& is the Bayes optimal regression function (Lemma 1). Thus, we have the decomposition:
(u Rv)) Ex( = (o: Tux) dx(g; Tiss) +
dd Tin) - En(O)
(28)
Tu.k
We can bound Ta,k and a separately:
(a) For each & E [K], we condition on the labeled samples (i.e., on h2) and employ standard Rademacher bound the function class:
the og = for &o (())
With probability least 1 - (/(2))
2 log (2log(2K/8) (2K/8)
1/2
Ta sup gEG
delgs hw)) du (gigh)))
22 (67, o 0g) B₁
N₂
2 1og(2KK/0)
1/2
56. (9) + Bx
(29)
N₂
where the first inequality applies symmetrization (Lemma E.5) and the bounded difference inequality (Lemma E.2), and the second inequality follows by contraction (Lemma E.4).
(b) For each E [K], we apply Lemma D.4 to bound Ta. in terms of the excess risk of hig which is minimizer of the empirical risk (+) defined in Eq. (2):
Ru (h) = Σ 2 (Y.
In order to use the lemma, we need to show that the excess risk of hig is indeed upper bounded by ek- First, observe that the excess risk can be upper bounded as follows
En (fw) Rr((x)) (F)
Ru (Fxx) - Ru (Fvz) + Ru(h))) Rx( +R R&(ft)
< 2 sup
(x) - -R+(h)
beHi
Again by symmetrization (Lemma E.5). bounded difference (Lemma E.2), and contraction (Lemma E.4) for the function class E Hg {(x,)) + (g, h(x)) h E He). we obtain that with probability at least - 8/(2K),
Mog(2K/8)
1/2
2 sup (R(hh) - (h) NER
< 49 (fx o He. + 2Bg
2 2ogg(2K/
1/2
< 12 (H+) + 2B
17
39

---

And so, by Lemma D.4, we obtain that with probability at least - 6/(2K),
llog(2K/0)
1/2
To S co 12 (H4) + 2B,
(30)
where GE = La / 2/p
The claim in Eq. (26) follows by a union bound. By combining Equations (28) to (30), we obtain that with probability at least 8, for all & [K]]
sup (g: hv)) - Ek(O)) S Sxx/2. 9EG
where we can set as:
[2log(2K6)) N;
1/2
(2log(2K/6) 1/2
Ek = 4L (9) + B₁:
+ ck 12L (Hx) 2Bg
71
This concludes the proof Theorem
D.4
Proof of Theorem 2
In this section, we provide the proof of Theorem 2, but leave some of the technical details to auxiliary results that prove after the main proof. See also Fig. for visualization of the proof.
D.4.1 Preliminaries
Recall that s a linear scalarization. We begin by introducing the notation μ4 = P as well as the mixture distribution 14, s(1, ... ,(K)- Recall the definitions of the (semi-) norms
IIfl, = V (15II [1
Ifll
IC Xtmpp
and
V
which correspond to the inner products (denoting (:. the inner product RP)
(.S8); = / (U,J") dup and (1.) = <<((, ((((::))AA(KK)))
We first verify that these are indeed (semi-)Hilbert norms and inner products.
Lemma D.5. The functions (:, (: and fille-l-ll,, defined above the inner products and norms of the L2 (1se) and L (p.)) (al.,-BBBchnee spaces of functions X - 11112)
See [30, Definition 1.2.15] for definition. We prove Lemma D.5 in Appendix D.4.3 and use throughout without explicitly referring to it. Note that have implicitly assumed that Fall C NGE[K] L' (px). order to use first-order calculus throughout the proof, we derive the gradient and smoothness of the map >> (g: h)) below. We also prove Lemma D.6 in Appendix D.4.3.
Lemma D.6 (Gradients and smoothness). For any h E Hi x ... Hx and linear scalarization denote by V. ddd h)) X + R the gradient of the map g d, (g: h) induced by the Fréchet derivatives on L (1.)) and the inner product (: Then it holds that
duk
V Vgdo(g h)) +
Σ k=1
Ak
x
v2) (x - -x(x))).
djs
Moreover, if Assumption 2 holds and we denote = diam |1-11 (Q)), then the map + dg h) is C = v(1 + Dm-mmooth in ||-I1gp- that is, the gradiens from above is C -Lipschiittt continuous in with respect to 11- If additionally Assumption holds, then for 9s arg min peg d, f*) and all g EG
-
mm
dg f do 8))
1a.
(31)
2
'Note that whenever As > 0, the Radon-Nikode derivative duu due is dell-defined.
40

---

&
U
uk + 4
Gellggh) C Gely + 12f*))
Figure 5: Informal visualization of the proof of Theorem 2. We first localize the set of estimators (0. S} (dotted red line) around the random "helper" set {gl E S} (dashed blue line) within the set GA (Tyi h).. We then expand a set 9x (Ug, f") centered the "true"
{g. E S} (solid green line) to include Ge (ug; h) C Gs (u, 4; f*) where l bounds maximal deviation of gs to g'- This way, we may bound the critical random critical radius u of (u, h) in terms of the deterministic critical radius u of Ga(u; f*) and lg as ug up K.
set
Lemma is direct consequence of the gradient characterization in Lemma D.6 together with Theorem 46 in [69]. Finally, we show that if Assumption 4 holds, the norms I1-Ila and ||-Il, are equivalent.
Lemma D.7. Let S c Sin be in the set of linear scalarizations (5). Then, for any [0, oo)
1ilk [fll..
dpk
sup
th [K], S.f E Fall En = Wk E [K]. s E S ess sup
$ 17
dus
We also prove Lemma D.7 in Appendix D.4.3.
D.4.2 Main proof of Theorem
Recall the empirical and population minimizers of the corresponding risk discrepancies from Eq. (7)
Vs S Is E arg min da (g; SEG
and E arg min de (g: f*)
9Eg
Our goal is to bound T=. inf Ta(g) simultancously for all s E S. By Lemma 1, we have (++) inf, yeg (g(g) d, (Ts; f*) d, (g.; f*) so that we focus on bounding this expression.
The basic decomposition of our proof is a triangle inequality with a helper of minimizers of the population risk discrepancy, defined with respect to pseudo-labeled data as
g' arg min (g h). gEg
Specifically, by the smoothness from Lemma D.6, we can bound the excess trade-off
Cam
d.(ge:f)) dg(gs f = 2 1g - 9 < Crem
|1 -''l.
11 gall.)
(32)
=:Tu um
Here Tllb quantifies the error from having finite amount of labeled data to estimate fž with h and how that error propagates to g', and TTm quantifies how close to g. we can get with the finite amount of unlabeled data. Our goal will be to bound the terms Tlab and Tum using localization, simultaneously for all E S. For the general proof technique of localization, we take inspiration from approaches outlined in [63, 56, 35, 9, 11, 36).
We proceed three main steps. See also Fig. 5. To bound Tlab, we first use standard localization bounds for the ERMs in each task separately, using uniform bound on the local sets Hu (r) = (He- fī) rr from Eq. (11). We then show how their errors translate to g'. through a deterministic stability argument.
41

---

2. To bound Tun we condition on h and simultaneously localize around the (random) functions g for all s S, resulting uniform learning bound on local sets
Gu(r: h) rB
1-1l
UGG -0')))) 96)) .ES
(33)
that are "centered" the helper set fg/ S).
The resulting bound on T from the previous step is random, because g' depends on h, so we need to further bound it. We prove two ways of doing that, so that the bound takes the minimum of the two: the critical radius of (r(r, f* ) = rB lle Use gs) from Eq. (11) together with the bound on Tlab, or a worst-case bound taking the supremum over such {g' 8 E S}.
See also Fig. for visualization of the corresponding sets.
Throughout, we heavily use the following monotonicity property of the Rademacher complexity, analogous the usual localization proofs. The proof can be found in Appendix D.4.4. Lemma D.8. Consider the sets from Eqs. (11) and (33). Under Assumption 2, the functions
R (H+(r))
Ry, (Gr(r;))
and
r
(34)
r
r
are non-increasing on (0, 0o) for all h E H2 x ... X HK-
Step 1: Localization for ERMs in Hj and bounding Tlab, this step, we first bound the error of learning ft with the ERMs h2 (or, in fact, any other estimator that satisfies the basic inequality (hx 2 (ft)). Recall the definition H4 (r) = (H₂ - fi) n rB I-ll, from Eq. (11), and the corresponding critical radii 4 inf {r 2 0: r2 2 R (H)(r)) Using the non-increasing property
from Lemma D.8, we can summarize the bound in the following Lemma.
Lemma D.9. Under Assumptions I and 2, and if > 0 is sufficiently small, have that TP (FFaab 2
1 - 6, where we define the event
Be 14
L PE
log(K/0
Elab = Vk E [
The f
b
+
22
(35)
1
The proof of Lemma D.9 can be found in Appendix D.4.5, and essentially follows the localization technique from [9]: We bound the suprema of the empirical process over Ha(r) using Talagrand's inequality (Lemma E.3) terms of the Rademacher complexity and variance. Using Lemma D.8 and peeling argument, we get the bound in terms of the critical radius.
Next, we show that the bound from Eq. (35) directly translates into bound on the helper set (g/ 8 E S} with respect to labels from but known covariate distributions. To do so, we prove following stability result. Effectively, it removes the square-root from Lemma D.4 that appears in Theorem 1.
Proposition D.1 (Quadratic stability of minimizers). Denote 9 arg min dg(g: h) and C /3/n.. Under Assumptions and 2, we have for any h h' E Hi x ... x HK. any s = lin E S, that
K
96 h 11
<
St
N 11ke
k=1
We prove Proposition D.1 in Appendix D.4.6. Note that a linear bound would directly follow from Lipschitz continuity of the losses. However, this would yield much slower statistical rates than the stability argument from Proposition D.I. Recalling the definition of Ca from (35), we can now use Proposition D.1 with oe g' of Is, conclude that Elab, it holds that for all E S,
plab = l - 11 S St (c?.....
(36)
Eq. (36) describes how well our estimators would approximate the true set {g. E S} if we had an infinite amount of unlabeled data. that sense, this can be seen as an intermediate result the ideal semi-supervised setting by combining Eqs. (32) and (36).
42

---

Step 2: Localization along helper Pareto set in & to bound T We now need to take into account the finite sample effect of having only N₂ unlabeled samples to estimate the risk discrepancies.
To perform localization around the helper set, we again rely on Talagrand's concentration inequality (Lemma E.3). The benefit of Talagrand's inequality in standard localization usually comes from the fact that it accounts for the variance of the losses when centered at the ground truth, which can usually be controlled by its radius of the local function class. We also used this in Step 1. Now, however, we need to simalaneously localize for all scalarizations E S. Hence, recall (r; h) from Eq. (33) where, intuitively, r uniformly controls the deviations Os I' for all E S. To keep track of which dgg any g GR(r; h) "belongs to"", we also define the set
Mb(r)= = (s.g) s S.9 - d Gu(r,)))-
(37)
Lifting the set (r(r; hi) 8 x 9 is inspired by similar trick from multi-objective optimization, where the Pareto set is often lifted to this larger space to obtain its manifold structure, cf. [53].
We apply Talagrand's concentration inequality on MM(rr) and use a localization argument, sum- marized in the following lemma. Define the radii " = inf 2 0::0: r2 2 R (Gu(r; ())]
}. and note that these radii are deterministic with respect to the unlabeled data, but are random with re- spect to the labeled data through the ERMs, point revisited in the next section. Recall that 9. the minimizer of (g; h) and g is the minimizer of de(g; h) (Eq. (7)). The next proposition bounds Tun 19x - I (or, in fact, the deviation of any estimator satisfying the basic inequality (G. h) < (g':: h)).
Proposition D.2 (Localization along helper Pareto set). Under Assumptions I and 2, and for sufficiently small 8 O, we have that IP( "E
2 1 - 8, where define the event
K
L
log (2K/0)
}. (38)
E
V8
lin ES: 10
x
AR
?
N&
The proof of Proposition D.2 can be found in Appendix D.4.7.
Step 3: Bounding the random critical radii u.- Recall that üg is deterministic with respect to the unlabeled data, but random with respect to the labeled data. To make the bound fully deterministic, we prove two bounds, so that their minimum appears in Theorem 2.
Option I is taking the trivial approach: recall from Eq. (11) that we define for the function o = arg geg d. (g;; h)) the set
(x(r:h) = (G 5 (rBBll..
SES
Then the following deterministic worst-case localized radii
i1 : sup heHix x xHx
inf (r 2 02 Rk (rx(r))))
bounds up < uh (and uf < u deterministically (i.e., also almost surely).
Option 2 is more nuanced: If Assumption 4 holds, we can combine Eq. (36) with an expansion argument to bound üg terms of the I1 and the ut. To relate them, we employ the following key proposition.
Proposition D.3 (Critical radius shift). Let G be any class of functions that is convex (Assumption 2). and let E N. Let ||-|| be any norm Fall and let B (f E Fan || S 1) be its unit ball. Define
((r)
n -
and g'(r) U (G- - nB
SES
as well as the critical radii (for Rr defined w.r.t. an arbitrary distribution)
inf {r 2 0: RT (G(r) S r2 and inf in 0: R,, (g'())) 5t²
Let A = sup.es llg. 9/11- Then it holds that ū < 5(u + A).
43

---

The proof of Proposition D.3 can be found in Appendix D.4.8. We can apply Proposition D.3 to our setting: recall the definitions of (r) from Eq. (33) and (r) from Eq. (11), and the definitions U
inf r 2 0 r² 2 (r(r; and u, = inf {r 2 0: r² 2 Ri, (9x(r; f*)) From Assumption
Lemma D.7, and Eq. (36), we know that on E from Eq. (35), for C3 sup:es (S....., skk
sup Ilol Us k S sup llo' gell S sup xES
(k) S 1/ C =: 22
.ES
.S
Employing Proposition D.3 with this A yields uf E u We define
2 C C
Bk
L
Codd_
= max kE[K]
?
(39)
1k
g == sup.cc EE s(G,..., (x)) and ns = 1/ ////uupess DES (11/11..... 1/nx). We can bound
up < u + n 2st 5
L2 12
Bk
L
log 10g(4K/8) K
u + 1 Cst
sup 8 .ES
P
72
1=
log (4K/8)
S u + 2/ Cardd
13
ns
S C
(u + +1 +
log(4K/6)
(40)
ns
Note that in general, either bound can be tighter. For practical purposes, it may be easier to bound dg anyways, so the detour through us may be unnecessary.
Putting everything together. From Eq. (32), we see that on 1/// n 13p2 which holds with
probability at least 1 - 5 by union bound, for all E S, the excess s s-trade-off (@e) inf ing (g)
bounded by
Cmm
(Tum + Tlab)
L2 2
12 722
B₁ ?
log (g((4/0))
12 1
BB
12 log(4 (//()//)
C
N
uk
+
+ Ost
1/
P
T
(from Eqs. (36) and (38))
L2
B
L
A C Che max
uug
+ +2 + (NE + +ng log( (KK
72
7
=:C
where S only hides universal constants. From the two options of bounding ü, we obtain:
1. The first bound, valid without Assumption 4: Recalling CRm vv(1 + D), C 27 x
K Cb (T + 2 + (No + + 1)
T...))
inf TT(g) 2 gEg
k=1
(3(1 + D)
L2 72
Be
B
L
where C₁ x
max
+
pk
2. The second bound, valid under Assumption 4, by plugging in Eq. (40) and Codd from Eq. (39)
To(Ge) inf To(g) S SEG
Cx (uk + Pg + (NE + n55 log())(g(())))) (4K/8))
km
Ö = C . Cst x C Tp 22 max 72
B
L
where
KE[K]
That concludes the proof of Theorem 2, with the proofs of the auxiliary results presented next.
44

---

D.4.3 Proof of preliminary lemmata
Proof of Lemma D.5. The claim for (t. 1l.lle, k E [K] is true by definition, but also as special case of the scalarized form: for any == = E Slin and f, f E (2(()) ) we have
(. Σ No I (. J.
K
J J (..P) d
K
- du
Σ
where (:-) is the Euclidean inner product. This is exactly the inner product of the Bochner (P(s) space (e.g., [30]). Further, plugging in f we obtain directly that (f. II. verifying that the norm is induced by this inner product.
Proof of Lemma D.6. Recall that ) denotes the inner product of the norm 11-11 Σ A I1-11 In this proof, we use Frécket derivatives (denoted D) and the corresponding gradients V, induced by the inner product (-, .). Background on Fréchet derivatives can be found in [2. 12]. From Lemma D.5 we know that ||- actually is the (semi-) Hilbert norm that corresponds to the Bochner L (pss) space with respect to the space (IR9, (1-112), where recall that μl denotes the mixture distribution
where
PR = PX.
It is then easily shown that the gradient of Σ k= d (x((((**)) for any differentiable functions
Qu IR9 D y + R with suppey (|VQ(()) I M < co, induced by (1 is given by
due dp
A [[x*)( XX + R2,
(z))Qx(((z))
Indeed, for any f f Fall C (Ha)), we can write the Fréchet derivative as the limit
K
E [[x(o(x*++ + +ff(x*)) E (((((()*))
D
E [Qx(0(X(]]]]
A lim 6
E
k=1
K
XE ( (dominated convergence)
duz (x))pu(x)
(VVQ) f())
dp.
dhz (z)VQu(o(z)) ) dde(z) Ns dps
Al dji (VQ, g). du,
where we could use dominated convergence thanks to sup (Q())ll, s M < co. This implies the claimed form of the gradient.
Since & is Lipschitz and differentiable, its gradient in is bounded. Further,
K
K
V Vyda(g:h) V
Axdx
V
A (x ((x*))
and the gradient of Bregman divergence in its second argument is given by
V Do y) = V, (o(x) - Q(y) - (Voly), x 5\) =-Voly) - v2o(y) vod()) Vo(v)
vVo(u)(y - =),
45

---

so that the previous derivations imply for the Bregman losses that
K
djtk
V Voda h)
Ak
( ha (x))),
(x)
dus
which is the first claim of the lemma.
Note that na plmast surely Ex=1
dus d dps
1. Hence, for every fixed h, and 9.9'.
V qds (g; - h.))('':h>11
K
duk
dk
(2) 9) VVoold')((e - - duc,
dis
Ns duc
[ - 9 (g') 96) g')l1 dps
(Jensen's 's inequality)
dips
A diik (IIV'nn - of 1)112 + +1((F)x(()) - Vo - 2 dps.
(41)
dps
To bound the first term, we use from Assumption 2 that the Ez-operator norm of (²)(g(x)) is bounded by v > so that
V r')ll2 S v [lg 3 1l2
To bound the second term, we use that 11/2 911l2 < diam (2/ =: D, and so
(v))) Vor(g')) - 10112 S D Pol
which together with the smoothness from Assumption 2 implies
V Vo 1/' (poklo+tld gg)) g'idt) Sv 8'1l2
Plugging both into Eq. (41) yields
K
diu
(): - (dd
Au dus
2² (1+D) 11g 9'1l2 du. (1+D)3 llg g''l²
Hence, by equivalent characterizations of smoothness (e.g.. [12, Corollary 18.14)) it follows that (g h) - d. (V, I), s u(1 + D)
l|g
gllle.
2
By Assumption 3, we know that the global minimizer of f + do(fi f*) is contained in G. By definition, therefore g, coincides with and hence for g' gs and h f we know that VVd,(ss f*), - 9s), = and obtain the bound
d. a. d, (gsi 8¹) v(1+D)
lgg 10
2
This concludes the proof.
Proof of Lemma D.7. Denote μ4 pk and μs Ex AntAE. Recall the definition of the essential supremum of a function f X - (with respect to p..):
ess sup f inf {a IR n. (f oa)) =}
We start with " Since (tx E X dpv./dpa()) 2 (?2)) = 0. for any l E [K], s E S and Falls
duk dus < 17 11f1 = || - 1lf.l.. 1lf112 = / 11f112
dji
46

---

Now we show "=": Choose an arbitrary * 0 E y and measurable A C A, and let f (v/ l Note that I1 = 14- Then for all 8 = li ES
mx(A)= / [1f112 11fll = x² |1
n2 2 A3 I1fll1 n Σ )
This implies the bound a = css css dju /djs I n7² since for any E > 0 we can choose the measurable event Ag = fir (onx/ddu(()))) so
c) which satisfies (by definition) (s((Ae) > 0 and
n²= (x
Ms (As) Ja duk dip 2 a - E.
pe (As)
duu
Taking 8 - concludes the proof.
D.4.4 Proof of Lemma D.8
For the first function, the argument is standard, repeat it here for completeness. Let < and consider some E H4 (r'). Then ||A]| S and hence (////r)) I r, so that (r/r")h E Hx(r) by the star-shape of Hy from Assumption 2. Therefore, have that
T D (H+(r')) =
sup hEH(r") nh Ji (x)())) (=1j=1
T
S R (H+(r))
which is the claim.
For the other function the proof identical once we realize that the convexity of G from Assumption implies that (r: h)) is star-shaped around the origin. Indeed, for any h E Hi ... H. and g arg geg d. (g; h), since (g g.¹ rr is convex and contains the origin,
g E UG 9.t) rB SES
Va E [0, 1], E
UG - -0--5,) nrB sES
We require this star-shapedness for all h E Hi .... x Hk. because we also localize around g'. g that are random elements and may be anywhere in G.
D.4.5 Proof of Lemma D.9
The proof of this Lemma is a mixture of Corollary 5.3 in [9] and Theorem 14.20 in [63]; see also [35] for an exposition. We repeat here for completeness and because we make slightly different assumptions from [9, 63], see Remark below. Recall the definition of the sets for any 2 0,
He(r) (Hs - ft) rr
and the random variables
Ta(r)
sup (Ra -x - (R) Rr (
h- (r)
which are the suprema empirical processes indexed by the function classes defined as
{z,yy + h((),((x)) Lu(y, fā()) h ft E Hx(r)).
By Assumption I, these function classes are uniformly bounded by Bg 2 0. Hence, by Talagrand's concentration inequality (Lemma E.3), for any choice of deterministic radii Ti. ,K 2 O. the event
T((rk) log K/8)
+ Bog (K/5)
= wk E [K] TR(rx) < 2E [Ta(rk)] + v2
n4
n
holds with probability at least 1 Here T((r) is a short-hand for the variance proxy from Lemma E.3, defined
(r)) sup Var (((("*,((x*))) (ar*,f(("""))
h-f(EHe(r)
47

---

We now bound E (Tx( and (rx)). Using symmetrization (Lemma E.5) and vector contraction (Lemma E.4), recalling that Eg is Lg- Lx-Lisschitz w.nt. the 2n-m its second argument, we can bound
E [T+(r)] & 6L my (Hx(r))
and
+k(r) S L3.22
Therefore, we get on the event Q (Fi...., that for all k E [K]
log(K/6)
log (K/6)
(rx)) S 12L (H&(r=))
V2LLTA
+ 3B
72k
Tkk
Now recall the definition
4. = inf fr 2 02 2 Rt (H((r)))
By (34), we get that for any 2 4
R (r)(
R (H+(4))
4
and therefore, if rs 2 4 for all k, on the event Qo (ri...,, TK) (which holds with probability at least 1 - 8), it holds that
log(K/8)
log(K/o)
(r(rk) & 12 V2TurR
+ 3B
(x(rr,))) 5).
nk
We now choose Tk : ha silli:: which are random radii, so we have to perform a peeling argument. Define the event
W == (3k E [K], Hss : 1|h fill& 2 l and Ta(llh fille) 2 3 fill: 8)}
Because || | 11 S diam 1-11 (D) =: D, we know that for any M satisfying 2d 2 D =
M 2 log // l2g(2). for any |//- 10--at ftllk 2 l2 there must be at least one 0 S m S M so that 2m-
1--11,, 1 S ||/ - fElla S I. Moreover, a calculation shows that the functions $ satisfy
S M: 34, 1k, 0) 2 2x 1g, 6/2m)..
for sufficiently small 6, and so P(Wlab)) is bounded by
P
U Mc(M]
{Ek E [K], h E H4: 3m--1 S - 1illf 2
and To(l/h fāll Z 34 - 111
P E [K] Tx(2").)) 34 44. 5))
ME(M]
(0) Σ E E [K]: 12(2" 2 2 (2 8/2m))))m))
8
Σ
S
2m
mE(M]
M
where in (a) we used that P(O (2'' (2.",,...,,2 2n )) 2 1 -5/2
Now, by the standard risk decomposition, have that
(haa))) R&( (hx) - (ua + R( - Re(stt +Ra(st) Rx
50
2Tx ((TTM= 58 l1)
and we can make case distinction.
48

---

Remark 1. Many localization proofs for general loss functions only assume strong convexity and Lipschitz continuity (see, c.g., Section 14.3 in [63]), and therefore one needs handle the case where the rad-ua is bounded but the excess loss is not (tightly) bounded, which would occur in the first case below. our setting, by the smoothness (Lemma D.6), a bounded radius directly implies bounded excess risk, so this case cannot occur and no separate treatment is required.
ft llll I l and ((W S 6, we have with probability least 1 -
1i
done, rh = |T silla
Either nk
44-- and so, because
Tk (mk) = Th (||Tu== sill.) s 30h (liie= Si 66 3 (rk, 6)
Recall that by Assumption 1, Øx is py -tronryy convex w.r.t. 11.112. so that (x v/ 2 Hence, we have that
Mk
lly v'112
2
1
E XtrPk
|xx
- F1(x
S
E la (IE(X*))TTe) Pk xkart
2
2
Rx (hxz) - Ra(sk)) S
4 Ta(rk) S
12
du (rk,
14
where we used Lemma in the second equality. Solving r S
12 tb (rk: 8) for Tke we get that Nh
82944 1
144
8 1
(g(()
Bx
+
Me
1
Hence, in either case we have
L3
Bk
L
log(K/6)
<
2
+
+
2
H4
Therefore, because F(W]ab) < 6, we have that PP
P((Dlab)
2 - 6, where
Dlab V/k vk [K]:
- 5:
1122
Bk
L
log(K/o)
+
Mk
Tik
which concludes the proof for localization in H4.
D.4.6 Proof of Proposition D.1
Recall the form of the gradient V Vyd=(g; h) from Lemma D.7. For every fixed g, and any h. h',
V do (c) - v Vods(g;
K
dus (V> -9) - -Voa(o) 9))) |2
A dji
dus
dpık
Ah
([(") - 9) )2he - - dps
(Jensen's 's inequality)
djts
K
dfik
< 1/
A
||
hike 112 dus
dli
km/
2
A liee 11.12.
(42)
This is what we call "cross-smoothness.
Denote g = t and g' = g/!. We may now use a generalization of the stability argument used the proof of Theorem in [65]. where the following argument used in R and for unconstrained
49

---

optimization: By the convexity of g (Assumption 2), and the optimality of g' we get these two variational inequalities
(V (Vdds( (g: h g). 2 0 and (V h)) I¹) 2.200 = (Vgd.(d:h'', o 9), s 0,
see Lemma 2 and [69, Theorem 46]. Combining both, and subtracting (V:ds(ghh') )'), g' - g) on both sides we see that
(Vgdalg; h) Vgda(g:h') - g), 2 (Vod.lg':h) V Vod h' g 9). (43)
From the second item in Assumption 2, and the main results in [49], we get that the right-hand side of (43) is lower bounded as
2 11g - 0'1; = (Vodolg':h) (od.(g:h'), 1 h' - 9),,
and from the cross-smoothness in (42), get that the left-hand side of (43) is upper bounded by Vyds (g: h 11 119' - gll.
(Vodilg)h) - V (o) g). - V (g:
K
S 1g glle
Σ
Au l1
Combining the two, we can see that
K
22 K
27 [gg - 5' - s 1lg all.
Σ
Au 11, - nilll = 11g - 5 S
2 11/e - 111122
472
k=
This is the claimed quadratic bound.
D.4.7 Proof of Proposition D.2
Throughout this proof, condition on the hy. In particular, all expectations and variances are condi- tioned on hig. Recall from Eq. (33) that for any 2 0
(x(r;
U(9 g') Br
SES
and from Eq. (37) that
Ma(r) { (s.9) E S - L. E Gu(r:h))
The first part of this proof is mostly standard and follows the same proof structure as Lemma D.9. Define the random variables
Zr(r)= sup (e.0)EMa(r)
(atn The (o6i (ds Tux) du (g'ss Trx))]
1 No
Σ (Ca
sup (+gg)EMe(r)
N&
(x"e en (X (X*), I (x*)))
which are the suprema of an empirical processes over the function classes for h E [K]
{ x 4s (ha(z)) g(z)) La ( (s.g) E Ma(r)}
By Assumption 1, these function classes are uniformly bounded by Bg 2 O. Hence, by Talagrand's TK 2 0. the event
concentration inequality (Lemma E.3), for any choice of deterministic radii ri....,
(rx))) (K/5)
+ Bu log K/0)
(T = Wk E [K] (r(r & (E(ZZ( + 2
Nk
N₁
50

---

holds with probability at least 1 - 8. Here (r()) is a short-hand for the variance proxy from Lemma E.3, defined in this section as
pl(r)
sup Var (.())eM((r)
We now bound E (r)) and (f()). Using symmetrization (Lemma E.5) in addition to vector contraction (Lemma E.4), recalling that lx is L Li-Lisschitz w.r.t. f--norm in its second argument, we can bound
E [Zx(r) & 6L (Gr(r;
and
() - Dir
Therefore, we get on the event (rl,..... TK) that
log( K/8)
log (K)))
Zy(rk) & 12L (G h)) + V2LATN
Nx 6Bk
N%
Define
_ = i {r fr 02 R (Gx (r)(r)))))
By Lemma D.8, which holds under Assumption 2, we get that for any r 2 Uk
R (Gx(r; Rk, (Gx (2):))
uk.
"
Therefore, rx ug for all k, on the event Q3 (Ti...,, TR) (which holds with probability least 1 - 6), it holds that for all & E [K],
log (K/8)
log(K/8) (x((r, 6).
(x(rk) & 12Laru + ViLLRAA
3B₁
N₁
N
We now come to the part of the proof that is less standard. Consider the family of random radii
r = 1g. g'llR
E
We perform a peeling argument to bound the probabilities of the two events
Wh0 = a E [K] (Mx)) 2 V (u,,
W = (3k E []], s E S. E g - 2 ū₁ and -x - sllle) 3lg d .))).
Remark 2. Contrary Remark 1, here include the where the radii are small, because have to control all K radii simultaneously. One could also adapt the following proof without this case, but the resulting bound would be the same (up to constants).
By the previous derivations, P ((Wn)) S 6, and for Win we apply peeling argument. Because llg ماادو < diamy 1, (V) =: D, we know that for any M satisfying
2 2 ū 2 D + M log(D/ū;) log(2),
and for any 11g - of ll 2 Ug there must be at least one 0 < m < M so that 2
u1 S 2
2119 - I'lla S
u Moreover, calculation shows that the functions 1 satisfy
4A S m < M 3 (2 m2m--1u... ur 8) 2 4A 42 m)
for small enough 6, which yields that
P (WaI) P
U { E & 2m S l1g galla S 22n
mE(M)
and Za (llg (dll) 2 3V galla 8)}
Σ M
P(kk E [K] (x(2"Tn > 34 (2m Eu 6))
(a)
Σ M
P(kk [K] ZA(2"TT))) V2 8/2m))
Σ
S 6.
2m
mE[M]
51

---

where in (a) we used that P(Q8/2 8/2m union bound yields P (
2 1 5/2Th. Combining the two with
) 2 - 26. Condition on (W3,)) n (W&1).
By the standard risk decomposition, we get for all S
ds h) - do(g':hh = dTsTss h) - d=(Ts: h)) + d.(0,; h) - d.(d's h) +d.( h)) - do(d'sh h)
50
s (0.:h) - -o: h)) + do h)) - d
= ((da (drlGes (āsi hu)) - du (Toi hx) + du (gss hx) - dx Tex) kE[K)
Ss ((Z2(T)))
(44)
Further, by the "multi-objecttvv Bernstein condition" l10. 2'al2 s (d. h) do - h)), implicd by the second item from Assumption 2, and Eq. (44),
2 = s ((r1)² (rk)))........))) = 110 0'l1?
Σ (d (GsTs:h h) - do(g': h)) - ((Zn(ri))E(II)
On the event (88))) n (W&T), we thus get for every
i s
Σ
da XxVVIc
+
Σ
Mrrisu
An v (ūk, 0) Σ 1e33a(TT:0)
We can simplify the first term using ab (a² + 62) as
K
K
(gg(
log(K/ K1))
A v
(2g, 5)
Σ
A
12L + V2LuūR V
+ 3BB
N₂.
N₂.
k=1
K
log(K/6)
A
13L + (Lx + 3BB)
=: by.1-
N₂
Plugging this into the bound on r3 yields
1
K
log( log(K/0)
log( (K/0)
r3
Av
36Larfur + 5LETRY
+ 18B
+ +b..1
N₂
Nx
k=1
1
K
VDu do -Tk)
(VAe
36Lxūz + 5L
log(K/O /8) N₁.
+ 18
K
A
Bg log( (g/()))
+b..1
7
N₂.
k=1
k=1
K
1/2
K
1/2
1
Σ
(x2)2
Σ
+
1s.1 + ba
7
1/2
T
+b.
=:a,
52

---

where the last inequality is Cauchy-Schwarc Some algebra shows that r S rga, + b, implies rs I 2 + b,), and so
K
1
log(K/5)
2
La
1 2 2
A
36Lx4 + +5la
+
13
uk
?22
N&
==1
LL + +BBr)
log K/6)
18 B₁ log K/0)
+
+
N₂
7
N
K
LK
L 7
L
B&
(K/())
λ
2
U
7
7
Nk
k=
K
12
m2
Bk
log( (K/8)
uk
+
7
7
N₂
where in the last line we used LE/7 2 1. Therefore, because ((Ww)) n (Wa.))) have that IP (L
2 11-26, 26, we
8, where
K
L
L3
Bs
log (og(2K/0)
E L
Vs u S: 19 -'1ll S
u
+
72
722
Nx
which concludes the proof of this part.
D.4.8 Proof of Proposition D.3
Recall that A supses l1g. 0'll- For every r 2 0, we have the following key inclusion
g'(r) C G(r + A) + {9. g. S}
To see that, let h g ge (r)). Then (g', ga) = g gs and |/ + (g' - ST
Because Rademacher complexity is sub-additive, we get that for all 2 Rn (g)(r) = R, (G(r + A) {9. g. S))
< RR, (G(r + A)) R. (1y. J/ E ES)
S RM (g(r + A)) Rt, (9(A))
where in the last step we used that
{gg g. s E 8) [g. 9. is e 8} G(A).
Using that for all r 2 u we have R. (G(r) S ,², we get that
Ri (g'(u + A)) S Ri (g(u + 2A)) R. (G(A)) S (u 22)² Ri (G(A)) and using that r + R., (G()) /r is non-increasing (by Assumption 2 and Lemma D.8), we get that RA, (G())
A
Ri (G(u + A)) A(u A),
u
which together yields
Ri (g' (u + A)) < (u + 2A)² + A
Again, by the fact that r + Rr (g'(r)) (r)) /r non-increasing (Lemma D.8), we get that for all r 2 A
R (r) < + Ri (G' (u A)) < u+A (2)) + +A(u+AI
In particular, for the choice r = 5(u + A)
Ri (g' (5(u A))) 5 5(u + A)
((u 22)² A(u + A))
u A
= 5 =6(u + A)² + +2u + A)A + A + A(u + A))
S 5(5(u 2)
(5(u+ + A))²
which implies that ū S 5(u + A), completing the proof.
53

---

E
Auxiliary results
Lemma E.1
(Lipschitz continuity of Bregman divergences), Assume diam
| ()))
sup ouyy lyy - y'll < oc and that is smoohh w.r.f ||-Il and [V Vo(2)ll. S M 1 =||.
Then Do is Lipschitz continuous in both of its arguments separately, that is, for all y, we have
[Do(,,z) Db(2,x)]
2 M)
diam || (3) 11 =11
2
(D - 2o(1,2)1 -Do,))
<
2 M) diamp-Il [1 || - =1|-
"
Proof. This follows from the threc-point identity: First,
Doly. x) - (2(2, = [ 2) (y 2, Vo(x) vo(z))]
2
V/
11
=1| + |1y =|l [ vo(z)]l
wn
2 |1
=11² + 2M 11 - =|| || =|l
W
M)
diammp- (2)) 11y =|l
2
and second, by the argument,
D))y. Doly. 2)
D2 x) (y - vo(xx) vo(2))]
V
|| x + 1ly =|| V (xx) vo(2)ll
2
V
2 || x|| + 2M Ily = || =|l
s 2
M diamp | ())) || 21l
which concludes the proof.
E.1
Concentration inequalities
Lemma E.2 (Consequence of McDiarmid's inequality [43]). Let F be a function class measurabee fanctions X - Th. that is B-bounded, supzex [f(x)] & B for all J E F, and X, X1...., Xn be i.i.d. random elements in X. Define
Z sup fEF
- -[(
11
Then holds that
blog(1/))
PP
Z
E
[Z]
S B
2 1 25.
The proof can found, for instance, in [63, 56]. A significant improvement over Lemma E.2 is Talagrand's concentration inequality, stated next.
Lemma E.3 (Talagrand's concentration inequality [60]). Let F be countable function class of measurable functions X + R that is B/2-bowal 2/2bbednddd, supeex [s(z)] S B/2 for all f F, and X1,..., ,x, be i.i.d. random elements in X. Define
Z = sup fEF
f(X.) E[f(x)) and o²(F) sup E [(((x)) - -(((())) < B².
JEF
Then it holds that
o²(F) log(1/8)
+ logg log(116))
P
2E [Z] + v2
2 1
54

---

E.2 Rademacher complexities
While there are multiple notions of Rademacher complexity for vector- valued functions [50], our choice of Rademacher complexity in this work is motivated by the following contraction inequality, which is used multiple times in our proofs.
Lemma E.4 (Vector contraction, Theorem 3 in [42] adapted for Rademacher complexities with absolute values). Let H be a class of functions - y C IRS, Assume that &. : : x y + R is
L-Lipschitz continuous in its second argument with f2-norm in IR9, that
Vy.u/s v² E EV: Then it holds for o H == (2,,0) - (())(()): H. that
10(y.v') f(v. 1 L 22112
R. H) 2V2LRR, (H) S 3LR,, (H);
where Rr denotes the coordinate-wise Rademacher complexity.
This contraction incquality crucially relies on the & -iiissccitz continuity. If the loss exhibits more favourable Lipschitz continuity, e-g., with respect to f--norm with 2, then results can readily be adapted to use other contraction inequalities [24].
We now state two more well-known results from learning theory appearing throughout the manuscript, solely for convenience purposes.
Lemma E.5 (Symmetrization in expectation, e.g., Theorem 4.10 in [63]). Let F be a class of functions X + I and E N. Let X X,, be i..dd samples in X. Then
E
sup
Σ ((x.) - -E(Xx)] fET
< 29R, (F).
Lemma E.6 (VC Bounds, [10, 91). Suppose that H. consists of functions X - {0, 1} and that H.
has VC dimension dx N. Let n 2 du- Then there exists a constant > 0 so that the Rademacher complexity of H with respect to any distribution on X is bounded as
Rr (H) S min (v
22dx log(en/ (e(een//H))))))
CV
If H consists of functions X + [-B, B) and has VC-subgraph dimension (a.k.a. pseudo-dimension) du N, then there exists constant C such that the Rademacher complexity of H with respect to any distribution on X is bounded as
2dy log(en/
dx
Rr (H) S min 2B
CBV
Moreover, for the norm ball of functions with the same distribution as the Rademacher complex- ? Ri, (H Then there exists
ity, B = { (²( : [I (w)) $ 1.3 let = inf {r 0: r0:r2
constant C > 0 so that
0² < C dx hog(en/da))
n
55

---

Table of Notations
Table 2: Notation
Symbol
Definition
l. Dø
loss Bregman divergence: y x - R
(x)
risk: B[(4(Y**, [(x*))]
(f)
empirical risk: 1 E ((xt))
(R)
excess risk: R4 (f) inf (&)
Ta(f)
s-trade-off: (()( Ex(f))
excess s-trade-off: T.()) gen Ta(g)
risk discrepancy: ([ex(h((**) ((x*))
empirical risk discrepancy: N. Em (x()(X))
h.)
scalarized discrepancy: s(d (.). (f:k))
(f:h))
empirical scalarized discrepancy:
(x((:kk))
f (F)NEIK)
Bayes-optimal models: ft arg min seF (f(
h (ha)RE[K]
ERMs in Hu: πu = arg min (h)
Is
Pareto set in G: arg min d, (g: f*)
g'
helper Pareto set in G: arg min (g h)
Øs
our estimator: arg min gEg de(g;h)
x
linear scalarization: Ek-1 λR
x
Tchebycheff scalarization: maх AEUE
By
4-bbll:: {v E RRd |||||| 11}
B
62-bll: {u E Rd ||a|| 1
Bd
bbll: {o E Rd: || 1
diam (A)
diameter of the set A TR: sup {| - ~ = A}
Rademacher complexity w.r.t. distribution k and n samples
l U
critial radii from Eq. (12)
56


Reviews:
[{"review_id": "ozYECTtqAu", "reviewer": "Reviewer_eRZf", "summary": "This paper studies semi-supervised multi-objective learning (S-MOL), where a learner must solve multiple prediction tasks (risks $R_k$) simultaneously using both labeled and unlabeled data. To address this problem, the authors investigate the sample complexity of learning theory pareto optimal models. To my knowledge, the authors derive the first sample-complexity results of this kind.  They prove a minimax lower bound (Proposition 1) showing that for general losses the labeled-sample complexity scales with the complexity of the full model class $G$ – even if the Bayes predictors for each task and infinite unlabeled data (equivalently, the marginal distribution of feature data of each task)  are available .  By contrast, they show that for Bregman losses (e.g. squared loss, cross-entropy) one can exploit unlabeled data via a simple pseudo-labeling algorithm.  Specifically, they obtain uniform-convergence upper bounds (Theorem 1) and stronger localized Rademacher-complexity bounds (Theorem 2) for this algorithm.  These bounds demonstrate that the labeled sample complexity depends only on each task’s class $H_k$ (where $H_k$ is a simpler model for which the individual prediction task $k$ can be done with negligible error), while the complexity of $G$ enters only through the unlabeled data requirements. Further the effect of complexity of G vanishes when we have infinite unlabeled data.  In effect, this shows when and how unlabeled data can significantly reduce the label complexity of learning multiple Pareto-optimal trade-offs.", "questions": "1. The results focus on Bregman losses and linear scalarizations. Could the authors discuss whether the analysis might extend to other loss families (e.g., hinge) or scalarizations (e.g., \n2.  A short paragraph or table comparing sample complexity to supervised MOL, multi‑distribution learning, and classical SSL would help highlight what is truly new.\n3. As mentioned in weaknesses, Assumption 2 requires each loss to be a bounded, Lipschitz, strongly-convex Bregman loss. This is not the case even for KL loss, unless we consider strong convexity with respect to generalized norm such as $\\ell_1$ norm for KL. Is it possible to extend the analytical argument to support the strong convexity in the generalized form?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "# Strengths\n* **Strong theoretical contributions.**  The hardness result (Proposition 1) is an interesting result: it shows that in general S-MOL has no advantage over supervised MOL in the worst case.  Even when the Bayes models $f^*_k$ and the marginal distributions are known, any algorithm needs $\\Omega(K,d_G/\\epsilon^2)$ labeled examples to achieve $\\epsilon$-optimality for all trade-offs. In particular, the proof shows that even in the case of two tasks, the sample complexity can be large, even when the optimal models for individual tasks is known.   This lower bound is non-trivial (proved via reduction to multiple Hypothesis testing problem and applying Assouad’s lemma) and highlights the fundamental difficulty of S-MOL without further structure. \n* **Effective pseudo-labeling algorithm and upper bounds.**  The paper’s key positive result is that for Bregman losses, a simple pseudo-labeling approach yields much lower label complexity.  By first learning each task’s Bayes predictor $h_k$ in a simpler model $H_k$ (which is good enough for learning task $k$) from labels, and then using these to pseudo-label unlabeled samples, the algorithm reduces the multi-task problem to solving scalarized objectives on unlabeled data .  Theorem 1 gives a uniform learning bound via standard Rademacher analysis.  For VC-type classes  $\\tilde O(Kd_{H}/\\epsilon^4)$ labels and $\\tilde O(Kd_G/\\epsilon^2)$ unlabeled samples are needed.  Importantly, the result shows large complexity of $G$ can be absorbed by unlabeled data, so the label cost is driven by the (smaller) $H_k$’s.\n* **Advanced analytical techniques.**  Beyond the uniform bound, the authors derive localized fast-rate bounds (Theorem 2) using finer Rademacher-complexity tools .  By carefully analyzing the interaction between the estimated regressors and the true Pareto-optimal models (using a stability argument from [47]), they avoid the “square-root” penalty in the labeled terms.  Theorem 2 shows that if the critical radii of $H_k$ are small, the convergence can be much faster (e.g. improving from $n^{-1/4}$ to $n^{-1/2}$ in rate).  The technical argument is well-explained (with a helpful figure) and leverages known results [6,22] for multi-task generalization.  These theoretical tools are non-trivial and represent a solid extension of localized Rademacher analysis to the multi-objective SSL context.\n# Weaknesses\n*  **Strong assumptions.**  The positive results rely on several restrictive assumptions.  Assumption 1 requires each task class $H_k$ to contain the true Bayes predictor and be well-specified.  Assumption 2 requires each loss to be a bounded, Lipschitz, strongly-convex Bregman loss. This is not the case even for KL loss, unless we consider strong convexity with respect to generalized norm such as $\\ell_1$ norm for KL. Further, for theorem 2 we have 4 more assumptions. These conditions are mathematically convenient but limit scope.  In practice, tasks may be mis-specified or losses may not decompose in this way.  The paper acknowledges that without such structure, Proposition 1 shows no benefit to SSL.  Thus the usefulness of the method depends on how often real problems satisfy these conditions.\n* **Clarity of exposition (minor).**  The paper is dense and notation-heavy.  Although definitions are given, a non-expert reader may struggle.  For example, the metric assumptions for Theorem 2 (Assumptions 3–6) are quite technical and deferred to the appendix, which could be better summarized in prose.  Also, the connection between the pseudo-label algorithm and classical co-training or multi-task methods is not fully explored, which might help intuition.  These are not serious flaws but areas where the writing could be smoothed or given more intuition (beyond the formal statements).", "was_revised": true, "final_justification": "My assessment is the same as before. This paper is a solid theoretical work. I will keep my positive score.", "rebuttal": "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.\n\n**Summary of our contributions.** \n\nFirst, 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. \n\nIn 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? \nWe’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.\n\n**On our assumptions.** \n\nLet 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.\n\n- **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.\n\n- **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. \n\n- **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].\n\nWe’ll add a discussion on which losses satisfy these assumptions to clarify the full extent of our results.\n\n**Scalarizations.** \n\nWe’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.\n\n**Beyond Bregman losses.**\n\nWhile 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].\n\n**Overview of sample complexities and existing works.** \n\nFor 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.\n\nIn 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).  \nThe 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.\n\nOur 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.\nWe will include a table of sample complexities in the updated paper. \n\n[A] Balcan, M. F., & Blum, A. (2006). An augmented PAC model for semi-supervised learning.  \n[B] Yu, Y. L. (2013). The strong convexity of von Neumann’s entropy. Unpublished note, 15.  \n[C] T. Heskes. Bias-variance decompositions: the exclusive privilege of Bregman divergences."}, {"review_id": "xHdFSsraGP", "reviewer": "Reviewer_McKt", "summary": "This paper investigates the sample complexity of semi-supervised multi-objective learning (MOL), where the goal is to simultaneously solve for multiple learning objectives, or \"tasks,\" using a single model. The work addresses a key challenge: while each individual task might be simple to solve within a small model class ($\\mathcal{H}_k$), finding a model that achieves a good trade-off among all tasks might require a much more complex model class ($\\mathcal{G}$). \n\nFor \"uninformative\" losses like the zero-one loss, the paper establishes a sample complexity lower bound showing that the amount of labeled data required scales with the complexity of the large trade-off class $\\mathcal{G}$. This limitation holds even if the learner has access to infinite unlabeled data and the optimal models for each individual task.\n\nFor the important class of Bregman losses (which includes squared error and cross-entropy), the authors show that unlabeled data can significantly alleviate the need for labeled data. They propose a simple pseudo-labeling algorithm (PL-MOL) and establish sample complexity upper bounds for it. The key result is that for this algorithm, the labeled sample complexity depends only on the complexity of the simple, individual-task classes ($\\mathcal{H}_k$), while the complexity of the larger trade-off class ($\\mathcal{G}$) is absorbed by the unlabeled sample complexity.", "questions": "1. The main theoretical result (Theorem 1) cleanly separates the sample complexity, with labeled data complexity depending on the simpler classes $\\mathcal{H}_k$ and unlabeled data complexity depending on the more complex class $\\mathcal{G}$. Is this separation fundamental to semi-supervised MOL, or is it a feature of the specific pseudo-labeling approach?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is the first to formally study the sample complexity of multi-objective learning (MOL) in a semi-supervised setting. It addresses the practical question of when and how unlabeled data can reduce the need for labeled data when finding optimal trade-offs requires a more complex model class than solving individual tasks. \n2. The paper provides a balanced perspective by establishing both a negative and a positive result. It first proves a strong hardness result, showing that for general losses like the zero-one loss, even infinite unlabeled data doesn't help reduce the labeled sample complexity. It then shows that for the important class of Bregman losses (e.g., squared error, cross-entropy), this barrier can be overcome.", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**Summary of contributions**\n\nFirst, 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. \n\nIn 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? \nWe’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.\n\n\n**Separation of labeled and unlabeled data.**\n\nThe 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:\n\nThat 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).\n\nAlso 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."}, {"review_id": "uwRZYQY6w9", "reviewer": "Reviewer_n4Vo", "summary": "The authors prove that unlabeled data is powerless to cut the Θ(K d_G / ε²) label cost of learning all Pareto trade-offs under generic losses, but show that for the broad Bregman-loss family a simple pseudo-labeling routine lets unlabeled examples absorb the dependence on the large joint class, so the remaining label complexity scales only with the per-task classes instead of $\\mathcal{G}$.", "questions": "If we were to consider some more recent generalization measures, such as [1], can this study be poentially enhanced to fit the literture of deep models and lead to some more informative and pratical results?\n\n[1] Theoretical analysis of self-training with deep networks on unlabeled data.", "limitations": "N.A.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper offers a rigorous proof that clarifies exactly how unlabeled data can reduce labeled-sample complexity relative to fully supervised learning.\n\n2. The derived results looks interesting - in worst case, unlabeled data cannot help to learn the Pareto-optimal decisions for generic losses, but can be useful for Bregman-loss family (CE, MSE, etc.)\n\n3. The high-level proof sketch distills the core argument clearly, making the full derivation much easier to follow.\n\n**Weaknesses:**\n\n1. The bounds rely on classical complexity measures such as VC dimension and Rademacher complexity; for modern models these quantities are often vacuous, limiting practical relevance.\n\n2. The relationship of the results in this paper between previous works should be high-lighted and discussed, it is known that there are many discussions on the sample complexity of SSL and multi-task learning respectively, but how related are the results in this paper comparing to those results? \n\n3. I am generally happy with Assumption 1-5, but Assumption 6 appears to be too strong - this basically enforces hypothesis class must be linear - akin to W1, this weakness also limits the scope of this study to much simpler model and does not fit the scope of recent literatures.\n\n4. Because Bregman losses already cover the vast majority of practical objectives, the negative result for generic losses has limited real-world impact.. \n\n5. The motivation emphasizes “complex model classes” and cites state-of-the-art deep architectures in related works, yet the main theorems do not extend to those settings.\n\nOverall, this seems to be a technical solid paper addressing a rather new problem, and could be of interest to the learning theory community, but the practical significance of the derived results remains modest in my view.", "was_revised": true, "final_justification": "My opinion for this paper remains the same - a theoretical solid paper considering a relatively new problem, but with very little practicability and relevance to cutting-edge reserach (even for DNNs). The hypothesis class being considered in this paper remains to be simple and the derived results cannot will reconcile with modern deep learning (a known problem, not specified to this paper).", "rebuttal": "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. \n\n**Summary of contributions**\n\nFirst, 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. \n\nIn 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? \nWe’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.\n\n\n**Beyond Rademacher complexities** \n\nWe 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. \n\nWe’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).\n\nWe 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.\n\n**Practial implications of our work**\n\nIn 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.\n\nAnother 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. \n\n\n**Relationship to SSL and MTL.**\n\nThank 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. \n\nWhether 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. \n\nAs 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.\n\nBecause 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.\n\n**Assumption 6.**\n\nWe 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]). \n\n**Negative result.**\n\nIn 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.\nThis 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. \n\nWe hope these discussions clarify any remaining concerns and encourage the reviewer to ask any further clarifying questions if necessary.\n\n\n[D] Wei, C., & Ma, T. (2019). Improved sample complexities for deep networks and robust classification via an all-layer margin.\n\n[E] Wei, C., Shen, K., Chen, Y., & Ma, T. (2020). Theoretical analysis of self-training with deep networks on unlabeled data."}, {"review_id": "VcgFKPFflF", "reviewer": "Reviewer_v5Nn", "summary": "This work investigates when the statistical cost of multi-objective learning can be mitigated, where the role of unlabeled data and loss functions is elucidated. Specifically, the authors first show that it is still necessary to collect enough labeled data for each task separately to control the complexity of the model class $\\mathcal{G}$ under the general loss, even if the Bayes optimal model for each task is known and there is infinite unlabeled data. The authors then focus on the Bregman loss and propose a simple pseudo-labeling algorithm with uniform and local upper bounds on sample complexity.", "questions": "1. Deriving results relies on many strict assumptions. Do they usually hold in practical applications? It is up to the authors to validate them using real-world datasets.\n2. Please add a discussion on the impact of the proposed pseudo-labeling algorithm on the possible generation of labeling noise.\n3. Please add the effect on the Pareto front of changes in the proportion of unlabeled data.", "limitations": "The derivations in this paper rely on several strict assumptions. It is not clear whether all the assumptions hold in practical applications. In addition, the validation of the benefits of the proposed algorithm in this paper lacks larger-scale real data validation.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n1. The theoretical contribution of this paper is solid. This paper establishes a sample complexity framework for semi-supervised MOL for the first time, and explicitly states the necessary conditions for “when unlabeled data is useful”. It analyzes the complexity of labeled samples for multi-objective learning in terms of both lower and upper bounds.\n2. The proposed solution is simple, practical, and easy to integrate.\n\nWeaknesses:\n1. The empirical validation of this paper is insufficient and lacks real-world scenario examples, such as multi-risk trade-offs in medical diagnosis, autonomous driving, and other large-scale evaluations on practical problems.\n2. No empirical comparison is made with existing deep learning-based MOL methods.", "was_revised": true, "final_justification": "I have read the rebuttals of authors and comments of other reviewers. I will keep my original score. Thanks.", "rebuttal": "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. \n\n\n**Summary of contributions**\n\nFirst, 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. \n\nIn 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? \nWe’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.\n\n**Implications for real-world settings.** \n\nA 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.\n\nThe 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. \n\n**Testing assumptions and additional experiments.** \n\nMost 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. \n\nAt 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.\n\n**Impact of label noise.** \n\nThe 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.\n\n**Effect on the Pareto front as a function of unlabeled data.**\n\n 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.\n\n\nAs 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."}]

Author rebuttal:

Meta-review: This paper appears to be the first to formally study the sample complexity of multi-objective learning (MOL) in a semi-supervised setting. All the reviewers agree that the paper addresses a practical and interesting question, and provides balanced results on theory and simulation. During the rebuttal period, the authors and the reviewers were actively engaged, which led to a favorable decision of this paper.
Decision: Accept (spotlight)