8 citations · 18 across the 23 of their papers we have counts for
29 papers
Streaming Algorithms for Monotonicity Testing
Amir Azarmehr, Soheil Behnezhad, Lily Chung +3
Consider a poset - or equivalently an -vertex DAG - and a boolean function on its vertex set. We say is monotone if f…
Samplability makes learning easier
Guy Blanc, Caleb Koch, Jane Lange +2
The standard definition of PAC learning (Valiant 1984) requires learners to succeed under all distributions -- even ones that are intractable to sample from. This stands in contras…
The power of quantum circuits in sampling
Guy Blanc, Caleb Koch, Jane Lange +2
We give new evidence that quantum circuits are substantially more powerful than classical circuits. We show, relative to a random oracle, that polynomial-size quantum circuits can…
A Distributional-Lifting Theorem for PAC Learning
Guy Blanc, Jane Lange, Carmen Strassle +1
The apparent difficulty of efficient distribution-free PAC learning has led to a large body of work on distribution-specific learning. Distributional assumptions facilitate the des…
Robust learning of halfspaces under log-concave marginals
Jane Lange, Arsen Vasilyan
We say that a classifier is \emph{adversarially robust} to perturbations of norm if, with high probability over a point drawn from the input distribution, there is no point…
Predicting quantum channels over general product distributions
Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh +3
We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an -qubit channel and an observable , we aim to learn the…
Harnessing the Power of Choices in Decision Tree Learning
Guy Blanc, Jane Lange, Chirag Pabbaraju +3
We propose a simple generalization of standard and empirically successful decision tree learning algorithms such as ID3, C4.5, and CART. These algorithms, which have been central t…
Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions
Jane Lange, Ephraim Linder, Sofya Raskhodnikova +1
We study local filters for the Lipschitz property of real-valued functions , where the Lipschitz property is defined with respect to an arbitrary undirected graph $…
Agnostic proper learning of monotone functions: beyond the black-box correction barrier
Jane Lange, Arsen Vasilyan
We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given uniformly random examples of an unknown…
Lifting uniform learners via distributional decomposition
Guy Blanc, Jane Lange, Ali Malik +1
We show how any PAC learning algorithm that works under the uniform distribution can be transformed, in a blackbox fashion, into one that works under an arbitrary and unknown distr…
Certification with an NP Oracle
Guy Blanc, Caleb Koch, Jane Lange +2
In the certification problem, the algorithm is given a function with certificate complexity and an input , and the goal is to find a certificate of size $\le \text…
A Query-Optimal Algorithm for Finding Counterfactuals
Guy Blanc, Caleb Koch, Jane Lange +1
We design an algorithm for finding counterfactuals with strong theoretical guarantees on its performance. For any monotone model and instance , our a…
Open Problem: Properly learning decision trees in polynomial time?
Guy Blanc, Jane Lange, Mingda Qiao +1
The authors recently gave an time membership query algorithm for properly learning decision trees under the uniform distribution (Blanc et al., 2021). The previ…
Popular decision tree algorithms are provably noise tolerant
Guy Blanc, Jane Lange, Ali Malik +1
Using the framework of boosting, we prove that all impurity-based decision tree learning algorithms, including the classic ID3, C4.5, and CART, are highly noise tolerant. Our guara…
Properly learning monotone functions via local reconstruction
Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan
We give a -time algorithm for properly learning monotone Boolean functions under the uniform distribution over . Our algorithm is robust to ad…
The Query Complexity of Certification
Guy Blanc, Caleb Koch, Jane Lange +1
We study the problem of {\sl certification}: given queries to a function with certificate complexity and an input , output a size- c…
On the power of adaptivity in statistical adversaries
Guy Blanc, Jane Lange, Ali Malik +1
We study a fundamental question concerning adversarial noise models in statistical problems where the algorithm receives i.i.d. draws from a distribution . The definit…
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…
Reconstructing decision trees
Guy Blanc, Jane Lange, Li-Yang Tan
We give the first {\sl reconstruction algorithm} for decision trees: given queries to a function that is -close to a size- decision tree, our algorithm provide…
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\}^…