5 papers
Testing Unate Distributions
Daeho Lee, Shivam Nadimpalli, Mingda Qiao +1
We initiate the study of *unate distributions* over -- a natural analogue of unate Boolean functions -- by considering two basic testing problems that parallel well-st…
Computational and Statistical Hardness of Calibration Distance
Mingda Qiao
The distance from calibration, introduced by BÅasiok, Gopalan, Hu, and Nakkiran (STOC 2023), has recently emerged as a central measure of miscalibration for probabilistic predicto…
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…
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…
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…