5 papers
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…
A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
Xi Chen, Shyamal Patel, Rocco A. Servedio
The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing:…