Introduction
In machine learning, there is a classic trade-off between efficiency and capacity. Associative rules, like Hebbian learning, are "single-pass": they update weights once per example and are computationally cheap, but they suffer from low storage capacity. Conversely, iterative rules, such as the Perceptron algorithm or Support Vector Machines, boast "full capacity"—they can fit any linearly separable dataset—but often require multiple passes over the data, making them slower and more memory-intensive.
This paper investigates a fundamental question: Is it possible to have the best of both worlds? Specifically, can we design a learning rule for a single neuron that fits every example in a single pass without "forgetting" previous examples, while remaining within the family of "span rules"? (Span rules are those where the new weight vector is simply a linear combination of the old weights and the current input, encompassing Hebbian learning, the perceptron rule, and backpropagation).
Methodology: A Feasibility Problem
To answer this, the researchers framed the search for such a learning rule as an optimization feasibility problem. They formalized the definition of "span rules" as updates where $w^{(t)} = \alpha^{(t)}w^{(t-1)} + \beta^{(t)}x^{(t)}$.
Instead of using traditional real-world datasets, the study utilized the complete set of linearly separable dichotomies of the $N$-dimensional hypercube ($H^N$). This represents the absolute theoretical limit of what a single linear threshold neuron can possibly learn.
The authors modeled all possible training sequences as a massive tree, where each path represents a unique stream of training examples. They then converted the requirements for a single-pass, full-capacity rule into a system of linear inequalities. If a solution exists for this Linear Program (LP), a valid learning rule exists. High-performance solvers (Gurobi, MOSEK, ECOS) were used to test the feasibility of this LP across different input dimensions ($N$).
Key Findings: The $N=8$ Threshold
The study's most surprising finding is a mathematical "impossibility result" that hinges on the input dimension. For small dimensions ($N \le 7$), the linear program is feasible, meaning a single-pass, full-capacity span rule is mathematically possible.
However, once the input dimension reaches $N=8$, these rules vanish entirely. For $N \ge 8$, the linear program becomes strictly infeasible. To ensure this wasn't a numerical artifact, the authors manually identified a specific sub-graph of the training tree for $N=8$ and proved its infeasibility using an exact mathematical certificate.
This reveals a fundamental geometric limit to how much information a simple linear update can carry. While the Representer Theorem suggests optimal weights can be expressed as a linear combination of inputs, this paper proves you cannot calculate those specific coefficients incrementally in a single pass while maintaining full capacity. A single-pass rule must essentially "guess" an update that satisfies the current example while respecting all unseen future examples. As dimensions grow, the geometric constraints become too crowded to satisfy.
Limitations and Future Work
While this establishes a firm boundary for simple neurons, several questions remain open:
- Input Types: The study focuses strictly on binary inputs ($x \in \{-1, +1\}^N$). Feasibility might differ for specific distributions of real-valued data.
- Network Architecture: The result applies to a single linear threshold unit. It is unknown whether multi-layer networks, which possess higher "cardinal capacity," can bypass this limitation via hidden layers.
- Beyond Span Rules: The impossibility result is specific to span rules. Algorithms that store more state than just the current weight vector might still achieve single-pass full capacity, albeit at a higher computational cost.
- Generalization vs. Capacity: This work focuses purely on capacity (fitting the training data). Future research could explore how these strict single-pass constraints affect a model's ability to generalize to unseen data.
Summary updated