Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent

• URL: http://arxiv.org/abs/2605.28612v1
• Date: Wed, 27 May 2026 15:26:16 GMT
• Title: Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent
• Abstract summary: High-dimensional parity functions are critical for machine learning, cryptography, and error correction.<n>Standard neural network architectures typically require exponential sample complexity.<n>We show that compact product-based neural architectures combined with data sparsity enable efficient parity learning.<n>This work opens new possibilities for neural arithmetic, structured reasoning, binary neural networks, and machine learning applied to automated protocol discovery.
• Score: 1.6802038598427533
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: 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.

Related papers

• Neural Approximation and Its Applications [73.11802084858294]
  We introduce the neural basis function by leveraging an untrained neural network as the basis function.<n>We suggest the neural approximation (NeuApprox) paradigm for multivariate function approximation.<n>Experiments on diverse multi-dimensional images, light field data, videos, traffic data, and point cloud data demonstrate the promising performance of NeuApprox.
  arXiv  Detail & Related papers  (2026-03-04T06:05:43Z)
• Beyond Softmax: A Natural Parameterization for Categorical Random Variables [61.709831225296305]
  We introduce the $textitcatnat$ function, a function composed of a sequence of hierarchical binary splits.<n>A rich set of experiments show that the proposed function improves the learning efficiency and yields models characterized by consistently higher test performance.
  arXiv  Detail & Related papers  (2025-09-29T12:55:50Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• Global Convergence and Rich Feature Learning in $L$-Layer Infinite-Width Neural Networks under $μ$P Parametrization [66.03821840425539]
  In this paper, we investigate the training dynamics of $L$-layer neural networks using the tensor gradient program (SGD) framework.<n>We show that SGD enables these networks to learn linearly independent features that substantially deviate from their initial values.<n>This rich feature space captures relevant data information and ensures that any convergent point of the training process is a global minimum.
  arXiv  Detail & Related papers  (2025-03-12T17:33:13Z)
• Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function [24.457000214575245]
  We introduce a new technique to characterize the discontinuities and oscillations of the utility function on any fixed problem instance.<n>This can be used to show that the learning theoretic complexity of the corresponding family of utility functions is bounded.
  arXiv  Detail & Related papers  (2025-01-23T15:10:51Z)
• Fourier Circuits in Neural Networks and Transformers: A Case Study of Modular Arithmetic with Multiple Inputs [35.212818841550835]
  One-hidden layer neural networks and one-layer Transformers are studied.<n>One-hidden layer neural networks attain a maximum $ L_2,k+1 $-margin on a dataset.<n>We observe similar computational mechanisms in attention of one-layer Transformers.
  arXiv  Detail & Related papers  (2024-02-12T05:52:06Z)
• Optimal Approximation with Sparse Neural Networks and Applications [0.0]
  We use deep sparsely connected neural networks to measure the complexity of a function class in $L(mathbb Rd)$. We also introduce representation system - a countable collection of functions to guide neural networks. We then analyse the complexity of a class called $beta$ cartoon-like functions using rate-distortion theory and wedgelets construction.
  arXiv  Detail & Related papers  (2021-08-14T05:14:13Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• PAC-learning gains of Turing machines over circuits and neural networks [1.4502611532302039]
  We study the potential gains in sample efficiency that can bring in the principle of minimum description length. We use Turing machines to represent universal models and circuits. We highlight close relationships between classical open problems in Circuit Complexity and the tightness of these.
  arXiv  Detail & Related papers  (2021-03-23T17:03:10Z)
• Neural Network Approximations of Compositional Functions With Applications to Dynamical Systems [3.660098145214465]
  We develop an approximation theory for compositional functions and their neural network approximations. We identify a set of key features of compositional functions and the relationship between the features and the complexity of neural networks. In addition to function approximations, we prove several formulae of error upper bounds for neural networks.
  arXiv  Detail & Related papers  (2020-12-03T04:40:25Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)

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.