Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates learning high-dimensional parity functions using product networks, a compact neural architecture. It demonstrates that by combining product networks with stochastic data sparsity (Bernoulli inputs with $p_e \leq 1/N$) and careful hyperparameter tuning, efficient parity learning becomes possible, even for input dimensions up to $N = 100,000$. Theoretical guarantees of convergence are provided and validated empirically, showing polynomial complexity scaling.
Product networks, combined with stochastic data sparsity, can efficiently learn high-dimensional parity functions that are typically intractable for standard neural networks.
Parity functions are fundamental Boolean operations with critical applications across machine learning, cryptography, and error correction. Yet, learning high-dimensional parity functions poses significant challenges: in a general setting, standard neural network architectures typically require exponential sample complexity, making gradient-based optimization intractable for large number of inputs $N$. We demonstrate that compact product-based neural architectures combined with stochastic data sparsity (Bernoulli inputs with $p_e \leq 1/N$) and appropriate hyperparameter choice enable efficient parity learning, with theoretical guarantees of convergence. Experiments validate our theory across dimensions up to $N = 100{,}000$, with empirical evidence showing optimal hyperparameter choices for $p_e$ and learning rate $α$, as well as polynomial complexity scaling laws. This work establishes fundamental connections between architectural inductive bias and data sparsity, opening new possibilities for neural arithmetic, structured reasoning, binary neural networks, and machine learning applied to automated protocol discovery.