Near-optimal Active Regression of Single-Index Models

We thank the reviewer for the comments. Below we address the reviewer's questions.

• Presentation: We agree with the reviewer that the paper is very technical and providing background on the mathematical tools such as Lewis weights helps readers unfamiliar with these concepts better understand our result. We will move this background from the appendix to the main text with additional explanations to improve the presentation.

  In Line 219 - Line 226, the techniques used to upper bound $\sup_{x \in T} \operatorname{Err}(x)$ have been employed in several earlier works related to the active regression problem (such as (Yasuda, 2024)) or subspace embeddings. Therefore, we intentionally phrased them as black boxes as they are not our main contribution. We will make this clearer in the revised version. The most novel contribution lies in the section on ``further improvement'', which enables us to achieve a near-optimal dependence on $\epsilon$ in query complexity.

• Motivation for $(1+\epsilon)$-approximation: We would like to clarify that our paper does not consider the agnostic case, that is, the function $f$ is given. The statement of Theorem 1 says ``given ... $f$'' and Algorithm 2 lists $f$ as part of the input. Therefore, the hardness result of the agnostic case does not apply here. Even in the agnostic case, where one can only have a PTAS for $(1+\epsilon)$-approximation, a smaller query complexity implies solving a smaller-scale regression problem (dimension $\operatorname{poly}(d/\epsilon)$ versus $n$), which is advantageous, particularly when solving such problems is computationally hard (runtime $(d/\epsilon)^{\operatorname{poly}(1/\epsilon)}$ versus $n^{\operatorname{poly}(1/\epsilon)}$).

We thank the reviewer for the comments. Below we address the reviewer's questions.

• Q1: As explained in the introduction section, the impossibility result of Gajjar et al. (2024) states that one cannot hope for

  $$\|f(A\hat{x})-b\|_2^2 \leq C\cdot \textsf{OPT}$$

  with an algorithm using a polynomial number of queries. Therefore, their error guarantee contains an additive term as

  $$\|f(A\hat{x})-b\|_2^2 \leq C(\textsf{OPT} + \epsilon L^2\|Ax^\ast\|_2^2).$$

  Note that this is for $p=2$ with a constant-factor approximation. For us, this hardness result remains and our result has a similar error guarantee to that of Gajjar et al. (2024). We obtain a $(1+\epsilon)$-approximation for general $p$ with an analogous error (see Theorem 1)

  $$\|f(A\hat{x})-b\|_p^p \leq (1+\epsilon)(\textsf{OPT} + \epsilon L^p\|Ax^\ast\|_p^p).$$

  By rescaling $\epsilon$ by at most a constant factor, we can rewrite the error guarantee above as

  $$\|f(A\hat{x})-b\|_p^p \leq (1+\epsilon)\textsf{OPT} + \epsilon L^p\|Ax^\ast\|_p^p.$$

• Q2: Theorem 1 is an upper bound while Theorems 2 and 3 are lower bounds. The success probabilities in these theorems can be made an arbitrary number greater than $1/2$ by adjusting the constants (the hidden constants in big-$O$ and big-$\Omega$ notations usually depend on the failure probability). We chose these constants specifically to simplify the analyses and will make appropriate adjustments to improve the readability.

• Q3: At present, we do not have a high-probability result, as the primary focus is on achieving near-optimal query complexity. For failure probability $\delta$, the current argument introduces a $1/\delta$ factor in the query complexity, owing to the application of Markov's inequality for the initial value of $R$. It may be possible to improve the dependence on $\delta$ using the techniques similar to those in (Musco et al., 2022), and we leave this as a direction for future work.

Regarding the weaknesses,

• W1: There are relatively few papers with provable query complexities for this problem, and, to the best of our knowledge, we have cited all known theoretical works in this line of research. On the other hand, we believe that there are other papers related to our problem and including them may help readers better understand our problem and active regression in general. We will provide a more comprehensive literature review of the relevant areas in the revised version.

• W2: This submission focuses on the theoretical aspects of query complexity, with a particular emphasis on the $\epsilon$-dependence of query complexity. While fewer queries may suffice for certain real-world datasets, we consider this a potential direction for future work.

• W3: The algorithm is presented in Section 3. We agree with the reviewer that moving it earlier in the paper may enhance readability.

The following are our responses to the reviewer's questions.

• Line 148: Here we are looking at the $\ell_p$ norm and it can be proved that exact equality (i.e. isometric embedding) is generally impossible. Normally the approximation in subspace embeddings is multiplicative, i.e., one has a distortion parameter $\epsilon$ and wants $(1-\epsilon)\|Ax\|_p \leq \|SAx\|_p \leq (1+\epsilon)\|Ax\|_p$.

• Line 163: In the definition of $\operatorname{Err}(x)$ in Equation (5), we use $x^\ast$, which is the optimal solution to the regression problem. Here, we are saying that this $x^\ast$ can be actually replaced with an arbitrary point $\bar{x}$ in the definition of $\operatorname{Err}(x)$ and the argument for upper bounding $\operatorname{Err}(x)$ still works. Indeed, in our detailed analysis, we will pick $\bar{x}$ to be different points including $x^\ast$ and hence we would like to highlight this flexibility.

• Line 172: The symbol ``$\lesssim$'' indicates an inequality up to a constant factor, similar to the big-$O$ notation. Specifically, we write $f(x) \lesssim g(x)$ if there exists a constant $C$ such that $f(x) \leq C g(x)$. This notation is explained in the Preliminaries section (Section A) of the appendix and we will move it to the main text to improve the presentation.

• Line 197: This inequality is exact.

• Line 215: This inequality uses ``$\lesssim$'', indicating that a constant factor is lost.

• Line 220: Equation (9) shows that $\|A\hat{x}\|_p^p \lesssim R$ for $R = \frac{1}{\epsilon}\textsf{OPT} + \|Ax^\ast\|_p^p$. This fits the definition of $T$ (with appropriate constants hidden in $\lesssim$) and so $\hat{x}\in T$.

• Line 299: To repeat the process, observe that Line 296 gives a better bound on $\|A\hat{x}\|_p^p \lesssim \frac{1}{\sqrt{\epsilon}}\textsf{OPT} + \|Ax^\ast\|_p^p$ and so we can define a new, smaller $R$ to be $R = \frac{1}{\sqrt{\epsilon}}\textsf{OPT} + \|Ax^\ast\|_p^p$. Using this new $R$ and repeat the argument, we can then obtain a better bound $\|A\hat{x}\|_p^p \lesssim \frac{1}{\epsilon^{1/4}}\textsf{OPT} + \|Ax^\ast\|_p^p$ and so on. The regularization term does accumulate, but the accumulated error is still bounded by $\log$ factors and will be absorbed in the $\log$ factor in the final bound. We will make this clearer in the revised version.

• Line 397: We thank the reviewer for pointing out this confusion. This line should read "$\leq (1 + c \epsilon)2^p(n-k) + c \epsilon \|a x^\ast\|_p \approx (1 + c \epsilon)2^p n(1-2\epsilon) + c \epsilon \|a x^\ast\|_p$" by Line 377. We can rigorously express this approximation as an inequality by applying the Chernoff bound, as detailed in the appendix. We use $\approx$ here to substitute in the expectation, providing intuition of our idea.

• Line 423: There is a typo. The "$(1/\epsilon-1)^p$'' should be ``$(1/\epsilon+1)^p$''. Recall that $n = 1/\epsilon^p$. Thus, we have $n-1+(1/\epsilon+1)^p = n-1 + (1+\epsilon)^p/\epsilon^p = n-1+n(1+\epsilon)^p > 2n(1+\epsilon)$.

We thank the reviewer for the detailed comments. We would like to clarify that the main body of the paper presents only an outline of our approach, focusing on the core ideas, while the full rigorous proof is provided in the appendix. Given that rigorous proofs have been included, we do not think the paper is ''not rigorous or reproducible'' or lacks ''scientific rigor''.

We would also like to clarify that this submission focuses on the theoretical aspects of query complexity, with a particular emphasis on the $\epsilon$-dependence of query complexity. While fewer queries may suffice for certain real-world datasets, we consider this a potential direction for future work.

Below, we address the reviewer's major suggestions:

• Line 68: There is a typo. Gajjar et al. (2023b) achieved $\tilde{O}(d/\epsilon^4)$ queries, which was later improved to $\tilde{O}(d/\epsilon^2)$ by Gajjar et al. (2024).

• Line 191: The main purpose of this part (Lines 187--200) is to explain why we set the regularization parameter to be $\epsilon$. Indeed, in this equation, we would like to explain $\tau$ should be smaller than $\epsilon$. As explained in Line 193, the final guarantee has the term $\epsilon \|Ax^\ast\|_p^p$ and hence we should set $\tau$ smaller than $\epsilon$ regardless of the error term. Hence, the error term plays a minor role in this argument and we intentionally did not fully expand it. The use of regularized regression was previously employed in the work of Gajjar et al. (2024). Our submission uses the same regularized regression problem. While we could have omitted the explanation and used the regularized version as our starting point, we chose to include it for completeness.

• Equations (10) and (13): These error bounds are similar to previous work such as that of Yasuda (2024). The most novel part of this submission is the section on ``further improvement'', which enables us to obtain a near-optimal dependence on $\epsilon$ in query complexity. Therefore, we intentionally phrased them as black boxes as they are not our main contribution. We will make this clearer in the revised version.

• Extension to $d>1$ is not as difficult as $d=1$. Once the argument for $d=1$ works out, it is more or less a standard technique to extend it to $d > 1$. Hence, we presented it in a way that focuses on our main contribution, which is the case of $d=1$. The full proof for $d>1$ can be found in the appendix. We will polish the paper to improve the presentation.

Can we say that you achieve $(1+\epsilon)$-approximation with the complexity of Gajjar et al. (2024)?

Additionally, regarding (13) and "Further Improvement", is your main contribution showing how the iterative refinement of (13) results in tighter guarantees?

Your work is not experimentally rigorous, or reproducible in general, since no experiments are provided.

Similarly, it seems many approximations are given without sufficient justification, e.g., how some terms can easily be omitted without issues in the subsequent calculations. This makes the analysis (at least in the main text) lacking in rigor. You could have potentially frame your work in a more digestible manner.

Moreover, the appendix feels convoluted. There are many assumptions, for which the corresponding justifications seem to be missing. Some examples:

• Line 978: How did the error term in Corollary 16 turn into this, where is the $\epsilon$-term on the left side? Consequently, it is not clear how (27) is reached.
• Line 1058: Where is this assumption coming from?
• Line 1080: Following here, it is not clear to me how you compute $Y_i$ or how such a given $K$ exists.

Regarding Line 299, you need to carefully explain how the omitted additive and multiplicative terms accumulate with successive iterations. It is hard to see and judge in the current approximative form.

Thank you for the reply. Although, I am not fully convinced by the state of the paper, I am raising my score after considering your rebuttals.

We thank the reviewer for the comments. Below we explain the difficulty in extending the lower bound from $d=1$ to $d>1$ when $p>2$:

We first briefly summarize the constructions in (Yasuda, 2024) and our paper for $d=1$. In (Yasuda, 2024), the first hard instance gives $x^\ast=0$ and $\textsf{OPT}=0$ while the second hard instance gives $x^\ast\neq 0$ and $\textsf{OPT}\leq 1-\epsilon$. In our construction, the first hard instance gives $x^\ast=1$ and $\textsf{OPT}=2/\epsilon^p$ while the second hard instance gives $x^\ast=-1$ and $\textsf{OPT}=2/\epsilon^p$. The key difference is that Yasuda's construction is asymmetric (with one of the $\textsf{OPT}$ values being $0$) whereas our construction is symmetric.

When extending the result to the case of $d > 1$, Yasuda (2024) constructs a set $S$ of unit vectors of size $d^{p/2}$, where any two vectors in the set are almost orthogonal. The existence of such a set is shown in previous work. The asymmetry can then be exploited as follows: duplicate the first hard instance in each of these $d^{p/2}$ directions, then choose one of these instances and flip it to the second hard instance with probability $1/2$. If the chosen copy is not flipped, we have $x^\ast=0$ and $\textsf{OPT}=0$. If the chosen copy is flipped, we have $x^\ast\neq 0$ and $\textsf{OPT}\leq 1-\epsilon +\text{small error}$. This small error is negligible because the other directions are almost orthogonal to the chosen direction and the $\textsf{OPT}$ value of the first hard instance is $0$.

Unfortunately, our construction is symmetric and neither $\textsf{OPT}$ value is $0$. To extend the lower bound to $d^{p/2}$ using the set $S$ defined above, we cannot follow the same approach because of the absence of a "base" instance like the first hard instance in Yasuda's construction. This prevents us from setting all copies to be the "base" instance with a random flip on one of them, as the $\textsf{OPT}$ value is not $0$, which makes the small error mentioned above is no longer negligible.

Regarding the possibility of an asymmetric construction in our case, we found that the symmetry is crucial for improving the lower bound to $1/\epsilon^p$ when $d=1$. Therefore, we encounter this dilemma when extending the lower bound to the case of $d>1$.