Rewarding High-Quality Data via Influence Functions

Adam Richardson, Aris Filos-Ratsikas, Boi FaltingsarXiv 2019 · arXiv

Introduction

In the era of federated learning and crowdsourced data, a critical challenge has emerged: how to fairly compensate contributors for the quality of their data. When a central entity (the "Center") relies on independent agents to provide data, a flat-fee payment structure often fails. Rational agents are incentivized to provide low-effort, "heuristic" data—such as random noise—to minimize their own costs while still collecting the fee.

This paper proposes a game-theoretic incentive scheme that rewards contributors based on the "influence" their data exerts on a linear regression model's accuracy. By leveraging a novel second-order approximation of influence, the authors demonstrate that truthful reporting of high-quality data is a game-theoretic equilibrium, naturally rewarding early contributors who provide the most significant gains in model performance.

Methodology

The core of the proposed mechanism is the use of Influence Functions. Traditionally, measuring the value of a specific data point requires removing it and retraining the model to observe the change in loss—a process that is computationally prohibitive for large datasets. To address this, the authors introduce several key innovations:

Second-Order Approximation

While previous research utilized first-order Taylor expansions to approximate influence, this paper identifies a critical flaw: the mean influence in such models is zero, making them unsuitable for payment calculations. The authors introduce a second-order term that more accurately captures the actual decrease in the loss function. As shown in the table below, this second-order approach significantly reduces approximation error across multiple real-world and synthetic datasets.

Comparison of approximation errors between 1st and 2nd order methods across various datasets.

Sequential Batching and Initialization

Recognizing that data typically arrives in streams, the authors developed a theory for batch processing, comparing "M-Inclusive" and "M-Exclusive" methods. To handle the "cold start" problem where no model exists for the first contributors, they propose a "knowledge-less initialization" using samples from a uniform distribution to represent a state of zero prior knowledge.

Key Results and Insights

Accuracy and Efficiency

The second-order approximation proves to be remarkably accurate. For instance, on a synthetic linear dataset, the relative error was reduced from $4.8 \times 10^{-3}$ with the first-order method to just $1.3 \times 10^{-8}$ with the second-order method. Beyond accuracy, the approximation offers significant computational advantages. As the input dimensionality of the data increases, the time required for exact retraining grows much faster than the time required for the approximation.

Computation time comparison between exact retraining and approximate influence as input dimensions scale.

The "Early Bird" Advantage

A significant finding of this work is the natural emergence of an "early bird" incentive. Influence naturally decreases as the model matures and more data is collected. Because the model's loss drops most drastically with the initial high-quality contributions, the mechanism automatically allocates higher rewards to early participants, encouraging rapid data reporting.

Game-Theoretic Stability

The authors prove that if agents believe their observations have zero-mean error, reporting truthfully constitutes a Bayes-Nash Equilibrium (BNE). This means that if an agent expects others to be honest, their own most profitable strategy is also honesty. Furthermore, the system is robust against "liars"; agents providing junk data to an independent test set will receive negative rewards and eventually opt out of the system.

Limitations and Future Work

While the current framework provides a robust solution for linear regression, extending these closed-form solutions to complex models like deep neural networks remains a challenge. Additionally, the mechanism assumes the Center can estimate the "cost of effort" for agents to ensure rewards are sufficiently motivating. Future research may also explore integrating differential privacy into the reward calculation to protect contributor data while maintaining fair compensation.

Summary updated

BibTeX
@misc{richardson2019rewarding,
  author = {Adam Richardson and Aris Filos-Ratsikas and Boi Faltings},
  title = {{Rewarding High-Quality Data via Influence Functions}},
  year = {2019},
  eprint = {1908.11598},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.11598},
}
Figure