MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Distribution-Independent PAC Learning of Halfspaces with Massart Noise

Themis Gouleakis
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 3, AG 4, RG1, MMCI, AG 2, INET, AG 5, SWS  
AG Audience
English

Date, Time and Location

Tuesday, 30 June 2020
13:00
30 Minutes
000
000
(virtual)

Abstract

We study the problem of distribution-independent PAC learning of halfspaces in the presence of Massart noise. Specifically, we are given a set of labeled examples (x,y) drawn from a distribution D on R^{d+1} such that the marginal distribution on the unlabeled points x is arbitrary and the labels y are generated by an unknown halfspace corrupted with Massart noise at noise rate η < 1/2. The goal is to find a hypothesis h that minimizes the misclassification error Pr(x,y)∼D [h(x) =/= y]. We give a poly (d, 1/ε) time algorithm for this problem with misclassification error η + ε. We also provide evidence that improving on the error guarantee of our algorithm might be computationally hard. Prior to our work, no efficient weak (distribution-independent) learner was known in this model, even for the class of disjunctions. The existence of such an algorithm for halfspaces (or even disjunctions) has been posed as an open question in various works, starting with Sloan (1988), Cohen (1997), and was most recently highlighted in Avrim Blum’s FOCS 2003 tutorial.


Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Contact

Themistoklis Gouleakis
+49 681 9325 1022

Tags, Category, Keywords and additional notes

Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.

Themistoklis Gouleakis, 06/23/2020 09:28 AM
Themistoklis Gouleakis, 06/17/2020 08:47 AM
Themistoklis Gouleakis, 06/17/2020 08:46 AM -- Created document.