NIPS 2018
Sun Dec 2nd through Sat the 8th, 2018 at Palais des CongrĂ¨s de MontrĂ©al
Paper ID: 1817 Communication Efficient Parallel Algorithms for Optimization on Manifolds

### Reviewer 1

This paper develops parallel algorithms in a manifold setting. For doing this, this paper uses Iterative Local Estimation Algorithm with exponential map and logarithm map on a manifold. They show the upper bound for the loss under some regularity conditions. They also verify their algorithm on simulated data and real data. In terms of quality, their method is both theoretically and experimentally verified. Their theoretical analysis is sound with the concrete assumptions and bound for the loss. In terms of clarity, this paper is clearly written and well organized. Introduction gives good motivation for why parallelization on optimization algorithm on a manifold is important. In terms of originality, adapting parallel inference framework in a manifold setting is original and new as I know. References for parallel inference framework are adequately referenced. In terms of significance, their method enables to parallelize inference on manifolds, which is in general difficult. Their theoretical analysis gives an upper bound for the loss with high probability. And their experimental results also validate the correctness of their algorithms. I, as the reviewer, am familiar to differential geometry on manifolds but not familiar to parallel optimizations. And I also have some minor suggestions in submission: Submission: 66th line: D is the parameter dimensionality: shouldn't D be the data space? 81th line: 2nd line of the equation is not correct. It should be 1/2 < theta-bar{theta}, (Hessian L_1(bar{theta}) - Hessian L_N(bar{theta})) (theta-bar{theta}) > or something similar to this. 118th line: In R_{bar{theta}_1} t R_{bar{theta}_1} theta_2, bar should be removed. 123th line: log_{bar{theta}}^{-1} theta -> log_{bar{theta}} theta 146th line: L' should be appeared before the equation, something like "we also demand that there exists L' in R with (math equation)" 229th line: aim extend -> aim to extend ------------------------------------------------------------------------------- Comments after Author's Feedback I agree to Reviewer 4 to the point that the authors need to provide better motivations for how the process communication becomes expensive in for the optimization on manifolds. But I am convinced with the author's feedback about the motivation and still appreciates their theoretical analysis of convergence rates, so I would maintain my score.

### Reviewer 2

1. In line 113, what is R_{\theta}? 2. In line 117, it should be triangle inequality not triangular. 3. In line 126, addictive--> additive. 4. Inverse retraction map is called lifting. Also, please mention the radius of the regular geodesic ball inside which retraction map is a bijection. 5. In line 169, please bold x_is and bold S in hypersphere. 6. Eq. (2) is FM iff \rho is geodesic distance. 7. In line 177, what is 'big circle distance', should be arc length. 8. The fastest state-of-the-art FM estimator algorithm on hypersphere is by Chakraborty et al. in MFCA 2015. Please comment on performance improvement compare to this online algorithm. Overall, though the idea is nice, I believe it mostly depends on the previous theorem (Thm. 1). Experimental section lacks comparison with the state-of-the-art. Needs proof reading and significant corrections with notations, technical content. ---------------------------------------------------------------------------------------------- POST REBUTTAL COMMENTS: The authors did a decent job with the rebuttal. My comments are successfully addresses (more-or-less). I was though concern about the motivation after reading R4's reviews, my opinion is authors did a good job there as well. I agree that minimizing the exact loss function is not feasible, hence the solution proposed is well motivated after reading the rebuttal. So, in summary, I vote for acceptance and am going to increase my vote to a 7 assuming that authors will do a check for correctness of the technical content, notations etc..