  Spiking Neural Networks (SNN) are mathematical models in neuroscience to
describe the dynamics among a set of neurons that interact with each other by
firing instantaneous signals, a.k.a., spikes. Interestingly, a recent advance
in neuroscience [Barrett-Den\`eve-Machens, NIPS 2013] showed that the neurons'
firing rate, i.e., the average number of spikes fired per unit of time, can be
characterized by the optimal solution of a quadratic program defined by the
parameters of the dynamics. This indicated that SNN potentially has the
computational power to solve non-trivial quadratic programs. However, the
results were justified empirically without rigorous analysis.
  We put this into the context of natural algorithms and aim to investigate the
algorithmic power of SNN. Especially, we emphasize on giving rigorous
asymptotic analysis on the performance of SNN in solving optimization problems.
To enforce a theoretical study, we first identify a simplified SNN model that
is tractable for analysis. Next, we confirm the empirical observation in the
work of Barrett et al. by giving an upper bound on the convergence rate of SNN
in solving the quadratic program. Further, we observe that in the case where
there are infinitely many optimal solutions, SNN tends to converge to the one
with smaller l1 norm. We give an affirmative answer to our finding by showing
that SNN can solve the l1 minimization problem under some regular conditions.
  Our main technical insight is a dual view of the SNN dynamics, under which
SNN can be viewed as a new natural primal-dual algorithm for the l1
minimization problem. We believe that the dual view is of independent interest
and may potentially find interesting interpretation in neuroscience.
