More Like this

1. Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits

   Su, Lili; Chang, Chia-Jung; Lynch, Nancy (December 2019, Neural computation)

   Winner-Take-All (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 spike-based WTA network to the inherent randomness of the input spike trains. In this work, we consider a spike-based 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 information-theoretic 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 order-optimal (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
2. Spike-Based Winner-Take-All Computation: Fundamental Limits and Order-Optimal Circuits

   https://doi.org/10.1162/neco_a_01242  

   Su, Lili; Chang, Chia-Jung; Lynch, Nancy (January 2019, 7th Workshop on Biological Distributed Algorithms (BDA))

   Winner-Take-All (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 spike-based WTA network to the inherent randomness of the input spike trains. In this work, we consider a spike-based k–WTA model wherein n randomly generated input spike trains compete with each other based on their underlying statistics, and k winners are supposed to be selected. We slot the time evenly with each time slot of length 1ms, and model the n input spike trains as n independent Bernoulli processes. The Bernoulli process is a good approximation of the popular Poisson process but is more biologically relevant as it takes the refractory periods into account. Due to the randomness in the input spike trains, no circuits can guarantee to successfully select the correct winners in finite time. We focus on analytically characterizing the minimal amount of time needed so that a target minimax decision accuracy (success probability) can be reached.We first derive an information-theoretic lower bound on the decision time. We then design a simple WTA circuit whose decision time, for any fixedδ∈(0,1), is order-optimal in terms of its scaling in the network size n, the number of true winners k, and the task complexity TR. 

   more » « less
3. Compressed Counting with Spiking Neurons (Extended Abstract)

   Hitron, Yael; Parter, Merav (January 2019, 7th Workshop on Biological Distributed Algorithms (BDA))

   We consider the task of measuring time with probabilistic threshold gates implemented by bio-inspired 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 [Awerbuch-Peleg, 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
4. Equal sums in random sets and the concentration of divisors

   https://doi.org/10.1007/s00222-022-01177-y  

   Ford, Kevin; Green, Ben; Koukoulopoulos, Dimitris (June 2023, Inventiones mathematicae)

   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
5. Maximum Likelihood Estimation for Learning Populations of Parameters

   Vinayak, Ramya; Kong, Weihao; Valiant, Gregory; Kakade, Sham (January 2019, International Conference on Machine Learning (ICML))

   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