Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed a communication efficient distributed algorithm to compute the leading eigenvector of a covariance data matrix where the rows of the matrix are distributed on multiple nodes. They presented a distributed Riemannian gradient descent to compute the leading eigenvector and avoid projection onto constraint operation. To prove the convergence of Riemannian gradient descent, they first derive the weakly-quasi-convex property of the objective.  A quantization scheme is also proposed to save communication costs. Finally, they proved the convergence of the algorithm, and the communication complexities for different initialization schemes.

main_review: Distributed eigenvector estimation is important in many distributed ML algorithm's implementation, and communication cost is also a pain point in distributed learning. This paper, for the first time, tackles these two aspects together. Using Riemannian gradient descent to optimize manifold-constrained problems is a popular idea, and so is the quantized idea to save communication cost. The authors are the first to combine these ideas and apply them to distributed PCA. The structure of this paper is clear and easy to follow. I believe a reader without prior knowledge can follow this paper. The paper is well-organized and the presentation of the theorem/lemma is clear. 

limitations_and_societal_impact: 1. For the quantization algorithm, it will be great if the authors can give the explicit mapping rule in the main paper, since the readers may not be familiar with lattice quantization. 

2. I would like the authors to discuss the relation between this work and federated PCA [Grammenos, Andreas, et al.19], where they also consider data matrix is distributed on different nodes.
 

3. I would like to see some experiments on the effectiveness of this algorithm, so that we can see how the quantization idea improves the communication cost compared to the non-quantized version.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper considers the problem of distributed computation of the leading eigenvector of a data covariance matrix. To solve this problem, a distributed variant of Riemannian gradient descent is proposed. Convergence is proven and an upper bound is given on the number of bits that need to be transmitted to estimate the leading eigenvector. Finally, the dependency of the method on its initialization is analyzed.

main_review: Originality:

The paper presents a novel algorithm for the computation of the leading eigenvector of a covariance matrix, as it is done in principal component analysis. The paper fills a gap in the literature since compared to previous approaches, the proposed technique is specifically designed to minimize the bandwidth cost, i.e. the number of bits transmitted between the nodes. The main contribution of the paper is the theoretical analysis of the approach, in particular the convergence is proven and a bound on its communication complexity is given.

Quality: 

The derivation of the algorithm is technically sound, and the authors show theoretically that the approach is indeed communication efficient. However, there is no experimental evaluation of the approach. For a paper proposing a novel algorithm, I would expect at least some experiments that show its usefulness in practice. Moreover, while the approach is motivated by the application to principal component analysis, the paper only focuses on computing the first eigenvector, while in practice typically multiple eigenvectors are required.

Clarity: 

The paper is clearly written and well-organized. However, as stated above, a section containing the experimental validation of the approach as well as details on the implementation are missing.

Significance:

Due to the ever increasing amounts of data, coming up with novel distributed algorithms is a worthy goal. As such, the paper makes an important contribution to the field, in particular since it is specifically designed to be efficient in terms of communication complexity. Moreover, the distributed variant of Riemannian gradient descent may turn out to be useful in different contexts. On the other hand, the paper appears to be incomplete as it lacks any sort of experimental evaluation. Moreover, for the approach to be adopted for PCA it should be extended to compute multiple eigenvectors of the covariance matrix.


Post Rebuttal:

My main concern was the lack of experimental evaluation, which was addressed by the authors in their rebuttal. I have therefore increased my score.
limitations_and_societal_impact: The authors discuss limitations of the work in the last section of the paper. Since this is a methodological contribution, there is no direct societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies the problem of finding the leading eigenvector in a distributed setting, where the $i$-th worker holds $m_i$ pieces of local data and the goal is to find the leading eigenvector of the global covariance data matrix while minimizing the total communication cost. Unlike most of the previous results that largely focus on round complexity, this paper considers bit complexity. 

The proposed algorithm is a combination of the Riemannian gradient descent over an $\ell_2$ sphere and the vector quantization method based on Davies et al. (2021). The main technical contribution of this paper is showing a "strong-weak-convexity" result of the quadratic function $-x^TAx$ over a Riemannian manifold, which resolves a technical issue in Huang et al. (2020).  
main_review: Though this paper fixes a technical issue in the previous work Huang et al. (2020),  I do feel the novelty is rather limited since both the Riemannian gradient descent and the vector quantization technique are well-studied before. In addition, I have the following concerns/suggestions:

1. The comparison with prior works can be improved. For instance, although previous works mainly focus on the round complexity, one can apply standard vector quantization techniques to convert the round complexity to the bit complexity. The authors should compare their proposed scheme with this baseline. 


2. Following the previous point, to study the round complexity of the proposed scheme, one can check in how many iterations the Riemannian terminates. However, in the Algorithm section (Page 6) the authors did not specify the stopping criteria.


3. The final bit complexity involves a term $\gamma$ (which is defined as $n\max \lambda_i$). To better compared with other results, the authors can show how it scales as a function of $n, b$ under the i.i.d. setting (and perhaps assume $m_i = m$).


4. An experimental result to verify the proposed scheme would highly strengthen the paper.


5. The presentation can be improved. For instance, in the main body, several important definitions that appear in the appendix are referenced. Some of them should be moved to the main paper. Also, the algorithm section on Page 6 can be made more concise.


6. A minor typo in line 77: $A = \sum_{i}^n M_i^TM_i$ instead of  $\sum_{i}^d M_i^TM_i$.



limitations_and_societal_impact: The authors have listed the limitations as part of future works. This work does not present any foreseeable societal consequences due to its theoretical nature.
review_title: null

Meta-review: All reviewers support acceptance for the contributions on communication-efficient distributed PCA and the theoretical aspects of the proposed approach. I also recommend acceptance. However, please make sure to incorporate experimental results in the final version to validate the theoretical findings. A discussion on how to compute multiple eigenvectors would also strengthen the paper.
Decision: Accept (Poster)