Abstract: In the discrete Tempotron learning problem, a neuron receives time-varying inputs. For a set of input sequences (the $\mathcal{S}_-$ set), the neuron must remain sub-threshold at all times; for another set (the $\mathcal{S}_+$ set), it must exceed the threshold at least once. This paper presents a graphical treatment of a reformulated Tempotron problem, demonstrating that its general form is equivalent to determining if a polytope is contained within the union of a set of other polytopes. Using results from computational geometry, we show that this problem is $W[1]$-hard. This geometric phrasing provides new insights into the limitations of gradient-based learning and suggests that sampling-based approaches can provide polynomial-time approximations under specific conditions.
Introduction
The Tempotron is a fundamental model in computational neuroscience used to understand how individual neurons learn to process information encoded in spike timings. To "learn," a neuron must adjust its synaptic weights so that it remains quiet (sub-threshold) for certain input patterns while firing (super-threshold) at least once for others. While heuristic algorithms exist for training these models, the underlying mathematical structure and fundamental computational difficulty of the problem have remained opaque. This paper bridges the gap between neuroscience and computational geometry to characterize the "shape" of the Tempotron learning problem.
Geometric Formulation
By introducing a slightly reformulated version called the Continuous Tempotron (C-Tempotron), the learning problem can be mapped onto high-dimensional geometry. The constraints imposed by the "no-spike" patterns ($\mathcal{S}_-$) define a convex polytope in the weight space, referred to as the Inclusion Set ($\mathcal{X}_{inc}$). This represents the "safe zone" where the neuron's activity remains below the firing threshold.
Conversely, the "must-spike" patterns ($\mathcal{S}_+$) define the Exclusion Set ($\mathcal{X}_{exc}$). For a neuron to fire, it only needs to cross the threshold at a single point in time. The inverse of this—the set of weights that fail to cause a spike for a given pattern—defines another set of polytopes. The union of these "bad" polytopes forms the exclusion set. Finding a valid set of weights is thus equivalent to finding a point within the inclusion set that is not covered by the union of the exclusion polytopes.
Computational Complexity and the Geometry of Failure
Mapping the Tempotron to the polytope coverage problem allows for a rigorous analysis of its complexity. Drawing on established results in computational geometry, the paper proves that the problem is $W[1]$-hard. This classification places the Tempotron in the same complexity class as finding cliques in graphs, explaining why finding an exact solution becomes increasingly difficult as the number of inputs and time steps grows.
This geometric perspective also explains why traditional gradient-based learning rules often fail. In high-dimensional space, the exclusion polytopes act as barriers. A gradient-descent algorithm may attempt to move toward a solution but get "pushed" against the boundary of an exclusion zone. Even if a valid solution exists on the other side, the algorithm may become stuck, as the solution space is often "fractured" into many small, disconnected domains spread across the weight space.
Sampling-Based Approximations
While an exact solution is computationally hard to find, the paper proposes a sampling-based path forward. By leveraging polynomial-time methods for sampling from convex bodies, one can approximate the solution space. If we accept a false-negative rate of $\delta$, the number of samples required is $n \ge \log(1/\delta)/p$, where $p$ is the ratio of the solution volume to the inclusion set volume. This approach provides a potential alternative to gradient descent when the solution volume is sufficiently large.
Conclusion and Future Work
This research provides a formal geometric foundation for understanding spiking neuron models. While the $W[1]$-hardness proof highlights the inherent difficulty of the problem, the concept of a "fractured" landscape offers a new way to think about biological learning. Future work remains to address the transition from discrete to continuous time, which may introduce fundamental changes in high dimensions. Additionally, the question of how biological neurons—which lack access to global geometric solvers—manage to navigate these complex landscapes remains a key area for investigation.
Summary updated