mlsanityData to 7 Oct 2026

Statistical Queries and Statistical Algorithms: Foundations and Applications

arXiv 2004.00557 ↗First posted 1 Apr 2020cs.LG cs.CC stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

We give a survey of the foundations of statistical queries and their many applications to other areas. We introduce the model, give the main definitions, and we explore the fundamental theory statistical queries and how how it connects to various notions of learnability. We also give a detailed summary of some of the applications of statistical queries to other areas, including to optimization, to evolvability, and to differential privacy.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Apr 2020.

Builds on

No reference list yet.

Built on by

Cited by year

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

21 papers.

Sort:

  1. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 142
  2. 2024Neural network learns low-dimensional polynomials with SGD near the information-theoretic limitcited by 45
  3. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  4. 2023A survey on the complexity of learning quantum statescited by 31
  5. 2022Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networkscited by 27
  6. 2024Hardness of Learning Neural Networks under the Manifold Hypothesiscited by 18
  7. 2022On the non-universality of deep learning: quantifying the cost of symmetrycited by 17
  8. 2024On the hardness of learning under symmetriescited by 13
  9. 2024Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinationscited by 13
  10. 2024On the Complexity of Learning Sparse Functions with Statistical and Gradient Queriescited by 13
  11. 2021On the power of adaptivity in statistical adversariescited by 12
  12. 2024Smoothed Analysis for Learning Concepts with Low Intrinsic Dimensioncited by 11
9 more
  1. 2021On the Hardness of PAC-learning Stabilizer States with Noisecited by 8
  2. 2025Hardness of Learning Fixed Parities with Neural Networkscited by 7
  3. 2022Learning ReLU networks to high uniform accuracy is intractablecited by 5
  4. 2023Boolformer: Symbolic Regression of Logic Functions with Transformerscited by 5
  5. 2025Specialization after Generalization: Towards Understanding Test-Time Training in Foundation Modelscited by 5
  6. 2021Approximate Maximum Halfspace Discrepancycited by 3
  7. 2025LLM Priors for ERM over Programscited by 3
  8. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  9. 2023A Unified Model and Dimension for Interactive Estimationcited by 0