acceptodds
Withdrawn from ICLR 2027

OPBO: Order-Preserving Bayesian Optimization

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

Abstract

Bayesian optimization (BO) is widely used for optimizing expensive black-box problems under limited evaluation budgets. However, its performance often degrades as the problem dimension increases. Most high-dimensional BO methods address dimensionality while retaining value-based surrogate objectives. We argue that the surrogate learning objective itself may also contribute to this difficulty. We therefore study replacing value-based surrogate objectives with order-based objectives in high dimensions and characterize when order learning becomes preferable to value regression. Our analysis shows that the advantage of order learning increases when the numerical representation is harder to fit and when the dimension is large relative to the number of observations. These results motivate Order-Preserving Bayesian Optimization (OPBO), which replaces value regression with neural ranking surrogates. We compare value-based and order-based surrogates across 20 synthetic instances and four real-world tasks under Standard BO, TuRBO, and HeSBO. Under the same evaluation budget, ranking surrogates generally perform better, with larger gains at higher dimensions. The source code is available at https://anonymous.4open.science/r/OPBO-89B4/.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Bayesian optimization, Order-Preserving

Reviews

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

This paper investigates replacing value-based objectives with rank-based objectives in high dimensions, trying to reveale situations where order learning is preferable to value regression. Through comparisons using 20 synthetic instances and 4 real-world tasks, rank surrogates generally showed superior performance under the same evaluation budget, with this benefit being particularly marked in high-dimensional problems. Furthermore, the study found that a crossover between value and rank estimation, controlled by the complexity of the numerical representation, exists. For end-to-end optimization, Pairwise and ListMLE achieved the second-best average rank across all BO configurations, suggesting that direct order learning can be particularly advantageous when the complexity of the objective function's numerical representation introduces unnecessary complexity in candidate selection.

Critical strengths
  1. Quantification of Conditions Favoring Rank Learning: The paper is theoretically valuable for explicitly identifying the conditions under which rank learning is superior to value regression. Specifically, demonstrating the criteria for the inversion of preference, defined by the difficulty of numerical representation due to monotonic transformation (DvalD_{\mathrm{val}}) and the dimension-to-sample ratio (γ\gamma), is a significant theoretical contribution. Furthermore, the proper separation of the covariance matrix inverse computation via one-step comparison is appropriate.

  2. Alignment Between Theoretical Setup and Empirical Validation: The mapping between the theoretical problem formulation and the empirical validation is relatively clear. The structure, which systematically extends the methodology—by controlling the difficulty of numerical representation through monotonic transformations and validating it from limited samples to neural networks and actual BO—is highly rational. The comparison with Rank-NN is particularly strong, as it effectively distinguishes the proposed approach from simple rank transformation and ranking loss methods.

Critical weaknesses
  1. The primary failing of this paper is its poor presentation. In the Theoretical Analysis of Section 3, the rationale behind introducing individual definitions and propositions is unclear, making it difficult to understand what the study is actually investigating. While it is possible the reviewer is simply unable to follow the paper's logic, the manuscript cannot be considered highly comprehensible.

  2. A Gap Between Theoretical Formulation and the Proposed BO Algorithm. The theory focuses on affine estimators, initial gradient directions, and independent candidate sets within the Gaussian Single-Index Model. Conversely, the proposed method is a BO that iteratively learns an ensemble of neural networks. Therefore, the theoretical superiority demonstrated currently does not sufficiently explain the performance gains in the actual BO setting. Specifically, the correspondence between the theoretical condition γ<1\gamma < 1 and the high-dimensional settings explored in the experiments is ambiguous. Consequently, the loss incurred by relying only on ordinal information is not discussed adequately. Furthermore, in the regret decomposition of Proposition 3, the cost of ranking errors depends on the gap in objective function values. However, Pairwise and ListMLE appear to be designed to operate without utilizing that gap (please correct the reviewer if this is a misunderstanding). Thus, it is not necessarily true that learning the rank correctly is the most efficient way to minimize regret. The trade-off between the robustness gained by discarding numerical information and the information lost should be the core focus of this research.

Questions for authors
  1. Robustness Against Regularized Value Regression: Does the advantage of rank learning still hold when compared against properly regularized value regression? The theory currently focuses mainly on comparison with standard least squares estimation, but instability near γ→1\gamma \to 1 could potentially be mitigated using techniques such as ridge regression. It would be important to verify if superiority persists even when compared to such sophisticated baselines.

  2. Validity of Using Rank Model Uncertainty for BO Exploration: Is it valid to utilize the uncertainty derived from ranking models in the BO exploration phase? While the variance across ensembles is employed for exploration, there is no guarantee that this variance accurately represents the uncertainty of the predicted rank. Specifically, can the study rigorously validate whether the rank-based improvement achieved in HeSBO successfully implements an appropriate exploration–exploitation trade-off?

  3. Core Differentiation from Existing Ranking-Based BO: What is the key differentiator from existing ranking-based BO research? The mere introduction of ordinal learning into BO is not novel. While we believe the novelty resides in the theoretical characterization of the conditions under which rank learning excels, the paper must more clearly demonstrate what novel insights are revealed by this theory that previous studies failed to capture.

Reviewer_DQjnOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper asks whether the surrogate's training objective contributes to the difficulty of high-dimensional Bayesian optimization, independently of its architecture or the outer BO loop. It studies objectives that is monotone recodings of a latent score and compares affine value regression with pairwise and listwise ranking losses. Its analysis gives a limiting directional alignment for each estimator under a Gaussian single-index model, a threshold that says when ranking wins (Eq9), and a corollary that converts alignment into latent selection regret. OPBO then swaps the surrogate inside Standard BO, TuRBO, HeSBO for a ranking model and scores candidates by rank or by ensemble disagreement. Experiments cover 24 tasks where four synthetic functions at five dimensions from 200 to 1000, plus Rover, MOPTA08, Walker and DNA. Five surrogates are compared under four outer configurations, with 10 seeds, 40 shared Latin-hypercube points and 500 evaluations. The ranking losses take the two best mean within-framework ranks in all four configurations.

Critical strengths

The experimental protocol is the cleanest part of the paper. All five surrogates share the initial design, the candidate draws and the evaluation budget. The recoding invariance check is run. parameter hashes, predictions and selections are audited, the code aborts if finite-precision recoding changes an observed tie or rank. In the controlled setting of Sec3.5 the authors also report that MSE-NN is competitive at small dimension-to-sample ratios, including the case where their story fails. For a comparison that could easily be confounded by candidate generation. This protocol makes the rank ordering in Fig4a interpretable.

Critical weaknesses

The abstract is written for a different theorem. The abstract says the advantage grows "when the dimension is large relative to the number of observations", but Theorem 7 is proved for n > d, and Sec 4 contains no dimension-resolved analysis. The abstract reads as if it was written for a different theorem than the one in Sec3. The authors may need to review AI's output more carefully.

Section 4 reports mean ranks over all 24 tasks and per-task trajectories in the appendix, with no aggregate by d and no uncertainty. The design already contains the sweep (4 functions at 5 dimensions).

The comparison has no inferential statistics, and the value baseline has no control that separates "order versus value" from "which target scaling". Fig 4a gives overall mean ranks of about 1.90 for ListMLE and 1.98 for Pairwise, against 3.585 for GP and 3.605 for MSE-NN. The top two are visibly separated from the rest, but MSE-NN and GP are 0.02 apart with no confidence interval, no Friedman test and no per-task win table. MSE-NN standardises targets by their sample median and standard deviation within each fit. That is not robust to within-task skew, and a log1p or robust-scaled target is never run in the BO benchmarks; nonlinear recodings appear only in the controlled Section 3.5 setting. Until that control is run, the ranking advantage could be a target-scaling advantage, which would undercut the benchmark-level claim.

Questions for authors
  1. Report mean within-framework rank as a function of d, aggregated over the four synthetic functions and four outer configurations, with confidence intervals. If the trend is flat, would you revise the abstract sentence about larger gains at higher dimensions?
  2. Theorem 7 requires gamma = d / n (0 < gamma < 1). Three of the five benchmark dimensions have gamma > 1 at a budget of 500. What happens in that regime, and does the predicted ordering survive?
  3. The paper does not separate the mechanism from the scaling. Can you report MSE-NN with log1p or robust-scaled targets on Rosenbrock and Dixon-Price?
Reviewer_5wsNOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes a Bayesian optimization approaches based on pairwise or listwise neural ranking surrogates anking surrogates instead of value regression surrogates. The main reasons for this change is that order learning increases BO performance when the numerical feature representation is harder to fit and when the dimension is large relative to the number of observations. Specifically, the paper compares value regression and order learning under order-preserving transformations of the same realized observations. The paper showcases the method across various synthetic BO datasets

Critical strengths
  • The question and approach as valid: BO relies on ranking of surrogate values, so replacing the surrogates by ranking methods might be beneficial
  • The paper proposes nonlinear neural surrogates
Critical weaknesses
  • The novelty is unclear. Ranking-based BO methods already exist in the literature. Pairwise and ListMLE are established losses.
  • The paper relies on strong assumptions, limiting the applicability (isotropic Gaussian inputs, a Gaussian single-index model, independent training and candidate samples)
  • The theory does not analyze the implemented ranking surrogates (e.g., Theorem 7 addresses gradients at a zero affine score, not trained neural ensembles)
  • The choice of ranking losses is under-motivated. Section 2.3 defines Pairwise and ListMLE without explaining their respective benefits, alternatives, or when one should be preferred
  • The experimental baselines are not sufficient. RankOpt, PoPBO, and BORE are discussed but not benchmarked. The paper also does not distinguish its surrogate-learning approach from acquisition-ranking stabilization methods such as OrthoBO, or investigate whether they are complementary
  • The empirical summary makes practical significance difficult to assess. Average ranks obscure effect sizes and uncertainty in the aggregate comparison
  • The paper is lacking a clear flow of reading, including background explanations and consistent, introduced notation. For example, Section 2.4 introduces acquisition rules without first explaining their role in exploration versus exploitation. Notation switches among iteration indices and candidate-set symbols
Questions for authors
  • What makes the method specific to the high-dimensional setting? Why not consider a general setting?
  • Which parts of the Gaussian assumptions are essential for the method?
  • The analysis specializes to affine MSE regression (line 215). What changes for regularized or nonlinear regression, robust losses, or learned monotone output transformations?
  • How does OPBO compare with OrthoBO under matched budgets? Since the methods address different sources of ranking error, could acquisition variance reduction complement an ordinal surrogate rather than serve as a competing approach?

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

Related papers

Discussion (0)

Sign in to comment.