30 citations · 97 across the 13 of their papers we have counts for
15 papers
Online Pen Testing
Mingda Qiao, Gregory Valiant
We study a "pen testing" problem, in which we are given pens with unknown amounts of ink , and we want to choose a pen with the maximum amount of remaini…
A Fourier Approach to Mixture Learning
Mingda Qiao, Guru Guruganesh, Ankit Singh Rawat +2
We revisit the problem of learning mixtures of spherical Gaussians. Given samples from mixture , the goal is to estimate the means $…
Open Problem: Properly learning decision trees in polynomial time?
Guy Blanc, Jane Lange, Mingda Qiao +1
The authors recently gave an time membership query algorithm for properly learning decision trees under the uniform distribution (Blanc et al., 2021). The previ…
Properly learning decision trees in almost polynomial time
Guy Blanc, Jane Lange, Mingda Qiao +1
We give an -time membership query algorithm for properly and agnostically learning decision trees under the uniform distribution over . Even in the…
Decision tree heuristics can fail, even in the smoothed setting
Guy Blanc, Jane Lange, Mingda Qiao +1
Greedy decision tree learning heuristics are mainstays of machine learning practice, but theoretical justification for their empirical success remains elusive. In fact, it has long…
Exponential Weights Algorithms for Selective Learning
Mingda Qiao, Gregory Valiant
We study the selective learning problem introduced by Qiao and Valiant (2019), in which the learner observes labeled data points one at a time. At a time of its choosing, the l…