# Learning with Boolean threshold functions

arXiv: https://arxiv.org/abs/2602.17493 · HTML: https://mlsanity.com/paper/2602.17493/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 37 references that are in the map.
- First posted on arXiv 19 Feb 2026.

## Builds on (most cited first, 16 of 16)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models](https://mlsanity.com/paper/2211.10438/) (2022)
- [Learned Step Size Quantization](https://mlsanity.com/paper/1902.08153/) (2019)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [PACT: Parameterized Clipping Activation for Quantized Neural Networks](https://mlsanity.com/paper/1805.06085/) (2018)
- [Deep Differentiable Logic Gate Networks](https://mlsanity.com/paper/2210.08277/) (2022)
- [Learning Without Loss](https://mlsanity.com/paper/1911.00493/) (2019)
- [Understanding Boolean Function Learnability on Deep Neural Networks: PAC Learning Meets Neurosymbolic Models](https://mlsanity.com/paper/2009.05908/) (2020)
- [Projecting onto rectangular hyperbolic paraboloids in Hilbert space](https://mlsanity.com/paper/2206.04878/) (2022)
- [A projection-based framework for gradient-free and parallel learning](https://mlsanity.com/paper/2506.05878/) (2025)
- [The Flow-Limit of Reflect-Reflect-Relax: Existence, Stability, and Discrete-Time Behavior](https://mlsanity.com/paper/2512.23843/) (2025)
- [Backpropagation from KL Projections: Differential and Exact I-Projection Correspondences](https://mlsanity.com/paper/2512.24335/) (2025)

## Built on by (most cited first, 2 of 2)

- [Transformers Can Learn Rules They've Never Seen: Proof of Computation Beyond Interpolation](https://mlsanity.com/paper/2603.17019/) (2026)
- [Machine-learnable Sets](https://mlsanity.com/paper/2606.28947/) (2026)

## Abstract (arXiv)

We develop a method for training neural networks on Boolean data in which the values at all nodes are strictly ± 1, and the resulting models are typically equivalent to networks whose nonzero weights are also ± 1. The method replaces loss minimization with a nonconvex constraint formulation. Each node implements a Boolean threshold function (BTF), and training is expressed through a divide-and-concur decomposition into two complementary constraints: one enforces local BTF consistency between inputs, weights, and output; the other imposes architectural concurrence, equating neuron outputs with downstream inputs and enforcing weight equality across training-data instantiations of the network. The reflect-reflect-relax (RRR) projection algorithm is used to reconcile these constraints. Each BTF constraint includes a lower bound on the margin. When this bound is sufficiently large, the learned representations are provably sparse and equivalent to networks composed of simple logical gates with ± 1 weights. Across a range of tasks -- including multiplier-circuit discovery, binary autoencoding, logic-network inference, and cellular automata learning -- the method achieves exact solutions or strong generalization in regimes where standard gradient-based methods struggle. These results demonstrate that projection-based constraint satisfaction provides a viable and conceptually distinct foundation for learning in discrete neural systems, with implications for interpretability and efficient inference.