Regularized Langevin Dynamics for Combinatorial Optimization

However, it seems to lack theoretical evidence

Is it possible to apply regularization to the solution updates only when detecting local optima?

Thank you for your insightful question. Given the short time period, here we simply outline some perspective for the theoretical analysis.

When not at the local optimum, RLD could accelerate the convergence. The main assumption here is that the graph is sparse (which is very common in CO), so it is unlikely for $d$ variables to be adjacent to each other and the gradient remains accurate after the change.

In terms of the ability to escape optimum, we would like to point out the connection between RLD and path-auxiliary proposal [1], whose first-order version, PAFS, is also the fundamental algorithm behind iSCO. RLD could be treated as a generalized version of PAFS in terms of updating in expectation $d$ coordinates at each step, so it also satisfies Theorem 3 in that paper. Based on this generalization form, we propose a more efficient (parallel) sampling strategy to avoid the sequential sampling in PAFS, thus accelerating the search and significantly outperforming iSCO.

[1] Sun, et al. Path Auxiliary Proposal for MCMC in Discrete Space. ICLR 2022.

How do you initialize the solutions?

The initialization is a Bernoulli distribution of probability 0.5 for each variable.

the hyperparameters are extensively tuned across problems and problem scales

We would like to clarify that all our hyperparameters are tuned via random search (see section A.1) rather than grid search. The hyperparameters in Tables 4 and 5 reflect this randomness rather than an extensive tuning process.

Moreover, only the initial temperature $\tau_0$​ and the regularization target $d$ would impact performance and were carefully tuned in our experiments. We believe that tuning just two parameters is far from overfitting the dataset.

How do you ensure a fair comparison with the baseline methods, especially the ablation baseline (e.g., vanilla SA)

For our ablation baseline, $K$, $T$, $\beta$ and $\tau_0$ are kept the same as the ones used in our method. Another parameter $\alpha$ is searched over {0.001,0.01,0.1}$ as presented in Figure 1.

Methods such as DIMES and DIFUSCO learn to initialize the solutions … Could you please elaborate on the rationale behind the choice of baselines?

We would like to clarify that our method also initializes the solution since it does not guarantee the feasibility. We use the greedy decoding to transform the searched initialization to a feasible solution. For DIMES and DIFUSCO, they also have the greedy decoding variant. But given their poor performance, we only report the best variant with a sampling-based decoding.

Is the high efficiency of your method due to the ability to use a very large batch size … Comparing per-instance solution duration …

We test all instances sequentially in our experiment, so the per-instance solution duration is simply total_time/(# instances). RLSA only needs <0.2s per instance except on ER-[9000-11000] (around 6s per instance).

it appears to be much less effective for a prominent and extensive subset of CO problems involving global constraints

This is an insightful question but we want like to mention that tackling global constraints typically need strong inductive biases and this is a common challenge for all energy-based models (EBMs). Here we refer to some recent EBM-based CO solvers that also face this dilemma and exclude the evaluation on the problems with global constraints such as TSP.

[1] Haoran Sun et al., ‘Revisiting Sampling for Combinatorial Optimization’, ICML 2023.

[2] Dinghuai Zhang et al., "Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets", NeurIPS 2023 spotlight.

[3] Sebastian Sanokowski et al., A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization. ICML 2024.

The reason behind is because the global constraints are highly structured, while EBMs are general solvers, whose formulation itself prevents a better performance than heuristics with a strong inductive bias such as k-OPT.

It seems reasonable to compare your method against other approaches designed to escape local optima during solution improvements. Are there any feasible alternatives you considered for comparison?

Note that SA itself is a strategy to escape the local optimum and we have already included the SOTA baseline iSCO. We have also experimented with the restarting strategy on top of our ablation baseline but find no clear advantage.

Another method is semidefinite programming, as we included in Table 2. However, this method is in general very slow compared to SA methods.

Is it possible to adaptively regularize the solution updates?

We have tried but found no clear gain. Note that RLD itself should be counted as an adaptive strategy on the MCMC proposal (with an adaptive $\alpha$ in Equation 8).

There are concerns regarding experimental fairness, particularly in the comparison of iSCO and RLSA… The experimental section in the iSCO paper reports DIMES achieving a size of 42.06 on ER-[700–800] in 12.01 minutes and 332.80 on ER-[9000–11000] in 12.51 minutes, which aligns with previously reported results. However, the iSCO results in this paper do not consistently reflect this…

We sincerely appreciate your question and want to offer an important clarification on a confounding issue. That is, in the iSCO paper (Sun et al. 2023), they reported the average running time per instance for iSCO, while they reported the total running time for all other methods (DIMES included). This mis-alignment in time measurements makes iSCO look 16 or 128 times better than the reality (given the test-set size is 16 and 100 for ER graphs). We have contacted the authors of that paper, and they confirmed that it was indeed an error on their behalf. (if needed and possible, we could attach their relevant material)

To fix such a confounding issue, we reported the total running time for all the methods in our results tables. This is why our numbers look inconsistent to that in the iSCO paper, but for a good reason. We will revise related sentences about those tables, to make the point more transparent.

We fully understand that the mistake in Sun et al. 2023 caused the confusion in your review. If the above clarification sufficiently addressed this issue, would you kindly adjust your score accordingly?

Since RLSA consistently outperforms RLNN across test cases, the contribution of the neural network method appears to be limited.

Recall that our RLNN is designed to address a limitation of RLSA, i.e., its reliance on closed-form formulation of the gradient (as mentioned in the first sentence of Section 3.3). In other words, RLSA requires additional knowledge for making it works; when such knowledge is not available, RLNN is a better alternative. And it should not be surprising that RLSA performs better since it has more prior knowledge.

RLNN is weaker than DiffUCO

In fact, RLNN has comparable performance to DiffUCO, based on the results in Tables 1 and 2 (RLNN outperforms DiffUCO in 4 out of 6 datasets). More importantly, the training of RLNN is much more efficient than that of DiffUCO because RLNN only needs to be trained locally while DiffUCO relies on a sequential training loss. For example, the training time is 1 hour for RLNN and 2 days plus 2 hours for DiffUCO (reported in section C.6, Sanokowski, et al. 2024) on RB-200.

typos & metrics

We want to apologize for the presentation issues, and we would fix them in our future version.

We sincerely thank you for your positive feedback, here are the response to your concerns.

Is there any advantage of RLNN compared to RLSA? It seems it falls behind of RLSA on both decision quality and inference time.

Recall that our RLNN is designed to address a limitation of RLSA, i.e., its reliance on closed-form formulation of the gradient (as mentioned in the first sentence of Section 3.3). In other words, RLSA requires additional knowledge for making it works; when such knowledge is not available, RLNN is a better alternative. And it should not be surprising that RLSA performs better since it has more prior knowledge.

It would be better if the paper could give a theoretical analysis of the proposed regularization.

Thank you for your suggestion. Given the short time period, here we simply outline some perspective for the theoretical analysis.

When not at the local optimum, RLD could accelerate the convergence. The main assumption here is that the graph is sparse, so it is unlikely for $d$ variables to be adjacent to each other and the gradient remains accurate after the change.

In terms of the ability to escape optimum, we would like to point out the connection between RLD and path-auxiliary proposal [1], whose first-order version, PAFS, is also the fundamental algorithm behind iSCO. RLD could be treated as a generalized version of PAFS in terms of updating in expectation $d$ coordinates at each step, so it also satisfies Theorem 3 in that paper. Based on this generalization form, we propose a more efficient (parallel) sampling strategy to avoid the sequential sampling in PAFS, thus accelerating the search and significantly outperforming iSCO.

[1] Sun, et al. Path Auxiliary Proposal for MCMC in Discrete Space. ICLR 2022.

We sincerely appreciate the reviewer's thoughtful comments and constructive suggestions.

the novelty appears somewhat incremental—essentially amounting to relatively simple adjustments to existing techniques

We see your point but would like to highlight that our approach addresses a fundamental limitation of the previous method (discrete Langevin-like sampling in Zhang et al., 2022, and iSCO in Sun et al. 2023) in solving CO problems, with SOTA performance on benchmarks and significantly reduced computational costs. Which should be informative for the research community, we hope.

However, the theoretical justification for why their specific form of regularization effectively escapes local minima remains somewhat intuitive rather than rigorously proven.

Thank you for your insightful question. Given the short time period, here we simply outline some perspective for the theoretical analysis.

When not at the local optimum, RLD could accelerate the convergence. The main assumption here is that the graph is sparse, so it is unlikely for d variables to be adjacent to each other and the gradient remains accurate after the change.

In terms of the ability to escape optimum, we would like to point out the connection between RLD and path-auxiliary proposal [1], whose first-order version, PAFS, is also the fundamental algorithm behind iSCO. RLD could be treated as a generalized version of PAFS in terms of updating in expectation $d$ coordinates at each step, so it also satisfies Theorem 3 in that paper. Based on this generalization form, we propose a more efficient (parallel) sampling strategy to avoid the sequential sampling in PAFS, thus accelerating the search and significantly outperforming iSCO.

[1] Sun, et al. Path Auxiliary Proposal for MCMC in Discrete Space. ICLR 2022.

Have you evaluated its performance on larger-scale problems (e.g., tens of thousands of nodes)?

Please notice our results on ER-[9000-11000] in Table 1: RLSA outperforms iSCO using only 2.5% running time. Also, RLNN takes a similar amount of time as DIMES but delivers significantly better results. All these results provide strong evidence for the advantage of our approach on larger-scale problems.

However, previous diffusion-based sampling methods have also demonstrated applicability to problems with global constraints, such as vehicle routing or scheduling tasks. Considering that your evaluations mainly focus on combinatorial problems with relatively simple (local) constraints, have you investigated how well your method performs on problems with stronger global constraints, such as the Traveling Salesman Problem (TSP)?

This is an insightful question but we would like to clarify that tackling global constraints typically need strong inductive biases and this is a common challenge for all energy-based models (EBMs). Here we refer to some recent EBM-based CO solvers that also face this dilemma and exclude the evaluation on TSP.

[1] Haoran Sun et al., ‘Revisiting Sampling for Combinatorial Optimization’, ICML 2023.

[2] Dinghuai Zhang et al., "Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets", NeurIPS 2023 spotlight.

[3] Sebastian Sanokowski et al., A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization. ICML 2024.

The reason behind is because global constraints are highly structured, while EBMs are general solvers, whose formulation itself prevents a better performance than heuristics with a strong inductive bias such as k-OPT.

Besides, we would like to mention that diffusion models themselves cannot handle global constraints, whose success heavily relies on (i) the supervision, which smooths the landscape (ii) decoding heuristics (2-OPT, MCTS or permutation), which is the key to handle the global constraint.