Showing 2025Show all
3 papers · 1 filter
cs.LG2025
Limitations of Membership Queries in Testable Learning
Jane Lange, Mingda Qiao
Membership queries (MQ) often yield speedups for learning tasks, particularly in the distribution-specific setting. We show that in the \emph{testable learning} model of Rubinfeld…
cs.DS2025
No Price Tags? No Problem: Query Strategies for Unpriced Information
Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld
The classic *priced query model*, introduced by Charikar et al. (STOC 2000), captures the task of computing a known function on an unknown input when each input variable can only b…
cs.LG2025
Online Prediction with Limited Selectivity
Licheng Liu, Mingda Qiao
Selective prediction [Dru13, QV19] models the scenario where a forecaster freely decides on the prediction window that their forecast spans. Many data statistics can be predicted t…