Research map / Learning theory and algorithms / Sample complexity

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

ICML 2024 · Learning theory and algorithms › Sample complexity · approach: Robust and surrogate-loss learning bounds

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that no span rule (weight update in the span of old weights and current input) can be both single-pass and full-capacity for a single linear threshold neuron with binary inputs, via an infeasible linear program at N=8.

Problem

Whether learning rules for a linear threshold neuron on binary inputs can be both single-pass (fit each example immediately, in one presentation) and full-capacity (fit every linearly separable training set).

Approach

Defines span rules (new weights are a scalar combination of old weights and current input), derives a necessary linear-program condition for single-pass full-capacity span learning, and shows the LP is feasible for N≤7 but infeasible for N=8 (with a hand-checkable certificate), and infeasibility propagates to all N≥8.

Key results

• The necessary-condition linear program is feasible for N≤7 and infeasible for N=8 across solvers (Gurobi, MOSEK, ECOS, CBC), with Gurobi the only solver without detected inconsistencies.
• A hand-verified infeasibility certificate for a pair of dichotomies at N=8 (sub-graph rooted at node 6) shows span rules cannot be single-pass and full-capacity.
• Proposition 4.2 shows infeasibility at N extends to all N≥8 by induction.

Measured effects reported in the paper

Surprising findings

• Even for a single linear threshold neuron with binary inputs, single-pass full-capacity span learning is impossible starting at N=8, although it is feasible for N≤7.
• Random subsets of dichotomies at N=8 were often infeasible, with feasibility rate near 0.1 for half-size samples, suggesting multiple infeasible subsets.

Limitations

• Only binary inputs and a single linear threshold unit are studied; real-valued inputs and multi-layer networks are not covered.
• Generalization and margin properties are not addressed; only data-fitting capacity is analyzed.
• Numerical solver issues required a hand-checked certificate and the Monte-Carlo results are only suggestive.

Experimental setup

Datasets: all canonical linearly separable dichotomies of the N-dimensional half-hypercube for N≤9

Metrics: LP feasibility solver run time feasibility rate under random dichotomy subsampling

Baselines: perceptron linear associative networks Hopfield networks support vector machines

Builds on: perceptron learning Hebbian learning Widrow-Hoff learning Winder region enumeration

Closest papers by meaning

• Learning a Single Neuron with Bias Using Gradient Descent (NeurIPS 2021 · similarity 0.86)
• Learning threshold neurons via edge of stability (NeurIPS 2023 · similarity 0.86)
• On the Complexity of Learning Neural Networks (NeurIPS 2017 · similarity 0.85)
• Stable Minima of ReLU Neural Networks Suffer from the Curse of Dimensionality: The Neural Shattering Phenomenon (NeurIPS 2025 · similarity 0.84)
• Two Tales of Single-Phase Contrastive Hebbian Learning (ICML 2024 · similarity 0.84)
• Flat Channels to Infinity in Neural Loss Landscapes (NeurIPS 2025 · similarity 0.83)