Paper-Conference

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
Aggregating Incomplete and Noisy Rankings
We consider the problem of learning the true ordering of a set of alternatives from largely incomplete and noisy rankings. We introduce …
Dimitris Fotakis, Alkis Kalavasis, Konstantinos Stavropoulos
PDF Cite URL