From Local Pseudorandom Generators to Hardness of Learning

Understand

We prove hardness-of-learning results under a well-studied assumption on the existence of local pseudorandom generators.

• As we show, this assumption allows us to surpass the current state of the art, and prove hardness of various basic problems, with no hardness results to date.
• Our results include: hardness of learning shallow ReLU neural networks under the Gaussian distribution and other distributions; hardness of learning intersections of $\omega(1)$ halfspaces, DNF formulas with $\omega(1)$ terms, and ReLU networks with $\omega(1)$ hidden neurons; hardness of weakly learning deterministic finite automata under the uniform distribution; hardness of weakly learning depth-$3$ Boolean circuits under the uniform distribution, as well as distribution-specific hardness results for learning DNF formulas and intersections of halfspaces.
• We also establish lower bounds on the complexity of learning intersections of a constant number of halfspaces, and ReLU networks with a constant number of hidden neurons.