BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20240310T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20231105T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20240910T013221Z
UID:2eaf23dd-8c35-4138-8249-06d7e3bc530e
DTSTART;TZID=America/New_York:20231127T160000
DTEND;TZID=America/New_York:20231127T170000
CREATED:20231126T123724
DESCRIPTION:Abstract: In statistical learning theory\, the problem of deter
mining the optimal sample complexity of binary classification was a longst
anding challenge only recently resolved by Hanneke. Unfortunately\, these
arguments rely on the so-called uniform convergence principle which limits
its applicability to more general learning settings. In this talk\, we wi
ll discuss a new technique that overcomes this limitation and allows us to
derive optimal sample complexity bounds for settings where uniform conver
gence is provably suboptimal and in some cases\, does not yield any quanti
tative finite sample guarantees\, e.g. multiclass classification\, partial
concept classification\, and bounded regression. Our bounds resolve a few
open questions in the literature\, and our learning algorithm is based on
a novel analysis of the online-to-batch framework of Littlestone and the
celebrated one-inclusion graph algorithm of Haussler\, Littlestone\, and W
armuth.\nBased on joint work with Ishaq Aden-Ali\, Abhishek Shetty\, and N
ikita Zhivotovskiy.
LAST-MODIFIED:20231126T123724
LOCATION:32-D507
SUMMARY:Optimal PAC Bounds without Uniform Convergence
URL:https://calendar.csail.mit.edu/events/271327
END:VEVENT
END:VCALENDAR