Research map / Adversarial robustness and security / Certified and empirical robustness
On Lp-norm Robustness of Ensemble Decision Stumps and Trees
Yihan Wang, Huan Zhang, Hongge Chen, Duane Boning, Cho-Jui Hsieh
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace ℓ∞ certified training with ℓ1 certified training for boosted stumps (ℓ1 robust training) | ensemble decision stumps · MNIST 2 vs. 6 and Fashion-MNIST shoes, ℓ1 verified error | ℓ1 verified test error: e.g. 44.22% -> 33.46% (MNIST 2 vs. 6, ϵ1=1.0) | Improved |
| Replace ℓ∞ certified training with ℓ1 certified training for boosted stumps | ensemble decision stumps · breast-cancer and diabetes, ℓ1 verified error | ℓ1 verified test error: breast-cancer 99.27% -> 35.77% (improves); diabetes 35.06% -> 31.82% (improves) | Mixed |
| Replace ℓ∞ certified training with ℓ1 certified training for boosted trees | ensemble decision trees · Fashion-MNIST shoes, MNIST 1 vs. 5, MNIST 2 vs. 6, breast-cancer (ℓ1 verified error) | ℓ1 verified test error: e.g. 89.54% -> 65.18% (Fashion-MNIST shoes); breast-cancer 99.63% -> 47.05% | Improved |
| Use the DP-based approximate ℓ1 verification instead of MILP for stump ensembles | ensemble decision stumps · ℓ1 verification on five datasets | verification time per sample: e.g. 0.11s MILP vs 0.0013s DP on MNIST 1 vs 5 (about 71X speedup) | Improved |
| Use the DP-based approximate ℓ1 verification instead of MILP for stump ensembles | ensemble decision stumps · Fashion-MNIST shoes ℓ1 verification | verified err.: 10.45% (MILP) vs 10.55% (DP) | Hurt |
| Use approximate multi-level ℓ1 verification (K=3, L=2) instead of MILP for tree ensembles | ensemble decision trees · breast-cancer, diabetes, Fashion-MNIST shoes, MNIST 1 vs. 5 ℓ1 verification | verified err. and avg. time: verified error matches MILP on 4 of 5 datasets (e.g. 8.03% vs 8.03%); MNIST 2 vs. 6 8.60% MILP vs 8.80% approx; speedups | Mixed |
| Use ℓ0 complete verification for stump ensembles (linearithmic algorithm) | ensemble decision stumps · five datasets, ϵ0=1 | verified err. and avg. time: avg time under 0.1 s per sample (e.g. 0.010s on MNIST 1 vs 5) | Improved |
| Use an ε schedule (gradually increasing ε) during certified ℓp training instead of a large fixed ε from the start | ensemble stumps and trees ℓp training · ℓp certified training | qualitative (argued) | No clear effect |
Closest papers by meaning
- Robustness Verification of Tree-based Models (NeurIPS 2019 · similarity 0.90)
- (De-)Randomized Smoothing for Decision Stump Ensembles (NeurIPS 2022 · similarity 0.88)
- Robustness Verification of Multi-Class Tree Ensembles (AAAI 2024 · similarity 0.87)
- Probably Approximately Global Robustness Certification (ICML 2025 · similarity 0.86)
- Robust Loss Functions for Training Decision Trees with Noisy Labels (AAAI 2024 · similarity 0.84)
- Sparse Transfer Learning Accelerates and Enhances Certified Robustness: A Comprehensive Study (AAAI 2025 · 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.
