Browse Teach Curate

Hardness of Learning Fixed Parity Functions with Gradient-Trained Neural Networks

A proof that training a one-hidden-layer ReLU network with perturbed gradient descent on any fixed parity function of at least a minimal size provably fails to learn it, closing the gap left by worst-case statistical-query bounds, via a new bound on the decay of the Fourier coefficients of linear threshold (weighted majority) functions.

Data Text

2501.00817

A learning-theory paper explaining why fixed parity functions are hard to learn with neural networks in practice. Parity functions (products of a subset of +/-1 coordinates) are efficiently learnable…