2 citations · 2 across the 7 of their papers we have counts for
5 papers · 1 filter
A Separation Between Distribution-Free SQ Learning and Dimension Complexity
Shyamal Patel
We show that there exists a class of boolean functions C such that there is a distribution-independent statistical query algorithm for learning C that makes a polynomial numb…
Distribution-Free Halfspace Testing with Samples
Xi Chen, Renato Ferreira Pinto, Nathaniel Harms +2
We prove a tight lower bound on the number of samples required for testing halfspaces over , in the distribution-free sample-based model where the underlying…
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
Adam R. Klivans, Shyamal Patel, Konstantinos Stavropoulos +1
Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al. (2020)) and TDS learning (Klivans et al.…
Tight Bounds for Learning Polyhedra with a Margin
Shyamal Patel, Santosh Vempala
We give an algorithm for PAC learning intersections of halfspaces with a margin to within error that runs in time $\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1})…
Learning Functions of Halfspaces
Josh Alman, Shyamal Patel, Rocco A. Servedio
We give an algorithm that learns arbitrary Boolean functions of arbitrary halfspaces over , in the challenging distribution-free Probably Approximately Correct (P…