- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper studies variable decomposition for cooperative-coevolution-style black-box optimization. A finite evaluation history of an objective on is available, a decomposition (a cover of the variables, overlaps allowed) is selected, and a fixed protocol then optimizes the resulting subspaces. A decomposition is scored by the expected number of further evaluations needed to reach -accuracy, , and a strategy by its total cost , which includes the evaluations spent on probing.
Contributions as I understand them:
- A count of the space of covers, which grows doubly exponentially in (Thm 1).
- A non-identifiability result (Thm 2): if one decomposition beats another on some function consistent with , the order is reversed on another consistent function. Together with Lemma 1 this is read as "finite black-box observations cannot identify decompositions for efficient optimization."
- A two-dimensional example (Sec. 4.1) in which Differential Grouping returns the same grouping for two functions that agree on its four probes but favour different decompositions. It is used to argue that structural recovery and optimization gain can diverge.
- A minimax result (Thm 3). Under a 0-1 loss for selecting an optimal decomposition, and assuming every decomposition is the unique optimum for some consistent function, the uniform distribution over all decompositions is the unique minimax choice.
Validation: proofs of Thms 1-3 in the main text and Appendix A, and experiments on 128 generated 1000-dimensional problems. There, a random partition into 50-variable groups (Random-50) followed by CMA-ES is compared with DG2, RDG3, CSG and IRRG. It reaches the aggregate targets with the fewest or tied-fewest evaluations and uses roughly 112-781x less wall-clock time at the common budget (Tables 3 and 5).
Critical strengths
-
Separating structural recovery from optimization quality. The paper defines the quality of a decomposition by downstream optimization cost (Definition 2, Eq. 2; strategy cost in Eq. 5) rather than by agreement with a planted interaction structure, and it shows that a correct interaction verdict can select the slower decomposition. This is a useful reframing for a line of work that often reports grouping accuracy as a goal in itself. The point is already visible in the paper's own example. For alone, DG correctly detects the coupling and groups , while the reported finite-budget comparison in Table 1 favours the separate decomposition at every . The precise hitting-time interpretation of that table needs clarification (Question 2), but the illustration stands. I consider this the paper's most distinctive contribution, and it is the main reason I see value in the work.
-
A practically relevant empirical observation. On these generated problems, a probe-free random partition (Random-50) reaches the reported aggregate log-gap targets with the fewest or tied-fewest evaluations (Table 3). At the common evaluation budget it also uses approximately 112-781 times less wall-clock time (Table 5). The size of the evaluation advantage varies substantially by baseline and target. This is worth reporting, even though, as discussed below, the experiment does not yet show that randomization is what produces the gain.
Critical weaknesses
- The main non-identifiability theorem is false for protocols it permits, and its stochastic extension is not established.
Theorem 2 is stated for any fixed optimization protocol (L263). Such a protocol may query under and under . The second order can never reach a target earlier. Take the objective equal to at and elsewhere, with and an empty initial history. The hitting times are 2 and 3, so is strictly better on this function, while is strictly better on none. This contradicts the claimed preference reversal. Lemma 2 has the corresponding problem: querying one point twice cannot reproduce two distinct objective values.
Assuming the protocol never revisits points and does not stop early repairs the deterministic construction over a function class that permits single-point edits. It does not repair the stochastic proof at L285-287. That proof constructs an objective separately for each realization of the randomness, whereas comparing expected hitting times requires a single fixed objective, and a fixed single-point edit is almost surely unobserved under atomless query distributions. So the general claim used to answer the paper's main question (L88-90) is not established. Covering randomized continuous optimization, which is the setting of and of the experiments, needs a new argument or a material restriction of the claim. This is my main Soundness concern.
A more minor point: the repaired adversarial construction is not specific to decompositions. On finite domains, for non-revisiting searches that continue through the domain, its conclusion follows from a conditional no-free-lunch argument (Wolpert 1996; Wolpert & Macready 1997), which limits what it adds.
- The minimax theorem does not justify the practical random-decomposition recommendation.
Theorem 3 is correct under its explicit unique-winner assumption, but its optimizer is uniform over all covers of , whereas Random-50 samples balanced partitions into groups of 50. At a fixed history and under that assumption, consider a one-shot distribution supported only on Random-50 partitions. Its worst-case 0-1 selection loss is one, just as for any deterministic choice, because some compatible function has an omitted cover as its unique minimizer of . This does not compare the full strategies' evaluation costs. But the theorem's 0-1 loss supplies no bound on evaluation cost either, and the assumption's applicability to the experimental protocol is not demonstrated.
The experiments do show competitive performance. They do not isolate randomization from avoiding probes and using smaller groups (the structure-driven methods have mean group sizes of 244-902, Table 6), and a fixed partition into groups of 50 is the most direct missing control. The paper itself acknowledges probing and group-size costs (L428-432). The issue is the further connection to minimax robustness (L395-396, L435-438) and the headline claim that "we theoretically show that it provides a zero-cost and minimax-robust baseline" (L99-101).
A related formal minimax random-selection result already appears in Ziomek & Bou-Ammar (ICML 2023, Thm 4.6; https://proceedings.mlr.press/v202/ziomek23a/ziomek23a.pdf), although its model and loss differ. My concern is the unsupported theoretical explanation of the practical recommendation, not the correctness of the conditional theorem or the existence of the empirical gains.
Questions for authors
-
(Clarification) Under which protocol assumptions do Theorem 2 and Lemma 2 hold? Please state the non-revisiting and continuation conditions explicitly. Non-revisiting alone is not enough if the protocol may stop depending on the decomposition: under it may query , and under query and stop. Please also either give a proof for stochastic protocols on continuous domains or restrict the theorem. A correct proof of the stochastic case would change my assessment of Soundness.
-
(Clarification) How are Tables 1, 2 and 4 computed? Is each entry an expectation over runs of the per-run hitting time, or the point where an averaged best-so-far curve crosses the target, as in Table 3? How are runs that do not reach the target within the budget counted? Table 4 decreases as the target tightens in four places (RDG3 from to ; CSG from to to ; IRRG from to ). An average of nested hitting times over a fixed set of runs cannot do that. Please report attainment rates alongside these tables.
-
(Clarification) Optimal values. The domain of the Sec. 4.1 example is not stated; Fig. 1 suggests . On that box, in Eq. 25 has its minimum at about , near , not as stated at L781. At the minimizer of , the added term equals . Please state the domain and recompute Table 2. Relatedly, Appendix A.3 samples from (L684), while Table 4's note says for all sampled problems (L826). Which reference value defines the targets?
-
(Clarification, with additional experiments) To attribute the gains to randomization, the most direct control is a fixed, arbitrary partition into 50-variable groups (for example, consecutive indices). A sweep over the group size for both random and fixed partitions, and structure-driven methods with group sizes capped at 50, would be further informative but are secondary. Please also state whether Random-50 re-draws its partition during optimization, and whether the 32 shared initial points are charged to every method. Per-problem paired comparisons would help support the stability claims. The answers determine whether the experiments support randomization specifically or rather small groups without probing, which bears on Critical Weakness 2.
-
(Suggestion for future work; not affecting my score) A cost-linked theorem for bounded-size partitions, for example with a capped hitting time as the loss, would be a useful extension. I am not requiring this specific result. My current concern is the unsupported connection between Theorem 3 and the strategy evaluated, which narrowing the claim and presenting Random-50's performance as empirical would also address.
We sincerely thank all reviewers for their careful reading of our manuscript and their thoughtful and constructive feedback. We greatly appreciate the time and effort they have devoted to reviewing our work.