Research map / Learning theory and algorithms / Prediction and decision losses
ElliCE: Efficient and Provably Robust Algorithmic Recourse via the Rashomon Sets
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.
Proposes ElliCE, which approximates the epsilon-Rashomon set by an ellipsoid built from the loss Hessian and solves a convex QCQP for counterfactuals that stay valid across that ellipsoid.
Problem
Counterfactual explanations for algorithmic recourse become unreliable when the Rashomon set (near-optimal models) is large, since a recourse valid for one model may fail for another; existing robust methods are slow (MILP) or lack guarantees over the near-optimal set.
Approach
Approximates the Rashomon set by an ellipsoid defined by the loss Hessian, derives a closed-form worst-case logit over that ellipsoid, and turns robust counterfactual search into a convex QCQP with provable validity, uniqueness, Lipschitz stability, and alignment with top Hessian eigenvector.
Key results
- On MLPs with data-supported counterfactuals, ElliCE achieves robustness 1.00 on FICO and German across Retrain, Dropout Rashomon, and AWP evaluators, versus T:Rex at 0.83 on FICO Retrain.
- ElliCE is 3.9x to 685x faster than T:Rex or Delta-robustness for data-supported MLP counterfactuals, with absolute runtimes under two seconds.
- Robustness-proximity trade-off is shown: ElliCE gets highest robustness at a given length, but robust counterfactuals can be longer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ElliCE instead of DeltaRob for robust recourse | MLP counterfactual generation · FICO, AWP | robustness: 0.96 $\pm$ 0.07 -> 1.00 $\pm$ 0.00 | Helped |
| Use ElliCE instead of DeltaRob for robust recourse | MLP counterfactual generation · German Credit, Random Retrain | robustness: 0.98 $\pm$ 0.01 -> 1.00 $\pm$ 0.00 | Helped |
| Use ElliCE instead of T:Rex for robust recourse | MLP counterfactual generation · Diabetes, Dropout Rashomon | robustness: 0.90 $\pm$ 0.08 -> 0.99 $\pm$ 0.02 | Helped |
| Use ElliCE instead of T:Rex for counterfactual proximity | MLP counterfactual generation · FICO | L2 proximity: 2.77 $\pm$ 0.19 -> 3.53 $\pm$ 0.17 | Hurt |
| Use ElliCE instead of DeltaRob for counterfactual proximity | MLP counterfactual generation · German Credit | L2 proximity: 3.45 $\pm$ 0.06 -> 3.48 $\pm$ 0.10 | Hurt |
| Use ElliCE instead of ROAR for counterfactual proximity | MLP counterfactual generation · Diabetes | L2 proximity: 1.86 $\pm$ 0.24 -> 2.15 $\pm$ 0.39 | Hurt |
| Use ElliCE instead of T:Rex for data-supported counterfactual generation | MLP · FICO | runtime: $7.006 \pm 0.058$ -> $1.792 \pm 0.123$ | Helped |
| Use ElliCE instead of Delta Rob for data-supported counterfactual generation | MLP · COMPAS | runtime: $360.480 \pm 6.701$ -> $0.526 \pm 0.011$ | Helped |
Surprising findings
- Delta-robustness and PROPLACE needed very different hyperparameter ranges for linear models versus MLPs, while ElliCE was consistent across model types.
Limitations
- Ellipsoidal approximation is a simplification of the true Rashomon set.
- For neural networks, analysis captures only local rather than global model multiplicity.
- Formal guarantees on uniqueness, stability, and trade-off do not transfer to the input space of MLPs due to non-convexity.
Experimental setup
Datasets: Australian Credit FICO German Credit Banknote Parkinson's Diabetes COMPAS Wine Quality Extended Iris
Benchmarks: Australian Credit FICO German Credit Banknote Parkinson's Diabetes COMPAS Wine Quality Extended Iris
Metrics: robustness L2 proximity LOF plausibility runtime
Baselines: T:Rex Delta-robustness (Interval Abstractions) PROPLACE ROAR
Builds on: Rashomon effect T:Rex Delta-robustness ROAR PROPLACE
Closest papers by meaning
- From Rashomon Theory to PRAXIS: Efficient Decision Tree Rashomon Sets (ICML 2026 · similarity 0.88)
- Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse (ICLR 2023 · similarity 0.87)
- The Rashomon Set Has It All: Analyzing Trustworthiness of Trees under Multiplicity (NeurIPS 2025 · similarity 0.87)
- Promoting Counterfactual Robustness through Diversity (AAAI 2024 · similarity 0.85)
- From Search to Sampling: Generative Models for Robust Algorithmic Recourse (ICLR 2025 · similarity 0.85)
- LeapFactual: Reliable Visual Counterfactual Explanation Using Conditional Flow Matching (NeurIPS 2025 · 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.