Request documentation on QUBO solver's spiking algorithms

[nnbtam]

Hi Lava team,

I would like to ask if your team can provide some documentation on the algorithms (NEBM and SCIF) behind the QUBO solver of Lava-optimization library.

The reason is that I want to gain insights into the mechanism by which each algorithm solves QUBO and how we may tune the hyperparameters to produce optimal solutions.

Updated: Here is some of my understanding of the two algorithms, which I am not sure if it is correct or not.

• From tutorial 2 on QUBO solving, I understand that the NEBM is implemented based on Jonke et al. spiking Boltzmann machine, NEBM solves QUBO by (1) starts with a random initial state vector x of N variables corresponding to N neurons, and (2) each neuron membrane potential evolves with time so that the optimal state vector x* will correspond to the lowest energy value.

• Meanwhile SCIF is more based on the CuBA LIF (a neuron has 2 internal variables: current and membrane potential) and its mechanism in solving QUBO is similar to NEBM.

However, I still do not understand the sentence mentioned in tutorial 2

Negative weights increase the chance that the connected neuron will spike, positive weights decrease the chance.

as I thought that $p(x_k)(t) = \frac{1}{\tau}e^{u_k(t)}$ and $u_k(t) = b_k + \sum_{l} w_{lk} x_l$. From the two equations in Jonke et al. and given Q is a symmetric matrix, I thought negative weights will then decrease membrane potential and the chance that the connected neuron will spike.

I would appreciate any clarifications and documentation on the two algorithms. Thank you!
Regards,
Tam

[phstratmann]

Dear Tam,

Thanks for reaching out, and for your interest in our QUBO solver!

Could you briefly mention whether you are a member of Intel's Neuromorphic Research Community? If so, I can provide you with a rather detailed documentation. In addition, we will share more information in a talk during our upcoming INRC workshop: https://intel-ncl.atlassian.net/wiki/spaces/INRC/blog/2023/06/08/1945239558/Register+Today+Summer+2023+Workshop

We will also soon have another release. I will see if we find time to extend the QUBO tutorial with a more detailed description.

In general, the QUBO solver solves the problem
min sum_{i} x_i z_i,
where
z_i = -q_{ii} - sum_j x_j q_{i,j}
x_i \in {0,1},
q_{i,j} are the elements of the QUBO matrix.

Each neuron represents a variable x_i. Each neuron has a state corresponding to z_i. Based on this state, the neuron determines whether to switch based on the equations described in the NEBMPyModel (for NEBM) or PyModelCspScifFixed (for SCIF). Two neurons i, j are connected by weights given by q_{i,j}. When one neuron switches its value x_i from 0 to 1, it will send a spike +1 across the weight, or -1 if it switches from 1 to 0.

In addition, each neuron with x_i=1 will send its state z_i to a CostIntegrator neuron. The CostIntegrator neuron then accumulates the states z_i, which determines the overall cost of the current state.

To tune hyperparameters, you can also use the SolverTuner. To see how it works, please refer to test_solver_tuner.py

I hope this helps? If not, please continue asking!

[nnbtam]

Hi @phstratmann, thank you very much for your response. I'm currently registered as an affiliated member of INRC, and my PhD supervisor has submitted the project plan for INRC to become a research member.

Should I ask my supervisor to provide evidence of me being a member of his project to gain access to the detailed documentation?

Thank you!

[phstratmann]

Hi Tam,

Thanks for your patience. You will receive more information on the hyperparameter tuning during our upcoming workshop, in the optimization session. In addition, could you reach out to me via email (firstname.lastname[at]intel.com)? Then I can check your INRC member status and provide you with a more detailed documentation.

[nnbtam]

Hi Philipp,

I have reached out to you via email for the technical documentation. Thank you very much for your valuable time and support!

[nnbtam]

Hi Philipp,

I have a question regarding the new set of SA-based neuron models in the QUBO tutorial. From the example below, does it mean neuron models on Loihi2 could solve QUBO problems with larger number of variables and sparser QUBO matrix, compared to neuron models on CPU?

Thank you very much in advance!
Tam

[phstratmann]

Dear Tam,

That is correct. We are putting our full efforts into iteratively advancing the Loihi solver algorithm. For this reason, we have stopped to advance the CPU backend in October. We will update the CPU version once we have completed the development of the Loihi solver.

Due to this, the Loihi solver will provide a substantially better performance in terms of solution accuracy. Please note that we will later update the QUBO solver algorithm on CPU backend so that it acquires the same solution accuracy, but Loihi is expected to continue being substantially faster and more energy efficient.

I hope this helps.
If so, you may just close the discussion/issue.
If not, feel free to reach out again.