8 citations · 13 across the 6 of their papers we have counts for
11 papers
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…
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…
Estimating decision tree learnability with polylogarithmic sample complexity
Guy Blanc, Neha Gupta, Jane Lange +1
We show that top-down decision tree learning heuristics are amenable to highly efficient learnability estimation: for monotone target functions, the error of the decision tree hypo…
Query strategies for priced information, revisited
Guy Blanc, Jane Lange, Li-Yang Tan
We consider the problem of designing query strategies for priced information, introduced by Charikar et al. In this problem the algorithm designer is given a function $f : \{0,1\}^…