# Addressing Budget Allocation and Revenue Allocation in Data Market Environments Using an Adaptive Sampling Algorithm

arXiv: https://arxiv.org/abs/2306.02543 · HTML: https://mlsanity.com/paper/2306.02543/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 48 references that are in the map.
- First posted on arXiv 5 Jun 2023.

## Builds on (most cited first, 27 of 27)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Data Shapley: Equitable Valuation of Data for Machine Learning](https://mlsanity.com/paper/1904.02868/) (2019)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Towards Efficient Data Valuation Based on the Shapley Value](https://mlsanity.com/paper/1902.10275/) (2019)
- [Beta Shapley: a Unified and Noise-reduced Data Valuation Framework for Machine Learning](https://mlsanity.com/paper/2110.14049/) (2021)
- [A Principled Approach to Data Valuation for Federated Learning](https://mlsanity.com/paper/2009.06192/) (2020)
- [Data Valuation using Reinforcement Learning](https://mlsanity.com/paper/1909.11671/) (2019)
- [A Distributional Framework for Data Valuation](https://mlsanity.com/paper/2002.12334/) (2020)
- [A Marketplace for Data: An Algorithmic Solution](https://mlsanity.com/paper/1805.08125/) (2018)
- [A Survey on Data Pricing: from Economics to Data Science](https://mlsanity.com/paper/2009.04462/) (2020)
- [Efficient computation and analysis of distributional Shapley values](https://mlsanity.com/paper/2007.01357/) (2020)
- [Model-based Pricing for Machine Learning in a Data Marketplace](https://mlsanity.com/paper/1805.11450/) (2018)
- [Finding Influential Training Samples for Gradient Boosted Decision Trees](https://mlsanity.com/paper/1802.06640/) (2018)
- [Online Variance Reduction for Stochastic Optimization](https://mlsanity.com/paper/1802.04715/) (2018)
- [Revenue Maximization for Query Pricing](https://mlsanity.com/paper/1909.00845/) (2019)
- [A Note on "Efficient Task-Specific Data Valuation for Nearest Neighbor Algorithms"](https://mlsanity.com/paper/2304.04258/) (2023)
- [Adaptive Importance Sampling for Finite-Sum Optimization and Sampling with Decreasing Step-Sizes](https://mlsanity.com/paper/2103.12243/) (2021)
- [Optimal Data Acquisition for Statistical Estimation](https://mlsanity.com/paper/1711.01295/) (2017)
- [Online Variance Reduction with Mixtures](https://mlsanity.com/paper/1903.12416/) (2019)
- [Data Acquisition for Improving Machine Learning Models](https://mlsanity.com/paper/2105.14107/) (2021)
- [Adaptive Client Sampling in Federated Learning via Online Learning with Bandit Feedback](https://mlsanity.com/paper/2112.14332/) (2021)
- [Optimal and Quantized Mechanism Design for Fresh Data Acquisition](https://mlsanity.com/paper/2006.15751/) (2020)
- [L-SVRG and L-Katyusha with Adaptive Sampling](https://mlsanity.com/paper/2201.13387/) (2022)

## Built on by (most cited first, 5 of 5)

- [What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions](https://mlsanity.com/paper/2405.13954/) (2024)
- [DAVED: Data Acquisition via Experimental Design for Data Markets](https://mlsanity.com/paper/2403.13893/) (2024)
- [2D-OOB: Attributing Data Contribution Through Joint Valuation Framework](https://mlsanity.com/paper/2408.03572/) (2024)
- [ALI-DPFL: Differentially Private Federated Learning with Adaptive Local Iterations](https://mlsanity.com/paper/2308.10457/) (2023)
- [D2M: A Decentralized, Privacy-Preserving, Incentive-Compatible Data Marketplace for Collaborative Learning](https://mlsanity.com/paper/2512.10372/) (2025)

## Abstract (arXiv)

High-quality machine learning models are dependent on access to high-quality training data. When the data are not already available, it is tedious and costly to obtain them. Data markets help with identifying valuable training data: model consumers pay to train a model, the market uses that budget to identify data and train the model (the budget allocation problem), and finally the market compensates data providers according to their data contribution (revenue allocation problem). For example, a bank could pay the data market to access data from other financial institutions to train a fraud detection model. Compensating data contributors requires understanding data's contribution to the model; recent efforts to solve this revenue allocation problem based on the Shapley value are inefficient to lead to practical data markets. In this paper, we introduce a new algorithm to solve budget allocation and revenue allocation problems simultaneously in linear time. The new algorithm employs an adaptive sampling process that selects data from those providers who are contributing the most to the model. Better data means that the algorithm accesses those providers more often, and more frequent accesses corresponds to higher compensation. Furthermore, the algorithm can be deployed in both centralized and federated scenarios, boosting its applicability. We provide theoretical guarantees for the algorithm that show the budget is used efficiently and the properties of revenue allocation are similar to Shapley's. Finally, we conduct an empirical evaluation to show the performance of the algorithm in practical scenarios and when compared to other baselines. Overall, we believe that the new algorithm paves the way for the implementation of practical data markets.