📊 statistics

LARP: Learner-Agnostic Robust Data Prefiltering

This paper introduces and analyzes Learner-Agnostic Robust Data Prefiltering (LARP), a framework for designing prefiltering procedures that guarantee worst-case performance across a diverse set of downstream learners, while quantifying the inherent trade-off between this robustness and the efficiency of learner-specific filtering.

Original authors: Kristian Minchev, Dimitar I. Dimitrov, Nikola Konstantinov

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kristian Minchev, Dimitar I. Dimitrov, Nikola Konstantinov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a librarian in charge of a massive, public library (the dataset). People from all over the world come to this library to read books and write their own stories (the learners or models). Some people write poetry, others write scientific papers, and some write mystery novels. They all have different styles and needs.

The problem is that the library has been invaded by a prankster who has slipped in thousands of fake, torn, or nonsensical pages into the books (data contamination). If the librarians don't clean up these bad pages, the writers will end up writing terrible stories based on bad information.

The Old Way vs. The New Way

The Old Way (Learner-Specific Prefiltering):
Usually, if a specific writer (say, a poet) comes to the library, they might hire a personal editor to go through the books and remove only the pages that would confuse a poet. Another writer (a scientist) would hire a different editor to remove pages that would confuse a scientist.

Pros: The editor knows exactly what the writer needs.
Cons: It's incredibly expensive and slow. If 100 different writers come to the library, you have to hire 100 different editors to clean the same library 100 times.

The New Way (LARP - Learner-Agnostic Robust Prefiltering):
The paper proposes a new strategy: The librarian (the data provider) hires one super-editor to clean the library once before anyone enters. This editor doesn't know who the specific writers are or what they are writing. Their only job is to remove the "worst" pages that would hurt anyone trying to write a story, regardless of the genre.

Pros: You only pay for one cleaning job. It's efficient.
Cons: Because this editor has to protect everyone at once, they might be a bit too cautious. They might remove a page that a poet would have loved, just to be safe for the scientist. This is the "Price of LARP."

The Core Discovery: The "Price of LARP"

The authors call the difference between the "perfect personal editor" and the "one-size-fits-all librarian" the Price of LARP.

Think of it like a safety net.

If you build a safety net just for a tightrope walker (one learner), you can make it very specific and efficient.
If you build a giant safety net for a circus with acrobats, trapeze artists, and jugglers (many learners), the net has to be bigger and stronger to catch everyone. But because it's so big and strong, it might be slightly less comfortable or efficient for the tightrope walker than their custom net would have been.

The paper proves mathematically that this "Price of LARP" is real. When you try to protect a huge, diverse group of learners with a single cleaning process, the results are slightly worse on average than if everyone had their own custom cleaning.

The Trade-Off: Is it Worth It?

The paper asks: If the "one-size-fits-all" cleaning is slightly worse, why do it?

The answer is cost.
Imagine the library is huge (like the internet). Hiring 1,000 personal editors to clean the library for 1,000 different writers would cost a fortune. But hiring one team to clean it once, and then having the 1,000 writers split the bill, is much cheaper.

The authors ran a "game" in their math to show that if the library is big enough, the money saved by splitting the cleaning bill is so huge that it completely makes up for the slight drop in story quality caused by the "Price of LARP."

What They Tested

To prove this works, the authors ran experiments:

Image Tasks: They took a dataset of pictures (CIFAR-10) and added "noise" (wrong labels, like calling a cat a dog). They tried to clean the data once for a group of different AI models (some simple, some complex). They found that while the "group cleaning" wasn't perfect for every single model, it was good enough for everyone, and the "price" (the drop in performance) was small.
Tabular Tasks: They did the same with spreadsheet data (Adult dataset), testing different types of algorithms (like decision trees and neural networks). Again, the "group cleaning" worked well.
Fairness: They even tested a scenario where some learners cared about accuracy and others cared about fairness. They showed that even with these conflicting goals, a single cleaning process could still provide a decent result for everyone.

The Bottom Line

The paper introduces LARP as a way for data providers to clean public datasets once, so that anyone who uses the data later can trust it, even if they are using very different methods.

The Catch: It's not perfect for every single user; there is a small "tax" (Price of LARP) on performance because you are trying to please everyone at once.
The Win: For large datasets, the savings in time and money from doing the cleaning once instead of hundreds of times outweighs that small tax. It's a trade-off between "perfect for one" and "good enough for all, much cheaper."

In short: It's better to have one slightly imperfect filter for the whole world than to have the world pay to filter the data individually for every single person.

Technical Summary: LARP: Learner-Agnostic Robust Data Prefiltering

Problem Definition
Public datasets are foundational to modern machine learning but are frequently contaminated with noisy, inaccurate, or maliciously manipulated samples. While robust learning methods exist to handle such data, they typically focus on finding a single robust learner. This paper addresses a distinct challenge: Learner-Agnostic Robust Data Prefiltering (LARP). The problem is defined as designing a prefiltering procedure $F$ by a data provider that guarantees performance for a pre-specified set of downstream learners $\mathcal{L}$ simultaneously. Unlike learner-specific prefiltering, where the filter is optimized for a single algorithm, LARP requires a single filter to protect the worst-case loss across a heterogeneous set of learners. The authors formalize the objective as minimizing the learner-agnostic risk, defined as the maximum risk over the set $\mathcal{L}$ :
$R_{agn}(F) := \max_{l \in \mathcal{L}} R(l(F(S)), \theta)$
where $S$ is the contaminated dataset and $R$ is the risk function.

Methodology and Theoretical Framework
The paper establishes the feasibility of LARP and analyzes the inherent trade-offs involved in protecting multiple learners simultaneously.

Theoretical Analysis (Scalar Mean Estimation):
- Hardness Result: The authors demonstrate that non-trivial bounds on learner-agnostic risk necessarily depend on the properties of the learner set $\mathcal{L}$ . They provide a lower bound showing that if $\mathcal{L}$ contains learners with highly heterogeneous behaviors (e.g., some efficient, some inefficient for the specific instance), the worst-case risk can be $\Omega(1)$ regardless of the prefiltering, even if a filter exists that minimizes risk for a specific subset.
- Upper Bounds: For a specific family of distributions (strictly smooth distributions) and a set of Huber estimators, the authors prove that a quantile-based prefiltering procedure (removing samples with high outlyingness scores) achieves an upper bound on the learner-agnostic risk. The bound consists of two terms:
  - A standard robust statistics term dependent on the contamination rate $\epsilon$ and dataset size $n$ .
  - A term dependent on the learner set, specifically $\max_{\delta \in \Delta} \delta^2$ , where $\delta$ represents the robustness parameter of the Huber estimators. This term highlights that protecting a broader set of learners (including those with large $\delta$ ) incurs a higher worst-case loss.
- PAC-Style Setup: Using an idealized "oracle" prefiltering procedure that removes a fraction of data based on ground-truth noise status, the authors derive minimax bounds. These bounds show that if the prefiltering effectiveness $t$ exceeds the contamination rate $\epsilon$ , the learner-agnostic risk can be bounded, though the bound depends on the heterogeneity of the learners' robustness parameters ( $A_l, B_l$ ).
The "Price of LARP":
The paper introduces the concept of the Price of LARP, quantifying the utility reduction incurred by using a single learner-agnostic filter compared to the optimal learner-specific filter for each individual. Formally, it is the average reduction in utility across the learner set $\mathcal{L}$ when using a single procedure $F$ versus the optimal $F^*_l$ for each $l$ .
Game-Theoretic Cost-Benefit Model:
To address the potential utility loss, the authors propose a game-theoretic model where downstream learners can split the cost of a single prefiltering procedure. They define the cost of prefiltering as $Cn^\alpha$ (where $\alpha \ge 1$ ). They prove that if the dataset size $n$ is sufficiently large, there exists a payment scheme where the cost savings from splitting the prefiltering effort outweigh the performance loss (Price of LARP), incentivizing all learners to participate in the agnostic scheme.

Empirical Results
The authors empirically measure the Price of LARP on the Adult (tabular) and CIFAR-10 (image) datasets with uniform label noise ( $\epsilon=30\%$ ).

Effectiveness of Prefiltering: In learner-specific settings, prefiltering significantly improves downstream performance (e.g., CIFAR-10 accuracy increased from ~52-62% to 67% for CNNs; SVM F1 scores on Adult improved from 0.17 to 0.48).
Quantifying the Price: The experiments confirm a statistically significant Price of LARP.
- Heterogeneity: The price increases as the heterogeneity of the learner set increases (measured by the number of models $k$ and the range of regularization parameters).
- Contamination Rate: The price generally increases with the contamination rate $\epsilon$ , though it may decrease at very high $\epsilon$ where all learners prefer minimal prefiltering.
- Dataset Size: The dependence of the price on dataset size $n$ is weak.
Risk Heterogeneity: Experiments on the Bank Account Fraud dataset with learners balancing accuracy and fairness (different risk functions) showed similar trends, confirming that conflicting objectives also incur a price.

Key Contributions

Formalization: The paper provides the first theoretical framework for data prefiltering designed to protect the accuracy of a specified set of learners simultaneously, contrasting it with classic robust learning which optimizes for a single learner.
Theoretical Guarantees: It establishes upper bounds on learner-agnostic risk for scalar mean estimation and provides a PAC-style analysis for idealized prefiltering, explicitly linking the bounds to the properties of the learner set.
Empirical Characterization: It quantifies the "Price of LARP" across real-world datasets, demonstrating that while a performance gap exists compared to learner-specific filtering, it is measurable and influenced by learner heterogeneity and contamination rates.
Economic Justification: It offers a game-theoretic argument that for large datasets, the cost savings of a shared prefiltering effort can offset the performance losses, making LARP a viable strategy for data providers and users.

Significance and Claims
The authors position this work as an initial step toward understanding how data providers can perform principled prefiltering to ensure reliability for downstream inference. They claim that:

It is possible to provide meaningful LARP guarantees and empirical improvements across natural families of learners.
There is an inherent trade-off: protecting a broader set of learners leads to more pessimistic accuracy guarantees compared to individual prefiltering.
Despite this trade-off, LARP is beneficial for large-scale datasets because the reduction in repeated data curation costs (when multiple users share the prefiltering effort) can outweigh the performance degradation.
The work aligns with calls for transparency in dataset creation and data-centric strategies for robust AI, offering a mechanism for data providers to certify dataset quality for a wide range of potential users.

The paper concludes modestly, noting that future work should generalize these results to regression/classification tasks, design provably optimal procedures, and extend the framework to settings where data modification (rather than just removal) is permissible.

The Old Way vs. The New Way

The Core Discovery: The "Price of LARP"

The Trade-Off: Is it Worth It?

What They Tested

The Bottom Line

More like this