On the Feasibility of Single-Pass Full-Capacity Learning in Linear Threshold Neurons with Binary Input Vectors

Ruipeng Liu, Borui He, Naveed Tahir, Garrett Ethan Katz

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.

Tree representation of training sequences

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.

Number of passes required across dimensions

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

Abstract

Known learning rules tend to fall near one of two extremes: single-pass associative learning with low complexity and capacity, and multi-pass iterative learning with high complexity and capacity. In this work we investigate the mathematical feasibility of learning rules that are both single-pass and achieve the theoretical upper bound on capacity. We consider a fairly broad family of learning rules we call ``span rules,'' which include known rules such as Hebbian learning, perceptron learning, and backpropagation as special cases. To our knowledge, previous work has not determined whether single-pass, full-capacity span rules exist, even in the most fundamental case of a linear threshold neuron with binary input vectors, which is the focus of this study. We derive a necessary condition for the existence of such learning rules, which takes the form of a linear program, and show that the linear program is infeasible. This establishes an impossibility result that span rules can not be both single-pass and full-capacity.
BibTeX
@inproceedings{liu2024feasibility,
  author = {Ruipeng Liu and Borui He and Naveed Tahir and Garrett Ethan Katz},
  title = {{On the Feasibility of Single-Pass Full-Capacity Learning in Linear Threshold Neurons with Binary Input Vectors}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=l7vQQi0I2d},
}
Figure