30 citations · 97 across the 13 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021
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…
cs.LG2021
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…
cs.LG2021★ 1 cited
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…