12 papers
Iterative Chow Filtering for Learning with Distribution Shift
Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans +2
Recent work due to Goel et al. gave the first efficient algorithms for learning with distribution shift in the challenging PQ framework. In this setting, a learner receives labeled…
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.…
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…
The Importance of Being Smoothly Calibrated
Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar +1
Recent work has highlighted the centrality of smooth calibration [Kakade and Foster, 2008] as a robust measure of calibration error. We generalize, unify, and extend previous resul…
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…