Computing optimal discrete readout weights in reservoir computing is NP-hard

Abstract

We show NP-hardness of a generalized quadratic programming problem, which we called Unconstrained N-ary Quadratic Programming (UNQP). This problem has recently become practically relevant in the context of novel memristor-based neuromorphic microchip designs, where solving the UNQP is a key operation for on-chip training of the neural network implemented on the chip. UNQP is the problem of finding a vector $\mathbf{v}\in S^N$ which minimizes ${\mathbf{v}}^{T}Q\mathbf{v}+{\mathbf{v}}^T\mathbf{c}$, where $S=\{s_1,\dots ,s_n\}\subset \mathbb{Z}$ is a given set of eligible parameters for $\mathbf{v}$, $Q\in {\mathbb{Z}}^{N\times N}$ is positive semi-definite, and $\mathbf{c}\in {\mathbb{Z}}^N$. In memristor-based neuromorphic hardware, $S$ is physically given by a finite (and small) number of possible memristor states. The proof of NP-hardness is by reduction from the Unconstrained Binary Quadratic Programming problem, which is a special case of UNQP where $S=\{0,1\}$ and which is known to be NP-hard.

8 pages submitted to Neurocomputing