Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Joshi, Nirmit, Misiakiewicz, Theodor, Srebro, Nathan
Format:	Preprint
Published:	2024
Subjects:	Machine Learning Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks
by: Abbe, Emmanuel, et al.
Published: (2022)

Learning single-index models via harmonic decomposition
by: Joshi, Nirmit, et al.
Published: (2025)

Metalearning with Very Few Samples Per Task
by: Aliakbarpour, Maryam, et al.
Published: (2023)

Statistical Query Lower Bounds for Smoothed Agnostic Learning
by: Diakonikolas, Ilias, et al.
Published: (2026)

Statistical Query Lower Bounds for Learning Truncated Gaussians
by: Diakonikolas, Ilias, et al.
Published: (2024)

Limitations of Membership Queries in Testable Learning
by: Lange, Jane, et al.
Published: (2025)

Learning Partitions with Optimal Query and Round Complexities
by: Black, Hadley, et al.
Published: (2025)

SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
by: Diakonikolas, Ilias, et al.
Published: (2024)

Exact Learning of Weighted Graphs Using Composite Queries
by: Goodrich, Michael T., et al.
Published: (2025)

Smoothed Score Queries and the Complexity of Sampling
by: Liu, Jingbo
Published: (2026)

New Statistical and Computational Results for Learning Junta Distributions
by: Beretta, Lorenzo
Published: (2025)

Clustering with Non-adaptive Subset Queries
by: Black, Hadley, et al.
Published: (2024)

Agnostic Learning of General ReLU Activation Using Gradient Descent
by: Awasthi, Pranjal, et al.
Published: (2022)

Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
by: Kalavasis, Alkis, et al.
Published: (2026)

Query-Efficient Correlation Clustering with Noisy Oracle
by: Kuroki, Yuko, et al.
Published: (2024)

Value-Compressed Sparse Column (VCSC): Sparse Matrix Storage for Redundant Data
by: Ruiter, Skyler, et al.
Published: (2023)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
by: Croquevielle, Luis Alberto, et al.
Published: (2026)

Learning and Testing Convex Functions
by: Pinto Jr., Renato Ferreira, et al.
Published: (2025)

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
by: Rapoport, Emma, et al.
Published: (2025)

Collaborative Learning with Different Labeling Functions
by: Deng, Yuyang, et al.
Published: (2024)

Testably Learning Polynomial Threshold Functions
by: Slot, Lucas, et al.
Published: (2024)

On Exact Learning of $d$-Monotone Functions
by: Bshouty, Nader H.
Published: (2025)

Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
by: Rohatgi, Dhruv, et al.
Published: (2025)

Query-decision Regression between Shortest Path and Minimum Steiner Tree
by: Tong, Guangmo, et al.
Published: (2024)

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
by: Kamath, Gautam, et al.
Published: (2025)

Robust Sparse Regression with Non-Isotropic Designs
by: Liu, Chih-Hung, et al.
Published: (2024)

Computational and Statistical Hardness of Calibration Distance
by: Qiao, Mingda
Published: (2026)

Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms
by: White, Nathan, et al.
Published: (2026)

Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
by: Silwal, Sandeep, et al.
Published: (2025)

Statistical-Computational Trade-offs for Density Estimation
by: Aamand, Anders, et al.
Published: (2024)

Query Efficient Structured Matrix Learning
by: Amsel, Noah, et al.
Published: (2025)

A Simple Sparse Matrix Vector Multiplication Approach to Padded Convolution
by: Chaudhry, Zan
Published: (2024)

Efficient Algorithms for Verifying Kruskal Rank in Sparse Linear Regression and Related Applications
by: Zhou, Fengqin
Published: (2025)

Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise
by: Zeng, Shiwei, et al.
Published: (2023)

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
by: Chen, Hongjie, et al.
Published: (2025)

The Space Complexity of Approximating Logistic Loss
by: Dexter, Gregory, et al.
Published: (2024)

Learned Static Function Data Structures
by: Hermann, Stefan, et al.
Published: (2025)

Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
by: Fichtenberger, Hendrik, et al.
Published: (2022)

Quantum Local Differential Privacy and Quantum Statistical Query Model
by: Angrisani, Armando, et al.
Published: (2022)

Chasing Convex Functions with Long-term Constraints
by: Lechowicz, Adam, et al.
Published: (2024)