WinnerTakeAll (WTA) refers to the neural operation that selects a (typically small) group of neurons from a large neuron pool. It is conjectured to underlie many of the brain’s fundamental computational abilities.However, not much is known about the robustness of a spikebased WTA network to the inherent randomness of the input spike trains. In this work, we consider a spikebased k–WTA model where in n randomly generated input spike trains compete with each other based on their underlying firing rates, and k winners are supposed to be selected. We slot the time evenly with each time slot of length 1ms, and model then input spike trains as n independent Bernoulli processes. We analytically characterize the minimum waiting time needed so that a target minimax decision accuracy (success probability) can be reached.We first derive an informationtheoretic lower bound on the decision time. We show that to guarantee a (minimax) decision error≤δ(whereδ∈(0,1)), the waiting time of any WTA circuit is at least((1−δ) log(k(n−k) + 1)−1)TR,whereR ⊆(0,1) is a finite set of rates, and TR is a difficulty parameter of a WTA task with respect to setRfor independent input spike trains.Additionally,TR is independent ofδ,n, andk. We then design a simple WTA circuit whose waiting time isO((log(1δ)+ logk(n−k))TR), provided that the local memory of each output neuron is sufficiently long. It turns out that for any fixed δ, this decision time is orderoptimal (i.e., it 2 matches the above lower bound up to a multiplicative constant factor) in terms of its scaling inn,k, and TR.
more »
« less
SpikeBased WinnerTakeAll Computation: Fundamental Limits and OrderOptimal Circuits
Winnertakeall (WTA) refers to the neural operation that selects a (typically small) group of neurons from a large neuron pool. It is conjectured to underlie many of the brain’s fundamental computational abilities. However, not much is known about the robustness of a spikebased WTA network to the inherent randomness of the input spike trains.In this work, we consider a spikebased k–WTA model wherein n randomly generated input spike trains compete with each other based on their underlying firing rates and k winners are supposed to be selected. We slot the time evenly with each time slot of length 1 ms and model then input spike trains as n independent Bernoulli processes. We analytically characterize the minimum waiting time needed so that a target minimax decision accuracy (success probability) can be reached. We first derive an informationtheoretic lower bound on the waiting time. We show that to guarantee a (minimax) decision error≤δ(whereδ∈(0,1)), the waiting time of any WTA circuit is at least ((1−δ)log(k(n−k)+1)−1)TR,where R⊆(0,1)is a finite set of rates and TR is a difficulty parameter of a WTA task with respect to set R for independent input spike trains. Additionally,TR is independent of δ,n,and k. We then design a simple WTA circuit whose waiting time is 2524L. Su, C.J. Chang, and N. Lynch O((log(1δ)+logk(n−k))TR),provided that the local memory of each output neuron is sufficiently long. It turns out that for any fixed δ, this decision time is orderoptimal (i.e., it matches the above lower bound up to a multiplicative constant factor) in terms of its scaling inn,k, and TR.
more »
« less
 Award ID(s):
 1810758
 NSFPAR ID:
 10161820
 Date Published:
 Journal Name:
 Neural computation
 Volume:
 31
 Issue:
 12
 ISSN:
 08997667
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


We consider the task of measuring time with probabilistic threshold gates implemented by bioinspired spiking neurons. In the model of spiking neural networks, network evolves in discrete rounds, where in each round, neurons fire in pulses in response to a sufficiently high membrane potential. This potential is induced by spikes from neighboring neurons that fired in the previous round, which can have either an excitatory or inhibitory effect. Discovering the underlying mechanisms by which the brain perceives the duration of time is one of the largest open enigma in computational neuroscience. To gain a better algorithmic understanding onto these processes, we introduce the neural timer problem. In this problem, one is given a time parameter t, an input neuron x, and an output neuron y. It is then required to design a minimum sized neural network (measured by the number of auxiliary neurons) in which every spike from x in a given round i, makes the output y fire for the subsequent t consecutive rounds.We first consider a deterministic implementation of a neural timer and show that Θ(logt)(deterministic) threshold gates are both sufficient and necessary. This raised the question of whether randomness can be leveraged to reduce the number of neurons. We answer this question in the affirmative by considering neural timers with spiking neurons where the neuron y is required to fire for t consecutive rounds with probability at least 1−δ, and should stop firing after at most 2 t rounds with probability 1−δ for some input parameter δ∈(0,1). Our key result is a construction of a neural timer with O(log log 1/δ) spiking neurons. Interestingly, this construction uses only one spiking neuron, while the remaining neurons can be deterministic threshold gates. We complement this construction with a matching lower bound of Ω(min{log log 1/δ,logt}) neurons. This provides the first separation between deterministic and randomized constructions in the setting of spiking neural networks.Finally, we demonstrate the usefulness of compressed counting networks for synchronizing neural networks. In the spirit of distributed synchronizers [AwerbuchPeleg, FOCS’90], we provide a general transformation (or simulation) that can take any synchronized network solution and simulate it in an asynchronous setting (where edges have arbitrary response latencies) while incurring a small overhead w.r.t the number of neurons and computation time.more » « less

Abstract We study the extent to which divisors of a typical integer n are concentrated. In particular, defining $$\Delta (n) := \max _t \# \{d  n, \log d \in [t,t+1]\}$$ Δ ( n ) : = max t # { d  n , log d ∈ [ t , t + 1 ] } , we show that $$\Delta (n) \geqslant (\log \log n)^{0.35332277\ldots }$$ Δ ( n ) ⩾ ( log log n ) 0.35332277 … for almost all n , a bound we believe to be sharp. This disproves a conjecture of Maier and Tenenbaum. We also prove analogs for the concentration of divisors of a random permutation and of a random polynomial over a finite field. Most of the paper is devoted to a study of the following much more combinatorial problem of independent interest. Pick a random set $${\textbf{A}} \subset {\mathbb {N}}$$ A ⊂ N by selecting i to lie in $${\textbf{A}}$$ A with probability 1/ i . What is the supremum of all exponents $$\beta _k$$ β k such that, almost surely as $$D \rightarrow \infty $$ D → ∞ , some integer is the sum of elements of $${\textbf{A}} \cap [D^{\beta _k}, D]$$ A ∩ [ D β k , D ] in k different ways? We characterise $$\beta _k$$ β k as the solution to a certain optimisation problem over measures on the discrete cube $$\{0,1\}^k$$ { 0 , 1 } k , and obtain lower bounds for $$\beta _k$$ β k which we believe to be asymptotically sharp.more » « less

Consider a setting with N independent individuals, each with an unknown parameter, p_i in [0,1] drawn from some unknown distribution P*. After observing the outcomes of t independent Bernoulli trials, i.e., Xi ~ Binomial(t, p_i) per individual, our objective is to accurately estimate P*. This problem arises in numerous domains, including the social sciences, psychology, healthcare, and biology, where the size of the population under study is usually large while the number of observations per individual is often limited. Our main result shows that, in the regime where t << N , the maximum likelihood estimator (MLE) is both statistically minimax optimal and efficiently computable. Precisely, for sufficiently large N , the MLE achieves the information theoretic optimal error bound of O(1/sqrt(t log N)) for N< exp(t), and O(1/t) for N> exp(t), with regards to the L1 distance between the true cdf and the estimated cdf.more » « less

We provide a new bicriteria O(log2k) competitive algorithm for explainable kmeans clustering. Explainable kmeans was recently introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian (ICML 2020). It is described by an easy to interpret and understand (threshold) decision tree or diagram. The cost of the explainable kmeans clustering equals to the sum of costs of its clusters; and the cost of each cluster equals the sum of squared distances from the points in the cluster to the center of that cluster. The best non bicriteria algorithm for explainable clustering O(k) competitive, and this bound is tight. Our randomized bicriteria algorithm constructs a threshold decision tree that partitions the data set into (1+δ)k clusters (where δ∈(0,1) is a parameter of the algorithm). The cost of this clustering is at most O(1/δ⋅log2k) times the cost of the optimal unconstrained kmeans clustering. We show that this bound is almost optimal.more » « less