Learning with Boolean threshold functions

• URL: http://arxiv.org/abs/2602.17493v1
• Date: Thu, 19 Feb 2026 16:07:25 GMT
• Title: Learning with Boolean threshold functions
• Authors: Veit Elser, Manish Krishan Lal,
• Abstract summary: We develop a method for training neural networks on sparse data in which the values at all nodes are strictly $pm 1$.<n>Across a range of tasks, this method provides a viable and efficient foundation for learning in neural systems.
• Score: 0.013714053458441644
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a method for training neural networks on Boolean data in which the values at all nodes are strictly $\pm 1$, and the resulting models are typically equivalent to networks whose nonzero weights are also $\pm 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 $\pm 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.

Related papers

• BEP: A Binary Error Propagation Algorithm for Binary Neural Networks Training [21.908847701590428]
  Binary Neural Networks (BNNs) offer substantial reductions in computational complexity, memory footprint, and energy consumption.<n>However, training BNNs via gradient-based optimization remains challenging due to the discrete nature of their variables.<n>This paper introduces Binary Error Propagation (BEP), the first learning algorithm to establish a principled, discrete analog of the backpropagation chain rule.
  arXiv  Detail & Related papers  (2025-12-03T19:03:55Z)
• A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networks [0.0]
  We present a formal and constructive simulation framework for nondeterministic finite automata (NFAs) using time-shared, depth-unrolled feedforward networks (TS-FFNs)<n>Our formulation symbolically encodes automaton states as binary vectors, transitions as sparse matrix transformations, and nondeterministic branching-including $varepsilon$-closures-as compositions of shared thresholded updates.
  arXiv  Detail & Related papers  (2025-05-30T01:18:35Z)
• Semantic Loss Functions for Neuro-Symbolic Structured Prediction [74.18322585177832]
  We discuss the semantic loss, which injects knowledge about such structure, defined symbolically, into training. It is agnostic to the arrangement of the symbols, and depends only on the semantics expressed thereby. It can be combined with both discriminative and generative neural models.
  arXiv  Detail & Related papers  (2024-05-12T22:18:25Z)
• Robust Stochastically-Descending Unrolled Networks [85.6993263983062]
  Deep unrolling is an emerging learning-to-optimize method that unrolls a truncated iterative algorithm in the layers of a trainable neural network.<n>We show that convergence guarantees and generalizability of the unrolled networks are still open theoretical problems.<n>We numerically assess unrolled architectures trained under the proposed constraints in two different applications.
  arXiv  Detail & Related papers  (2023-12-25T18:51:23Z)
• Unlocking Deep Learning: A BP-Free Approach for Parallel Block-Wise Training of Neural Networks [9.718519843862937]
  We introduce a block-wise BP-free (BWBPF) neural network that leverages local error signals to optimize sub-neural networks separately. Our experimental results consistently show that this approach can identify transferable decoupled architectures for VGG and ResNet variations.
  arXiv  Detail & Related papers  (2023-12-20T08:02:33Z)
• Towards Practical Control of Singular Values of Convolutional Layers [65.25070864775793]
  Convolutional neural networks (CNNs) are easy to train, but their essential properties, such as generalization error and adversarial robustness, are hard to control. Recent research demonstrated that singular values of convolutional layers significantly affect such elusive properties. We offer a principled approach to alleviating constraints of the prior art at the expense of an insignificant reduction in layer expressivity.
  arXiv  Detail & Related papers  (2022-11-24T19:09:44Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• Stochastic Deep Networks with Linear Competing Units for Model-Agnostic Meta-Learning [4.97235247328373]
  This work addresses meta-learning (ML) by considering deep networks with local winner-takes-all (LWTA) activations. This type of network units results in sparse representations from each model layer, as the units are organized into blocks where only one unit generates a non-zero output. Our approach produces state-of-the-art predictive accuracy on few-shot image classification and regression experiments, as well as reduced predictive error on an active learning setting.
  arXiv  Detail & Related papers  (2022-08-02T16:19:54Z)
• Bimodal Distributed Binarized Neural Networks [3.0778860202909657]
  Binarization techniques, however, suffer from ineligible performance degradation compared to their full-precision counterparts. We propose a Bi-Modal Distributed binarization method (methodname) That imposes bi-modal distribution of the network weights by kurtosis regularization.
  arXiv  Detail & Related papers  (2022-04-05T06:07:05Z)
• Robustness Certificates for Implicit Neural Networks: A Mixed Monotone Contractive Approach [60.67748036747221]
  Implicit neural networks offer competitive performance and reduced memory consumption. They can remain brittle with respect to input adversarial perturbations. This paper proposes a theoretical and computational framework for robustness verification of implicit neural networks.
  arXiv  Detail & Related papers  (2021-12-10T03:08:55Z)
• SiMaN: Sign-to-Magnitude Network Binarization [165.5630656849309]
  We show that our weight binarization provides an analytical solution by encoding high-magnitude weights into +1s, and 0s otherwise. We prove that the learned weights of binarized networks roughly follow a Laplacian distribution that does not allow entropy. Our method, dubbed sign-to- neural network binarization (SiMaN), is evaluated on CIFAR-10 and ImageNet.
  arXiv  Detail & Related papers  (2021-02-16T07:03:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.