Paper-Conference

The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination

Inspired by recent work on learning with distribution shift, we give a general outlier removal algorithm called iterative polynomial …

Adam Klivans, Konstantinos Stavropoulos, Kevin Tian, Arsen Vasilyan

Efficient Calibration for Decision Making

A decision-theoretic characterization of perfect calibration is that an agent seeking to minimize a proper loss in expectation cannot …

Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar, Pranay Tankala

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube

We give the first fully polynomial-time algorithm for learning halfspaces with respect to the uniform distribution on the hypercube in …

Gautam Chandrasekaran, Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Sparse Linear Regression is Easy on Random Supports

Sparse linear regression is one of the most basic questions in machine learning and statistics. Here, we are given as input a design …

Gautam Chandrasekaran, Raghu Meka, Konstantinos Stavropoulos

Learning Constant-Depth Circuits in Malicious Noise Models

The seminal work of Linial, Mansour, and Nisan gave a quasipolynomial-time algorithm for learning constant-depth circuits (𝖠𝖢0) with …

Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees

We give the first provably efficient algorithms for learning neural networks with distribution shift. We work in the Testable Learning …

Gautam Chandrasekaran, Adam Klivans, Lin Lin Lee, Konstantinos Stavropoulos

Testing Noise Assumptions of Learning Algorithms

We pose a fundamental question in computational learning theory: can we efficiently test whether a training set satisfies the …

Surbhi Goel, Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan

Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random

We study the problem of PAC learning $\gamma$-margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the …

Gautam Chandrasekaran, Vasilis Kontonis, Konstantinos Stavropoulos, Kevin Tian

Tolerant Algorithms for Learning with Arbitrary Covariate Shift

We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one …

Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos, Arsen Vasilyan

Efficient Discrepancy Testing for Learning with Distribution Shift

A fundamental notion of distance between train and test distributions from the field of domain adaptation is discrepancy distance. …

Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Konstantinos Stavropoulos, Arsen Vasilyan