Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination

We thank the reviewer for their time and effort in providing feedback and their positive assessment of our work. 

Regarding the proof sketches on Pages 8 and 9: Unfortunately the page restriction did not give us sufficient room for proper explanations of everything in the main body; we will reorganize/rephrase them better using the additional page allowed in the revised version.

We thank the reviewer for their time and effort in providing feedback and their positive assessment of our work. 

• We analyzed the class of SQ algorithms because it is a very versatile and powerful class of algorithms. Please see [FGRVX17] for details. We believe that the same construction should lead to similar hardness against other classes of algorithms, such as low-degree polynomial tests (see [BBHLS21] for a connection to SQ algorithms) and natural Sum-of-Square formulations.

• Sensitivity to the precise distribution of the contamination:

  • The sample complexity requirement is understandably dependent on the choice of the noise distribution. Intuitively, if the noise is very benign (for example, if the noise is always zero), then roughly $d$ samples suffice (both information-theoretically and computationally), whereas if the noise is chosen carefully (say discrete Gaussian, as we show), then the computational sample complexity can be large. Importantly, we prove an information-computation tradeoff over the worst-case oblivious contamination, which is the standard goal in the minimax setting.

  • The SQ hardness would continue to hold not only for discrete Gaussians (DG), but any distribution $E$ that is sufficiently close to DG in terms of its moments. This follows from the arguments implicit in Theorem 3.7, where we transferred SQ hardness from usual Gaussian to DG using nearly matching moments.

• The choice of discrete Gaussian

  • At a high level, we chose discrete Gaussian because of the following insights (please see Section 1.2 for more details)
    • The case of continuous Gaussian is information-theoretically and SQ hard (but, unfortunately, is not a valid instance of our problem as it does not assign $>= \alpha$ mass to 0), and
    • Distinguishing between continuous Gaussian and discrete Gaussian should be SQ-hard.  Hence, by choosing discrete Gaussian as our instance, we simultaneously satisfy the model assumption and the desired SQ
  • Furthermore, the discrete gaussian noise is also optimal (in the sense of the largest SQ complexity) for the *testing* problem: there exists an efficient SQ algorithm that solves the testing problem (with any valid noise satisfying Definition 1.1) with only polynomially many queries to the VSTAT$(m)$ oracle for $m$ roughly $\sqrt{d}/\alpha^2$.  As mentioned in the conclusions section (Section 4), establishing optimality for the estimation problem is left as an interesting open problem.

We thank the reviewer for their time and effort in providing feedback and their positive assessment of our work. We respond to their questions in more detail below:

• “Connection to the original problem is not as direct as one would like to be”

  • We point out that our SQ-hardness result also applies directly to the search version of the problem (see [FGRVX17, Definition 2.1] for details) without going to the testing problem. As an example, see [DKPPS21] who studied both the search and testing versions. 

  • We presented the testing problem because (i) the testing problem already captures the underlying SQ hardness while being no harder than estimation, and (ii) the connection between SQ and low-degree polynomials has been established for testing problems [BBHLS21].

  • Please let us know if we have misunderstood your question. 

• “It proves that, within the statistical query model, exact recovery requires …”

  • We would like to mention that we establish hardness not only for exact recovery, but also for weak recovery (error less than $\rho/4$). This follows from Proposition 1.4 and Theorem 1.6. 

• “The proof goes through multiple equivalent rephrasings of the same testing problems. Can this be simplified?

  • We use only one rephrasing (Proposition 3.2), which follows from a simple computation of conditional distribution. Please let us know if we may have misunderstood your point.

  • If the reviewer is asking whether we could directly prove SQ hardness for discrete Gaussians without the connection with standard Gaussian, then for the reasons mentioned in Section 1.2 (related to Gaussian Fourier Analysis), it is unclear to us.

• “The result is not optimal and implies a gap only when $\alpha \ll 1/\sqrt{d}$”

  • We agree with the reviewer, and we have mentioned this as a concrete open problem in the Conclusion section.

We thank the reviewer for their time and effort in providing feedback and their positive assessment of our work. 

We are grateful to the reviewer for their suggestions and typos. 

Please find the answers to questions below:

• Line 149: We mean that under $P$, the marginal of $X$ (respectively $y$) matches that of $X$ under $Q_v$ (respectively $y$ under $Q_v$) . But unlike $Q_v$, where $X$ and $y$ are not independent, they are independent under $P$.

• Lines 151-152: We meant that the distribution of $X|y$ has the following structure (please see the proof of Proposition 3.3 for more details):

  • If $u$ is orthogonal to $v$, then $u^\top X$ (conditioned on $y$) is distributed as standard Gaussian.

  • If $u$ is equal to $v$, then $u^\top X$ (conditioned on $y$) is distributed as $A_y$.

That is, $X|y$ is an instance of High-DImensional Hidden Direction Distribution (Definition 2.7). In the notation of that definition, X|y \~ P_v^{A_y}.

• Line 174: We meant Definition 2.4. We will update the terminology and link the definition there.