acceptodds
Withdrawn from ICLR 2027

Finite Black-Box Observations Cannot Identify Decompositions for Efficient Optimization

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

The No-Free-Lunch theorem provides an algorithm-level statement: no decomposition strategy can be universally dominant across black-box optimization problems. We focus on a more basic, information-level question about decomposition itself rather than the strategy that implements it: To this end, we establish a general theoretical framework for analyzing decomposition in black-box optimization, which explicitly characterizes the decomposition space and the intrinsic complexity of optimal decomposition identification. Building on this framework, we establish a non-identifiability theory and answer the question in the negative: decompositions for efficient optimization cannot be reliably identified from finite black-box observations. Through theory-driven counterexample analysis, we reveal a fundamental objective mismatch in prevailing decomposition strategies that infer problem structure from finite information: their long-standing emphasis on structural recovery may not align with the ultimate goal of efficient optimization. We further revisit the random decomposition strategy, which is generally considered ineffective, and show that it provides a minimax-robust strategy under finite information. Together, the theoretical and empirical findings provide guidance for several promising directions in future research on decomposition strategy design.

Primary area:
optimization
Keywords:
divide-and-conquer, black-box optimization, decomposition, cooperative coevolution, no-free-lunch theorem

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_gMcMOpenReview ↗
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 hh of an objective ff on X⊆RD\mathcal X\subseteq\mathbb R^D is available, a decomposition G\mathcal G (a cover of the DD variables, overlaps allowed) is selected, and a fixed protocol A\mathcal A then optimizes the resulting subspaces. A decomposition is scored by the expected number of further evaluations needed to reach ε\varepsilon-accuracy, Lε(f,G,A∣h)L_\varepsilon(f,\mathcal G,\mathcal A\mid h), and a strategy by its total cost CεC_\varepsilon, which includes the evaluations spent on probing.

Contributions as I understand them:

  1. A count of the space of covers, which grows doubly exponentially in DD (Thm 1).
  2. A non-identifiability result (Thm 2): if one decomposition beats another on some function consistent with hh, 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."
  3. 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.
  4. 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
  1. 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 f1f_1 alone, DG correctly detects the coupling and groups {x1,x2}\{x_1,x_2\}, while the reported finite-budget comparison in Table 1 favours the separate decomposition at every ε≤0.7\varepsilon\le0.7. 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.

  2. 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
  1. 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 z1,z2,…z_1,z_2,\dots under G\mathcal G and z1,z1,z2,…z_1,z_1,z_2,\dots under G′\mathcal G'. The second order can never reach a target earlier. Take the objective equal to 00 at z2z_2 and 11 elsewhere, with ε<1\varepsilon<1 and an empty initial history. The hitting times are 2 and 3, so G\mathcal G is strictly better on this function, while G′\mathcal G' 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 LεL_\varepsilon 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.

  1. 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 [D][D], 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 LεL_\varepsilon. 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
  1. (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 G\mathcal G it may query z1,z2z_1,z_2, and under G′\mathcal G' query z1z_1 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.

  2. (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 ε=0.7\varepsilon=0.7 to 0.60.6; CSG from 0.60.6 to 0.50.5 to 0.40.4; IRRG from 0.50.5 to 0.40.4). An average of nested hitting times over a fixed set of runs cannot do that. Please report attainment rates alongside these tables.

  3. (Clarification) Optimal values. The domain of the Sec. 4.1 example is not stated; Fig. 1 suggests [0,1]2[0,1]^2. On that box, f2f_2 in Eq. 25 has its minimum at about 0.04090.0409, near x1=x2≈0.199x_1=x_2\approx0.199, not 00 as stated at L781. At the minimizer of f1f_1, the added term equals 20⋅w(0.2,0.2)⋅0.005=0.04096>020\cdot w(0.2,0.2)\cdot0.005=0.04096>0. Please state the domain and recompute Table 2. Relatedly, Appendix A.3 samples f⋆f^\star from [−1000,1000][-1000,1000] (L684), while Table 4's note says f⋆=0f^\star=0 for all sampled problems (L826). Which reference value defines the targets?

  4. (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.

  5. (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.

Reviewer_39icOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates a fundamental question in black-box optimization: Can variable decompositions that facilitate efficient downstream optimization be reliably identified from finite objective function observations? From the perspective of limited information, the authors argue that finite observations are insufficient to reliably determine the optimal decomposition, and further emphasize that accurately recovering variable interaction structures does not necessarily lead to better optimization performance.

The main contributions can be summarized in three aspects:

1.Unified Theoretical Framework: The paper defines a generalized decomposition space that accommodates overlapping variable groups and evaluates decomposition quality using the expected number of function evaluations required to achieve a prescribed optimization accuracy. 2. Non-Identifiability Theory: The paper advances the theoretical claim that efficient decompositions cannot be reliably identified from finite black-box observations. It also highlights a potential objective mismatch between structural recovery and downstream optimization efficiency. 3. Reassessment of Random Decomposition: The authors establish that uniform random decomposition selection constitutes a minimax-robust strategy under finite-information conditions, providing a new decision-theoretic interpretation of random decomposition.

Regarding experimental validation, the results support two limited conclusions: accurate structural recovery does not necessarily translate into better optimization performance, and simple random decomposition can be computationally efficient under certain high-dimensional problem distributions and optimization protocols. Although the experiments are reasonably extensive and provide some convincing empirical evidence, there are limitations in the sufficiency and rigor of the validation, as well as its consistency with the theoretical claims. The experiments rely primarily on manually constructed examples and synthetic benchmark problems, with limited validation on real-world applications. Moreover, the experimental design does not adequately control for potential confounding factors, including group dimensionality, structural identification costs, and the computational complexity of the downstream optimizer. The central concern is that the paper has not yet rigorously established the logical connection between information-theoretic non-identifiability and lower bounds on downstream optimization performance.

Critical strengths

The paper addresses a fundamental research question worthy of further investigation: how to identify decompositions that genuinely facilitate downstream optimization under limited information, rather than merely pursuing accurate structural recovery. The research perspective is also interesting, as the authors highlight that accurately recovering variable interaction structures does not necessarily lead to improved optimization efficiency. This insight may help shift the design of decomposition strategies from structure-driven approaches toward optimization-performance-driven approaches.

Critical weaknesses

The proof of Theorem 2 may contain some ambiguities or issues concerning its underlying assumptions and boundary cases. Furthermore, a rigorous theoretical connection between the minimax optimality of random decomposition and its actual optimization performance remains to be established.

Questions for authors

Clarification Requests:

  1. Does Theorem 2 rigorously hold under the current assumptions? The proof of Lemma 2 appears not to adequately account for the consistency of function values at repeatedly queried points.
  2. Can the minimax result in Theorem 3 genuinely support the paper’s central claim regarding the robustness of random decomposition in practical optimization? Could the authors clarify whether the assumptions underlying this theorem hold in practical black-box optimization settings, and how the theorem establishes the robustness of Random-50 in terms of actual optimization performance?
Reviewer_31AcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether optimal problem decompositions for black-box optimization can be identified purely from finite observations. The authors introduce a theoretical framework demonstrating that the decomposition space grows doubly exponentially with problem dimensionality. The central contribution is a non-identifiability theorem, which proves that finite observations cannot reliably identify an efficient decomposition because infinitely many distinct functions can yield the same finite history while requiring different decomposition strategies. To illustrate this, the paper highlights an "objective mismatch" in structure-driven strategies, demonstrating that structural recovery does not inherently guarantee optimization gains. Finally, the authors prove mathematically and validate empirically that a random decomposition strategy provides a computationally efficient and minimax-robust baseline under finite information constraints.

Critical strengths
  • The authors provide a rigorous mathematical formalization of the general decomposition space. Furthermore, the non-identifiability theorem (Theorem 2) establishes a solid mathematical foundation for the paper's core claims. And the authors prove that the often-dismissed random decomposition strategy is uniquely minimax optimal under finite information (Theorem 3).
  • The paper makes a compelling distinction between structural recovery and actual optimization gain. Highlighting this objective mismatch serves as a strong, necessary critique of prevailing interaction-based decomposition methods, such as Differential Grouping.
  • The experimental results effectively expose the computational overhead of structure-driven methods, accurately noting that methods like DG2 require O(D2)O(D^2) function evaluations. In contrast, the Random-50 strategy achieves competitive optimization performance with essentially zero decomposition cost.
Critical weaknesses

see the questions below

Questions for authors
  • How does the non-identifiability theorem hold up if the function class F\mathcal{F} is restricted by standard assumptions like Lipschitz continuity or bounded gradients?
  • To what extent is the empirical success of the Random-50 strategy tied to the internal adaptation mechanisms of CMA-ES? Would these comparative results hold if a simpler or less robust optimizer were used for the subproblems?
  • The counterexample demonstrating objective mismatch is elegantly constructed, but it relies on a 2-dimensional problem. Can you provide intuition or evidence regarding how frequently this specific mismatch occurs in high-dimensional, practical applications?
  • If a strategy is allowed to dynamically update its variable groupings based on continuous evaluation feedback, rather than relying solely on a fixed initial history, does the minimax robustness of the random decomposition strategy (Theorem 3) still apply?

Comments on the paper

1 comment

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.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.