Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
This paper studies the quadratic regression problem, where the response is the sum of a linear and quadratic term. The naive approach to solving this on p-dimensional vectors would be to expand it to a regression problem on p^2 dimensional vectors. The main contribution of this paper is a new algorithm that achieves running time and space complexity that are subquadratic in p, building off of ideas about how to get subquadratic algorithms for the maximum inner product problem. The paper makes solid progress on a basic regression problem.