Cover Image

Limitations of Membership Queries in Testable Learning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lange, Jane, Qiao, Mingda
Format:	Preprint
Published:	2025
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

Online Prediction with Limited Selectivity
by: Liu, Licheng, et al.
Published: (2025)

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

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

Testable Learning with Distribution Shift
by: Klivans, Adam R., et al.
Published: (2023)

On the Distance from Calibration in Sequential Prediction
by: Qiao, Mingda, et al.
Published: (2024)

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

Sample-Adaptivity Tradeoff in On-Demand Sampling
by: Haghtalab, Nika, et al.
Published: (2025)

Testable Learning of General Halfspaces under Massart Noise
by: Diakonikolas, Ilias, et al.
Published: (2026)

Efficient Testable Learning of General Halfspaces with Adversarial Label Noise
by: Diakonikolas, Ilias, et al.
Published: (2024)

Truthfulness of Calibration Measures
by: Haghtalab, Nika, et al.
Published: (2024)

Robust learning of halfspaces under log-concave marginals
by: Lange, Jane, et al.
Published: (2025)

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

On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries
by: Joshi, Nirmit, et al.
Published: (2024)

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

No Price Tags? No Problem: Query Strategies for Unpriced Information
by: Nadimpalli, Shivam, et al.
Published: (2025)

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

A Distributional-Lifting Theorem for PAC Learning
by: Blanc, Guy, et al.
Published: (2025)

Online Learning with Limited Information in the Sliding Window Model
by: Braverman, Vladimir, et al.
Published: (2026)

Misalignment, Learning, and Ranking: Harnessing Users Limited Attention
by: Agarwal, Arpit, et al.
Published: (2024)

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

Optimal $k$-Secretary with Logarithmic Memory
by: Qiao, Mingda, et al.
Published: (2025)

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

Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
by: Bshouty, Nader H., et al.
Published: (2026)

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

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

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

Online Algorithms with Limited Data Retention
by: Immorlica, Nicole, et al.
Published: (2024)

Language Generation in the Limit: Noise, Loss, and Feedback
by: Bai, Yannan, et al.
Published: (2025)

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

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

Samplability makes learning easier
by: Blanc, Guy, et al.
Published: (2025)

Multi-LLM Query Optimization
by: Dean, Arlen, et al.
Published: (2026)

Smoothed Analysis of Learning from Positive Samples
by: Lee, Jane H., et al.
Published: (2025)

Graph Inference with Effective Resistance Queries
by: Bennett, Huck, et al.
Published: (2025)

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

Learning on the Edge: Online Learning with Stochastic Feedback Graphs
by: Esposito, Emmanuel, et al.
Published: (2022)

Learning-Augmented Algorithms for $k$-median via Online Learning
by: Hebbar, Anish, et al.
Published: (2026)

Learned LSM-trees: Two Approaches Using Learned Bloom Filters
by: Fidalgo, Nicholas, et al.
Published: (2025)

Predicting quantum channels over general product distributions
by: Chen, Sitan, et al.
Published: (2024)

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