research
∙
08/28/2023
Local Lipschitz Filters for Bounded-Range Functions
We study local filters for the Lipschitz property of real-valued functio...
share
research
∙
04/05/2023
Agnostic proper learning of monotone functions: beyond the black-box correction barrier
We give the first agnostic, efficient, proper learning algorithm for mon...
research
∙
03/27/2023
Lifting uniform learners via distributional decomposition
We show how any PAC learning algorithm that works under the uniform dist...
research
∙
11/04/2022
Certification with an NP Oracle
In the certification problem, the algorithm is given a function f with c...
research
∙
07/14/2022
A Query-Optimal Algorithm for Finding Counterfactuals
We design an algorithm for finding counterfactuals with strong theoretic...
research
∙
06/29/2022
Open Problem: Properly learning decision trees in polynomial time?
The authors recently gave an n^O(loglog n) time membership query algorit...
research
∙
06/17/2022
Popular decision tree algorithms are provably noise tolerant
Using the framework of boosting, we prove that all impurity-based decisi...
research
∙
04/25/2022
Properly learning monotone functions via local reconstruction
We give a 2^Õ(√(n)/ε)-time algorithm for properly learning monotone Bool...
research
∙
01/19/2022
The Query Complexity of Certification
We study the problem of certification: given queries to a function f : {...
research
∙
11/19/2021
On the power of adaptivity in statistical adversaries
We study a fundamental question concerning adversarial noise models in s...
research
∙
11/01/2021
Provably efficient, succinct, and precise explanations
We consider the problem of explaining the predictions of an arbitrary bl...
research
∙
09/01/2021
Properly learning decision trees in almost polynomial time
We give an n^O(loglog n)-time membership query algorithm for properly an...
research
∙
07/02/2021
Decision tree heuristics can fail, even in the smoothed setting
Greedy decision tree learning heuristics are mainstays of machine learni...
research
∙
05/08/2021
Learning stochastic decision trees
We give a quasipolynomial-time algorithm for learning stochastic decisio...
research
∙
12/16/2020
Testing and reconstruction via decision trees
We study sublinear and local computation algorithms for decision trees, ...
research
∙
11/03/2020
Estimating decision tree learnability with polylogarithmic sample complexity
We show that top-down decision tree learning heuristics are amenable to ...
research
∙
10/22/2020
Query strategies for priced information, revisited
We consider the problem of designing query strategies for priced informa...
research
∙
10/16/2020
Universal guarantees for decision tree induction via a higher-order splitting criterion
We propose a simple extension of top-down decision tree learning heurist...
research
∙
06/01/2020
Provable guarantees for decision tree induction: the agnostic setting
We give strengthened provable guarantees on the performance of widely em...
research
∙
04/09/2020
Politeness for the Theory of Algebraic Datatypes
Algebraic datatypes, and among them lists and trees, have attracted a lo...
research
∙
12/06/2019
Constructive derandomization of query algorithms
We give efficient deterministic algorithms for converting randomized que...
research
∙
11/18/2019