Parity functions, where the label is the XOR of a hidden subset of input bits, are the standard example of a problem that neural networks can represent but gradient descent cannot find. Each bit on its own carries no information about the label, so the gradient is flat almost everywhere. Recent work reports that this barrier falls when inputs are sparse, meaning most bits are zero. In that regime a multiplicative "product network" trained by plain gradient descent learns parities in 100,000 dimensions. Separately, cryptographers and complexity theorists believe a closely related sparse problem stays hard for every efficient algorithm once labels are noisy. That problem is the noisy planted K-XOR problem: random equations, each touching exactly K secret bits, with a fraction of the right-hand sides flipped. These two beliefs cannot both be taken at face value. This note proposes to locate gradient-trained networks precisely between them.
The core observation is simple. When each input bit is on with probability about 1/N, a constant fraction of examples have exactly one active bit, and their label simply reveals one secret bit. The reported gradient successes therefore live at the degenerate end of a density dial. The other end of that dial, with every example touching exactly K bits plus label noise, is the planted K-XOR ensemble. Average-case complexity places its efficient-algorithm threshold at roughly $n^{K/2}$ samples. We propose to turn this dial and measure, as a scaling exponent, how many samples gradient-trained networks need at each K. This places gradient descent on a ladder whose rungs are known. Information-theoretically about $n\log n$ samples suffice. Spectral methods, which conjecturally mark the limit of all efficient algorithms, need about $n^{K/2}$. Correlation-style learners naively need about $n^{K-1}$.
Core Claim
On noisy sparse parity with exactly K active bits per example, gradient-trained networks will not inherit the tractability seen at density 1/N. The central question is whether their sample threshold scales as $n^{K/2}$ or as $n^{K-1}$. Matching $n^{K/2}$ would mean gradient descent behaves like the spectral methods believed optimal among efficient algorithms. Scaling as $n^{K-1}$ would mean an intrinsic gap specific to gradient methods, sitting on top of the conjectured computational gap.
Concretely, let $s\in\{0,1\}^n$ be a hidden secret. Each example is a uniformly random set $S$ of exactly K coordinates, encoded as a 0/1 vector $x$. Its label is $y=\bigoplus_{i\in S}s_i \oplus e$, where the noise bit $e$ is 1 with probability $\eta$. With $m$ the number of training examples, define the threshold exponent $\alpha^*(\text{learner},K,\eta)$ as the smallest $\alpha$ such that $m=n^{\alpha}$ examples give held-out accuracy at least $1/2+\delta$ with probability above one half, in the limit of growing $n$. The prediction is that $\alpha^*\ge K/2$ for every gradient learner, since anything lower would contradict the refutation conjecture. The open empirical question is where in $[K/2,\,K-1]$ each gradient learner lands.
The case K=3 has special weight. More data speeds up training time in learning halfspaces over sparse vectors uses Feige's random 3-SAT hypothesis to prove that 3-sparse halfspaces need exponential time at $O(n/\epsilon^2)$ samples but polynomial time at $\tilde\Omega(n^2/\epsilon^2)$. It also conjectures that the true transition is at $n^{1.5}$, which is exactly $n^{K/2}$ for K=3. Our K=3 experiments ask directly whether gradient descent exhibits that data-versus-computation transition, and at which exponent.
How the Three Directions Fit
The gradient-sparsity literature motivates the question. Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent designs a product node $\prod_i (w_i x_i + 1 - w_i)$. It proves that this node's loss becomes convex when inputs are Bernoulli with $p_e\approx 1/N$, and it explicitly lists learning parity with noise (LPN) as open. Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent shows that sign SGD with a dead-zone threshold and a $z^k$ activation reaches $\tilde O(d^{k-1})$ samples on the uniform hypercube. That exponent is the source of our $n^{K-1}$ "naive" rung. Neither paper studies fixed-weight sparse inputs with label noise, which is the regime where hardness conjectures actually apply.
The average-case direction supplies the hardness floor and the method of argument. From average case complexity to improper learning complexity, Complexity Theoretic Limitations on Learning Halfspaces, and Hardness of Learning a Single Neuron with Adversarial Label Noise all argue the same way. A learner that predicts well on planted data, and therefore fails on purely random data, becomes a distinguisher that refutes random CSPs. We reuse this logic as an experimental protocol rather than a proof. Every learner is run on planted and fully random label sets, and we record when its held-out accuracy separates them. These papers embed CSPs in adversarial input distributions. Our inputs are the natural random-clause distribution itself, so no embedding is needed.
The cryptographic direction supplies the empirical puzzle. Practically Solving LPN in High Noise Regimes Faster Using Neural Networks finds that a two-layer MLP trained with Adam beats Gaussian elimination and BKW (Blum–Kalai–Wasserman, a classical LPN solver) at high noise. It does so only for $n\le125$ with dense rows, and it offers no scaling theory. Sparse rows are the setting where we can push $n$ into the thousands. They therefore let us tell genuine polynomial scaling apart from small-$n$ artifacts, which is the question that paper leaves open.
Two cited results constrain the design. Positive Distribution Shift as a Framework for Understanding Tractable Learning shows that choosing the training distribution is equivalent to non-adaptive membership queries. With such queries, parity is trivial: one can query unit vectors. We therefore forbid any distribution choice by the learner. On the hardness of learning under symmetries shows that building symmetries into the architecture does not remove flat landscapes. We therefore do not expect invariant architectures to change the exponent, and include one only as a check.
Research Program
The first component is analytic and modest. For the product node and for a two-layer ReLU network at standard initialization, we compute the expected gradient and its variance on fixed-weight-K inputs. We will show that the population gradient for any single coordinate vanishes for $K\ge2$. We will also identify the lowest-order term that carries signal, which we expect to be a $(K-1)$-wise co-occurrence statistic. A counting heuristic then predicts the scaling: estimating a degree-$(K-1)$ statistic over $\binom{n}{K-1}$ index tuples, from data in which each tuple appears about $mK/n^{K-1}$ times, gives $\alpha\approx K-1$ for one-shot gradient signal. Multi-step dynamics could in principle aggregate weak signals the way spectral methods do and approach $K/2$. This heuristic is a hypothesis to test, not a theorem.
The second component is a measurement apparatus. We build a generator that interpolates between the Bernoulli $p_e=1/N$ ensemble and the fixed-weight-K ensemble. A parameter $\lambda\in[0,1]$ is the fraction of examples resampled to have weight exactly K, with all other examples drawn from Bernoulli($1/N$). This lets us watch the product network's success decay as the degenerate weight-1 examples are removed. For each learner, K in {3,4}, $\eta$ in {0, 0.05, 0.1, 0.25}, and $n$ on a geometric grid, we binary-search the sample size reaching the accuracy criterion. We then fit $\alpha^*$ as the slope of $\log m^*$ against $\log n$, reporting bootstrap intervals over 10 secrets per cell. For K=3 we target $n$ from 256 to 8192, which keeps $n^{2}$ examples within reach because sparse inputs store K indices per example. For K=4 we target $n$ up to about 1024 and accept that the $n^{3}$ rung may only be bracketed.
Baselines
The naive reference point is predicting the majority label. This yields 1/2 accuracy on balanced parity, and it is what Positive Distribution Shift as a Framework for Understanding Tractable Learning reports for a two-layer ReLU network on uniform degree-25 parity ("0.5 (random guessing) for the entire duration of the run"). Alongside it we run the label-shuffled null: the same learners trained on random labels. This calibrates how much held-out accuracy finite-sample memorization alone produces.
The strongest existing algorithm for the planted K-XOR question is a spectral method. For even K this is the standard matrix that pairs coordinate halves of each clause. For odd K we use its usual pair-of-clauses variant. These are the algorithms that conjecturally achieve the $n^{K/2}$ efficient threshold. No reported result was found on Lacuna for spectral recovery on planted K-XOR at any concrete $n$, so we will implement it ourselves and fit its exponent on the same grid. This also validates the apparatus: it should land near $K/2$. In the noiseless case we add Gaussian elimination, and in the noisy dense comparison we add BKW. For the dense LPN regime, the strongest reported neural number is from Practically Solving LPN in High Noise Regimes Faster Using Neural Networks: a two-layer MLP solved $n=26$, $\tau=0.498$ in 66 minutes on 8 GPUs, against 3.12 days on 64 CPU cores for Guess-then-Gaussian elimination. We reproduce that cell before moving to sparse inputs, so our MLP is demonstrably as strong as theirs.
The gradient learners under test are three. The first is the product node of Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent, with its reported learning-rate scaling $\alpha\propto N$. It reports 100% validation accuracy at $N=16$ after seeing under 2% of the truth table, which we reproduce at $\lambda=0$. The second is the Adam-trained MLP from the LPN paper. The third is the sign SGD of Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent, which reports 96.89–99.69% test accuracy for $k\in\{2,3,4\}$ on the uniform cube and which we reproduce first.
All methods receive identical sample sets, an equal hyperparameter grid of 32 configurations, and a fixed per-cell wall-clock budget on the same hardware. The key ablation is the $\lambda$ sweep. If the product network's advantage disappears as $\lambda\to1$, its reported success is attributable to weight-1 examples rather than to the architecture. "Beating" a baseline means a smaller fitted $\alpha^*$ with non-overlapping bootstrap intervals. A gradient learner matching the spectral exponent within error would itself be the headline result.
Why not just…?
Why not just run the product network on noisy Bernoulli($1/N$) data, which directly answers its own open LPN question? At that density the noisy problem is nearly a lookup task with majority voting: each weight-1 example is a noisy copy of one secret bit, so about $n\log n$ samples suffice for any reasonable method. A success there would say nothing about hardness. The $\lambda$ sweep includes this point as its left endpoint precisely to show it is easy for every baseline, including per-coordinate vote counting.
Why not just trust the spectral and refutation literature and skip gradient experiments? Those results bound what any efficient algorithm can do. They say nothing about whether gradient descent reaches that bound, and the file notes that cryptographic hardness "do[es] not typically explain the fine-grained dynamics of why specific local gradient algorithms fail." The gap between $n^{K/2}$ and $n^{K-1}$ is a real, unanswered question about gradient descent specifically.
Why not just scale the dense-LPN MLP experiments of Practically Solving LPN in High Noise Regimes Faster Using Neural Networks to larger $n$? Dense LPN is believed exponentially hard, so larger $n$ only yields runtimes growing too fast to fit any polynomial exponent. Sparse inputs give a regime with a polynomial efficient threshold, where an exponent is measurable. This alternative is a genuine threat in one respect: grokking-style late generalization could make our binary search underestimate gradient learners. We guard against this by training each cell to 20 times the step count at which training accuracy saturates before declaring failure.
Why not just let the learner choose a helpful training distribution, as positive distribution shift does? As Positive Distribution Shift as a Framework for Understanding Tractable Learning proves, that power equals non-adaptive membership queries, which make parity trivial. It answers a different question from learning out of naturally arriving random examples.
Decisive Checks
The first check is validation. The spectral baseline's fitted exponent must fall within 0.15 of $K/2$, and the majority predictor and shuffled-label runs must sit at chance. Otherwise the apparatus is not measuring computational thresholds.
The second check is the K=3 headline. If gradient learners show $\alpha^*\approx1.5$, gradient descent matches the conjectured efficient limit and empirically realizes the $n^{1.5}$ transition conjectured in More data speeds up training time in learning halfspaces over sparse vectors. If they show $\alpha^*\approx2$, there is a gradient-specific gap. The K=4 runs, where the two rungs are $n^{2}$ and $n^{3}$, distinguish these hypotheses with a wider margin.
The third check is the $\lambda$ sweep, which tests whether the product network's tractability tracks the fraction of weight-1 examples. A finding of $\alpha^*<K/2$ that is stable across $n$ for any gradient learner would be evidence against the random K-XOR refutation conjecture. We would treat it with suspicion and recheck it at the largest feasible $n$ before reporting.
References
- More data speeds up training time in learning halfspaces over sparse vectors
- Learning High-Dimensional Parity Functions with Product Networks using Gradient Descent
- Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent
- From average case complexity to improper learning complexity
- Complexity theoretic limitations on learning halfspaces
- Hardness of Learning a Single Neuron with Adversarial Label Noise
- Practically Solving LPN in High Noise Regimes Faster Using Neural Networks
- Positive Distribution Shift as a Framework for Understanding Tractable Learning
- On the hardness of learning under symmetries