Learning Geometric Concepts from Positive Examples

28 Jan
Theory of Computation Seminar
Christos Tzamos, University of Wisconsin-Madison
Monday, January 28, 2019 - 1:45pm to 2:45pm
Pierce Hall 213 (Brooks Room)

We consider the learnability of geometric concepts and distributions given only positive examples.  While learning from positive examples is generally not possible without any additional assumptions, we propose two approaches that enable us to obtain positive results. When samples are generated from a structured distribution such as a Gaussian, we show that any concept class that has low Gaussian surface area can be learned using only few positive samples.   In addition, we show that when an oracle is available that can check the validity of generated examples during training, stronger results can be obtained even under arbitrary distributions and under the presence of "model errors".   We show that, while proper learning often requires exponentially many queries to the invalidity oracle, improper distribution learning can be done efficiently using polynomially many queries. 

The talk will be based on my recent work with Hanneke, Kalai, and Kamath (COLT 2018) and Daskalakis, Gouleakis and Zampetakis (FOCS 2018)  and more recent follow-ups.

Speaker Bio: 

Christos Tzamos is an As­sis­tant Pro­fes­sor in the De­part­ment of Com­puter Sci­ences at Uni­ver­sity of Wis­con­sin‐Madi­son and a mem­ber of the The­ory of Com­put­ing group. His re­search in­ter­ests lie in the in­ter­face of The­ory of Com­pu­ta­tion with Eco­nom­ics and Game The­ory, Ma­chine Learn­ing, Sta­tis­tics and Prob­a­bil­ity The­ory. He com­pleted his PhD in the The­ory of Com­pu­ta­tion group of MIT ad­vised by Costis Daskalakis and worked as a post‐doc­toral re­searcher at Mi­crosoft Re­search New Eng­land. Be­fore that, he stud­ied Elec­tri­cal and Com­puter En­gi­neer­ing at NTUA and was a mem­ber of Core­lab work­ing with Dim­itris Fo­takis. Christos received the George M. Sprowls Award for the best Com­puter Sci­ence PhD the­sis in the EECS De­part­ment of MIT and is a recipient of the Simons Graduate Award in Theoretical Computer Science. He is also a recipient of a Best Paper award at the ACM Conference on Economics and Computation in 2013.