# On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries arXiv: https://arxiv.org/abs/2407.05622 · HTML: https://mlsanity.com/paper/2407.05622/ ## 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 (most cited first, 26 of 26) - [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014) - [A Mean Field View of the Landscape of Two-Layers Neural Networks](https://mlsanity.com/paper/1804.06561/) (2018) - [On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport](https://mlsanity.com/paper/1805.09545/) (2018) - [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022) - [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023) - [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022) - [Online stochastic gradient descent on non-convex losses from high-dimensional inference](https://mlsanity.com/paper/2003.10409/) (2020) - [Mean Field Analysis of Neural Networks: A Central Limit Theorem](https://mlsanity.com/paper/1808.09372/) (2018) - [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022) - [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019) - [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021) - [Neural Network with Unbounded Activation Functions is Universal Approximator](https://mlsanity.com/paper/1505.03654/) (2015) - [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022) - [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021) - [Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models](https://mlsanity.com/paper/2305.10633/) (2023) - [On Learning Gaussian Multi-index Models with Gradient Flow](https://mlsanity.com/paper/2310.19793/) (2023) - [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024) - [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021) - [SGD Finds then Tunes Features in Two-Layer Neural Networks with near-Optimal Sample Complexity: A Case Study in the XOR problem](https://mlsanity.com/paper/2309.15111/) (2023) - [Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models](https://mlsanity.com/paper/1807.00891/) (2018) - [On the Power of Differentiable Learning versus PAC and SQ Learning](https://mlsanity.com/paper/2108.04190/) (2021) - [Statistical Queries and Statistical Algorithms: Foundations and Applications](https://mlsanity.com/paper/2004.00557/) (2020) - [On the Complexity of Learning Neural Networks](https://mlsanity.com/paper/1707.04615/) (2017) - [Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds](https://mlsanity.com/paper/1805.02677/) (2018) - [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022) - [Minimum complexity interpolation in random features models](https://mlsanity.com/paper/2103.15996/) (2021) ## Built on by (most cited first, 15 of 15) - [Pretrained transformer efficiently learns low-dimensional target functions in-context](https://mlsanity.com/paper/2411.02544/) (2024) - [Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2408.07254/) (2024) - [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025) - [The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models](https://mlsanity.com/paper/2506.05500/) (2025) - [Low-dimensional Functions are Efficiently Learnable under Randomly Biased Distributions](https://mlsanity.com/paper/2502.06443/) (2025) - [Robust Feature Learning for Multi-Index Models in High Dimensions](https://mlsanity.com/paper/2410.16449/) (2024) - [Test time training enhances in-context learning of nonlinear functions](https://mlsanity.com/paper/2509.25741/) (2025) - [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026) - [From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD](https://mlsanity.com/paper/2510.21020/) (2025) - [The Multiscale Single-Index Model: A Stylized Model for Hierarchical Feature Learning](https://mlsanity.com/paper/2607.03347/) (2026) - [Mamba Can Learn Low-Dimensional Targets In-Context via Test-Time Feature Learning](https://mlsanity.com/paper/2510.12026/) (2025) - [The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently](https://mlsanity.com/paper/2605.10237/) (2026) - [The Mechanism of Weak-to-Strong Generalization: Feature Elicitation from Latent Knowledge](https://mlsanity.com/paper/2605.12908/) (2026) - [Learning with Shallow Neural Networks on Cluster-Structured Features](https://mlsanity.com/paper/2605.14927/) (2026) - [Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model](https://mlsanity.com/paper/2606.15219/) (2026) ## 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.