BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1035
DTSTAMP:20230914T125948Z
SUMMARY:Testing Noisy Linear Equations for Sparsity
DESCRIPTION:Speaker: Anindya De (University of Pennsylvania\nUnited States)
\n\nAbstract: \nAbstract: Consider the following basic problem in sparse l
inear regression -- an algorithm gets labeled samples of the form (x\, +
\\eps) where w is an unknown n-imensional vector\, x is drawn from a bac
kground distribution D and \\eps is some independent noise. Given the pro
mise that w is k-sparse\, the breakthrough work of Candes\, Rhomberg and
Tao (2005) shows that w can be recovered with samples and time which scal
es as O(k log n). This should be contrasted with general linear regressio
n where O(n) samples are information theoretically necessary.\nIn this
talk\, we look at this question from the vantage point of property testin
g and study the decision variant of the following question -- namely\, wh
at is the complexity of deciding if the unknown vector w is k-sparse (or
at least say 0.01 far from k-sparse in \\ell_2 distance). We show that th
e decision version of the problem can be solved with samples which are in
dependent of n as long as the background distribution D is i.i.d. and the
components are not Gaussian. We further show that weakening any of the c
onditions in this result necessarily makes the complexity scale as log n
(thus showing our results are tight).\nJoint work with Xue Chen (Northwes
tern) and Rocco Servedio (Columbia).\n
URL:https://www.tcs.tifr.res.in/web/events/1035
DTSTART;TZID=Asia/Kolkata:20200106T103000
DTEND;TZID=Asia/Kolkata:20200106T113000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR