Pith. sign in

REVIEW 4 major objections 6 minor 23 references

Cultivating Archipelago of Forests: Evolving Robust Decision Trees through Island Coevolution

T0 review · 4 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An island-based algorithm coevolves trees and attacks per island, migrates top individuals, and weights the final forest by a mixed Nash equilibrium, beating prior robust-tree methods on 20 benchmarks.

desk verdict Island migration plus MNE weighting is a real, well-ablated empirical improvement over the authors' own CoEvoRDT, but the minimax theorem does not justify the Nash voting weights as used. read the letter →

arxiv 2412.13762 v1 pith:7MPIWDDJ submitted 2024-12-18 cs.LG cs.NE

Adam Żychowski , Andrew Perrault , Jacek Mańdziuk This is my paper · ORCID
classification cs.LGcs.NE
keywords islandmodelcoevolutionaryalgorithmdecisionforestadversarialrobustnessminimaxregretmixedNashequilibriumevolutionarycomputationensembleweighting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that separating evolution into islands, exchanging top trees between them, and weighting the final forest by a mixed Nash equilibrium of a zero-sum tree-versus-perturbation game produces ensembles that beat existing robust-tree and robust-forest methods on both adversarial accuracy and minimax regret across 20 datasets. The reason to care is practical: decision trees stay interpretable, and this recipe improves their resistance to attacks without giving up that interpretability. The headline evidence is a best average adversarial accuracy of 0.784 and a best average max regret of 0.082 among the tested forest ensembles.

What carries the argument

The load-bearing mechanism is a zero-sum game between two strategy sets: the fittest decision tree from each island is the tree player's pure strategy, and the union of all island perturbation populations is the perturbation player's pure strategy set. The mixed Nash equilibrium of this game, computed with a standard equilibrium algorithm, supplies the voting weights; in a zero-sum game the minimax theorem guarantees that this weighting maximizes the robustness metric over the strategies considered. Around this, the island model with periodic migration of top trees and perturbations maintains diversity, and distinct per-island training sets sampled with replacement act like a random forest's bagging.

What would settle it

Compare ICoEvoRDF against its equal-voting ablation on a held-out perturbation set produced by a different attack procedure than the one used during evolution; if equal voting matches or beats Nash voting there, the paper's claimed weighting advantage does not transfer beyond the coevolved attack distribution.

Watch

Extended reading notes

Core claim

The central discovery asserted by the paper is that an island model changes the game for coevolutionary robust forests. Instead of one population, multiple islands each coevolve a decision-tree population against a perturbation population, and every ng generations the most fit trees and perturbations migrate between neighboring islands in a ring topology. At the end, the fittest tree from each island enters a zero-sum game against the union of all island perturbation populations, and the mixed Nash equilibrium of that game gives the voting weights. Compared with equal voting, Nash voting adds a small but consistent gain, and compared with repeated independent runs of the single-island method, migration adds a larger gain. The paper reports the best average adversarial accuracy (0.784) and best average max regret (0.082) among the forest methods tested on the 20 benchmarks, and shows that seeding one island with trees from an existing robust-tree algorithm can improve the mixture further.

Load-bearing premise

The load-bearing premise is that the perturbations evolved on the islands are representative enough of the attacks used to score the final forest, so the Nash voting weights computed on that internal game transfer to evaluation.

Editorial extensions

If this is right

  • Seeding one island with an existing robust-tree method such as FPRDT makes the final forest at least as good as that method and often better, so ICoEvoRDF can act as a wrapper that combines heterogeneous tree generators.
  • The same machinery produces a single decision tree, and the island version outperforms both the single-population CoEvoRDT and repeated independent runs, so migration is useful even when the final model is one tree.
  • Because different island training sets and migration increase measured external diversity, and diversity tracks performance, the algorithm's gains should persist with more islands up to a point; the paper finds diminishing returns beyond about 30 islands.
  • Computation for the island method can be parallelized across islands with a shared memory for migration, cutting wall-clock time by a factor of 8-10 without changing results, which is not available to boosting baselines.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The Nash weights are only as good as the perturbation population that defines the internal game, so a fair stress test is to score the final forest against an attack set generated independently of evolution.
  • The reported diversity-performance correlation suggests that an explicit diversity-promoting selection pressure or an adaptive migration topology could push the method further, but that goes beyond the paper's experiments.
  • Since the method's fitness function is a black-box score, the island-plus-MNE recipe can likely be ported to other non-differentiable objectives, including fairness metrics, which the authors list as future work.
  • Max-regret numbers are computed on a fixed sample of 10^5 random perturbations, so the reported regret gaps should be read as comparisons on that sample; exact adversarial regret would be the ultimate check.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper proposes ICoEvoRDF, an island-based coevolutionary algorithm that evolves decision tree and perturbation populations on multiple islands with periodic migration, and uses a mixed Nash equilibrium to weight trees in the final forest ensemble. The authors claim superior adversarial accuracy and minimax regret over state-of-the-art robust tree ensemble methods across 20 benchmark datasets, and support the claim with ablations, diversity analysis, standard deviations, and a large parameter study on a held-out dataset.

Significance. If the results hold, the main contribution is a flexible island-coevolution framework that can incorporate existing robust tree methods and improve them through migration and game-theoretic weighting. The empirical evaluation is thorough for an evolutionary computation paper: 20 datasets, ablation studies separating the effects of input sampling, migration, and voting, a diversity analysis, standard deviations over 20 runs, and a 10,000-run parameter study on a held-out dataset. The code is publicly available, which is a substantial strength. The principal weakness is that the game-theoretic justification for the Nash-voting mechanism is not valid as stated, and one core migration parameter is never assigned a value in the manuscript, both of which need to be addressed before the central claims can be accepted.

major comments (4)
  1. [Decision forest composition] The paper states that 'probabilities from the mixed equilibrium DT strategy T are directly used for voting weights.' The minimax theorem justifies optimality only for a randomized classifier that draws a tree according to T; its payoff is E_T[xi(T,P)]. The deterministic weighted-voting classifier used in Tables 1 and 2 has payoff xi(weighted vote, P), which is not equal to that expectation in general. The game-theoretic foundation for Nash-based voting is therefore not valid as written. This is load-bearing because Table 1 shows the equal-voting variant averaging 0.779, below PRAdaBoost's 0.782, while the Nash-weighted variant averages 0.784; the headline superiority over PRAdaBoost in adversarial accuracy depends on this mechanism. The authors should either provide a rigorous argument for the weighted-vote classifier, or explicitly present the MNE weights as a heuristic weighting scheme and remove the minimax-optimality claim.
  2. [Parameterization / Algorithm 1] The migration count ktop appears in Algorithm 1 (line 6) and in Eq. (5), but no value is given for it in the main text or in the supplementary material. The Parameterization section lists every other hyperparameter (NT, NP, np, Ntop, pc, pm, ps, e, NHoF, lc, lg, ng, |I|) but omits ktop. Since migration is credited with the improvement over independent CoEvoRDT runs in the 'Single decision trees' section, this missing parameter prevents replication and leaves a key mechanism underspecified. Please report the value used in all experiments and, ideally, a sensitivity analysis for ktop.
  3. [Ablation study / Tables 1 and 2] The improvement of Nash voting over equal voting is not assessed for statistical significance. For adversarial accuracy the average gain is 0.784 - 0.779 = 0.005, which is smaller than the typical reported standard deviation of about 0.010. Given that the central claim relies on the Nash-voting component, the authors should report paired significance tests for the EV vs NV ablation. This would clarify whether the mechanism behind the headline improvement is reliable, especially since only 9 of 17 adversarial-accuracy wins over PRAdaBoost are reported as significant.
  4. [Metrics calculation (supplementary)] The max regret results are based on 10^5 randomly sampled perturbations. The standard error analysis in supplementary Table 12 shows that the estimate is stable across different draws, but it does not bound the distance to the true max regret. The claim that ICoEvoRDF outperforms all methods 'in each case with statistical significance' should be qualified as applying to the estimated max regret under this sampling procedure, or the authors should provide evidence that the ranking is robust to the choice of perturbation sample. This limitation should be acknowledged in the main text.
minor comments (6)
  1. [Supplementary, Parameterization] In the supplementary parameterization list, the symbol lc is used both for 'number of consecutive generations for each population' and for 'generations without improvement limit'; in the main text the former is denoted np. This notation conflict should be fixed.
  2. [Islands initialization / Results] The main text contains empty cross-references, e.g., 'discussed in Section .' and 'see Section ).' in the 'Islands initialization' and parallelization paragraphs; these should be filled in or removed.
  3. [Table 1] The header 'A VERAGE' should read 'AVERAGE', and the ICoEvoRDF variant column headers (ICoEvoRDFEVSI etc.) are cramped; consider splitting the table or using a more readable format.
  4. [Introduction] The statement that existing evolutionary approaches 'operate only with a single population' is imprecise, since CoEvoRDT coevolves a perturbation population alongside the decision tree population; please rephrase to 'single population of decision trees'.
  5. [Computation time] The discussion of parallelization refers to the supplementary pseudocode but does not explain in the main text that the parallel version increments the generation counter by ng/|I|; a brief clarifying sentence would help readers understand the equivalence between the sequential and parallel versions.
  6. [Single decision trees] The notation N CoEvoRDT is used without a definition in this paper; please define it or provide a pointer to the definition in the cited reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: ICoEvoRDF's headline gains come from empirical search and are ablated against external baselines; the MNE weighting step is a validity gap, not a fitted-input prediction.

full rationale

ICoEvoRDF is an empirical algorithm paper: its central claim is that a particular evolutionary search plus Nash-weighted voting reaches better values of two explicit robustness metrics on 20 benchmarks. I inspected the claimed derivation chain for places where an output quantity is identical by construction to an input or to a fitted value. The Nash-based voting step is the only place where a theoretical justification is invoked: the paper cites the minimax theorem and then uses the MNE mixing probabilities directly as voting weights. This is not a circular step, because the MNE weights are not fitted to the evaluation numbers; the evaluation adversarial accuracy is computed by an exact MILP procedure, and the max-regret values use an independent fixed set of 10^5 random perturbations, not the evolved perturbation populations used to compute the equilibrium. The gap between the randomized mixed-strategy guarantee and the deterministic weighted-vote classifier is a validity concern, not an equivalence of inputs and outputs. The reuse of the authors' prior CoEvoRDT algorithm as the per-island evolutionary engine is a real self-citation, but CoEvoRDT is an externally published AAAI result, is not invoked as an unverified uniqueness theorem, and the paper's claimed improvements are ablated against CoEvoRDT forests and N CoEvoRDT reruns. Parameter and topology choices are empirical tuning, not fitted outputs disguised as predictions. No equation in the paper reduces a reported result to an input by definition, and no benchmark number is the direct value of a fitted parameter. I therefore find no significant circularity.

Assumptions & free parameters 14 free parameters · 4 assumptions · 0 invented entities

The method introduces no new physical entities or conserved quantities. Its free parameters are evolutionary algorithm hyperparameters, mostly tuned on the held-out cod-rna dataset or adopted from the authors' prior CoEvoRDT work. One parameter, ktop, is left unspecified, which is a concrete reproducibility gap.

free parameters (14)
  • Number of islands |I| = 10
    Set to 10 for computational parity with PRAdaBoost; sensitivity experiments show more islands improve results (supplementary Tables 6-11).
  • Decision tree population size NT = 200
    Adopted from CoEvoRDT recommendations; sensitivity analysis on diabetes and cifar10:0v5 shows larger populations help.
  • Perturbation population size NP = 500
    Chosen during parameterization on cod-rna.
  • Generations per island phase ng = 40
    Set as the number of generations between migrations.
  • Consecutive generations per population np = 20
    Parameterization on cod-rna.
  • Ntop (best trees in perturbation evaluation) = 20
    Parameterization on cod-rna.
  • Migration count ktop
    Defined in Eq. (5) and Algorithm 1 but never assigned a value in the paper or supplement.
  • Crossover probability pc = 0.8
    Parameterization on cod-rna.
  • Mutation probability pm = 0.5
    Parameterization on cod-rna.
  • Selection pressure ps = 0.9
    Parameterization on cod-rna.
  • Elite size e = 2
    Parameterization on cod-rna.
  • Hall of Fame size NHoF = 200
    Parameterization on cod-rna; HoF mechanism from CoEvoRDT.
  • Generations without improvement limit lc = 100
    Parameterization on cod-rna.
  • Generation limit lg = 1000
    Parameterization on cod-rna.
assumptions (4)
  • standard math Minimax theorem for finite zero-sum games guarantees the mixed Nash equilibrium maximizes the robustness metric.
    Invoked in Problem definition to justify using MNE weights for the DT vs perturbation game.
  • domain assumption The threat model is L-infinity ball perturbations; all datasets use L-infinity-constrained attacks.
    Robustness metrics (2) and (4) are defined over N_epsilon(x) = {z : ||z-x||_inf <= epsilon}; conclusions may not extend to other norms.
  • domain assumption CART is used as the reference model h' when computing regret.
    Regret in Eq. (3) is relative to the best possible model; the paper chooses CART as this reference, so regret values are reference-dependent.
  • ad hoc to paper Sampling 10^5 random perturbations estimates minimax regret well enough for comparison.
    Supplementary Metrics calculation selects this sample size based on decreasing standard error, not on a certified bound to the true max regret.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Cultivating Archipelago of Forests: Evolving Robust Decision Trees through Island Coevolution." pith.science (2026). https://pith.science/paper/7MPIWDDJ

@misc{pith2026241213762,
  author       = {Pith},
  title        = {Pith review of: Cultivating Archipelago of Forests: Evolving Robust Decision Trees through Island Coevolution},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7MPIWDDJ}},
  note         = {Machine review of arXiv:2412.13762}
}
read the original abstract

Decision trees are widely used in machine learning due to their simplicity and interpretability, but they often lack robustness to adversarial attacks and data perturbations. The paper proposes a novel island-based coevolutionary algorithm (ICoEvoRDF) for constructing robust decision tree ensembles. The algorithm operates on multiple islands, each containing populations of decision trees and adversarial perturbations. The populations on each island evolve independently, with periodic migration of top-performing decision trees between islands. This approach fosters diversity and enhances the exploration of the solution space, leading to more robust and accurate decision tree ensembles. ICoEvoRDF utilizes a popular game theory concept of mixed Nash equilibrium for ensemble weighting, which further leads to improvement in results. ICoEvoRDF is evaluated on 20 benchmark datasets, demonstrating its superior performance compared to state-of-the-art methods in optimizing both adversarial accuracy and minimax regret. The flexibility of ICoEvoRDF allows for the integration of decision trees from various existing methods, providing a unified framework for combining diverse solutions. Our approach offers a promising direction for developing robust and interpretable machine learning models

Figures

Figures reproduced from arXiv: 2412.13762 by the authors.

Figure 1
Figure 1. The ICoEvoRDF scheme. The illustration shows 4 islands with ring migration topology. Each island contains two [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 1
Figure 1. Tested islands migration topologies. greater improvements compared to increasing the size of the decision tree population. Notably, no substantial gains are observed beyond 30 islands, suggesting diminishing returns with further increases in the number of islands. Metrics calculation For calculating adversarial accuracy we used method based on Mixed Integer Linear Programming which calculate ex￾act value of adversar… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Andriushchenko, M.; and Hein, M. 2019. Provably robust boosted decision stumps and trees against adversarial at- tacks. Advances in neural information processing systems , 32

    work page 2019

  2. [2]

    E.; Hall, L

    Banfield, R. E.; Hall, L. O.; Bowyer, K. W.; and Kegelmeyer, W. P. 2006. A comparison of decision tree ensemble creation techniques. IEEE transactions on pattern analysis and ma- chine intelligence, 29(1): 173–180

    work page 2006

  3. [3]

    Breiman, L. 2001. Random forests. Machine learning, 45: 5–32

    work page 2001

  4. [4]

    Breiman, L. 2017. Classification and regression trees. Rout- ledge

    work page 2017

  5. [5]

    Bull, L.; Studley, M.; Bagnall, A.; and Whittley, I. 2007. Learning classifier system ensembles with rule-sharing. IEEE transactions on evolutionary computation , 11(4): 496–502

    work page 2007

  6. [6]

    Chen, H.; Zhang, H.; Boning, D.; and Hsieh, C.-J. 2019. Robust decision trees against adversarial examples. In In- ternational Conference on Machine Learning , 1122–1131. PMLR

    work page 2019

  7. [7]

    Codenotti, B.; De Rossi, S.; and Pagan, M. 2008. An exper- imental analysis of lemke-howson algorithm. arXiv preprint arXiv:0811.3247

    work page Pith review arXiv 2008

  8. [8]

    E.; et al

    Freund, Y .; Schapire, R. E.; et al. 1996. Experiments with a new boosting algorithm. In icml, volume 96, 148–156. Citeseer

    work page 1996

Show all 23 references
  1. [9]

    Fudenberg, D.; and Kreps, D. M. 1993. Learning mixed equilibria. Games and economic behavior, 5(3): 320–367

    1993

  2. [10]

    Zhang, Q.; and Li, J.-J. 2015. Distributed evolutionary al- gorithms and their models: A survey of the state-of-the-art. Applied Soft Computing, 34: 286–300

    2015

  3. [11]

    Guo, J.-Q.; Teng, M.-Z.; Gao, W.; and Zhou, Z.-H. 2022. Fast Provably Robust Decision Trees and Boosting. In In- ternational Conference on Machine Learning , 8127–8144. PMLR

    2022

  4. [12]

    D.; and Joseph, A

    Kantchelian, A.; Tygar, J. D.; and Joseph, A. 2016. Evasion and hardening of tree ensemble classifiers. In International Conference on Machine Learning, 2387–2396. PMLR

    2016

  5. [13]

    Knight, V .; and Campbell, J. 2018. Nashpy: A Python library for the computation of Nash equilibria. Journal of Open Source Software, 3(30): 904

    2018

  6. [14]

    E.; and Howson, J

    Lemke, C. E.; and Howson, J. T., Jr. 1964. Equilibrium points of bimatrix games. Journal of the Society for Indus- trial and Applied Mathematics, 12(2): 413–423

    1964

  7. [15]

    V .; Melab, N.; and Talbi, E.-G

    Luong, T. V .; Melab, N.; and Talbi, E.-G. 2010. GPU-based island model for evolutionary algorithms. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, 1089–1096

    2010

  8. [16]

    Michalewicz, Z. 2013. Genetic algorithms + data structures = evolution programs. Springer Science & Business Media

    2013

  9. [17]

    Ranzato, F.; and Zanella, M. 2021. Genetic adversarial train- ing of decision trees. In Proceedings of the Genetic and Evolutionary Computation Conference, 358–367

    2021

  10. [18]

    Rokach, L.; and Maimon, O. 2005. Decision trees. Data mining and knowledge discovery handbook, 165–192

    2005

  11. [19]

    Savage, L. J. 1951. The theory of statistical decision. Jour- nal of the American Statistical association, 46(253): 55–67

    1951

  12. [20]

    Skolicki, Z. 2005. An analysis of island models in evolution- ary computation. In Proceedings of the 7th annual workshop on Genetic and evolutionary computation, 386–389

    2005

  13. [21]

    Skolicki, Z.; and De Jong, K. 2004. Improving evolution- ary algorithms with multi-representation island models. In International conference on parallel problem solving from nature, 420–429. Springer

    2004

  14. [22]

    Tanese, R. 1989. Distributed genetic algorithms for function optimization. University of Michigan. v. Neumann, J. 1928. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1): 295–320. V os, D.; and Verwer, S. 2021. Efficient training of robust decision trees again...

    1989

  15. [23]

    Yu, X.; and Gen, M. 2010. Introduction to evolutionary al- gorithms. Springer Science & Business Media. ˙Zychowski, A.; Perrault, A.; and Ma ´ndziuk, J. 2024. Co- evolutionary Algorithm for Building Robust Decision Trees under Minimax Regret.Proceedings of the AAAI Conference ...

    2010

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.