BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1178
DTSTAMP:20230914T125953Z
SUMMARY:Convergence of nearest neighbor classification
DESCRIPTION:Speaker: Sanjoy Dasgupta (UC San Diego Jacobs School of Enginee
ring\nSan Diego\, California.)\n\nAbstract: \nThe "nearest neighbor (NN) c
lassifier" labels a new data instance by taking a majority vote over the k
most similar instances seen in the past. With an appropriate setting of k
\, it is capable of modeling arbitrary decision rules.\nTraditional conver
gence analysis for nearest neighbor\, as well as other nonparametric estim
ators\, has focused on two questions: (1) universal consistency---that is\
, convergence (as the number of data points goes to infinity) to the best-
possible classifier without any conditions on the data-generating distribu
tion---and (2) rates of convergence that are minimax-optimal\, assuming th
at data distribution lies within some standard class of smooth functions.\
nWe advance what is known on both these fronts. But we also show how to at
tain significantly stronger types of results: (3) rates of convergence tha
t are accurate for the specific data distribution\, rather than being gene
ric for a smoothness class\, and (4) rates that are accurate for the distr
ibution as well as the specific query point.\nAlong the way\, we introduce
a notion of "margin" for nearest neighbor classification. This is a funct
ion m(x) that assigns a positive real number to every point in the input s
pace\; and the size of the data set needed for NN (with adaptive choice of
k) to predict correctly at x is\, roughly\, 1/m(x).\nThe statistical back
ground needed for understanding these results is minimal\, and will be int
roduced during the talk.\nThis is joint work with Akshay Balsubramani\, Ka
malika Chaudhuri\, Yoav Freund\, and Shay Moran.\nBio:\nSanjoy Dasgupta wo
rks on unsupervised and minimally supervised learning. He is a professor o
f computer science at UC San Diego.\nYouTube livestream: https://www.youtu
be.com/watch?v=NMrPyN2neaw\n
URL:https://www.tcs.tifr.res.in/web/events/1178
DTSTART;TZID=Asia/Kolkata:20220111T103000
DTEND;TZID=Asia/Kolkata:20220111T113000
LOCATION:Via Zoom
END:VEVENT
END:VCALENDAR