BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Steve Hanneke (TTIC) DTSTART:20210303T180000Z DTEND:20210303T190000Z DTSTAMP:20260423T035027Z UID:TCSPlus/21 DESCRIPTION:Title: A Theory of Universal Learning\nby Steve Hanneke (TTIC) as part of TC S+\n\n\nAbstract\nHow quickly can a given class of concepts be learned fro m examples? It is common to measure the performance of a supervised machin e learning algorithm by plotting its "learning curve"\, that is\, the deca y of the error rate as a function of the number of training examples. Howe ver\, the classical theoretical framework for understanding learnability\, the PAC model of Vapnik-Chervonenkis and Valiant\, does not explain the b ehavior of learning curves: the distribution-free PAC model of learning ca n only bound the upper envelope of the learning curves over all possible d ata distributions. This does not match the practice of machine learning\, where the data source is typically fixed in any given scenario\, while the learner may choose the number of training examples on the basis of factor s such as computational resources and desired accuracy.\n\nIn this work\, we study an alternative learning model that better captures such practical aspects of machine learning\, but still gives rise to a complete theory o f the learnable in the spirit of the PAC model. More precisely\, we consid er the problem of universal learning\, which aims to understand the perfor mance of learning algorithms on every data distribution\, but without requ iring uniformity over the distribution. The main result of this work is a remarkable trichotomy: there are only three possible rates of universal le arning. More precisely\, we show that the learning curves of any given con cept class decay either at an exponential\, linear\, or arbitrarily slow r ates. Moreover\, each of these cases is completely characterized by approp riate combinatorial parameters\, and we exhibit optimal learning algorithm s that achieve the best possible rate in each case.\n\nJoint work with Oli vier Bousquet\, Shay Moran\, Ramon van Handel\, and Amir Yehudayoff.\n LOCATION:https://researchseminars.org/talk/TCSPlus/21/ END:VEVENT END:VCALENDAR