2017/06/05 by Nancy Lynch, Cameron Musco, Lynch, Nancy +3
Computer Science · Engineering · #Advanced Memory and Neural Computing #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Biological sciences #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Neural Networks and Applications #Neural and Evolutionary Computing (cs.NE) #Neurons and Cognition (q-bio.NC) #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1706.01382
openalex publication_date 2017/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study distributed algorithms implemented in a simplified biologically\ninspired model for stochastic spiking neural networks. We focus on tradeoffs\nbetween computation time and network complexity, along with the role of\nrandomness in efficient neural computation.\n It is widely accepted that neural computation is inherently stochastic. In\nrecent work, we explored how this stochasticity could be leveraged to solve the\n`winner-take-all' leader election task. Here, we focus on using randomness in\nneural algorithms for similarity testing and compression. In the most basic\nsetting, given two n-length patterns of firing neurons, we wish to\ndistinguish if the patterns are equal or \ε-far from equal.\n Randomization allows us to solve this task with a very compact network, using\nO (\(\√(n)\log n)/(\ε)\) auxiliary neurons, which is\nsublinear in the input size. At the heart of our solution is the design of a\nt-round neural random access memory, or indexing network, which we call a\nneuro-RAM. This module can be implemented with O(n/t) auxiliary neurons and\nis useful in many applications beyond similarity testing.\n Using a VC dimension-based argument, we show that the tradeoff between\nruntime and network size in our neuro-RAM is nearly optimal. Our result has\nseveral implications -- since our neuro-RAM can be implemented with\ndeterministic threshold gates, it shows that, in contrast to similarity\ntesting, randomness does not provide significant computational advantages for\nthis problem. It also establishes a separation between feedforward networks\nwhose gates spike with sigmoidal probability functions, and well-studied\ndeterministic sigmoidal networks, whose gates output real number sigmoidal\nvalues, and which can implement a neuro-RAM much more efficiently.\n