Learning from conflicting data with hidden contexts
Authors: Tianren Zhang
Yizhou Jiang
Xin Su
Shangqi Guo
Chongkai Gao
Feng Chen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Conflicting data
hidden contexts
subjective learning
multi-domain learning

Abstract: Classical supervised learning assumes a stable relation between inputs and outputs. However, this assumption is often invalid in real-world scenarios where the input-output relation in the data depends on some hidden contexts. We formulate a more general setting where the training data is sampled from multiple unobservable domains, while different domains may possess semantically distinct input-output maps. Training data exhibits inherent conflict in this setting, rendering vanilla empirical risk minimization problematic. We propose to tackle this problem by introducing an allocation function that learns to allocate conflicting data to different prediction models, resulting in an algorithm that we term LEAF. We draw an intriguing connection between our approach and a variant of the Expectation-Maximization algorithm. We provide theoretical justifications for LEAF on its identifiability, learnability, and generalization error. Empirical results demonstrate the efficacy and potential applications of LEAF in a range of regression and classification tasks on both synthetic data and real-world datasets.

Under review as a conference paper at ICLR 2023
LEARNING FROM CONFLICTING DATA WITH HIDDEN CONTEXTS
Anonymous authors Paper under double-blind review
ABSTRACT
Classical supervised learning assumes stable relation between inputs and outputs. However, this assumption is often invalid in real-world scenarios where the input- output relation in the data depends some hidden contexts. We formulate more general setting where the training data is sampled from multiple unobservable domains, while different domains may possess semantically distinct input-output maps. Training data exhibits inherent conflict in this setting, rendering vanilla empirical risk minimization problematic. We propose to tackle this problem by introducing an allocation function that learns to allocate conflicting data to different prediction models, resulting in an algorithm that we term LEAF We draw an intriguing connection between our approach and a variant of the Expectation- Maximization algorithm. We provide theoretical justifications for LEAF on its identifiability, learnability, and generalization error. Empirical results demonstrate the efficacy and potential applications of LEAF a range of regression and classification tasks both synthetic data and real-world datasets.
INTRODUCTION
Classical supervised learning assumes stable relation between inputs and outputs (Vapnik] 1999). On the other hand, real-world objects often have a variety of semantic properties, and which one is of interest depends on the context. Such contexts are implicitly embedded in the datasets during the labeling process in conventional supervised learning. However, contexts may not be accessible in many open-ended real-world scenarios due to their innate unobservability (Harries al.,) 1998) or privacy and security constraints (McMahan et al.] 2017: Mitchell et al. 2021). With hidden contexts, the same input may correspond distinct outputs due to the change of the context, violating the stable relation assumption. For example, when collecting uncurated image-label pairs from the Internet for general recognition task, an image of a red sphere may be sometimes labeled as "red" and sometimes "sphere". Similar cases are also identified across datasets (Taori et al. 2020); an image of scuba diver can be labeled as "scuba diver" in ImageNet (Deng et (009) while being labeled as "person" " in Youtube-BB BB (Real al. 2017). Contexts can also reflect human preferences whose identities not available in privacy-sensitivy applications, whilst influencing predictions (Kairouz et al. 2021)
It is easy global Empirical Risk Minimization (ERM) is problematic since the data exhibit inherent conflict: the outputs conditioned on the same input can be semantically distinct across different examples, thus mutually interfering during training. Existing machine learning models usually rely on human efforts filter or re-label the data to eliminate this conflict (Krause al., 2016 Vo al. 2017 Taori et al. 2020). These workarounds typically require domain knowledge on the specific problem, and could be ineffective when some crucial indeinnfrrmttin of the data is hard define or collect in practice (Hanna et al., 2020). It is then natural to ask: can we empower the learner to automaticully eliminate the conflict in the training data without additional human intervention?
that when the stable relation assumption is invalid, the common practice of performing
In this work, we formulate the problem of training conflicting data by assuming that the data comes from multiple unobservable domains; different domains may have semantically distinct input-output maps, while the map in each domain is stable. In particular, instead of learning a global model, our goal is to learn multiple local models that separately capture mutually conflicting input-output relations in data. To this end, propose LEAF (LEarning from conflicting data by Allocation Function), a learning framework that comprises high-level allocation function and a low-level model set. The allocation function learns allocate the data among the models to eliminate the conflict,

---

Under review as a conference paper at ICLR 2023
while the models learn local predictions. Our key insight is that the conflict itself can be exploited to learn a good allocation strategy: if the allocation function assigns conflicting examples to the same model, then this will hinder the global minimization of training eπrоr due the conflict, which can in turn be used to improve the allocations. Using a probablistic reinterpretation of our framework, we establish connection between LEAF and variant of appectation-Maximiaai ct al. 1977), showing that an analytic form of the allocation function can be explicitly derived.
(EM) (Dempster
We provide theoretical justifications of LEAF by analyzing its identifiability, learnability, and gener- alization error. Our theoretical results generalize the analysis on classical single-domain supervised learning with no conflict [Vapnik] 1999). revealing the conditions under which LEAF can provably recover all conflicting concepts and providing generalization error upper bound. Empirically, we conduct extensive experiments that span regression and classification tasks on both synthetic data and real-world datasets. Experimental results show that LEAF effectively resolves the conflict in the training data, significantly outperforms task task-specific approaches three settings reflecting practical scenarios with different label space structures, and achieves competitive results with fully supervised learning methods with domain index or label set oracles. In summary, our contributions are three-fold:
We formulate supervised learning setting of learning from conflicting data, which captures the key difficulty in training on the data with multiple hidden contexts.
We introduce a theoretically grounded learning framework termed LEAF that automatically elimi- nates the conflict in data and establish its connection with variant of the EM algorithm.
We empirically evaluate LEAF on a wide range of tasks, in which LEAF effectively resolves the conflict in data without additional human intervention, outperforms task-specific approaches, and achieves competitive results even with fully supervised learning methods.
2 PROBLEM FORMULATION AND THE LEAF FRAMEWORK
In this section, we formulate our learning problem and introduce the LEAF framework. We adhere to the conventional supervised learning terminology: let X' S TR. be an input space, y an output space, H hypothesis space where each hypothesis (model) is function from X' to V, and é: ))x)) - [0, 1] a non-negative and bounded loss function. We denote by X(S) the Lebesgue measure of S for any S C X. N.Y. We use [k] = 21,2,... ... k} for positive integers / and use 1 as the indicator function. For probability density Px over X, we denote by mPpp(Px)= == {ar E X Px (z) > 0} its support. For set S, use |S] to denote its cardinality. We use superseripts to denote sampling indices (e.g., d' and x²)) and subscripts to denote element indices in a given ordered set (e.g., d,).
2.1 PROBLEM FORMULATION
We begin by formalizing the notion of conflict. Following the seminal works in domain adapta- tion (Ben-David et al., 2010a Mansour et al. 2009| 2008). we define a domain d as a pair (Px, c) consisting of an imput distribution Pxer X² and a target function : X + y. We assumee that the training data sampled from domain set D = { = ((P,, ) containing N (agnostic to the learner) domains, and the goal of the learner to learn all target functions )=1- We focus on the setting where there exists conflict between domains, which we make formal by Definition] [
Definition 1 (Conflicting domains). For two domains (P, d) and (P',d') let Xmt SPp n supp(P") P') be the intersection of the supports of their input distributions. We say that the two domains are conflicting if there exists S C Xiut such that X(5) > O and c(x) ) # c' c(xx) for every x E S.
We assume that there exist conflicting domains in the domain set D. Since conflicting domains involve different target functions, one needs multiple models to capture those different onput- maps in the training data. We thus equip the learner with a model set H = [ parameterized by θ = {0,) }KK with cardinality K > 1, in contrast to conventional supervised learning that only trains a global model. Intuitively, K should be sufficiently large fully resolve the conflict in the training data; this depends not only on the number of domains, but also how "severe" the conflict is among all domains. We formalize this notion by introducing the conftict rank of the domain set.
Definition 2 (Conflict rank). For a domain set D = {(P,, ) its conflict rank is defined as
R(D)= == SC SCXX((S)> 30000mE5 xES
max min {c(x) | (P.c) E D, x e supp(P)}
(1)
For brevity, we omit the subscript X in Px when it is clear from the context.
2

---

Under review as a conference paper at ICLR 2023
Note that the cardinality of set only counts the number of its distinct elements. In brief, the conflict rank of a domain set is the maximum number of different outputs conditioned on the same input across all domains. holding for all inputs in a subset of X' with non-zero Lebesgue measure. We will theoretically show in Sec. 3 that R(D) plays an important role in the learnability of our framework.
The training data is drawn in bilevel fashion. Concretely, we consider domain distribution Q over the domain set D. Each batch of the training data is drawn from a domain from D, where the domain itself is drawn from the domain distribution Q. Given the number of batches m and batch size n, m domain examples d' ..... d are first i...d. drawn from Q (a domain can recur multiple times): then, are i.i.d. drawn from the input distribution P corresponding to d = (Pi, c²) and labeled by c:: ydd ct (x*x),, ), Vj E [n]. The key deviation from classical supervised learning is that the identities of domains are unobservable, thus the learner does not know from which domain each batch is drawn. An implicit assumption made here is that the examples in the same batch belong to the same domain when n > 1, which is reasonable since we usually do not expect the hidden contexts to change capriciously in practice (Helmbold & Long 1994 Harries et al., 1998). Moreover, we also show that this assumption is not only reasonable but also necessary for our setup under some conditions (Appendix G. and theoretically and empirically validate the robustness of our method under the scenario where each batch may contain cross-domain noise (Appendix C..3 and E.T). Finally, we note that while our sampling process is akin to meta-learning, our main goal differs in that we aim to learn multiple local models that independently capture conflicting target functions, while meta-learning learns global meta-model that enables cross-domain adaptation
for each i E [m]] ri inputs x"I.... :... i
between related domains ( (Thrun& & Pratt 1998 Pentina & Lampert 2014 Amit & Meir 2018).
2.2 THE LEAF FRAMEWORK
In this section, we formulate the training objective of LEAF. Recall that our goal is to learn all target functions from potentially conflicting domains. Then, a straightforward start point is the empirical multi-task error, i.e., the average loss over all batches given data allocation oracle:
m 7
ETMTL (T)
(ioracto(i)
m
1=1
where Joracle: [m] + H determines to which model in H each batch is assigned so that the conflict in training data can be eliminated. However, Goracle unavailable in our setting; we thus replace it with a data-driven allocation function that searches over the space of allocations to resolve the conflict. In classical supervised learning, those allocations are manually designed and thus rely on the understanding of the designers the task; by contrast, we aim to learn data allocations end-to-end without additional human intervention. We then introduce the training objective of LEAF:
Definition 3 (LEAF training objective). For every i E [m]] let Z' in the i-th batch. Then, the empirical error of LEAF is given by
(xx,, yا
be the examples
2
e (H)
[ (+ (x")
where 9 HK Xm x ym + H is the empirical allocation function; and the expected error is er (H) == Ea (g (g, c(x)),
where g : HK x D H is the expected allocation function.
Besides the empirical error (H(H), we also introduce an expected error er (H) for LEAF, These definitions resemble the empirical and expected risks in classic supervised learning (Vapnik 1999):
while we only have finite examples to identify the domains and perform data allocation in practice, also want to study to what extent this strategy differs from the best we do theoretically giving the (expected) allocation function access to the true data distribution of each domain as in er(H). This is captured by our generalization error analysis in Sec. (Theorem 3).
by
2.3 ALLOCATION FUNCTION DESIGN AND OVERALL ALGORITHM
Given the objective 3). a naive implementation of LEAF is to parameterize the allocation function ğ with extra parameters independent of model parameters θ and train the whole system end-to-end.
3

---

Under review as a conference paper at ICLR 2023
However, this design choice requires additional computational overhead and, more importantly, does not sufficiently consider the interaction between the high-level allocation function and low- level prediction models. In this section, we introduce reinterpretation of LEAF from the angle of likelihood maximization, and derive an analytic form of the allocation function by drawing a connection between LEAF and variant of the EM algorithm (Dempster al.. 1977) on conflicting data. Let Pe(Y) X) be the predictive conditional distribution of the model set H parameterized by O, where we use X and Y as the shorthand for (x"1, We consider maximizing a lower bound of the empirical conditional log-likelihood
xmx) and (y"1,... ,... yy""), respectively.
m
K
n
pe hy x²) = F(g.
log pe (Y (X) 2
ME ((bx)
Σ log j=1
(5)
g(ha)
k=k==
where q posterior distribution over H. By an EM-style derivation (see details in Appendix A.I we
break the optimization on the i-th batch into two alternating steps: in the E-step, we maximize Fig, ))
by updating model posterior q; in the M-step, we maximize F(g, θ) by updating model parameters e
through maximizing the weighted sum of likelihoods Ex=1 ((hx) ) Σj= log |x h1x) given
This suggests a connection between EM and LEAF: the E-step corresponds to the functionality of the allocation function that selects model in H for given data batch, while the M-step corresponds to updating the selected model by minimizing the prediction error.
In the common practice of EM, the output of the E-step is multimodal distribution over components. Nevertheless, here we expect a unimodal output. This is because the aim of the allocation function is to resolve the conflict via data allocation, thus conflicting examples should be deterninistically assigned to different models. We enforce a unimodal E-step by assuming the posterior q as a Kronecker- distribution over H. This variant has also been explored in the literature, referred to as Viterbi EM (Brown et al., 1993) [Spitkovsky et al., 2010) or hard EM (Samdani et al. (012)). We empirically observe that this choice brings consistent performance gains over standard EM, in terms of both final performance and robustness. Under the unimodality constraint, the E-step yields
q (h) ( arg max NEH
log pe 1
(6)
under uniform model prior. This motivates a principled choice of the allocation functions:
(+) arg min Σ e [[(((*) ), yd Vi E [m],
(7a)
g(H, arg min Ex e [h(x), e (x)), Vi E [N]. heHf
(7b)
In other words, a simple implementation that selects a model from H that yiclds the smallest error suffices. Compared to the naive implementation using a separately parameterized 9. this choice requires no extra parameters and is free from explicit bilevel optimization. We note that the connection between Eqs. (6) and 7 is not rigorous in general, with no assumptions on the forms of loss function and conditional distribution family. Fortunately, we show in Appendix A.2 that an exact equivalence can be derived in both common regression and classification settings under some natural assumptions.
Overall algorithm. For each data batch. LEAF consists of two phases: (i) for each model in H, evaluate its average error on the batch; (ii) update the model that yields the smallest error using the batch of data. We provide the pscudo-code of LEAF in Appendix B and the implementation details for different tasks in our experiments in Appendix D
Convergence guarantee. Since LEAF is derived from an EM framework, existing convergence guarantee of (generalized) EM also applies here. Notably, it is known that under fairly general conditions on the monotonicity of the likelihood with respect to posterior in each iteration, the likelihood values in (generalized) EM converge to stationary points (see e.g., Chapter 3 Mclhhchnn & Krishnan| (2007)) Similarly, LEAF shares similar guarantee of converging to stationary point of the empirical error 3 under similar conditions. See Appendix A.4 for more discussion.
Connection to latent variable modeling. In broad sense, LEAF is type of latent variable modeling approach by treating the domain identity of each data pair as a (discrete) latent variable. However, to the best of our knowledge, prior methods actually focus our conflicting data setup, to which LEAF is tailored with several key design choices and assumptions that differ it from general latent variable modeling methods. We provide more discussion in Appendix F and G
4

---

Under review as a conference paper at ICLR 2023
3 THEORETICAL ANALYSIS
In this section, we provide theoretical justifications of LEAF on its identifiability, learnability, and generalization error. Our theory answers the following key questions: (i) Is minimizing the expected error 4 sufficient for identifying conflicting domains? (ii) What is the minimal number of models K required to achieve a low error? (iii) Is minimizing the empirical error (3) sufficient for minimizing the expected error, given the discrepancy induced by both the empirical allocation function and the empirical error minimization process compared with their expected counterparts? We assume realizable, i.e., contained by the hypothesis space H. This assumption
that all target functions is reasonable for rich hypothesis spaces (e.g., parameterized DNNs), and helps underline the key characteristics of our problem. The proofs of all theoretical results are deferred to Appendix C
We first analyze whether minimizing the expected error 4 with the choice of the allocation func- tion (7b) sufficient for identifying the conflicting domains and recovering all target functions. We give an affirmative answer to this question by characterizing the form of the optimal solution of A
Theorem (Identifiability of conflicting domains). The following two propositions are equivalent:
(i) For the domain distribution Q satisfying that Q(d)= for every d E D, the expected error of L.EAF satisfies er (H) = O.
(ii) For each domain d = (P. in D, there exists E H such that Ex~p [h(x),, c(x)] = 0.
Theorem D suggests that minimizing the expected error naturally elicits a global optimal solution where every target function learned accurately on the support of its corresponding input distribution, and errs only sets with zero Lebesgue measure. We then focus on the condition under which a zero expected error can be achieved. This naturally relates to the learnability of LEAF under the framework of Probably Approximately Correct (PAC) learning (Valiant 1984) (see detailed definitions in Appendix ). While learnability in the conventional PAC analysis mainly depends on the complexity of the hypothesis space (ef. Chapter 6.4 of ArShhhe-SShwart & Ben-David (2014)), conflicting data incurs a new source of complexity by its conflict rank, which we expect can be compensated by the cardinality of the model set. We prove a necessary condition of the PAC learnability of LEAF, Since our result also applys to single-model ERM (K = 1). it also illustrates the infeasibility of only training a global model from a theoretical perspective.
Theorem 2 (PAC learnability). For a domain set D with conflict rank R(D) and a model set with cardinality K, necessary condition of the PAC learnability of LEAF is K 2 R(D).
In other words, the cardinality of the model set needs to be at least equal to the conflict rank of the domain set to guarantee that our problem is possibly PAC-leamable. Note that this requirement not directly related to the number of domains; it relies more on the innate structural property of the data sampled from the conflicting domains characterized by the conffict rank of the domain set.
Remark 1. While it is generally hard to derive a both necessary and sufficient condition of PAC learnability theoretically (which requires a sample-efficient optimization algorithm), we empirically observe that K > R(D) is indeed an essential condition of learnability with rich hypothesis spaces implemented as parameterized DNNs. We also note that several works (Allen-Zhu et al.. 2019 Du et al. 2019) have proved that werrparameterrzzd NNs trained by SGD can achieve zero training error in polynomial time, which implies a PAC learnability as long as the conflict in the training data is removed (referred to as the non-degenerate data assumption in Allen-Zhu et al. (2019). We leave more rigorous analysis for future work.
The last question we are concerned about is whether the discrepancy between our empirical and expected objectives (3) 4 also known as the generalization error, can be controlled with theoretical guarantees. This question is crucial since we only have access to the empirical error estimated by the empirical examples sampled from the underlying distributions in practice, while our ultimate goal is to minimize the expected error. While conventional supervised learning enjoys statistical guarantees on the upper bound of the generalization error induced by the single-model ERM process (Vapnik) 1999), LEAF introduces another source of generalization error by the discrepancy between the empirical and expected allocation functions. Therefore, upper-bounte boper-bounding the generalization error of LEAF is important and non -oiviali We present Theorem that shows an upper bound of the generalization error when the data in each batch is noiseless, i.c., sampled from the same domain, and prove more general result in Appendix C.3 under the case where each batch is itself a mixture of the data from the sampled domain and other domains with a given mixing ratio.
5

---

Under review as a conference paper at ICLR 2023
Theorem 3 (Generalization error upper bound). For any 5 E (0, 1}, the following inequality holds uniformly for all model sets H H. with probability least 1 d:
9(S) (In 2m/2mm/
In 8/24
1
e
- (H) +
(8a)
m
m
domain estimation ervor
N
m&
(SS (In 2m ((S) 1) In 6/12N
(8b)
m
Am
dn estimation
(S) (In 21)2(5) + 2v
In 6/24m
2
(8c)
11
atlocation estimation ervor
where S ((P,c) c) mingen px (h(x; θ), e(x)]} is the function set of the expected domain- wise error, S = {(2,8) + f [h(r; 0), is the function set of the instance-wise error, my = E (d' dx) dx) ,k [N] is the count of the k-th domain in D during the sampling process, and 2() the VC-dimension (Vapnik & Chervonenkis 1971) for some set of real functions.
Theorem 3 indicates that the expected error er H bounded by the empirical error ér(H) plus three terms. The domain estimation error term (8a) is derived by bounding the discrepancy between the empirical and expected domain distributions; it converges to zero when the number of batches - xc. The instance estimation error term (8b is derived by bounding the discrepancy between the empirical and expected data distributions; it converges to zero when m - do or the batch size 00, which captures the effect of the recurrence of domains during sampling. The allocation estimation error term 8c is derived by bounding the discrepancy between the empirical and the expected allocation functions; it converge to zero when
30. In practice, often suffices for controlling the generalization error. We posit that this is due to that the domains in experiments are rather diverse, thus reducing the difficulty of discriminating between them.
find very small
Comparison with existing bounds. We compare the general form of our bound ( with exist- ing bounds in classical supervised learning and meta-learning. In general, supervised learning bounds (Vapnik 1999 McAllester| 1999) contain an instance-level error term akin to (8b), while meta-learning bounds (Pentina & Lampert 2014 Amit & Meir 2018) further contain domain- level error term akin to (8ap (with no explicit treatment of domain recurrences). Yet, classical supervised learning only considers single domain or multiple domains with known example-dome correspondances; meta-learning treats each batch adaptation. Thus, none of these bounds contain an explicit model inference error term as (8c).
task and learns global meta- model for
Remark 2. While our bound applies VC-dimension as the complexity measure, extensions to other data-dependent complexity measures such as the Rademacher complexity (Bartlett & Mendelson 2002 Koltchinskii & Panchenko 2000) straightforward.
EXPERIMENTAL EVALUATION
In this section, we evaluate LEAF on two common super- vised learning settings of regression and classification that involve conflicting data. Our experiments are designed to (i) assess the efficacy of LEAF on eliminating the conflict in the training data, (ii) showcase the applicability of LEAF in three practical classification scenarios that in- volve multiple paralleled, hierarchical, or opposite input- output relations in different domains, and (iii) compare LEAF with task-specific approaches.
yo
(a) Ground truth
(b) ERM result
Figure The ground truth of the regres- sion task and the result of an ERM learner.
4.1 REGRESSION
We start with an illustrative regression problem in which the examples are simultaneously sampled from three heterogeneous functions with additive Gaussian noise. The ground truth of these functions

---

Under review as a conference paper at ICLR 2023
8
(a) MAML
(b) Modular
(c) Sparse MoE
(d) LEAF-EM
(e) LEAF
Figure 2: Results on the regression task where the examples are simultancously sampled from three
heterogeneous functions. LEAF is the only method that smoothly recovers all functions.
shown in Figure Ta In this task, a vanilla ERM learner will trivially output the mean of all functions as shown in Figure 1b Each prediction model is instantiated by a neural network regressor with ReLU nonlincarities trained by Adam (Kingma & Bal 2015). More details are in Appendix [D.]
Baselines. We compare LEAF with two types of baselines: (i) meta-learning that learns global meta-model that can be rapidly fine-tuned different functions, and (ii) Mixture-of-Experr (MoE) that learns set of expert networks and parameterized gating network that fuses the outputs of experts. For (i), we use MAML (Finn et al., (017)). a widely-usee gradient- gradient-based meta-lcarning approach, and Modular meta-lcarning (Alet et al. 2018)) that extends MAML with multiple modules. For (ii), we use Sparse MoE (Shazeer et al. (017) that achieves state-of-the-an results on language modeling tasks; we augment the input of the gating network with the ground-truth outputs to make it sensible of the conflict, and enforce that only one expert is selected by the gating function for each example. We also compare variant of our method, LEAF-EM that uses standard EM without the unimodal constraint. More details on the baselines are in Appendix D.I.I
Evaluation protocol. For meta-lcarning methods, we use additional examples for the learned model to adapt to each function and plot the fitted curves after adaptation. For other methods, we directly plot the fitted curves of all models or experts and compare the outputs with the ground-truth functions.
Results. As shown in Figure 2 LEAF is the only method that smoothly recovers all functions. Meta-learning methods do not produce accurate predictions in fine-graine fine-grained details due to their nature of few-shot fine-tuning, Sparse MoE completely fails in this task; we posit that this is because the gating network in MoE separately parameterized and trained end-to-end, leading to optimization difficulty on conflicting data. By contrast, the analytic allocation function relieves the burden of learning additional gating parameters and leads to better results. Finally, LEAF-EM performs worse than LEAF, showing the advantage of using the unimodality constraint.
4.2 CLASSIFICATION
To evaluate LEAF in more practical scenarios, we consider three classification tasks that involve paralleled, hierarchical, and opposite input-output relations across the domains. These settings reflect real-world scenarios with different types of hidden contexts, as we detail below:
Paralleled relations. Data from different domains has paralleled labels that represent independent attributes of the same input, such as "red" and "sphere".. This is common for uncurated data, e.g., web data. For this setting, we use two datasets. (1) Colored MNIST, a variant of MNIST where each digit is colored and assigned with an additional color label, resulting in two domains: Digit and Color, (2) Fashion Product Images (Aggarwal) 2019). a multi-attribute product classification dataset that involves three domains: Gender, Category and Color, as shown Figure 3a
Hierarchical relations. Data from different domains has labels with an innate hierarchy, such as "person" and "scuba diver". This is common for different datasets with different labeling purposes or different levels of expertise of the human annotators. For this setting, we use the CIFAR-100 dataset (Krizhevsky & Hinton 2009). widely-used image recognition dataset that consists of 100 classes with fine labels subsumed by 20 superclasses with coarse labels, resulting in two domains: Superclass and Class with hierarchical label space structure, as shown in Figure 3b
Opposite relations. Data from different domains has completely opposite labels, such as "like" and "dislike". This is often due to preferences or sentiments of human users. For this setting, we re-label the Fashion Product Images dataset, simulating a domains: Male and Female, shown in Figure 3e The Male domain treats all products with the "male" attribute as positive and other products as negative, while the Female domain treats all products with the "female" attribute positive and other products negative.
deeenddeed scenario with two
7

---

Under review as a conference paper at ICLR 2023
Domains
Labels
Domains
Labels
Domains
Labels
Color
Blue
Superclass
Vehicles
Male
Positive
Gender
Male
Category
Apparel
Class
Bus
Female
Negative
(a) Paralleled relations: Fashion
(b) Hierarchical
relations:
(c) Opposite relations:
Fashion
Product Images
CIFAR-100
Product Images with preferences
Figure 3: Classification datasets with paralleled, hierarchical, and opposite input-output relations.
Baselines. (i) ERM-top k: we directly use the top-k outputs of ERM. (ii) Semi-supervised multi- label learning: we alternatively interpret learning from conflicting classification data as multi-laber learning (Zhang & Zhou 2014) with missing labels (see Appendix D.2.1 for more discussion); in light of this, we adopt two representative methods, PseudoLabel (Lee) 2013) and LabelProp (Iscen et al. 2019), to iteratively fill up the missing labels during training. (iii) Sparse MoE: the same baseline as regression, with each expert instantiated as neural network classifier. Moreover, consider two baselines with additional label set or domain index information. (iv) MLL oracle: multi-label learning where we provide the full label set for each example. (v) MTL oracle: multi-task learning where we provide the ground-trutt domain index for each example. As in regression, we also evaluate the LEAF-EM variant of our method. More details of datasets and baselines are in Appendix [D2]
Evaluation protocol. For LEAF and other methods that use multiple low-level models, we report the errors based on the low-level model that yields the smallest error for each domain: given domain d with test examples {(x; 34) ) the error on d is defined as min Σi= 1 xz, # ysl, which is
an unbiased estimator of the expected error 4 by taking the loss function to be the 0-1 loss. For
methods with no multi-model architecture, we compare their output label sets with the ground-truth label set for each test example and report the error on each domain. Note that multi-label learning methods do not apply to the opposite relations setting and we thus omit their results.
Results. As shown in Tables [ and 2 LEAF significantly outperforms all baselines in all three tasks, yielding smaller prediction errors on all domains. Even compared with fully supervised learning methods with label set domain index oracles, LEAF performs competitively. Once again, we ob- serve that LEAF consistently surpasses the LEAF-EM variant, suggesting the benefits of a unimodal E-step.
Table I: Results on the classification task with opposite input-output re- lations. We report prediction errors on both domains, Male and Female.
Error (%)
Methods
Male
Female
Visualization of low-level feature spaces. To complement the
ERM
49,50
50.50
quantitative results, we visualize the features learned by the low-level models of LEAF the paralleled relation setting on Fashion Product Images. As depicted in Figure 4 the low-level models indeed learn feature spaces that separately capture the semantics of different domains.
Sparse MoB
82.18
32.43
LEAF-EM
22.10
81.85
LEAF
7.40
9.65
MTL oracle
7.14
6.53
4.3 ADDITIONAL EXPERIMENTS AND RESULTS
We also conduct additional experiments to demonstrate the efficacy and robustness of LEAF and study the impact of the number of low-level models and parameters. Due to space limit, these experiments and results are deferred to Appendix E Here we provide a list of them and refer the interested readers to the corresponding sections in the appendix. (i) In E. we evaluate the robustness of LEAF under both the cross- and in-domain noise; (ii) in E.2 we evaluate LEAF on real-world multi- dimensional regression task; (iii) in E.3 we study the impact of the number of low-level models and sampling parameters on LEAF; (iv) in E.4 we report the training and inference time cost of LEAF and baselines in the classification task; (v) E.5 we provide additional visualization on the iteration process and the low-level feature spaces learned by LEAF models.
Black
Calar-
Waze
Geeder
Male
Blue
Moddl
Model 2
raingnne an
Model 3
Apguesi
Cregrey
Footwarr
Figure 4: Visualization of different low-level feature spaces learned by LEAF on Fashion Product Images.
8

---

Under review as a conference paper at ICLR 2023
Table 2: Results on the classification tasks with paralleled and hierarchical input-output relations. We
report prediction errors on Digit and Color domains of Colored MNIST, Gender, Category and Color domains of Fashion Product Images, and Superclass and Class domains of CIFAR-100
Colored MNIST
Fashion Product Images
CIFAR-100
Methods
Error (%)
Error (%) Category
Ertor (%)
Digit
Color
Gender
Color
Superclass
Class
ERM-top &
3,04
0.39
22.80
18.02
33.15
27.35
31,20
PseudoLabel
7.47
10.08
33.69
20.04
34.06
28.46
38,96
LabelProp
11.52
13.57
14.59
50.43
64.48
66.62
45.17
Sparse MoF
15.70
25.40
37.13
27.76
44.28
45.63
51.15
LEAF-EM
6.83
4.76
26.67
6.01
18.70
32.71
33.83
LEAF
1.70
0.03
7.87
1.93
12.85
21.40
25.05
MLL oracle
1.02
0.00
8.46
1.17
9.45
22.08
26.29
MTL oracle
1.20
0.00
7.14
1.90
11.04
21.11
25.08
5 RELATED WORK
Early work on supervised learning with the presence of hidden contexts (Schlimmer & Granger 1986; Helmbold & Long 1994, Wiimeer& & Kubai 1993) adopts the notion of context to model concept drifting. Most of them consider an online learning scenario and aim to track the changing contexts datastream. |Harries et al. (9998) propose to extract hidden contexts from the offline data using contextual clustering, but their method requires additional contextual clues and does not scale to modern machine learning datasets. More recent work explores to leverage the available contextual information to facilitate learning in various scenarios, such as question answering (Choi
et al., 2018), image and scene understanding (Shotton et al. 2009; Chen et al. 2015), retrieval (Zhao al. 2018), and recommendation systems (Pazzani & Billsus 2007). A series of works either
implicitly or explicitly model the contexts in different data distributions to improve the adaptability
2019 Harrison et al.) of global meta-model (ao al., 2019] Zintgraf al. 2019 Rakelly al.
2019). Several works on similarity learning investigate the case where the similarity between images depends on different latent attributes (Amid & Ukkonen 2015 Veit al. 1017:Nigan et al.) 2019). requiring image triplets as the inputs. Su et al. (2020) study a multi-task learning problem where the goal of the learner objective from ours and no theoretical justification.
learn from online examples without task indices, but with a different learning
Extensive literature has explored the collaboration of multiple models or modules completing one or multiple tasks (Doya et al. 2002 Andreas et al. [0166] Alet et al., 2018 Meyerson & Miikkulaieen 2019: Yang et al., 20200 Yuksel et al.] 2012] Shazeer al.] (017). The difference between these methods and LEAF is that the multi-model architecture of LEAF is driven by the inherent conflict in conflicting data, and we only allow a single low-level model to be invoked for a particular batch. We provide more discussion the related work in Appendix F
LIMITATIONS AND DISCUSSION
In this work, we formulate a novel supervised learning setting of learning from conflicting data, which captures the key difficulty in training on the data with multiple hidden contexts. We hope that our work can serve as a stepping stone in the pursuit of more general and automatic learning frameworks, and list some limitations of the current work that are worth exploring in the future:
Principled methods for handling noisy data. While we have empirically assessed the robustness of LEAF under both cross-domain and in-domain noise (Appendix E.I). p. it is promising to combine LEAF with robust learning approaches (Zhang & Sabuncu 2018 Song et al. 2022) to develop more principled methods for distinguishing hidden contexts from data noise.
Determining the number of prediction models. A critical problem in LEAF is to determine the number of low-level models. In Appendix E.3 we discuss several heuristics for this problem and provide primary experimental results. Nonetheless, developing theoretically grounded approaches for choosing or adapting the number of prediction models is exciting future direction.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
In a broad sense, the goal of this work is to contribute to the development of more general and automatic machine learning frameworks. Therefore, like other methods that also aim to reduce the human labor in machine learning. our work may induce negative societal impacts due to the concerns of the robustness and explainability of our models. While devising more robust and explainable machine learning models has been considered as paralleled research fields, in this work we provide primary robustness assessments of LEAF in Appendix [.T and show that our framework does not exhibit more severe robustmess downside compared with existing deep learning models that widely used today. We also note that our method can benefit from future advances in robust and explainable machine learning research. On the other hand, by reducing the need of explicit context identifiers during training, our method may facilitate machine learning research in privacy-sensitive scenarios where contexts are available due to privacy constraints.
REPRODUCIBILITY STATEMENT
This paper includes both theoretical analysis and experimental results. For theoretical results, we state all assumptions and discuss the reasons for introducing them before presenting the results, as in Sec. S Complete proofs of all theoretical results and relevant definitions are included in Appendix C For experimental results, specify the training details (c.g., data splits, hyperparameters, network architectures) in Appendix and provide the source code in the supplementary material.
REFERENCES
Param
A Aggarwal.
Fashion product images dataset.
https: www. http://wwwwwggl.ccoco
par
http:pppwdduttt-aaa-daaaatataeee dataess 2019.
Ferran Alet, Tomás Lozano-Pérez, and Leslie P. Kaelbling. Modular meta-learning, In CoRL, 2018.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via parameterization. In ICML, 2019.
Ehsan Amid and Antti Ukkonen. Multiview triplet embedding: Learning attributes in multiple maps. In ICML, 2015.
Ron Amit and Ron Meir. Meta-leaming by adjusting priors based extended pac-bayes theory. In ICML, 2018
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In CVPR, 2016.
Peter I.. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2002.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. theory of learning from different domains. Machine learning, 19(1-2):151-175, 20.
Shai Ben-David, Teresa Luu, Tyler Lu, and David Pal. Impossibility theorems for domain adaptation. In AISTATS, 2010b.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to new unlabeled sample. In Advances in Neural Information Processing Systems, 2011.
Peter Brown, Vincent J Della Pietra, Stephen A Della Pietra, and Robert Mercer. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263-311,
1993.
Liang- Chinh Chen, George Papandreou, lasonas Kokkinos, Kevin Murphy, and Alan L. Yuille. Semantic image segmentation with deep convolutional nets and fully connected CRFs. In ICLR, 2015.
10

---

Under review as a conference paper at ICLR 2023
Eunsol Choi, He He, Mohit lyyer. Mark Yatskar, Wen-tau Yih, Yejin Choi, Perey Liang, and Luke Zettlemoyer. QuAC: Question answering in context. In EMNLP, pp. 2172-211422 2018.
Gerda Claeskens, Nils Lid Hjort, et al. Model selection and model averaging. Cambridge Books, 2008.
Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1): 1-22, 1977.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In CVPR, 2009.
Thomas G. Dietterich. Ensemble learning. The handbook of brain theory and neural networks, 2(1): 110-125, 2002.
Kenji Doya, Kazuyuki Samejima, Ken-ichi Katagiri, and Mitsuo Kawato. Multiple model-based reinforcement learning. Neural Computation, 1466)13347-136, 2002.
Simon S. Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In ICML, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agmostic meta-learning for fast adaptation of deep networks. In JCML, 2017.
Jordi Fonollosa. Sadique Sheik, Ramón Huerta, and Santiago Marco. Reservoir computing compen- sates slow response of chemosensor arrays exposed to fast varying gas concentrations continuous monitoring. Sensors and Aciuators B: Chemicul, 215:618 1-619,66---22 2015.
Alex Hanna, Emily Denton, Andrew Smart, and Jamila Smith-Loud. Towards a critical race method- ology in algorithmic fairness. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pp. 501-512, 2020.
Michael Bonnell Harries, Claude Sammut, and Kim Horn. Extracting hidden context. Machine Learning, 32(2):001-126, 1998.
James Harrison, Apoorva Sharma, Chelsea Finn, and Marco Pavone. Continuous meta-learning without tasks. In ICLR, 2019.
David P. Helmbold and Philip M. Long. Tracking drifting concepts by minimizing disagreements. Machine Learning, 14(1):27-45, 1994.
Judy Hoffman, Mehryar Mohri, and Ningshan Zhang. Algorithms and theory for multiple-source adaptation. Advances in Neural Information Processing Systems, 2018.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks, In CVPR, 2017.
Ahmet Iscen, Giorgos Tolias, Yannis Avrithis, and Ondrej Chum. Label propagation for deep semi-supervised learning. In CVPR, 2019.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans. Josh Gardner, Zachary Garrett, Adrià Gascón. Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateck Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1-2): 1-210, 2021.
11

---

Under review as a conference paper at ICLR 2023
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher processes and bounding the risk of function learning. In High dimensional probability 11, pp.
Springer, 2000.
Jonathan Krause, Benjamin Sapp, Andrew Howard, Howard Zhou, Alexander Toshev, Tom Duerig, James Philbin, and Li Fei-Fei. The unreasonable effectiveness noisy data for fine-grained recognition. In ECCV, pp. 301-320, 2016.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009,
Dong-Hyum Lee. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. Workshop on challenges in reprexentation learning, ICML, 2013.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation with multiple sources. In Advances in Neural Information Processing Systems, 2008
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. In COLT, 2009.
David A. McAllester. PAC-Bayesian model averaging. In COLT, 1999.
Geoffrey J. McLachlan and Thriyambakam Krishnan. The EM algorithm and extensions. John Wiley & Sons, 2007. ISBN 0-470-19160-0.
H. Brendan McMahan, Eider Moore, Daniel Ramage, and Seth Hampson. Communication-cfficiinnn learning of deep networks from decentralized data. In AISTATS, 2017.
Elliot Meyerson and Risto Miikkulainen. Modular universal reparameterization: Deep multi-task learning across diverse domains. In Advances Neural Information Processing Systems, 2019.
Shira Mitchell, Eric Potash, Solon Barocas, Alexander Amour, and Kristian Lum, Algorithmic fairness: Choices, assumptions, and definitions. Annual Review of Statistics and Its Application, 8 (1):141-163, 2021.
Krikamol Muandet, David Balduzzi, and Bernhard Scholkopf. Domain generalization via invariant feature representation. In ICML, 2013.
Bengt O. Muthén. Latent variable modeling in heterogencous populations. Psychometrika, 54(4): 557-585, 1989. ISBN: 1860-0980 Publisher: Springer.
Bengt O. Muthén. Beyond SEM: General latent variable modeling. Behaviormetrika, 29(1):1-117 2002. ISBN: 1349-6964
Publisher: Springer.
Ishan Nigam, Pavel Tokmakov, and Deva Ramanan. Towards latent attribute discovery from triplet similarities. In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 402-410, 2019.
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering. 22(10))1345-1333 2010. ISSN 1041-4347.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito,o Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, 2019.
Michael J. Pazzani and Daniel Billsus. Content-based recommendation systems. In The adaptive web, pp. 325-341. Springer, 2007.
Anastasia Pentina and Christoph H Lampert. A pac-bayesian bound for lifelong learning. In ICML, 2014.
Kate Rakelly, Aurick Zhou. Deirdre Quillen, Chelsea Finn, and Sergey Levine. Efficient off off-policy meta-reinforcemmet learning via probabilistic context variables. In /CML. 2019.
12

---

Under review as a conference paper at ICLR 2023
Esteban Real, Jonathon Shlens, Stefano Mazzocchi, Xin Pan, and Vincent Vanhoucke. Youtube- boundingboxes: A large high-precision human-annotated data set for object detection in video. In 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 7464-7473. IEEE, 2017.
Omer Sagi and Lior Rokach. Ensemble learning: A survey. WIREs Data Mining and Knowledge Discovery, 8(4);e 1249, 2018.
Rajhans Samdani, Ming- Wei Chang, and Dan Roth. Unified expectation maximization. In Proceed- ings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2012.
Jeffrey C. Schlimmer and Richard H. Granger. Incremental learning from noisy data, Machine learning, 133):117-34, 1986.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, Cambridge, 2014.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The coarelly-gate mixture-of-experts layer. In ICLR, 2017.
Jamie Shotton, John Winn, Carsten Rother, and Antonio Criminisi. Textonboost for image under- standing: Multi-class object recognition and segmentation by jointly modeling texture, layout, and context. International journal of computer vision, 81 81(1):2-23, 2009.
Anders Skrondal and Sophia Gabe-Heskethh Generalized latent variable modeling: Multilevel, longitudinal, and structural equation models. Chapman and Hal//CRC, 2004. ISBN 0-429-20549- X.
Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae- Jae-Gil Lee. Learning from noisy labels with deep neural networks: A survey. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-19, 2022.
Valentin Spitkovsky, Hiyan Alshawi, Daniel Jurafsky, and Christopher D Manning. Viterbi training improves unsupervised dependency parsing. In Proceedings of the Fourteenth Conference on Computational Natural Language Learning, pp. 9-17, 2010.
Xin Su, Yizhou Jiang, Shangqi Guo, and Feng Chen. Task understanding from confusing multi-task data. In ICML, 2020.
Chuanqi Tan, Fuchun Sun, Tao Kong, Wenchang Zhang, Chao Yang, and Chunfang Liu. A survey on deep transfer learning. In International conference on artificial neural networks, 2018.
Rohan Taori, Achal Dave, Vaishaal Shankar, Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustness to natural distribution shifts in image classification. In Advances Neural Information Processing Systems, pp. 18583-18599, 2020.
Sebastian Thrun and Lorien Pratt (eds.). Learning to learn. Kluwer Academic Publishers, Boston, MA, 1998.
Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27( 1984.
V. N. Vapnik and A. Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264 1971.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
Andreas Veit, Serge Belongie, and Theofanis Karaletsos. Conditional similarity networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp- 1781-1789, 2017.
Phong D. Vo, Alexandru Ginsca, Hervé Le Borgne, and Adrian Popescu. Harnessing noisy Web images for deep representation. Computer Vision and Image Understanding, 164:68-81, 2017.
13

---

Under review as a conference paper at ICLR 2023
Mei Wang and Weihong Deng. Deep visual domain adaptation: A survey. Neurocomputing, 312: 135-153, 2018.
Gerhard Widmer and Miroslav Kubat, Effective learning in dynamic environments by explicit context tracking. In ECML, 1993.
Ruihan Yang. Huazhe Xu, Wu, and Xiaolong Wang- Multi-task reinforcement learning with soft modularization. In Advances in Neural Information Processing Systems, 2020.
Huaxiu Yao, Ying Wei, Junzhou Huang, and Zhenhui Li. Hierarchically structured meta-learning. In ICML, 2019.
Seniha Esen Yuksel, Joseph N. Witson, and Paul D. Gader. Twenty years of mixture of experts. IEEE Transactions Neural Networks and Learning Systems, 23(8):1177-1199 2012.
Cha Zhang and Yunqian Ma. Ensemble machine learning: methods and applications. Springer, 2012.
Min-Ling Zhang and Zui-Hua Zhou. review on multi-label learning algorithms. IEEE Transactions on Knowledge and Data Engineering, 26(8):1819-1837, 2014.
Zhilu Zhang and Mert Sabuneu. Generalized cross entropy loss for training deep neural networks with noisy labels. In Advances in Neural Information Processing Systems, pp. 8792-8802, 2018.
Xiangyun Zhao, Haoxiang Li, Xiaohui Shen, Xiaodan Liang, and Ying Wu. A modulation module for multi-task learning with applications in image retrieval. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 401-416, 2018.
Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization in vision: survey. arXiv preprint arXiv:2103.02500 2021.
Zhi-Hua Zhou. Ensemble learning. In Machine Learning, pp. 181-210. 2021.
Luisa M. Zintgraf, Kyriacos Shiarlis, Vitaly Kurin, Katja Hofmann, and Shimon Whiteson. Fast context adaptation via meta-learning, In ICML, 2019.
14

---

Under review as a conference paper at ICLR 2023
APPENDIX
A CONNECTION BETWEEN LEAF AND EM
A.1 DERIVATION DETAILS OF E-STEP AND M-STEP OBJECTIVES
In this section, we provide the derivation details of the E-step and M-step objectives stated in Sec. 2.3 As we have mentioned in the main text, we reinterpret LEAF through the lens likelihood maximization and seek to maximize the conditional likeeiiiddoo
K
logpe (Y (X) =
log
pe py("), hx |x
k=
where X = (xx11 ))n) and Y (yll y m.n
We then show that lower bound of the
conditional likelihood
p is given by
po (y hi x²1)
log pe (Y X)
log
(hax)
g(h(z)
h=1
(1ba) log pe Ma x(()
g(bxx)
(10)
(bb, log [p(nx |x" (yl'' hx))
g(hx) log g(hx),
F)
where is arbitrary posterior distribution over the model set H, and the second step in the derivation follows from Jensen's ' Inequality. The EM algorithm can then be considered as performing coordinate ascent alternating over y and O, corresponding the E-step and the M-step, respectively. Using Viterbi EM (Brown et al., 1993 Spitkovsky et al. 2010; Samdani et al. 2012). we assume that q is Kronecker- Delta distribution, which outputs non-zero probability mass only single point. Due to the unimodularity of simplex constraints (Samdani et al. 2012), this results in an analytic q:
(h) 5 h arg max log po (y |xx))
WeH
(11)
8 h arg max log p(h' xx pe (y |xx),11) h2')
Well
By assuming uniform model prior p(h x) we have
q(h) á (n = arg max log log (y |x (1))))) WEH
(12)
Given the posterior q and the uniform model prior, the M-step we maximize
7
F(O)
Σ
(hv,) log pe("")) |x hx))
(13)
Adaptation to the batch setting. The model posterior given by Equation (2) is estimated based on each data pair ")). Note that in each data batch, different data pairs are i.idd. drawn from the sampled domain. We can leverage this fact to integrate the estimations of the model posterior obtained by different empirical examples.
For example, consider the i-th batch Z = {(x1), > Since different data pairs (xM, y²),, [n] are i.i.d., their corresponding posteriors ((h) are also identical. Hence, given the data batch
15

---

Under review as a conference paper at ICLR 2023
Z' y we have
((h) a(h) (²) = q(h) x² y
Vj E [n)
log pe py |x 129
(14)
= 6 h arg max h'EH
Similarly, rewrite the overall M-step objective
13
m
F(O)
ah
x² y²) log log (y |x hw)
K
(hv Z')
log (y xx hx)
(15)
K
(hk
log (y |x hw).
We then write the E-step and the M-step objectives in the i-th batch as:
E-step: set ((h) = 06 = arg maxNEH Σラ= log pe xx, ,n)
M-step: given 9, maximize
K (*)) = Σ g(ha)
log
(16)
A.2 DISCUSSION ON THE ALLOCATION FUNCTION AND MODEL POSTERIOR ESTIMATION
In Sec. 2.3 we motivate an analytic form of the allocation function using an EM-based maximum likelihood formulation. However, the exact equivalence between the E-step in EM and the allocation function has not been rigorously proved since it relies on the exact forms of the loss function & and the conditional likelihoods pe (y x h). As complement, in this section consider standard regression and classification settings, and show that the exact equivalence between estimating the model posterior and the allocation function can be obtained under some natural assumptions on the loss function and conditional distribution families.
A.2.1 REGRESSION WITH ISOTROPIC GAUSSIAN JOINT LIKELIHOOD
Consider a regression task where we assume that for each example (xx), "yy"")) ), i E [m], j E [n]. the joint distribution of conditional likelihoods pe (y (x),,,)) E [K] conforms to an isotropic Gaussian Nu o² Ix) with mean 2 = (x1(x)), h2(x)), h (xx))) and variance o² 22
where I is K x K identity matrix. We then write Equation (14)
(hh) = 8 h = arg max
log (y 1x9,1))
K'EH
1
(y'j - 1 1))
8
h arg max
log
exp
KEEH
VTT
20
J=1
(17)
Σ/= (y+t - 11' (()2)))8
0
h arg max log WEH
exp
(2T) 2/ nn
20
0 h
arg min KEH
Σ (y" - )
This amounts to the empirical allocation function 7 with squared loss Ely, v') (y -/²²2.
16

---

Under review as a conference paper at ICLR 2023
A.2.2 CLASSIHICATION WITH INDEPENDENT CATEGORICAL LIKELIHOODS
Consider an L-way classification task where we assume that for each example (x" y i E [m], j e [n]. the distributions of conditional likelihoods pe (y'2 |x' hx), [K] conform to independent cat- egorical distributions with parameters (A 1 ... Agg
(h1 (xx)), h2(xx)).. . (x²)).
where each h& (x*) ) (Iea (x*)). har (x*)) )) k E [K] is an I-dimensional, non-negative vector that sums up 1, representing the probability of each category. We apply an one-hot encoding the
labels and let each y (vi ... .92) .9)) {0, 17 with Σ vi 1. We then write Equation (4 as
(hh) arg max
log pe (y 11)))a))
ham)
HICH
Σ log
New (2))
arg max HIEH
(18)
Di log hws (xx)
arg max H
h arg min
Vi
3 log has {x((x(5))
This amounts to the empirical allocation function 7a with cross-entropy loss E(y, v/ = Σt= y1 log
A.3 LEAF WITH STANDARD EM
In this section, we discuss an alternative choice of a (stochastic) allocation function using standard we can write the E-step and M-step objectives in the i-th
EM. Following the derivation Sec. A.I batch as:
E-step: set q(h) p(hl Z*).
M-step: given 9, maximize
K (O) Σ g(hx) k=1
Σ log ly hx))
(19)
The difference is that in standard EM, the maximization in the E-step is done by setting g as the posterior p(h] Z²). By Bayes' theorem, we have
p(h| 12') p(h) p(Z' (h)
2(Zi)
p(h) 11 p(x h) II; Poly'i |x(5,n)
(20)
p(z+)
C II ( ()).
where C' can be viewed normalization constant. As in Sec. A.2 in the sequel provide implementation of this LEAF variant in both regression and classification settings.
A.3.1 REGRESSION WITH ISOTROPIC GAUSSIAN JOINT LIKELIHOOD
We consider the same regression setting as in Sec. A.2.I where the joint distribution of conditional likelihoods pe (y x hw), k E [K] conforms to isotropic Gaussian. We then write Equation (20)
17

---

Under review as a conference paper at ICLR 2023
p(h) ((61z²)
C. II
pe py hx
1=1
(21)
Eラ= (y - h(x()))² 1xx))) 27
1
=C
(2 exp
20²
This gives the normalized model posteriors
p h4 Z*)
p(h (2)
Σ k
m= pl (*))
2ij=1 (y
hr (xx)
(22)
exp
Vk [K].
Σm exp
Lijn (yis (xbr))))
2x
In other words, each model in the model set is sampled according softmax probability determined by their negative squared losses on the data batch and a variance parameter 20², which reflects the noise of the regression outputs. Since o² is generally unknown, in practice treat this as additional hyperparameter (details are in Sec. D)
A.3.2 CLASSIFICATION WITH INDEPENDENT CATEGORICAL LIKELIHOODS
We consider the same classification setting as in Sec. A.2.2 where the distributions of conditional likelihoods (y x² h2,, E [K] conform independent categorical distributions. We then
write Equation 20 as
p(h1 = II
po po 1x ht)
/=1
(23)
C
ha (x"))11".
/=1|=
This gives the normalized posteriors
pl1k Z²)
p(he 7
Σm p(liml 2²)
exp vi" log (xx((()))
(24)
Vk E [K].
ΣK exp
V1 log h (xtt)
In other words, each model in the model set is sampled according to a softmax probability determined by their negative cross-entropy losses on the data batch.
A.4 CONVERGENCE GUARANTEE OF LEAF
In this section, discussion the convergence guarantee of LEAF based on existing convergence guar- antee of (generalized) EM. It has been shown that under fairly general conditions on the monotonicity of the likelihood with respect to posterior in each iteration. the likelihood values in (generalized) EM converge to stationary points with zero gradients [McLachlan & Krishnan) 2007). On the other hand, in the analysis above, we show that for the setting of regression with squared loss and classification with cross-entropy loss, LEAF is essentially equivalent to likelihood maximization using type of generalized EM method. These two facts then indicate that LEAF can converge to a stationary point of the empirical error 3 under the monotonicity condition that each iteration decreases the empirical error 3) by improving the allocations. In practice, this monotonicity condition may not strictly hold if we parameterized DNNs the low-level models of LEAF, due to the non-convexity of the training objective. However, empirically we found that LEAF always converge stably in all of our experiments.
18

---

Under review as a conference paper at ICLR 2023
Algorithm LEAF
Require: Model set H { parameterized by {=x]k=1 optimizer OPT, the number of batches m, batch size meta-batch size B.
1: for 1,2, ; batches do
2: Sample the examples {xx", ""
1j=1-
3: Select model from the model set: h E arg mingen Σj=1 (1((x)),)))
4: Compute the gradients grad* +- Ve ビラ=1 (x*)),)))))
5: if = 0 (mod B) or = m then
6: Average the gradients over B batches: grad + B Ep=o grad
7: Update model parameters θ < OPT(O, grad).
8: end if
9:
end for
B ALGORITHM PSEUDO-CODE
We provide the pseudo-code of LEAF in Algorithm In our implementation, introduce meta- batch size hyperparameter and average the updates in each B meta-batches. This similar to the mini-batch training in standard supervised learning in order obtain more stable parameter updates and improve the robustness against the noise during optimization.
C PROOFS OF THEORETICAL RESULTS
In this section, we provide the full proofs of Theorems ! and prove a generalized result of Theorem in the main text. For better exposition, restate each theorem before its proof.
C.I PROOF OF THEOREM !
Theorem (Identifiability of conflicting domains). The following two propositions are equivalent:
(i) For the domain distribution Q satisfying that Q(d) >> 0 for every d E D, the expected error of LEAF satisfies er er(H) O.
(ii) For each domain (P, c) in D, there exists H such that Ex~ [h(x). c(x)] = 0.
Proof. Recall the definition of the expected error er(H) under the expected allocation func- tion 7b):
er H E, - (P.c)- min Ex [h(x), c(x)].
(25)
helf
The derivation of proposition (i) from proposition (ii) directly follows from the definition (25 by expanding on the first expectation operator over the domain distribution Q.
Reversely, we prove proposition (ii) from proposition by contradiction. Suppose proposition (ii) is false. Then, there exists d, = (P,, E D (i E [N]) such that for all h4 H ( E [K]). Ex-p, (x), (xx) > 0 holds. We thus have
er(H) = =E==(PP) min Ex-pl [l(x), hEH
2 ((d,) min Ex E (M(x), (x))] heh
(26)
> 0.
This is in contradiction with proposition (i). Therefore, proposition (ii) must hold if proposition (i is true. This completes the proof.
C.2 PROOF OF THEOREM 2
We start by revisiting the definition of PAC learnability (Valiant 1984).
19

---

Under review as a conference paper at ICLR 2023
Definition 4 (PAC learnability, single-domain case). A target function class (concept class) C is said to be PAC-learnable if there exists an algorithm A and a polynomial function poly(....>> such that for any 0 and >> O, for all distributions P on X and for any target function c C, the following holds for any sample size 2 poly (4e, 1/8, Hi, size((c))
Ps-Pi [Ex-pl (hs (xsxx),((x) S 2c
(27)
where hig E H. is the hypothesis returned by algorithm A after receiving labeled sample S, k. is number such that the computational cost of representing any element I E X is at most ((k), and size(c) denotes the maximal cost of the computational representation of of E.
Since the goal of our setting is to learn multiple target functions simultaneouslly (correponding to all target functions in the domain set). we introduce a natural extension of Defimition 4 to the multi-domain case. Given domain set = {Pi, ci) J.Y with cardinality N and confliting rank R(D), we denote by C := {c (P.c) E D its corresponding target function set that contains all target functions belonging to the domains the domain set D, and denote by C a target function set class in which each element is target function set. Following the formulation in Sec. 22.1 we allow the algorithm A to return hypothesis Hg { HK (rather than a single hypothesis as in the standard PAC learning model) given a labeled sample S that is drawn according to the bilevel sampling process as in Sec. 2.1
Definition 5 (PAC learnability, multi-domain case). A target function set class C is said to be PAC-Icarnable if there exists an algorithm A and a polynomial function poly(;,....) such that for any 0 and 5 > O, for all distributions Q D = {(P, G.) Jim for all distributions PI, Py on X, and for any target function set E C. the following holds for any sample size mn poly (2/e, 1/6, K. size(C)):
Ve C, 3he E Hg such that Is's [Rx~ [M(x), (Mx) 162
(28)
where Hs E H. is the hypothesis set returned by algorithm A after receiving labeled sample S, number such that the computational cost of representing any element x E X is at most O and size(C) denotes the maximal cost of the computational representation ofC E C.
Before proving Theorem 2 we first prove a lemma:
Lemma If LEAF is PAC-leurnable according to Definition 5 then there exists an algorithm A
such that for any 5 > O, the hypothesis set Hs returned by A after receiving labeled sample S with infinite examples satisfies
Ps [er(Hs) 0) - 5.
(29)
Proof. Recall the definition of the expected error er H under the expected allocation func- tion 7b)
er H)) (P min Bx-nr [M(x), c(x))
(30)
heh
Suppose that LEAF is PAC-learnable. Then, Equation 28 holds for the sample size mn 2 poly(1/s, 1/8, Ke, size(C)) By setting - have that for any 0 >>>
Ve C, 3h Hg such that Ps [E (1(x), c((x), 0] > 1-
(31)
holds when the sample size is infinite. This equals to
min Ex-pl [h(x), c(x)] = 0) 2 21-8
Ps
(32)
hell
for every d (P,c) E D. By replacing â with 6/N in Equation (3) and a union bound argument, we have that for any distribution Q on D,
Ps
Ea=(P,) min Ex (((x))c(x)) beHs
0 =0 2 1-
(33)
holds. Combining Equations
30
completes the proof.
Now are ready to prove Theorem 2
20

---

Under review as a conference paper at ICLR 2023
Theorem 2 (PAC learnability). For domain set D with conflict rank R(D) and model set with cardinality K, a necessary condition of the PAC learnailiity of LEAF is 2 R(D).
Proof. Recall the definition of conflict rank (Definition 2
R(D)
max min SCX DES
{c(x)) I (P.c) E D2æ supp(Pi)}
(34)
where X(S) is the Lebesgue measure of S. In what follows, drop the dependency of R(D) on the domain set for simplicity, and denote the conflict rank of the domain set by R. From Equation (34). have that there exists subset S X such that X(S)
and there are R distinct domains d(R) = (((R). (R)) in the domain set D satisfying
d(1)= = (Pt) Cun),
((1)()) + (2))(a)) + + (z)
(35)
for all x E S. We now prove the main result by contradiction. Suppose that K < R. by the drawer principle, we have that there exists el E E(c)) G(2): ... c(x) such that
vh H, el (x) + h(x))
(36)
holds for all x S. We then have that
er(H) = (d=(P.o)
min Ex-rl NEW
2 Q (d)
min
E m [M(x),
bEH
Q (d'
min
((M()), apt(x)
(37)
bEH
2EX
2 Q (d
min
e c (P)(x)
hEH
JES
>
holds with probability 1. On the other hand, by Lemma 1 we have that if LEAF is PAC-learnable, then there exists an algorithm that outputs hypothesis set Hg satisfying er(Hs (H5) = with probability 1 - 8 for any 8 > O, which is in contradiction with (37). Therefore, we must have K R.
C.3 GENERALIZED THEOREM 3 AND PROOF
In this section, we state and prove a generalized version of Theorem in the main text. Sec. 2.1 formulate LEAF by a bilevel sampling procedure: first, domains are i.id. drawn from domain distribution Q over the domain set D, resulting in m batches; then, for each batch, n inputs are i.i.d. drawn from the corresponding domain's input distribution and labeled by its target function. Here relax the second step of this sampling process by allowing the data in each batch to be drawn from other domains apart from the sampled domain. This models a general and more realistic scenario where each data batch is not absolutely "clean" and may contain a small portion of "noisy" data from other domains.
Formally, we introduce a mixing ratio parameter a E [0, 1) that captures the expected percentage of noisy examples: for each data pair in the i-th (i E [n]) batch, with probability 1 a is drawn from the sampled domain d' = (P", e²), and with probability a it is drawn from other domains in the domain set, i.e., D C D {d'). This amounts to sampling from a mixture of input distributions Piix (1 - Pi + afi where pi is the input distribution of one or a mixture of multiple domains from D {d'}. Correspondingly, we also introduce a "mixed" target function denoted by ciixx = (1 (1- a) d + ač', which indicates that the input will be labeled by of sampled from pi while labeled by if sampled from pi.
Clearly, the mixing ratio needs be small for effective training, but would also like to theoretically investigate how the generalization error of LEAF relates to a.
Now are ready to state Theorem 4 which is generalization of Theorem 3 in the main text:
21

---

Under review as a conference paper at ICLR 2023
Theorem 4 (Generalization entor upper bound). For any mixing ratio E [0, 1) and any ò E (0. 1]. the following inequality holds uniformly for all model sets H E H with probability at least 1 - 6:
1 +
1
((S) (In (5)) + 1) In 8/24
1
Hr
a (
(38a)
a-a
m
m
1
m
(S) (In 2m4,, n/s(n)((s))))))))) 1) In 9/12N
1
(38b)
myn
2
2(S) (In 20/2/ + 1) - In 6/24m 1
(38c)
1-a
where S = {minnen(PPc) + Ex [h(x: θ) c(x)]} is the function set of the domain-wise expected error, S (a, + e [h(z; 0), } is the function set of the instance-wise error, my Ein 1 (d' = dR).
[N] is the count of the k-th domain in the domain set D during the sampling process, and (-)) is the SomikkChhrvvonenis (VC) dimension Vapnik & Chervonenkis 1971 for some set of real functions
Remark 3. It is straightforward recover Theorem 3 in the main text using Theorem 4 by setting the mixing ratio a = O.
C.3.1 TECHNICAL LEMMAS AND INTERMEDIATE RESULTS
Before giving the proof of Theorem (generalized Theorem 3) we first introduce several technical lemmas.
Lemma 2. Let { [Eiji=) be set of events satisfying I (EE) 2 1 - 6; with some 6, 2 0, = 1,.
Then, TP (n Ex) 2 Σi= 8,
Proof. Straightforward using the union bound.
The next lemma is well-known result in statistical learning theory Vapnik (199), and is standard tool for upper-bounding the generalization error of empirical and expected data distributions:
upper bound (Vapnik (999)). Let Z be space, and let A be a parameter space. Lei A < Q(2; a:) < B, a E A be a measurable and bounded real function set, of which the VC-dimension (Q)). Let {z, [= be the data set sampled i.i.d. from a distribution P on Z with size n. Then, for any E (0, 1). the following inequality holds with probability at least 1 8:
Lemma 3 (Single-task generalization
EzpP ((z;a)= - Σ (zz a)) $ S - ())e))((() + n
(39)
where
(nn 9(2) ( + 1) In 1/4
(40)
n
Given the technical lemmas, we now present some intermediate results that will necessary in the proof of Theorem 4 We define the following shorthand:
h helean E Earg min Ex [h(x), cxx)),
(41a)
REH
ig E aag min
Σ (x(((x)) ,*J,
(41b)
KEH
"The standard VC-dimension is defined on sets of indicator functions and thereby only applies to the binary classification setting. Here we adopt generalized notion of VC-dimension, which is defined on real function sets and thus applies to general loss functions, while having no impact on the forms of the generalization error hounds. See Chapter 3 of /Vapnik 1999) for details and discussion.
22

---

Under review as a conference paper at ICLR 2023
where i E [m] denotes the i-th batch of LEAF, and H is the model set. Note that here the arg operator defined on the model set H rather than the hypothesis space H. For each batch with index i, we also define a clean data batch elean = { (xeleau y ) that i.i.d. drawn from d', corresponding to the case with mixing ratio a = O. Recall that we use superscripts to denote the sampling index. e.g., d' (Pi, c²) denotes the i-th domain sample, which can be any domain the domain set D.
We first prove a lemma that upper- bounds the generalization error induced by the discrepancy between the empirical and expected domain distributions:
Lemma 4 (Domain estimation error). Let Q be distribution over the domain set D, and let d' = =P' .P)....)... , = (Pm, c be domain examples i.i.d. drawn from Q. Then, for any δ E (0, the following inequality holds uniformly for all model sets H E HK with probability at least 1 --: 8:
dd
helf min Ex [1(x)), cxx) - Ba,~ min 18x~ p, [h(x), ( c(x))
(42)
In (2m/ + In 8/4
((Pcc) + minnen it pl (1(x; θ), c(x))} is the function of the domain-wise expected error, and (-) is the VC-dimension of some set of real functions.
where S
Proof. We define "domain--veraged" loss function over the model set H and the domain d = (P.c):
Č(H, d) = min pl [h(x), c(x)]
helf H
Then, we have
min px c - Edin min Ex [h(x), REH
beHf
E dH, E (H,d)).
Finally, replacing the function set Q Lemma
with
S
{(P.c)
mingen Ex [h(x: 0), c(x)]} completes the proof.
We then prove lemma that upper-bounds the empirical error induced by the discrepancy between the empirical allocation function (7a) and the expected allocation function (b)
Lemma 5 (Allocation estimation error). Let {(x*), y"") be the data batch drawn in the i-th (i E [m]) batch of LEAF with mixing ratio Then, for any [0.1) 1) and any 5 (0, 1). the following inequality holds uniformly for all model sets H E H. with probability at least 8:
m
m
(x11 (xclean)
[h (xx) y'6]
y clean
m
m
j=1
j=1
( In (2m/2(S) + 1) 6/12
α
(43)
S <a er 11) t
(S) 2n/215/ + 1) In 6/12m 2
-
n
where S = ((.c)) + mingEH Ex [x(x: θ), c(x)]} is the function of the domain-wiss
expected error, S = { {xx y) + [1 f), y)} is the function set of the sample-wise -isee error, and 9 is the VC-dimension of some set of real functions.
23

---

Under review as a conference paper at ICLR 2023
Proof. We have the following decomposition:
m
(Xclean)
y
clean
m
1
8 hi (xx1) .34)
m
m
n2 j=1
Middea (Xolean)
- Ex [ Caccceeam(( (x), o² cx
.Yolean
(44)
m
pio [H (x), c(xx] Exnran mix
[R]((x)) cinixe (xx)
171
m
12 Σ j=1
Exppi l [x((x)) m (mx))
hi (xx) s01
m
n
in which the original difference is decomposed into three terms in the RHS.
We can use the following technique bound both the first term and the last term: by substitut- ing Q in Lemma with S = {(z.8) v) + é (1; sI} and replacing 5 with 4/3m, every term
in the summation operator can be upper-bounded by ( In (2n/2(S) 1) In 1/12m 1
71
n
with probability at least 1 - 6/3m: we then combine the terms in the summation operator using Lemma 2 showing that both the first term and the last term in the RHS of (44) can be bounded by
( In (2n/9(5) 1) In 6/12m
+ n
with probability at least 6/3.
n
There remains the middle term in the RHS of (4.. for which we have
m
Ex [N (x), c² (x)] E Ex e [h)(xx), cini ( (x))
1=1
pil [Mictean (x), o² cx(x) Exapie [1(()))
(45)
m
Ex
of (x)] pil [x)
m
By the definitions in 41a) and (41b), the first term in the RHS of (45) is non-positive and thus can be upper-bounded by zero. For the other term, we have
m
Ex ll [Mr.llann (x), (xx)] Exmpil (xx()))((x)))
m
E Exp l (h), cz (xx]
er(Hr a
Σ pxl (x),
Edi-Q min Ex-r, (M(x), cx()) WEH
where the inequality is due to the nonnegativity of the loss function l. By replacing with 8/3 in Lemma 4 the second term in RHS of the last line can be upper-bounded by 2 In
In 6/12 a with probability at least 1 - 8/3.
Finally, combining the above three bounds corresponding to the terms in the RHS of 44 using Lemma 2 completes the proof.
C.3.2 PROOF OF THEOREM 4 (GENERALIZED THEOREM 3
Now are ready to give the proof of Theorem
24

---

Under review as a conference paper at ICLR 2023
Proof. Combining the empirical and expected objectives B we have
4 with the allocation functions 7a 7b
er(H) - (r) Ba min Ex (M(x),, cx(x)]
min Σ e [b (xx) .y (46)
REH
where for every E [m]] the data ((x2, y is sampled from P Pinx = (1 a) + a Pt and
labeled by cixx = (1 - a)c' + ač' with mixing ratio a E (0,
We then have the following decomposition:
1 m
er(H) - (H)
min Ex (x)x)))(()) beh
Σ
min Ex Ex (x(x)),'(x)) hell
m
m
m
min E pal l [h(x), of (x)] be
Ni (x (x
Y
clean
m
772
m
m
hictean (xeleam)
6 [h (x*1) ,
y
clean
min hEH n
m
m
(47)
Applying the definitions in (41a) and (41b), we rewrite the equation above:
1 m
er(H) - - EdinQ beH
min Ex ((xxx).(()))
min NEH
Ex [h(x),, cf
m
m pi pol (hi (x), [x)]
hi (xe)) (x(ccaa))
y io
clean
m
m7
n
1m1
m
m
n
Thg (xx) .
h Melean (xelean)
Y clean
m
m
(48)
in which the generalization error of LEAF is decomposed into three terms. These terms represent different aspects that impact the generalization error:
The first term represents the discrepancy between the expected and empirical domain distributions.
The second term represents the discrepancy between the expected and empirical data distributions in each batch.
The last term represents the discrepancy between the expected and empirical allocation functions. Note that when the mixing ratio a > 0, this term also accounts for the discrepancy induced by the noise the data batches.
In the sequel, we bound these terms separately to derive the final generalization error upper bound:
Bounding the first term. By replacing 8 with 9/6 in Lemma 4 have that
Ed min Ex- e (x(x), hEH
Σ
min helt
Ex (x(
(49)
9 In (2m/ 1) In 5/24
m
m
holds uniformly for all H HK with probability at least 6/6.
25

---

Under review as a conference paper at ICLR 2023
Bounding the second term. By rearranging the terms and use my Σ 1 (c' = ck): [m), & E [N], we have
1
pil l Clenn (x))
h Millean
(xéleat)
y clean
m
m
j=1
m
Ex-pil I (x), cx(x)
Σ
M (xilear)) Ecleau
m
i=l
N
nmm Σ
my - Ex [ha (x), cx()]
he (Xk,clean Sk,ctean)
m
==1
N
Ex (x),
[hk (xle V k,
mk
m
In the above, we rearrange the total m data batches according to the domains they belong to. With little abuse of notation, in the third and fourth lines use hig denote the hy- pothesis that yields the smallest expected error in the k-th domain in the domain set D, i.e., hi = arg minje Ex-P, [[(xx,, cx()] examples so that the examples from the same domains that emerge multiple times can be accumulated and jointly considered, which leads to a sharper and more realistic error bound. In this way, we use {(x, {(xk,cleam Vkkelean)) ) & E [N] to denote the aggregated data that belongs to k-th domain in D. By replacing d with 6/NN in Lemma] for every E [N] and å E (0, 1] we have that
[N]. The above transformation aggregates the domain
1
Ex (x), Cx (x)]
nm, Σ e [ig (rkj, Ukj)]
((8) (In 2m (SS) + 1) In 6/12N
mgn
m
holds uniformly for all H HK with probability at least 8/SN. By Lemma 2 we have that
px pil (hi (x), (x)]
hi
(x
771
m
1=1
(50)
my
(S) (In 2m/n/2(8) + 1) In 6/12N
m
mgn
mr
holds uniformly for all H E HK with probability at least - 6/3.
Bounding the last term.
By replacing 8 with 6/2 in Lemma
we have that
m
m
hi
(xxlean)
y Yclean
hG (xx) .80²
m
m
n2
j=1
i=1
j=1
2 (2m/915)) + 1) - In 6/24
a
(51)
< a (r(H) + a
(IS)(In 2n/9(8) + 1) In 6/20m 2
+ +2
holds uniformly for all H HK with probability at least 6/2.
26

---

Under review as a conference paper at ICLR 2023
Finally, combining the above three bounds 49
50
5
using Lemma gives that
( In (2m/2(5) + In 8/24
- ((H)-E((1))
m
m
N
mk
(S) (In 21m (m/n//(()) + 1) In 1/2N
+
m
myn
mn
k=1
(52)
Φ In (2m (2/ + + a er (H) +
In 6/24
a
+
77
772
(SS) (2nn2222///// 2n/ 1) In 6/24m
+ +
n
n
holds uniformly for all H E 7tth with probability at least 1 - 8. A simple transformation of the above inequality completes the proof.
D EXPERIMENTAL DETAILS
In this section, we provide additional details our experiments. All of our experiments are conducted based on PyTorch (Paszke et al. 2019) using a NVIDIA 2080ti GPU. The datasets we use can be downloaded from public data sources, and does not contain personally identifiable information or offensive content.
D.1 REGRESSION
We consider regression scenario in which the examples are randomly sampled from three heteroge- neous functions in absolute, sinusoidal and logarithmic function families:
y 2 | + nnoise: -2 S x 2
y 2 sin
3z + 2 Enoise: -
(53)
3 y 2 log
Snoise
-2 x 52
where &noise (0, 2. is the additive Gaussian noise. We consider each function domain, and set the parameters of L.AF as m = 250, = 2, i.e., a total number 500 examples are collected in 250 batches, each with two examples. In each batch, randomly select function and uniformly sample the examples from the selected function.
Model and optimizer. We use a model set with three neural network regressors with the same architecture. Each network consists of five fully-connected layers, with 32 neurons in each layer and ReLU nonlinearities between the layers. We use a standard SGD optimizer with learning rate 0.05, momentum = 0.9, and lg weight decay = 10 to train these models.
D.1.1 BASELINE DETAILS
MAML. We use standard PyTorch implememtation MAMI. from GitHut We adopt the same network architecture for MAMI. ours, and use the following hyperparameters:
Shot 2, Evalation 100, Outer step size 0.05, Inner step size 0.015,
Iuner grad steps 2, Eval grad steps 5, Eval iters 10, Iterations 20000.
In each batch, we use two support examples and another two query examples for MAML to fine-tune its model. Note that this amounts to batch size of four, which is larger than LEAF (with only two examples in each batch).
Modular mera-lea We use the official Py Torch implementation of modular meta-learning from " Since modular meta-learning uses more neural network modules than LEAF, we apply smaller network for each module, with the following hyperparameters:
(MIT license) httpar//athoaoccc///aaaaaaaeeeea earnin (MIT license)
27

---

Under review as a conference paper at ICLR 2023
Shot 2, Support 2, Network Linear 1 16 - 16 Composer = Sum, meto_ = 0.003, Steps = 3000.
modules 5,
Like MAML, in each batch use two support examples and another two query examples for modular meta-learning for fine-tuning, resulting in a batch size four.
Sparse MoE. We implement this baseline following the design in (Shazeer et al. 2017) where the output of the MoE model can be written as
K Σ G(t):
(54)
where G(x) and (2)2) the output of the gating network and the output of the i-th expert network for the input H, respectively. We use the same number experts as the number of low-level models in LEAF, and use the same network architecture in LEAF for each expert. In the original work (Shazeer et al. 2017). the MoE model used in language modeling tasks with no explict conflict in the training data, thus the gating network can modulate the outputs of experts only using the input æ. However, when dealing with conflicting data, only having access to the input is not sufficient for gating since different examples may have distinct outputs for the same input. Therefore, we augment the input of the gating network with the ground-truce output y, resulting in
y Σ ((.,v),E.(c)
(55)
In (Shazeer al., 2017), the authors choose noisy top-k gating strategy to obtain sparse gating function. We follow this design and further set k: = 1 as LEAF, since we only want one model (expert) be activated given an example. Concretely, the output of the gating network is given by
G(æ, y) (oftmax((KepIopl(([( vH))
(56)
where
H (I,, ([x, y] Wg): + 8 - llog (1 + exp ([x, y| W Wnoise);) if 0s is the largest element of v.
(57)
KeepTopl(U): 1o. otherwise.
which 6 ~ (0, 1) is the noise. As shown in the above, the gating network involves two trainable weight matrices, W, and Wnoise. which is trained end-to-end along with the training of all experts. This differs from LEAF that does not involve additional trainable parameters in the allocation function. During testing, show the outputs of all experts.
LEAF-EM. We implement this variant in the same way as LEAF, expect that the allocation function stochastic with the sampling strategy in Sec. A.3. This sampling process involve additional hyperparameter y corresponding to the 2,2 parameter in Equation (2); we set v = 0.1 in our experiments.
D.2 CLASSIFICATION
As stated in the main text, consider three classification settings that involve paralleled, hierarchical, and opposite input-output relations across the examples. In the sequel, we provide the experimental details on these settings separately.
Paralleled relations. For this setting, we use two datasets, namely Colored MNIST and Fashion Product Images.
Colored MNIST is an extended version of the classical digit recognition dataset MNIST. For each gray-scale digit image in the MNIST training set, we randomly color using a pre-defined color pool consisting of eight colors: (red, blue, yellow, green, pink, cyan, white, purple), and assign each colored digit with an additional color label. This results two domains in the colored dataset with 60000 training images: Digit and Color, shown in Figure 5 In each training batch, randomly select one domain and inherit the ground labels in the selected domain for all examples. We set the sampling parameters of LEAF 600000, 1, corresponding 10 training epochs. We
28

---

Under review as a conference paper at ICLR 2023
2
Domains
Color
Digit
Labels
Cyan
Figure 5: Paralleled relations:
Colored MNIST.
use model set with two neural network classifiers with the same architecture, consisting of three convolutional layers and one fully-connected layer with ReLU nonlinearities between the layers. We use the Adam optimizer (Kingma& & Ba 2015) with learning rate- 0.002 and betas = (0.5, 0.999) without weight decay for training.
Fashion Product Images (Aggarwal 2019) is a dataset for automatic attribute completion and question answering with multiple category labels. We choose three main parallel tasks with eight main labels from the original dataset, resulting in three domains namely Color, Gender, and Category containing accessories), respectively. There
labels (black, white, blue), ). ( imale.femalee and totally 1 15000 training images. In each training batch, randomly select one domain and inherit the ground-truth labels in the selected domain for all examples. We set the sampling parameters of LEAF m 750000, n corresponding to 50 training epochs. We use model consisting of three neural network classifiers with the same architecture. Each model has five convolutional layers and one fully-connected layer with ReLU nonlinearities between the layers. We use the Adam optimizer with learning rate 0.002 and betas (0.5, 0.999) without weight decay for training.
Hierarchical relations. For this setting. we use the CIFAR-100 dataset (Krizhevsky Hinton 2009), which is a widely-used benchmark for image recognition. It has a hierarchical structure with 20 superclasses and 100 classes, with 60000 images in total. Each superclass further contains 5 "fine" classes; for instance, the superclass insect contains bee, beetle, butterfly, caterpillar, and cockroach. In each training batch, we randomly select one domain and inherit the ground trunh labels in the selected domain for all examples. We set the sampling parameters of LEAF corresponding to 40 training epochs. We use model set with two neural network classifiers with the same architecture. For each model, for feature extraction for LEAF and all baselines, and add two fully-connected layers after the backbone with ReLU nonlinearities. We use a standard SGD optimizer with learning rate 0.1 and momentum 0.9 with no weight decay to train the models.
1200000, n 2,
a pre-trained DenseNet (Huang al. 2017) backbone
Opposite relations. For this setting, we use relabeled Fashion Product Images dataset to simulate the hidden context that depends on human preferences. Concretely, we re-label the Fashion Product Images dataset and construct a preference-dependen scenario with two domains: Male and Female. This simulates the scenario where the preference is based on the gender attribute. The re- re-labeling process is as follows: we randomly split the dataset into two domains according to the "gender" attribute: 50% of examples labeled as "male" and 50% examples labeled as "female" are assigned to the first domain with "male" re-labeled as "positive" and "female" re-labeled as "negative", and other examples are assigned to the second domain with "male" re-labeled "negative" and "female" re-labeled as "positive". In each training batch, we randomly select one domain and use the "positive" or "negative" attribute of the examples as the ground-truth labels for classification. We set the sampling parameters of LEAF to m = 37500, n = 20, corresponding to 50 training epochs. We use model set with two neural network classifiers with the same architecture. Each model consists of five convolutional layers and one fully-connected layer with ReLU nonlinearities as in the Fashion Product Images in the paralleled relation setting. We use the Adam optimizer with learning rate- = 0.002 and betas = (0.5, 0.999) without weight decay for training.
D.2.1 BASELINE DETAILS
ERM-top k. This baseline directly models the relation between inputs and outputs using a probability distribution p(y xx), which is the learning target. For classification problems, when different domains
29

---

Under review as a conference paper at ICLR 2023
share similar frequencies during sampling, such a distribution can be approximated with the total probability formula
x
Σ p(y d. Q(d) dED
Σ ply x, DED
(58)
DI
For conflicting data, the resulting conditional distribution is multi-modal, and network trained by the cross-entropy loss can provide an unbiased estimation of it. However, this method may suffer if the occurence frequencies of different domains differ significantly. Also, introduces a hyperparameter k used when selecting the top-k outputs; in practice we directly use the ground-truth domain number for k, which leaks some additional information for this baseline.
Semi-supervised multi-label learning, We alternatively interpret learning from conflicting classifi- cation data multi-label learning with missing labels: for a given input X, consider the "fully" labeled data (xr y {yr J/= conflicting data can then be modeled providing only one label y E y for each z, with all other labels missing (note that this a very extreme setting). Therefore, existing superviee learning approaches may be modified to handle such problems. We consider two representative techniques, including PseudoLabel (Lee) 2013) and Label propagation (Iscen) al. 2019). Both implementations are slightly modified to fit our tasks.
PseudoLabel randomly allocates additional "pseudo" labels to each input to compensate the missing labels. The learning machine is trained on the augmented dataset and then reevaluate the confidence of all pscudo labels according to its predictions. All pseudo labels will itcratively be modified during training until convergence.
Label propgation (LabelProp) builds a graph over the examples, where each node on the graph represents data sample, and each edge represents the distance of two nodes collects in the feature space. The labels are propagated on adjacent nodes until all examples are fully labeled. The feature space also iteratively adjusted during training.
Sparse MoE. This baseline follows the implementation in the regression task as detailed in Sec. D.1.1 Each expert instantiated neural network classifier with the same architecture as the models in LEAF. We resize the one-hot labels in the examples to the same height and width as input images for the gating network.
LEAF-EM. We implement this variant in the same way as LEAF, expect that the allocation function stochastic with the sampling strategy as in Sec. A.3.2
MLL oracle. We provide the label annotations from all domains simultancously for the learner, resulting in "multi-hor" label vector for each example. This transforms the original setting to standard multi-label learning problem. We train a single network with the same architecture as LEAF using the multi-hot label vectors as supervision by using binary cross-entropy loss for each dimension of the multi-hot label vector.
MTL oracle. We provide the ground-truth domain index for each example. The raw data is then partitioned into subsets for several classification tasks without conflict, resulting in a standard multi- task learning problem. We train separate networks with the same architecture as LEAF models on these subsets. We also tried adding a shared representation layer among all networks, but found it slightly decreasing the performance, potentially due to different domains generally using distinct semantic features for their classification tasks.
E ADDITIONAL. EXPERIMENTS AND RESULTS
In this section, we provide additional experimental results and visualization.
E. EMPIRICAL ROBUSTNESS STUDY UNDER CROSS- AND IN-DOMAIN NOISE
In this section, we empirically evaluate the robustness LEAF against both the cross- and the in-domain noise.
Cruss-domain noise. We consider the same setting as in our theoretical analysis in Sec. C33 where
introduce mixing ratio parameter E [0, 1) that controls the expected percentage of noisy
30

---

Under review as a conference paper at ICLR 2023
Table 3: Results of LEAF under different levels of cross-domain noise. We report the mean prediction errors and standard deviations on Gender, Category, and Color domains of Fashion Product Images over three independent trials.
LEAF-EM
LEAF
Mixing ratio
Error (%)
Error (%)
Gender
Category
Color
Gender
Category
Color
0 (clean)
26.67
+0.82
18.7040.92
2.27
1.93
12.85+0.67
Q 1%
27.13
6.1540.94
19.20
7.91 20.40
1.95
12.97
2%
27. 27.42
6.2341.42
20.1043.20
7.94
2.08
13.22+1.20
a = 5%
28. 2.
7.54
25.79+3.70
8.14=1.12
2.18+1.17
13.44+1..0
10%
29.30 13.80
6.64
24.60
8.17 11.7
2.37
13.35 12.30
20%
29.1216.60
8.77
35.73
8.30
2.22
13.33
Table Results of LEAF under different levels of in-domain noise. We report the mean prediction errors and standard deviations on Gender, Category, and Color domains of Fashion Product Images over three independent trials.
Error (%) Category
Noise ratio
Gender
Color
B (clean)
7.87
1.93
12.85_0.67
8 1%
2.35
2.01 20.45
12.98
3 2%
12.28
10.56
14.00=1.04
3 = 5%
22.36+3.87 3.88
19.72=1.16
27.70=3.75
examples: for each data pair in the i-th (i [n]) batch, with probability 1 - a it is drawn from the sampled domain d' (Pi, c²), and with probability it is drawn from other domains in the domain set, i.e., D \\ {d'}. ). As the mixing ratio increases, the data becomes more and more "noisy" with examples from other domains. We evaluate the robustness of LEAF well as the LEAF-EM variant on the paralleled relation setting on the Fashion Product Images dataset with different levels of noise: 0, 1%, 2%, 5%, 10,, 20%, where a O corresponds to the standard setting without cross-domain noise. As shown in Table 3 LEAF is robust against the cross-domaie noise: as the mixing ratio increases from 0 20%, the test prediction errors of LEAF only increases marginally. Also, LEAF is more robust to cross-domain noise than the LEAF-EM variant with generally smaller standard deviations of the prediction errors.
In-domain noise. We consider the setting where for each domain, every example may be randomly assigned a false label, but this false label still belongs the label set of the domain. For instance, image labeled as "red" in the "color" domain may be mis-labeled as another color, e.g., "yellow".. We introduce a noise ratio parameter cross-domain noise setting, we evaluate the robustness of LEAF on the paralleled relation setting on the Fashion Product Images dataset with different levels of noise: 8 = 1%. 2%, 5%, where corresponds to the standard setting without in-oomain noise. As shown in Table LEAF generally exhibits some performance degradation under the in-domain label noise, similar phenomenon to the standard single-domain setting with supervised learning models; note that we do not use any additional strategy to improve the robustness of our model against the label noise, and a better result can be expected if we further adopt robust learning techniques in the literature top of LEAF.
[0, 1) that controls the probability of this label noise. Like the
E.2 MULTI-DIMENSIONAL REGRESSION ON REAL-WORLD DATA
To further demonstrate the efficacy of LEAF in regression problems, we conducted an experiment on real-world multi-dimensional regression dataset from UCI machine learning repository: Gas sensor array under dynamic gas mixtures dataset (Fonollosa et al,, 2015). This dataset contains the recordings of 16 chemical sensors exposed to two different dynamic gas mixtures and the aim is to
31

---

Under review as a conference paper at ICLR 2023
Table 5: Results of LEAF on multi-dimensional regression task on gas sensor array under dynamic gas mixtures dataset. We report RMSE on each domain and the macro-average RMSE over both domains.
Methods
RMSE (domain Methane)
RMSE (domain CO)
RMSE (macro-average)
ERM
76.5
89.7
83.1
LEAF
34.0
72.6
53.3
Oracle
31.9
66.8
49.4
predict the concentrations of gases, with 417,8504 instances and 16-dimensional attributes. We treat each gas mixture as one domain, representing Ethylene & Methane (domain Methane) and Ethylene & CO (domain CO) gas mixtures, and randomly split both domains into training (90%) and test sets (10%). Since this is large dataset, we consider more examples in each batch and set the sampling paramters of LEAF to n = 50. We use a model set consisting of two neural network regressors for LEAF, and use the Adam optimizer for training.
In this task, we compare LEAF with vanilla single model regressor (trained by ERM on the union of both domains) and an oracle regressor with two models separately trained by ERM on each domain. We report root mean square error (RMSE) on each domain and the macro-average RMSE over both domains in Table 5 The results indicate that LEAF benefits from its automatic data allocation process, surpassing the ERM baseline that only trains a single global model by a large margin and performing competitively with the oracle.
E.3 ABLATION STUDY ON THE IMPACT OF THE NUMBER OF LOW-LEVEL MODELS AND SAMPLING PARAMETERS
In this section, we empirically study the impact of the number of low-level models and sampling parameters on the performance of LEAF, and discuss some heuristies for determining the number of low-level models in practice.
We begin by evaluating the performance of LEAF with different number of low-level models
(K = 2, 3. 4 with K = 3 as the default) and sampling parameters (m = 50, n = 2; m 250, n = 1 and m = 250, n with m = 250, n as the default) on the regression task considered in our
experiment (Figure D}. As shown in Figure 6 LEAF with K > R(D) (K =
4) successfully
distinguishes different functions and recover each of them accurately, while LEAF with K < R(D)
(K 2) fails, which matches the result of Theorem 2 In particular, LEAF with K = 4 automatically leaves one network to be redundant (dashed curve in Figure 6f). demonstrating the robustness on the number of low-level models of our framework. Meanwhile, LEAF with fewer batches = 50 (b)) roughly recovers all three functions but does not yield accurate predictions in fine-grained details; this corresponds to the instance-wise estimation error term (8b) in the generalization error due to that the product mn being not sufficiently large. On the other hand, LEAF with batch size n = 1 (Figure 6c) produces smooth predictions in the details, yet partially swaps some parts of different functions; this corresponds to the allocation estimation term (8c) in the generalization error due to that n being not sufficiently large for identifying the domains.
We then empirically study the effect of additional low-level models on LEAF in the classification tasks. Concretely, for each dataset in the paralleled relation and the hierarchical relation settings, we employ model set with the model number larger than the number of domains by one. We empirically observe that with an additional model, LEAF can still learn accurate predictions for each domain using subset of the model set, with results shown in Table 6 The additional model may be simply "abandoned" as in the regression task, or becomes nearly identical to one of the other models. This naturally raises the question of how to determine the number of low-level models in LEAF when we have no prior knowledge on the number of conflicing domains in the training data. Here we discuss some heuristics for this problem. In summary, there are two lines of methods that can be useful:
As shown by Theorem 2 a necessary condition of the PAC-Icarnailiity of LEAF is K 2 R(D); in other words, the number of low-level models must be sufficiently large to possibly
32

---

Under review as a conference paper at ICLR 2023
0
0
0
-1
-1
-1
-2
-2
-2
NIEE 1,00
KISP: BASH
-2
D
-2
(a) Ground truth
(b) LEAF with fewer batches
(c)
LEAF with smaller batch size
(m = 50)
(n
1)
8
8/
2
0
-2
(d) LEAF with two low-level models (K- =
(c) LEAF with three low-level
(f) LEAF with four low-level
models (K 3)
models (K =
Figure 6: The impact of sampling parameters and the number of low-level models on LEAF in the regression task.
Table Results LEAF with an additional model (referred as "LEAF-AM" in the table) on the classification tasks with paralleled and hierarchical input-output relations. We report prediction errors on Digit and Color domains Colored MNIST, Gender, Category and Color domains of Fashion Product Images, and Superclass and Class domains of CIFAR-100.
Colored MNIST
Fashion Product Images
CIFAR-100
Methods
Error (%)
Error (%)
Error (%)
Digit
Color
Gender
Category
Color
Superclass
Class
LEAF
1.70
0.03
7.87
1.93
12.85
21.40
25.05
LEAF-AM
2.25
0.17
7.91
1.82
13.15
23.52
24.81
achieve zero training error even in the realizable case. Therefore, we can progressively increase the number of low-level models and choose the minimal number that elicits low training error. This is analogous to using Akaike Information Criterion (AIC) or Bayesian Information Criterion (BIC) metrics (Claeskens al. 20088) that both can be viewed as balancing the training erгоr and the number of total parameters (which is directly proportional to the number of low-level models) of the whole model.
As shown by Theorem T if the number of models is strictly larger than the conflict rank of the domain set, then there must exists a subset the model set that separately captures the target functions in all domains. Therefore, model set by tracking the calling frequency of each model during training and removing the ones that the models (after the models are sufficiently trained) and removing the models with identical outputs other models for sufficient number of examples.
filter out the redundant models in the
seldom called, by checking the redudancy between the outputs of
E.4 WALL-CLOCK TRAINING AND INFERENCE TIME ON THE FASHION PRODUCT IMAGES DATASET
In Table 7 we compare the computational cost of LEAF and other baselines in terms of training and inference time the Fashion Product Images dataset. We measure the required wall-clock time (in seconds) for each method to reach convergence during training as well as the averaged wall-clock time for each method predict all labels of one given input (in milliseconds). Concretely, for LEAF
33

---

Under review as a conference paper at ICLR 2023
Table 7: Wall-clock training and inference time of LEAF and baselines on the Fashion Product Images dataset. The training time of ERM-top k, PseoduLabeel LabelProp, Sparse MoE, LEAF-EM and LEAF measured over 50 epochs, and the training time of MLL oracle and MTL oracle is measured over 10 epochs. The inference time of all methods is measured using an average over 3,000 test examples.
Methods
Training time (in seconds)
Inference time (in milliseconds)
ERM-top &
415
0.67
PseudoLabel
833
2.00
LabelProp
915
0.59
Sparse MoE
886
0.84
LEAF-EM
672
0.81
LEAF
580
0.79
MLL oracle
159
0.68
MTL oracle
93
0.76
and all baselines except for two oracles (MLL oracle and MTL oracle), we train the models for 50 epochs with 15,000 images in every epoch; for MLL oracle and MTL oracle, we train for 10 epochs since these methods generally converge faster. For each method, we test its total inference time on the same 3,000 test examples randomly sampled from the test set and report the mean inference time on each test example. All results are obtained with PyTorch using a NVIDIA 2080ti GPU.
As shown in the table, the time cost of LEAF is generally par with or lower than baselines that also involve iterative training (Pseudol.aby and LabelProp). Although the ERMM-topk baseline trains faster, it learns global model without the mechanism of data allocation and thus performs considerably worse than LEAF, as we have shown in earlier sections. Meanwhile, compared with the MTL oracle that knows the example-domain correspondences in advance, LEAF only exhibits little additional computational overhead (note that the training time of LEAF is measured over 50 epochs, while that of MTL oracle is measured over only 10 epochs). This indicates that although LEAF incorporates an extra data allocation process implemented by the allocation function, this process only induces a limited computational cost since it only requires additional network forward processes without loss backpropagation, which is in general computational efficient.
E.5 ADDITIONAL VISUALIZATION
In this section, we provide additional visualization on the iteration process and the low-level feature spaces learned by LEAF.
E.5.1 ITERATION PROCESS ON THE REGRESSION TASK
In LEAF, since the performance of the low-level models will impact the data allocation process of the high-level allocation function, the training of the allocation function and low-level networks is highly relevant. As shown by Figure 7 we provide illustrative example in regression, in which the different colored lines refers to the allocations to different models. All networks are randomly initialized, and in each iteration, each sample may be reallocated by the allocation function and used to further train the low-level networks. With the increase of iterations, both the high-level data allocation strategy and the low-level predictions will converge with the minimization of the global training error. The last subfigure displays the final decision boundary of allocation function and indicates that all data points have been correctly allocated.
E.5.2 FEATURE VISUALIZATION ON THE CLASSIFICATION TASK
LEAF can extract different semantics from the same input and map them to different feature spaces by different low-level models. Figure g displays the features output by all low-level models learned by LEAF, where each color represents a low-level model and each point in the figure corresponds to an input image in the Fashion Product Images dataset. As shown in the figure, different low-level models learn metrics based on different semanties of the inputs.
34

---

Under review as a conference paper at ICLR 2023
Epoch 0
bpooc 20
Epoch
Epoch 60
87
0
0
11
-1
-1
2
11
0
-2
-1
-2
-2
0
2
Figure 7: An example of the iteration process and the final decision boundaries of the allocation function in the regression task.
Calagory
Gender
Color
Figure 8: Additional visualization of different low-level feature spaces of LEAF on the Fashion
Product Images dataset.
F MORE DISCUSSION ON RELATED WORK
In this section, we provide more discussion related work.
Ensemble learning. Ensemble learning approaches typically employ multiple models to coopera- tively solve given task (Dietterich) 2002 | /Zhang Ma 2002 (Sai Rokach, 2018 Zhou (02T). The prediction of each model is combined by weighting (boosting), majority voting (bagging) learning a second-level meta-learner (stacking). Since different models process the same set of data (although sometimes with different instance weights), there is typically explicit "hard" allocation process in ensemble learning between the examples and the models. In contrast, the multi-mode architecture of LEAF is driven by the inherent conflict the conflicting training data, and each model only handles a proportion of the whole dataset without overlapping.
Domain adaptation (Ben-Davie et al.) 220 Pan & Yang. 2010 Tan al. 2018 Wang Deng 2018 Hoffman et al., 2018) and domain generalization (Blanchard et al. 2011 Muandet et al. 2013 Zhou et al. (002)) consider the scenario where the learner trained on one or multpple source domain(s) transferred one or multiple new target dsmain(s). Typically, domain adaptation focuses on the problem where there exist some labeled or unlabeled instances in the new domain, while domain generalization considers the setting where there the information of the new domains is inaccessible during training (i.e., zero-shot generalization). other words, these formulations focus on the adaptation or generalization capability the model on the target domain(s) and do not consider training on the sources domains itself to be issue. By contrast, LEAF focuses on the multi-domain training process and considers the scenario where directly training global model by ERM using the data from multiple conflicting domains is problematic, and aims to resolve this training issue by performing automatic data allocation. In other words, the data setup between work and unsupervised domain adaptation is fundamentally different: common
Domain adaptation and domain generalization.
35

---

Under review as a conference paper at ICLR 2023
assumption adopted by most of unsupervised domain adaptation is covariate shift assumption (Ben David et al. 2010b), i.e. the input- conditoond label distribution p(y x) is the same for all domains while the input marginal distribution p(x) varies. By contrast, we define conflicting domains as the target function from different domains give distinct outputs for the same set of inputs, which stands for varying p(y x). Therefore, the setup of unsupervised domain adaptation and our work are orthogonal. We also note that from theoretical view, existing domain adaptation methods are provably infeasible in our problem since their success requires the existence of model with low error simultanesouly on all domains (see e.g., Mansour et al. (2009) (Bnn-Davic et al. (2010b)), which is not true if varies lot across different domains. Finally, the example-domen domain correspondences are usually available in domain adaptation and domain generalization settings, while LEAF weakens this assumption by only assuming that the examples in each batch are obtained from the same domain.
Latent variable modeling. Latent variable modeling (Skrondal & Rabe-Hesketh 2004 Muthén 1989 2002) is a general approach that models the relation between observed variables with unob- served, latent variables. In broad sense, LEAF falls into the category of latent variable modeling by treating the domain of each data pair as a (discrete) latent variable. Nevertheless, the notion of latent variable modeling itself is rather general, and distinct methods may be developed based on the specific problem setup. To the best of our knowledge, the problem of learning from conflicting data has not been formalized or addressed by prior latent variable modeling methods. Meanwhile, several key design choice (using Viterbi EM rather than standard EM) and data assumption (n > 1) of LEAF is tailored to our problem setup, thus differing LEAF from general latent variable modeling approaches. See the next section for more detailed discussion.
G NECESSITY OF USING BATCHES OF DATA (n > 1) RATHER THAN SINGLE DATA PAIRS (n = 1) FOR CONFLICTING DOMAIN IDENTIFICATION
In this section, we discuss the necessity of the assumption that we observe a size-n batch rather than single data pairs (n 1). which is often considered by general latent variable modeling methods without further structural assumptions on data. To summarize, n = 1 poses fundamental difficulty in identifying conflicting domains and, in the worst case, n = 1 makes identification of conflicting domains impossible. We will first construct two examples, one for regression and one for classification, to illustrate this impossibility:
Consider a regression problem with two domains, namely di and d2, where training (x,yy
pairs are uniformly sampled from y1 xr [0, 1] in di and y/2 - xr 30 [0, 1] in da.
respectively. Then, in the n = 1 setting, both of the following two solutions achieve zero training error:
S1: (1 = I, I E [0, 1]
and h2(x) = 1 - x, x E [0, 1];
Nr x E [0, 0.5)
and ha(x) 1 - x. a E (0,0.5)
S2: h1(2) 1 11-2, x E [0.5. 1]
x [0.5. 1]
However, only S1 is the desired solution that separately recovers y11 by h1(2)) and recovers y2 by h2(2z), while S2 does not recover either y1 or y/ by any of the model. However, S1 and S2 are not identifiable when can also see that when n > would effectively present the undesired solution S2, since we may sample two points (x², and (x²2, y²) from the same domain with x² E [0, 0.5) and x² E [0.5, 1] in the same batch, so that S2 does not achieves zero training error anymore. In fact, we did observe such cases in our regression experiments (see Figure bc in Appendix E.3 where n = 1 leads to incorrect identification of domains.
1 since both of them are optimal during training. We
Consider a classification problem that follows the CIFAR-10 100 setup in our experiments, where each x corresponds to the input image and corresponds to the label. There are two domains, di and d2, where images in dj are labeled by superclass names, while images in d2 are labeled by class names. As illustrative example, we consider di with labels "fish" and "flowers" and d2 with labels "shark", "flatfish",, "roses" and "sunflowers". with the first two labels belonging to "fish" and the last two labels belonging to "shark". Both d1 and de contains input images that belong to "shark", "flatfish", "roses" " and "sunflowers" " with the same distribution. Then, in the n = I setting, both of the following two solutions achieve
36

---

Under review as a conference paper at ICLR 2023
Table 8: Comparisons between LEAF, LEAF-EM and EM (n 1) on CIFAR-100. We report
prediction errors Superclass and Class domains.
CIFAR-100
Methods
Error (%)
Superelass
Class
LEAF LEAF-EM
21.40
25,05
32.71
33.83
EM (n = 1), 1st run
61.71
52.46
EM (n 1), 2nd run
67.43
55.20
EM (n = 1), 3rd run
71.33
48.79
zero training emro. S1: model h1 classifies all images by their superclass labels, while model h2 classifies all images by their class labels. S2: model hı classifies fish images according their superclass labels and classifies flower images by their class labels, while model h2 classifies fish images by their class labels and classifies flower images by their superclass labels. In other words, S1 recovers the target function in both domains, while S2 fails to recover any target function since the outputs of both models h1, hg in S2 are mixtures of superclass labels and class labels. Similar to the regression case, from being an optimal training solution since superclass labels "fish" and "flowers" can be sampled in the same batch and thus should predicted by the same model.
can prevent S2
Besides the concrete failure cases provide above, our theoretical result on the generalization error bound of LEAF also sheds light on the failure of the = case:to bound the generalization error between empirical and expected allocation functions (Eq. (8ch Theorem 3 we generally require sufficiently large n. Therefore, n = 1 may create a non-new non-negligibl gap between empirical (training) error and expected error. Since our Theorem ! suggests an equivalence between domain identification and reaching small expected error, having a gap between empirical and expected errors can pose difficulty in domain identification.
Finally, we run extra experiments to illustrate this failure of n = 1 on CIFAR-100: we added new baseline denoted by EM (n 1) that (1) uses standard EM and (2) eliminates the information about which datapoints come from the same batch. We evaluated its performance on the CIFAR- 100 dataset (with two low-level models), following the same setup as in our main experiments in the main text. However, this baseline cannot converge stable solution, and we found its performance have large fluctuations across different runs and generally much worse than both LEAF and LEAF-EM. This validates the counterexample the identifiability issue in the case in the above. Detailed results are in Table g
37


Reviews:
[{"review_id": "vTCsCFZFNM8", "reviewer": "Reviewer_eW7y", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authros proposed the method that can deal with conflicting contexts scenario. Authors proposed a LEAF architecture for solving the problem. Authors also showed the effectiveness of the proposed method using toy and real-world datasets. Also, they offer the theoretical bounds for their method.", "summary_of_the_review": "I think the draft contains the solid method for solving unique aspect of the supervised learning task. The problem looks important and the proposed method looks also sound. Experimental and theoretical analyses are also thorough. I recommend accept for this draft.", "strength_and_weaknesses": "- I think the problem of conflicing contexts seems novel and important for solving the real-world problems.\n- The examples for context-conflicting cases are well exampled.\n- The LEAF method looks sound and novel enough.\n- Experimental results are impressive, showing superior performance to several competitive baselines (ie. meta-learning, MoE, etc)\n- Theoretical bounds also look sound.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hnI-CtXEs5", "reviewer": "Reviewer_4gxX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method for learning from data following a mixture of distributions whose input-output relationships are different. The proposed method maintains multiple hypothesis functions accounting for those different distributions and minimizes the loss between the label and the closest output among those given by the hypothesis functions. The authors explain a connection between the proposed method and the EM algorithm. They also show an identifiability result and a generalization error bound between the proposed training objective and an oracle risk. The experiments show the superiority of the proposed method against other methods that are not designed for this setup.", "summary_of_the_review": "I like the direction of the work, but I think the quality of the paper should be improved before being published. There are many major issues as I mentioned in the weakness section. I suggest rejecting the paper.", "strength_and_weaknesses": "# Strengths\n- The paper seems to tackle an important and interesting problem.\n- The method performs excellently according to the experiments.\n\n# Weaknesses\n- The problem setup is not very clear. In particular, the evaluation metric, or the test error, is not clearly defined, and the paper does not explain what information is given to the model in prediction.\n- It does not seem easy to choose $K$. The authors mention some connection to $R(D)$, but how do we estimate this number?\n- In Eq. (3), the method allows $\\hat{g}$ to look at $y^{ij}$, which feels strange to me because we don't have access to it in the test phase.\n- There is no guarantee that the proposed training minimizes the \n- Knowing each set of $m$ samples comes from one distribution seems to be a strong assumption. The theory requires $m$ tends to infinity to ensure the convergence of $\\hat{\\operatorname{err}}(H)$ to $\\operatorname{err}(H)$. The paper briefly mentions this point, but the argument is not very convincing to me.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NL0D6ZGc9n", "reviewer": "Reviewer_yevj", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper first formally defines a new and practically important problem setting where data are generated from multiple domains and the generation process is completely hidden. It then propose a concrete EM-based algorithm with reasonable theoretical guarantees. Empirical evaluations are conducted on various tasks and high quality python code is provided.\n", "summary_of_the_review": "I recommend to accept the paper considerting the overall contribution of problem setting, algorithm, theoretical analysis and empirical evaluation.\n", "strength_and_weaknesses": "Strength\n- This paper considers the new problem setting of learning from hiddenly conflicting data, and proposes a reasonable rigorous definition based on domain generalization.\n- It then proposes a pratical EM-based algorithm for the new problem, and analyzed its learnability and generalization ability compared with existing general supervised learning case.\n- Empirical evaluation is carefully conducted and experiment python files are provided with detailed README.\n\nWeakness\n- As the proposed algorithm is based EM, it is nice to have dicussions on its convergence conditions.\n- Hidden conflicts defined in this paper resembles graphical models with a latent variable, although graphical models cast stronger assumptions on the data generation process. Some dicussion on this topic is desired.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3_46Me3Iikb", "reviewer": "Reviewer_zrsD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers supervised learning in the setting where the data is drawn in a 2 stage process: first, a domain is selected, second, a batch of data is drawn from this domain. The observations include the batch index, but not the underlying domain the data was collected from. The learning problem considered here is to find 1. a predictor that is optional for each domain, and 2. a rule for assigning a batch to a domain. The paper proposes a straightforward method for doing this.", "summary_of_the_review": "Although I think the data setup is interesting and potentially fruitful, I don't think the results of the paper in its current form really communicate this. Minimally, the paper would require making it precisely clear how the batch size > 1 case helps vs simple latent variable modeling.  ", "strength_and_weaknesses": "For context, it may help to consider two closely related cases:\n1. (latent variable modeling) We know that each data point is drawn according a hierarchical scheme that first draws a distribution, then draws the data point from this distribution. In this case, the obvious thing to do would be to set up learning via a latent variable model. This corresponds to the case where batch_size=1 in the present paper.\n2. (unsupervised adaptation) We observe batches drawn from a number of domains, but we don't know a priori the relationship between domains. In particular, we don't know that there are only K distinct kinds of possible relationship. Then, the natural approach is to build a model that, given a new set of inputs, self-modifies to improve predictions on these inputs; see https://arxiv.org/abs/2102.12206 for an example of this kind of approach, and https://arxiv.org/abs/2112.05090 for a benchmark of such methods. In the present paper, this is done by guessing which of the K classifiers should be used for the test batch.\n\nWith this context, the main strength of the paper is that the particular setting it considers---data is observed as batches, and we know each batch is from a fixed domain---seems to add in extra structural assumptions in a manner that is realistic for some applications, and which may allow for better methods or analysis. The particular approach they take here (use EM to alternate assigning batches to classifiers and updating the classifiers according to batch assignment) is straightforward and reasonable.\n\nHowever, in this view, the main weakness of the paper is that doesn't really focus on what's interesting about their data setup. Specifically, the natural baselines for comparison are 1 (latent variable modeling) and 2 (unsupervised domain adaptation). But it seems to me that the discussion, theory, and experiments all comparatively neglect these comparitor cases. That makes it both hard to assess the importance of the method, and hard to know what the important conceptual takeaways of the paper are. Generally, I think the paper needs to be substantially reworked to make all this clear.\n\nAs particular instances,\n1. How does knowing that some pairs share the same domain help with identification (relative to straight latent variable modelling)? \n2. How does the assumption that that there are only K domains help relative to general unsupervised domain adaptation? E.g., in terms of the PAC rate and in terms of empirical performance\n\nSome further issues I see:\n1. Theorems 1 and 2 seem trivial. \n\n2. It's actually not obvious that ERM should fail in this data setup. The optimal classifier is P(Y| x) = \\sum_k p(k | x) P(Y | k, x), where k denotes the underlying domain. If p(k|x) is learnable from the data, then a suitable ERM procedure should succeed. The claim here is presumably something like p(k|x) is not learnable given only single sample batches, but is learnable using multi sample batches. But, if that is the claim, I'm not able to find it spelled out clearly anywhere in the paper.\n\n3. In the experiments, it's not clear to me what \"ERM\" means. In particular, is the capacity of the ERM model the same as the LEAF model? A fair comparison would be to run the EM algorithm, but eliminate the information about which datapoints come from the same batch---is that what you're doing? If so, it wasn't clear to me\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject