Research map / Learning theory and algorithms / Prediction and decision losses
Auditing Local Explanations is Hard
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical study of auditing local explanations (LIME/Anchors/gradient-style) via black-box queries of predictions and explanations, giving sample complexity bounds tied to explanation locality and arguing that high-dimensional local explanations are practically unauditable.
Problem
Whether third-party auditors or user collectives, with only pointwise access to a classifier's decisions and local explanations, can verify that explanations are faithful to the model, and how many samples this requires.
Approach
Defines an explainability loss for local explanations (region R_x and local classifier g_x), links auditing sample complexity to the "locality" (minimum probability mass of local regions), proves matching-order lower and upper bounds (roughly 1/locality), and shows that for concentric-sphere data gradient-style explanations have exponentially small locality in dimension.
Key results
- Lower bound: auditing with n <= c0/(max(eps1,eps2) * lambda^(1-c1*max(eps1,eps2))) points fails with probability at least 1/3, so sample requirements scale roughly as 1/locality.
- Upper bound: an auditor succeeds with sample complexity about O~(1/eps2^2 + 1/(lambda gamma^2 eps1^2)), matching the 1/lambda dependence of the lower bound as eps go to 0.
- For concentric-sphere data in dimension d, any linear explanation at an outer-sphere point has either local loss at least 1/6 or local mass at most 3^(1-d).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| decrease the explanations' locality | Auditing local explanations with pointwise decisions and explanations · Auditing local explanations | sample complexity: inversely proportional to its locality; \Omega\left(\frac{1}{\lambda^{1 - O(\epsilon)}}\right) | Hurt |
| use reasonably large local regions | Auditing local explanations · Auditing local explanations | sample complexity: \tilde{O}\left(\frac{1}{\epsilon_2^2} + \frac{1}{\lambda\gamma^2\epsilon_1^2} \right) | Helped |
| use a locally linear explanation with low local loss | Any explainer in \mathcal{E}(\mathcal{B}_d, \mathcal{L}_d) on the concentric-sphere example · Concentric-sphere example | local mass: \Lambda(E, f, x) \leq 3^{1-d} | Hurt |
| use a larger local neighborhood for a linear explanation | Locally linear explanations on the concentric-sphere example · Concentric-sphere example | local loss | Hurt |
| use a neighborhood small enough for local linearity | Locally linear explanations on the concentric-sphere example · Concentric-sphere example | local mass: exponentially small with respect to the data dimension | Hurt |
| maximize local mass | Anchors · Low-dimensional tabular data | auditing feasibility | Helped |
| apply Anchors to image classifiers using its modified locality objective | Anchors · High-dimensional image data | locality | Hurt |
Surprising findings
- Under the framework, auditing pointwise explanations in high dimensions may be practically impossible for user collectives without model access.
- Anchors-style explanations on images are argued to have extremely small locality because the local regions contain unrealistic superimposed images.
Limitations
- Passing the audit is necessary but not sufficient for trust; targeted misleading explanations are not detected.
- Shapley-value methods do not fit the local explanation definition, so the framework does not cover them.
- The high-dimensional claims for LIME, SmoothGrad and Anchors on images are argued from examples and figures rather than measured locality.
Experimental setup
Metrics: sample complexity explainability loss locality
Builds on: LIME Anchors SmoothGrad
Closest papers by meaning
- Trust Regions for Explanations via Black-Box Probabilistic Certification (ICML 2024 · similarity 0.86)
- Robust ML Auditing using Prior Knowledge (ICML 2025 · similarity 0.85)
- SMI: Statistical Membership Inference for Reliable Unlearned Model Auditing (NeurIPS 2026 · similarity 0.84)
- Selective Explanations (NeurIPS 2024 · similarity 0.84)
- Automated Assessment of Fidelity and Interpretability: An Evaluation Framework for Large Language Models’ Explanations (Student Abstract) (AAAI 2024 · similarity 0.84)
- Adaptive auditing of AI systems with anytime-valid guarantees (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.