GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
For distributed computing environment, we consider the empirical risk minimization problem and propose a distributed and communication-efficient Newton-type optimization method. At every iteration, each worker locally finds an Approximate NewTon (ANT) direction, which is sent to the main driver. The main driver, then, averages all the ANT directions received from workers to form a Globally Improved ANT (GIANT) direction. GIANT is highly communication efficient and naturally exploits the trade-offs between local computations and global communications in that more local computations result in fewer overall rounds of communications. Theoretically, we show that GIANT enjoys an improved convergence rate as compared with first-order methods and existing distributed Newton-type methods. Further, and in sharp contrast with many existing distributed Newton-type methods, as well as popular first-order methods, a highly advantageous practical feature of GIANT is that it only involves one tuning parameter. We conduct large-scale experiments on a computer cluster and, empirically, demonstrate the superior performance of GIANT.
severely limited bandwidth and high latency. As a result, it is imperative to reduce the communications between the center and a node or between two nodes. In such settings, the preferred methods are those which can perform expensive local computations with the aim of reducing the overall communications across the network.
Optimization algorithms designed for distributed setting are abundantly found in the literature. Firstorder methods, i.e, those that rely solely on gradient information, are often embarrassingly parallel and easy to implement. Examples of such methods include distributed variants of stochastic gradient descent (SGD) [17,27,47], accelerated SGD [35], variance reduction SGD [10,28], stochastic coordinate descent methods [5,13,20,31] and dual coordinate ascent algorithms [30,43,46]. The common denominator in all of these methods is that they significantly reduce the amount of local computation. But this blessing comes with an inevitable curse that they, in turn, may require a far greater number of iterations and hence, incur more communications overall. Indeed, as a result of their highly iterative nature, many of these first-order methods require several rounds of communications and, potentially, synchronizations in every iteration, and they must do so for many iterations. In a computer cluster, due to limitations on the network's bandwidth and latency and software system overhead, communications across the nodes can oftentimes be the critical bottleneck for the distributed optimization. Such overheads are increasingly exacerbated by the growing number of compute nodes in the network, limiting the scalability of any distributed optimization method that requires many communication-intensive iterations. To remedy such drawbacks of high number of iterations for distributed optimization, communicationefficient second-order methods, i.e., those that, in addition to the gradient, incorporate curvature information, have also been recently considered [16,36,29,45,7,15,38]; see also Section 1.1.
The common feature in all of these methods is that they intend to increase the local computations with the aim of reducing the overall iterations, and hence, lowering the communications. In other words, these methods are designed to perform as much local computation as possible before making any communications across the network. Pursuing similar objectives, in this paper, we propose a Globally Improved Approximate NewTon (GIANT) method and establish its improved theoretical convergence properties as compared with other similar second-order methods. We also showcase the superior empirical performance of GIANT through several numerical experiments.
The rest of this paper is organized as follows. Section 1.1 briefly reviews prior works most closely related to this paper. Section 1.2 gives a summary of our main contributions. The formal description of the distributed empirical risk minimization problem is given in Section 2, followed by the derivation of various steps of GIANT in Section 3. Section 4 presents the theoretical guarantees. The most commonly used notation is listed in Table 1. Due to the page limit, the readers can refer to the long version [41]; Section 5 provides a summary of our experiments. The proofs can be found in the long version [41].
The paper introduces GIANT, a distributed variant of Newton algorithm. The considered problem is important and the paper gives a nice contribution to the field of distributed optimisation. The paper is very clear and nice to read, and propose nice theoretical contributions and experiments, with a detailed bibliography and positioning with respect to priori work.  Here is my main criticism :  * Authors acknowledge that their approach is close to previous works, namely DANE, for which GIANT seem to coincide to DANE in the least-squares loss case. However, the rate obtained in the paper is much better, certainly thanks to the introduction of the incoherence assumption, which is well known in the field of compressed sensing and randomized linear algebra. I think that the paper would benefit from a more thorough comparison of approaches, and to what extent this row-coherence assumption is reasonable in practical assumptions. It would help also to understand where the gap between the rate of GIANT and DANE comes from, if it is either related to the different set of assumptions, or if it comes from an alternative proof technique.  * The numerical experiments are a bit disappointing. It proposes a comparison to good baselines, but on  medium scale datasets (epsilon, covertype) and then on larger datasets, constructed as extensions of cover type. Many large or huge datasets for binary classification are available : it would be really interesting and more transparent to see the performances of these distributed optimisation algorithms for more realistic problems, for which feature matrices are really different. Indeed, considering different simulation setups for features hardly accounts for the variability of features in realistic problems. Indeed, the process of augmentation of the cover type dataset is probably helping with the incoherence, since it consists in row duplications with small Gaussian noise and features are augmented with random Fourier features. Furthermore, no experiments / guarantees for sparse features matrices are provided. In big data setting, with very large n / large d, features are typically sparse (word counts for instance)  In summary, I like the paper and think that it deserves to be published, but I won't be shocked if it is not. I sincerely believe that it can be strongly improved by an extension of the experiments to several real-world large scale datasets, that are now commonly available in kaggle or UCI platforms.