mlsanityData to 14 Oct 2026

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries

arXiv 2407.05622 ↗First posted 8 Jul 2024cs.LG cs.DScited by 15

Not on the map. Why?

Abstract (arXiv)

The goal of this paper is to investigate the complexity of gradient algorithms when learning sparse functions (juntas). We introduce a type of Statistical Queries (mathsfSQ), which we call Differentiable Learning Queries (mathsfDLQ), to model gradient queries on a specified loss with respect to an arbitrary model. We provide a tight characterization of the query complexity of mathsfDLQ for learning the support of a sparse function over generic product distributions. This complexity crucially depends on the loss function. For the squared loss, mathsfDLQ matches the complexity of Correlation Statistical Queries (mathsfCSQ)--potentially much worse than mathsfSQ. But for other simple loss functions, including the ℓ1 loss, mathsfDLQ always achieves the same complexity as mathsfSQ. We also provide evidence that mathsfDLQ can indeed capture learning with (stochastic) gradient descent by showing it correctly describes the complexity of learning with a two-layer neural network in the mean field regime and linear scaling.

Key facts. Cited by 15 papers in the map (data through 14 Oct 2026). Builds on 26 of its 48 references that are in the map. First posted on arXiv 8 Jul 2024.

Builds on

26 of 48 references.

References · 26

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 466
  3. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 426
  4. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  5. 2023SGD learning on neural networks: leap complexity and saddle-to-saddle dynamicscited by 143
  6. 2022The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networkscited by 142
  7. 2020Online stochastic gradient descent on non-convex losses from high-dimensional inferencecited by 119
  8. 2018Mean Field Analysis of Neural Networks: A Central Limit Theoremcited by 107
  9. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  10. 2019Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratiocited by 85
  11. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 69
  12. 2015Neural Network with Unbounded Activation Functions is Universal Approximatorcited by 63
14 more
  1. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 63
  2. 2021The staircase property: How hierarchical structure can guide deep learningcited by 62
  3. 2023Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Modelscited by 61
  4. 2023On Learning Gaussian Multi-index Models with Gradient Flowcited by 57
  5. 2024The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponentscited by 52
  6. 2021Quantifying the Benefit of Using Differentiable Learning over Tangent Kernelscited by 41
  7. 2023SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problemcited by 39
  8. 2018Optimality and Sub-optimality of PCA I: Spiked Random Matrix Modelscited by 33
  9. 2021On the Power of Differentiable Learning versus PAC and SQ Learningcited by 28
  10. 2020Statistical Queries and Statistical Algorithms: Foundations and Applicationscited by 22
  11. 2017On the Complexity of Learning Neural Networkscited by 18
  12. 2018Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Boundscited by 18
  13. 2022On the non-universality of deep learning: quantifying the cost of symmetrycited by 18
  14. 2021Minimum complexity interpolation in random features modelscited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 6; 2026: 6.

15 papers.

Sort:

By area:

  1. 2024Pretrained transformer efficiently learns low-dimensional target functions in-contextcited by 31
  2. 2024Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamicscited by 15
  3. 2025Survey on Algorithms for multi-index modelscited by 15
  4. 2025The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Modelscited by 9
  5. 2025Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributionscited by 8
  6. 2024Robust Feature Learning for Multi-Index Models in High Dimensionscited by 5
  7. 2025Test time training enhances in-context learning of nonlinear functionscited by 3
  8. 2026Positive Distribution Shift as a Framework for Understanding Tractable Learningcited by 3
  9. 2025From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGDcited by 2
  10. 2026The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learningcited by 2
  11. 2025Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learningcited by 1
  12. 2026The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficientlycited by 1
3 more
  1. 2026The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledgecited by 1
  2. 2026Learning with Shallow Neural Networks on Cluster-Structured Featurescited by 1
  3. 2026Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Modelcited by 0