We thank the reviewer for their attention to our work and the insightful questions they have raised. Below, we provide responses to each of the questions.
> **Question 1: It is not clear whether Alg. 1 is online or offline.**
Our Alg.1 is an online algorithm that takes a data point one by one, and performs learning in $O(dm)$ space complexity to output $N$, an approximate unfair subspace (see Section 3.2). Although we have shortened our pseudocode due to space constraints, the main estimators used in Alg. 1 (see Eqn. (5) in our draft) are updated in an online manner using only vector-vector additions and vector-matrix multiplications. We included the complete pseudocode of Alg.1 in Appendix B, where the reviewer can find a more clarified version of our Alg. 1.
In the offline setting, as we can fully compute $\mathbf{Q}$ and $\mathbf{f}$ from the given offline data, the unfair subspace $\mathbf{N}$ can be computed via SVD of $[\mathbf{Q} | \mathbf{f}]$, as discussed in Section 3.2. Depending on the problem setting, one can still transform an offline setting into an online setting by going through the data points one by one. This would help alleviate memory limitations or other issues, as we’ve done in our CelebA dataset experiment.
> **Question 2: Effect of the iteration number $U$ on the theorems in Section 6 and the performance of Alg. 1**
Thank you for pointing this out. Our final sample complexities (Theorem 6.3) are derived by multiplying the iteration number by the batch size for each phase, which is why there isn’t an explicit mention of the iteration number $U$ in the theorem statements; for the proof we have chosen a suitable $U$, and it is included in our Theorem 6.3. Precisely, Theorem 6.1 and 6.2 characterize the sufficient block size for ensuring small noise terms in the noisy power iterations, and Lemma 6.1 (which is taken from [8]) universally characterizes the iteration number that ensures a small final error, given that the iteration errors are small.
Let us further elaborate on the effect of the block size $b$ and the iteration number $U$ on the convergence rate of the noisy power method. With a closer look at the convergence result by Hardt & Price [8], especially their Lemma 2.2 and Theorem 2.3 (Lemma 2.3 and Theorem 2.4 of their arXiv version, resp.), the distance between the noisy power method iterates and the ground truth decays roughly as $\varepsilon + C^U$, where $\varepsilon$ scales inversely with the square root of the block size $\sqrt{b}$, $U$ is the iteration number, and $C$ is a problem-dependent quantity that depends on the singular value gap and $\varepsilon$. Thus, for a fixed block size $b$, our choice of $U$ is a minimal choice (and thus “tight”) such that the second term becomes negligible compared to the first term, resulting in the error $\varepsilon \sim \frac{1}{\sqrt{b}}$. In other words, even though $U$ is increased far beyond our choice, the final error will still be $\varepsilon$, i.e., a much higher number of iterations does not lead to an error less than $\varepsilon$.
Again, we emphasize that our choice of $U$ is *sufficient* to ensure the final error is small. In practice, a lesser iteration number may be sufficient for good performance. Indeed, for our CelebA dataset experiments and additional UCI/synthetic dataset experiments, we have observed that a moderate number of iterations (10~20) is enough.
For completeness, lastly, we provide here the precise form for the iteration number in Alg. 1 (For the notation, please refer to Assumption 6.2.):
$$ U = O\left(\frac{\nu_m}{\nu_m-\nu_{m+1}}\log\frac{d}{\epsilon\delta}\right) = O\left(\frac{K_{m,\nu}}{\Delta_{m,\nu}}\log\frac{d}{\epsilon\delta}\right) $$
We hope these responses resolve the reviewer’s concerns, and we are happy to answer any more questions or concerns that the reviewer may have.