Speaker: Xue Chen

\nAffiliation: Northwestern Universit
y

Title: Active Regression via Linear-Sample Sparsification

\n< p>Abstract:\nWe present an approach that improves the sample comp
lexity for a variety of curve fitting problems\, including active learning
for linear regression\, polynomial regression\, and continuous sparse Fou
rier transforms. In the active linear regression problem\, one would like
to estimate the least squares solution \\beta^* minimizing ||X \\beta – y|
|_2 given the entire unlabeled dataset X \\in \\R^{n \\times d} but only o
bserving a small number of labels y_i. We show that O(d/\\eps) labels suff
ice to find an \\eps-approximation \\wt{\\beta} to \\beta^*:

\n<
/div>\n

E[||X \\wt{\\beta} – X\\beta^*||_2^2] \\leq \\eps ||X \\beta^* – y||_2^2.

\nThis improves on the best previous result of O(d \\log d
+ d/\\eps) from leverage score sampling. We also present results for the
*inductive* setting\, showing when \\wt{\\beta} will generalize to fr
esh samples\; these apply to continuous settings such as polynomial regres
sion. Finally\, we show how the techniques yield improved results for the
non-linear sparse Fourier transform setting.

\n

Bio: Xue Chen is broadly interested in randomized algorithms and the use of randomness in computati on. Specific areas include Fourier transform\, learning theory and optimiz ation\, and pseudorandomness. He obtained his Ph.D. at the University of T exas at Austin\, under the supervision of David Zuckerman. Currently\, he is a postdoctoral fellow in Northwestern University.

DTSTART;TZID=America/New_York:20190227T120000 DTEND;TZID=America/New_York:20190227T130000 SEQUENCE:0 SUMMARY:[Theory Seminar] Xue Chen URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-xue-chen/ X-COST-TYPE:free END:VEVENT END:VCALENDAR