Research map / Learning theory and algorithms / Prediction and decision losses
Trust Regions for Explanations via Black-Box Probabilistic Certification
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.
Introduces black-box probabilistic certification of feature-based explanations, finding the largest l-infinity trust region where an explanation's fidelity stays above a threshold, via three query strategies (unif, unifI, adaptI) with finite-sample and EVT bounds.
Problem
Explanations for black-box models come without guarantees on how stable or widely applicable they are; the goal is to find the largest hypercube around an example where an explanation's quality (e.g., fidelity) provably meets a threshold, using only query access.
Approach
Formulate explanation certification as a search for the largest l-infinity trust region with probabilistic guarantees; propose three sampling strategies (uniform, uniform incremental with Gaussian prototypes, adaptive incremental that concentrates queries on promising prototypes) within a binary-search-like outer loop, with finite-sample bounds and EVT-based asymptotic bounds.
Key results
- On synthetic data, unif, unifI and adaptI converge to the true optimal half-width 1/d and are an order of magnitude or more faster than ZO+ (e.g., d=10^4, Q=10^4: adaptI 88.3 s vs ZO+ 4384.8 s).
- On HELOC, LIME-based explanations let about 80% of LIME queries be saved while covered points satisfy fidelity >= 0.75 with high probability.
- Explanations for examples inside a certified region are more similar to the certified explanation than those outside (top-5 intersection 0.85 vs 0.77; Spearman 0.74 vs 0.61 on HELOC).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Ecertify instead of ZO$^+$ | Synthetic certification with adaptI · Synthetic d=10^4, Q=10^4 | time (s): $4384.76$ -> $88.342$ | Helped |
| Use adaptI rather than unif | Ecertify · Synthetic d=10^4, Q=10^4 | certified half-width: $8.9\times 10^{-5}$ -> $9.4\times 10^{-5}$ | Mixed |
| Use unif for low-dimensional data, unifI for intermediate dimensions, and adaptI for high dimensions | Ecertify · Synthetic benchmarks across dimensions | certified half-width | Mixed |
| Use certified trust-region coverage to select covered HELOC examples for explanation reuse | LIME explanations · HELOC | model query savings: 80% | Helped |
Surprising findings
- LIME trust regions are typically much larger than SHAP's, yet LIME does not dominate SHAP because its fidelity at the example itself can fall below threshold.
Limitations
- Guarantees are probabilistic and rely on random sampling, so reported half-widths may differ from true ones across runs.
- Results on real data depend on explainer settings and threshold choice, and only fidelity is studied as quality metric.
- Synthetic experiments use a simple three-piece piecewise linear model; generality to large deep networks is only shown on a few image models.
Experimental setup
Datasets: ImageNet CIFAR10 HELOC Arrhythmia synthetic piecewise linear function
Benchmarks: synthetic piecewise linear function ImageNet CIFAR10 HELOC Arrhythmia
Metrics: certified half-width running time (s) fidelity threshold satisfaction query savings explanation similarity (top-5 intersection, Spearman rank co
Baselines: ZO+ (zeroth-order toolbox)
Builds on: LIME SHAP randomized smoothing extreme value theory
Closest papers by meaning
- Reliable Post hoc Explanations: Modeling Uncertainty in Explainability (NeurIPS 2021 · similarity 0.88)
- Locally Invariant Explanations: Towards Stable and Unidirectional Explanations through Local Invariant Learning (NeurIPS 2023 · similarity 0.88)
- Constraint-Driven Explanations for Black-Box ML Models (AAAI 2022 · similarity 0.87)
- Auditing Local Explanations is Hard (NeurIPS 2024 · similarity 0.86)
- Improving Perturbation-based Explanations by Understanding the Role of Uncertainty Calibration (NeurIPS 2025 · similarity 0.85)
- Faithful Model Explanations through Energy-Constrained Conformal Counterfactuals (AAAI 2024 · similarity 0.85)
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.