8 citations · 18 across the 18 of their papers we have counts for
5 papers · 1 filter
Provably efficient, succinct, and precise explanations
Guy Blanc, Jane Lange, Li-Yang Tan
We consider the problem of explaining the predictions of an arbitrary blackbox model : given query access to and an instance , output a small set of 's features that i…
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…
Multiway Online Correlated Selection
Guy Blanc, Moses Charikar
We give a -competitive algorithm for edge-weighted online bipartite matching. Prior to our work, the best competitive ratio was due to Fahrbach, Huang, Tao, and Za…
Learning stochastic decision trees
Guy Blanc, Jane Lange, Li-Yang Tan
We give a quasipolynomial-time algorithm for learning stochastic decision trees that is optimally resilient to adversarial noise. Given an -corrupted set of uniform random sampl…