4 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…
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…
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…