`

Timezone: »

Poster
Sketching Structured Matrices for Faster Nonlinear Regression
Haim Avron · Vikas Sindhwani · David Woodruff

Sat Dec 07 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor #None
Motivated by the desire to extend fast randomized techniques to nonlinear $l_p$ regression, we consider a class of structured regression problems. These problems involve Vandermonde matrices which arise naturally in various statistical modeling settings, including classical polynomial fitting problems and recently developed randomized techniques for scalable kernel methods. We show that this structure can be exploited to further accelerate the solution of the regression problem, achieving running times that are faster than "input sparsity''. We present empirical results confirming both the practical value of our modeling framework, as well as speedup benefits of randomized regression.