Communication Efficient Parallel Algorithms for Optimization on Manifolds
The last decade has witnessed an explosion in the development of models, theory and computational algorithms for "big data" analysis. In particular, distributed computing has served as a natural and dominating paradigm for statistical inference. However, the existing literature on parallel inference almost exclusively focuses on Euclidean data and parameters. While this assumption is valid for many applications, it is increasingly more common to encounter problems where the data or the parameters lie on a non-Euclidean space, like a manifold for example. Our work aims to fill a critical gap in the literature by generalizing parallel inference algorithms to optimization on manifolds. We show that our proposed algorithm is both communication efficient and carries theoretical convergence guarantees. In addition, we demonstrate the performance of our algorithm to the estimation of Fréchet means on simulated spherical data and the low-rank matrix completion problem over Grassmann manifolds applied to the Netflix prize data set.
The rebuttal letter of the authors carefully considered my remarks, committed to fix some of the issues, while deferred some more substantial work to the future. I am pleased to accept the manuscript after having read the perceptive rebuttal letter, which addressed most of my considerations. To me, the most fundamental issue is that some of the assumptions made in the paper don't hold in contemporary distributed computing systems, but I am open to accept the paper in terms of its theoretical contribution.  This paper builds upon and extends the iterative local estimation algorithm (ILEA) in two ways. Firstly, this paper allows optimization to take place on a different machine between iterations. Secondly, the more general so-called retraction map is used in place of the exponential map. Ultimately, the goal of the paper is to scale global optimization in a parallel fashion while exploiting the geometry of the parameter space.  The paper aims at addressing the important problem of scalable parallel optimization and takes reasonable steps towards this aim. At the same time, there are several points to consider attentively towards the proclaimed aim: 1.1) It is not entirely clear to me for which parallel architecture the algorithm is designed. Is the goal to use the algorithm for high performance computing or for distributed or cloud computing? On the basis of lines 31-33, it seems to me that the authors have designed the algorithm for low latency distributed frameworks, such as Hadoop or Spark. If this is the case, low latency is not the only design principle for a scalable distributed algorithm. It is also important that the algorithm is designed keeping in mind that it is meant to work on data management layers, such as HDFS and YARN. Thus, the assumption made in lines 63-65 about IID observations across different machines is not aligned with the reality of batch and real-time data workloads provided by YARN. In more statistical terms, online learning problems can't be based on IID distributed data across nodes, and in general the users, developers or engineers don't manage cloud computing at so low-level so as to align data allocation according to such an IID assumption through time. 1.2) Along the lines of the above remark, it is not mentioned in the examples which parallel framework was used for running the proposed algorithm. Did you use an implementation of the message passing interface (MPI) or the actor model in Akka for instance? You may provide more information about these matters in section 5 (simulation study). 1.3) The first example is based on a sphere. Given that the Betti number of a sphere is zero, this example does not provide a geometrically challenging parameter space. It would be useful to use a more challenging manifold. 1.4) The algorithm is also ran on Netflix data. The issue here is that there is no absolute RMSE to compare the proposed algorithm to other established optimization methods. The landmark paper on optimization 'Lipschitzian optimization without the Lipschitz constant' by Jones, Perttunen and Stuckman, journal of optimization theory and application, 1993, provides nine test functions for benchmarking optimization algorithms, see Table 1 and equation (12) in Jones' paper. To get an idea of how well your proposed algorithm works, I suggest you run it on these benchmark functions and you tabulate the results along with the analogous results for other standard optimization methods. 1.5) You mention in lines 35-36 that your goal is to address challenges arising from inference on big non-Euclidean data or data with non-Euclidean parameters. Since you define the manifold M in the parameter space in lines 104-105, my understanding is that the paper addresses only the latter case (data with non-Euclidean parameters), so I would suggest you drop the reference to the former case (big non-Euclidean data) from lines 35-36.  Some minor fixes are proposed below: 2.1) Line 18: Change 'include diffusions matrices' to 'include diffusion matrices'. 2.2) Line 30: A useful paper missing from the list of relevant references you provide in line 30 is the following, 'Merging MCMC subposteriors through Gaussian-process approximations' by Nemeth and Sherlock. 2.3) Line 66: It is mentioned that calligraphic D refers to the parameter dimensionality. If not mistaken, calligraphic D refers to data rather than parameters in your paper? 2.4) Lines 71-72: You may want to rephrase this sentence, there seems to be unintended repetition of the point about communication. 2.5) Lines 104-105: The symbols d and M appear in lines 104-105 for the first time if not mistaken. State more explicitly here that d is the dimension of the parameter space and that the manifold M lives in the parameter space. It can be deduced by reading carefully, yet it would help the reader to state this more directly. 2.6) Line 117: The notation d_{R} has not been introduced. It can be guessed that d_{R} is a metric given that you refer to the triangular inequality, yet it would be helpful to introduce notation more explicitly. 2.7) Line 126: Change 'the addictive constant' to 'the additive constant'. 2.8) Lines 134-135: It is not clear to me what 'population risk' means. Do you mean 'global risk'? 2.9) From line 150 onwards, you use three vertical lines instead of two; do the three vertical lines refer to a norm different than the norm represented by two vertical lines? If this is not a typo, introduce the relevant notation (unless of course you have already explain this in the paper and it eluded me). 2.10) In equation (3), you introduce the symbol 'W'. Does W_{ij} denote a binary variable indicating the presence or absence of an edge between the i-th movie and j-th user? Introduce the notation W_{ij} and its possible relation with the symbol w_k appearing right before line 203.