ASSS : Adaptive Stratified Sampling for Shapley-like Values
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-28
DOI: 10.1145/3802016 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Junyuan Pang und 4 weiteren Autor:innen. Die Arbeit nennt 68 Literaturangaben. Gefördert von: NSFC, the Zhejiang Provincial Natural Science Foundation for Distinguished Young Scholars, the Zhejiang Province Pioneer Plan.
Abstract (Originalsprache)
The Shapley-like values, rooted in cooperative game theory, have gained significant recognition in data valuation and query answering. Due to the exponential complexity of their exact computation, many sampling-based approaches have been developed for Shapley-like value estimation. One widely used approach is stratified sampling, where samples are stratified into n strata and n is the number of players. However, while stratified sampling offers variance reduction, its unbiasedness is contingent upon full stratum coverage, necessitating an onerous Ω( n 2 log n ) samples. This dependency renders static n -stratified sampling vulnerable under limited budgets, resulting in biased or unstable estimates. To tackle the problem, we introduce novel adaptive stratification strategies for Shapley-like values to retain unbiasedness for stratified sampling with fewer samples. Based on the intuition ''the fewer samples, the fewer strata'', we develop ASSS ( A daptive S tratified S ampling for S hapley-like values). Two types of approaches ASSS-A (stratify A fter sample) and ASSS-B (stratify B efore sample) are proposed to offer flexible trade-offs between sample efficiency and memory usage. Experimental results on real and synthetic datasets exhibit the effectiveness and efficiency of ASSS-A and ASSS-B.
Förderung
- NSFC
- the Zhejiang Provincial Natural Science Foundation for Distinguished Young Scholars
- the Zhejiang Province Pioneer Plan
Zitieren
APA
Pang, J., Zhang, J., Song, J., Liu, J., & Ren, K. (2026). ASSS : Adaptive Stratified Sampling for Shapley-like Values. Proceedings of the ACM on Management of Data, 4(3), 1-28. https://doi.org/10.1145/3802016
Vancouver
Pang J, Zhang J, Song J, Liu J, Ren K. ASSS : Adaptive Stratified Sampling for Shapley-like Values. Proceedings of the ACM on Management of Data. 2026;4(3):1-28. doi:10.1145/3802016
BibTeX
@article{Pang2026,
author = {Pang, Junyuan and Zhang, Jiayao and Song, Jiazheng and Liu, Jinfei and Ren, Kui},
title = {ASSS : Adaptive Stratified Sampling for Shapley-like Values},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--28},
doi = {10.1145/3802016}
}
EUVIMED