research
∙
07/08/2023
A Strong Composition Theorem for Junta Complexity and the Boosting of Property Testers
We prove a strong composition theorem for junta complexity and show how ...
share
research
∙
03/27/2023
Lifting uniform learners via distributional decomposition
We show how any PAC learning algorithm that works under the uniform dist...
research
∙
02/17/2023
Subsampling Suffices for Adaptive Data Analysis
Ensuring that analyses performed on a dataset are representative of the ...
research
∙
11/04/2022
Certification with an NP Oracle
In the certification problem, the algorithm is given a function f with c...
research
∙
09/07/2022
Multitask Learning via Shared Features: Algorithms and Hardness
We investigate the computational efficiency of multitask learning of Boo...
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
∙
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
∙
06/10/2021
Multiway Online Correlated Selection
We give a 0.5368-competitive algorithm for edge-weighted online bipartit...
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
∙
08/14/2020
Efficient hyperparameter optimization by way of PAC-Bayes bound minimization
Identifying optimal values for a high-dimensional set of hyperparameters...
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
∙
12/06/2019
Constructive derandomization of query algorithms
We give efficient deterministic algorithms for converting randomized que...
research
∙
11/18/2019
Top-down induction of decision trees: rigorous guarantees and inherent limitations
Consider the following heuristic for building a decision tree for a func...
research
∙
04/19/2019