13 citations · 13 across the 15 of their papers we have counts for
6 papers · 1 filter
Learning Under Graphical Models
Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra +1
In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the unif…
Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
Recent work has shown the surprising power of low-degree sandwiching polynomial approximators in the context of challenging learning settings such as learning with distribution shi…
The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
Adam R. Klivans, Konstantinos Stavropoulos, Kevin Tian +1
Inspired by recent work on learning with distribution shift, we give a general outlier removal algorithm called iterative polynomial filtering and show a number of striking applica…
Testing Noise Assumptions of Learning Algorithms
Surbhi Goel, Adam R. Klivans, Konstantinos Stavropoulos +1
We pose a fundamental question in computational learning theory: can we efficiently test whether a training set satisfies the assumptions of a given noise model? This question has…
Tester-Learners for Halfspaces: Universal Algorithms
Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal tester-learner runs in fully polynomial time…
An Efficient Tester-Learner for Halfspaces
Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan (2023). In this model, a learner certifies t…