{"648986":{"#nid":"648986","#data":{"type":"event","title":"ARC Colloquium:  Ilias Diakonikolas (UW Madison)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EIlias Diakonikolas (UW Madison)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 20, 2021\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp; \u003C\/strong\u003ELearning with Massart Noise\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EWe 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\u0026lt;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\u0026rsquo;s FOCS 2003 tutorial.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nIn 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.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThe talk will primarily be based on joint works with Themis Gouleakis and Christos Tzamos; and with Daniel Kane.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.iliasdiakonikolas.org\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Learning with Massart Noise - Klaus 1116 East at 11am"}],"uid":"27544","created_gmt":"2021-07-22 14:47:47","changed_gmt":"2021-08-25 13:01:37","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2021-09-20T12:00:00-04:00","event_time_end":"2021-09-20T13:00:00-04:00","event_time_end_last":"2021-09-20T13:00:00-04:00","gmt_time_start":"2021-09-20 16:00:00","gmt_time_end":"2021-09-20 17:00:00","gmt_time_end_last":"2021-09-20 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}