- Rating
- 2
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper proposes LEMON, a continuous relaxation framework for finite-state combinatorial optimization. Each discrete variable is represented by a probability vector on a simplex, and a concave attractor is added to remove fractional local minima. The main theoretical result shows when the continuous local minima correspond exactly to the one-flip local minima of the original discrete problem. The solver then uses projected ADAM, discrete decoding, exact verification, and optional correction. Experiments cover MIS, graph coloring, Max-k-Cut, and k-way number partitioning.
Critical strengths
-
The product-simplex representation preserves the native categorical one-variable neighborhood rather than replacing one label change with multiple binary flips. The landscape-equivalence result also applies to arbitrary finite-order interactions and provides a sharp characterization of the admissible attractor slope.
-
The separation between continuous search and discrete certification is a strong design choice. The method does not assume that projected ADAM converges to a valid discrete local optimum; instead, it verifies feasibility and exact one-flip changes after decoding.
Critical weaknesses
-
The Max-5-Cut ablation in Table 5 appears inconsistent with the stated local-optimality verification procedure. The paper states that the No-ADAM and Projected-ADAM variants use the same discrete correction procedure, and that Max-k-Cut post-processing ends with an exhaustive check of all one-vertex moves. Therefore, both final solutions should be one-vertex local optima. For a nonnegative weighted -cut, every such local optimum satisfies , where is the total edge weight. Thus, for paired instances, . However, Table 5 reports 895.82 versus 1372.40, while . The reported values therefore violate this necessary condition. This suggests that the reported values, experimental protocol, weight assumptions, or actual post-processing procedure differ from the description.
-
The NPP implementation description does not clearly explain the large improvement attributed to projected ADAM. The manuscript states that NPP starts from an LPT partition embedded at simplex vertices and then applies projected ADAM using Eq. (21), while the other blocks remain at vertices. For positive inputs, the LPT solution is already locally optimal with respect to a single-item move under the max-minus-min discrepancy objective. At such a vertex, the stated gradient gives . Under the stated projection and standard zero-initialized ADAM moments, the projected update appears to return to the same simplex vertex. It is therefore unclear how the continuous stage leaves the LPT initialization and produces the reported 86.1% improvement. Moreover, Eq. (21) applies only while the other blocks remain at vertices, so the actual NPP update procedure needs to be clarified.
Questions for authors
-
Can the authors reconcile the Max-5-Cut results in Table 5 with the exhaustive one-vertex local-optimality check? In particular, could the authors report the total edge weight, final cut value, and best remaining one-vertex improvement for both variants and confirm that both underwent exactly the same correction and verification procedure?
-
What exact operation allows the NPP projected-ADAM search to leave the LPT simplex vertex? Please clarify the ADAM initialization, block-update order, projection procedure, attractor coefficient, and whether any perturbation, soft initialization, or intermediate discretization is used. If multiple blocks become fractional, how is Eq. (21) used?
-
In Table 4, the LEMON coloring result reports a 100% certificate rate and zero corrections while the final conflict value is . Does “Certificate” mean only one-flip local optimality rather than a proper-coloring certificate? If so, could these two notions be reported separately?
-
What independent reference values support the statement that LEMON matches the reference optimum on 53/61 MIS instances? Table 8 does not provide an explicit optimum column, and its caption also states that LEMON beats pCQO-MIS in all cases, although some displayed rows contradict this statement. Could the authors clarify the source of the 53/61 count and correct the benchmark summary?
4 comments
Reply to Q3, and Q4 of Reviewer ZPFy
Q3: Coloring certificate.
As clarified in Q3 of reviewer nhWp, the 100% (10/10) certification rate refers to one-flip local optimality, not proper coloring (zero conflicts), which was achieved in only 1/10 runs. We now report these outcomes separately in the revised manuscript (lines 1391–1392).
Q4: MIS reference values.
As clarified in Q3 of reviewer nhWp, the 53/61 count means LEMON matches or exceeds both pCQO-MIS and ReduMIS, not that it attains certified global optima. Against pCQO-MIS, LEMON performs better/equally/worse on 9/48/4 instances; against ReduMIS, the counts are 1/52/8. On p_hat1000-3, LEMON achieves 65, compared with 67 and 68, respectively, correcting the previously misstated deficits. We have revised the abstract and Table 10 caption accordingly.
Thank you for the detailed response and revisions. I appreciate that the authors acknowledged the original Max-5-Cut experimental error and clarified the Gaussian-perturbed initialization and blockwise discretization used for NPP. These revisions address important concerns in my original review. However, I still have two concerns about the experimental evidence.
- The revised Max-5-Cut experiment does not fully resolve the certification concern.
The authors now report one-flip certification rates of 57% and 93% for No ADAM and Projected ADAM, respectively. This clarifies why the local-optimality bound need not hold for every time-limited output. However, the original manuscript described exhaustive verification after discrete correction, whereas the revised experiment introduces a 5 ms budget under which some outputs remain uncertified. The distinction between certified solutions and time-limited outputs should be made explicit. I would also like to know whether the reported certification rates are measured after correction and whether verification time is included in the budget.
- The NPP results still do not fully isolate the contribution of projected ADAM.
The Gaussian perturbation explains how the algorithm can escape the LPT local optimum, and the revised block-update procedure addresses the condition required by Eq. (21). However, the new ablation compares unperturbed LPT with perturbed projected ADAM, with and without the attractor. It does not isolate the improvement caused by projected ADAM itself from that caused by perturbation and subsequent discrete correction. A comparison against Gaussian-perturbed LPT followed by the same discrete correction, without projected ADAM, would be important for supporting the claimed contribution of continuous optimization.
Overall, the revisions improve the clarity of the implementation and correct several issues in the original experiments. Nevertheless, I remain unconvinced that the current evidence fully supports the claimed benefits of the continuous search procedure. I therefore maintain my Weak Rejection recommendation.
We appreciate the reviewer's positive acknowledgment of the revisions and the quick follow-up.
1. The exhaustive verification described in the original manuscript applies to our main benchmark experiments. The Max-5-Cut ablation instead uses a fixed 5 ms budget for optimization and a discrete correction to fairly compare No ADAM and Projected ADAM. The reported certification rates (57% and 93%) are measured after correction, using one-flip verification performed outside the 5 ms budget. Thus, all outputs are checked, but only those passing the one-flip check are certified; the remaining outputs are time-limited solutions without a local-optimality guarantee. We have now mentioned the verification procedure in the revised manuscript.
2. We agree that the earlier ablation did not fully isolate the contribution of projected ADAM. To address this, we added the suggested baseline: Gaussian-perturbed LPT followed by discrete correction, without ADAM. We repeated the comparison over the same 10 seeds, using identical perturbation and correction procedures. This allows us to separate the effects of perturbation, continuous optimization, and the attractor.
| Dist., | LPT MSD | LPT + Pert | LPT + Pert + Corr | ADAM () | LEMON () | Gain vs. LPT | Gain vs. Corr |
|---|---|---|---|---|---|---|---|
| , 5 | 59.13% | 58.06% | |||||
| , 10 | 87.31% | 87.74% | |||||
| , 5 | 57.79% | 58.54% | |||||
| , 10 | 71.90% | 71.36% | |||||
| , 5 | 43.90% | 42.79% | |||||
| , 10 | 55.52% | 57.04% |
LPT + Pert denotes Gaussian perturbation followed by decoding, while LPT + Pert + Corr additionally applies discrete correction without ADAM. The gain columns report LEMON's relative MSD reduction against LPT and perturbation-plus-correction, respectively. All MSD values are averaged across the 10 seeds (lower values are better).
The results directly address the reviewer's concern:
-
Perturbation and correction alone: The resulting MSD remains close to the original LPT solution across all six settings; indicating that one-flip correction alone largely returns to comparable local optima.
-
Contribution of projected ADAM: Even without the attractor (), projected ADAM reduces mean MSD by 12.2% to 26.9% relative to perturbation-plus-correction across all six settings.
-
Additional contribution of the attractor: Adding the attractor further reduces MSD relative to ADAM (). Overall, LEMON achieves 42.79% to 87.74% lower MSD than perturbation-plus-correction.
Thus, the controlled comparisons demonstrate that projected ADAM improves solution quality beyond Gaussian perturbation and discrete correction, while the attractor provides an additional benefit.
We have included these comparisons, clarified the experimental procedure, and updated Table 7 in the revised manuscript.
Reply to Q1, W1, Q2 & W2 of Reviewer ZPFy
Thank you for carefully examining the local-optimality conditions and NPP initialization, and for identifying two points that required clarification and correction.
Q1: Max-5-Cut edge-weight bound and verification
We thank the reviewer for identifying this inconsistency. We reran the experiment on ER(100, 0.3) graphs over 100 paired runs, using the same 5 ms wall-clock budget per run.
Both variants use the same discrete correction procedure, but the fixed runtime budget does not guarantee convergence to a one-flip local optimum always. Thus, the bound C≥0.8W applies to certified solutions, not necessarily to every time-limited output.
Under the same budget, projected ADAM achieves a 16.98% higher mean cut and increases the one-flip certification rate from 57% to 93%, demonstrating better solution quality and more frequent convergence to discrete local optima.
W1: Max-5-Cut ablation consistency
The original No-ADAM value of 895.82 resulted from sampling from the wrong ER graph. We corrected the graph-generation setting and reran both variants under identical 5 ms budgets.
The corrected result s are adressed in Q1. The respective one-flip certification rates are 57% and 93%, confirming that projected ADAM more frequently reaches locally optimal solutions within the same runtime budget.
We have clarified the fixed-budget protocol and corrected the corresponding results in the revised manuscript.
Q2 & W2: Exact NPP operations.
The reviewer is correct: projected ADAM initialized at a one-item locally optimal LPT vertex, with zero moments, cannot escape through the stated block updates. Our implementation addresses this through Gaussian-perturbed initialization and intermediate discretization, now clarified in Appendix D of the revised manuscript.
The procedure is as follows:
Gaussian-perturbed initialization. Starting from the LPT assignment sLPT, we initialize qi=ΠΔ(esiLPT+zi), where zi∼N(0,Ik) independently. The perturbation can change the decoded labels: a competing label b overtakes the LPT label a whenever zi,b−zi,a>1. Thus, multiple items can change assignments simultaneously, allowing the search to escape the one-item local optimum of LPT.
Sequential block optimization. We process items in random order, keeping all inactive blocks at their decoded simplex vertices. For each active block, we compute the k exact conditional endpoint energies and apply projected ADAM. The updated block is then decoded by argmax and reset to the corresponding vertex. Consequently, Equation (21) is always evaluated with all other blocks at vertices, as required.
Parameters and verification. We use learning rate 0.08, (β1,β2)=(0.9,0.999), ϵ=10−8, zero-initialized moments, and Euclidean simplex projection. The attractor coefficient is η=0.25 for 32-bit integer inputs and η=δ/2, with δ as the smallest decimal resolution of the input numbers. For example, {2.15,10.3,7.12} gives δ=0.01 and η=δ/2=0.005. These choices satisfy the sufficient slope condition 2η⩽δ. Final assignments are independently checked for feasibility and improving one-item moves.
NPP ablation. To separate the effects of perturbation and the attractor, we conducted a 10-seed ablation comparing unperturbed LPT, Gaussian-purturbed projected ADAM without the attractor (η=0), and with the attractor (LEMON, η>0). Representative results from Table 7 are shown below.
We see that LEMON achieves the lowest mean MSD in all six settings, reducing MSD by 43.90% to 87.31% relative to LPT. The ablation separates two effects: Gaussian perturbation allows the search to leave the original LPT assignment, while the η=0 versus η>0 comparison demonstrates the attractor's additional benefit. One-item local optimality is independently verified after discrete correction, rather than assumed from projected ADAM convergence.
We have further explained these in Appendix D of the revised manuscript.