NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:4344
Title:Interaction Hard Thresholding: Consistent Sparse Quadratic Regression in Sub-quadratic Time and Space

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.