Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies distributed PCA. Let A be the matrix of interest. Each machine has access to a local version of A_i, and the goal is to design communication-efficient algorithms to estimate the eigenspace of A. This is a classical problem, and the contribution of this paper falls into a new algorithm that is robust to outliers in A_i. It is shown that the approximation error matches a recent non-robust algorithm up to a certain additive error.
strengths_and_weaknesses: - The term `local matrix' was used in many places but its definition remains unclear. The only example was given at line 23, and a formal restriction was set out in Eq. (6). It is, however, unclear to me when (6) is satisfied under standard assumptions on the clean data.

- Theorem 1: the presentation here is too general to understand the merit. For example, the scaling of $E_{high}$ is unclear. While it can easily be upper bounded by $(\delta_r / \delta)^2$, the latter itself is unbounded. Readers have to read 4 more pages to see that it is a vanishing term (under certain conditions).

- Theorem 4 and Corollary 1: it is surprising that the failure probability does not vanish - it even grows with problem size! I guess this is the price paid to make the approximation error diminish, but overall such tradeoff is inherently making the results vacuous.

- The Algorithm 1 seems a sandwich of prior results: step 1 is borrowed from [25], step 2 is from [8], and step 3 (robust mean estimation) has been broadly studied in recent years. So what is the main technical contribution?

questions: See above. In particular, I feel it is a serious technical flaw to have a failure probability = $1/n + \log(mn)p$, which makes sense only when the problem size stays as a constant.
limitations: N/A
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Thanks for the rebuttal. It provides some clarity and I have increased my score slightly. However, as can be inferred from the rebuttal, my original assessment of algorithmic and theoretical contribution being quite limited is accurate. The existence of a CVPR paper with an inferior methodology does not warrant acceptance of a paper with limited contribution.

Regarding the spectral norm analysis, as the authors acknowledged, there is a number of papers requiring spectral norm conditions and spectral-norm based analysis. See, e.g.,

a) Steinhardt, J., Charikar, M., and Valiant, G. (2017). Resilience:
A criterion for learning in the presence of arbitrary
outliers

b) Data, D. and Diggavi, S. (2020). Byzantine-resilient SGD
in high dimensions on heterogeneous data.

c) Blanchard, P., Guerraoui, R., Stainer, J., et al. (2017). Machine
learning with adversaries: Byzantine tolerant gradient
descent. In Advances in Neural Information Processing
Systems

d) Bulusu, S., Khanduri, P., Sharma, P., and Varshney, P. K.
(2020). On distributed stochastic gradient descent for
nonconvex functions in the presence of byzantines.

and the references therein and their citations.

-----Original review
This paper proposes an algorithm for the problem of eigenspace estimation algorithm for distributed environments with arbitrary node failures. In particular, a Byzantine adversary model is chosen where a fraction of the participants may communicate arbitrary orthogonal matrices to a server where aggregation happens. The paper builds upon the existing work to put together three components that result in the proposed scheme: i) suitable reference selection, ii) alignment, and iii) robust filtering. It is shown the proposed algorithm enjoys a bounded error consisting of three additive error terms.


strengths_and_weaknesses: Strength:
1. A specialized algorithm for robust distributed eigenspace estimation and PCA.

Weakness:
1. Limited contribution and significance. Although the paper may be technically sound, the contribution seems to be a mere application of three existing components put together in a seemingly non-difficult fashion.
2. Limited experiments. The impact of changing important parameters such as the number of samples $n$ and number of nodes must be studied. Furthermore, the performance against the centralized solution must be compared and other attach mechanisms must be tested (the latter is important to test the efficacy of the robust reference selection method).
questions: 1. What is novel about putting the three components discussed in Algs 2,3,4? What are the algorithmic and theoretical challenges in doing so?
2. To me, the interesting part was the robust reference selection method discussed in Algorithm 2. It is stated that this method builds upon [25]. Could you elaborate on this and discuss the similarities and differences?
3. An iterative refinement method is discussed in [8] to limit the variance stemming from arbitrary reference selection. How does the proposed method without the robust filtering component compare with the iterative refinement method from [8]?
limitations: yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers a setting where $m$ nodes collaborate via a server to (approximately) compute the eigenspace spanned by the $r$ principal eigenvectors of a matrix $A$. Each node has access to i.i.d. samples of $A$, and the goal is to exchange information among the nodes to compute an estimate of $A$ that is "better" than what each node could compute in isolation. The key challenge tackled in the problem is the aspect of *security*: a fraction $\alpha$ of the nodes is adversarial and can act arbitrarily. The problem then is to still provide meaningful results for the estimation of $A$ that scale gracefully with the corruption fraction $\alpha$. The authors address this problem by developing a robust distributed eigenspace estimation algorithm that requires only one round of communication; rigorous convergence bounds are also established for this algorithm. 
strengths_and_weaknesses: I found the paper quite well-written in general; the main algorithmic ideas and proof techniques are explained in a very clear way. My main comments are as follows. 

*Strengths*
- Although adversarially robust distributed optimization/statistical learning has been studied in several prior works, the specific formulation considered in this paper is novel: I have not seen robust mean estimation ideas used in the context of distributed eigenspace estimation before. The analysis of the proposed algorithm is also solid, making the overall approach a meaningful contribution.

The comments I have are mainly to clarify a few issues, but nothing major. I should also point out here that I am not an expert on eigenspace estimation.

*Comments*
- Coming back to the aspect of novelty, the contribution of the paper would be further strengthened in my opinion if the authors could articulate more elaborately why their algorithmic ideas/analysis are not subsumed by the numerous prior works on Byzantine-robust distributed optimization. What exactly makes their setting different/challenging? Can't the eigenspace estimation problem also be cast as an optimization problem? What precludes this line of approach?

Right now, the authors mention in passing that the existing works on robust distributed optimization/learning typically employ iterative algorithms that require multiple rounds of communication between the master and the worker nodes. In contrast, their approach requires only one round of communication. If this is the main/only point of departure from existing literature, then it is not too convincing. Indeed, consider the paper *Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates*, Yin et al., 2018 (ref [30] in this paper). The authors in this paper do in fact study a *one-shot* robust distributed learning algorithm that requires just one round of communication with the server right at the very end. Thus, the aspect of communication-efficiency/one-shot communication is by no means unique to the eigenspace estimation problem considered in this work. In this context, I would encourage the authors to clarify distinctions relative to prior work.

- It seems that the authors consider a *batch* setting where each node $i$ already has access to multiple samples of $A$, and has been able to construct an estimate $A_i$ that is not too far off from $A$ (at least line 114 alludes to this). Would the ideas/results in this paper extend naturally to a *streaming/online* setting where nodes acquire samples of $A$ over time, and exchange information immediately via the server to compute instantaneous estimates? The challenge that I foresee here is that initially, even for the good nodes, their estimates $A_i$ may be far off from the ground truth $A$ (since they haven't acquired enough samples yet). Hence, it may be hard to separate adversarial errors from statistical errors. 

- In this work, the additional price paid due to adversarial corruption is $O(\sqrt{\alpha})$. While such an additive price is in fact unavoidable (based on lower bounds in the robust mean estimation literature), could the dependence on $\alpha$ be improved if the noise is well behaved? To be more precise, suppose the samples of $A$ seen by the good nodes are perturbed by i.i.d. Gaussian noise. In this case, recent results in the high-dimensional robust mean estimation literature reveal that one can go from $O(\sqrt{\alpha})$ to $O({\alpha})$, in terms of the dependence on the corruption fraction $\alpha$; see [R1] below. I am wondering if similar conclusions can be drawn for the eigenspace estimation problem considered here.

[R1] *All-in-one robust estimator of the gaussian mean*, Dalalyan and Minasyan, Annals of Statistics, 2022.

- On a final note, is Algorithm 2 and its analysis in Proposition 1 new? How does the analysis compare with that in Ref [25]?


----------------------------------------------- **Post Rebuttal**  ---------------------------------------------

I thank the authors for the rebuttal. I have read through the authors' responses to both my questions, and the questions raised by the other Reviewers. I think the authors have done a good job highlighting the non-trivial aspects of both the algorithm design and the analysis. In particular, my own opinion is that an approach **should not be penalized** just because it combines/builds on existing algorithmic ideas. There is considerable credit in piecing together existing ideas in a meaningful way, and providing concrete theoretical statements to back up the developed theory - the paper under review falls in this category. As such, I have increased my score. 

questions: I have no further questions beyond the clarifying questions I posed earlier. 
limitations: I do not see any negative societal impacts of this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper develops and analyzes a decentralized algorithm for eigenspace estimation in the presence of compromised nodes. This work extends the work of (Charisopoulos et al. 2021) to the robust setting, i.e., when a fraction of the nodes send faulty responses. The most interesting contribution of the paper is the performance guarantee in the form of an upper bound on the error between the true and estimated space.   
strengths_and_weaknesses: Strengths
+ The proof is elegant and very well written. This is a solid paper. 
+ Developing a robust version of the procrustes algorithm is commended given the emergence of robust learning.
+ The ideas are compelling. In particular, (i) since a fraction of the measurements is corrupted, a reliable reference is constructed to be used for alignment by choosing the index corresponding to the smallest radius of sufficiently large balls around the received sample containing more than half of the machines; (ii) robust mean estimation is adequately used to aggregate the local versions given the presence of outliers.
+ The different ingredients of the algorithm are analyzed in a nice progression leading to a deterministic analysis, which is then used to give high probability bounds for subgaussian distributions. 

Weaknesses (most are minor)
- While the paper provides performance guarantees, the sufficient condition is loose. It requires the fraction of compromised nodes to be even smaller than 1/12. The numerical results show sustained performance even when half of the nodes are corrupted.   
- There is non-cited work on communication efficient robust PCA in the distributed setting. This is one example: 
 M. Rahmani and G. Atia, “A Decentralized Approach to Robust Subspace Recovery,” Allerton 2015.
While the approaches are different this is relevant and the claim in the Related Work section should be corrected. 
- Some symbols are never defined in the body of the theorem and the reader has to look carefully at the parameters passed to the functions in the algorithms to understand what they represent (examples: p, omega, \Sigma_G0, ...). 
- The numerical results section is a bit limited and can be improved for further validation. 
questions: * It would help to clarify where the loosness of the bound is coming from. Is it from the robust mean estimation component? You could probably add some thoughts to the discussion regarding stronger techniques to tighten the bounds. 
* Please make the theorems self-contained by defining the symbols in the statement of the theorem.
* More numerical results could be added to the supplement.  
limitations: N/A
review_title: null

Meta-review: metareview: The scores on this paper are mostly positive, with only one being below the threshold.  That reviewer was primarily concerned about novelty and significance, which is a rather subjective matter, and at least one reviewer defended the paper in this regard (and all 3 other reviews indicated it to be sufficient).  Most other concerns appear to have been generally resolved during the rebuttal period.

Even the reviewer that defended the novelty/significance did acknowledge that the presentation could be significantly improved, particularly for making clear what the paper offers compared to the existing literature.  I strongly encourage the authors to carefully consider the presentation of terminology, notation, and discussion of contributions/novelty, so that readers are able to grasp these things as easily as possible.

Overall, while the decision is not quite definite, this paper does appear to pass the bar.
confidence: Less certain
Decision: Accept