Theoretically Provable Spiking Neural Networks
Authors: Shao-Qun Zhang
Zhi-Hua Zhou
Venue: NeurIPS 2022 Accept (2022)
Keywords: Spiking Neural Networks
Self Connection
Continuous Dynamical Systems
Approximation Power
Computational Efficiency

Abstract: Spiking neural networks have attracted increasing attention in recent years due to their potential of handling time-dependent data. Many algorithms and techniques have been developed; however, theoretical understandings of many aspects of spiking neural networks are far from clear. A recent work [Zhang and Zhou, 2021] disclosed that typical spiking neural networks could hardly work on spatio-temporal data due to their bifurcation dynamics and suggested that the self-connection structure has to be added. In this paper, we theoretically investigate the approximation ability and computational efficiency of spiking neural networks with self connections, and show that the self-connection structure enables spiking neural networks to approximate discrete dynamical systems using a polynomial number of parameters within polynomial time complexities. Our theoretical results may shed some insight for the future studies of spiking neural networks.

Theoretically Provable Spiking Neural Networks
Shao-Qun Zhang
Zhi-Hua Zhou
National Key Laboratory for Novel Software Technology Nanjing University, Nanjing 210093, China zhangsq, zhouzh @lamda, nju. edu. cn
Abstract
Spiking neural networks have attracted increasing attention in recent years due to their potential of handling time-dependent data. Many algorithms and tech- niques have been developed; however, theoretical understandings of many aspects of spiking neural networks are far from clear. A recent work [B4] disclosed that typical spiking neural networks could hardly work on spatio-temporal data due to their bifurcation dynamics and suggested that the self-connection structure has be added. In this paper, we theoretically investigate the approximation abil- ity and computational efficiency of spiking neural networks with self connections, and show that the self-connection structure enables spiking neural networks approximate discrete dynamical systems using polynomial number of parame- ters within polynomial time complexities. Our theoretical results may shed some insight for the future studies of spiking neural networks.
Introduction
The past decades have witnessed an increasing interest in spiking neural networks (SNNs) due to their great potential of modeling time-dependent data [2X, 32, 37]. The fundamental units SNNs usually formulated as the combination of an integrated process (e.g., some first-order parabolic equations) and a step firing function. There has been significant progress on computational and implementation techniques for SNNs in computer vision [ 63), speech recognition [60), [9],, rein- forcement learning [ GX], few-short learning [IG 22 [ etc. However, theoretical understand- ings of many aspects of SNNs, such the approximation ability and computational efficiency spatio-temporal systems, are far from clear.
Some researchers [19, 20. 211, [I]] focused on the approximation universality of SNNs, in which some typical SNNs can simulate the standard computational models such as Turing machines, random mapping, etc. There are also efforts on the computational efficiency of SNNs for some specific issues, such as the convergence the limit results and computational complexity of SNNs for the sparse coding problem [34 35 and temporal quadratic programming [S] X], respectively.
access machines, threshold circuits, sequence-to-sequene
Amazingly, a recent study [ theoretically proved that, contrary to previous beliefs, typical SNNs can hardly work well on spatio-temporal data, because they in nature are bifurcation dynamical systems with fixed eigenvalues in which many patterns inherently cannot be learned. They also suggested that adding self-connection structure can enhance the representation ability of SNNs on spatio-temporal systems that fully connect the spiking neurons in the same layer and solves adaptive cigenvalues discrete dynamical systems.
'Zhi- Hua Zhou is the corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we theoretically investigate the approximation ability and computational efficiency of the self coffeeonectinn spike neural networks (scSNNs). Our theoretical results show that equipped with self connections, scSNNs can approximate discrete dynamical systems using polynomial number of parameters within polynomial time complexities. Our main contributions are summarized as follows:
We prove that the proposed scSNNs are universal approximators in Theorem
As for spatial approximation. we prove that broad range of radial functions can be well approximated by scSNNs with polynomial spiking neurons in Theorem D.
As for temporal approximation, we prove that multivariate spike flows can be approximated by scSNNs within polynomial time in Theorem B and verify this conclusion in simulation experiments.
The rest of this paper is organized as follows. Section D introduces notations. Section E presents the scSNNs and some related concepts. Section | provides three key theorems show the universal ap- proximation ability and (parameters and time) complexity of scSNNs for approximating the discrete dynamical system. Section EI develops in-depth discussions of the effects led by self-connection. Section E concludes this work.
2
Notations
Here, we provide some useful notations, which are detailed in Appendix. Let [AV {1, ........... N be an integer set for N E N and | denotes the number of elements in collection, c.g.. [[M]+ = N. Let /-1 be the imaginary unit, and æ x 0 means that every element v; < 0 for any i. Let the sphere S()) and globe (r) be S(r) = {x ||||| =) and B(r) {a | S r] for any r E R, respectively. Given a function (n). we denote by h1(n) = ((g(n) if there exist positive constants C2 and no such that (1g(n) S (n(n) S c2g(n) for every 2 no: (n)) = (g((n) if there exist positive constants and such that (2( < cg(n) for every 2 no: hy(nn) = (g(()) if there exist positive constants e and no such that ha(n) 2 eg(n) for every 2 ha(n) = o(g(n)) if there exists positive constant no such that (a(n) < cg(n) for every c > and n 2 no.
Let C(K, R) be the set of all scalar functions f K + R continuous on K C R". Given a (01, ........ am) E Nm, we define
Jon 802
D f(x) = dr dr
f(x)
nr
where x = (21, Ø2, ..... xn E K. Further, we define
Ck(K, R) = {f f C(K,R) and D" E C(K,R), for E [4]
For 1 s 00, we define
((K,R) - {s f
1/2 < <00) FEC(K,R) and 11 & (/ dx))
This work considers the Sobolev space Wlp(K, K, R), defined as the collection of all functions f E (K(, and Dr f CP(KP (K, R) for all lol E [1]. that is,
| ( D {())
1/P
00.
This paper employs E, to denote the n x n unit matrix and det(.) to indicate the determinant operation on the matrix. Two n-by-n matrices A and B are called similar, denoted as A B, if there exists an invertible n X matrix P such that B = P-1AP AP. The general linear group over n invertible matrices with entries in F. Especially,
field F. denoted GL F),, the of we define that special linear group (L F) is the subgroup of (n, F) and consists of matrices with determinant For any field F, the n X n orthogonal matrices form the following subgroup
O F) (P GL(n, F) P PPT_ E,

---

Static Input
Imput: Spike Sequence
Hidden Layers
Output: Spike Count
Neural Encoding
Neural Encoding
V12
Vis
Fas
(0:-)
-1/Te
V2a
Polsson Encoding
DASIDVS
-1/T
Figure 1: Illustrations of scSNNs and Self Connections.
of the general linear group GL(n, F). Similarly, we have the special orthogonal group, denoted as (O(n, which consists of all orthogonal matrices of determinant 1 and is normal subgroup of (n,, I)). This group is also called the rotation group, generalizing that linearly transforms geome- tries while holding the surface orientation.
Let (x()) be the density function of some probability measure μ, which satisfies
f 1 dx = 1.
(a)) da
=ER
For continuous functions f and g. we have the following equalities under Fourier transform
Ilʃ - 1fo-gollzat gollez()) II golleata) and fō f δ
for the convolution operator *.
Self-connection Spiking Neural Networks
Let be the number of spiking neurons, ull) E R" and s(l) R" denote the vectors of membrane potentials and spikes which u1(1) and (1) are membrane potential and spikes of neuron
i E [n] at time /. 2 O, respectively. Inheriting the recognition in [14], we here consider the self- connection SNN (scSNN) as follows:
du,(t) dt
Tm +1)+
1
Σ (6)
Σ W
(1)
JE(n]
kE[m)
where Tm is a vasitive-valued signal from input channel & [mm] at time V E Raxx and W RRux denote the self-connection and connection weights matrices, respectively. Hence, Σxem Wi indicates the signal re- ceived by neuron i at time I, and Σjenn V1)s;(() denotes the effect the membrane potential of neuron i when neuron j fires spike, illustrated in Figure II. In general, we force the self- connection matrix V be symmetric.
with respect to membrane time, (t) indicates the
Based on the spike response model scheme [12]] Eq. (I) has the following solution with the boundary condition Wrest
(t) = I' exp
8 (s-t" t'
(1)+
+ Σ W ds
(2)
Tm
JE(n)
kE(m)

---

where t' denotes the last firing time t' = maxfs (;(s) = ffiring. 8 < t for pre-given firing threshold "firing > O. Spiking neuron model employs the typical threshold rule, that is, neuron i fires spikes s,(1) at time f. if and only if uu(()) 2 Wfäring. After firing, the membrane potential is instantaneously reset to a lower value trest (rest voltage). Note that this work does not consider using absolute refractory periods [[_]]] or refractory kernels [9].
Let the timing set T; {t (t) Ufirings E [0,T]] record the firing times of neuron i and N₂ = = In general, we consider using the firing rate (T²) - N:/TT to characterize the spike dynamics, where fe indicates the average number of spikes of neuron at time interval [0. 77. It is clearly observed that f! is discontinuous since N, is a step function regarding (t( and time t. To ensure the well-posed characteristics of the firing rate functions, we here employ the spike excitation function fe+ u + to smooth the firing procedure, for example,
ui(l)
Linear:
(t)
Ufrrrig
π t- ((K)
(,(t)
Cos-based:
fe (t) _ 1 cos
2 (k--1) ((K)
U ufering!
where g(k) and ((++1) are two adjacent timings from T; in which & E N+ and ((A) < (k+1), Sim- ilar smooth treatments spike excitation functions can refer to [13]] 333 Thus, f (T) can be approximated by an Instantaneous Firing Rate (IFR) function
(4) where x E Rmm l' E T,, and I E [7]. It is observed that the proposed IFR function fi( () induces a discrete dynamical system, in which ((,,t)= : Rmm - is Spatial function and f(x, is a temporal flow.
f((x,t) = (t((((t)((tttt)))
TR
About Neural Encoding. The actual input data (e.g., image or video) should usually be pre- converted into spiking version before fed up to SNNs. The conversion procedure is called neural encoding, as shown in Figure MI There are two main categories of neural encoding approaches: tem- poral encoding and rate-based encoding; the former encodes input data by exploiting the distance between time instances that fire spikes [90]], and the latter encodes input data as a count sequence of the fired spikes within temporal windows [[8]. The rate-based encoding is the simplest and most popular scheme in SNNs. The representative techniques are usually encoded by Poisson distribu- tion or recorded by dynamic vision sensor [G) 277] Recent years have witnessed a lot of efforts on the information capacity of neural encoding, specially rate-based encoding, from empirical [K. [7]] and theoretical [241, 35 [fj sides. Throughout this paper, we adopt rate-based encoding the de- fault and focus on the firing rates of SNNs, generalizing the computational powers concerning the spike count.
About Firing Rates, When we investigate the dynamics and neural computation of SNNs, the firing rates or equally the number of firing spikes are the key measure of network activities for in- vestigating neural computation and model dynamics because of the close relation between firing rates and network function (including neural input, connectivity, spiking function, and firing pro- cess) [I] Z]. There are great efforts to use firing rates in SNNs for some real-world tasks, such as vision [I3 33, ! and speech recognition [30. By] Besides, Barrett et al. [[]] and Chou et al. [8] showed that the averaged firing rate can approximate the optimal solutions of some quadratic pro- grams within polynomial complexity. This work employs an "instantaneous" firing rate rather than the averaged firing rate or the total number of firing spikes used in previous studies. This manner provides a feasible way to construct the discrete dynamical systems using the IFR functions, based on which we can develop in-depth understandings of SNNs from spatial and temporal aspects.
Approximation to Discrete Dynamical Systems
In this section, we first present the universal approximation for scSNNs, and then show the parame- ters and time complexities of the IFR functions led by scSNNs for approximating discrete dynamical systems from spatial and temporal aspects, respectively.
4.1 Universal Approximation
Now, we present our first theorem about the universal approximation of scSNNs as follows:

---

Definition Let 1 E N+. The function f(z) is said to be l-finite if f is an I-times differentiable scalar function that satisfies
D's(2)da) <0.
Theorem Let C Th be a compact set. 1fe spike excitation funnctioonn Se is I-finite and wi E TR where: i [n]. then for all r []. there exists some time such that the set of IFR finctions f(.,t) K R of the form f(x,tt Lie(n) wif t) is dense in (K R).
Theorem shows that the scSNN universal approximator, which provides solid cornerstone for developing SNNs' theory.
The proof idea of this theorem be summarized follows. We utilize the invertibility of the Fourier transform on Sobolev space Wha (K, IR) (p > 1), to project the concerned functional space Cr(K, (K,R) IR) into a characteristic space, and the corresponding objective function is transformed as single integral over the characteristic space. According Fubini's theorem, the approximation problem on Cr(KRR) can be converted into another that uses multiple integrals to single integral on the characteristic space. The subsequent proof can then be completed along the thought lines of the technical exposition given by Carslaw and Rogosinski [[]]] obtained Appendix
The full proof of Theorem M can be
4.2 c-Approximation with Parameters Complexity
This subsection presents second theorem about the parameters complexity of scSNNs follows:
Definition We say that g is a radial function g(x') g(x) for any ||x'|| = ||2||]
Theorem Given a compact set Tm IRm probability measure p. and radial function g Tt + R. For some apposite spike excitation function Se and any O, there exists some time such that the radial function y can be well approximated by a one-hidden-layer ScSNN of
O(mm25/1) spiking neurons, thut is,
[f(x - <c.
Theorem M shows that the scSNNs with polynomial spiking neurons can well approximate broad scope of radial functions, which may shed some insights on that scSNNs admit input rotations [[66],
such the rotation-based data argument techniques [09] and invariant models [23].
This paper provides ways for proving this theorem. Here, we only introduce the proof idea of the interesting one (full proof is shown in Appendix B), and another proof way can be accessed in Ap- pendix C This proof idea can summarized follows. The radial function is invariant to rotations and dependent on the input norm, corresponding to the phase and norm (i.e., radial) of inputs, respec- tively. is observed that (t) in Eq. (I)) induces a local recurrent function concerning the input (t).. Thus, there exists collection of parameters such that the IFR function is dependent on the norm of inputs. Besides, the IFR function admits the phase since V is a symmetric matrix. Thus, there exist some linear connections (including rotation transformations) such that the weighted aggregation of these spiking neurons is invariant to rotations. Summing up the approximation recognition, there family of radial functions that can be well approximated by one-hidden-laye scSNNs.
We formally begin our proof of Theorem M with some useful lemmas.
Lemma Let g [r, R] > be an T--Lipschitz there exist some time and an IFR function fax 1) led by one-hidden-llyer scSNN of n spiking neurons such that
ALLipschtt.functiin function for r S. R. For any 8 > C. 2 1, and
& C. Tm// (Vr6), (mm((rrr)
sup [(([==])) f(x, t) 88 mE
R is L-Lipschitz radial function supported on the set Lemma' For m > C2 0, g: m
Sa {x 0 C ||ج||| - 2C2mm)
5

---

For any 5 > O, there exist some time t and an IFR function f(x,t) t) led by scSNNs of one-hidder layer with width at most C₂ (C2))))) (mm))) /8 such that
sup (g(x)) - f(x, 1) 8 meRm
Lemma @ shows that the L-Lipschitz radial functions be approximated by the IFR function fæx, t) led by scSNNs of one-hidden layer with polynomial parameters.
Lemma Define
g(x) =
Σ (g) with gi(a) = ||| || e 2t)
(5)
where E, E +11,+11, N a polynomial function of m, and Ω4 are disjoint intervals of width OLL/N) on values in the range (vmm). For any E (11,++1 (i [N]), there exists Lipschitz function h: SA + [-1, +1] such that
J (g(x)) h(x))²² (x) S (C
Lemma E shows that any non- Lipschitz function h(x) can be approximated and bounded by Lips- chitz function with density dº_
Proof of Theorem Let g(x) = N (z) be defined by Eq. (5) and N 2 4C, m2 Accord-
ing to Lemma B. there exists Lipschitz function h with range [-1, +1] such that
V3
[1(x)) g(æ))lea S
C2(m)
Based Lemmas 0 and Z any Lipschitz radial function supported on SA can be approximated by an IFR function f(x, t) led by scSNNs of one- me-hidden layer with width at most C3C, (m) Cg is a constant relative to C2 and This means that there exists some time f such that
(m) 15/4, where
sup h(xx) f(x, 8.
Thus, have
[1(xx) - f(x, ((x,t)ll (()s()) 56.
Hence, the range of f(; 1) is in (-1-1, 5, +1 + 0) C [2, Provided the radial function, defined by Eq. (E), we have
v3
[[ - f(x (lll)) & (l((x) - h(x)) + |1h(x)) - ((xx)))l22()) S C2(m) + 5
This implies that given constants m > C2 > and C3 > 0, for any 8 > and e; E +1} (i E [N]), there exists some time such that the target radial function g can be approximated by an IFR function f(x t) led by scSNNs of one-hidden layer with range [-2, +2] and width at most C2C,(m) that is,
V3
[l((z) f(x, t)llza()) &
C2(m)1/4 + <<50 61
This completes the proof.
4.3 Apprroximation with Time Complexity
The IFR function generates a discrete dynamical system, comprising Spatial function and tem- poral flow. Both Theorems || and focus on the Spatial (e.g., spatial) approximation characteristics of the IFR function. This subsection investigates its temporal characteristics, especially how long it takes for self-connected SNN to achieve a specified task or target function. Now, we present our third theorem about the time complexity of scSNNs as follows.

---

Definition 3 A matrix V E R (ifm S n) is said to be non-degenerate if m. X m sub-matrix Vf has fall rank.
Theorem 3 Let 2 m. Let xx(() rT(a)) and [(xx) A for dς 0, & E [m], and t [T.. is a non-degen non-degener matrix, then for any > and matrix E RR=x" with |G]| < oc, when the time complexity satisfies
Vn IGIll
T2 Ω
<VIV22
there exists some mee-hidden-laee scSNNs with the IFR vector f = (f.....;fa) such that
E ( T) GAIl2 <6.
(6)
Theorem C shows that without training, the scSNNs can well approximate the multivariate spike flows (MSF, i.e. linear functions of X) within an explicit polynomial time complexity. In contrast the conventional ANN theory and our proposed theorems above that show the spatial approxima- tion ability, this theorem portrays the computational efficiency of a flow function led by scSNNs. Besides, there are few studies on the computational efficiency of SNNs, and we summarize the com- parative results in Table II Notice that approximating specific functions, such as MSF in this work, more challenging than solving some problems with locally competitive algorithms [[=]]] Thus, it is observed that Theorem B provides rigorous guarantee for SNNs to solve some algorithmic problems. Besides, Theorem B relaxes the dimension of the self-connection matrix V from n to m, which provides a more general result for approximating MSF with any dimension.
Table 1: Comparative Results Computational Efficiency of SNNs.
Works
Models
Objects
Computational Complexity
Tang et al. [65]
configured SNNs
solving Sparse Coding Problem solving Quadratic Programming
Convergence
Chou et al. [X]]
simple SNNs
Polynomial Complexity
Our Work
scSNNs with Poisson inputs
approximating MSF
Polynomial Complexity
The proof idea of this theorem originates from the attractor theory in dynamical systems. One key lemma is as follows.
Lemma 4 Given U Au Ü U R", and > O, when 1 2 Ω Ya [Aallz)
(e it holds
(A,)( Åll S e, where the modified IFR function f (2, t) is led by a scSNN without connection matrix W fed up to the constant spike sequence at every timestamp.
Lemma g shows that when fed up to constant spike sequence À every timestamp, a weighted sum of IFR functions can converge to an attractor around the inputs within polynomial temporal computation. Based on the results of Lemma EL it suffices to prove that the expectation of the concerned IFR function f (ax, t) can approximate f(,,") (*) within time interval [0, T] where t* < T < Q( v [Gllee. Full proof of Theorem E can be obtained in Appendix D
<v -VIIVIIa
The aforementioned results, time complexity bound in detail, can be verified by a simulated experi- ment. We here simulate a 4 10, 000 spike sequence from the Iris data sets with a timestamp of 0.001 using Poisson encoding. We employ the one-hidden-layed scSNN [B]] that contains self-connection structure as the conducted SNN model. The number of input channels and hidden neurons are 4 and 10, respectively. The self-connection matrix V is randomly sampled from [0, 1] with bias 1/3. The above configurations meet the conditions of Theorem Table lists the papper-prramter values in the conducted scSNN. For any linear matrix G E R4 with || l|| co, define indica- tor to = / || Thus, by exploiting the relation among c, f, and fe, we can verify the explicit <v VIVI
polynomial bound, especially the order of magnitude function ?(-)) in Theorem BL
Figure plots the experimental results. From Figure (a)), the conducted scSNN first approximates the objective function at faster rate and then maintains a lower approximation emor. Figure (Xbb signifies that log(e) inversely proportional log(te), i.e., log(te) + + log(e) = where a, b, > 0. Figure (lc) shows the relation plots between (t.) and log(t). Notice that the conducted ScNN
7

---

Table 2: Hyper-pare parameeer Setting of scSNNs.
Parameters
Value
Parameters
Value
Time Step
0.001
Firing Threshold
1
Expect Spike Count (True)
100
Membrane Time Tix
0.2
Expect Spike Count (False)
10
Time Constant of Synapse T3
0.008
Encoding Length T
10, 000
Maximum Firing
10
Refractory Period
0.016
Maximum Time
10
can achieve the same approximation error at different timestamps, we only care about the shortest one, that is, the blue solid curve below the red dashed line. It is observed that log(t) proportional to log(te)) i.e., log(t) log(tz) + b where O and b E R. In summary, we have demonstrated the effectiveness of our theoretical results.
-15
115
15
L.C.1
(a) Curve: l-e.
(b) Curve: log(te)-log(c)
(c) Curve: log(tt)-log(t)
Figure 2: Magnitude Curves of e, t, and t
5
Discussions
Despite increasing focus the potential of handling spatio-temporal data, the theoretical un- derstandings of many aspects (e.g., approximation ability and computational efficiency) of SNNs still far from clear. Some seminal studies focused on the universality of SNNs. Maass et al. [I19, PU. 2 showed that some typical SNNs can simulate the standard computational models such Turing machines, random access machines, threshold circuits, etc. She et al. [3I]] showed some universal approximation properties of SNNs by exploiting the spike propagation paths. How- ever, the best of our knowledge, few theoretical guarantees on the approximation complexity and computational efficiency of SNNs have been provided. There are only some academic studies on the convergence in the limit results for SNNs solving the sparse coding problem [6a], [Si and the con- vergence rates for SNNs solving temporal quadratic programming [8]. Recently, two studies [[]]] and [ل provided calculable ways for approaching the lower and upper bounds of adaptive SNN
systems, respectively.
Our starting point is recent advance proposed by Zhang and Zhou [ in which they showed that adding self connections enables SNNs to achieve adaptive dynamical systems with spatio-temporal representation. This work developed in-depth analysis of approximation ability and computa- tional efficiency of self connections in SNNs. is observed that self connections facilitate our re- sults; re-using firing spike variables st)) contributes to approximating the norm of input sequences <t)), and the symmetric self-connection matrix coincides with rotation and dual transformations, which are crucial in the proofs of Theorems and B Our theoretical derivatives not only show the universal approximation properties of scSNNs but also disclose the parameters and time com- plexities for ScSNNs approximating discrete dynamical systems, which prospectively provide solid support for the theory development of SNNs. Unfortunately, this paper has not yet shown the the- oretical advantages of scSNNs over non-self-connection SNNs (it is valuable to be studied in the future). But we believe that the current results have disclosed the importance and power of self connections for enhancing the approximation and computational ability of SNNs, which may shed some insights on developing provable and sound SNNs.

---

In light of the preceding merits, many issues are worthy of being studied in the future. One im- portant future issue to explore some practical techniques for scSNNs. For example, Theorem shows the power of scSNNs on representing radial or equally rotation-invariant functions. So we conjecture that adding self connections may be more compatible with some invariant models and data augmentation techniques, such as image rotation [255 29 Besides, the current implementation roughly follows the ideas of Zhang and Zhou [[E]], i.c., the effect from the k-th neuron to the i-th neuron equals to the last spike of neuron k multiplied by weighted factor as shown in Eq. (I). Such self-connection graph enable SNNs to maintain adaptive characteristies for representing dis- crete dynamical systems. However, it inevitably leads to larger memory consumption when the input spike sequences are high- high-dimensional and segh-freueenc.. Therefore, it is prospective to ex- plore some more practical techniques or modules for scSNNs, which may open up possibilities for achieving sound SNNs.
Another important future issue is to develop in-depth theoretical understandings of SNNs. from aspects of approximation complexity, computational efficiency, representation ability [IL5. 266 E.], and per-tearamtterieed architectures [E], ESJ. Furthermore, it is interesting to explore the theoretical advantages of SNNs with self connections over SNNs without ones, especially from the perspectives of approximation, optimization, and generalization.
6 Conclusions
In this paper, we present the theoretical understandings of the approximation ability and computa- tional efficiency of the self-connection SNNs, i.e., scSNNs. We provided three main theorems to show the universal approximation properties, parameters complexity for spatial approximation, and time complexity for temporal approximation of the scSNNs. Our theoretical results disclose the ef- fects of self connections of scSNNs for approximating discrete dynamical systems using polynomial number of parameters within time complexities.
Acknowledgments and Disclosure of Funding
This research was supported by the National Natural Science Foundation of China (NSFC 61921006) and the Collaborative Innovation Center of Novel Software Technology and Industrialization.
References
[1] E. D. Adrian. The impulses produced by sensory nerve endings. The Journal of Physiology. 61(49):156 193, 1926.
[2] A. Aertsen, P. L.M. Johannesma, and D. J. Hermes. Spectro-temports receptive fields of audi- tory neurons in the grassfrog. Biological Cybernetics, 38(4):235-244 1980.
[3] Anumula, D. Neil, Т. Delbruck, and S.-C. Liu. Feature representations for neuromorphic audio spike streams. Frontiers in Neuroscience, 12:23, 2018.
[4] Arora, S. Du, W. Hu, Z. Li, and R. Wang. Fine-grained analysis of optimization and general- ization for overparameterized two-layer neural networks. In Proceedings of the 36th Interna- tional Conference on Machine Learning, pages 322-332, 2019.
[5] D. G. Barrett, S. Denève, and C. K. Machens. Firing rate predictions in optimal balanced networks. In Advances in Neural Information Processing Systems 26, pages 1538-1546, 2013,
[6] W. Bialek, Rieke, R. van Steveninck, and D. Warland. Reading a neural code. Science, 252(5014)11854-1857 1991.
[7] H. S. Carslaw and W. Rogosinski. Introduction to the theory of Fourier's series and integrals. Bulletin of the American Mathematical Society, 37:510-511, 1931.
[8] C.-N. Chou, K.-M. Chung, and Lu. On the algorithmic power of spiking neural networks. In Proceedings of the 10th Innovations Theoretical Computer Science Conference, pages 26:1- 16:1-26:20, 2019.

---

[9] G. Dumont, A. Payeur, and A. Longtin. A stochastic-fiedd description of finite-size spiking neural networks. PLoS Computational Biology. 13(8):1005691, 2017.
[10] R. Eldan and O. Shamir. The power depth for feedforward neural networks. In Proceedings of the 29th Annual Conference on Learning Theory, pages 907-940, 2016.
[11] R. Florian. Reinforcement learning through modulation of spike-timing-deponne synaptic plasticity. Neural Computation, 19(6):1468-15 1500- 2007.
[12] W. Gerstner. Time structure of the activity neural network models. Physical Review E, 51(1):738, 1995.
[13] D. Huh and T. Sejnowski. Gradient descent for spiking neural networks. In Advances in Neural Information Processing Systems 32, pages 1440-1450, 2018.
[14] E. Hunsberger and C. Eliasmith. Spiking deep networks with LIF neurons. arXiv:1510.08829, 2015.
[15] A. Jacot, F. Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 32, pages 8571 8580, 2018.
[16] S. R. Kheradpisheh, M. Ganjtabesh, S. J. Thorpe, and T. Masquelier. STDP-based spiking deep convolutional neural networks for object recognition. Neural Networks, 99:56-67, 67, 2018.
[17] N. Kuwabara and N. Suga. Delay lines and amplitude selectivity are created in subthalamic auditory nuclei: The brachium of the inferior colliculus of the mustached bat. Journal of Neurophysiology, 69(5):1713-1722 1993.
[18] L. Lobo, J. Del Ser, A. Bifet, and N. Kasabov. Spiking neural networks and online learning: An overview and perspectives. Neural Networks, 121:88-100, 2020.
[19] W. Maass. Lower bounds for the computational power of networks of spiking neurons. Neural Computation, 8(1):1-40, 1996.
[20] W. Maass. Networks of spiking neurons: The third generation of neural network models. Neural Networks, 1019):1659-177 1997.
[21] W. Maass and C. M. Bishop. Pulsed Neural Networks. MIT press, 2001.
[22] T. Masquelier and S. J. Thorpe. Unsupervised learning of visual features through spike timing dependent plasticity. PLoS Computational Biology, 3(2)=31, 2007.
[23] S. Mei, T. Misiakiewicz, and A. Montanari. Learning with invariances in random features and kernel models. In Proceedings of the 34th Annual Conference on Learning Theory, pages 1351-3418, 2021.
[24] B. A. Olshausen and J. Field. Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature, (6583))))60776669 1996.
[25] Panda and K. Roy. Unsupervised regenerative learning of hierarchical features in spiking deep networks for object recognition. In Proceedings of the 2016 International Joint Confer- ence on Neural Networks, pages 299-306, 2016.
[26] T. Poggio, A. Banburski, and Q. Liao. Theoretical issues in deep networks. Proceedings of the National Academy of Sciences, 117449:30039-33045, 2020.
[27] R. Q. Quiroga, L. Reddy, G. Kreiman, C. Koch, and Fried. Invariant visual representation by single neurons in the human brain. Nature, 435(7045): 102, 102, 2005.
[28] K. Roy, A. Jaiswal, and P. Panda, Towards baske- machine intelligence with neuromor- phic computing. Nature, 575(7784))607--17,220) 2019.
[29] R. Roy and Kailath. Esprit-estimation of signal parameters via rotational invariance tech- niques. IEEE Transactions Acoustics, Speech, and Signal processing, 37(7):984-99) 1989.
10

---

[30] B. Schrauwen, M. DHaene. D. Verstraeten, and J. Van Campenhout, Compact hardware liquid state machines on FPGA for real-time speech recognition. Neural Networks, 21(2-3):511-523, 2008.
[31] X. She, S. Dash, and S. Mukhopadhyay. Sequence approximation using feedforward spiking neural network for spatiotemporal learning: Theory and optimization methods. In Proceedings of the 9th International Conference Learning Representations. 2021.
[32] T. Shimokawa, K. Pakdaman, and S. Sato. Time-scale matching in the response of leaky integrate-and-fire neuron model to periodic stimulus with additive noise. Physical Review E. 59(3):3427, 1999.
[33] B. Shrestha and G. Orchard. SLAYER: Spike layer error reassignment in time, In Advances in Neural Information Processing Systems 32, pages 4119-1488, 2018.
[34] P. P.T. Tang. Convergence of LCA flows to (c) LASSO solutions. arXiv: 1603.01664 2016.
[35] P. T. P. Tang, T.-H. Lin, and M. Davies. Sparse coding by spiking neural networks: Conver- gence theory and computational results. arXiv:1705.05473 2017.
[36] S. Thorpe, A. Delorme, and R. Van Rullen. Spike- based strategies for rapid processing. Neural Networks, 14(6-7):715-72) 2001.
[37] R. VanRullen, Guyonneau, and S. J. Thorpe. Spike times make sense. Trends in Neuro- sciences, 28(1):1-4, 2005.
(38) E. Vasilaki, N. Frémaux, R. Urbanczik, W. Senn, and W. Gerstner. Spike-based reinforce- ment learning in continuous state and action space: When policy gradient methods fail. PL.S Computational Biology, ((12):e1000588) 2009.
[39] D. Verstracten, B. Schrauwen, D. Stroobandt, and J. Van Campenhout. Isolated word recogni- tion with the liquid state machine: case study. Information Processing Letters, 95(6):521- 528, 2005.
[40] Q Yu, H. Tang, K. C. Tan, and H. Yu. A brain-inspired spiking neural network model with temporal encoding and learning. Neurocomputing, 138:3-13, 2014.
[41] G. Zhang and S.-Q. Zhang. Structural stability of spiking neural networks. arXiv:2207.04876 2022.
[42] S.-Q. Zhang, W. Gao, and Z.-H. Zhou. Towards understanding theoretical advantages of complex-reaction networks. Neural Networks, 151:80-93, 2022.
[43] S.-Q. Zhang, F. Wang, and F.-L. Fan. Neural network gaussian processes by increasing depth. IEEE Transactions on Neural Nenworks and Learning Systems, pages 1-6, 2022.
[44] S.-Q. Zhang, Z.-Y. Zhang, and Z.-H. Zhou. Bifurcation spiking neural network. Journal of Machine Learning Research, 22(253):1-21, 2021.
[45] Z. Zhou. Why over-parame ver-parraettrrizatoon of deep neural networks does not overfit? Science China Information Sciences, 64(1):1-3, 2021.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as a URL)? [No] The simulation experiments employ the codes of Zhang and Zhou [[ and detail the data, settings, and configurations in Pages 7-8. So we believe easily to reproduce our experimen-
tal results. We will publicash our codes soon possible if this paper is accepted. how they
(b) Did you specify all the training details (e.g., data splits. hyper-parameee were chosen)? [Yes] See Table D.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [es]]
(d) Did you discuss whether and how consent was obtained from people whose data you'te 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "9m7e2lRGLRx", "reviewer": "Reviewer_CgzY", "summary": "In this work the authors explore spiking neural networks (SNN) with self-connections and their ability to approximate functions spatially and temporally and how computationally efficient they are. The authors show in the paper that  SNNs can approximate approximate continuous dynamical systems within polynomial parameters and time complexities.\n", "questions": "I have no questions for the authors.", "limitations": "yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper builds on previous work showing that self connections are needed in SNN to work on spatiotemporal data due to their bifurcation dynamics. The paper explores the theoretical properties of SNNs with self-connection which is a novel contribution. However, since it closely follows the previous paper, which already showed that self-connections are needed. the originality is very limited. The theoretical approach used in this paper is also not novel. The theory presented in the paper is sound and there are no major errors as far as I can understand. The paper is fairly clearly presented. However, I would suggest to improve figure 2 by making the axis labels more legible, they are way too small.  Regarding the significance of the paper, the paper essentially corroborates previous literature and therefore I think its significance is also limited. It is unlikely to make a huge impact, but the work done here was necessary and it has been solidly executed.    ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "67rlOTIqjk", "reviewer": "Reviewer_6Qhf", "summary": "This manuscript, theoretically studies the approximation powers and computational efficiency of spiking neural networks with self-connections (scSNNs)). It is demonstrated that the self-connection structure enables spiking neural networks to approximate continuous dynamical systems within polynomial parameters and time complexities.", "questions": "1- Why Theorems 1 \\& 2 only consider compact subsets $K \\subseteq \\mathbb{R}^m$? If the assumption of compactness is removed or at least weakened, can both theorems be still proven?", "limitations": "The authors have discussed the limitations of the work and there is no potential negative societal impact.\n\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is ideally well supported by theoretical arguments. Some proofs (given in both the main text and Appendix) are written in a nice and technical way. Providing summarized proof ideas after theorems is very helpful. \n\n- The paper is well organized and clearly written. The problem was well motivated and the writing was consistent in tackling this problem throughout the work.\n\n\n**Weaknesses**\n- The paper needs more experimental support/evidence. It would be worthwhile to see at least one more example to evaluate the obtained theoretical results.\n\n*Minor issues*:\n\n-- Fig. 2 is not so visible and needs to be improved. Font size and and axes labels should perhaps be larger. \n\n-- It might be better to number some equations (in the proofs) so that one can refer to them.\n\n-- There are some typos/grammatical errors: Line 525, denote ---> denotes; line 530, we an ---> we can; line 563, \"**There**, it is sufficient to show [...]\"? Lines 568 \\& 570, is ---> be", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3ZEu7iNzxIg", "reviewer": "Reviewer_qm3g", "summary": "The authors prove 3 theorems for \"self-connection\" (which I understand as recurrent) spiking neural networks (scSNNs), showing that scSNNs are universal approximators, they can approximate radial functions using polynomial spiking neurons, and they can approximate multivariate spike flows within polynomial time, which they also verify via simulations.", "questions": "The authors should also connect self-connection SNNs with recurrent SNNs -- to my understanding these are the same and the latter term is far more prevalent.\n\nRest of the questions / comments are listed above. Overall the manuscript is very dense and has not been connected well to other results and concepts/practices in the field. No effort is made to make the material useful/accessible to a wider audience. If the authors can clarify my points above and provide more intuitive understanding as well, I would be willing to improve my rating.", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Looking at equation (1), \"self-connection\" seems to mean recurrent connections. There are already theorems showing that recurrent neural networks can approximate dynamical systems (e.g. Schäfer, A. M., & Zimmermann, H. G. (2006). Recurrent Neural Networks Are Universal Approximators. https://doi.org/10.1007/11840817_66 or Seidl, D. R., & Lorenz, R. D. (1991). A structure by which a recurrent neural network can approximate a nonlinear dynamic system. https://doi.org/10.1109/IJCNN.1991.155422). The novelty to my understanding here is to show the same with recurrent *spiking* neural networks -- I am unsure if this has been shown already or is new. The authors are advised to clarify what is new compared to the non-spiking (or possibly existing spiking) proofs.\n\nThe proof uses spike response model (SRM) for the neurons. Would the proof also go through if a Leaky Integrate and Fire (LIF) model is used for neurons?\n\nThe definition of $f(\\mathbf{x},t)$ in Theorem 1 seems to be a weighted sum of the instantaneous firing rates of the individual neurons as defined in equation 4. If I understand correctly, theorem 3 seems to suggest that without training, one can decode these instantaneous firing rates to approximate any MSF. This is reminescent of liquid state machine (reservoir computing). Perhaps the authors can highlight what is different and/or connections if any to the same? Also in theorem 3, $\\mathbf{V}$ is an nxm matrix -- I suppose this is different from the $\\mathbf{V}$ defined in equation 1 as an nxn self-connection matrix. If yes, then please use a different symbol here, else please clarify.\n\nDisclaimer: I am not qualified to comments on the mathematical soundness, and would leave it to other reviewers.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept