Home
Publications
Awards
Light
Dark
Automatic
Paper-Conference
Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random
Gautam Chandrasekaran
,
Vasilis Kontonis
,
Konstantinos Stavropoulos
,
Kevin Tian
Cite
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
In the well-studied agnostic model of learning, the goal of a learner– given examples from an arbitrary joint distribution on …
Gautam Chandrasekaran
,
Adam Klivans
,
Vasilis Kontonis
,
Raghu Meka
,
Konstantinos Stavropoulos
PDF
Cite
URL
Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
Recent work of Klivans, Stavropoulos, and Vasilyan initiated the study of testable learning with distribution shift (TDS learning), …
Adam Klivans
,
Konstantinos Stavropoulos
,
Arsen Vasilyan
PDF
Cite
URL
Testable Learning with Distribution Shift
We revisit the fundamental problem of learning with distribution shift, in which a learner is given labeled samples from training …
Adam Klivans
,
Konstantinos Stavropoulos
,
Arsen Vasilyan
PDF
Cite
URL
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
PDF
Cite
URL
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
PDF
Cite
URL
An Efficient Tester-Learner for Halfspaces
We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan …
Aravind Gollakota
,
Adam Klivans
,
Konstantinos Stavropoulos
,
Arsen Vasilyan
PDF
Cite
URL
Tester-Learners for Halfspaces: Universal Algorithms
We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal …
Aravind Gollakota
,
Adam Klivans
,
Konstantinos Stavropoulos
,
Arsen Vasilyan
PDF
Cite
URL
Agnostically Learning Single-Index Models using Omnipredictors
We give the first result for agnostically learning Single-Index Models (SIMs) with arbitrary monotone and Lipschitz activations. All …
Aravind Gollakota
,
Parikshit Gopalan
,
Adam Klivans
,
Konstantinos Stavropoulos
PDF
Cite
URL
Learning and Covering Sums of Independent Random Variables with Unbounded Support
We study the problem of covering and learning sums $X = X_1 + ··· + X_n$ of independent integer-valued random variables $X_i$ (SIIRVs) …
Alkis Kalavasis
,
Konstantinos Stavropoulos
,
Emmanouil Zampetakis
PDF
Cite
URL
»
Cite
×