Lune

ICML2024Top-tier venue

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

Ruipeng Liu, Borui He, Naveed Tahir, Garrett E. Katz

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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on3

  1. Language Models are Few-Shot LearnersTom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah et al.NeurIPS 2020 · 64,255 citations
  2. Reverse-engineering deep ReLU networksDavid Rolnick, Konrad P. KordingICML 2020 · 121 citations
  3. Learning to Learn with Feedback and Local PlasticityJack Lindsey, Ashok Litwin-KumarNeurIPS 2020 · 38 citations

Related papers

  1. Learning representations for binary-classification without backpropagationMathias LechnerICLR 2020 · 6 citations
  2. Kernelized information bottleneck leads to biologically plausible 3-factor Hebbian learning in deep networksRoman Pogodin, Peter E. LathamNeurIPS 2020 · 48 citations
  3. New Efficient Multi-Spike Learning for Fast Processing and Robust LearningShenglan Li, Qiang YuAAAI 2020 · 5 citations
  4. Identifying Learning Rules From Neural Network ObservablesAran Nayebi, Sanjana Srivastava, Surya Ganguli, Daniel L. K. YaminsNeurIPS 2020 · 27 citations
  5. Bounds on the computational complexity of neurons due to dendritic morphologyAnamika Agrawal, Michael A. BuiceNeurIPS 2025
Dusk over the sea between two cliffs drawn in fine vertical lines