Research map / Learning theory and algorithms / Sample complexity
Statistical-Query Lower Bounds via Functional Gradients
Surbhi Goel, Aravind Gollakota, Adam Klivans
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce agnostic learning of a single activation to learning depth-two networks using functional gradient descent with a surrogate loss | ReLU regression under Gaussian marginals · Gaussian marginals, ReLU regression | SQ query lower bound: 2^{n^c} \epsilon | Hurt |
| Apply the same reduction to sigmoid units | Sigmoid learning · Gaussian marginals, sigmoid learning | SQ query lower bound: 2^{n^c} \epsilon | Hurt |
| Apply the same reduction to halfspaces | Halfspace learning · Gaussian marginals, halfspace learning | SQ query lower bound: 2^{n^c} \epsilon^3 | Hurt |
| Use the nonstandard surrogate loss and Frank–Wolfe functional gradient descent | Learning monotone Lipschitz functions of combinations of an agnostically learnable class · Probabilistic concept model | learning guarantee | Improved |
Closest papers by meaning
- Robust Regression of General ReLUs with Queries (NeurIPS 2025 · similarity 0.89)
- On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.89)
- Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model (ICLR 2025 · similarity 0.89)
- Algorithms and SQ Lower Bounds for Robustly Learning Real-valued Multi-Index Models (NeurIPS 2025 · similarity 0.86)
- Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.86)
- Revisiting Agnostic Boosting (NeurIPS 2025 · similarity 0.86)
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.
