Algorithms & Randomness Center (ARC)
Ilias Diakonikolas (UW Madison)
Monday, September 20, 2021
Klaus 1116 East - 11:00 am
Title: Learning with Massart Noise
Abstract: We study the classical problem of learning halfspaces in the presence of Massart (or bounded) noise. In the Massart model, an adversary can flip the label of each example independently with probability at most $eta<1/2$. The goal of the learner is to find a hypothesis with small misclassification error. Characterizing the efficient learnability of halfspaces in the Massart model has been a longstanding open question in learning theory, posed in various works, starting with Sloan (1988), Cohen (1997), and highlighted in Avrim Blum’s FOCS 2003 tutorial.
In this talk, we will survey two recent results that resolve this question. We will start by describing the first polynomial-time learning algorithm for Massart halfspaces with non-trivial error guarantees. We will then complement this upper bound with a Statistical Query lower bound, establishing that the error guarantee achieved by our algorithm is essentially optimal. Our findings highlight the algorithmic possibilities and limitations of distribution-free robustness with respect to natural semi-random noise models.
The talk will primarily be based on joint works with Themis Gouleakis and Christos Tzamos; and with Daniel Kane.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
