mlsanityData to 7 Oct 2026

From Local Pseudorandom Generators to Hardness of Learning

arXiv 2101.08303 ↗First posted 20 Jan 2021cs.LG stat.MLcited by 24

Not on the map. Why?

Abstract (arXiv)

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 ω(1) halfspaces, DNF formulas with ω(1) terms, and ReLU networks with ω(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. Moreover, our results imply the hardness of virtually all improper PAC-learning problems (both distribution-free and distribution-specific) that were previously shown hard under other assumptions.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). Builds on 24 of its 79 references that are in the map. First posted on arXiv 20 Jan 2021.

Builds on

24 of 79 references.

References · 24

  1. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  2. 2017Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputscited by 61
  3. 2020Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descentcited by 57
  4. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  5. 2017An Analytical Formula of Population Gradient for two-layered ReLU network and its Applications in Convergence and Critical Point Analysiscited by 52
  6. 2015Complexity Theoretic Limitations on Learning Halfspacescited by 50
  7. 2020Statistical-Query Lower Bounds via Functional Gradientscited by 50
  8. 2020Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networkscited by 49
  9. 2017Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minimacited by 40
  10. 2020Tight Hardness Results for Training Depth-2 ReLU Networkscited by 35
  11. 2019Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginalscited by 32
  12. 2018Learning Two Layer Rectified Neural Networks in Polynomial Timecited by 31
12 more
  1. 2016Distribution-Specific Hardness of Learning Neural Networkscited by 27
  2. 2014Complexity theoretic limitations on learning DNF'scited by 21
  3. 2017When is a Convolutional Filter Easy To Learn?cited by 21
  4. 2018Learning One Convolutional Layer with Overlapping Patchescited by 21
  5. 2018Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Boundscited by 18
  6. 2017On the Complexity of Learning Neural Networkscited by 17
  7. 2013From average case complexity to improper learning complexitycited by 16
  8. 2020A Deep Conditioning Treatment of Neural Networkscited by 15
  9. 2020Hardness of Learning Neural Networks with Natural Weightscited by 15
  10. 2013Provable Bounds for Learning Some Deep Representationscited by 14
  11. 2018Improved Learning of One-hidden-layer Convolutional Neural Networks with Overlapscited by 6
  12. 2019On the Learnability of Deep Random Networkscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 4; 2024: 5; 2025: 5; 2026: 2.

24 papers.

Sort:

By area:

  1. 2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
  2. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  3. 2024Provably learning a multi-head attention layercited by 21
  4. 2021On the Cryptographic Hardness of Learning Single Periodic Neuronscited by 20
  5. 2025A Theory of Learning with Autoregressive Chain of Thoughtcited by 20
  6. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  7. 2022Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problemscited by 16
  8. 2021Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activationscited by 15
  9. 2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimensioncited by 11
  10. 2023Computational Complexity of Learning Neural Networks: Smoothness and Degeneracycited by 10
  11. 2022Learning (Very) Simple Generative Models Is Hardcited by 9
  12. 2021Efficiently Learning Any One Hidden Layer ReLU Network From Queriescited by 6
12 more
  1. 2022Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANscited by 6
  2. 2024Improved Hardness Results for Learning Intersections of Halfspacescited by 6
  3. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
  4. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  5. 2023Most Neural Networks Are Almost Learnablecited by 2
  6. 2023Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopescited by 2
  7. 2025The Probably Approximately Correct Learning Model in Computational Learning Theorycited by 2
  8. 2023On the Computational Benefit of Multimodal Learningcited by 1
  9. 2025PAC Learning is just Bipartite Matching (Sort of)cited by 1
  10. 2025Statistical Quality and Reproducibility of Pseudorandom Number Generators in Machine Learning technologiescited by 1
  11. 2025On the Hardness of Learning Regular Expressionscited by 1
  12. 2026Enhanced and Efficient Reasoning in Large Learning Modelscited by 0