Research map / Adversarial robustness and security / Certified and empirical robustness
Coevolutionary Algorithm for Building Robust Decision Trees under Minimax Regret
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 CoEvoRDT, a coevolutionary algorithm that alternately evolves decision tree and input-perturbation populations, using mixed Nash equilibrium to build a Hall of Fame, to learn robust decision trees under adversarial accuracy or minimax regret.
Problem
Building robust decision trees against L-infinity input perturbations; adversarial accuracy is overly pessimistic for large perturbations, and minimax regret cannot be directly optimized by existing greedy DT methods.
Approach
Coevolution of competing DT and perturbation populations, with a Hall of Fame built from mixed Nash equilibrium strategies (mixed trees and mixed perturbations), enabling direct optimization of minimax regret or adversarial accuracy; can also seed with outputs of other methods such as FPRDT.
Key results
- CoEvoRDT achieved the lowest max regret on all 20 datasets (e.g., cifar10:0v5 0.241 vs 0.314 for best competitor FPRDT).
- For adversarial accuracy, CoEvoRDT had the best mean on 13 of 20 datasets (5 statistically significant), with FPRDT superior on the remaining 7.
- On fashion-mnist, CoEvoRDT with a single run gave max regret 0.238 vs 0.304 for a single FPRDT run, but FPRDT with 100 repeats still did not reach CoEvoRDT's single-run result.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use CoEvoRDT rather than FPRDT | robust decision trees · 20 benchmark datasets | max regret | Helped |
| add the FPRDT output tree to the CoEvoRDT initial population | CoEvoRDT · 20 benchmark datasets | max regret | Helped |
| add the FPRDT output tree to the CoEvoRDT initial population | CoEvoRDT · 20 benchmark datasets | adversarial accuracy | Helped |
| use CoEvoRDT instead of FPRDT | robust decision trees · adversarial accuracy, 13 of 20 datasets | adversarial accuracy | Helped |
| add Nash mixed trees to the Hall of Fame rather than only the highest-fitness tree (ablation) | CoEvoRDT · fashion-mnist | max regret: .256 -> .240 | Helped |
| replace Nash mixed trees with an equal-probability mixed tree of top K trees (ablation) | CoEvoRDT Hall of Fame · fashion-mnist | max regret: .240 -> .246 | Hurt |
| replace Nash mixed trees with pure trees from the Nash equilibrium (ablation) | CoEvoRDT Hall of Fame · fashion-mnist | max regret: .240 -> .245 | Hurt |
| replace Nash mixed trees with top K highest-fitness trees (ablation) | CoEvoRDT Hall of Fame · fashion-mnist | max regret: .240 -> .249 | Hurt |
| increase Hall of Fame size from 0 to 20 using Nash mixed trees (ablation) | CoEvoRDT · fashion-mnist | max regret: .261 -> .240 | Helped |
| increase the number of independent FPRDT runs from 1 to 100 (ablation) | FPRDT · fashion-mnist | max regret: .304 -> .282 | Helped |
| increase the number of independent CoEvoRDT runs from 1 to 100 (ablation) | CoEvoRDT · fashion-mnist | max regret: .238 -> .228 | Helped |
Surprising findings
- Multiple FPRDT repeats improve adversarial accuracy beyond a single CoEvoRDT run, though for more than 20 repeats both converge to similar values.
- Adversarial accuracy can be maximized by trivial trees (e.g., always predicting one class) when perturbations are large, motivating minimax regret.
Limitations
- Max regret and adversarial accuracy are estimated on a sample of 10^5 random perturbations rather than computed exactly.
- Runtime is higher than FPRDT for a single run (2-8x), and CoEvoRDT is only on par with FPRDT on adversarial accuracy for some datasets.
- Evaluated only on axis-aligned L-infinity perturbations and 20 datasets.
Experimental setup
Datasets: ionos breast diabetes bank Japan:3v4 spam GesDvP har1v2 wine collision-det mnist fashion-mnist
Benchmarks: ionos breast diabetes bank Japan3v4 spam GesDvP har1v2 wine collision-det mnist:1v5 mnist:2v6
Metrics: max regret adversarial accuracy computation time
Baselines: CART Meta Silvae RIGDT-h GROOT FPRDT
Builds on: FPRDT CART Lemke-Howson algorithm
Closest papers by meaning
- Cultivating Archipelago of Forests: Evolving Robust Decision Trees Through Island Coevolution (AAAI 2025 · similarity 0.90)
- Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback (ICML 2025 · similarity 0.85)
- Adversarially Robust Decision Transformer (NeurIPS 2024 · similarity 0.84)
- TTTS: Tree Test Time Simulation for Enhancing Decision Tree Robustness against Adversarial Examples (AAAI 2024 · similarity 0.84)
- On the Adversarial Robustness of Multi-Kernel Clustering (ICML 2025 · similarity 0.84)
- Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays (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.