- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper relaxes the Ising problem to a difference of convex objective functions. Two solver variants DOCH, and ADOCH that leverage the difference of convex structure are proposed and analyzed. Extensive numerical results are provided that highlight the performance of DOCH and ADOCH on various problem sizes ranging up 10^7 spins.
Critical strengths
The paper proposes a continuous quartic relaxation of Ising as a difference of convex problem, which is elegant and appears to be novel. (Caveat: I am not an expert on Ising, so I cannot relate the solution approach to the literature and earlier relaxation attempts.)
The convergence analysis (convergence to critical points of the relaxed problem) are rather routine and follow the literature. The results and claimed rates agree with the literature and appear to be sound, although I have not analyzed the proofs line-by-line. The key innovation of the paper is the relaxation as difference of convex and the empirical performance.
Critical weaknesses
There seems to be an issue with Fig. 3, b. The update step of DOCH is homogenous, so the iterates at different \beta values from the same initial condition match up to scaling. The same applies to the rounded iterates. Yet, Figure 3, (b) appears to show how the Ising energy changes with changing beta parameter. Can the authors clarify what is going on?
Looking at Table 8: it seems that there can be a large discrepancy between the average case result (mean E) and the best result (smallest E). Is such a discrepancy also present in corresponding baselines? Maybe the key results/tables could be augmented with success probabilities/restarts of both DOCH, ADOCH, and baselines?
Questions for authors
Please address the two points listed as weakness.
2 comments
Thank you for the additional clarification and the revision. I maintain my positive score.
We sincerely thank the reviewer for the encouraging assessment, particularly for recognizing the simplicity of the difference-of-convex formulation, the convergence analysis, and the large-scale experimental evaluation.
W1. Apparent dependence of the Ising energy on β in Figure 3b.
We agree with the reviewer that, for fixed J and α and an identical initialization, changing β only rescales the DOCH iterates by a positive factor. Consequently, their signs and the corresponding discrete Ising energies remain unchanged.
The key clarification concerns the experimental protocol in Figure 3b. Although the 100-spin SK coupling matrix J is fixed, we use independent random initializations for each value of γ. Moreover, we select α separately for each γ using the adaptive energy-based tuning procedure in Appendix M (Algorithm 9), and set β=nγ∣∣J+αI∣∣∞.
Thus, the experiments differ not only in β, but also in their initializations and potentially in α. The homogeneity argument therefore does not imply identical finite-sample average Ising energies across these experiments. The observed differences can arise from initialization variability and changes in the adaptively selected α.
We agree that Figure 3b should not be interpreted as showing a direct dependence of the rounded Ising energy on β. For fixed α and identical initialization, this energy is invariant to β in exact arithmetic. The figure instead reflects the combined effects of independent initializations and adaptive parameter selection in a practical setting.
We have now clarified this distinction in the figure caption and revised Remark G.2 to avoid attributing the observed energy variation directly to β.
W2. Discrepancy between mean and best performance in Table 8.
As discussed in W6 of Reviewer v1pn, Table 8 shows substantial mean-best variability for ADOCH on the planted rank-one signed-bipartite instances. In contrast, DOCH recovers the certified optimum in all runs at n=100 and achieves a mean energy within 1% of the optimum at n=1000. This variability is less pronounced on broader Ising and MAX-CUT benchmarks (Tables 4 and 5), where ADOCH achieves mean objective ratios of 0.984 to 0.994 over 100 independent runs.
Regarding the baselines, Tables 4 and 5 already report mean and best energies over 100 independent runs for DOCH, ADOCH, QQA, and iSCO on broader Ising and MAX-CUT benchmarks. ADOCH achieves mean objective ratios of 0.984 to 0.994, indicating considerably more consistent performance on these instances. Figures 5, 17, and 18 also present histograms and statistical summaries from 100 runs.