Interaction Hard Thresholding: Consistent Sparse Quadratic Regression in Sub-quadratic Time and Space

In this paper we provide a new algorithm - Interaction Hard Thresholding (IntHT) - which is the first one to provably accurately solve this problem in sub-quadratic time and space. It is a variant of Iterative Hard Thresholding; one that uses the special quadratic structure to devise a new way to (approx.) extract the top elements of a p