acceptodds
Withdrawn from ICLR 2027

When Do Cheap Evaluations Preserve the Best Composed Program?

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

Abstract

Cheap evaluations are useful for searching over composed programs only when they identify candidates that remain strong after their continuations are optimized. We study this question for a finite library of first decisions. A least-squares decomposition separates each composed-value gap into a component aligned with the cheap ranking and a constrained continuation residual. The relative size of these components gives a one-sided condition for preserving the cheap winner and a sharp boundary beyond which a pairwise ordering cannot reverse. The same geometry extends to programs with multiple legs and yields certificates for retaining a small candidate set. Guided by this analysis, we evaluate an adaptive rule that reads continuations until the remaining candidates cannot challenge the incumbent, and a promotion rule that carries candidates through weak early fidelities. In simulated control archives, the geometric certificates agree with observed orderings and adaptive reads recover the best composed choice at reduced evaluation cost. On public multi-fidelity optimization benchmarks, the promotion rule improves final-fidelity regret against standard budget-matched schedules.

Primary area:
learning theory
Keywords:
Compositional decision-making, multi-fidelity optimization, ranking preservation, compositional policy evaluation

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_gDdAOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies whether inexpensive evaluations preserve the best candidate in a finite library after its continuation is optimized. It decomposes final scores into an aligned component and an orthogonal residual, derives a sharp pairwise ranking condition and top-k retention certificates, and extends the decomposition to multiple stages. It also evaluates regression-based screening (SCREEN) and budget-based promotion (ENV) on simulated control tasks and public multi-fidelity benchmarks.

Critical strengths

The finite-library formulation makes the distinction between preserving the full ranking and retaining the eventual optimum explicit. The pairwise boundary is sharp within the stated residual model. The experiments report favorable cost–accuracy trade-offs and include matched-schedule comparisons, which help separate the effects of promotion rules from those of schedule selection.

Critical weaknesses

The theoretical novelty is limited. Applying the classical three-correlation inequality to the two score vectors and the vector ((e_i-e_j)/\sqrt{2}), where (e_i) and (e_j) are coordinate basis vectors, yields Theorem 6, including its sharpness. [1] Theorem 9 follows directly from linearity of the least-squares projection. Neither requires an argument specific to optimizing continuations.

The algorithms provide limited additional novelty. SCREEN combines a standard regression prediction bound with a stopping rule using the current best value; its guarantee assumes simultaneous validity of the unread candidates’ bounds, which is not established for the sequential procedure. ENV changes promotion counts and schedules within the successive-halving framework. [5] Neither algorithm derives its decisions or guarantees from Theorem 6 or Theorem 9.

The empirical gains show that these particular heuristics can be useful, but do not resolve the central novelty concern. Overall, I do not find the theoretical or algorithmic contribution sufficient for acceptance.

Questions for authors

What mathematical contribution remains beyond the classical three-correlation inequality and linearity of projection? Please identify a precise statement or proof step that is not recovered by these reductions.

What is the independent algorithmic contribution of SCREEN and ENV beyond regression screening and successive-halving-style allocation? Please identify the substantive change and explain which comparisons isolate its benefit from schedule selection and budget accounting.

Reviewer_JS5sOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper asks when the first decision ranked best by its immediate value a_d is also best by the backed-up value mu_d = a_d + gamma^t b_d, where b_d is the optimal continuation value. This is the familiar question of when a greedy choice agrees with a one-step lookahead (immediate rewards vs. accumulated discounted rewards in RL; ranking paths via g+h for different heuristics h in search, etc). Yet the connection is not made. The "decomposition" is the OLS identity, and the "sharp boundary" is Cauchy–Schwarz. The certificate requires rho = corr(a, mu), which can only be computed once all continuations b_d, the expensive quantities, are known. So the theory does not appear to be usable. The writing is not clear enough either; the title talks about composition of programs, which seems to imply something entirely different.

Critical strengths
  • The question of when cheap evaluations can safely prune candidates is relevant.

  • The derivations appear to be correct

Critical weaknesses
  • The results seem a bit circular. The certificate needs rho_pred, which needs the full vector b. Once b is known, argmax mu can be read off and no certificate is needed.

  • I don't find the technical content meaningful enogh and the algorithms do not seem to use the theoretical formulation. Eq. 5 is least squares, Thm. 6 is Cauchy–Schwarz, and Thm. 9 is linearity. SCREEN is branch-and-bound with a tuned, non-admissible regression bound, so Prop. 10 holds only when the bound happens to be valid.

  • Related work on greedy/myopic choices versus lookahead choice, rollouts and branch-and-bound is missing.

Questions for authors
  1. How can rho_pred (or lambda) be obtained, or bounded, before the continuations are evaluated?
  2. In what sense does §6.1 test the theory, given that rho is computed from the same continuation values the certificate is checked against?
  3. Which step of SCREEN or ENV depends on Theorem 6?
Reviewer_PBvcOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper studies when ranking first-stage candidates by a cheap score preserves the best candidate after an expensive, optimized continuation. Regressing the continuation value on the cheap score, it derives an exact condition (in terms of the correlation between cheap and composed scores) under which a pair of candidates keeps its order, together with top-kk certificates and an extension to multi-stage compositions. Based on this, it proposes a stopping rule for reading continuations (SCREEN) and a promotion rule for multi-fidelity hyperparameter optimization (ENV), evaluated on dm_control policy compositions and LCBench/YAHPO.

Critical strengths
  • The decomposition (Eq. 5) and Thm. 6 give a clean, exact, and distribution-free relation between fidelity correlation and rank preservation, which also extends to chains (Thm. 9).
  • The cost accounting in the experiments is careful (shared budget, FIT/TEST split, paired comparisons).
Critical weaknesses
  • The theory cannot be applied before the expensive evaluations, and its validation is circular. SS, λ\lambda and ρpred\rho_\mathrm{pred} are computed from the OLS fit on the full continuation vector (Eq. 3–4). Given ρpred\rho_\mathrm{pred}, Thm. 6 is an exact geometric fact. Finding no reversed pair among 30,913 (Sec. 6.1, B.1) therefore only confirms an identity numerically. The same holds for the sharpness check and, as far as I can see, for the 0.9 "correlation gate" (Sec. 3.4). The paper itself states that the certificate requires a bound on λ\lambda and knowledge of sign(S)\mathrm{sign}(S) (Sec. 4.1), but never shows how to get these from cheap or prior-task information. So the main contribution does not answer the question in the title.
  • The algorithms are weakly connected to the theory and the evidence is thin.
    • SCREEN is a standard sequential stopping rule with a linear prediction interval and no coverage guarantee (B.6). It is not compared to linear best-arm identification or racing. Its gains over fixed blocks/UCB (Table 2) are in the third to fifth decimal, change sign, and rest on only 6 and 3 catalogs for Cheetah and Pointmass.
    • ENV is described only informally (Sec. 5.2). BOHB beats it (Table 4), and against tuned SH with a fixed schedule the result is mixed (B.9). Adaptive multi-fidelity methods are missing (PASHA, DyHPO, ifBO, ASHA, learning-curve extrapolation, one-epoch early discarding).
    • Several baseline defects were fixed after the fact (B.8).
    • The title and abstract talk about "composed programs", but no program-synthesis or LM-pipeline experiment is included.
Questions for authors
  1. Is ρpred\rho_\mathrm{pred} or λ\lambda estimated anywhere without the full continuation values (including the 0.9 gate)? If not, how would a practitioner apply Thm. 6 / Cor. 7?
  2. Please give ENV as pseudocode (promotion counts per rung, budget feasibility, what is tuned on FIT).
  3. What is the control setup: what are the 16 first-leg policies, what is the "objective direction qq", how are the second-leg optimizations done, and how many independent catalogs/seeds per domain?
  4. Why the framing as "composed programs" without any program or LM-pipeline experiment?

Suggestions:

  • Compare SCREEN to linear best-arm identification / racing, and ENV to PASHA, DyHPO, ifBO and ASHA under the same budget.
  • Show how to obtain a bound on λ\lambda from cheap or prior-task information, and how often the certificate fires with an estimated bound.

Minor points / Details

  • "Program" is never defined; in Sec. 2 it is a pair of policies.
  • Eq. 1 is a verbal identity, not an equation.
  • Cor. 3: "gdg_d is a derivative of FxF_x at the origin" is ambiguous.
  • Sec. 3.4: "twelve comparisons" and "361 of 1056 eligible cells" are not defined at this point.
  • Sec. 6.1: please state that the absence of violations follows from Thm. 6 by construction.
  • B.6 and Fig. 4 contain internal notes ("must be checked against its producer", "b147"/"b171"). Code is not available.
  • Table 3 / Fig. 3a: BOHB is best overall, while the abstract says ENV "improves final-fidelity regret". Please comment.
  • Fig. 3b: the colormap is not explained.
  • Related work could be improved
    • Y.-C. Ho, R. S. Sreenivas, P. Vakili. Ordinal optimization of DEDS. Discrete Event Dynamic Systems 2:61–88, 1992. (Order is easier than value; top-kk retention under noisy/cheap evaluations, i.e. the question of this paper.)
    • M. Soare, A. Lazaric, R. Munos. Best-Arm Identification in Linear Bandits. NeurIPS 2014. (Close to SCREEN.)
    • O. Bohdal, L. Balles, M. Wistuba, B. Ermis, C. Archambeau, G. Zappella. PASHA: Efficient HPO and NAS with Progressive Resource Allocation. ICLR 2023. (Adapts pruning based on rank stability between rungs, close to the motivation of ENV.)
    • M. Wistuba, A. Kadra, J. Grabocka. Supervising the Multi-Fidelity Race of Hyperparameter Configurations (DyHPO). NeurIPS 2022.
    • R. Egele, F. Mohr, T. Viering, P. Balaprakash. The Unreasonable Effectiveness of Early Discarding After One Epoch in Neural Network Hyperparameter Optimization. Neurocomputing 597:127964, 2024.

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

Related papers

Discussion (0)

Sign in to comment.