Randomness of the solver on accuracy

[szhaoesat]

Hi,
Nice work with interesting ideas!
If I understand the code correctly. The following code is used as the MH step:

FUSE/solver.py

Lines 85 to 87 in b070abf

	rand = jax.random.uniform(sub_key, shape=(p,))
	pos = ((jax.nn.sigmoid(-betas[j] * grad) - rand) > 0).flatten()
	new_state = jnp.where(mask, pos, state)

However, it doesn't change the accuracy performance, if I change it to:
pos = -beta[j]*grad > jnp.zeros((p,))

What do you think about this?

[DevrathIyer]

Sorry for the late response - just seeing this! It's interesting that you note that this doesn't cause any accuracy degradation. We would expect that, without the randomness, the algorithm would just be "hill climbing" and would get caught in local minima. Your suggested code would always follow the gradient (actually, neither the magnitude of the gradient nor the value for beta would matter - only the sign of the gradient).

Let me check it out.

[DevrathIyer]

Hi there - I have used your proposed code change and I see that the success rates decrease significantly. Specifically, I tried TSP conventional and encoded, and I saw TSP6 rates drop from 100% to 9% and 99.4% to 80.8%, respectively.

Have you done any experiments on your end and seen the accuracy not drop?

Thank you for checking out the code and please feel free to write with any further questions!

[szhaoesat]

Hi, thanks for the reply! With the "hill climbing" version code, I checked the accuracy with the following command and changed the different n from [6,8,100]. They all show zero accuracy drop...
When n is equal to 8, the command I used:

python3 solver.py -be 2.5 -lr 0.1 -f tsp -n 8

"hill climbing" log shows even less cycle required:

[generate] Encocded Energy Function! Nothing to generate...
[compile] Compile time was 0.32
33
[lower] Lowering to p-computer...
[lower] Lowering time was 0.00
[run] Beginning execution...
[run] Done! Runtime was 0.63
==== RUN STATS ====
CtS: 3
Best Cycle: 3
Sol qual(%): 0.00

"MH" log shows as below:

[generate] Encocded Energy Function! Nothing to generate...
[compile] Compile time was 0.33
33
[lower] Lowering to p-computer...
[lower] Lowering time was 0.00
[run] Beginning execution...
[run] Done! Runtime was 0.66
==== RUN STATS ====
CtS: 74
Best Cycle: 74
Sol qual(%): 0.00

[DevrathIyer]

Thanks for looking into this! The commands you gave run a single trial (the log text saying "RUN STATS" was a mistake on my part!) - it may be possible that hill climbing works on particular instances, and that the default seed generates these kinds of "lucky" instances.

Could you try running ./scripts/run_tsp_exp.sh and report back the results? This should give us a good sense of whether this is a wider phenomenon (I have run it on my end and thats where I was reporting the earlier numbers from).