6 views

Skip to first unread message

Jun 21, 2023, 10:00:58 AM6/21/23

to BIU Theory Seminar, vasi...@mit.edu

Hello all,

**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.

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.

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.

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

Search

Clear search

Close search

Google apps

Main menu