NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center

### Reviewer 1

This paper proposes a new algorithm – Interaction Hard Thresholding (IntHT) for the quadratic regression problem, a variant of Iterative Hard Thresholding that uses the special quadratic structure to devise a new way to (approx.) extract the top elements of a $p^2$ size gradient in sub-$p^2$ time and space. Then the authors show that IntHT linearly converges to a consistent estimate under standard high-dimensional sparse recovery assumptions. Perhaps, the algorithm is the first one to provably accurately solve quadratic regression problem in sub-quadratic time and space. Overall I find the results and the algorithms are quite interesting although the main idea of the new algorithm is quite simple: It mainly combines the existing technique from [20] with IHT to compute the top elements of the full gradient. The paper is well organized and presented. Minor comments: -As also noted in the paper, the quadratic regression problem has a strong background in real applications. Could you give a real example that $\Theta$ is sparse? - I am quite curious about the proof novelty. What is the key novel of the proof? ------After rebuttal----------------------- The authors have addressed my concerns well.

### Reviewer 2

Originality: This paper applies approaches in Maximum Inner Product to the problem of quadratic regression in order to reduce the time and space complexities. It is also interesting that convergence analysis can be established for such methods. Quality: Although theoretical results have been established for the proposed methods, the strength and optimality of the established results are unclear. Furthermore, the numerical simulations do not show the trade-off between statistical and computational efficiencies. Clarity: The paper is basically well-written. Significance: The problem is not really well motivated, so it is hard to evaluate the significance of the proposed method. -----------After rebuttal---------- Given my previous concerns are mostly addressed, I changed my rating from 5 to 7.