You are here

Joint CSE/Statistics Seminar Daniel Hsu

Columbia Unversity
Thursday, November 9, 2017, 3:00 pm

Daniel Hsu
EA 170
209 W. 18th Ave
Columbus, Ohio 43210

Linear Regression without Correspondence

Algorithmic and statistical aspects of linear regression when the correspondence between the covariates and the responses is unknown. First, I'll give a fully polynomial-time approximation scheme for the natural least squares optimization problem in any constant dimension. Next, in an average-case and noise-free setting where the responses exactly correspond to a linear function of iid draws from a standard multivariate normal distribution, I'll describe an efficient algorithm based on lattice basis reduction that exactly recovers the unknown linear function in arbitrary dimension.  Last, I'll establish lower bounds on the signal-to-noise ratio for approximate recovery of the unknown linear function.

This is joint work with Kevin Shi (Columbia) and Xiaorui Sun (Microsoft Research).

Bio: Daniel Hsu is an assistant professor in the Computer Science Department and a member of the Data Science Institute, both at Columbia University. Previously, he was a postdoc at Microsoft Research New England, and the Departments of Statistics at Rutgers University and the University of Pennsylvania. He holds a Ph.D. in Computer Science from UC San Diego, and a B.S. in Computer Science and Engineering from UC Berkeley. He received a 2014 Yahoo ACE Award, was selected by IEEE Intelligent Systems as one of "AI's 10 to Watch" in 2015, received a 2016 Sloan Research Fellowship, and is a 2017 Kavli Fellow.