6 papers · 1 filter
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…
Computational-Statistical Tradeoffs from NP-hardness
Guy Blanc, Caleb Koch, Carmen Strassle +1
A central question in computer science and statistics is whether efficient algorithms can achieve the information-theoretic limits of statistical problems. Many computational-stati…
Fast decision tree learning solves hard coding-theoretic problems
Caleb Koch, Carmen Strassle, Li-Yang Tan
We connect the problem of properly PAC learning decision trees to the parameterized Nearest Codeword Problem (-NCP). Despite significant effort by the respective communities, al…
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
Guy Blanc, Alexandre Hayderi, Caleb Koch +1
Smooth boosters generate distributions that do not place too much weight on any given example. Originally introduced for their noise-tolerant properties, such boosters have also fo…
Superconstant Inapproximability of Decision Tree Learning
Caleb Koch, Carmen Strassle, Li-Yang Tan
We consider the task of properly PAC learning decision trees with queries. Recent work of Koch, Strassle, and Tan showed that the strictest version of this task, where the hypothes…
A Strong Direct Sum Theorem for Distributional Query Complexity
Guy Blanc, Caleb Koch, Carmen Strassle +1
Consider the expected query complexity of computing the -fold direct product of a function to error with respect to a distribution . One…