Subjective Learning for Open-Ended Data
Authors: Tianren Zhang
Yizhou Jiang
Xin Su
Shangqi Guo
Feng Chen
Venue: ICLR 2022 Submitted (2022)
Keywords: Open-ended data
machine learning
supervised learning
data conflict

Abstract: Conventional supervised learning typically assumes that the learning task can be solved by learning a single function since the data is sampled from a fixed distribution. However, this assumption is invalid in open-ended environments where no task-level data partitioning is available. In this paper, we present a novel supervised learning framework of learning from open-ended data, which is modeled as data implicitly sampled from multiple domains with the data in each domain obeying a domain-specific target function. Since different domains may possess distinct target functions, open-ended data inherently requires multiple functions to capture all its input-output relations, rendering training a single global model problematic. To address this issue, we devise an Open-ended Supervised Learning (OSL) framework, of which the key component is a subjective function that allocates the data among multiple candidate models to resolve the "conflict'' between the data from different domains, exhibiting a natural hierarchy. We theoretically analyze the learnability and the generalization error of OSL, and empirically validate its efficacy in both open-ended regression and classification tasks.

Under review as a conference paper at ICLR 2022
SUBJECTIVE LEARNING FOR OPEN-ENDED DATA
Anonymous authors
Paper under double-blind review
ABSTRACT
Conventional supervised learning typically assumes that the learning task can be solved by learning a single function since the data is sampled from a fixed dis- tribution. However, this assumption is invalid in open-ended environments where no task-level data partitioning is available. In this paper, we present a novel su- pervised learning framework of learning from open-ended data, which is modeled as data implicitly sampled from multiple domains with the data in each domain obeying a domain-specific target function. Since different domains may possess distinct target functions, open-ended data inherently requires multiple functions to capture all its input-output relations, rendering training a single global model problematic. To address this issue, we devise an Open-ended Supervised Learning (OSL) framework, of which the key component is subjective function that allo- cates the data among multiple candidate models to resolve the "conflict" between the data from different domains, exhibiting a natural hierarchy. We theoretically analyze the learnability and the generalization error of OSL, and empirically vali- date its efficacy in both open-ended regression and classification tasks.
INTRODUCTION
A hallmark of general intelligence is the ability of handling open-ended environments, which roughly means complex, diverse environments with no manual task specification (Adams et al.] 2012 Clunel 2019: Colas et al.) 2019 Wang et al. 2020). Conventional supervised learning typ- ically assumes that the learning task can be solved by approximating a single ground-truth target function (Vapnik, 2013). However, this assumption is invalid in open-ended environments where the data may implicitly belong to multiple, disparate domains with potentially different target functions since manual leskl data partitioning is available. For instance, when collecting image-label pairs from the Internet, an image of red sphere can correlate with the label of both "red" and "sphere", implicitly representing two distinct domains or "metaconcepts" (Han et al. 2019): "color" and "shape". While being generic, this setting also characterizes many practical scenarios where the data comes from multiple sources, contexts or groups: for example, in federated learning the data is distributed on multiple clients, and in algorithmic fairness research the data is from different pop- ulations. In these scenarios, the input-conditional label distribution may vary in different domains (also referred to as concept shift (Kairouz et al., (021)) due to personal preferences or other latent factors, corresponding to different target functions.
Since different domains may possess different target functions, training single global model by running Empirical Risk Minimization (ERM) using all data is problematic due to the potential "con- flict" between the data from different domains: in the "red sphere" example above, directly training on all data will lead to the unfavorable result of "50% red, 50% sphere". Similar phenomena have also been observed by prior works (Finn al. 2019 Su et al. 2020), where a learner simultancously regressing from multiple target functions trivially outputs their mean. This indicates that the data sampled from open-ended environments, which we refer to as open-ended data, exhibits structural difference from conventional supervised data. Formally, we introduce a novel, dataset-level measure named mapping rank, which represents the minimal number of functions required to "fully express" all input-output relations in the data and can be used to expound such difference more clearly.
Definition 1 (Mapping rank). Let X be input space, y an output space, and Z = {(Ix, 1:)) a dataset with cardinality I. Let F(r) = {ft) be a function set with cardinality r. where each element is vingle-valued deterministic funtiiin from X to Y. Then, the mapping rank of Z, denoted

---

Under review as a conference paper at ICLR 2022
by R: R(Z), is defined as the minimal positive integer r, satisfying that there exists a function set (r) such that for every (z. y) E Z. there exists f E F(r) with f(z) = y.
Note that here we assume that there exist deterministic relations between inputs and outputs in the same domain, which is generally a mild assumption and is satisfied in many practical applications. Under Definition [] conventional supervised data yields a mapping rank R as it assumes that the whole dataset can be expressed by single function. In contrast, open-ended data has a mapping rank R since for the same input different outputs exist, manifested as the conflict between data samples that renders training a single model problematic. Hence, it is natural to consider allocating the data to multiple models, that the data processed by each model has mapping rank R and thus can be handled with ERM. Although in some scenarios, apart from data samples there also exists indeiinformation or metadata that can be exploited to identify the domains, this information may be difficult to define or collect in practice (Hanna et al. 2020; Creager et al.) [021); even when such side-information is available, in many cases it still remains unclear how to leverage such information to detect and resolve the potential conflict between domains. Therefore, the problem of how to properly allocate open-ended data among the models is highly non-trivial.
To tackle the aforementioned challenge, we present an Open-ended Supervised Learning (OSL.) framework to enable effective learning from open-ended data. Concretely, OSL maintains a set of low-level models and high-level subjective function that automatically allocates the data among these models so that the data processed by each model exhibits no conflict. The term "subjective" is used since in conventional supervised learning such allocation is manually performed during the data collecting process and thus conforms to human subjectivity. The motivation of such process is that if the subjective function yields an inappropriate allocation, i.e., assigning conficcing data samples to the same model, then it will hinder the global minimization of the training error due to the conflict, which in turn drives the subjective function to alter its allocation strategy. Using a probablistic reformulation of OSL, we establish the connection between the data allocation and the posterior maximization using a variant of Expectation Maxiiiiiii-aaiiiiiiiiin (EM) algorithm (Dempster et al. 1977), and show that the optimal form of the subjective function can be explicitly derived.
Theoretically, we respectively analyse the Probably Approximately Correct (PAC) learnabil- ity [Valiant 1984) and the generalization error of OSL. Using the tools from statistical learning theory (Vapnik] (013), we show that the relation between the number of low-level models and the mapping rank of data plays key role in the learnability of OSL., and the generalization error of OSL can be decomposed into terms that respectively reflect high-level data allocation and low- level prediction errors. Empirically, ended regression and classification tasks to verify the efficacy of OSL. Our results show that OSL. can effectively allocate and learn from open-ended data without additional human intervention. In summary, our contributions are three-fold:
conduct extensive experiments including simulated open-
Open-ended data and mapping rank. We formalize a new problem of learning from open-ended data, and introduce a novel measure termed as mapping rank to outline the structural difference between open-ended data and conventional supervised data.
OSL framework with theoretical guarantee. We present an OSL framework to enable effective learning from open-ended data (Section 2). and theoretically justify its learnability (Section 3.1 and generalizability (Section 3 respectively.
Empirical validation of efficacy. We conduct extensive experiments on both open-ended regression and classification tasks. Experimental results validate our theoretical claims and demonstrate the efficacy of OSL (Section 4p.
2 OPEN-ENDED SUPERVISED LEARNING
In this section, we present the overall formulation and the algorithm of OSL. We adhere to the
conventional terminology in supervised learning, and let X' be an input space, y an output space, H a hypothesis space where each hypothesis (model) is a function from X' to )/ and f: : x y + [0. a non-negative and bounded loss function without loss of generality. We use [k] for positive integers k, and denote by 1 (-) the indicator function. We use superscripts to denote sampling indices (e.g., d' and x²2) and subscripts as element indices (d))
f1,
2

---

Under review as a conference paper at ICLR 2022
2.1 PROBLEM STATEMENT
We begin by introducing the notion of domain to formulate the generation process of open-ended data. Inspired by Devi- et al. (2010), we define domain d as pair (P, e) consisting of distribution on X and a deterministic target function e: X + y, and assume that the open-ended data is generated by a domain sel D = {d:) = {(Pi cz) J containing N (agnostic to the learner) domains. Each domain has its own sub-dataset Z, ((raj Viy)) with cardinality 4, where Tal, Fet are i.i.d. drawn from P. and Vij 02 (2(2tt) The whole dataset is the union of these sub-datasets: Z = - Zj with cardinality 1 = Σi= then consider a bilevel sampling procedure: first, m domain samples d',... , d are i.i.d. drawn from distribution Q defined on D (the same domain may be sampled multiple times), resulting in m sampling episodes; second, in each sampling episode n data samples are iidd drawn from the sub-dataset corresponding the sampled domain. Hence, the dataset or any sub-datasets may be sampled multiple times during training. This sampling regime is analagous to the bilevel sampling process adopted by meta-learning. However, meta-learning usually assumes dense distribution of related domains to enable task-level generalization (Pentina & Lampert 2014 Amit & Meir 2018), while OSL is compatible with scarce and disparate domains and inter-domain transfer is orthogonal.
i=1 4 and mapping rank 1 < R S N. We
As we have mentioned in Section a single model is not sufficient in this setting when R >>>>> 1. Thus, we equip the learner with a hypothesis set H { consisting of K > 1 hypotheses, enhancing its expressive capability. Although both N and K are assumed to be unknown, we will show that in general K 2 suffices (Section (.1]. which eases the difficulty of setting the hyperparameter K.
In the above setting, an episodic sample number parameter n is introduced to maintain the local consistency of data, implicitly assuming that we are able to sample a size-n data batch at time from each domain. While this formulation subsumes the fully online case of 1, we note that although sometimes setting n = works in practice, it also tends to be risky since it may raise difficulties in controlling the generalization error, as we will both theoretically and empirically demonstrate in the following sections (see Section 3.2 and Section 4.3)
2.2 GLOBAL ERROR
In this section, we present the global learning objective of OSL. Since the open-ended dataset im- plicitly contains multiple underlying input-output mapping relations, primary start point can be the empirical multi-task loss with pre-defined data-domain correspondences:
m
êrMTL(H)
l (hORACLE(E) (z"), ,88).
(1)
m
where ORACLE [m] [K] is an oracle mapping function that determines which hypothesis
each data batch Zt = (( ) in episode is assigned to. However, in OSL the oracle mapping function is unavailable, imposing a fundamental discrepancy. To tackle this difficulty, here we substitute the oracle mapping function with a learnable empirical subjective function I : H. x X" x y + H that aims to select a hypothesis h from the hypothesis set H for the data batch Zt. This substitution yields the empirical global error of OSL:
m (
(H)
e0
(2)
Our insight is that the data batch itself can be harnessed to guide its suitable allocation in the pres- ence of mapping conflict: intuitively, single model trained by conflicting data batches result in an inevitable training error, thus hindering the minimization of the global error. This in turn facilitates data allocation with less conflict. Given the empirical error 2 the corresponding expected global error is
er (H := EEdraBEuPP ((x),
where g HK x D + H is expected subjective function, which can be viewed as the empirical subjective function with infinite samples from every single domain so that all available domain information can be fully reflected by the data samples. The global objective B characterizes the scenario where the leamerr interacts with only one domain in a particular time period (which is natural in the real world), therefore its performance can be separately tested in all domains.
3

---

Under review as a conference paper at ICLR 2022
So far, framework remains incomplete since the subjective function remain undefined. In the next section, we will present our design of the subjective function and elucidate its rationale.
2.3 DERIVATION OF SUBJECTIVE FUNCTION
To attain reasonable choice of the subjective function, in this section provide alternative, probabilistic view OSL from the angle maximum conditional likelihood, and draw an intriguing connection between the choice of the subjective function and the posterior maximization using variant of the EM algorithm (Dempster et al. 1977) on open-ended data. Concretely, let p(Y X) represents the predictive conditional distribution of the hypothesis set H, where we use X and as the shorthand for (a ,,!? x _ ) and (y . ....... yy respectively. We consider maximiz- .y
ing the empirical log- likelihood pog X) -E Ej=1 log Ex=1P(y" ,h- h& (x4) using EM, where h denotes the selected hypothesis. Accordingly, in the i-th sampling episode, in the E-step we aim to estimate the model posterior P(h = h& (2)) ) that represents the responsibility of the k-th hypothesis in the hypothesis set w.r.t. the local data batch Z' {(x') وو") while in the M-step we seek to maximize
K ((H) = P(h-=ha 7')
Σ log TTeP (y' | hx)]
(4)
k=1
where Thk == P(h = ha) 0 denotes the prior of the k-th hypothesis in H. This draws a direct connection between OSL and EM: the E-step corresponds to the functionality of the subjective function that chooses a hypothesis for a given data batch; the M-step corresponds to updating the selected hypothesis by minimizing the empirical prediction error in the episode. The main difference is that here we assume the subjective function to be deterministic, representing a "hard" assignment of the data to the model. This entails the usage of variant known hard EM (Samdani et al., 2012). which considers the posterior to be a Dirac delta function. Applying this constraint, the E- step of EM yields h arg m Σソ= log ply xx' hy) under uniform prior, motivating principled choice of the subjective function:
9 (H, ) = arg min
Σ e (1((z)),))) [m].
(5a)
kEH
g H d.) arg min E (h(x), E [N].
(5b)
REH
which can be interpreted as selecting the hypothesis that incurs the smallest (empirical or expected) error. While this connection is not rigorous in general, in some cases exact equivalence can be ob- tained when certain types of loss functions and likelihood families are applied, which encompasses common regression and classification settings. We provide concrete analysis in Appendix A
2.4 OVERALL ALGORITHM
In practice, we assume that the hypothesis set H comprises K parameterized hypotheses with pa- rameter vectors θ (0,, 02 ... 0xx respectively. In the high level, with the choice of the empirical subjective function 5a our algorithm consists of two phases in each sampling episode: (i) evaluating the error of each hypothesis // w.r.t. the data in this episode, and (ii) training the hypothesis with the smallest error. For brevity, we introduce notion of empirical episodic error defined as
a (h: (l=;))== Ee
- [h ( , i [m).
(6)
where h E H. is a hypothesis parameterized by 6. Then, phase (i) aims to find a hypothesis that minnnize Note that this selection process may induce bias between empirical and expected objectives and 3 since a hypothesis that minimizes the empirical loss on finite samples may not minimize the expected loss this domain. Hence, the global error of OSL can be intuitively decomposed into high-level subjective error that measures the reliability of the model selection, and a low-level model error that measures the accuracy of models, of which we provide detailed theoretical analysis in Section 3.2 In practice, we parameterize each hypothesis in the hypothesis set with deep neural network (D (DNN), and apply stochastic gradient descent (SGD) for the optimization process. We provide the pseudo-code of OSL. in Appendix
4

---

Under review as a conference paper at ICLR 2022
3
THEORETICAL ANALYSIS
In this section, we present the theoretical analysis on OSL. All proofs are deferred to Appendix C
3.1 LEARNABILITY
We first analyze the learnability of OSL based on PAC learnability (Valiant 1984). Since our analysis directly applys to conventional supervised learning by setting K 1, we also verify the conflict phenomenon mentioned in S [ theoretical perspective. While the learnability in conventional PAC analysis mainly relates to the choice of the hypothesis space, open-ended data imposes a source of complexity by its mapping rank, and we expect the cardinality of the proposed hypothesis set can compensate this complexity. We consider the realizable case where the hypothesis space covers the target functions in all domains, which helps underline the core characteristic of our problem. We begin by a result on the form of the optimal solutions of OSL.
Proposition 1 (Form of the optimal solutions). Assume that the target functions in all domains are realizable. Then, the following two propositions are equivalent:
(1) For all domain distributions Q and data distributions P2, ,N. er( = 0.
(2) For each domain d (P,c) in D, there exists h E H such that En [k(x), (())
Proposition Suggesss that minimizing the expected global error 33 with (bjeeliitsss a global optimal solution where every target function is learned accurately in the realizable case. Note that this does not require N hypotheses for N domains, since non-conflict domains can be incorporated into the same model. In other words, what determines the minimal cardinality of the hypothesis set is not the number of the domains, but the number of confticting domains, which can be exactly characterized by the mapping rank. Formally, we attain necessary condition of the PAC learnability of OSL. Theorem (Learnaiiity)) A necessary condition of the PAC learnability of OSL is K 2 R.
Theorem D indicates that the cardinality the hypothesis set should be large enough to enable effective learning, and shows the impact of mapping rank on the learnability of OSL.
Remark 1. While is generally hard to derive a necessary and sufficient condition of PAC learn- ability theoretically (which requires a sample-efficient optimization algorithm), we empirically find that K 2 R is indeed an essential condition for learnability with complex hypothesis spaces (pa- rameterized DNNs). We also note that several recent works (Allen-Zhu et al. [2019] Du et al.) al]] 2019)) have proved that over-parameterized neural networks trained by SGD can achieve zero training error in polynomial time under non-convexity, which may also be used to enhance our analysis. We leave a more rigorous study for future work.
3.2 GENERALIZATION ERROR
We have shown that minimizing the expected global error is sufficient for effective learning from open-ended data. However, practice, since we only have access to the empirical global error, how to control the discrepancy between these two errors, i.e., the generalization error, remains crucial. In this section, we identify the terms in the generalization error that respectively correspond to the high-level subjective error and the low-level model error of OSL, and discuss their controlling strategies. The key results are (i) the number of episodes and episodic samples can compensate each other in controlling the low-level model error, and (ii) the number of episodic samples is critical for controlling the high-level subjective error. We have the following theorem:
Theorem 2 (Generalization error bound). For any 8 E (0. 1}. the following inequality holds uni- formly for all hypothesis sets H E H. with probability at least 1 8:
VC(S) (In 2m/vc(s) + 1) In 6/12
< (H)
(7a)
VC(S) (In 2m/n/vc(s) + 1) In 8/18
m&
(7b)
m
mgn
mn
Am
VC(S) (In 2n/vC(S) + 1) In 8/24m
2
+ 2
(7c)
n
5

---

Under review as a conference paper at ICLR 2022
Labels
Labels
Labels
Color
Oyan
Color
Blue
Superclass
Vehicles
Gender
Male
Number
4
Category
Appare
Class
Bus
Train
(a) Parallel task:
Colored MNIST and Fashion Product Images
(b) Hierarchical task: CIFAR-100
Figure 1: Open-ended classification tasks and datasets.
where S [(P. + pl [h(a;; 0), c(x)]),0 E O is the function set of the domain-wise expected
error, S = (1,, v) - [b(x; 8), ul.. A E ② is the function set of the sample-wise error, my
E === 1 (ct = ck) is the sampling count of the larget function from the k-th domain dy E [N]).
and VC(.) the Vapnik- Chervonenkis (VC) dimension (Vapnik & Chervonenkis 1971).
Theorem 2 indicates that the expected global error bounded by the empirical global error plus three terms. The subjective estimation enror term [ is derived by bounding the discrepancy be- tween the empirical and the expected subjective functions due to the limitation of finite episodic samples (detailed derivation is in Appendix C.3) This term can be controlled by the sample-level complexity term VC(S) and the number of cpisodic samples n, which certifies the necessity of the local consistency assumption in Section Although in theory this error term converges to zero only n + oc, in practice we find that usually a very small n (c.g., n = 2) suffices (see Section relatively diverse, thus reducing
We posit that this is because the domains in experiments the difficulty of discriminating between different domains. The domain estimation error term 7a contains a domain-level complexity term VC(S), and converges to zero if the number of episodes reaches infinity (m + oo); the instance estimation error term 7b contains sample-level complexity terms VC(S), and converges to zero if the sample number in each episode or the number of episodes reaches infinity (n + oo or m - oc), showing the synergy between high-level domain samples and low-level data samples in controlling the model-wise generalization error.
Comparison with existing bounds. We compare our bound 7 with existing bounds of conventional supervised learning (Vapnik] 2013) McAllester, 1999) and meta-learning (Pentina & Lampert 2014] Amit & Meir 2018). Typically, supervised learning bounds contain instance-leve complexity term as 7b and meta-learning bounds further contain a task-level complexity term as 7a Yet, conven- tional supervised learning only considers single domain or multiple known domains, while meta- learning treats each episode as a new domain rather than domains that may have been encountered in OSL. Thus, none of these bounds contains explicit inference term as 7c
Remark 2. While our bound applies VC dimension as the complexity measure, extensions to other data-dependant complexity measures such Rademacher and Gaussian complexities (Bartlett & Mendelson 2002) Koltchinski & Panchenko] 2000)p is straightforward. It is worth noting that the bounds based on these measures share the same asymptotic property w.r.t. m and in the bound
4 EXPERIMENTS
In this section, we report experimental results on two basic supervised learning tasks with open- ended data: regression and classification. Our experiments are designed (i) validate our theoretical claims, (ii) assess the effectiveness of OSL, and (iii) compare OSL with task-specific baselines.
4.1 SETUP AND BASELINES
Open-ended regression. We consider an open-ended regression task in which data points are sam- pled from three heterogeneous functions with varied shapes, as shown Figure (a lines). The details of this task are in Appendix D
To the best our knowledge, there no off-the-shelf method that can automatically disentangle the data from different domains in the open-ended regression setting. The most relevant approach from our view is meta-learning that learns global model which can be fastly fine-tuned to fit each domain (this is different from OSL, which assigns different models to conflicting domains explic- itly). Hence, we compare OSL with three baselines. (1) Vanilla: a conventional ERM-based learner. (2) MAML. (Fin et al. 2017): popular gradient-based meta-learning approach. (3) Modular (Alet

---

Under review as a conference paper at ICLR 2022
MS 0665
5314
NSC 0531L
(a) Vanilla (dashed)
(b) MAML
Modular
(a) Smaller m
(b) Smaller
9
y
9
(d) OSI. (K- = 2) (c) OSI. (K 3) (1) OSL (K
(c) Subjective error of (b) (dashed)
Figure 2: Results of OSL, and the baselines on the open- ended regression task. (a) Ground-truth functions (solid) and the result of Vanilla (dashed). (b)() Results of MAML and Modular. (f) Results of OSL with different num- ber of low-level models (solid). The dashed line in (f) in- dicates that OSL abandons redundant model.
Figure 3: Impact of sampling hyperpa-
rameters on OSL. (a) Fewer episodes
(m 50). (b) Fewer episodic sam-
ples (n 1). (c) The subjective error
when n = 1 (dashed lines represent
incorrect data allocations).
ctt al., 2018): a modular meta-learning approach that extends MAML using multiple modules. We set the hyperparameters of OSL to K = 3, 250 and π 2. To verify theoretical results, we also run OSL with different number of hypotheses (K = 2 and = 4) and different sampling hyperparameters (m 50,
and m 250, 1). More details are in Appendix D
In addition, we demonstrate the effectiveness of OSL on a real-world multi-dimensional regression task; details and results are in Appendix E.
Open-ended classification. We consider two types of open-ended image recognition tasks where the same image may correspond to different labels in different sample pairs. We refer these tasks according to the structure of their label spaces, namely parallel and hierarchical tasks. For parallel tasks, we derive the data respectively from Colored MNIST, a variant of MNIST where each digit is assigned with a digit label and a color label, and Fashion Product Images (Aggarwal 2019). a multi-attribute clothes dataset that involves main parallel tasks including gender, category and color classification, as shown in Figure Ia] we construct open-ended datasets by randomly choosing one label from the label set for each image. For the hierarchical task, we derive the data from CIFAR-100 (Krizhessky & Hinton 2009), widely-used image recognition dataset comprising 100 classes with "fine" labels subsumed by 20 superclasses with "coarse" labels, as shown in Figure [b] we construct the open-ended dataset by randomly using the fine or the coarse label for each image.
In classification, the most relevant problem setting to OSL multi-label learning ęZhang Zhou 2014], which considers the scenario where an input x is related with label set y [1,) ) This setting is similar to OSL in terms that both OSL and multi-label learning considers the scenario where the same input may relate to multiple labels. However, the key difference is that multi-label learning requires that all labels in the label set are provided simaltaneously, while in OSL each data sample only contains one label y/ E y. Therefore, the setting of OSL can be alternatively modeled as "multi-label learning with missing labels", i.e., in each sample N - 1 labels in are missing and only one label remains (note that this very extreme setting). Hence, we compare OSL with the following baselines. (1) Probabilistic concepts (ProbCon): this baseline directly models the relation between inputs and outputs using an conditional probability distribution (Devroye al. 1996). We adopt a single-model DNN to learn this probability distribution using the cross-entrop loss and choose top-N labels as the final prediction results. (2) Semi-supervised multi-label learning: this class of methods model open-ended classification the problem of "multi-label learning with missing labels" (Yu et al.) 2014 Bi Kwok 2014 Huang et al.) 2019), i.c., only one label in each label set is available. We compare OSL with two representative semi-supervised methods: Pseudo- Maaeel (Pseudo-L) (Lee 2013) and Label propagation (LabelProp) (Iscen et al. 2019). We also introduce two oracle baselines using additional information. (3) Full labels Lull-L):: a standard multi-label learning method where we provide the full label set for each image, hence there is no missing labels. (4) Full tasks (FullT)): a standard multi-task learning method where the "task" of

---

Under review as a conference paper at ICLR 2022
each image is designated by human experts in advance ensure that there is conflict within each task. More details on baselines can be found in Appendix D
To further demonstrate the applicability of OSL, also conducted experiment Fashion Prod- uct Images with simulated concept shift between domains with the same label space; details and results in Appendix
4.2 EVALUATION METRICS
Since the global error of OSL is related to the error of both the high-level subjective function and the low-level models, we respectively propose two metrics to quantitatively estimate these errors.
Subjective error. This metric measures the learner's ability to perform appropriate data allocation. Given a domain d, a suitable subjective function should yield stable allocations for all data batches sampled from this domain. Thus, measure the enror of the subjective function using the rate of inconsistent data allocations, which we define as
SUBERR(d) = max REH La
( =n]
(8)
where la denotes the total number of samples in domain d (the same below).
Model error. This metric measures the learner's ability to make accurate in-domain predictions, which is analagous to traditional single-task error metrics. Given domain it takes the form of
MODERR(d) = min beft la
Σ e (2,)
(9)
where we apply ely, v') (y 1/2 for regression and e(y, 3/) ( # v/) for classification.
4.3 EMPIRICAL RESULTS AND ANALYSES
Open-ended regression. We compare the perfor- mance of OSL. and the baselines in Figure 2 Unsur- prisingly, the vanilla baseline converges mean function (dashed curve in Figure 2a). MAML successfully predicts the left part of all target func- tions by fine-tuning from episodic samples, but fails in the right part where functions exhibit larger differ- ence. We hypothesis that it is because meta-learning typically requires tasks to be in sufficient numbers, and with more similarity. Although Modular rectly predicts the general trend of the curves, its predictions still inaccurate in fine- fine-grained de- tails. Note that both meta-learning methods use more episodic data samples than OSL (see Ap- pendix I.3.I). Meanwhile, OSL with K > R (K 4) successfully distinguishes different functions and recover each of them accurately while OSL with K < R (K 2) fails, which matches our analysis in Section 3.1 In particular, OSI with K = automatically leaves one network to be redundant (dashed curve Figure 2f). demonstrating the robustness of our algorithm.
Black
trivial
Male
Color
Gender
Female
Blue
Subjoctive
Subjestivve 2
Subjective
Apparel
Canegory
ccessociis
Figure 4: Visualization of the features output by OSL in Fashion Product Images.
Figure illustrates the impact of sampling hyperparameters on OSL. Concretely, OSL with fewer sampling episodes m = 50 induces a large model error D which corresponds to the sample-wise estimation term in the generalization error 7b since the product vı is not sufficiently large. On the other hand, OSL with fewer episodic samples n = induces a large subjective error & which corresponds to the subjective estimation term in the generalization error 7e Another interesting phenomenon is that the curves in Figure 3b are partially swapped compared with the ground truth when 1, indicating wrong data allocation, which also corroborates theory.
8

---

Under review as a conference paper at ICLR 2022
Table 1: Results of OSL and the basclines on open-ended classification tasks. We report subjective and model errors on Number (Num) and Color (Col) domains of Colored MNIST, Gender (Gen), Category (Cat) and Color (Col) domains of Fashion Product Images, and Superclass (Sup) and Class (Cla) domains of CIFAR- respectively.
Colored MNIST
Fashion Product Images
CIFAR-100
Methods
SUBERR
MODERR
SUBERR
MODERR
SUBERR
MODERR
Num
Col
Num
Col
Gen
Cat
Col
Gen
Cat
Col
Sup
Cla
Sup
Cla
ProbCon
0.09 0.34
3.04
0.39
8.81
13.54
12.50
22.80
18.02
33.15
5.59
5.44
27.35
31.20
Pseudo-L
6.62 9.25
7.47
10.08
4.95
5.40
14.59
33.69
20.04
34.06
9.26
8.38
28.46
38.96
LabclProp
7.53 0.28
11.52
13.57
2.91
7.22
21.97
14.59
50.43
64.48
18.82
10.34
66.62
45.17
OSL (ours)
0.10 0.00
1.70
0.03
0.00
0.00
0.00
7.87
1.93
12.85
1.05
0.82
21.40
25.05
Full-L.
0.23 0.00
1.02
0.00
1.19
0.86
7.44
8.46
1.17
9.45
7.84
0.84
22.08
26.29
Full-T
0 0
1.20
0.00
0
0
0
7.14
1.90
11.04
0 21.11 25.08
Open-ended classification. Table 1 shows the results of OSL and the baselines open-ended classification tasks. On all tasks, OSL outperforms all baselines on both the subjective error and the model error. It is also worth noting that compared to the oracle Full-L with full label annotations, OSL still induces smaller subjective error, showing a strong capability of domain-level cognition that resembles the "ground truth" of human experts (Full-T). In addition, we visualize the features output by OSL on Fashion Product Images, as shown by Figure 4 The visualization shows that different models of OSL automatically focus on different label subspaces corresponding different domains, which further complements our empirical results.
5 RELATED WORK
Apart from the formulation in this paper, open-ended data may also be formulated using the frame- work of multi-label learning with partial labels (Zhang & Zhou 2014) or probabilistic density es- timation, such as probabilistic concepts (Kearns & Schapire 1994, Devroye et al., (996) and the energy-based learning framework (LeCun et al., (006)) A fundamental difference between these formulations and OSL is that these methods learn a unified model, while our method explicitly en- courages the learner to perform high-level data allocation and result in set of independent models. A recent work by Su et al. (2220) studies a similar problem as ours where the goal of the learner is to learn from mast samples without task annotation. However, work employs different objective function and our method has formal theoretical justification.
Extensive literature has investigated the collaboration of multiple models (or modules) in completing one or more tasks (Doya et al. 2002] Shazeer et al. 2017] Meyerson & Mikkulainen 2019 Alet
al., 2018 Nagabandi et al., 2019 Chen et al., 2020 Yang et al.) (020). The difference between our work and these works is that our multi-model architecture is driven by the inherent conflict in open-ended data without manual alignment between models and tasks, and we only allow a single low-level model to be invoked during a particular sampling episode.
DISCUSSION
An important open problem in machine learning is move from highly specialized AI systems to agents with more general abilities. While various viewpoints exist, the notion of ended environments has been advocated by an increasing number of works (Goertzel & Pennachin 2007] Clune, 2019 Silver et al. 202T). In this work, we attempt to formalize this notion in the context of supervised learning, and provide a general learning framework with theoretical guarantee. We hope that our work can facilitate future research in this direction.
Limitations and future work. As mentioned in Section [ our formulation is limited to the fully- informative data where absolute predictions can be made given the inputs. While this assumption is valid in a variety of applications, it is interesting to develop methods that can also handle data with stochasticity. Other future work includes developing lifelong learning agents that benefit from the growing diversity of onen-ended data as the sampling process continuously proceeds, and extending our framework other learning regimes, e.g., semi-supervised learning and reinforcement learning.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
This paper presents a new supervised learning framework which considers learning from the data directly sampled from open-ended environments such the real world. Hence, our work may facilitate the development of more generally applicable artificial agents. Also, as mentioned in Section[], our work has potential practical applications in federated learning and algorithmic fairness domains. Therefore, our work may promote the development of learning algorithms.
and fair machine
REPRODUCIBILITY STATEMENT
For all theoretical results in this paper (Proposition D Theorem 1 and Theorem 2). we provide complete proofs in the appendix (see Appendix C For the open-ended regression and classification experiments, we provide Py PyTorch implementations in the supplementary material; the code for the classification experiment on CIFAR-100 will be released if the paper is accepted since it requires additional pre-trained network backbones to run. The details of datasets, baselines and hyperparam- eters are provided the appendix (see Appendix D
REFERENCES
Sam Adams, Itmar Arel, Joscha Bach, Robert Coop, Rod Furlan, Ben Goertzel, J. Storts Hall, Alexei Samsonovich, Matthias Scheutz, Matthew Schlesinger, Stuart C. Shapiro, and John Sowa. Mapping the landscape of human-level artificial general intelligence. Al Magazine, 33(1), 2012.
Param Aggarwal.
Fashion product images dataset. attps://wwit http://wwwwkggll..ee com/ maaiaaae-ddtasset....eee 2019.
r aaraaagan
Ferran Alet, Tomás Lozano-Pérez, and Leslie Kaelbling. Modular meta-learning, In CoRL, 2018.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. ICML, 2019.
Ron Amit and Ron Meir. Meta-learning by adjusting priors based on extended pac-bayes theory. In ICML, 2018
Peter L. 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 Wort- Vaughan. A theory of learning from different domains. Machine learning, 79(1-2):151-175, 2010.
Wei Bi and James Kwok. Multilabel classification with label correlations and missing labels. In AAAI, 2014.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Generalizing from several related classification tasks to a new unlabeled sample. In Advances in Neural Information Processing Systems, 2011.
Yutian Chen, Abram I. Friesen, Feryal Behbahani, Arnaud Doucet, David Budden, Matthew W Hoffman, and Nando de Freitas. Modular meta-learning with shrinkage. In Advances in Neural Information Processing Systems, 2020.
Jeff Clune. AI-GAs: Al-generating algorithms, an alternate paradigm for producing general artificial intelligence. arXiv preprint arXiv: 100e::905000000 10985, 2019.
Cédric Colas, Pierre Fournier, Olivier Sigaud, Mohamed Chetouani, and Pierre- Yves Oudeyer. CU- RIOUS: Intrinsically motivated multi-task, multi-goal reinforcement learning. In ICMI., 2019.
Elliot Creager. Jöm-Henrik Jacobsen, and Richard Zemel. Environment Inference for Invariant Learning. In ICML, 2021.
10

---

Under review as a conference paper at ICLR 2022
Arthur P. Dempster, Nan M. Laird, and Donald B. Rubin. Maximum likelihood from incompleee data via the EM algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1):1-22, 1977.
Lue Devroye, László Györfi, and Gábor Lugosi. A probabilistie theory of pattern recogni- lion, volume 31 of Stochustic Modelling and Applied Probability. New York, 1996. doi: 10.10077978-1-400 1-412--------.
Thomas G. Dietterich. Ensemble learning. The handbook of brain theory and neural networks, (1):110-125, 2002.
Kenji Doya, Kazuyuki Samejima, Ken-ichi Katagiri, and Mitsuo Kawato. Multiple model-based reinforcement learning. Neural Computation, 14(6)1347-1369, 2002.
Simon S. Du, Jason D. 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-agnostic meta-learning for fast adaptation of deep networks. In ICML, 2017.
Chelsea Finn, Aravind Rajeswaran, Sham Kakade, and Sergey Levine. Online meta-learning. In ICML., 2019.
Jordi Fonollosa, Sadique Sheik, Ramón Huerta, and Santiago Marco. Reservoir computing com- pensates slow response of chemosensor arrays exposed fast varying gas concentrations in continuous monitoring. Sensors and Actuators B: Chemical, 215:618-629 2015.
Ben Goertzel and Cassio Pennachin. Artificial general intelligence, volume 2. 2007.
Chi Han, Jiayuan Mao, Chuang Gan, Josh Tenenbaum, and Jiajun Wu. Visual concept-meetcooneet learning. In Advances in Neural Information Processing Systems, 2019.
Alex Hanna, Emily Denton, Andrew Smart, and Jamila Soith-Loud. Towards critical race method- ology in algorithmic fairness. In Proceedings of the 2020 conference on fairness, accountability, and transparency, pp. 501-512, 2020.
David Haussler. Probably approximately correct learning. AAAI, 1990.
Judy Hoffman, Mehryar Mohri, and Ningshan Zhang. Algorithms and theory for multiple-source adaptation. In Advances in Neural Information Processing Systems, 2018.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In CVPR, 2017.
Jun Huang. Feng Qin, Xiao Zheng, Zekai Cheng. Zhixiang Yuan, Weigang Zhang, and Qingming Huang. Improving multi-label classification with missing labels by learning label-specific fea- tures. Information Sciences, 492:124-146, 2019.
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, Adria 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, Prateek 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 2022
Michael J. Kearns and Robert E. Schapire. Efficient distribution-free learning of probabilisstic cepts. Journal of Computer and System Sciences, 48(3):464 1994.
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. 143-457. Springer, 2000.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Sumit Chopra, Raia Hadsell, M. Ranzato, and F. Huang. A tutorial energy based learning. Predicting structured data, 2006.
Dong-Hyu Lee. Pseudo-label:
The simple and efficient semi-supervised learning method for deep neural networks. Workshop on challenges in representation learning, ICML, 2013.
David A. McAllester. PAC-Bayesian model averaging. 307435.
COLT, 1999. doi: 10. 10.1145/307400.
Elliot Meyerson and Risto Miikkulainen. Modular universal reparameterization: Deep multi-task learning across diverse domains. In Advances in Neural Information Processing Systems, 2019.
Krikamol Muandet, David Balduzzi, and Bernhard Scholkopf. Domain generalization via invariant feature representation. In ICML, 2013.
Anusha Nagabandi, Chelsea Finn, and Sergey Levine. Deep online learning via meta-learning: Continual adaptation for model-based RL. In ICLR, 2019.
Sinno Jialin Pan and Qiang Yang. A survey on transfer learning. IEEE Transactions on Knowledge and Data Engineering. 22(10):1355-1359 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, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, nigh-performance deep learning library. In Advances in Neural Information Processing Systems, 2019.
Anastasia Pentina and Christoph H Lampert. A pac-bayesian bound for lifelong learning. In ICMI., 2014.
Omer Sagi and Lior Rokach. Ensemble learning: A survey. WIREs Data Mining and Knowledge Discovery, 8(4):e 1249, 2018
Rajhans Samdani, Ming- Weig Chang, and Dan Roth. Unified expectation maximization. Proceed- ings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2012.
Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gad gated mfxture-of-eepprtss layer. In ICLR, 2017.
David Silver, Satinder Singh, Doina Precup, and Richard S. Sutton. Reward is enough. Artificial Intelligence, 2021.
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 deep transfer learning. In International conference artificial neural networks, 2018.
Leslie Valiant. A theory of the learnable. Communications of the ACM, (
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-280, 1971.
12

---

Under review as a conference paper at ICLR 2022
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
Mei Wang and Weihong Deng. Deep visual domain adaptation: A survey. Neurocomputing, 312:
135-153, 2018.
Rui Wang, Joel Lehman, Aditya Rawal, Jiale Zhi, Yulun Li, Jeff Clune, and Kenneth Stanley. Enhanced poet: Open-ended reinforcement learning through unbounded invention of learning challenges and their solutions. In ICML, 2020.
Ruihan Yang. Huazhe Xu, Yi Wu, and Xiaolong Wang. Multi-task reinforcement learning with soft modularization. In Advances in Neural Information Processing Systems, 2020.
Hsiang-Fu Yu, Prateek Jain, Purushottam Kar, and Inderjit Dhillon. Large-scale multi-label learning with missing labels. In ICML, 2014.
Cha Zhang and Yunqian Ma. Ensemble machine learning: methods and applications. Springer, 2012.
Min-Ling Zhang and Zhi-Hua Zhou A review on multi-label learning algorithms. IEEE Transac- fions Knowledge and Data Engineering, 26(8):1819-1837 2014.
Kaiyang Zhou, Ziwei Liu, Yu Qiao, Tao Xiang, and Chen Change Loy. Domain generalization in vision: A survey, arXiv preprint arXiv:2103.02503, 2021.
Zhi-H Hua Zhou. Ensemble learning. In Machine Learming, pp. 181-210. 2021.
13

---

Under review as a conference paper at ICLR 2022
A DISCUSSION ON THE SUBJECTIVE FUNCTION
In Section we derive our design of the subjective function using a EM-based maximum likeli- hood formulation. However, the exact equivalence between the E-step of hard EM and the subjective function has not been established, since it relies on the exact form of the loss function É(V, y²) and conditional likelihood p(y(r, lyx); k [K]. As a complement, in the sequel we provide two examples where under the uniform prior, the exact equivalence between calculating the posterior P(h = 1 y) and the expected subjective function 5b can obtained (hence their empirical counterparts are also equivalent). Recall that under the uniform prior, the E-step of hard EM yields arg m log ply(a, h2).
Example 1 (Regression with isotropic Gaussian joint likelihood). Consider a regression task where assume that given the random variable (x,, y), the joint distribution of its conditional likelihoods conforms to an isotropic Gaussian N( <lx) where e R is a variance parameter and I is
K K identity matrix. From plylar, hv) exp (v (V- and (xxx)) (2) have that arg max ş plylar, hy) arg minsye [(y hu (x)))) This equals to the expected subjective function with squared loss f/.
y¹)².
Example (Classification with independent categorical likelihoods).. Consider multi-class clas- sification task where we assume that given the random variable (xr, y), all conditional likeli- hoods conform independent categorical distributions with parameters A2, Ak), where A (AE1, ... AKL). E/=1 Aaj = -1,k E [K] and is the total number of classes. From plylæ, hx) 1 (z) where y = (y), (y wr. E (0, ΣE U/ = and Aα(x) = (x) we have that arg m logp(y x. h₂) + arg mignn Σ yy log hæy where hxy(2) denotes the predicted probability of the j-th class and f/j the corresponding ground truth. This equals to the expected subjective function with cross-entrope loss Ely. v)) = = - y/ log
B ALGORITHM PSEUDO-CODE
We provide the pseudo-code of OSL Algorithm
C PROOFS OF THEORETICAL RESULTS
In this section, we provide the proofs of our theoretical results, For better exposition, we restate each theorem before its proof.
C.I PROOF OF PROPOSITION
Proposition 1 (Form of the optimal solution). Assume that the target functions in all domains are realizable. Then, the following two propositions are equivalent:
(1) For all domain distributions Q and data distributions P2.P PN. er(H) 0.
(2) For each d = (P, c) in D, there exists h E H such that E [h(x), c(x) 0.
Proof. The derivation of proposition (1) from proposition (2) obvious. On the other hand, proposition (2) is false, i.e., there exists & E [N] such that for all j E [K], hy # ck. Then, we have
er(ll) Ee.-Q min eTP, (h,
hell
2 q(cx) min ern. (h,
hell
From the above know that C₁ H, thus there exists Pe such that erp, (h, ck) > for every Н. This indicates that er(H) > 0, which is contradiction with proposition (a). Therefore, proposition (2) must hold if proposition (1) is true.
14

---

Under review as a conference paper at ICLR 2022
Algorithm OSL: Open-ended Supervised Learning
Require: Hypothesis set H- {h1, h2 hxk,, sampling hyperparameters and n.
1: for h = 1,2,, , epochs do
2: for 1, y episodes do
3: Sample data Z {(x') y)"), (I²² y²)) "
4: Select hypothesis h from the hypothesis set using the empirical subjective function 5a
5: Train the hypothesis h' by minimizing the empirical episodic error
6: end for
7:
end for
C.2 PROOF OF THEOREM 1
We first revisit the definition of PAC learnability.
Definition 2 (PAC learnability). target function set class C is said to be PAC learnable if there exists algorithm A such that for any 0 and 8 (0, for all distributions Q and distribution set P, the following holds:
(l)r(H) c 1
(10)
target function set class C is said to be PAC learnable if there exists an algorithm and polynomial function poly(;,.." such that for any >> 0 and 5 > 0, for all distributions Q and distribution set P, the following holds for any sample size mm poly(1/e, 1/6, size(c))
The above definition can viewed as an extension the single-task PAC learnability (Haussler, 1990) that considers the problem of learning single target function. Based this definition, in the following we give the proof.
Theorem 1. necessary condition of the PAC learnability of OSI is K 2 R.
Proof. According to Definition 2 if OSL is PAC learnable, there must exist an algorithm that outputs hypothesis set H with zero error, i.e., er er(H)
for every Q and P (otherwise the inequality I0 will not hold for small enough and 8 < 1). Proposition indicates that this is equivalent to e; E H E [N]. which is impossible if K < R according to Definition]
[]
C.3 PROOF OF THEOREM 2
We first introduce several technical lemmas.
Lemma 1. Let LEITT be a set of events satisfying ((E)) 2 - 8; with some 8, 2 0,i 1, n. Then, P 1- Lemma (Single-task generalization error bound (Vapnik 2013 Ler AS Q(2, S B be measurable and bounded real-valued function set, of which the Vapnik- Chenvii-hhrroonnisss (VC) dimension Vapnnk & Chervonenkis) 1971) is VC(Q). Let {z1, ø2, ... zn)r - be data samples sampled i.i.d. from a distribution P with size Then, for any ö (0, 1), the following inequality holds with probability at least 1 - 5:
2-
E ((x,)(2))) 1 12
( i=1
$ S - A)vc(n)
(11)
where
(nn) = VC(@) (In2n//c(2) + +1) 1n6/
(12)
n
Then, we upper bound the error induced by the estimation the expected subjective function 5bb in each sampling episode of OSL,, which is critical in bounding the generalization error. Recall that
15

---

Under review as a conference paper at ICLR 2022
superseripts to denote the sampling index, e.g., d' (P), d') denotes the i-th domain sample, which can be any domains in the domain set D. We define two shorthands as follows:
h := arg min pi c( i E [m)]
(13a)
hEH
in == arg min
Σ e [1 (1²2) y4 E [m]]
(13b)
hEH
where: denotes the i-th sampling episode OSL, H is the hypothesis set.
Lemma 3 (Subjective estimation error bound). Let { (x (ot")y²)) ......... (x0 "n be episodic sam- ples in the i-th (i E (m]) sampling episode ii.d. drawn from domain df with size n. Then, for any 5 (0, 1}, the following inequality holds uniformly for all hypothesis E with probubility at least 1 - 8:
1 m
Σ 2=1
e [h (x")
R (x²) v0]
m
(14)
VC(S) 2n 2n/vC(S) + 1) In 6/8m
2
2
where S = (II,)) + l [b( v), E θ is the function set of the sample-wise error.
Proof.
We have the following dccomposition:
h (x)) 50
h (z+1) v80]
h (x²) ,1 - Ex-rre (2)
Enp prl ef) Exnpil
E E (x)
n Σ
e hi (x (x*) yb4
+
in which the original difference is decomposed into three terms. By definition 13a and 13b
the middle term is non-positive. Using Lemma 2 by substituting Q with
[r, y)
l [h( (), y)} and replacing 8 with 6/2m, the first term and the last term can both be bounded by
VC(S) In (2n/vC(S) + 1) In 6/8m + with probability at least 6/2 (Lemma Combining
72
n.
these two bounds using Lemma completes the proof.
Now give the proof of the main theorem.
Theorem (Generalization error bound of OSL). For any â E (0, 11. the following inequality holds uniformly for all hypothesis sets H H. with probability at least 5:
er(H) s (H( + VC(S) (In (m/vc(s)))) + 1) - In 6/12
1
+ m
(15a)
m
m
VC(S) (In 2m/n/vc(S) + 1)
In 8/12N
+
(15b)
mgn
Am l
VC(S) (In 20/VC(()) + +) In 8/24m
+ 2
(15c)
n
where S = [(P, c) + Ep [h(x; 8), (x)) E θ is the function set of the domain-wise expected
error, S = {(x. y) + [b<x; 0),)), E ② is the function set of the sample-wis error, my
16

---

Under review as a conference paper at ICLR 2022
En 1 (d' ct) is the sampling count of the target function from the k-thh domain (k [N]), and VC(.) the Chenkk-Chrrooenkis (VC) dimension (Vapnik & Chervonenkis 1971
Proof. Combining the objectives 2 with the subjective function decomposition:
Sa 56 we have the following
er(H)- Er(H)- =
- min Ea (1((x),(((()) hell
1 m
Σ
min NEl
B pal pa
[h(x),
min E pil [1(x),
8 [ng (zx²) .
m
m
m
l h (I²) .30 Σ j=1
min NeW n
m
j=1
1=1
By definition
13a and
13b
we rewrite the equation above:
er(ff) - -(I))
p. (
1
m
E Bxrpil (
m
i=1
m
Ex [1 (x),
1
m
8 hng (2 .89
m
m
11 j=1
i=1
m
m Σ m
[hg (x²), 00
h (xt) 9/5
m
7
in which the generalization error of OSL is decomposed into three terms. By substituting Q in Lemma 2 by S ((P.c) + Exupl [h(z; 0), c(x)]} and replacing 8 with f/3, the first term can be bounded by /VC(S) In (2m/ve(5) + 1) In 6/12
with probability at least 1 - 5/3.. By replacing
m
m
VC(S) 2n/vc(s) + 1) In 6/24m
5 with 5/3 in Lemma we bound the last term by 2
+ with
n probability at least 1 f/3. There remains the middle term for which we have
1 pa [11(z),
1
Σ n
m
l [hg (x²) x8
m
m
1 Σ
Eip E ( - n
e [he (z .00
j=1
1
N
nm Σ j=1
My (hh
e [hi (Irgs mwyi
m
k=
1
N
E R. E (1)()).
1 nme
Σ
e (hg (Jag) Uks)
mi
m
nm
In the above we re-arrange the total m data batches accord- ing to the domains they belong to. With a little abuse of notation, in the third and fourth rows we use hi to denote the hypothesis that yields the smallest expected error in the k-th domain in D, i.e., hi arg minseR Ex-p, [h(z), cu (x)], k [N]. Note that this is different from the definition 13a, where h is defined upon the i-th domain sample. The above transformation ag- gregates the domain samples
Recall that my := E 1 (c'=
that data samples from the same domains that emerge multiple times can be accumulated and jointly considered, which leads to a tighter and more realistic error bound, By Lemma for every & E [N] and 8 E (0, 1). each inside term Exor, e (hg (2r), Cx cx(x))
17

---

Under review as a conference paper at ICLR 2022
mm Dj=r e [ng (raj, [k:)] can be bounded by VC(S) (In 2men/vc(s) + +) -Inn-nnn 8/12N
1
myn with probability least 6. By replacing 8 with 8/3N we bound the whole second term VC(S) (In 2man/vC(s) + 1) In 6/1N
mg
by Σk=1
me
1
with probability at least - 6/3
m
mgn
mn
(Lemma
Finally, combining the above bounds for all three terms using Lemma gives the result.
D EXPERIMENT DETAILS
In this section, additional details on the setup and settings of the experiment are provided. All experiments were conducted based on PyTorch (Paszke al. 2019) using NVIDIA 2080ti GPU. All data we used does not contain personally identifiable information or offensive content, and can be obtained from public data sources.
D.1 REGRESSION
We consider three heterogeneous mapping functions in absolute, sinusoidal and logarithmic function families as below:
|rr 2,
sin
3zx +
π
2
3 log
+ 5
y 2
1
where the range of x: is [-2, 2] for all three functions, yielding the open-ended data with R= 3. The sample hyperparameters are m = 250, n = 2, i.c. a total number of 500 data points are collected in 250 episodes, each with 2 samples in the data batch, and their underlying generation functions are randomly chosen from the three mapping functions.
Network and optimizer. A simple network architecture with 5 fully-comnected linear layers, each with 32 hidden units, is adopted and trained with SGD with step size a = 0.05, momentum = 0.9, and la weight decay- 10
D.2 CLASSIFICATION
Colored MNIST is an extended version of the well-known character recognition dataset MNIST, in which each gray-scale digital images are randomly colored with different colors. The dataset contains two parallel tasks of color and number classification (Rt = 2) with a total number of 60000 colored digits. The sample hyperparameters are m 60000, n
Fashion Product Images (Aggarwal 2019) is a dataset for automatic attribute completion and Q&A of clothing product images with multiple category labels in different domains. We choose 3 main parallel tasks (color, gender, category) with 8 main labels from the original dataset (R = 3), with 15000 images total. The sampling hyperparameters are m 15000, n
CIFAR-100 KKizhevsky & Hinton 2009) is classical benchmark for general image classification.
has a hierarchical structure with 20 superelasses and 100 classes, with 60000 images in total. Each superclass is from an upper-level "coarse" task, consisting of 5 "fine" classes, e.g., "insects" includes "bee, beetle, butterfly, caterpillar, cockroach". our experiments, these two different kinds of labels are randomly provided given image (R = 2). The sampling hyperparameters m 33000, n
Network and optimizer. In Colored MNIST, each network consists of 3 convolutional layers and fully-commn cullecconeetted layer. In Fashion Product Images, each network consists of 5 convolutional lay- and 3 fully-connected layers. We use Adam optimizer (Kingma & Ba 2015) with step size a = 0.002 and betas (0.5, 0.999) for these two datasets. In LIFAR-IOU. for OSL and all baselines, pre-trained DenseNet (Huang et al. 2017] backbone of Dem04Nett-L110-440 for
18

---

Under review as a conference paper at ICLR 2022
feature extraction to ensure fair comparison, and add 2 fully-comnected layers after the DenseNet backbone. We use SGD as the optimizer with step size a = 0.1 and momentum = 0.9.
D.3
BASELINE DETAILS
In this section, we provide more details on the baselines.
D.3.1 REGRESSION
MAML. For MAML, we adapt standard Py implememtation from GitHut with the same network with ours, and use the following hyperparameters:
Shot = 2, Evalation = 100, Outer step size = 0.05, Inner step size = 0.015,
Inner grad sleps 2, Eval grad sleps 5, Eval ilers 10, Ilerations 20000.
Modular, For modular meta-learning, we use the official PyTorch implementation from GitHut and use the following hyperparameters:
Shot = 2, Support = 2, Network = Linear 1 - 16 - 16 1,Nuum = 5, Composer Sun, meto.lr 0.003, Steps 3000.
Note that for Modular Meta-Learning a larger episodic sample number n = (consisting of support samples and 2 query samples) is adopted. Nevertheless, OSL still outperforms this approach using a smaller episodic sample number (n = 2).
D.3.2 CLASSIFICATION
Probablistic concepts. From the perspective of probability modeling, the relation between input and output y is subject probability distribution p(y xx), which the learning target. In open- ended classification, when different domains share similar frequency, such distribution can be approximated with total probability formula:
x
Σ plyl KEH
p(h)
Epuyl hEH
la
For classification problems, in each domain d, the corresponding ply x. h) is unimodal. Thus, their sum p(y x)) is multi-modal distribution, and network trained with cross-entropy loss is still an unbiased estimation for it. The final prediction is the labels with top-N conditional probabilities p(y .²)
Semi-supervised multi-label learning. From the perspective of semi-supervised multi-label learn- ing, the open-ended classification problem can be modeled as "multi-label learning with missing labels": consider the fully labeled data r + y {3 1.2 then, open-ended data provides only one label y E Y for each æ. i.e., all other labels are missing. Therefore, existing semi-super learning approaches may be modified to handle such problems. We consider two representative techniques, including Pseudo-label and Label propagation. Both implementations are slightly modified fit tasks.
Pseudo-label 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 pseudo labels according to its predictions, and all pseudo labels will iteratively modified during training until convergence.
Label propagation builds graph over the samples, where each node on the graph represents data sample, and each edge represents the distance of two nodes it collects in the feature space. The labels are propagated on adjacent nodes until all samples are fully labeled. The feature space is also iteratively adjusted along during training.
Full labels full tasks. Both these oracle baselines utilize manual annotations to tranform the open-ended data with R conventional supprreed data with R 1. More concretely, for Full
htt.a://hthhaa.oom/mrreeeee////s (MT license)
httpa////hhhaaccarraaaaaaaaaaaas larnninarnnnnnn (MIT license)
19

---

Under review as a conference paper at ICLR 2022
Table 2: Results of OSL 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 1) RMSE (domain 2) RMSE (macro-average)
Vanilla (single model)
76.5
89.7
83.1
OSL (ours)
34.0
72.6
53.3
Oracle
31.9
66.8
49.4
labels, label annotations from all domains are provided simultaneously as "multi-hot" label vector for each input sample, resulting in a standard multi-label learning problem. For Full tasks, raw data is separated into single-class classification tasks according to additional manual task annotation, resulting standard multi-task learning problem.
D.3.3 MEASURING THE SUBJECTIVE ERROR OF BASELINES IN CLASSIFICATION
Since the baselines classification experiments do not explicitly assign a separate model to each domain, the subjective error metric does not directly apply to these baselines. Hence, we estimate their subjective errors using another method: we directly select top-N predictions of these methods and compare them with the label spaces of different domains. We define the "coverage" of the selected top-N N labels over domain d as
La
COVERAGE(d) (d - La
1 13 top-N labels for input x; that in the label space of d),
where la denotes the total number of samples in domain d. The subjective error on is then calcu- lated as COVERAGE(A)
E ADDITIONAL EXPERIMENTAL RESULTS AND VISUALIZATIONS
In this section, we provide additional experimental results and visualizations.
E. MULTI-DIMENSIONAL OPEN-ENDED REGRESSION
To further demonstrate the efficacy of OSL in regression problems, we conducted experiments on real-world multidimensional regression dataset from UCI machine learning repository: Gas sen- sor array under dynamic gas mixtures dataset (Fonollosa et al. 2015). This dataset contains the recordings of 16 chemical sensors exposed to dynamic gas mixtures and the aim is to predict the concentrations gas mixture one domain, respectively representing Ethylene & Methane (domain 1) and Ethylene & CO (domain 2) gas mixtures, and randomly split both domains into training (90%) and test sets (10%).
gases, with 417,8504 instances and 16-dimensional attributes. We treat each
In this task, we compare OSL (two models, trained on the union of both domains) with a vanilla single model regressor (trained on the union of both domains) and an oracle regressor with two models separately trained on each domain. We report root mean square error (RMSE) on each domain and the macro-average RMSE over both domains in Table 2 The results indicate that OSL benefits from its automatic data allocation process, surpassing the vanilla baseline that trains single global model by a large margin and performs similarly with the oracle.
E.2 SIMULATED CONCEPT SHIFT CLASSIFICATION
To further demonstrate the applicability OSL, we conducted an experiment on Fashion Product Images with simulated concept shift between domains with the same lahel spaces. Concretely,
20

---

Under review as a conference paper at ICLR 2022
Labels
Male
Recommended
Domain
Not recommended
Female
Recommended
Domain
Not recommended
Open-ended classification tasks with simulated concept shift based on the Fashion Product Images dataset. Two domains indicate different recommendations based on the gender attribute.
Figure 5:
Table 3:
Results of OSL on simulated concept shift classification task. We report subjective and model errors on both domains.
SUBERR
MODERR
Methods
Domain 1 Domain Domain 1 Domain 2
Vanilla (single model)
49.5
50.5
OSL (ours)
5.37
5.37
7.40
9.65
Full-T (oracle)
0
0
7.14
6.53
randomly split the dataset into two domains according to the "gender" attribute: 50% of samples labeled as "Male" and 50% samples labeled "Female" relabeled as "I" and "Female" relabeled as "0", and other samples are assigned to domain 2 with "Male" relabeled "0" and "Female" relabeled as "I". As shown in Figure this setting resembles simple scenario of concept shift caused by human preference: the label "T" can be interpreted as an indicator of "interested" or "recommended", while the label "0" can be interpreted as an indicator of "not interested" or "not recommended". Since different people may have different preferences (in this simulated experiment this is caused by gender domain and domain respectively represents appropriate recommendations to male and female users), the data samples from different domains may possess different input-label conditional probability P(yl I), albeit with the same label space.
assigned to domain 1 with "Male"
Since the label space is binary and completely shared by both domains, multi-label baselines inapplicable in this setting since they will always produce both labels "0" and "1" for every input and do not discriminate between different domains, which is unmeaningful. Therefore, we compare OSL with the single-mode baseline (vanilla) and an oracle (Full-T) which separately train two models on both domains explicitly with data-domain correspondences known in advance. We report the model error and the subjective error of OSL in Table 3 Results show that the vanilla single-model baseline cannot learn meaningful prediction results since lacks the mechanism to distinguish conflicting samples from different domains, while OSL achieves relatively small subjective errors and similar model errors as the Full-T oracle, which demonstrate that OSL is effective even in the context where different domains possess exactly the same label spaces yet different input-label relations.
E.3 TRAINING AND INFERENCE TIME ON FASHION PRODUCT IMAGES
we compare the computational cost of OSL and other baselines in terms of training and inference time on 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 to predict all labels of one given input (in milliseconds). Concretely, for OSL and all baselines except for two oracles (Full-L and Full-T), we train the models for 50 epochs with about 15,000 images in every epoch; for Full-L and Full-T, we train for 10 epochs since these methods generally converge faster. For each method, 3,000 test samples randomly sampled from the test set and report the mean inference time on each test sample. All results obtained with PyTorch using NVIDIA 2080ti GPU.
In Table 4
test its total inference time on the same
21

---

Under review as a conference paper at ICLR 2022
Table 4: Wall-clock training and inference time of OSL and baselines on the Fashion Product Images dataset. The training time of ProbCon, Pseodu-L., LabelProp and OSL is measured over 50 epochs, and the training time of Full-L and Full-T is measured over 10 epochs. The inference time of all methods is measured using average over 3,000 test samples.
Methods
Training time (in seconds) Inference time (in milliseconds)
ProbCon
415
0.67
Pseudo-L
833
2.00
LabelProp
915
0.59
OSL (ours)
580
0.79
Full-L
159
0.68
Full-T
93
0.76
Epoch 0
Epoch 20
Epoch 40
Ezoch 60
-1
-2
-2
-2
Figure 6: An example of the iteration process and the final decision boundaries of the subjective function in the regression task.
As shown in the table, the time cost of OSL is generally on par with or lower than baselines that also involve iterative training (Pseudo-L and LabelProp). Although the ProbCon baseline trains faster, learns a global model without the mechanism of data allocation and thus performs significantly worse than OSL data-domain correspondences in advance, OSL only exhibits little additional computational over- head. This indicates that although OSL incorporates an extra data allocation process implemented by the subjective function, this process only induces a limited computational cost since it only requires additional network forward process without loss backpropagation, which is in general efficient.
have shown. Meanwhile, compared with the Full-T oracle that knows the
E,4 INTRRATION PROCESS ON THE REGRESSION TASK
In OSL, since the performance of the low-level models will impact the data allocation process of the high-level subjective function, the training of the subjective function and low-level networks can be regarded as iterative process, shown by Figure with example in open-ended regression, in which the different colored lines are designated to different subjects. All networks are randomly initialized, and in each iteration, each sample may be reallocated by the subjective function and used to further train the low-level networks. With the increasing of iterations, both subjective and model errors will reduce and converge along with the global loss. The last subfigure displays the final decision boundary of subjective function.
E.5 FEATURE VISUALIZATION ON THE CLASSIFICATION TASK
The OSL approach can extract different semantics from the same input sample, and map them to different feature spaces. Figure 7 displays the features output under all subjectives, where each color represents a subjective and each point corresponds to an image in the dataset.
F
MORE DISCUSSION ON RELATED WORK
In this section, we provide more discussion on related work.
Ensemble learning. Ensemble learning approaches typically employ multiple models to coopera- tively solve a given task (Dietterich) 2002) Zhang & Ma 2012 Sagi & Rokach] 2018 Zhou 202T). The prediction of each model is combined by weighting (boosting). majority voting (bagging)
22

---

Under review as a conference paper at ICLR 2022
Category
Gender
Color
Figure 7: Additional visualization of image features by OSL on Fashion Product Images.
learning a second-level meta-learner (stacking). Since different models process the same set of data (although sometimes with different sample weights), in ensemble learning there is typically no explicit "hard" allocation process between the data and models. In contrast, the multi-model architecture of OSL is driven by the inherent conflict in open-ended data, and each model only handles a proportion of the whole dataset without overlapping.
Domain adaptation and domain generalization. Pan & Yang. 2010 Tan et al. 2018 Wang & Deng
Domain adaptation (Ben-David al. 2010
2018
Hoffman et al. 2018) and domain gen-
eralization (Blanchard al., 2011: Muandet al.)
Zhou et al. [02] consider the scenario transferred to one or multiple new target domain(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 inaccessible during training (i.e., zero-shot gen- eralization). In other words, these formulations focus the adaptation or generalization capability of the model on target domain(s). In contrast, OSL focuses on the multi-domain Iraining process and considers the scenario where directly training a global model using the data from multiple con- flicting domains is problematic, and aims to resolve this training issue by performing automatic data allocation. Another important difference is that in domain adaptation and domain generalization the data-domain correspondences are available, while OSL weakens this assumption by only assuming that the data from each sampling episode is obtained from the same domain.
2013
where the learner trained on one or multiple source domain(s)
23


Reviews:
[{"review_id": "bPTLyJgxzhn", "reviewer": "Reviewer_R5W1", "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": "While the intuition behind the problem and the proposed solution is\nclear, the method is not clearly explained. In section 2.3, the\nconnection between the M and E steps is not clearly stated. More\nimportantly, the difference between conflicting and non-conflicting\ndomains is unclear. From the overall algorithm, it seems to me that\ndomains that do not share labels will be assigned to different\nhypotheses (even if, in principle, they could be mutually-exclusive\nlabels), because a hypothesis previously trained on a different set of\nlabels will not predict the new labels. If this is the case, the only\nnon-conflicting domains are those that share the same label set but\nmaybe have differences in the input (like in a domain-adaptation\nsetting).  In this case the method seems an overkill, as one can\neasily match the domains in the episodes by matching their labels (and\nthe subjective error should be minimized this way). The experiments\nseems to suggest that this is indeed the setting, because different\ndomains correspond to different label sets.\n\nAnother unclear part is how the method is applied in testing. Assuming\nthat testing is made on an episode corresponding to a single domain,\nhow is/are the appropriate hypothesis/hypotheses selected? If the\npredictions of all of them are collected, this seems to boil down to a\nsimple collection of multiclass classifiers (not sure what happens in\nthe regression case).\n\nDepending on the specific setting (to be clarified), there could be\nother (possibly simpler) competitors that are more appropriate. The\ncross-domain fertilization is not evaluated in the experiments as far\nas I can tell (apart from the matching of domains with the same\nlabels).", "summary_of_the_paper": "The paper proposes a learning setting involving a sequence of domains\nand a collection of hypotheses, During learning, each domain should be\nassigned to the most appropriate hypothesis by iteratively grouping\ntogether non-conflicting domains and keeping apart conflicting ones,\nso as to minimize the number of hypotheses learned and leverage\ncross-domain information when appropriate.", "summary_of_the_review": "The paper is unclear in the description of the method, so much that\nsome trivial solutions seem even more appropriate for the setting.\n\nSubstantial clarifications are needed to properly evaluate the quality\nof the contribution.\n\nAFTER REBUTTAL:\n\nThe authors did manage to address many of my concerns in their detailed rebuttal and extended experimental evaluation. The difference between the proposed setting and the existing alternatives is now clearer and the advantage of the method better highlighted thanks to the novel experiments. Some aspects are still a bit unclear (e.g. how the method is applied at the test phase), but I am now more inclined towards acceptance. ", "strength_and_weaknesses": "", "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": "RmsZCtmUwxb", "reviewer": "Reviewer_WErS", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "I like the general idea of the paper and appreciate the framework that I consider as novel and well suited for publication in general. I also find the technical part correct but did not check everything in detail. Concerns are caused by the baselines in the empirical comparison. The proposition of the framework clearly needs empirical support as the main argument is that a single classifier fails to learn all concepts properly. There need to be more information provided on the baselines to better understand whether they are appropriate or not. I am under the impression that the baselines may not be suitable to support the claims but this may be part of the rebuttal. \n\nI would appreciate a better differentiation to other ensemble learning approaches as well as learning with many classes/labels as well as transfer learning approaches in the discussion. ", "summary_of_the_paper": "The authors present a novel framework for learning different target concepts. They argue that so far, a single classifier is supposed to learn mixed concepts but usually fail. Hence, they propose a framework for sampling instances according to only a single target concept and solving this problem with classical ERM and repeating for other concepts. They provide theoretical analyses and empirical insights. ", "summary_of_the_review": "Conceptually and theoretically strong but line of argument needs empirical evidence to work out. Though evidence is provided in form of empirical results on three data sets, the baselines remain unclear. This problem need to be solved before publication would be OK (could be straight forward to do so) ", "strength_and_weaknesses": "", "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": "93BwxnGPVPH", "reviewer": "Reviewer_E4u9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "**List strong and weak points of the paper. Be as comprehensive as possible.**\n\n**Pros:**\n\n* Generally, the paper is well written and easy to grasp the underlying ideas and concepts except how the data sampling works (see questions).\n* The intorduction makes it very clear what the problem is this paper is trying to solve. (see additional feedback)\n* A strength of Section 2+3 is that it bundles the theoretical formulas with intuitions in natural language, which makes it very clear at any time what the author trying to achieve or show.\n\n**Cons:**\n\n* While the generated regression example is great to gain intuitions on how OSL works and the influence of its hyperparameters, it's difficult to draw conclusions in regard to \"real\" regression problems. (see question)\n* The proposed concept of the mapping rank seems to not account for label noise explicitly - but I would guess that in the presence of label noise there could be a rank > 1 even though there is only one sensible target function? \n* The experimental evaluation appears to be rather specific and the baselines appear not directly related to other state of the art approaches. It would probably be a much stronger paper, if the authors showed that the proposed approach improves on some metric that is not specific to this submission\n* The paper do not show training and prediction times for OSL and the other baselines. \n* Minor/Typos:\n  * in the introduction: would prefer to change \"(image, label) pairs\" -> \"image-label pairs\"\n  * in the introduction: \"can correlates\" -> \"can correlate\" or \"correlates\"\n  * last paragraph of the introduction: define PAC before use the abbreviation\n  * first paragraph of Section 6: \"facilicate\" -> \"facilitate\"\n  * page 4 last line: \"objectives 2 3\" -> \"objectives 2 and 3\"\n\n**Clearly state your recommendation (accept or reject) with one or two key reasons for this choice.**\n\nIf the authors can clarify the points below, I vote for accept. The introduced approach OSL solves the problem of allocating data from different domains to their model. Currently, we often see very over-parametrized models that try to solve this implicitly. OSL could present a path to more efficient ML.\n\n**Ask questions you would like answered by the authors to help you clarify your understanding of the paper and provide the additional evidence you need to be confident in your assessment.**\n\n* Did you try at least a multidimensional generated regression? I think it would be interesting to see the method comparison in at least >1-D generated regression, better for a datasets, e.g., form OpenML.\n* Could you clarify how the data sampling mechanism works?\n  * It is still not clear to me whether the dataset X is sampled once or iteratively. \n\n**Provide additional feedback with the aim to improve the paper. Make it clear that these points are here to help, and not necessarily part of your decision assessment.**\n\n* The first paragraph after Definition 1 (introduction) is a bit lengthy. Shortening to its main points (difference between R=1 and R>1, metadata difficult to use for data allocation) could improve clarity\n* Providing more description for Figure 2 and 3, especially, what the three lines show would add clarity\n* You should consider to move the description of the DNNs from appendix to the paper.\n* Providing an overview of training and prediction times of OSL and the baselines could be interesting for some readers.", "summary_of_the_paper": "The paper introduces \"Open-ended Supervised Learning (OSL)\", a method that handles data form multiple domains (open-ended data). OSL leverages an Expectation-Maximization (EM) algorithm to train the \"subjective function\" that allocates models to data domains. The paper presents the theoretical foundations and empirical results in which it outperforms existing baselines for (generated) regression and classification tasks.", "summary_of_the_review": "Interesting approach and novel concept of mapping rank, the experimental evaluation could provide more direct evidence for the value of the contribution. \n\nUpdate after authors‘ response:\nThe authors addressed all points and provided convincing additional experiments, I’m hence increasing my score.", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6FyKaq1o_E", "reviewer": "Reviewer_tMyf", "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": "Strengths of the paper are:\n-  The paper studies the important problem of learning on multiple domains with open-ended data. The proposed approach is novel, simple yet effective, as clearly demonstrated in both the theoretical and experimental results\n- The paper is very well contextualised in the existing literature \n- The paper is very well-written, organised and the claims are sufficiently justified\n\nWeaknesses of the paper are:\n- A few aspect are not entirely clear in the writing of the paper. For example, in page 3 it is mentioned that \"In the above setting, an episodic sample number parameter n is introduced to maintain the local consistency of data, implicitly assuming that we are able to sample a size-n data batch at a time from each domain.\" - does this mean that at each time all domains should have corresponding data batches or that each domain is sampled sequentially one after the other? Please clarify\n- There are some typos in the paper, e.g. Section 2.4 page 4", "summary_of_the_paper": "This paper proposes a framework for open-ended data by learning a subjective functions that allows to represent multiple domains without interference. The framework works in two stages: 1) evaluating a set of candidate hypotheses for each domain using a batch of data for that domain, 2) training the hypothesis with the smallest error  for each domain. The paper also proposes two new evaluation metrics, one to determine the error of the subjective function and one for calculating the model error in domain prediction. The authors provide both theoretical and experimental analyses of the proposed framework. In terms of theoretical analyses, the authors provide some guarantees in terms of learnability and generalisation error. In terms of experimental results, the authors test both regression and classification tasks with data of multiple labels and hierarchical labels. Comparisons to other approaches such as ProbCon, Pseudo-L and LabelProp in Colored MNIST, CIFAR-100 and Fashion Product Images datasets demonstrate gains of the proposed approach versus counterparts. ", "summary_of_the_review": "I find this paper very interesting. The proposed approach is novel, yet simple, and clearly works well for the problem of learning from open-ended data. I would recommend to accept this paper. ", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: Two reviewers increased their scores after considering the responses from the authors, and all reviewers are somewhat positive. However, the increased scores are still 6 only, and as the area chair, I have concerns about the foundations of this research.

The authors write "there is no off-the-shelf baseline that can automatically disentangle the data from different domains in the open-ended regression setting." This is not true for the standard situation of a mixture of regression lines, as in Section 4.1. Completely standard EM (not necessarily hard EM) will solve this problem, as long as the individual lines (sinusoids etc.) can be represented easily by the EM components. Another standard method that should be another baseline is a mixture-of-experts neural network. 

One thing that EM cannot handle is learning the number of components in a mixture model, as in learning the _k_ in _k_-means. To the extent that "open-ended" here refers to a new approach for this problem, with mathematical guarantees, it is interesting. But this point of view needs more explanation.

The paper begins "A hallmark of general intelligence is the ability of handling open-ended environments, which roughly means complex, diverse environments with no manual task specification." If there is one aspect of natural environments that is crucial and fundamental, it is the presence of noise. However, starting theoretically with Definition 1 and empirically with Section 4.1, the authors work in a world of deterministic functions. This mismatch undermines the conceptual significance of the paper.

Perhaps because of the universality of noise, the authors do not present a real-world dataset or task for which the OSL method is directly natural or applicable. Rather, they impose restricted specifications on datasets such as MNIST and introduce metrics that are novel, hence hardly natural, undermining the empirical significance of the paper.
Decision: Reject