One Sample Fits All: Approximating All Probabilistic Values Simultaneously and Efficiently

Summary

This paper studies efficient estimation of probabilistic values. It proposes an algorithm which can approximate any probabilistic value with average convergence $O(n \log n)$. It also proposes an improved algorithm for specific cases.

Strengths

This paper provides a solid contribution over previous work. The paper is well written and explains the main ideas clearly.

Weaknesses

If I’m understanding correctly, the algorithm approximates “any” instead of “all” probabilistic values, I.e. it’s a generic algorithm which can approximate any probabilistic value, but it can’t approximate all values simultaneously (one needs to rerun the algorithm for different values). How valuable is the average convergence rate? It’s likely that the easy ones contribute more, and the average rate for the cases of interest is worse.

Questions

See weaknesses.

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

See weaknesses.

Summary

The paper discusses a novel framework for efficiently approximating probabilistic values, such as Beta Shapley values and weighted Banzhaf values. These values are computationally expensive to calculate exactly, calling for approximation techniques. Specifically, they propose the One-sample-Fits-All Framework (OFA), which adheres to the principle of maximum sample reuse and not increasing variance. Besides, two variants, OFA-A (and OFA-S) optimize for all probabilistic values on average (and specific probabilistic values), respectively. Overall, they provide an efficient solution for approximating multiple probabilistic values simultaneously, with theoretical and practical implications.

Strengths

1. The quick approximation of probabilistic values is important. 2. The writing flow is clear and easy to follow (especially Sec. 3). 3. The theoretical part seems reasonable.

Weaknesses

1. The variances (and/or biases) of the estimations are not thoroughly examined; instead, they only consider whether the variances will increase based on the range/value of $m_s$. 2. The authors emphasize "the principle of maximum sample reuse" all the time, and treat it as a key principle. However, they do not provide a formal definition of this principle. 3. Similarly, a formal definition of "one-for-all estimators" is missing. 4. Line 95 mentions that an existing work already achieves $O(n/\epsilon^2 \log (n/\sigma))$, while the proposed OFA-A is $O(n \log (n))$. The significance of the contribution is unclear. 5. What does $q_s$ in line 159 mean?

Questions

See the weaknesses part.

Rating

6

Confidence

1

Soundness

3

Presentation

2

Contribution

3

Limitations

The limitations are not discussed explicitly in the main text.

Summary

This paper presents a novel framework called One-Sample-Fits-All (OFA) for efficiently approximating probabilistic values used in feature attribution and data valuation, such as Beta Shapley values and weighted Banzhaf values. The framework maximizes sample reuse and avoids variance amplification, making it capable of approximating all probabilistic values simultaneously. The authors leverage the concept of (ϵ,δ)-approximation to derive a formula that determines the convergence rate, which they use to optimize the sampling vector. The proposed framework includes two estimators: OFA-A, which is optimized for all probabilistic values on average, and OFA-S, which is fine-tuned for each specific probabilistic value. Empirical results demonstrate that OFA-A achieves the fastest known convergence rate for Beta Shapley values and competitive rates for weighted Banzhaf values.

Strengths

1. The paper introduces a novel one-sample-fits-all framework that can approximate a wide range of probabilistic values efficiently, addressing a significant gap in the literature. The use of (ϵ,δ)-approximation to derive convergence rates and optimize the sampling vector adds strong theoretical backing to the proposed method. 2. The OFA-A estimator achieves the best known time complexity for certain probabilistic values, indicating its computational efficiency.

Weaknesses

1. The empirical results are demonstrated on a classification task using LeNet and small datasets like MNIST. 2. The paper does not discuss much about the implementation details - the theoretical concepts and optimization processes might be complex for practitioners without a strong background in cooperative game theory and advanced statistical methods.

Questions

The paper does provide an extensive theoretical proof regarding scalability of the pipeline, but there is limited explorations in terms of emperical results for scalable real life datasets and problems. It would be nice to see some comments on that. While the scalability is theoretically supported, further empirical validation on larger datasets would strengthen the claim.

Rating

6

Confidence

1

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes the authors have indicated the weakness of their proposed method

Summary

The paper studies efficient estimators for probabilistic values, with applications in data valuation and feature attribution. Since the computation of probabilistic values requires an exponential number of utility function evaluations, efficient estimation of probabilistic values is necessary. Existing approaches for this either contain amplifying scalers that degrade the convergence rate or fail to perform maximum sample re-use (i.e. utility evaluations are not used to update the probabilistic value estimates for all players). The paper proposes an algorithm that solves both the above challenges at once, thus providing a one-for-all estimator that achieves superior time complexity on average. The theoretical results are supported by several experimental results that validate improvements in speed of convergence as compared to the previous methods.

Strengths

The paper provides a simple algorithm that updates the probabilistic values of all n players at once, thus improving our ability to compute multiple probabilistic values and allowing us to evaluate the best one for downstream applications. Since the exponential number of utility evaluations hinders the ability to perform this evaluation, this paper could be an important step towards understanding how to improve the time complexity of such methods. The paper carefully compares existing methods under the axes of amplifying scalers and maximum sample reuse, providing an intuitive goal for improved estimation algorithms. The experimental assessment supports the theory developed in the paper regarding (\epsilon, \delta) convergence rates.

Weaknesses

The proposed algorithm depends on obtaining a good sampling vector q. Although the paper addresses this in sections 4.1 and 4.2, it would be helpful to discuss this further (e.g., challenges in solving the minimization problem in 4.1, alternatives to the faster generic estimator in 4.2, etc). The experimental results vary the size of the dataset up to 256. In real-world data valuation tasks with larger sample sizes, would it be harder to scale this method despite beating all the baselines? It would be helpful to discuss the limitations of the proposed approach both in terms of theoretical analysis and applicability to tasks like data valuation (It does talk about the limitations under proposition 3, but it would be helpful to have a separate discussion on limitations)

Questions

Please see the weaknesses

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Although broader societal impacts may not apply to this paper, this work should have a section on the limitations of the proposed algorithm in a separate section in addition to the brief discussion in Proposition 3.