24 papers
Multigroup Fairness and Omniprediction: Separations and Equivalences
Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade +3
Omniprediction is a learning guarantee which requires a single predictor to be competitive relative to the best hypothesis from a benchmark class for any loss chosen from a family…
Efficient Robust Learning at the Information-Theoretic Limit
Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1
In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifie…
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.…
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…
Efficient Calibration for Decision Making
Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar +1
A decision-theoretic characterization of perfect calibration is that an agent seeking to minimize a proper loss in expectation cannot improve their outcome by post-processing a per…
A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first fully polynomial-time algorithm for learning halfspaces with respect to the uniform distribution on the hypercube in the presence of contamination, where an adver…
Sparse Linear Regression is Easy on Random Supports
Gautam Chandrasekaran, Raghu Meka, Konstantinos Stavropoulos
Sparse linear regression is one of the most basic questions in machine learning and statistics. Here, we are given as input a design matrix and meas…
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…
Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
Gautam Chandrasekaran, Adam R. Klivans, Lin Lin Lee +1
We give the first provably efficient algorithms for learning neural networks with distribution shift. We work in the Testable Learning with Distribution Shift framework (TDS learni…
Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
Gautam Chandrasekaran, Vasilis Kontonis, Konstantinos Stavropoulos +1
We study the problem of PAC learning -margin halfspaces with Massart noise. We propose a simple proper learning algorithm, the Perspectron, that has sample complexity $\widetild…
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…
Learning Constant-Depth Circuits in Malicious Noise Models
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
The seminal work of Linial, Mansour, and Nisan gave a quasipolynomial-time algorithm for learning constant-depth circuits () with respect to the uniform distribution…
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis +2
In traditional models of supervised learning, the goal of a learner-- given examples from an arbitrary joint distribution on -- is to output a hypoth…
Efficient Discrepancy Testing for Learning with Distribution Shift
Gautam Chandrasekaran, Adam R. Klivans, Vasilis Kontonis +2
A fundamental notion of distance between train and test distributions from the field of domain adaptation is discrepancy distance. While in general hard to compute, here we provide…
Tolerant Algorithms for Learning with Arbitrary Covariate Shift
Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos +1
We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one distribution but evaluated on a different, potentially a…
Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
Recent work of Klivans, Stavropoulos, and Vasilyan initiated the study of testable learning with distribution shift (TDS learning), where a learner is given labeled samples from tr…
Testable Learning with Distribution Shift
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
We revisit the fundamental problem of learning with distribution shift, in which a learner is given labeled samples from training distribution , unlabeled samples from test dist…
Agnostically Learning Single-Index Models using Omnipredictors
Aravind Gollakota, Parikshit Gopalan, Adam R. Klivans +1
We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. All prior work either held only in the realizable s…
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…
Learning and Covering Sums of Independent Random Variables with Unbounded Support
Alkis Kalavasis, Konstantinos Stavropoulos, Manolis Zampetakis
We study the problem of covering and learning sums of independent integer-valued random variables (SIIRVs) with unbounded, or even infinite, support.…
Aggregating Incomplete and Noisy Rankings
Dimitris Fotakis, Alkis Kalavasis, Konstantinos Stavropoulos
We consider the problem of learning the true ordering of a set of alternatives from largely incomplete and noisy rankings. We introduce a natural generalization of both the classic…