No Free Delivery Service: Epistemic limits of passive data collection in complex social systems

Maximilian Nickel

Abstract

Modern AI evaluation relies on the "train-test" paradigm, assuming that performance on a held-out set guarantees generalization. This paper demonstrates that for passive data collection in complex social systems—characterized by heavy-tailed distributions—this assumption is mathematically invalid. We define an epistemic limit where the true risk cannot be bounded, rendering standard validation metrics uninformative. Through analysis of $k$-cores and empirical studies on MovieLens and FB15K, we show that scaling data collection is an inefficient solution and that current benchmarks may provide a false sense of security, particularly across different demographic groups.

Introduction: The Problem with Passive Data

In traditional machine learning, validation is straightforward: we actively control data collection, sampling independently and identically distributed (i.i.d.) points from a target distribution. However, modern AI systems like Large Language Models (LLMs) and recommender systems rely on passive data collection. We scrape the web or observe user clicks—data that already exists rather than data we have curated to be representative.

Maximilian Nickel argues that this creates a fundamental "epistemic limit." In complex social systems, data follows power-law distributions where a few items are ubiquitous and the vast majority reside in a "long tail." This paper asks a critical question: Given our current data collection methods, can we actually know if a model performs well? The answer is often "no."

The Epistemic Limit of Passive Data

The paper defines test validity formally: an inference setting is test-valid only if the difference between the estimated test error and the true risk can be bounded across all "possible worlds" consistent with the observed data.

Conceptual framework of model validation under passive data collection.

When we look through the "keyhole" of passive data, many different "possible worlds" (underlying truths) could explain our observations perfectly. If these worlds differ significantly in the unobserved regions, our test score is a false signal of reliability.

Methodology: $k$-cores and Bregman Divergences

To quantify this limit, the author employs graph theory and matrix representation. Social interactions are modeled as partially observed matrices. A key finding links test validity to the $k$-core of the sample graph. For a model to be validated at a complexity level $k$, the data must be dense enough that every entity is part of a $k$-core—a subgraph where every node has at least $k$ neighbors.

Using Bregman Divergences, the paper proves that if data fails the $k$-core requirement, the "true" world could be arbitrarily different from the model's predictions, even with a perfect fit on the test set. This makes passive data "induction-hostile."

Empirical Evidence across Domains

The theoretical results are validated using benchmarks representing passive data: MovieLens 100k (recommender systems) and FB15K (knowledge graphs/symbolic reasoning).

Heavy-tailed distributions and domain mapping for recommender systems and symbolic reasoning.

In these datasets, the distribution of observations is extremely skewed. On MovieLens, the author demonstrated that multiple "possible worlds" explain the observed data perfectly but differ by up to 77% on unobserved data. This confirms that benchmark scores in these settings are often uninformative of true generalization.

The Scaling Trap and Demographic Inequity

A common response to poor performance is to "scale up." However, Corollary 2 (Inefficiency of Scaling) shows that the amount of data needed to reach a valid test setting scales linearly or polynomially with the domain size. For a domain with $10^7$ entities, validating a random node would require an astronomical $2 \cdot 10^{21}$ samples—far more data than exists.

Furthermore, this limit isn't distributed equally. In MovieLens experiments, test validity varied by demographic: 67% of "technicians" could be validated, but only 14% of "homemakers." This suggests that benchmarks might be "valid" for dominant groups while offering an illusion of quality for others.

Conclusion: Beyond Passive Scraping

The "No Free Delivery" theorem suggests we cannot simply scale our way out of this epistemic crisis. The paper calls for a shift from passive scraping to participatory data curation and decentralized methods. To truly validate AI in complex social systems, we must actively fill the gaps in our knowledge rather than relying on the biased residues of digital interaction.

Summary updated

BibTeX
@inproceedings{nickel2024no,
  author = {Maximilian Nickel},
  title = {{No Free Delivery Service: Epistemic limits of passive data collection in complex social systems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=XZ0fpoAKEB},
}
Figure