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.