7 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 predictor…
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…
Collaborative Learning with Different Labeling Functions
Yuyang Deng, Mingda Qiao
We study a variant of Collaborative PAC Learning, in which we aim to learn an accurate classifier for each of the data distributions, while minimizing the number of samples dra…
A Combinatorial Approach to Robust PCA
Weihao Kong, Mingda Qiao, Rajat Sen
We study the problem of recovering Gaussian data under adversarial corruptions when the noises are low-rank and the corruptions are on the coordinate level. Concretely, we assume t…