BIU theory seminar- June 28 : Arsen Vasilyan (MIT) - Testing distributional assumptions of learning algorithms

6 views
Skip to first unread message

Arnold Filtser

unread,
Jun 21, 2023, 10:00:58 AM6/21/23
to BIU Theory Seminar, vasi...@mit.edu
Hello all,

Next week (Wed June 28) we will meet for our theory seminar.
Location: Building 605 room 14.

Even though this will be the last week of the semester, we might have additional talks during summer, so stay tuned.

See you there,
Arnold

Speaker: Arsen Vasilyan (MIT)
Title: Testing distributional assumptions of learning algorithms
Abstract: There are many high dimensional function classes that have fast agnostic learning algorithms when assumptions on the distribution of examples can be made, such as Gaussianity or uniformity over the domain. But how can one be confident that data indeed satisfies such assumption, so that one can trust in output quality of the agnostic learning algorithm? We propose a model by which to systematically study the design of tester-learner pairs (A,T), such that if the distribution on examples in the data passes the tester T then one can safely trust the output of the agnostic learner A on the data.
    To demonstrate the power of the model, we apply it to the classical problem of agnostically learning halfspaces under the standard Gaussian distribution and present a tester-learner pair with combined run-time of n^{\tilde{O}(1/ϵ^4)}. This qualitatively matches that of the best known ordinary agnostic learning algorithms for this task. In contrast, finite sample Gaussianity testers do not exist for the L1 and EMD distance measures. A key step is to show that half-spaces are well-approximated with low-degree polynomials relative to distributions with low-degree moments close to those of a Gaussian.
    We also go beyond spherically-symmetric distributions, and give a tester-learner pair for halfspaces under the uniform distribution on {0,1}^n with combined run-time of n^{\tilde{O}(1/ϵ^4)}. This is achieved using polynomial approximation theory and critical index machinery.
    We also show there exist some well-studied settings where 2^{\tilde{O}(n^0.5)} run-time agnostic learning algorithms are available, yet the combined run-times of tester-learner pairs must be as high as 2^Ω(n). On that account, the design of tester-learner pairs is a research direction in its own right independent of standard agnostic learning.

Joint work with Ronitt Rubinfeld.

Arnold Filtser

unread,
Jun 28, 2023, 4:01:37 AM6/28/23
to BIU Theory Seminar, vasi...@mit.edu
The seminar starts in one hour!
Reply all
Reply to author
Forward
0 new messages