acceptodds
Withdrawn from ICLR 2027

TRINITY: RESIDUAL-AWARE QUADRATIC SEEDING FOR TENSOR-TRAIN BLACK-BOX OPTIMIZATION

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

Abstract

Trinity connects nonlinear surrogate prediction, bounded quadratic seeding and tensor-train search for discrete black-box optimization. The interface addresses branch cancellation: optimizing the quadratic branch can fail even when the full predictor is exact. For the tested DeepFM model, conditional affine corrections of its one-hidden-layer ReLU residual preserve quadratic couplings without auxiliary bits. A computable residual envelope yields a conditional retained-candidate bound, a near-sharp construction and explicit improvement conditions. Complete seeds are rescored with the full surrogate and initialize a correlated TT; only subsequent true-objective evaluations supply training labels. For the DeepFM instantiation (Trinity-D), across three photonic discretizations (512–2,048 variables), mean independently refined loss falls by 5.0%, 5.9% and 4.8% versus corrected full seeding at matched true calls and quadratic bit proposals. The ridge–DeepFM predictor reduces mean loss by 11.5% relative to Trinity-D onfresh higher-order instances, with a small regression on quadratic instances. Unequal inner work limits attribution, and classical baselines remain stronger in several settings. Recorded costs quantify conditional quantum potential without a measured quantum-speedup claim

Primary area:
optimization
Keywords:
Black-Box, DeepFM, Optimization, Quantum, QUBO, Tensor-Train

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_DX5EOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper attempts to study how to better perform optimisation of some categorical black-box function, given a limited number of function calls. This is done so by assuming the true function to be some quadratic factor plus a neural branch, which can be learned with quadratic inference and residual correction procedure. Then, the surrogate can be searched for the best candidate to try next.

Critical strengths
  1. The paper seems to tackle an interesting class of optimisation problem (although from the writing it is unclear which), and there seems to be a large amount of experiments ran for the proposed method.

  2. I appreciate some attempts for the theoretical analysis of the algorithm, although the writing of that makes the implication of the results somewhat unclear.

Critical weaknesses
  1. I think the paper in general could be structured and/or written better.

    • The first section of the paper makes it unclear as to what problem the work is solving is and what the proposed method is. I also think that later on, the paper also do not provide adequate explanation as to why their proposed method is different from the others, and why the authors expect the proposed methods to be an improvement over existing techniques. The class of problem being studied in the paper only appears in Sec 3, when it should probably be stated earlier for clarity.

    • In the described methods (Sec 3 and 4), given the problem, it is unclear why the structure for the decomposition of g(x) is chosen as such . It is then unclear as to why the proposed new structure/method makes sense and why there would expect to be improvement over existing works.

    • I also have issues with how the results are presented. I note these points separately in 2.

    While I do note that I am not an expert in quantum-based optimisation, I do still believe the paper is not written clearly enough that the information can easily be followed or inferred, at least by a researcher who do not directly work within the area (I would still expect the contributions and the proposed methods/results to be stated more clearly). I would recommend a rewriting of the paper to make the ideas and claims clearer, which I do not think can be done over the rebuttals period.

  2. I also have some doubts regarding the results.

    • In Table 1, it would seem that Trinity-D (the proposed method) seems to not be the best performing among the benchmarks, it is unclear as to why the negative results are significant and is noteworthy regardless. If they are able to outperform some of the methods that the author cares about, it needs to be explained better why the other algorithms' performance can be disregarded.

    • Additionally, Table 1 lacks error bars. While I believe (if I understand correctly) these do exist in the appendix, the statisitical significance of the reported results are probably important enough that they should be placed in the main text ahead of some of the other content anyway.

    • It is also unclear as to why these benchmarks are chosen. There are several other black-box optimisation methods (e.g., genetic algorithms, Bayesian optimisation, etc.) that the authors could also discuss. It is unclear why their proposed method provide an advantage over these techniques, and could potentially be resolved by additional results or more discussion for the nature of the tested problem.

Questions for authors
  1. Can the authors reiterate more clearly as to what the proposed methods of the paper is (beyond just combining existing techniques together), and why these design choices are significant? This could likely be explained through more detailed ablation of the introduced components (which may already be done in the appendix somewhere or possibly in Table 2 but is unclear as to which result would suggest these), or a better justification of the chosen design choices over existing methods.

  2. Given the presented results that do not look favourable to TRINITY-D, what are the takeaways of the results that is worth it for the presented paper?

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

The paper proposes Trinity, which uses a ReLU-corrected quadratic surrogate to generate complete seeds for a tensor-train search. The idea is reasonable and the writing is mostly clear. However, the central claims are stronger than the evidence, and the comparisons are not controlled well enough to attribute the gains.

Critical strengths
  1. The paper shows that the ReLU secant bound B(A,z) is computable, shrinks with smaller active blocks, and that a single-ReLU counterexample shows raw QUBO seeding can fail even with an exact predictor. This is a useful methodological contribution for anyone building QUBO-based search on neural surrogates.

  2. The paper reports all planned failures, incomplete cohorts, a float32 TT failure, excluded launcher errors, host migrations, and the ablation with mixed signs.

Critical weaknesses
  1. Theorem 1 concerns a retained archive candidate under a uniform surrogate-error assumption, rather than the final adaptive TT output.

  2. BODi has lower mean loss in all seven completed comparisons with Trinity-D. The three photonic discretizations also represent one task family.

  3. In Tab. 3, full seeding with the same ridge, DeepFM predictor slightly outperforms Trinity on fresh higher-order instances.

  4. Any claim of a benefit from “residual-aware” seeding needs a compute-matched control, or the claim should be softened to a better pipeline overall.

Questions for authors

1.Theorem 1 concerns a retained archive candidate under a uniform surrogate-error assumption, rather than the final adaptive TT output. How informative are these bounds on the actual experiments?

  1. Table 11 shows identical 1,024-variable results for SOTA. Are these methods never improve on the shared initial best, or is there a bug or shared-cache effect? If they never improve, what fraction of each method’s gain over initialization comes from the seed itself?
Reviewer_NffkOpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies expensive binary black-box optimization with a DeepFM surrogate, which combines a quadratic FM branch with a one-hidden-layer ReLU branch. It argues that optimizing only the quadratic branch can fail even when the surrogate is exact. It proposes Trinity: fix most variables, approximate the ReLU branch on the remaining subcube by affine functions, and fold it into a small QUBO without auxiliary variables. The resulting seeds then initialize tensor-train search with PROTES. The paper gives conditional guarantees and reports modest gains over full-QUBO seeding on a photonic design task, while baselines such as BODi remain stronger.

Critical strengths

The paper shows that optimizing the quadratic branch of an additive surrogate can fail even under exact prediction. It gives a cheap correction that keeps the QUBO size unchanged and comes with a computable error bound.

Protocols are fixed in advance, all methods share initial designs, photonic results are re-evaluated on a finer grid, and failures and incomplete runs are reported.

The runtime analysis bounds the possible quantum benefit instead of overclaiming it, which is useful for the FMQA line of work.

Critical weaknesses

The need for a QUBO interface is not established. The neural branch has a single hidden layer whose pre-activations are linear in the input (Eq. 2). The full surrogate can therefore be updated exactly and cheaply after each bit flip, and a classical annealer could search it directly. The QUBO form matters mainly for quantum or Ising hardware, where the paper’s own runtime analysis shows little to gain.

The theory does not support the algorithm as run. The main bound covers the best archived seed, not the designs actually evaluated, which come from the later PROTES search. It also assumes a uniform surrogate error, which is unrealistic with so few labels; prediction error then likely dominates the residual term the method controls. The residual bound itself does not appear to inform any algorithmic decision.

The proposed mechanism is not isolated. On higher-order instances, where the correction should matter most, Trinity underperforms full seeding. Ablations that remove the decomposition or the neural correction show no clear effect. Trinity also uses far more surrogate evaluations than its main comparator, and that comparator’s results coincide with random search on the larger photonic tasks.

Limited novelty. Most components, including FM-based QUBO surrogates, PROTES, QUBO decomposition and ReLU relaxations, already exist. BODi, and in many settings GA and CEM, outperform Trinity. With few repetitions and incomplete replications, the evidence remains preliminary.

Questions for authors

How does annealing directly on the full surrogate, with the same anchors and budget, compare with Trinity? If the results are comparable, what does the QUBO interface add in the classical setting?

Do the gains persist against a compute-matched full-seeding baseline and against Trinity without decomposition? Why does the main comparator return the same results as random search on the larger photonic tasks?

Under what conditions on the surrogate error does reducing the residual bound improve the true quality of the evaluated designs? Can any guarantee be extended to the PROTES output?

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

Related papers

Discussion (0)

Sign in to comment.