EUVIMEDEUVIMED entdecken
Crossref

ASSS : Adaptive Stratified Sampling for Shapley-like Values

Junyuan Pang, Jiayao Zhang, Jiazheng Song, Jinfei Liu, Kui Ren

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →