Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values
Banzhaf values;Shapley values;Kernel SHAP;Leverage Scores;Least Squares Regression
Yes
No ethics review needed.
1.Broader baselines and empirical settings. For example, the settings for “Noisy” are kind of simple. What’s the variance of the added noise? The study claims to evaluate the Banzhaf values of general set functions and suggests expanding the dataset range to explore more scenarios, such as MNIST, FMNIST, and CIFAR-10.

Minor:
line106： What does  mean, and is it consistent with Data Banzhaf[1] ? Does it represent -approximation in -norm.

Ref. 
[1]Jiachen T. Wang and Ruoxi Jia. Data banzhaf: A robust data valuation framework for machine learning. In AISTAT,  2023.
1. Few algorithms have been proposed to compute Banzhaf values for arbitrary set functions. This paper addresses this gap by introducing an algorithm that overcomes this limitation, representing a significant improvement. It also experimentally evaluates the estimator in relation to the true Banzhaf values,rather than relying just on convergence metrics.

2. Theorem 3.2 states that the Banzhaf values are the solution to the linear regression problem defined by matrix A and vector b. Theorem 3.3 is a standard guarantee for leverage score sampling. Corollary 3.4 Kernel Banzhaf can recover a solution  that has near optimal objective value but is far from the optimal solution .

3. This work compared the Kernel Banzhaf with state-of-the-art estimators across eight popular datasets, and the results confirmed the superior performance of the Kernel Banzhaf.
This work applies ideas proven effective for estimating Shapley values to Banzhaf values, introducing Kernel Banzhaf, a regression-based approximation algorithm for estimating Banzhaf values of general set functions. The authors demonstrate through extensive experiments that Kernel Banzhaf has significant advantages in sample efficiency and noise robustness. Additionally, they provide theoretical guarantees for the algorithm's performance.
1.While the theoretical underpinnings are well-developed, the paper may not provide a comprehensive assessment of the computational efficiency and practicality of the proposed method in real-world applications. Like the computational complexity analysis or empirical time/memory cost.

2.The study demonstrates the robustness of the Kernel Banzhaf algorithm primarily through relevant experiments. Figure 4 shows the horizontal line representing Kernel Banzhaf, which remains unchanged as noise levels increase.Previous studies, such as Data Banzhaf[1], have provided theoretical proof of robustness using the Safety Margin. This study may need to supplement related theoretical proofs.
Yes
No ethics review needed.
It is generally possible to achieve variance reduction by combining multiple estimators. 
Would it be possible to create an estimator with lower variance by mixing the proposed method with MC and MSR estimators using appropriate weights?
If further variance reduction can be achieved, it would be highly useful for practical applications.
A key strength of this research is the simplicity of the proposed estimator for the Banzhaf value. The method involves simply sampling subsets and solving a least squares problem, making the computation highly straightforward. Additionally, the theoretical complexity of the sampling process is studied. While an exact calculation requires all the $2^n$ subsets, the proposed approach reduces this to approximately $O(n \log n / \delta)$. This ease of implementation, along with the theoretical guarantees, gives the study valuable for applications involving the Banzhaf value.

The discussion in Appendix H regarding the (un)necessity of efficiency axiom is particularly interesting. I think the efficiency axiom is not necessary within the context of feature attribution. Therefore, this discussion supporting the usefulness of the Banzhaf value is especially important.
In this paper, the authors proposed an efficient method for approximating the Banzhaf value. The Banzhaf value, similar to the Shapley value, is a measure used in cooperative game theory. Unlike the Shapley value, however, the Banzhaf value assigns equal weights to all subsets. The authors showed that the Banzhaf value can be represented as the solution to a least squares problem, and they propose a sampling-based approach to approximate this least squares solution. Through experiments, the authors demonstrated that their method achieves higher accuracy than other existing methods for approximating the Banzhaf value.
There are no obvious weaknesses I found in this paper. If I have to mention a potential drawback, it might be that the Banzhaf value is less well-known compared to the Shapley value. However, as the authors discuss in Appendix H, the Banzhaf value can serve as a viable alternative to the Shapley value, and it would be ideal to see it become more widely studied alongside the Shapley value in the future.
Yes
No ethics review needed.
* The MSR estimator should obtain sample complexity that is comparable to proposer method under the classification setting. How you explain the fact Kernel Benzhaf obtains better results in the experiments for the classification datasets? Is that true in general or not?
* Can't the theoretical results of Wang & Jia be extended to regression by normalizing the responses? 
* In the contribution you write: "We argue that, up to log factors and the dependence on ϵ, our analysis is the best possible". What you mean by best? Do you mean tight? Or do you mean it is the best possible estimator for Banzhaf values?
* The proposed estimator seems to be more precise than current practice and hold theoretical guarantees.
* Experiments show that Kernel Banzhaf empirically has better sample complexity on eight tabular datasets.
This paper proposes a new estimator for Banzhaf, which can be used to derive feature importance for general ML models. Theoretical analysis provides control over the error of the estimator.
* While the authors show that their approach achieves good sample complexity, it is unclear how meaningful that improvement is in practice from the current manuscript. I would make two suggestions: (1) can you use the proposed method to analyze datasets of large sizes in which MC and MSR fail to produce meaningful results but Kernel Banzhaf succeeds? (2) For the datasets you analyze, can you show that Kernel Banzhaf recovers feature ranking (overall and among the top-k features), or a similar quantity the practitioners would typically be interested in?
* This work is similar to Musco & Witter, and while there are differences (Banzhaf instead of Shapley, and the theoretical analysis required different techniques), the level of novelty in this work is not very high.
@inproceedings{
anonymous2024kernel,
title={Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=7JlL8ECPJ7},
note={under review}
}
Banzhaf values offer a simple and interpretable alternative to the widely-used Shapley values. We introduce Kernel Banzhaf, a novel algorithm inspired by KernelSHAP, that leverages an elegant connection between Banzhaf values and linear regression. Through extensive experiments on feature attribution tasks, we demonstrate that Kernel Banzhaf substantially outperforms other algorithms for estimating Banzhaf values in both sample efficiency and robustness to noise. Furthermore, we prove theoretical guarantees on the algorithm's performance, establishing Kernel Banzhaf as a valuable tool for interpretable machine learning.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Banzhaf values Shapley values Kernel SHAP Leverage Scores Least Squares Regression
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/3d0bd6b8622faa254d17631050669055dfd3460e.pdf
interpretability and explainable AI
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/9c6a83da640fa95ae49a10b9d390538e230e87c4.zip
Kernel Banzhaf: A Fast and Robust Estimator for Banzhaf Values
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission