Theory Seminar

Testing Assumptions of Learning Algorithms

Arsen VasilyanSimons Institute
WHERE:
3725 Beyster Building
SHARE:
(PASSCODE: 985224).
Many algorithms in modern learning theory assume that data satisfies various distributional assumptions (such as Gaussianity or uniformity over {0,1}^d). To be confident that these algorithms give valid predictions, one needs to be confident that the assumptions these algorithms make are correct. This motivates the research direction of testing distributional assumptions of learning algorithms. This research direction studies algorithms that come together with a tester, which can alert a user if some assumptions are not satisfied. Conversely, if the tester finds a specific dataset to be satisfactory, then a user can be confident in the guarantee given by the learning algorithm.

In this talk, I will survey the current state of knowledge and known techniques. The talk will not assume any prior knowledge in learning theory, and will discuss connections with a wide array of other fields of theoretical computer science, including pseudorandomness, sum-of-squares relaxations and outlier removal.

Talk based on papers joint with Adam R. Klivans, Vasilis Kontonis, Ronitt Rubinfeld, Surbhi Goel, Aravind Gollakota, Abhishek Shetty and Konstantinos Stavropoulos.

Organizer

Greg Bodwin

Organizer

Euiwoong Lee