Research map / Optimization / Implicit bias and generalization
On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Differentiable Learning Queries (DLQ), a statistical-query model of gradient queries for a given loss, and gives tight adaptive and non-adaptive query complexities for learning sparse juntas via leap and cover exponents.
Problem
Characterizing the statistical query complexity of learning sparse functions (juntas) over general product distributions, and how it depends on the loss used for gradient-based learning, since CSQ only captures squared loss.
Approach
Defines DLQ_ℓ as SQ queries given by derivatives of a loss ℓ with respect to an arbitrary differentiable model, and shows the junta complexity is governed by a leap exponent (adaptive) or cover exponent (non-adaptive) over a loss-dependent system of detectable subsets; losses like ℓ1, hinge, and exponential match general SQ complexity, while squared loss matches CSQ.
Key results
- For the squared loss, DLQ complexity matches CSQ; for l1, hinge, and exponential losses, DLQ complexity matches SQ for any junta problem.
- Proposition shows a separation where Leap_SQ = Cover_SQ = 1 while Leap_CSQ = Cover_CSQ = P.
- Two-layer network with SGD: leap-1 functions are learned in Theta(d) steps (Theta(d^2) queries), while leap>1 functions remain stuck in a saddle subspace in the mean-field limit.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ℓ1 loss instead of squared loss | DLQ for junta y1, non-adaptive support recovery · Junta y1 | query complexity: Θ (d^4) -> Θ (d) | Helped |
| Use ℓ1 loss instead of squared loss | DLQ for junta y2, adaptive and non-adaptive support recovery · Junta y2 | query complexity: Θ (d^3) -> Θ(d) | Helped |
| Use ℓ1, hinge, or bounded-label exponential loss | DLQ for junta learning · All problems μ under the stated loss conditions | query complexity relative to SQ | Helped |
| Use squared loss rather than unrestricted SQ queries | DLQ for real-valued outputs · Junta learning | query complexity relative to CSQ | No clear effect |
| Use adaptive rather than non-adaptive queries | CSQ for junta y1 · Junta y1 | query complexity: Θ (d^4) -> Θ (d) | Helped |
| Train with layer-wise SGD when DLQ-leap is 1 | Two-layer neural network · Hypercube juntas with DLQ-leap 1 | excess test error: o(1) | Helped |
| Use mean-field gradient dynamics on a junta with DLQ-leap greater than 1 | Two-layer neural network · Hypercube juntas with DLQ-leap greater than 1 | coordinate alignment | Hurt |
Surprising findings
- For the squared loss, DLQ is no more powerful than CSQ, so gradient descent on squared loss can be far weaker than general SQ for some junta problems.
- Mean-field SGD with leap>1 cannot align with some relevant coordinates at any time.
Limitations
- null
Experimental setup
Metrics: query complexity exponent test mean squared error vs SGD iterations
Baselines: SQ CSQ
Builds on: Statistical Query learning leap complexity for CSQ on hypercube (Abbe et al.) saddle-to-saddle dynamics
Closest papers by meaning
- Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.89)
- The Power of Random Features and the Limits of Distribution-Free Gradient Descent (ICML 2025 · similarity 0.88)
- Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · similarity 0.87)
- Balancing Gradient and Hessian Queries in Non-Convex Optimization (NeurIPS 2025 · similarity 0.87)
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit (NeurIPS 2024 · similarity 0.87)
- Gradient Compressed Sensing: A Query-Efficient Gradient Estimator for High-Dimensional Zeroth-Order Optimization (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.