Hardness of Learning Fixed Parities with Neural Networks

Itamar Shoshani, Ohad Shamir

Learning parity functions is a canonical problem in learning theory, which although computationally tractable, is not amenable to standard learning algorithms such as gradient-base…