conftrace_

statistical query

50 papers

Explore in graph

Also known as

SQ

Co-occurring keywords

learning theory (519) lower bound (173) sample complexity (1169) differential privacy (1016) pac learning (283) agnostic learning (76) query complexity (183) gaussian distribution (127) massart noise (17) adaptive data analysis (10)

Papers

Active Classification with Few Queries under Misspecification NIPS 2024
Statistical Query Lower Bounds for Learning Truncated Gaussians COLT 2024
Computational-Statistical Gaps in Gaussian Single-Index Models (Extended Abstract) COLT 2024
Hardness of Learning Neural Networks under the Manifold Hypothesis NIPS 2024
Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds COLT 2024
SQ Lower Bounds for Learning Mixtures of Linear Classifiers NIPS 2023
SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians COLT 2023
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise COLT 2023
Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures COLT 2023
SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions NIPS 2023
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise NIPS 2023
List and Certificate Complexities in Replicable Learning NIPS 2023
On the Role of Entanglement and Statistics in Learning NIPS 2023
Adaptive Data Analysis in a Balanced Adversarial Model NIPS 2023
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals COLT 2022
Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise COLT 2022
SQ Lower Bounds for Learning Single Neurons with Massart Noise NIPS 2022
List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering NIPS 2022
On the power of adaptivity in statistical adversaries COLT 2022
Hardness of Learning a Single Neuron with Adversarial Label Noise AISTATS 2022
Efficient Algorithms for Learning from Coarse Labels COLT 2021
The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model COLT 2021
Robust Learning under Strong Noise via SQs AISTATS 2021
Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent COLT 2021
Differentially Private Query Release Through Adaptive Projection ICML 2021