1 Search Results for "Lu, Chi-Jen"


Document
On the Algorithmic Power of Spiking Neural Networks

Authors: Chi-Ning Chou, Kai-Min Chung, and Chi-Jen Lu

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)


Abstract
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ève-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 l_1 norm. We give an affirmative answer to our finding by showing that SNN can solve the l_1 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 l_1 minimization problem. We believe that the dual view is of independent interest and may potentially find interesting interpretation in neuroscience.

Cite as

Chi-Ning Chou, Kai-Min Chung, and Chi-Jen Lu. On the Algorithmic Power of Spiking Neural Networks. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{chou_et_al:LIPIcs.ITCS.2019.26,
  author =	{Chou, Chi-Ning and Chung, Kai-Min and Lu, Chi-Jen},
  title =	{{On the Algorithmic Power of Spiking Neural Networks}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.26},
  URN =		{urn:nbn:de:0030-drops-101191},
  doi =		{10.4230/LIPIcs.ITCS.2019.26},
  annote =	{Keywords: Spiking Neural Networks, Natural Algorithms, l\underline1 Minimization}
}
  • Refine by Author
  • 1 Chou, Chi-Ning
  • 1 Chung, Kai-Min
  • 1 Lu, Chi-Jen

  • Refine by Classification
  • 1 Theory of computation → Models of computation

  • Refine by Keyword
  • 1 Natural Algorithms
  • 1 Spiking Neural Networks
  • 1 l_1 Minimization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail