No Free Delivery Service: Epistemic limits of passive data collection in complex social systems
Authors: Maximilian Nickel
Venue: NeurIPS 2024 poster (2024)
Keywords: validity
model validation
complex systems
epistemology
scaling
large language models
recommender systems
Primary area: evaluation
TL;DR: Formal impossibility results for model validation in key AI tasks such as recommender systems and LLM reasoning if they require passive data collection from complex social systems.

Abstract: Rapid model validation via the train-test paradigm has been a key driver for the breathtaking progress in machine learning and AI. However, modern AI systems often depend on a combination of tasks and data collection practices that violate all assumptions ensuring test validity. Yet, without rigorous model validation we cannot ensure the intended outcomes of deployed AI systems, including positive social impact, nor continue to advance AI research in a scientiﬁcally sound way. In this paper, I will show that for widely considered inference settings in complex social systems the train-test paradigm does not only lack a justiﬁcation but is indeed invalid for any risk estimator, including counterfactual and causal estimators, with high probability. These formal impossibility results highlight a fundamental epistemic issue, i.e., that for key tasks in modern AI we cannot know whether models are valid under current data collection practices. Importantly, this includes variants of both recommender systems and reasoning via large language models, and neither naïve scaling nor limited benchmarks are suited to address this issue. I am illustrating these results via the widely used MovieLens benchmark and conclude by discussing the implications of these results for AI in social systems, including possible remedies such as participatory data curation and open science.

No free delivery service
Epistemic limits of passive data collection in complex social systems
Maximilian Nickel FAIR, Meta New York, NY maxn@meta com
Abstract
Rapid model validation via the train-test paradigm has been a key driver for the breathtaking progress in machine learning and Al. However, modern AI systems often depend on a combination of tasks and data collection practices that violate all assumptions ensuring test validity. Yet, without rigorous model validation we cannot ensure the intended outcomes of deployed Al systems, including positive continue advance Al research in scientifically sound way. In this paper, I will show that for widely considered inference settings in complex social systems the train-test paradigm does not only lack a justification but is indeed invalid for any risk estimator, including counterfactual and causal estimators, with high probability. These formal impossibility results highlight a fundamental epistemic issue, i.e., that for key tasks in modern AI we cannot know whether models are valid under current data collection practices. Importantly, this includes variants of both recommender systems and reasoning via large language models, and neither naïve scaling nor limited benchmarks are suited to address this issue. am illustrating these results via the widely used MOVIELENS benchmark and conclude by discussing the implications of these results for Al in social systems, including possible remedies such as participatory data curation and open science.
social impact,
Assumptions
based
Samples
based on
Model validation Ry a1 1/al <e)
Sample locations
x3
Figure I: Test validity complex systems. Given assumptions target distribution T, data set S" from a sampling distribution S. and quality metric 0, an inference setting test-valid if the difference between 0 and the true risk I. fh
can he bounded over the distribution of all possible worlds f ~ consistent with (A, D).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Introduction
Model validation, long taken to be "solved" via the train-test paradigm, has become one of the central challenges in modern machine learning and artificial intelligence. In unison with the dramatic increase of their capabilities, AI systems are now supposed to solve tasks of vastly expanded scope, including potentially Al-complete tasks such as open domain question answering, autonomous decision making, and ultimately, artificial general intelligence. Even before the recent triumphs of large language models and deep learning, Anderson [3] proclaimed "the end of theory" and the scientific method being obsolete due to the wonders of big data, large-scale computing, and data mining. At the same time, it is entirely unclear how rigorously evaluate the quality of models for these ambitious tasks. This lack of proper evaluation can then materialize in persistent issues of deployed systems related to generalization, e.g., hallucination [30], -il-of--distrbuuiinn generalization [39], fairness [6], and generalization to the long-tail [23, 24]. Importantly, these issues do not only affect the accuracy of models in a vacuum, but can also affect their social impact if they are deployed in consequential social contexts [16]. In this paper. aim to connect the former developments with the latter issues through the lens of epistemology. More concretely, ask:
Research Question 1. Given the ambitious tasks that we ask AI systems to solve and given how we currently collect data, can we know whether a model performs well for these tasks?
Answering RQ positively is central not only for the deployment of machine learning systems, but also for scientific progress within artificial intelligence itself. After all, knowledge of model's quality is a prerequisite to detect generalization issues and develop improved models. In deployed systems, a model's predictions are useless as good as they might be without knowing that they are, in fact, reliable. In social systems, where the consequences of model errors can be severe, having this knowledge is of even greater importance. Hence, the epistemic question of this work gets to the heart of various debates surrounding AI and its capabilities: How can we understand and measure the true capabilities of modern AI systems, which are so very impressive and yet lacking in fundamental ways at the same time [11]? What can we know about the quality of our models? Are our benchmarks suited to give insights into the intended tasks or do they project false image of quality? How can we develop systems such that they work for everyone? Will naive scaling solve all these problems or do we need to invest into entirely new approaches for evaluation within the scope of modern AI?
A prerequisite to answering RQ I positively is the validity of model validation: Without model validation we can not know wether a model is good or bad and without a valid model validation procedure we can not attain this knowledge. The almost exclusively used method for model validation in machine learning and Al is the ubiquitous train-test paradigm, i.e., the practice of estimating the generalization performance of model on a test set distinct from the training set. Arguably, much of the breathtaking progress in machine learning has been driven by the success of this single experimental paradigm as it allows for the rapid validation and, therefore, improvement of models [10]. However, it is crucial to note that the train-fest paradigm inherently an inductive method that aims to infer, not measure, the generalization error of a model from its етrоr test set. It is well known dating back at least to Hume [28, 29] and formalized in the context of machine learning by Wolpert [68] - that it is not possible to justify the validity of such inductive inferences without further assumptions. This raises the question: is the train-test paradigm still valid for the combination of tasks and data sets considered in modern AI and under what assumptions is this the case?
Importantly, such assumptions should be minimal in terms of ontological commitments, i.e., meet ontological parsimony (or minimality), since (a) model validation results can not provide insights about validity in the real world if they are contingent on strong ontological assumptions (b) any assumptions that are required to ensure the validity of model validation can not be validated through the same method without circular reasoning. In traditional machine learning settings, these ontological commitments are placed entirely on the data collection process and, such, the train-test paradigm is indeed suitable to validate any model assumption outside the data collection process. More concretely, under active data collection, i.c., when actively control the data collection process, we can create large enough test sets that are (approximately) sampled i.i.d. from the target distribution. Under these conditions, it is well known that the train-test paradigm allows us to validate models simply via their performance on this test set without making any further ontological commitments. This property the beauty of the train-test paradigm and what makes it valuable and successful.
However, domains in modern machine learning have become far too large to be covered via data sets in this active and controlled manner- the required effort would be prohibitively difficult and costly.

---

In lieu, passive data collection has become the predominant way to create data sets for modern Al systems. Here, data is collected without intervention from some social system that generates data within the domain of interest. For instance, rather than meticulously collecting independent samples from all possible facts in domain, training and validation corpora for QA models are gathered from what has been published on the internet. Similarly, preferences of users are collected over items that a recommender system has pre-selected, rather than sampling them i.id. over all possible user-item pairs. Importantly, these sample generating systems need not correspond to the target data generating process, have their own internal dynamics, and are driven by complex interactions of their parts and social processes, e.g., well-known phenomena such popularity bias [1], homophily [22, 37], or feedback loops [14].
Hence, I will ground RQ 1 in these conditions of current machine learning practice: Under passive data collection from a social system, can model validation be valid or not? To formalize the social systems with which an Al system interacts, am taking complex systems perspective and describe them as networks with well-established sampling biases and degree distributions. For these properties, I will show how they affect necessary conditions of test validity. These results can also be understood as a strengthening of the seminal No Free Lunch (NFL) theorems for supervised learning [68] in the context of social systems. While the NFL theorems show the impossibility of an assumption-free general purpose learning algorithm, a common criticism is that they need to assume an induction- hostile universe, i.e., full ontological neutrality [60]. In practice, where assuming reasonably induction induetion-riennll universe is common, the NFL theorems have had therefore limited impact. In contrast, the results of this work are grounded in current machine learning practice and considerably stronger: Even for non-trivial assumptions of an induction- -aduetloo-friendly universe, model validation can be shown to be invalid when data is collected passively in social systems. In other words, there is no free delivery service of data for model validation in complex social systems. To discuss the above results, I will provide a synthesis of results from learning theory, social science, and complex systems and combine them with new theoretical and empirical results on the validity of model validation. In partieular, the main contributions of this paper are follows:
Theorem 1 (Informal). For passively collected data in complex social systems the train-test paradigm cannot be valid under ontological parsimony for the vast majority of the system. This includes widely considered variants of recommender systems and question answering.
Corollary 2 (Informal). Naive scaling and limited benchmarks are prohibitively inefficient to address theorem and therefore not suited to attain test validity in these scenarios.
Supporting evidence. Theoretical results are supported via experiments on the popular MOVIE- LENS benchmark where widely considered recommendation tasks are shown to be test-invalid.
The remainder of this paper proceeds follows: Sections 2 and formalize passive data collection in social systems and connect it to test validity. Section 4 develops theorem 1, corollary 2, and supporting evidence. Sections 5 and 6 discuss related work and implications for Al in social systems.
2 Passive data collection and inference tasks in social systems
To construct validation data sets for large-scale domains, there exist currently two main practical approaches: (i) "scaling", ie., indiscriminately collecting as much data as possible from some domain and (ii) manually constructing benchmarks of limited size that probe certain subareas of the domain. In the following, I will focus on formalizing
(i) as passive data collection from social systems. Section 4 will then show that neither (i) (ii) can be solutions to the issues of this paper.
In sociology, a social system is often considered pattern of networked interactions that exists between individuals, groups, institutions [44]. For the purposes of this paper, I will consider social system to be a pair (f.S) where f X - y is a possible world of interactions such that X = X1 X x... X X, denotes the domain of interactions, y denotes the set of outcomes (or labels) of an interaction, and X + |0. 1] denotes the sampling distribution of the system over interactions. Within this framework, passive data collection refers sampling directly from S. This is in contrast active data collection where we would aim to sample directly from the target distribution T T - [0, 1] for inference task, e.g., via simple random sampling, stratified sampling, etc.
In complex social systems, S is driven by social processes that lead to two characteristic properties of samples: (i) they are biased and (ii) they follow heavy-tailed power-law distributions. The carliest
3

---

Table 1: Inference settings based passive data collection in complex social systems.
Domain X
Possible world f
Sample distribution S
Target distribution T
Recommender
User preferences
Probability user interacting with item, heavy-tailed and
Uniform,
systems
(r = 1/|U x
Symbolic reasoning
8 Px
Truth value of factoids
Probability observing factoid, heavy-tailed in P, and
Uniform. Pr(s.p.0 0) :t/p://///////// x
Reasoning- FB15k-237
Pepprion sooto
Prospen en (oo seale)
Seciale Bo
2214
10
Osscovations
Observations lsggrogaate over presicatest
(a) Heavy-tailed samples
(b) Reasoning
Figure 2: (a) Heavy-tailed samples in recommender and reasoning datasets. (b) Symbolic reasoning via LLMs. To validate reasoning capabilities of LLMs, natural language has to be mapped to logical knowledge representations. This shows that validation reasoning in LLMs is subject to the results of this paper. See also fig. 6b and supp. G.I.
work on (ii) is due to Simon [56], and has independently been discovered in multiple contexts, In fact, (ii) can often be understood as a consequence of (i), e.g., popularity bias leading to power-law distributions in social networks [5, 48]. See also supp. C for further discussion of these properties.
In the remainder, I will therefore focus on the presence of heavy-tailed distributions in 8 to understand how this ubiquitous property of social systems affects test validity. For this purpose, I will first introduce the concept of a sample graph, i.e., the observed interactions that we receive from S:
Definition 1 (Sample graph). A data set ~ S c X[ x X2 of observed interactions induces a bipartite sample graph G = (21, [2, 8) between entities of X, and X2 where an edge indicates that the corresponding interaction has been observed. In the following, will use S and G interchangeably.
For higher arity relations, definition can easily be generalized to hypergraphs. For simplicity, I will focus on bipartite graphs in the following. In sample graphs, the heavy-tailed property of complex systems materializes then through their degree distribution. While the exact nature of these distributions is disputed [13], I will follow Voitalov et al. [64] and assume that node degrees in 8 follow a regularly-varyio power-law distribution. Based on this observation, passive data in complex social systems will then refer to the following:
Definition 2 (Passive data in complex social systems). Let 8 ~ S be a sample graph drawn from sampling distribution S. Let Kj, K2 denote random variables that model the degree distribution in S of nodes in X1 and X, respectively. For passively collected data from complex social systems, I will then assume that K,, K2 follow regularly-varying power-law distributions. i.c.
P(K k) (k)k and P(K2 k) uz(k)k
where a; 0 are the tail indices and i; are slowly varying functions such that limy u(rx)/u(x) = for any r > O. Higher arity relations are defined analogously. Next, will show how passive data in social systems materializes in key inference settings (see also table 1).
Example 1 (Recommender Systems). Recommender systems are concerned with inferring the true preferences of a user over all items from set of revealed preferences sampled from S. As such they are a typical example for (f.S) where the target distribution T corresponds the uniform distribution over all possible interactions. Importantly, S is typically influenced by social processes and sampling bias as well as heavy-tailed distributions are well documented in recommender systems, For instance, an important factor for sampling biases are feedback loops. e.g., that past recommendations influence which recommendations are shown in the future [34, 14]. Another source of sampling bias is user feedback, which is often biased towards items with high ratings [59], as well as popularity bias [1, 48]. Popularity bias leads directly to heavy-tailed distributions in the degree distribution of the sample graph [48, 5]. See also fig. 2a for evidence of this property on MOVIELENS.

---

Example 2 (Symbolic reasoning and QA). Reasoning and question answering over symbolic knowl- edge representations are another key example for (f.S) In this setting, factoids are represented in form of (subject, predicate, object) triples and the task is to infer the truth value for any unknown factoid, i.e., for uniform target distribution T. Importantly, while facts about the world itself do not need to be influenced by social processes, our available knowledge about them, i.e., S, often is. In addition to aspects such as popularity bias, causes for this can range from which questions are studied in science [35, 36), over how data is collected [31]. to who has access to the internet and the ability to contribute to knowledge [67]. Consequently, heavy-tailed distributions are also well-documented in this setting. For instance, Steyvers et al. [61] showed that semantic networks typically follow heavy-tailed degree distributions. Similar distributions have been observed in large-scale knowledge graphs such DBPEDIA [4], YAGO [62], FREEBASE [9]. and WIKIDATA [65]. See also fig. 2a for evidence of this property on FB 5K. Importantly, this setting applies to any reasoning task over factoids in general irrespective of the data representation. For instance, the validation of reasoning capabilities for general purpose question answering in systems such as LLAMA [63, 21] and CHATGPT [47] needs to follow this blueprint. See also fig. 2b for an illustration.
3
Test validity
To answer RQ 1, I will focus the test validity of inference settings, i.e., whether task, assumptions, and data allow for any valid validations at all. For this purpose, I will use a deductive approach: model validation is valid if it is a logical consequence of its assumptions that the difference between its estimate and the true generalization error is bounded with high probability. To formalize this, let f. - y denote functions that map from sample domain X to target domain y. For clarity, I will assume noise-free f and h. Furthermore, let S ~ S = {xx ) denote a data set of m samples drawn from sampling distribution S X [0. 1] and let D {(x. f(x)) x E 8} denote its supervised extension. For notational convenience, I will also write D ~ S" when f is clear from context, In addition, let A S (f f X - y) be the set of all functions from X to y that are consistent with some set of assumptions on f such as being low-rank. Next, note that A and 'D then induce a set of possible worlds as follows:
Definition (Possible worlds). Let A be set of assumptions, D X a set of observations, and f:x - y. The set of possible worlds I is then the set of functions consistent with A and D, i.e.,
I == V(x, y) E D f(x) y)).
Furthermore, I will consider an inference setting (A, D. F) to be set of assumptions A, fixed dataset ~ Smm a target distribution T X + [0, 1] for which we want to make inferences, and an assumed distribution over possible worlds F. Note that if S # T, DD can not be an i.i.d. sample from T. For further details and notation see supps. A and B.
Next, let X be random variable over X and let 6 x y R. of hypothesis with respect to a single world f is then denoted by
R. be positive loss function. The risk
Jh = (x-x)((((xx)
Furthermore, let 0 denote any risk measure of a hypothesis ht on some test set T. For instance, 0 could denote the empirical risk or a re- e-weeghttdd estimator such as the Horviz--hhompsor adjusted empirical risk (see also table 4 in the supp. material). Hence, 0 does not only cover the standard Monte-Carlo estimator for the i.i.d. setting, but also estimators used in counterfactual and causal settings. To determine the test-validity of an inference setting, I am then interested in bounding the difference between the estimated risk (0) and the true risk of h (z).). Importantly, it is necessary to consider the risk of h relative to the distribution F over all possible worlds since no world f F can be excluded based on D) and A. Hence, test validity defined as follows:
Definition& 4 (Test validity). Let f ~ F denote distribution over possible worlds I and let H denote a hypothesis class. Furthermore, 1et L fh denote the risk of hypothesis for target distribution T and possible world f. Let / E R., denote any empirical risk measure of li on test set. Then, (A. D. T, is (e, ---test-vllid (test-invalid) if 6's difference to 4n can (cannot) be bounded accordingly, i.e.,
3K 3h K Py-F(10
T. t) 2 1-6
(e, -test-vivlly
(A, FF
VH 4h E H. PP)==((0
1, 1.1 > 6) > 6.
(6. 5) -est--tiinvl
5

---

The conditions in definition 4 for a valid validation setting are very mild since it requires only a single hypothesis class in which for a single hypothesis has bounded difference to the true risk with high probability. Since invalidity follows directly from validity via complement rule and negation, the conditions for a validation setting to be invalid are strong: For any possible hypothesis class it has to hold that the difference between # and the true risk of all hypotheses can not be bounded with sufficient probability. Importantly, both are statements about an inference setting, i.e., the combination of assumptions, observed data, and target distribution, and not about specific hypothesis (class), Furthermore, note that definition 4 implies realizability with regard to the assumptions: if {f V(x, y)) D f(x) = O A 0, an inference setting is test-invalid since P(O) = 0. However, definition 4 imposes no realizability or any other constraints on K.
Next, note that definition 4 implies straightforward necessary conditions for test validity:
Corollary 1 (Necessary condition for test validity). Let (A., D.T, F.F) be an inference setting, let E: y x --R. be a positive loss function, and let H be a hypothesis class. Furthermore, let 0 E R. be any risk estimate for h. Then, if (A,, D. F) is (c, -e-tevv-vlli,, it must hold that
3H E H : p = FLL fa S c 2 1
Proof sketch. Corollary 1 follows simply via the monotonicity of probability, i.e., it holds that I- 6 s Py-=F(10 - L 1 s E) S &P--F(Ly, E 0). This holds for any risk measure 9, loss E R. and hypothesis h. See supp. D for proof details.
4 Test validity under passive data collection in complex systems
In the following, will provide an overview of the main results as well high-level proof sketches. For clarity, I will consider only binary relations X = X, x X2 and possible worlds over unbounded output domains f x - R. For detailed proofs and discussion, as well extensions to ternary relations and bounded domains, see supps. E to G. To meet ontological parsimony' and get insights into the validity of the train-test paradigm, will focus on being the uniform distribution U and A imposing only minimal assumptions on f.
Next, derive bounds the validity of inference settings in complex social systems, I will represent possible worlds f as partially observed matrices which are constructed as follows:
Definition 5 (Matrix representation). For a function f ;2 x X2 - y over finite sets of size [X,]] = nn and [Xa] n2, its matrix representation F E Ru is given via F,5 = xxx,x) for all (x1,xy) E X, x 2 In the following, I will use and F interchangeably.
Using this matrix representation of a system, I will show in lemma 2 that the train-test paradigm is invalid if the rank of f. i..., the complexity of the system, exceeds the k-connectivity of the sample graph& S and if f is chosen uniformly from F. Here, k-connectivity is defined as follows:
Definition 6 (k-core and k-connectivity). The k-coee (or core of order k) of graph is its maximal subgraph such that all vertices are at least of degree k. A graph is k-connected if and only every vertex is in a core of order at least k.
Lemma 1 (Rank-k underdetermination)) Let A. = (f rank(f) s k). Then, if is not k-connected, the set of possible worlds I forms a non-empty vector space.
Proof sketch. Since S is not k-connected, any f with rank f) k can not be S-isomeric. It then holds via [38, Lemma 5.1] that J, i..., the set of matrices of rank & or less that are consistent with D, form a non-empty vector space. See supp. E for proof details.
In the spirit of Occam's razor, higher ranks of f correspond to more complex possible worlds. Lemma establishes then that if the k-connectivity of S does not match the complexity of the system f. the observations S do not constrain F sufficiently and a randomly chosen possible world can be arbitrarily different the non-observed entries. Via corollary 1, lemma I implies then
See also supp. B.2 for further discussion on the importance of ontological parsimony (minimalityy. 2hhis is trivially extended to higher arity functions using tensor representations. See also supp. G. Note that being in the c-core of 8 is stronger condition than having degree A: A node can be outside the core with degree larger than & if enough of its neighbors are outside the k-core (see also fig. 6c)

---

that k-connectivity is necessary for test validity if C belongs to the broad class of scalar Bregman divergences, i.e., widely used loss functions such as the square loss, the log loss, or the KL-divergence (see also table 5 in the supplementary material).
Lemma 2 (Rank-k k cest-invalidity). Let & be identical to lemma 1, let I be a scalar Bregman divergence, let F be the uniform distribution over I. and let T be the uniform distribution over X. Furthermore, let 0 E R+ be any risk estimator on a test set. Then, if 8 is not k-connected, (A., D. F,F) is test-invalid, i.e., it holds for any E 0 that
VHC E H: Py-=(10 - S e)
Proof sketch. If is not k-connected, F is vector space according to lemma 1. Lemma 2 follows then from corollary 1 for uniformly sampled f IJ and h I via a simple volume argument. For & J. the result follows again from F being a vector space via the generalized Pythagorean theorem for Bregman divergences [20, Eq. 2.3]. See supp. B.2 for proof details.
The consequences of lemma 2 are non-trivial. Under ontological parsimony, it shows that passive data from complex social systems, i... the foundation of basically all large-scale AI tasks, can not be used to validate the quality of models if S T. Clearly, no subset of 8, e.g., cross-validation, can fulfill this task either. Importantly, lemma 2 holds not only for empirical risk, but for any estimator on D, including counterfactual estimators, i.e., methods which are exactly meant to address S # T. This illustrates that lemma 2 is not simply an out-of distribbuiiinno or counterfactual estimation problem. Rather, is caused by a combination of
(S * T) and insufficient data (k- (k-connectivity < rank( Next, I will connect these results to the main result of this work.
Theorem 1 (Test validity in complex social systems). Let (A, F,F) be identical to lemma 2. Furthermore, let 8 STh where S follows power-law distributions such that the degrees of x E Xi in the sample graph S are drawn i..dd from a regularly-varying power-law distribution P( P(deg(.x) k) u(k)k-" ai Farthermore, let n; = |Rai be the size of domain X2. Then, the number V; of nodes in for which test validity holds decreases with a power-law decay in rank( = k, i.e
B[VI S nn((k)k""
Proof sketch. Test validity requires the k-connectivity of S to be greater or equal to rank(f) via lemmas and 2. Hence, only subgraphs where all vertices are at least of degree k can be valid. Theorem 1 follows then via the expected number of nodes with degree at least k in X,, i.e, B[V]] Σxex, ((de((() 2 k).
For heavy-tailed distributions, most nodes will be outside the required k-core for even moderately complex worlds. Hence, theorem 1 shows that the train-test paradigm cannot be valid under ontologi- cal parsimony for the vast majority of nodes in realistic social systems. Table 2 illustrates this using parameters that match the well-known Book Crossing dataset.
An immediate next question is then if the issues raised by theorem can simply be solved by scaling, i.e., by collecting more data from S - or via manually constructed benchmarks such as BigBench [58] to extrapolate from their results to the risk on T. Corollary 2 answers both questions via lemma (see supp. H for a detailed discussion and proof): (i) For scaling, we can ask how many draws from S would be necessary such that all nodes are within the k-core of S with high probability, i... how many samples are needed until arriving at a valid test setting. While there exists easily computable solution to this problem, we can compute a (weak) lower bound by asking how many samples from S are needed to sample random node in X, once. (ii) For benchmarks, we can ask how many nodes would need at least one additional data point to arrive at a valid test setting, i.e., how much manual data collection is at least needed create a benchmark that extrapolates T.
Table 2: Inefficiency of scaling and benchmarks; validity coverage for the Pareto distribution.
Scaling
Benchmarks
Xmun
[3]]
Samples needed to increase k-core of random node
Nodes with less than 100 obscrvations
2.5
5
10"
Ei-u [7;] > (120)2))**
/(xx"t //ax//
2 10
E[M]
[2] (x)")
9.9 10th
Book Crossing [69]
Amin
[X]]
Fraction of users with large enough degrees such that train-test measures and inferences are valid Rank 20: 11.3%,
2.38
8
10
Rank 8: 100%, Rank 10: 58.8%.
Rank 100: 0.2%
7

---

7-0
68
0.1
Uthel
Drginer
Proporton
R3
Hoult
109 Nevertt
0.2
034
3.77 U02
00
14, "A D'rece Ang
(a) eCDF of Maximum NAE
(b) eCDF of Pairwise NAF
(c) k-core per occupation
Bio. Sex
Decupation
0.90
2.00
0.54
5:91
0.33
0.50
0.25
294
2.94
0.55
6.97
0.27
2.97
Proportin of spens
Comploity
2
0.14
0.25
022
0.4
0.44
0.45
D.4
0:33
0.33
0.38
0.3
0.22
2:21
0
B14
0119
821
421
6:1
412
412
D25
022
0.23
0322
1123
2:38
U44 2/22
144
00
Dekemae
Engreee
Proganmeet
Temnsoie
(d) vest-validity per demographic group and model complexity
Figure 3: MOVIELENS 100k experiments (a) Empirical CDF (eCDF) of maximum NAE over possible worlds. Area over the curve (expected error) shaded. (b) eCDF of NAE for pairs of possible worlds. (c) cCDF k-coreper demographic group. (d) Proportion of users for which test- rest-validity holds relative to the rank of f.
Corollary 2 (Inefficiency of scaling and benchmarks). Let (A, D, T.F) and S be identical to theo- rem I. Furthermore, lel (i) Ti denote the expected number of samples from S until node x; E X is sampled, and let (ū) j denote the number of nodes in Xj with less then k samples. Then, T; scales at least polynomially and J scales lineraly in the size the domain [X]. Specifically,
BI-U [T]) (121/2) (11l22)a+//((a))))) (axx and B[N,]
[20 - (Xmin/
Clearly, sampling from S is highly inefficient to overcome the issues raised by theorem since (i) it is extremely difficult to get successful samples from the heavy tail (rare events) and (ii) covering all nodes outside sufficiently large k-cores in selective benchmarks is prohibitively expensive. See also table 2 for examples of these aspects for typical distributions in complex social systems.
Experimental evidence To illustrate the real consequences of the previous theoretical results, will now provide experimental evidence based on the MOVIELENS 100k dataset [27], critical benchmark that has, for years, been hidely-used recommender systems research. As predicted by lemma 2, I will show that there exist possible worlds of low complexity that all explain the observed data equally well but are widely different on the unobserved data. Hence, any quality metric that is inferred on this benchmark,
subsets of can not be informative about the true generalization error. For this purpose, I fit 100 matrices of rank k = 50 to the observed data D. All matrices, or possible worlds, fit the observed data and rank constraint with error below 10-3 and 10-2, respectively. See supp. I.1 for details. For pair of possible worlds (f.f') compute then the normalized absolute error (NAE) for each unobserved entry (i & 8 via NAE(Si, f',) = Ifij - ff fmmnn. This informs us about how different pairs of possible worlds can on the unobserved data. Figures 3a and 3b shows the empirical CDF (eCDF) of the NAE over unobserved entries for such pairwise comparisons
possible worlds as well as the worst-case over all worlds per entry. From fig. 3a, it can be seen that the worst case error across possible worlds per entry is substantial for the vast majority of unobserved entries. For instance, for 50% entries the NAE is above 77% of the worst case eиror. For arbitrary pairs of possible worlds, the situation is similar, where, depending particular pair of worlds, the NAE is between 23% to 49% for 50% of entries. Furthermore, the area over the eCDF curves in fig. 3b corresponds directly to the risk for pair of possible worlds and is again substantial for all pairs (see supp. 1.2 for details). Since any possible world can be the "true" world this shows again that the test error for any subset of this benchmark can not be informative for the true generalization error this task.
the
In addition to the NAE, fig. 3c shows the cumulative distribution of users within cores of order & per demographic group for MOVIELENS 100k. can be seen that the cumulative distribution can vary significantly between different demographics. For instance, while only 25% of "homemakers" are in
8

---

a k-core larger than 50, 40% of "technicians" are in a k-core larger than 80. It follows from lemma 2, that test-validity will therefore also vary significantly between demographic groups (if we assume that there are no significant differences in the complexity of preferences between groups). Figure 3d illustrates this point by showing the proportion of users for which test-validity holds relative to the rank of model. It can be seen that there exist clear differences already for moderately complex worlds. For instance, for a model of rank 60, test-validity would hold for 67% of "technicians" while it would only hold for 14% of "homemakers" Clearly, this has important implications for fairness, bias, and whether recommender systems work for everyone.
5 Related work
The no-free-lunch theorems for machine learning [68, 60] share important similarities to this work as both consider the expected risk over possible worlds. However, the results in this paper are stronger and directly applicable to current machine learning practice. While the NFL theorems consider the performance over all possible worlds without any restrictions - an assumption that is too restrictive in most instances - the results of this paper show that even for relatively strong assumptions about the set of possible worlds, e.g., low-rank structures, valid model validation is not generally possible for passive data collection in complex social systems. In motivation, this paper is also related to the works [19, 7, 25, 54, 41, 66] which study outcomes of underspecification in ML pipelines, model multiplicity and Rashomon sets. In the restricted context of personalized prediction, Monteiro Paes et al. [46]. discusses related limits to testing and estimation. Schaeffer et al. [52] discuss whether seemingly emergent capabilities of LLMs rather a result of insufficient metrics. In statistics, Meng [43] analyzed a scaling-related question similar to this paper: Given a carefully collected survey with low response rate (small data) or large, self-reported dataset without data curation (big data), which dataset should one trust more to estimate population averages? Outside machine learning, validity theory has long history in fields such as psychology and sociology. Here, test validity is considered a measure of the degree to which a test measures what it is intended to measure [18] and has been studied extensively in the context of psychological tests [45] and educational testing [32]. Increasingly, these notions of validity, have also been considered in machine learning [17, 51, 50, 2].
With regard to technical tools, this paper is also closely related to prior work in matrix completion. For instance, [33] studied the problem of unique and finite completability of matrices and derived similar k-core related bounds using determinantal varieties and algebraic geometry. Srebro al. [57] studied the problem of matrix completion based on non-uniform samples such as power-laws but assume that S = T. Meka al. [42] focused on power-law samples for S # T and, consistent with this work, require at least & samples per row and column to guarantee completability of a rank-k matrix. Cheng al. [15] derive similar results based on graph k-connectivity. Related non-i.i.d. observations, [38] developed framework to provide necessary conditions for matrix completion under deterministic sampling. Lemma 1 is based on these results. Different to these prior works, I provide formal impossibility results for test validity based on passive data in complex social systems. This allows to gain rigorous insights into the epistemic limits of what we can know based on this form of data collection. See also supp. J for further related work.
Discussion
The results in this paper provide new insights into the validity of the train-test paradigm when data is passively collected from complex social systems. In particular, have shown that there exists no free delivery service of data that allows for test validity on global scale in this setting. While valid inferences are possible with respect to the sampling distribution S and within high k-cores, they are unlikely if T extends to the entirety of the system. Hence, test validity depends on the interplay between task (T), the complexity of the system (A), and the k- k-connectivity of the sample graph (8) underlying the observed data (D), what is a combinatorial property of the data. These results are attained by establishing novel necessary conditions for which validation is possible. As AI systems are increasingly applied in conditions for which sufficient conditions of validity are difficult to guarantee, understanding such minimal conditions can provide guidelines into developing better and more robust systems. Importantly, it can help to demarcate inference goals that are not meaningful from ones that are attainable. It helps to understand the limits of what we can know and
9

---

which questions are futile to ask. This work provides a first step in this direction by establishing such epistemic limits of AI in complex social systems.
Furthermore, have shown that the sub-system for which valid inferences are possible shrinks rapidly with the complexity of the system and that na've application of the scaling paradigm is prohibitively inefficient to overcome these validity issues. As a consequence, solving many complex AI tasks are unlikely to come for free through scaling or for cheap through extrapolating from limited small- scale benchmarks. Instead, there exists an inherent trade-off between data quality, quantity, and task complexity. If we want to avoid asking AI systems to solve simpler tasks (e.g. non-out-of-on -fdittirbbuuion or smaller scope), new data curation efforts are likely needed. Due to the substantial amount of data that would have be collected, centralized data collection is often infeasible to overcome the validity issues of this paper. Instead, decentralized methods such as participatory data curation could provide a way forward. This aligns with insights from fairness which also highlight the need for participatory methods in data collection [31]. Similar arguments apply to the importance of open science and open-source models in this context.
Importantly, the theoretical results of this paper also provide direct insights into how to improve data collection for model validation via its k-core conditions. In particular, lemma and corollary imply two clear objectives for targeted data collection: (a) collecting data points that increase the k-connectivity of the sample graph and (b) collecting data points that increase the size of the -frre of the sample graph, where rank(f) is the complexity of the world that we want to assume. Pursuing (a) would increase the complexity of the world that can be assumed such that model validation is still valid for the entire sample graph, while pursuing (b) would increase the size of the subgraph for which a rank (f) = k assumption would still yield valid model validation. Hence, both objectives are based on the k-core conditions of this work and can be computed from given sample graph. Creating new mechanisms for efficient data collection based on these insights is therefore very promising avenue for future work.
Acknowledgments
I gratefully acknowledge the valuable feedback from Léon Bottou, Smitha Milli, Tina Eliassi-Rad, Mark Tygert, and anonymous reviewers which all helped to improve various versions of this paper.
References
[ Himan Abdollahpouri. "Popularity bias in ranking and recommendation". In: Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society. 2019, pp. 529-530.
[2] Rediet Abebe. Algorithhs on the Bench: Examining Validity of ML Systems in the Public Sphere. 2022.
[3] Chris Anderson. The End of Theory: The Data Deluge Makes the Scientific Method Obsolete, en. June 23, 2008. (Visited on 02/27/2024).
[4] Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. "DBpedia: A Nucleus for a Web of Open Data". In: The Semantic Web. Springer Berlin Heidelberg. 2007, pp. 722-735.
[5] Albert-LászIó Barabási and Réka Albert. "Emergence of scaling in random networks". In: Science 286 (5439 1999), pp. 509-512.
[6] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness and Machine Learning: Limitations and Opportunities. en. MIT Press, Dec. 19, 2023. 340 pp.
[7] Emily Black, Manish Raghavan, and Solon Barocas. "Model Multiplicity: Opportunities, Concerns, and Solutions". In: Proceedings of the 2022 ACM Conference Fairness, Accountability, and Transparency (Scoul, Republic of Korea). FAceT '22. New York, NY, USA: Association for Computing Machinery, June 20, 2022, pp. 850-863. (Visited on 02/27/2024).
[8] Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig, Stephan Hoyer, Felipe Jinares-Lópezz Fabian Pedregosa, and Jcan-Philippe Vert. "Ffffcient and Modular Implicit Differentiation" ". In: arXiv preprint 105. 15183 (2021).
[9] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. "Freebasc: a collaboratively created graph database for structuring human knowledge". " In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data (Vancouver, Canada). SIGMOD '08. New York, NY, USA: Association for Computing Machinery, June 9, 2008, pp. 1247-1250. (Visited on 12/3 12/222))33.
[10] Léon Bottou. Two big challenges in machine learning. 2015.
10

---

[1]]
Léon Bottou and Bernhard Schölkopf. "Borges and AI". In: arXiv [cs.CL] (Sept. 27, 2023).
[12] James Bradhury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclau- rin, George Necula, Adam Paszke, Jake VanderPlas, Skye Lonnderman-Minng, and Qiao Zhang. JAX: composable transformations of Python programs. Comp. software. Version 0.3.13. 2018 [13] Anna D Broido and Aaron Clauset. "Scale-free networks are rare". In: Nat. Commun. 10 (1 2019).
pp. 1-10.
[14] Allison J B Chaney, Brandon M Stewart, and Barbara E Engelhardt. "How algorithmic confounding in recommendation systems increases homogeneity and decreases utility". Proceedings of the 12th ACM conference on recommender systems. 2018, pp. 224 232.
[15] Dehua Cheng, Natali Ruchansky, and Yan Liu. "Matrix completability analysis via graph k-connectivity". In: Proceedings of the Twenty-Fii International Conference on Artificial Intelligence and Statistics. Ed. by Amos Storkey and Fernando Perez-Crus Vol. 84. Proceedings of Machine Learning Research. PMLR, 2018. pp.
[16] Lu Cheng. Kush R Varshney, and Huan Liu. "Socially Responsible AI Algorithms: Issues, Purposes, and Challenges". en. In: jair 71 (Aug. 28, 2021), pp. 1137-1181. (Visited 12/25/2023).
[17] Amanda Coston, Anna Kawakami. Haiyi Zhu, Ken Holstein, and Hoda Heidari. "A validity perspective evaluating the justified use of data-driven decision-making algorithms". In: arXiv LG) (June 29, 2022). (Visited on 1/01/20024.
[18] Lee J Cronbach and Paul E Meehl. "Construct validity in psychological tests". In: Psychol. Bull. 52 (4
1955). p. 281.
[19] Alexander D' A'mour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Fisenstein, Matthew Hoffman, Farhad Hormozdiari, Neil Houlshy, Shaobo Hou, Ghassen Jerfel, Alan Karthikesalingam, Mario Lucic, Yian Ma, Cory Mcl.can, Diana Mincu, Akinori Mitani, Andrea Montanari, Zachary Nado, Vivek Natarajan. Christopher Nielson, Thomas F Osborne, Rajiv Raman, Kim Ramasamy, Rory Sayres, Jessica Schrouff. Martin Seneviratne. Shannon Sequeira, Harini Suresh, Victor Veitch. Max Vladymyrov. Xuezhi Wang. Kellie Webster, Steve Yadlowsky. Tacdong Yun, Xiaohua Zhai and D Sculley. "Underspeciffcation presents challenges for credibility in modern machine learning". . In: J. Mach. Learn. Res. 23 (1 Jan. 1, 2022), pp. 10237-10297. [20] Inderjit $ Dhillon and Joel A Tropp. "Matrix nearness problems with Bregman divergences". In: SIAM J. Matrix Anal. Appl. 29 (4 Jan. 2008), pp. 1146.
[21] Abhimanyu Dubey et al. "The Llama 3 herd of models". In: arXiv [cs.Al] (July 31, 2024). (Visited on
10/30/2024).
[22] Francesco Fabbri, Francesco Bonchi, Ludovico Boratto, and Carlos Castillo. "The Effect of Homophily Disparate Visibility of Minorities in People Recommender Systems". en. In: JCWSM 14 (May 26, 2020), pp. 165-175. (Visited 12/25/2023).
[23] Vitaly Feldman. "Docs learning require memorization? a short tale about a long tail". en. In: Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing. STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing (Chicago IL USA). New York, NY, USA: ACM, June 22, 2020. (Visited on 04/28/2024).
[24] Vitaly Feldman and Chiyuan Zhang. "What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation". In: Advances in Neural Information Processing Systems. Ed. by H Larochelle, M Ranzato, R Hadsell, M F Balcan, and H Lin. Vol. 33. Curran Associates, Inc., 2020, pp. 2881-2891.
[25] Aaron Fisher, C Rudin, and F Dominici. "All models are wrong, but many useful: Learning variable's importance by studying entire class of prediction models simultaneously". In: J. Mach. Learn. Res. 20 (177 Jan. 4, 2018), pp. 1-81. (Visited on 04/28/2024).
[26]
Philippe Flajolet, Danièle Gardy, and Loys Thimonier. "Birthday paradox, coupon collectors, caching algorithms and self-organizing search". en. In: Discrete Appl. Math. 39 (3 Nov. 11, 1992), pp. 207-229.
[27] F Maxwell Harper and Joseph A Konstan. "The MovieLens Datasets: History and Context". In: ACM Trans. Interact. Intell. Syst. 5 (4 Dec. 22, 2015), pp. 1-19.
[28]
David Hume. Treatise of Human Nature (I) of the understanding. Vol. 1. 1739. (Visited on 12/21/2023).
[29]
David Hume. An Enquiry Concerning Human Understanding. 1748.
[30] Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Yejin Bang, Wenliang Dai, Andrea Madotto, and Pascale Fung. "Survey of Hallucination in Natural Language Generation" In:
arviv /cs.CL) CLJ (Feb. 8, 2022).
[31] Eun Seo Jo and Timnit Gebru. "Lessons from Archives: Strategies for Collecting Sociocultural Data in Machine Learning". In: Proceedings of the 2020 Conference on Fairness, Accountability, and Trans- parency (Barcelona, Spain). FAT* '20. New York, NY, USA: Association for Computing Machinery, 2020, pp. 306-316.
[32] Michael T Kane. "Validating the interpretations and uses of test scores". en. In: J. Educ. Meas. 50 (1 Mar. 2013). pp. 1-73.
11

---

[33]
Franz J Kiraly. Louis Theran. and Ryota Tomioka. "The algebraic combinatorial approach for low-rank matrix completion" In: J. Mach. Learn. Res. 16 (1 2015), pp. 1391-1436.
[34]
Karl Krauth, Yixin Wang, and Michael I Jordan. "Breaking Feedback Loops in Recommender Systems with Causal Inference". In: arXiv preprint arXiv:2207. 01616 (2022).
[35] Thomas S Kuhn. The structure of scientific revolutions. en. 2nd Edition. Chicago, IL: University of Chicago Press, Apr. 1, 1970. 210 pp.
[36] Hugh Lacey. Is Science Value Free?: Values and Scientific Understanding. Taylor Francis, 2005. (Visited 01/24/2024).
[37] David Liu, Virginie Do, Nicolas Usunier, and Maximilian Nickel. "Group fairness without demographics using social networks". In: Proceedings of the 2023 ACM Conference on Fairness, Accountability, and Transparency. ACM Conference Faimess,, Accountability, and Transparency (Chicago. IL. USA, 2023). FAccT '23. New York. NY, USA: Association for Computing Machinery, June 12, 2023, pp. 1432- 1449. (Visited on 04/28/2024).
[38] Guangcan Liu, Qingshan Liu, Xiao Xiao-Tong Yuan, and Meng Wang. "Matrix completion with deterministic
sampling: Theories and methods". : In: IEEE Trans. Pattern Anal. Mach. Intell. 43 (2 2019), pp. 549-5666
[39] Jiashuo Liu, Zheyan Shen, Yue He, Xingxuan Zhang. Renzhe Xu, Han Yu, and Peng Cui. "Towards
Out-Of-Distribttion Generalization: A Survey". In: arXiv [cs.LG] (Aug. 31, 2021).
[40] Benjamin M Marlin and Richard S Zemel. "Collaborative prediction and ranking with non-random missing data". In: Proceedings of the third ACM conference on Recommender systems. 2009, pp. 5-12. [41] Charles T Marx. Flavio du Pin Calmon, and Berk Ustun. "Predictive Multiplicity in Classification". In:
arXiv [cs (Sept. 14, 2019).
[42] Raghu Meka, Prateek Jain, and Inderjit Dhillon. "Matrix Completion from Power-Law Distributed Samples" In: Advances in Neural Information Processing Systems. Ed. by Y Bengio, D Schuurmans, Lafferty, C Williams, and A Culotta. Vol. 22, Curran Associates, Inc., 2009.
[43] Xiao-Li Meng. "Statistical Paradises And Paradoxes In Big Data (I) Law Of Large Populations, Big Data Paradox, And The 2016 US Presidential Election". In: Ann. Appl. Stat. 12 (2 2018), pp. 685-726. Merriam Webster Dictionary. Social system. en. (Visited 10/30/2024).
[44]
[45] Samuel Messick. "Meaning and Values in Test Validation: The Science and Ethics of Assessment". In: Educ. Res. 18 (2 1989), pp. 5-11.
[46] Lucas Monteiro Paes, Carol Long, Berk Ustun, and Flavio Calmon. "On the Epistemic Limits of Personalized Prediction". In: Advances in Neural Information Processing Systems. Ed. by S Koyejo, S Mohamed, A Agarwal, D Belgrave, K Cho, and A Oh. Vol. 35, Curran Associates, Inc., 2022. pp. 1979-
1991.
[47]
OpenAl et al. "GPT-4 Technical Report". In: arXiv [cs.CL] (Mar. 15, 2023).
[48]
Fragkiskos Papadopoulos, Maksim Kitsak, M Ángeles Serrano, Marián Boguná, and Dmitri Krioukow. "Popularity versus similarity in growing networks". " In: Nature 489 (7417 2012), p. 537.
[49] Daniel I. Pimentel-Alarcón, Nigel Boston, and Robert Nowak. "A characterization of deterministic sampling patterns for low-rank matrix completion". In: IEEE J. Sel. Top. Signal Process. 10 (4 2016), pp. 623-636.
[50]
Deborah Raji. There's 's more to data than distributions. Mar. 31, 2022. (Visited on 03/31/2022).
[51]
Benjamin Recht. Machine Learning has a validity problem. 2022. (Visited on 03/15/2022).
[52] Rylan Schaeffer. Brando Miranda, and Sanmi Koyejo. "Are Emergent Abilities of Large Language Models Mirage?" In: Thirty-evvntth Conference on Neural Information Processing Systems. Nov. 2, 2023. (Visited on 05/13/2024).
[53] Tobias Schnabel, Adith Swaminathan, Ashudcep Singh, Navin Chandak, and Thorsten Joachims. "Ree- ommendations as Treatments: Debiasing Learning and Evaluation". In: Proceedings of The 33rd Interna- tional Conference on Machine Learning. Ed. by Maria Florina Balcan and Kilian Q Weinberger. Vol. 48. Proceedings of Machine Learning Research. New York, New York, USA: PMLR, 2016, pp. 1670-1679. [54] Lesia Semenova, Cynthia Rudin, and Ronald Parr. "On the existence of simpler machine learning models". en. In: 2022 ACM Conference on Fairness, Accountability, and Transparency. FAceT "22: 2022 ACM Conference on Fairness, Accountability, and Transparency (Scoul Republic of Korca). New York, NY, USA: ACM, June 21, 2022. (Visited on 04/28/2024).
[55] Shai Shalcv-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithums. Cambridge University Press, May 19, 2014, 415 pp.
[56]
Herhert A Simon. "On a class of skew distribution functions". In: Biometrika 42 (3/4 1955), pp. 425-440. Nathan Srehro and Russ R Salakhutdinov. "Collaborative Filtering a Non-Uniform World: Learning with the Weighted Trace Norm". In: Advances in Neural Information Processing Systems. Ed. by J Lafferty, C Williams, J Shawe-Tayel
[57]
R Zemel, and A Culotta. Vol. 23. Curran Associates. Inc., 2010. [58] Aarohi Srivastava et al. "Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models". In: Transactions on Machine Learning Research (Jan. 19, 2023). (Visited on 01/06/2024).
12

---

[59] Harald Steck. "Training and testing of recommender systems on data missing not at random". In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 2010, pp. 713-722.
[60]
Tom F Sterkenburg and Peter D Grünwald. "The no-frce-lunch theorems of supervised learning.. In: Synthexe 199 (3-4 2021), pp. 9979-10015.
[61] Mark Steyvers and Joshua Tenenbaum. "The Large-scale structure semantic networks: Statistical analyses and a model semantic growth". In: Cogn. Sci. (1 2005), pp. 41-78.
[62] Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. "Yago: a core semantic knowledge", In: Proceedings of the 16th international conference on World Wide Web (Banff, Alberta, Canada). WWW '07. New York, NY, USA: Association for Computing Machinery, May 8, 2007, pp. 697-706 (Visited on 12/31/2023).
[63] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava. Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Pumit Singh Koura, Maric-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molyhog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan. Melanie Kambadur, Sharan Narang. Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. "Llama 2: Open Foundation and Fine-Tuned Chat Models", In: arXiv fes. CL/ (July 18, 2023).
[64]
Ivan Voitalov, Pim der Hoorn, Remeo der Hofstad, and Dmitri Krioukov. "Scale-free networks well done". Phys. Rev. Res. (Nov. 2018), p. 033034.
[65]
Denny Vrandečić and Markus Krötzsch. "Wikidata: free collaborative knowledgehase" In: Commun.
ACM 57 (10 Sept. 23, 2014), pp. 78-85.
[66]
Watson-Danicls, David C Parkes, and Berk Ustun. "Predictive multiplicity in probabilistic Jamelle Watson- Daniels, classification". en. In: Proc. Conf. AAAI Artif. Intell. 37 (9 June 26, 2023), pp. 10306-10311 (Visited on 04/28/2024).
[67]
Wikipedia contributors. Wikipedia: Who writes Wikipedia. (Visited on 01/24/2024).
[68]
David H Wolpert. "The lack a priori distinctions between learning algorithms". In: Neural Comput. (7 1996), pp. 1341-1390.
[69] Cai-Nicola Ziegler. Sean M McNee, Joseph A Konstan, and Georg Lausen. "Improving recommendation lists through topic diversification' en. In: Proceedings of the 14th international conference on World Wide Web WWW '05. the 14th international conference (Chiba, Japan). New York, New York, USA: ACM Press, 2005. (Visited 01/04/2024).
13

---

Supplementary Information
A
Notation
Random variables are are denoted by italic uppercase letters, e.g., S, X. Sets are denoted by calligraphic uppercase letters, e.g., X. 8. Constants are indicated with lowercase greek letters, c.g., 6, p. Functions and scalar are denoted by lowercase letters, e.g., f. and x. Matrices and higher-order tensors are indicated with bold uppercase letters, e.g., F, U.
Table 3: Notation
Concept
Notation
Possible world Hypothesis
f:X - y
h:X - y
Loss
f: y - R,
Sample distribution
S:X [0,
Target distribution
T:X - [0
Social system
(f.S)
Sample graph
S~S"
Test set
D f(x, :
Risk
LT =Bx-1(((6()),(000
Estimated risk
0 OER,
B Validity framework
In this work, am interested in the validity of inference settings, i.e., whether assumptions and observations allow for any valid inferences all. To formalize this, I will take the following high-level approach:
Inference setting An inference setting consists of set of assumptions A, a fixed dataset 'D which is collected from a sampling distribution S, and target distribution for which we want to make inferences. Note that S is not guaranteed to be identical to T. Hence, we're concerned with out-of-distribution generalization settings.
Expected risk over possible worlds Assumptions A and observed data D define a set of possible worlds F that is consistent with A and D. Given a probability distribution F over F, am then interested the expected risk over all possible worlds that are consistent with A and D.
Validity An inference setting is valid, if the expected risk over possible worlds can be bounded meaningfully at all, i.e., if there exists at least one hypothesis class for which the generalization error of least a single hypothesis can be bounded sufficiently.
To approach the question of validity, learning theory has traditionally focused nearly exclusively on sufficient conditions for valid inferences. Under active data collection, i.e., in scenarios where one can control exactly how data collected, sufficient conditions are highly attractive since they provide exact specifications for inferences be valid with high probability. However, under passive data collection, the situation is reversed. Sufficient conditions for the validity of inferences usually place highly restrictive demands on the data collection process (e.g., i.i.d. samples or simple random sampling) which are challenging to satisfy even when data is collected carefully in an active way. Since passive data collection, by definition, exerts no control over the sample generating process, these sufficient conditions are not met with near certainty. For this reason, I am focusing here on necessary conditions for validity, i.e., conditions that must always be satisfied for inferences to be valid. Under passive data collection, necessary conditions can provide important insights since they need hold for any data collection process or, conversely, can be used identify scenarios where inferences not valid with high probability.
14

---

B.1 Connection to No-Free-Lunch theorems
The validity framework of section 3 and the No-Free-Lune Lunch- theorems are closely connected. First, consider the expected risk over all possible worlds relative to F, i.e.,
[ = =
B
(I)
Equation (1) is then akin to the objectives considered in the seminal No Free Lunch (NFL) theorems [68, 60]. For instance, the NFL theorem for supervised learning can be written as VA B- Bx-r(((hADD)) (X). f(X)) 1/2, where U is the uniform distribution over all possi- ble worlds in an assumption-fre free setting (i.e., A = 0). l the 0/1 lloss and hA(D) is the hypothesis derived from a finite sample 'D with algorithm A. In contrast to the NFL theorems where A = implies an induction-hostic universe - my focus on friiecl settings (A 0) but where D is sampled from complex social system. Since 1. is non-negative random variable, we can then connect definition and eq. (1) via upper and lower bounds based on Markov's inequality.
Definition (Markov's s inequality). Let X be non-negative random variable and Then
P(X 2 a) s B[X]/a.
Hence, it follows that the expected risk over all possible worlds is large for invalid settings since holds that
By-F 2 e. P. C.Py-F(L)) > x)
B.2 Importance ontological parsimony and test validity in the i.i.d. setting
The strong appeal of the train-test paradigm that, with careful data collection, we require further ontological assumptions to ensure the validity of the model validation procedure. In particular, if we have a test set that is sampled independently from T, it follows straightforwardly from Hoeffding's inequality that we can meaningfully bound the approximation error over this test set [55, Theorem 11.1]. Let J T be a test of size m, sampled i.i.d. from the target distribution T. Then, holds that
PT-TTM (1:5 (c:s- Lng
log(2/0) 2m
2 1-
Importantly, this holds for any hypothesis h, any algorithm A, and any training set Hence, under careful data collection where we know that if the test set is sampled i.i.d. from T, any hypothesis can be validated based on the observed data only.
This property, i.e., that we can evaluate the performance of a model without further assumptions on the model itself, is crucial to compare the performance of different methods since different architecture, inference, and hyperparameter choices correspond to different assumptions. Maybe more importantly, this property also crucial validate our model assumptions on observed data (given that the sampling assumption holds), since otherwise we could only make statements relative to that our model assumptions hold, which is, of course, much weaker and not informative. Hence, if we need to make model specific assumptions for the validation error to be informative for the generalization error, the train-test paradigm would be relatively meaningless. Of course, the (considerable) challenge is to collect i.i.d. samples from the true targer distribution T which can not be guaranteed and is an important assumption on the data collection process.
Table 4: Estimators and quality measures.
Estimators
Risk Measures
Monte Carlo
Horvitz-Thompson
Empirical Risk
HT Weighted Emp. Risk
Estimator from 8 S
1 Evexx
E.es pitii
1 ((1)).
Eves fioca,/1x))
Estimated expected value
Ex-s[X]
Bx-[[X]
(x-rI((AXX) ((Ms
15

---

fir
Siy
1.5
COOPE 2
2.5
2.15
F- lereor?
(a) Sampling bias
(b) Pareto distribution
(c) Degree distribution MOVIELENS 100k
Figure 4: Properties of complex social systems (a) Graphical model of sampling bias. (b) Illustration of power-law distribution the example of the Pareto distribution. Degree distribution of MOVIELENS 100k.
C Complex social systems
In the following, will discuss how sampling bias and heavy- -tiled distributions can occur, and can be connected, in complex social systems. First, sampling bias is concerned with how S is collected. Most standard inference methods assume i.i.d. samples from T, but is well know that this assumption can be easily violated when sampling in complex systems.
Definition 8 (Sampling bias). Let 8/, denote the random variable corresponding entities (i.j) X, X2 j being samples time r. Samples in complex social systems can then neither be assumed to be independent across time nor independent with regard to the target value fij. i.e.,
P(S P(S))) and P(St))ftt) # P(S)))
Higher arity relations are defined analogously. See also fig. 4a for the assumed sample dependencies.
Sample biases as in definition be causes by aspects such popularity bias, i.e., if popular items are more likely to be sampled, and quality biases, i.e., if items with higher values for fij are more likely to be sampled.
prime example of how sampling bias in the form of popularity bias can lead to power-law distributions, is the influential Barabasi-Albert model [5]. In this model of complex networks, nodes are added to a network one by one and are connected to existing nodes with a probability proportional their degree, i.e., popularity. Formally, this model defined as follows:
Definition (Barabasi- Albert model). Let G = (X, E) be graph. Furthermore, let P(i ~i j) denote the probability that the edge ~ is added at time to & and let denote the degree of node x;. The Barabasi-Alun Albert model generates then graph as follows:
1. Start with small connected graph Go with m nodes.
2. each time step / 0, add a new node x to and connect it to m existing nodes in with probability proportional to their degree, i.e.,
Ki
P(i - v) Σ,ex Kj
It is then well known that definition 9 leads to power-law degree distribution in G, i.e., distribution where the probability of a node having k connections is proportional k- for some a > O.
D Proof corollary 1 (Necessary condition for test validity)
Corollary 1 (Necessary condition for test validity). Let (A, T.F) be an inference setting, let E: x RR be a positive loss function, and let H be hypothesis class. Furthermore, let 0 E R. be any risk estimate for h. Then, if (A., D. T, is (e, -eesttvvvlldd, must hold that
H Py F HE
2 1-
16

---

Link prediction Cora
Extreme Classification Wiki10-31K
10c
Sourte Ta-ge
Bitec wntt
Proportion (log scale)
Poportion (log scale)
Lobes
10
10
10
10
10"3
10
10
75 100
125
150
500
1000
1500
2000
Observations
Observations
(a)
(b)
Figure 5: Sample graph degree distributions for widely used benchmark datascts. (a) Graph learning and
link prediction Cora (b) Extreme classification via Wikil0-31k. can seen, all benchmarks follow similar heavy-tailed distributions their sample graph as the Moviel.ens dataset in main text. such, these henchmarks are subject to the same results and pathologies.
Aguatoos
Y1 17
(a) Validity relationships
(b) Tensor representation
(c) 2-core of graph
Figure 6: (a) Relation between assumptions, possible worlds, and hypotheses Assumptions define of functions f which subset are possible worlds F, i.c., those functions which are also consistent with observations D. While hypotheses H will often be equivalent to A. they can also be proper subset of A and do not need to overlap with F. e.g., due to additional assumptions computational requirements that constrain H. The functions f.f*. and lt indicate the relevant objects for the necessary conditions in corollary their relationships (solid and dotted lines), (b) Tensor representation of function f X[ X2 XX3 R. (c) Illustration of the 2-core of graph. Nodes within the 2-core are indicated by black. Nodes outside the 2-core are indicated as white, edges that are removed when reducing the 2-core are indicated dotted.
well
| s is equivalent to 0 L S SEA - Furthermore, Proof. First, note that |0 10-L have
0 1.1, s SE - = ( 1 - 856 {)..
follows then simply from the monotonicity of probability that
1- 6 - L7al s P e) F se+
E Proof lemma 1 (Rank-k underdetermination)
will first introduce the concept of S-isomerism and connect to k-connectivity. will then use these results to proof lemma 1.
First, let 8, = U (i. e 8) denote the set of observed columns for row i and 8., = {i: (i. 8)
denote the observed rows for column j. Let 8, [F] E m be the sub-matrix of F E Bmx which obtained by restricting the columns be the sub-matrix of F mx which is obtained by restricting the rows of F to the indices in S. Then, S-isomerism is defined as follows:
to the indices in 8,,. Similarly, let [F [F] E R S
Definition 10 (8-Isomeric). Let F Rmxx and let 8 S (1....mm) x (1.....m) with S.j # 0. Then,
is called S-isomeric iff
rank (8,, [F]) rank(F), L.... and
rank (8., [F)) rank(F),

---

Corollary 3 (Necessary condition for S-isomerism). Let 8 be sample graph and let rank(F) F) = k. If F is 8-isomeric, then it must hold that S k-connected.
Proof. First, note that rank(X) I min(m,n) n) for any X E __ Hence, it follows from definition 10 that for rank-k matrix to be 8-isomeric, each column and row needs have at least observed entries. Since this is equivalent k-connectivity, the result follows.
Lemma (Rank-k underdetermination).. Let A the set of possible worlds '5 forms non-empty vector space.
{f rank(f) s k}. Then, if is not k-connected,
Proof. Since rank(f) = k and 8 is not k-connected, it follows from corollary that is not 8- isomeric. Hence, holds via [38, Theorem 3.2] that there exist infinitely many matrices f that all explain the observed data 8 perfectly, i.e.,
f
rank(f") 2 raak(f)
=i v(i.)) E.
Moreover, it follows from [38, Lemma 5.1] that this set possible worlds forms a non-emply vector space V.
Proof lemma 2 (Rank-k test invalidity)
To prove lemma 2, will first show the following auxiliary proposition:
Proposition (Risk inequality for Bregman projection). Lei é - R, be a scalar Bregman divergence and let f* arg infy pn be the Bregman projection h onto vector space F. Then, holds that
L..- S 3/
Proof. First, note that fn is simply convex combination of scalar Bregman divergences, i.c..
1. Σ M())) XEX
Hence, 1 itself a (separable) Bregman divergence. Proposition follows than from the general- ized Pythagorean theorem for Bregman divergences [20, Eq. 2.3] since every vector space is a convex and f* is the projection of h onto F. i.c., it holds that
4n 2 Lyp- Lj.hh 2 L.y.
Lemma (Rank-k cest-invalidity). Let A be identical lemma 1, let E be a scalar Bregman divergence, let F be the uniform distribution over F, and let T be the uniform distribution over X. Furthermore, let R, any risk estimator on a test set. Then, if not k-connected,
(A., (A,D,TFF F,F is test-inm invalid, i.e,, it holds for any e > 0 that
VJCVh JC :y:FP L ())
Proof. Since the standard uniform distribution not defined on an entire vector space, will instead consider the limit of the class of uniform distributions of balls of radius Next, since is Borel measurable, B(f, e) = (f' LT,- E) defines a measurable set around each f F. Furthermore, let VolB E) denote the volume of such an e- "ball." Via the change of variables formula, we know
Table 5: Examples of Sealar Bregman Divergences
Divergence
8(x,y)
Divergence
((x,))
Squared loss
(x-y)²
KL-divergeecee ItakuraSaitoo
x llo(x//))
Log loss
x log(xx/)) + (1 xx) log((1 - x)/(1 - y))
- log((x/)) -
18

---

then that the volume of B(f.r r. e), i.., the volume of the original ball stretched in all directions by r 2 is given by
Vol B(f [ dx = Idini dy r
din'V VolB(f.e).
Next, let U, denote the uniform distribution over B(f.r- a.f.ree) E).
Then, the probability of sampling a
point inside B(f.e) e) when drawing points uniformly from B(f.r r E) with 2 1 is given by
A E F Py-u (crs se)=
Vol c(f.c) Vol r(f.r.e)
Moreover, V is non-empty follows that dimV 2 Hence, as we increase r to span large parts of V, it holds that
VeYf F: lim Py-u, (4h s =0)= =0.
5-00
Using eq. (2) will then show lemma 2 by considering the two cases E F and $.F.
If we assume h E J, lemma follows directly from corollary 1 and I being non-empty vector space according to lemma (since is not k-connected).
On the other hand, if & F, consider the projection of h onto F according to f, i.e. f = arg miny L fh Since 4), a Bregman divergence and a vector space, lemma follows then from corollary proposition 1 and the monotonicity of probability since L s fm
G Extensions to Higher-arity relations and bounded domains
G.1 Ternary and higher arity relations
First, note that higher arity functions can be represented as tensors of the same order as follows (see also fig. 6b for a visualization):
Definition 11 (Tensor representation). For function f : Xg x X2 X ... x Xx - R over finite sets of size [Xy] = mi, we can construct its tensor representation F E R.m Xm:x- Xmig via Fij.... fx;, .x.) for all x; E X1,x, E X2,..., E X4.
A trivial extension of theorem 1 and its related results can then be obtained by considering the rank of the projection of the tensor representation of f onto its matrix presentation such that Fij =Ex jk) (what equals the assumption that the rank of the predicate mode in f is one). Since predicates in many knowledge graphs are very sparse, the sum over k will often preserve this sparsity and the associated heavy-tailed distributions. In this case, the results of the matrix case extend directly to the tensor case. If this is not the case, it is necessary to extend the matrix analysis of lemma to the tensor case and consider cases where the predicate mode can have rank larger than one. However, this is beyond the scope of this paper and reserved for future work.
G.2 Bounded domains
In many practical applications, the output domain of the function f bounded, i.e., y [0. 1]. In this case, the main results of this paper can possibly be extended if f can be expressed in terms of bijective link function g, i.e., f(x) g(((x)) where are bijective include the logit and probit functions (binary variable) and the log function (Poisson variable). In the following, provide a brief outline of the argument: Since g is bijective, its inverse exists and we can work on O by applying g- to f. Next, for each column (or row) of Φ, consider the regression problem h; Uv; with the goal of modeling the observed entries of Φ. If the dimensionality (rank) of U and v, is larger than the number of observed entries in +; this regression problem becomes an underdetermined system. For areas of the sample graph that are too sparse, we can then find again infinitely many matrices that match all the observed entries of c but are different on unobserved entries. The main results of this paper would then extend directly to & and via the link function g to the bounded domain. One difference to the results in the unbounded case is that the above argument holds for the degrees in the sample graph, while the unbounded case holds for the stronger k-core condition.
X R. Common link functions that
19

---

H
Inefficiency of scaling and benchmarks
Lemma allows to answer the scaling question by asking how many draws from would be necessary such that all nodes are within the k-core of with high probability, i.e., how many samples needed until arriving at a valid test setting, In the following, I will discuss different ways to approximate this question.
H.1
Scaling and the coupon collector problem
One way to lower bound the number of samples needed to arrive at valid test setting would to calculate the number of samples needed to sample each node outside the required k-core at least once. This is an instance of the coupon collector problem with unequal probabilities. In particular, let 7p be the number of draws from S until have collected k distinct nodes from X2 for an arbitrary node in X1. Then, it follows from [26, Corollary 4.2] that
B[Tx] = Eny=o (-1) m- Σ111=g I-P5
where P, -Ej Pj and where Ensing denotes the sum over all subsets of size q. However, eq. (3) is hard to interpret and for that reason not very useful for our purposes. Moreover, eq. (3) is not even tractable compute at the scale that we would require for the settings considered in this paper. For instance, assume that we are dealing with relatively small-scale domain of [X] 10? entities. Since eq. (3) requires over all subsets of size 1, for model of rank 10 this operation alone would require more than
(
|00 k [--1)
107 (9))
2.75 10 FLOPS.
=
H.2 Proof for scaling bound in corollary 2
Since the coupon collector problem not computable, corollary considers an even weaker lower bound and asks how many samples are needed to sample average node at least once. For fixed node x,, this is an instance of number of trials until first success and follows a geometric distribution with expected value Ti 1/p,. Next, for power-law distribution with P(X x) u(x)x"* it holds that P(X x)) u' (x)x-(a+1) where u' is also slowly varying function. Hence, we have
1
u xxxx))x;
(a+1)
u (x;)
To illustrate eq. (4), consider the following example using the Pareto distribution instantiate U'. In this case, we have T; xx
/axx For random node in X os size it holds then that
Bi-Uy [7]] E axd
Bi-Uf [x+++]]
[x,
oxx (n/2)
ax min
min
where the inequality follows from Jensen's inequality for This concludes the proof.
I Experiments
All experiments were computed on single NVIDIA Volta V100 GPU and implemented using Jax [12], Jaxopt [8], Numpy, and Scipy. All experiments were computed on the MOVIELENS 100k benchmark [27] which is available at attps://grroppae and released under a custom license sttps://files: srruplens. org http://aaasetttmoviielelle txt.
ml
I.1 Computing possible worlds under rank constraints
To find possible worlds that fit the observed data under a rank-constraint, I will first compute single subspace for which can model all observed data with highest accuracy, For this purpose, am first fitting a matrix F UVT to the observed entries under a rank constraint, i.e., via min ||ss - Ysll? where the constraint rank(F s k) is enforeed simply via U m V Rn*k, Next, let U QR
20

---

be the QR decomposition of U. Then, we know that the set of possible worlds within the subspace spanned by Q R= must be of the form Po n Pg where
Po QQ"M and [Ms(M)),) = [i if (i, E
otherwise
the orthogonal projections onto the column space of and the observed entries, respectively. Furthermore, assume that we have already found matrices that are of rank & and which fit the observed entries Ys with high accuracy. We can then find the p 1-th matrix by minimizing the following objective:
X arg min [X))(X) - XI| (X) Ysll E IIX X/IlF X
s.t. Ymin X1 S Ymax- (5)
Importantly, the experimental results in section and fig. 3 hold already for only a single subspace U and considering further subspaces that also explain the observed data can only increase the differences between possible worlds reported in these experimental results.
I.2 Area over the eCDF as expected risk
In the following, will discuss how the area over the eCDF curves in fig. 3b correspond to the risk L ff between these pairs of possible worlds. In particular, let E be the random variable corresponding to the normalized absolute error of entries possible worlds f and f'. Furthermore, let Fx(x) = P(E x) be the CDF of E. The expected error between both possible worlds (in terms of NAE) is then equivalent to the area over the curve of eCDF, i.e.
[f(x) - (xx)
[ (1 (I-FE(x)ddx.
1f B,-U
Xmax Xynin
1.0
1.0
0.8
.00h Percentiis..
9000 Percenttt
Proportion
Proportion
0.5
..00h Persentie......
0.5
50th Peconnlle
.200 Persentile
0.2
20th Pecoentie
0.0
0.0
0.00
0.230.31
1.00
XJI (Xmox Xmm)
[X] X// (Xmax X
X.X
(a) cCDF of Maximum NAE
(b) cCDF of Pairwise NAE
Figure 7: Cora experiments. Empirical CDF of maximum NAE (a) and pairwise NAE (b). can be seen that expected error (area over the curve) behaves similarly to the MovieLens dataset in the main text.
J Related work
In statistics, Meng [43] analyzed scaling-related question similar to this paper: Given a carefully collected survey with low response rate (small data) large, self-reported dataset without data curation (big data), which dataset should you trust more to estimate population averages? For this purpose, Meng introduces an fikel--frmull-like identity which connects estimation quality data quality, data quantity, and problem difficulty. Similar to the results in this paper, Meng shows that data quantity highly inefficient to overcome issues in data quality, especially sampling related issues. While related in spirit, the results in this paper go beyond the question of surveying and population averages and establish related results in the more general context inductive inference via formalizing properties of complex social systems and their impact validity of inferences.
21

---

In motivation, this paper is also related to the work of D' Amour et al. [19] who study underspecifica- tion of machine learning pipelines as a cause for inference failures. this context, machine learning pipeline is "the full procedure followed to train and validate predictor". A machine learning pipeline then considered underspecified when can return many distinct predictors with equivalently strong test performance. This notion of underspecification is closed related to the concepts of possible worlds and validity in this paper.
Srebro et al. [57] studied the problem of matrix completion based on non-uniform observations such as power-laws. However, in contrast to this work, Srebro al. [57] assume that S T. The advantage of this assumption is that it leads to much simplified learning setting in which valid inferences are indeed possible. However, as I discuss in section I would argue that this is not the problem that many inference settings are concerned with (and that it is questionable in matrix completion setting as well). Further important results this context include [49] on low-rank matrix completion from deterministic samples as well as the work of Schnabel et al. [53] and Marlin et al. [40] on learning from biased samples. contrast to these prior works, I am expanding the setting to the validity of inferences and validation, provide necessary conditions, and situate them explicitly in the context of complex social systems.
K
Limitations
As most theoretical work, this work needs to make certain assumptions to make the phenomena of interest amenable to analysis. In this work, the core assumption is that samples in complex social systems follow heavy-tailed distribution. While this is very robust finding in social science and widely supported, discussed in section 2, it limits the results of this paper to this specific setting. For further analysis, this paper further assumes that this heavy-tailed distribution follows a regularly- varying power-law. This is again supported assumption [64] and allows for clean theoretical analysis. However, as discussed in section 2, is still disputed whether samples in complex social systems actually follow this particular form. However, it is undisputed that they follow heavy-tailed distribution, and as such, while the power-law based results might not apply exactly, their general implications are still supported.
22

---

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

---

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

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: We intend to release the code for experiments and proofs for the camera ready version. However, current time, not able to provide access to the code. Yet, all experiments should be easily reproducible from the information in the main text and supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (httpa://nips.cm
public/guidest
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nipss cc/publicc guides/ CodeSubm ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: See supp.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Error bars are not applicable to the experimental analysis of this paper. How- ever, fig. 3b shows the variability over possible worlds.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
25

---

Answer: [Yes]
Justification: See supp.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http///eurrpppppeee http///blcc/tthccctuiiiiieeeeeee
Answer: [Yes]
Justification: The research conducted in this paper conforms with the NeurlPS Code of Ethics, i.e., none of the potential harms apply this work, societal impact of this work is discussed, and impact mitigations are considered as far as they apply.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper is largely theoretical and focused on the validity of the train-tes teint paradigm complex social systems. As such it has direct connections to understanding and improving the social impact of deployed system. While the evaluation of this aspect is beyond the scope of this aspect, provide discussions connections to societal aspects such as fairness and participatory data collection. I also discuss fairness aspects in the Movielens experiments in section 4.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g., deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
26

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This paper is purely theoretical and does not release models or data that have high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The only existing assest used in the paper is the Moviel.ens 100k dataset for which citations are provided and the license linked in supp. I.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ con/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does currently not release new assets. In the future, code will be released under CC-BY-NC license.
Guidelines:
27

---

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


Reviews:
[{"review_id": "wi7C8impAk", "reviewer": "Reviewer_RViy", "summary": "The paper addresses the critical issue of model validation in AI systems, especially those deployed in complex social environments. It argues that the prevalent train-test paradigm, commonly used for model validation, is often invalid in these settings due to the inherent assumptions it violates. The paper presents formal impossibility results, demonstrating that for many AI tasks involving complex social systems, the train-test paradigm cannot ensure valid model performance assessments. The study uses the MOVIELENS benchmark to illustrate these issues and suggests remedies like participatory data curation and open science to address the epistemic limitations identified.", "questions": "1. Could you elaborate on alternative model validation paradigms that could be more suitable for complex social systems?\n2. Could you provide more examples or case studies beyond the MOVIELENS benchmark to illustrate the validity issues in different types of AI systems?\n3. Could you discuss any potential limitations of your approach and how they might be addressed in future research?", "limitations": "1. To make the paper more accessible, consider simplifying some of the theoretical discussions or providing more intuitive explanations alongside the formal proofs.\n2. Include more detailed discussions on how the suggested remedies, such as participatory data curation, can be practically implemented in real-world scenarios.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper provides novel insights into the limitations of the train-test paradigm, especially in the context of AI systems interacting with complex social systems.\n2. It offers formal proofs of the epistemic limitations, providing a robust theoretical foundation for its claims.\nRelevance: The study addresses a highly relevant issue in modern AI, given the increasing deployment of AI systems in socially impactful contexts.\n3. Using the MOVIELENS benchmark to illustrate the theoretical points adds practical relevance and makes the arguments more tangible.", "weaknesses": "1. The formal proofs and theoretical discussions might be too complex for practitioners without a strong background in the relevant mathematical and statistical concepts.\n2. While the paper suggests remedies, it does not delve deeply into how these can be practically implemented on a large scale, which could limit their immediate applicability.\n3. The results are heavily dependent on the specific characteristics of the social systems and data collection methods considered, which might limit the generalizability of the findings to other contexts or systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. I agree that your comments address important question and hope that the response to all authors as well as the below additional clarifications can alleviate your concerns. Since everything is addressable via minor clarification updates, I hope this will also allow you to raise your score.\n\n*The formal proofs and theoretical discussions might be too complex for practitioners without a strong background in the relevant mathematical and statistical concepts.*\n\n* Thank you for the suggestion. My aim is certainly to make this paper as accessible as possible, and I tried to do so via informal statements of the main results and providing extensive context. Unfortunately, the page constraints set limit on how much this is possible. However, I will follow your suggestion and add more intuitive examples where it is possible. \n* While I acknowledge the issue, I'd also point out that the impression might not be fully uniform, e.g., feedback from other reviewers states that the paper is \"easy to follow and fun to read\", \"very well-written\".\n\n*Could you elaborate on alternative model validation paradigms that could be more suitable for complex social systems*\n* Thank you for raising this question. With my current knowledge, I would not so much point to alternative model validation paradigms but rather to improved data collection for model validation via the paper's $k$-core condition. For details on this, please see the response to all authors.\n\n*Could you provide more examples or case studies beyond the MOVIELENS benchmark to illustrate the validity issues in different types of AI systems*\n* Thank you for this question. Indeed, these results apply to a wide range of settings. In the PDF attached to the response to all authors, I illustrate this using widely used benchmarks for three different settings:\n\t* Reasoning - FB15K-237 (https://paperswithcode.com/dataset/fb15k-237): Here the goal is to infer the truth value of (subject, predicate, object) triples using logical reasoning. It is a widely used benchmark for reasoning and, as can be seen from the PDF, has the same structural properties as MovieLens. As such the results of this paper apply directly (also discussed in Section 3 and Appendix D.3). The social system the generates the biased observation is both the production of knowledge and its recording in FreeBase.\n\t* Link Prediction in Graphs - CORA (https://paperswithcode.com/sota/link-prediction-on-cora): Here, the goal is to predict links/edges in a citation graph based on observed edges. It is a widely used benchmak in graph learning and again shows the same structural properties at MovieLens. The social system that generates the biased observations is the citation practice in science (incl. popularity bias etc). \n\t* Extreme Classification - Wiki10-31k (http://manikvarma.org/downloads/XC/XMLRepository.html): Here, the goal is to predict the correct labels for Wikipedia entries from a large number of user provided labels (hence extreme classification). The social system that generates the biased observation are the authors that contribute Wikipedia entries and their labeling practice.\n* In addition to these datasets, I also want to highlight that MovieLens is THE recommender systems benchmark (comparable to MNIST for vision) and is still widely used, even in SOTA LLM benchmarks such as BigBench (https://github.com/google/BIG-bench/blob/main/bigbench/benchmark_tasks/movie_recommendation/README.md)\n\n*Could you discuss any potential limitations of your approach and how they might be addressed in future research?*\n* Please see the limitations section in appendix of the paper.\n\n*The results are heavily dependent on the specific characteristics of the social systems and data collection methods considered, which might limit the generalizability of the findings to other contexts or systems.*\n* The NFDS results in this paper actually are two-fold:\n\t* 1) It first establishes necessary conditions that need to hold for *any* model validation to be valid\n\t* 2) and then shows that these conditions are violated when sampling from complex social systems\n* As such, the necessary conditions in 1) hold independently of the concrete application in social systems and provide general insights into the validity of model validation.\n* That being said, I again want to highlight the urgent need to also understand the interaction with social systems since this is affecting much of our practice. Hence, even if the results would only be contained to this setting, I wouldn't consider it a limitation.", "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": "", "extra_scores": {}}, {"review_id": "ZPoblj0CQC", "reviewer": "Reviewer_9VqZ", "summary": "Building advanced and very large general-purpose ML models using extremely large datasets from sources such as the Internet has gained a lot of recent attention.\nParticularly, when the training set is sampled from a distribution S while the target distribution is T, the paper introduces the notions of (\\epsilon,\\alpha)-validity and (\\epsilon,\\alpha)-invalidity for inference validity and defines test validity accordingly. \nThe paper shows that there is \"no free delivery service\" of data that allows inference/test validity on a global scale for complex social systems.\n\nMore importantly, the paper provides the metrics and necessary conditions that limit the scope of AI in complex social systems.", "questions": "No specific questions", "limitations": "Please see the weaknesses section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "S1. The paper studies a problem of immense importance: with the rapid growth of advanced ML models such as LLMs and their versatile usage across a wide range of tasks that impact societies and human lives, establishing the necessary conditions and checks and balances to limit their scope is vital. Formally introducing such metrics and conditions, this paper is an interesting step in that direction. \n\nS2. The paper follows a formal and careful writing scheme, which makes it easy to follow and fun to read.\n\nS3. The proposed validity framework and the inference and test validity concepts provide metrics for evaluating the validity extension of a model trained on a distribution S to T.", "weaknesses": "W1. While I enjoyed reading the formality and the definitions in section 2, I did not find the so-called no delivery service (NDS) of data surprising.\nAs the author also stated, based on the theory of ML and the NFL theorem, when there is a sampling bias, and the source and target distributions are different, the expected performance guarantee of the model does not carry over. This has also been extensively discussed under \"lack of generalizability\" concept.\n\nW2. It is not particularly a weakness, but if I am not mistaken, the NDS observation for complex social systems naturally follows the previously known heavy-tailed distribution property of these systems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. I agree that W1 is important to clarify and hope that the response to all authors as well as the below additional clarifications can alleviate your concerns. Since everything is addressable via minor clarification updates, I hope this will also allow you to raise your score. \n\n*W1. While I enjoyed reading the formality and the definitions in section 2, I did not find the so-called no delivery service (NDS) of data surprising. As the author also stated, based on the theory of ML and the NFL theorem, when there is a sampling bias, and the source and target distributions are different, the expected performance guarantee of the model does not carry over. This has also been extensively discussed under \"lack of generalizability\" concept.*\n* Thank you for raising this important question. The key difference to the known results and issues that you are listing is that, to the best of my knowledge, these are based on a \"lack of justification\" argument, i.e., that we know that our usual guarantees do not apply. In contrast, this paper provides much stronger insights in form of rigorous impossibility results. The insights that can be gained from such results are much more substantial and provide a path forward to improving the situation (while a lack of justification can not). Please see the response to all authors for a detailed discussion of this (also in terms of sufficient versus necessary conditions and their different contributions).\n* I also want to highlight that the results in this paper do point to an *actionable* path forward via targeted data collection using the $k$-core condition. This is also discussed in detail in the response to all authors. Again, this is possible because of the theoretical insights in this paper.\n* For \"lack of generalizability\":  How I am familiar with this concept in the context of validity theory is mostly as an empirical observation, e.g., that studies do not generalize beyond their very specific context. The results in this paper are again stronger, in the sense that the benchmark itself is invalid (not only that it doesn't generalize to *new* settings). \n* The practical importance of the results is also highlighted by the wide-spread usage of benchmarks like MovieLens in settings where it cannot be valid, even in SOTA LLM benchmarks such as BigBench (https://github.com/google/BIG-bench/blob/main/bigbench/benchmark_tasks/movie_recommendation/README.md)\n\n*W2. It is not particularly a weakness, but if I am not mistaken, the NDS observation for complex social systems naturally follows the previously known heavy-tailed distribution property of these systems.*\n* The NFDS results in this paper are two-fold:\n\t* They first establish necessary conditions that need to hold for model validation to be valid\n\t* and then show that these conditions are violated when sampling from complex social systems\n* As such the necessary conditions hold independently of the concrete application in social systems. \n* While the heavy-tailed distribution in complex systems have indeed been established prior to this work, one contribution of this paper is to combine this knowledge with the newly established necessary conditions to gain non-trivial insights into current practice of AI.", "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": "", "extra_scores": {}}, {"review_id": "HcOZKuzeOp", "reviewer": "Reviewer_qRpv", "summary": "This work shows that the classic paradigm of training and testing in ML has validity flaws that makes it unreasonable to generalize about performance from test-set performance. They use the no free lunch theorems to theoretically demonstrate this, and then show empirical lens on the MovieLens benchmark dataset for recommender systems. They show that multiple models are able to fit the observed data but still perform arbitrarily well on unobserved data.", "questions": "Above, in weaknesses.", "limitations": "Addressed", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is very well-written overall. It tackles a very important question that has many implications given how popular the train-test paradigm is.", "weaknesses": "I’m ultimately not very sure what the prescriptive argument of this work is. I understand that there is value in work for pointing out a problem, but the issues with generalizing performance of ML systems into the real world is widely known and empirically shown (as demonstrated by the presence of the WILDS dataset [https://wilds.stanford.edu/datasets/]. This work provides a theoretical grounding for this, but from the abstract’s final sentence, I expected more implications rather than just gestures to participation and open science. I would have liked to see implications which demonstrate the strengths of approaching this problem from a theoretical perspective, as opposed to just the empirical evidence we have of it.\n\nThere is also increasingly a line of work on the limitations of using observational data (as opposed to data from, e.g., randomized controlled trials, as well as performative prediction, which I felt this work could connect to more, since that seems to be part of the premise of the issue with passive data collection.\n\nA smaller point of confusion, I was unclear sometimes whether you were referring to “benchmark” only as the evaluation dataset or also the training dataset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. I agree that it is important to clarifying the prescriptive argument and the role of participatory methods. I hope that the response to all authors as well as the below additional clarifications can alleviate your concerns. Since everything is addressable via minor clarification updates, I hope this will also allow you to raise your score and confidence.\n\n*I’m ultimately not very sure what the **prescriptive argument** of this work is. I understand that there is value in work for pointing out a problem, but the issues with generalizing performance of ML systems into the real world is widely known and empirically shown (as demonstrated by the presence of the WILDS dataset [[https://wilds.stanford.edu/datasets/]](https://wilds.stanford.edu/datasets/%5D). This work provides a theoretical grounding for this, but from the abstract’s final sentence, I expected more implications rather than just gestures to participation and open science. I would have liked to see implications which demonstrate the strengths of approaching this problem from a theoretical perspective, as opposed to just the empirical evidence we have of it.*\n\n* Thank you for highlighting this issue, I agree that this is an important aspect. There are three aspects in your question that I would like to separate:\n\t* Prescriptive argument: The paper's theoretical results provide indeed *actionable* insights to improve data collection via the $k$-core condition for validity. In short, we would want to collect data such that either increases the $k$-connectivity or the size of the $\\text{rank}(f)$-subgraph. Importantly, we can compute from a given sample graph where to collect data points. Please see the response to all authors for a detailed discussion of this.\n\t* Lack of justification versus impossibility results: If I understand your comment correctly, the key difference between the known results and issues that you are listing is that, to the best of my knowledge, these are based on a \"lack of justification\", i.e., that we know that our usual guarantees do not apply. In contrast, this paper provides much stronger insights in form of rigorous impossibility results. The insights that can be gained from such results are much more substantial and provide a path forward to improving the situation, as in the $k$-core condition above (while just noting a lack of justification can not). Please see the response to all authors for a detailed discussion of this (including also the different contributions of sufficient and necessary conditions).\n\t* Participatory: I agree that the current discussion of this is insufficient, thanks for pointing me to it. The argument for participatory methods stems from the sheer amount of data that would need be collected in a *targeted* way according to the $k$-core scheme above. While we are currently preparing a paper for submission that introduces a novel method for this purpose, I believe that it is beyond the scope of this paper to also cover this aspect in detail, (e.g., it would need to introduce additional concepts related to mechanism design, game design, economics, and the efficient computation of the $k$-core objectives). However, I will add a further discussion why participatory data collection is favorable for the setting of large-amount of data + targeted collection.\n\n*There is also increasingly a line of work on the **limitations of using observational data** (as opposed to data from, e.g., randomized controlled trials, as well as performative prediction, which I felt this work could connect to more, since that seems to be part of the premise of the issue with passive data collection.*\n* I agree that that this is an important aspect. However, I would point out that the paper actually discusses connections to work that goes beyond observational data, i.e., to counterfactual and causal estimators (e.g., see lines 261-265 in the submission). To the best of my knowledge this is also the first impossibility result for such estimators in settings as considered in this paper. As such, the theoretical insights provide, in my opinion, non-trivial insights into the limitations of these popular approaches. Thank you for pointing me to this. I believe it is an important contribution of the paper and will discuss it more clearly in the updated version.\n\t\n*A smaller point of confusion, I was unclear sometimes whether you were referring to “benchmark” only as the evaluation dataset or also the training dataset.*\n* I agree that this is not clear from the current presentation. Part of the issue comes from the fact that in (k-fold) cross-validation part of the training set act as validation set. I will clarify this (maybe in the appendix due to space constraints).", "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": "", "extra_scores": {}}]

Author rebuttal:
Thanks to all reviewers for their insightful feedback, it will help me to clarify important aspects of the paper and improve its impact. Before addressing the reviewers' concerns in detail, I am happy to acknowledge the overall very positive feedback from all reviewers on soundness, contribution, and presentation, e.g.,
- "very well-written", "tackles a very important question that has many implications" (qRpv).
- "a problem of immense importance", "formal and careful writing scheme, which makes it easy to follow and fun to read" (9VqZ)
- "novel insights" into a "highly relevant issue in modern AI" (RViy) 

In the following, I will address two questions that came up in different form across reviewers. Please see the individual responses for further discussions related to points that are specific to a single review. I hope that the following discussion can alleviate the reviewers' concerns and allow to raise their scores since all points can be addressed easily via minor clarifications.

## Practical implications / prescriptive argument
Reviewers raised questions with regard to the practical implications of the theoretical results, i.e., are they useful to improve our data collection efforts? 

I agree that this is an important question and, indeed, the theoretical results of this paper provide *direct* insights into how to improve data collection for model validation via its $k$-core conditions. In particular, lemma 2 and corollary 3 imply two clear objectives for targeted data collection:   
- a) collecting data points that increase the $k$-connectivity of the sample graph. This would increase the complexity of the world that can be assumed such that model validation is still valid for the *entire sample graph*
- b) collecting data points that increase the size of the $\text{rank}(f)$-core of the sample graph, where $\text{rank}(f)$ is the complexity of the world that we want to assume. This would increase the *size of the subgraph* for which a $\text{rank}(f) = k$ assumption would still yield valid model validation

Hence, both objectives are based on the k-core condition and attack it from different angles: increasing the minimal complexity that we can assume for the entire graph or increasing the size of the valid subgraph for a given complexity. Moreover, both objectives can be computed from the known sample graph (doing this efficiently is non-trivial though).
	  
I thank the reviewers for highlighting the issue and agree that it is not very clear from the current write up. Unfortunately, when fitting the content within the page limit, I missed that the discussion of this aspect has suffered. I will include the above discussion in improved form in the updated manuscript.
	  
In this context, the argument for participatory methods stems from the sheer amount of data that would need be collected in a *targeted* way according to the scheme above. While we are currently preparing a paper for submission that introduces a novel method for this purpose, I believe that it is beyond the scope of this paper to also cover this aspect in detail, (e.g., it would need to introduce additional concepts related to mechanism design, game design, economics, and the efficient computation of the $k$-core objectives). However, I will add a further discussion why participatory data collection is favorable for large amount of data + targeted collection.

## Lack of justification versus Impossibility results
Reviewers raised also questions with regard to the significance of the theoretical results relative to known issues and results (e.g. known lack of performance guarantees, known limitations of observational data,)

The key difference between these known issues/results and this work is the difference between a lack of justification (known) and rigorous impossibility results (novel contribution of this work). For instance, while it is clear that standard learning theory does not apply to OOD settings, sampling bias etc. it is not clear that specific methods and practices are not valid. It just means we have no justification for them.

In contrast, the impossibility results in this work are much stronger. They show that there *cannot* be any method that leads to valid results in this setting, even for methods where this is not obvious at all such as counterfactual estimators. These results are also especially important in the context of scaling, which in most cases is exactly passive data collection from complex social systems and which is the dominant approach *today*. The results of this paper establish rigorous limits of this approach and show that alternative approaches are needed (such as the k-core approach discussed above).

Another way to look at it is in terms of *necessary versus sufficient conditions*. Sufficient conditions, which standard learning theory is often based on, provide insights into a specific/narrow case. They are important to motivate the validity of a specific method but do not say much when they are violated. On the other hand, this work establishes necessary conditions which provide conditions that have to hold for *every* case. Since they exclude a large set of hypotheses that otherwise would have to be explored, they provide important insights when the path forward is not entirely clear. This is exactly the case for evaluation in modern AI and why I believe the results of this paper are badly needed.

Again, I would like to thank the reviewers for highlighting this question. I agree that the discussion of this aspect is currently not optimal and will improve it along the above lines in the updated paper.

## Additional results
Per request of RViy, I have also attached a PDF with experimental results for additional settings on widely used datasets, relating the paper's results to reasoning (FB15k-237), graph link prediction (Cora) and extreme classification (Wiki10-31k). Please see also the response to RViy for further details.

Meta-review: The review team agrees that the paper has a clear and rigorous message through an impossibility result: for key tasks in modern AI, we cannot know whether models are valid under current data collection practices. While this conclusion might seem less surprising in hindsight, a theoretical formalization still has a lot of value. Albeit the focus is mainly theoretical, the reviewers appreciated that the paper used the Movielens dataset to illustrate the theoretical points. 

As several reviewers suggested, the paper would further benefit from better connecting its insights to practice, e.g., making the presentation of the paper more accessible to practitioners and discussing in greater depth  how the suggested remedies can be practically implemented in real-world scenarios. Adding more case studies beyond the movielens dataset would also help better illustrate the main message across different AI systems/models.

Overall, the review team, including myself, views positively the theoretical contribution of the paper. I believe the above concerns are minor and can be sufficiently addressed in a revision.
Decision: Accept (poster)