{'fraction_non_alphanumeric': 0.04197605282625969, 'fraction_numerical': 0.01391895224265008, 'mean_word_length': 4.363409257898604, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
LocalNewton: Reducing Communication Bottleneck for Distributed Learning

To address the communication bottleneck problem in distributed optimization within a master-worker framework, we propose LocalNewton, a distributed second-order algorithm with local averaging. In LocalNewton, the worker machines update their model in every iteration by finding a suitable second-order descent direction using only the data and model stored in their own local memory. We let the workers run multiple such iterations locally and communicate the models to the master node only once every few (say L) iterations. LocalNewton is highly practical since it requires only one hyperparameter, the number L of local iterations. We use novel matrix concentration-based techniques to obtain theoretical guarantees for LocalNewton, and we validate them with detailed empirical evaluation. To enhance practicability, we devise an adaptive scheme to choose L, and we show that this reduces the number of local iterations in worker machines between two model synchronizations as the training proceeds, successively refining the model quality at the master. Via extensive experiments using several real-world datasets with AWS Lambda workers and an AWS EC2 master, we show that LocalNewton requires fewer than 60% of the communication rounds (between master and workers) and less than 40% of the end-to-end running time, compared to state-of-the-art algorithms, to reach the same training~loss.


Introduction
An explosion in data generation and data collection capabilities in recent years has resulted in the segregation of computing and storage resources. Distributed machine learning is one example where each worker machine processes only a subset of the data, while the master machine coordinates with workers to learn a good model. Such coordination can be time-consuming since it requires frequent communication between the master and worker nodes, especially for systems that have large compute resources, but are bottlenecked by communication costs. Communication costs in distributed optimization can be broadly classified into two types-(a) latency cost and (b) bandwidth cost [1,2]. Latency is the fixed cost associated with sending a message, and it is generally independent of the size of the message. Bandwidth cost, on the other hand, is directly proportional to the size of the message. Many recent works have focused on reducing the bandwidth cost by reducing the size of the gradient or the model to be communicated using techniques such as sparsification [3,4], sketching [5,6] and quantization [7][8][9][10][11]. Schemes that perform inexact updates in each iteration, however, can increase the number of iterations required to converge to the same quality model, both theoretically and empirically [3,12]. This can, in turn, increase the total training time in systems where latency costs dominate bandwidth costs.
One setting where latency costs may outweigh bandwidth costs is federated learning, where the computation is performed locally at the mobile device (which is generally the source of the data) due to a high-cost barrier in transferring the data to traditional computing platforms [6,13]. Such mobile resources (e.g., mobile phones, wearable devices, etc.) have reasonable compute power, but they can be severely limited by communication latency (e.g., inadequate network connection to synchronize frequent model updates). For this reason, schemes like Local Stochastic Gradient Descent (Local SGD) have become popular, since they try to mitigate the communication costs by performing more local computation at the worker machines, thus substantially reducing the number of communication rounds required [14].
These trends suggest that optimization schemes that reduce communication rounds between workers are highly desirable. In this paper, we go one-step forward-we propose and analyze a second order method with local computations. Being a second order algorithm, the iteration complexity of LocalNewton is inherently low. Moreover, its local nature further cuts down the communication cost between the worker and the master node. To the best of our knowledge, this is the first work to propose and analyze a second order optimization algorithm with local averaging.
Additionally, in this paper, we introduce an adaptive variant of the LocalNewton algorithm, namely Adaptive LocalNewton. This algorithm chooses the number of local iterations adaptively at the master after each communication round by observing the change in training loss. Thus, it further refines the iterates obtained through LocalNewton by adaptively and successively reducing the number of local iterations, thereby improving the quality of the model updates. Furthermore, when the number of local iterations, L, reduces to 1, Adaptive LocalNewton automatically switches to a standard second order optimization algorithm, namely GIANT, proposed in [22].
In Sec. 4, we show that the iterates of LocalNewton converge to a norm ball (with small radius) around the global minima. From this point of view, we may think of LocalNewton as an initialization algorithm, rather than an optimization one; since it takes the iterates close to the optimal point in only a few rounds of communication. After reaching sufficiently close to the solution point, one may choose some standard optimization algorithm to reach to the solution. In Adaptive LocalNewton, we first exploit the fast convergence of LocalNewton (L ě 1), and afterwards, when L " 1, Adaptive LocalNewton switches to the standard optimization algorithm (e.g., GIANT [22]).
Our contributions. Inspired by recent progress in local optimization methods (that reduce communication cost by limiting the frequency of synchronization) and distributed and stochastic second order methods (that use the local curvature information), we propose a local second-order algorithm called LocalNewton. The proposed LocalNewton method saves on communication costs in two ways. First, it updates the models at the master only sporadically, thus requiring only one communication round per multiple iterations. Second, it uses the second-order information to reduce the number of iterations, and hence it reduces the overall rounds of communication.
Important features of LocalNewton include: 1. Simplicity: In LocalNewton, each worker takes only a few Newton steps [23] on local data, agnostic of other workers. These local models are then averaged once every Lpě 1q iterations at the master node.
2. Practicality: Unlike many first-order and distributed second-order schemes, Local-Newton does not require hyperparameter tuning for step-size, mini-batch size, etc., and the only hyperparameter required is the number of local iterations L. We also propose Adaptive LocalNewton, an adaptive version which automatically reduces L as the training proceeds by monitoring the training loss at the master.
3. Convergence guarantees: In general, proving convergence guarantees for local algorithms is not straightforward. Only recently, it has been proved [24] that local SGD converges as fast as SGD, thereby explaining the well-studied empirical successes [6]. In this paper, we develop novel techniques to highlight the convergence behaviour of LocalNewton. 4. Reduced training times: We implement LocalNewton on the Pywren framework [19] using AWS Lambda 1 workers and an AWS EC2 2 master. Through extensive empirical evaluation, we show that the significant savings in terms of communication rounds translate to savings in running time on this high-latency distributed computing environment. 5. Adaptivity: We propose Adaptive LocalNewton, which is an adaptive variant of the LocalNewton algorithm. In the adaptive scheme, based on the change in function objective value, the master modulates the number of local iterations at the worker machines. This improves the quality of the model updates as discussed in detail in Sec. 3.2.
6. LocalNewton as an initialization algorithm: Since the convergence guarantees of LocalNewton (see Sec. 4) only ensure that the iterates stay in a norm ball around the minima, one may rethink LocalNewton as an initialization algorithm, rather than an optimization one. In only a very few communication rounds, LocalNewton takes the iterates very close to the optimal solution. After that, our algorithm switches to a standard second-order algorithm, GIANT [22]. Observe that Adaptive LocalNewton reaches close to the optimal training loss very quickly, when compared to schemes like Local SGD [6,24], GIANT [22] and BFGS [26].
Related Work. In recent years, schemes such as local SGD have gained popularity, as they are communication-efficient due to only sporadic model updates at the master [6,13,14,27]. Such schemes that show great promise have eluded a thorough theoretical analysis until recently, when it was shown that local SGD converges at the same rate as mini-batch SGD [24,28,29]. Similar ideas that reduce communication by averaging the local models sporadically have also been applied in training neural networks to improve the training times and/or model performance [30,31]. Apart from local first-order methods, many distributed second-order (also known as Newton-type) algorithms have been proposed to reduce communication (e.g., [32] and [33] propose second-order algorithms in a decentralized setting where communication happens over a predefined graph, and [34] proposes batchexpansion training which reduces communication in early phases of the optimization). More recently, many communication-efficient second-order methods were proposed in the centralized setting, e.g., see [22,[35][36][37][38][39][40][41][42][43]. Such methods use both the gradient and the curvature information to provide an order of improvement in convergence, compared to vanilla firstorder methods. This is done at the cost of more local computation per iteration, which is acceptable for systems with high communication latency. However, such algorithms require 1 A high-latency serverless computing platform. 2 A traditional serverful computing platform. at least two communication rounds (for averaging gradients and the second-order descent direction), and a thorough knowledge of a fundamental trade-off between communication and local computation is still lacking for these methods. Stochastic second order optimization theory has been developed recently [44][45][46], and second order implementations motivated by this theory have been shown to outperform state-of-the-art [47,48].

Problem Formulation
We first define the notation used and then introduce the basic problem setup considered in this paper.
Notation. Throughout the paper, vectors (e.g., g) and matrices (e.g., H) are represented as bold lowercase and uppercase letters, respectively. For a vector g, }g} denotes its 2 norm, and }H} 2 denotes the spectral norm of matrix H. The identity matrix is denoted as I, and the set t1, 2,¨¨¨, nu is denoted as rns, for all positive integers n. Further, we use superscript (e.g., g k ) to denote the worker index and subscript (e.g., g t ) to denote the iteration counter (i.e., time index), unless stated otherwise.
Problem Setup. We are interested in solving empirical risk minimization problems of the following form in a distributed fashion where f j p¨q : R d Ñ R, for all j P rns " t1, 2,¨¨¨, nu, models the loss of the j-th observation given an underlying parameter estimate w P R d . In machine learning, such problems arise frequently, e.g., logistic and linear regression, support vector machines, neural networks and graphical models. Specifically, in the case of logistic regression, where j p¨q is the loss function for sample j P rns and γ is an appropriately chosen regularization parameter. Also, X " rx 1 , x 2 ,¨¨¨, x n s P R dˆn is the sample matrix containing the input feature vectors x j P R d , j P rns, and y " ry 1 , y 2 ,¨¨¨, y n s is the corresponding label vector. Hence, px j , y j q together define the j-th observation and pX, yq define the training dataset.
For such problems, the gradient and the Hessian at the t-th iteration are given by respectively, where w t is the model estimate at the t-th iteration.
Data distribution at each worker: Let there be a total of K workers. We assume that the k-th worker is assigned a subset S k Ă rns, for all k P rKs " t1, 2,¨¨¨, Ku, of the n data points, chosen uniformly at random without replacement. 3 Let the number of samples at each worker be s " |S k | @ k P rKs, where s ! n in practice. Also, by the virtue of sampling without replacement, we have S 1 Y S 2 Y¨¨¨Y S K " rns and S i X S j " Φ for all i, j P rKs. Hence, the number of workers is given by K " n{s.

Algorithms
In this section, we propose two novel algorithms for distributed optimization. First, we propose LocalNewton, a second order algorithm with local averaging. Subsequently, we also propose an adaptive variant of LocalNewton. Here LocalNewton acts as a good initialization scheme that pushes its iterates close to the optimal solution in a small number of communication rounds. Finally, a standard second-order algorithm is used to converge to the optimal solution.

LocalNewton
We consider synchronous second-order methods for distributed learning, where local models are synced after every L iterations. Let I t Ď rts be the set of indices where the model is synced, that is, I t " r0, L, 2L,¨¨¨, t 0 s, where t 0 is the last iteration just before t where the models were synced.
At the k-th worker in the t-th iteration, the local function value (at the local iterate The k-th worker tries to minimize the local function value in Eq (2) in each iteration. The corresponding local gradient g k t and local Hessian H k t , respectively, at k-th worker in t-th iteration can be written as

Algorithm 1: LocalNewton
Input : Local function f k p¨q at the k-th worker; Initial iteratew 0 P R d ; Line search parameter 0 ă β ď 1{2; Number of iterations T , Set I T Ď t1, 2,¨¨¨, T u where models are synced if t P I T then // Master averages the local models Find step-size α k t using line search (Eq. (5)) 11 Update model: Let us consider the following LocalNewton update at the k-th worker and pt`1q-st iteration: wherew t " 1 K ř K k"1 w k t @ t, and α k t is the step-size at the k-th worker at iteration t. 4 Also, define the local descent direction at the k-th worker at iteration t as p k t " We can see thatw t`1 "w t´pt . Detailed steps for LocalNewton are provided in Algorithm 1.
Note thatw t is not explicitly calculated for all t, but only for t P I t . However, we will use the technique of perturbed iterate analysis and show the convergence of the sequence f pw 1 q, f pw 2 q,¨¨¨, f pw t q to f pw˚q. In the next section, we present Adaptive LocalNewton, an algorithm to adaptively choose the number of local iterations, L.

Algorithm 2: Adaptive LocalNewton
Input : Minimum decrement δpą 0q in global loss function; 1 Initialization: f prev " f pw 0 q, Number of local iterations L, Set I T Ď t1, 2,¨¨¨, T u where models are synced every L local iterations 2 for t " 1 to T´1 do // k-th worker runs LocalNewton locally to get w k t 3 Workers run Algorithm 1 4 if t P I T then // Master averages the local models if f prev´f pw t q ă δ and L ě 1 then // The global function did not decrease enough

Adaptive LocalNewton
Motivating Example (Least-squares). Let us now consider the simple example of unregularized linear least squares, i.e., the loss function at the k-th worker is f k pwq " 1 s }y k´Xk w} 2 , where y k " ry k 1 , y k 2 , . . . , y k s s J P R s and X " rx k 1 , . . . , x k s s J P R sˆd . Note that one second-order iteration (with step-size one) reaches the optimal solution, say pw k q˚" for the local loss function f k pwq at the k-th worker.
Thus, applying LocalNewton here with L ě 1 would imply that the local iterates at the k-th worker are fixed at w k t " pw k q˚while the global iterates at the master are fixed at w t " 1 K ř K k"1 pw k q˚for all t P rT s. Note thatw t ‰w˚in general, wherew˚is the optimal solution for the global problem in Eq. (1). Hence, LocalNewton (Algorithm 1) does not reach the optimal solution for unregularized least-squares. In fact, in Theorems 4.3 and 4.4, we show that running LocalNewton algorithm results in an error floor of the order 1{ ? s for any convex loss function.  In general, Local-Newton reaches very close to the optimal solution. In that region, however, the convergence rate of LocalNewton is slow. This is mitigated by using Adaptive LocalNewton which appends the LocalNewton iterations with better quality (but more expensive) updates from GIANT. Motivated from the above example, if we want to attain the optimal solution, one needs to switch to optimization algorithms which yield no error floor. One standard example of such an algorithm is GIANT ( [22]), which is a communication-efficient distributed second-order algorithm. However, for general convex functions, the convergence of GIANT requires the initial point to be close to the optimal solution. From this point of view, one can think of LocalNewton as an initialization scheme that pushes the iterates close to the solution (within a radius of Op1{ ? sq) with a few rounds of communication. Then, one can switch to the GIANT algorithm to obtain convergence to the solution point. We call this algorithm Adaptive LocalNewton, where the master modulates the value of L successively over iterations and finally switches to GIANT to obtain the final solution. The details are given in Algorithm 2.
Recall that GIANT synchronizes the local gradients and the local descent direction in every iteration [22]. Further, it finds the step-size by doing a distributed backtracking line-search requiring an additional round of communication (Sec. 5.2, [22]). Finally, the master updates the model by using the average descent direction and the obtained step-size and ships the model to all the workers. Thus, each iteration in GIANT requires three rounds of communication. This approach has compared favorably to other popular distributed second-order methods (e.g., DANE [35], AGD [50], BFGS [26], CoCoA [37], DiSCO [36]).
In Fig. 2, we compare GIANT to LocalNewton, where LocalNewton is run with 100 workers for L " 1, 2 and 3, for two datasets-w8a and EPSILON obtained from LIBSVM [25]. Note that LocalNewton converges much faster with respect to communication rounds for all the three datasets since it communicates intermittently, i.e., once every few local second-order iterations (e.g., after 3 local iterations for L " 3). Not shown here is that testing accuracy follows the same trends. Further, the quality of the final solution improves as we reduce L. However, it reaches extremely close to the optimal training loss, but it converges very slowly (or flattens out) after that.
These empirical observations further motivate Adaptive LocalNewton: a second-order distributed algorithm that adapts the number of local iterations as the training progresses and ultimately finishes with GIANT. This can be done by monitoring the objective function at the master, e.g., reduce L if the loss stops improving (or switch to GIANT if L " 1). 5 See Algorithm 2, where we provide the pseudo-code for Adaptive LocalNewton. Whenever the global function value at the master does not decrease more than a constant δ, we decrease the value of L to improve the quality of second order estimate. In this sense, Adaptive LocalNewton can be seen as providing a carefully-constructed or gradually-annealed initialization for GIANT.
Comparison with GIANT : Algorithm 2 is further motivated by the theoretical guarantees we obtain in the subsequent section. In Theorems 4.3 and 4.4 of Sec. 4, we prove the convergence of LocalNewton to the optimal solution within an error floor starting with any initial point in R d . In sharp contrast, Theorem 2 in GIANT [22], the authors convergence guarantees to the optimal solution when the current model is sufficiently close to the optimal model. From Fig. 2, we see that Adaptive LocalNewton significantly outperforms GIANT in terms of rounds of communication. Adaptive LocalNewton starts from L=3, and yellow dots in its plot denote the reduction in the value of L by one or a switch to GIANT if L " 1.

Convergence Guarantees
In this section, we present the main theoretical contributions of the paper. For this, we only consider the (non-adaptive) LocalNewton algorithm. Obtaining theoretical guarantees for Adaptive LocalNewton is kept as an interesting future work.
First, we delineate some assumptions on f p¨q required to prove theoretical convergence of the proposed method.
Assumptions: We make the following standard assumptions on the objective function f p¨q for all w P R d : 1. f i p¨q, for all i P rns, is twice differentiable.
2. f p¨q is κ-strongly convex, that is, ∇ 2 f pwq ě κI. Lemma 4.1. Let f p¨q satisfy assumptions 1-4 and 0 ă ď 1{2 and 0 ă δ ă 1 be fixed constants. Then, if s ě 4B κ 2 log 2d δ , the local Hessian at the k-th worker satisfies for all w P R d and k P rKs with probability at least 1´δ.
Proof. See Appendix A.
Step-size selection: Let each worker locally choose a step-size according to the following rule for some constant β P p0, 1{2s, where the parameter α ‹ pď 1q depends on the properties of the objective function: 6 Now, we are almost ready to prove the main theorems-Theorem 4.3 discusses the case when L " 1, and Theorem 4.4 discusses the case when L ą 1. Before that, let us state the following auxiliary lemma which is required to prove the main theorems.
Proof. See Appendix A.
We next use the result in Lemma 4.2 to prove linear convergence for the global function f p¨q. We first prove guarantees for the L " 1 case, where the models are communicated every iteration but the gradient is computed locally instead of globally contrary to previous results [22] (thus reducing two communication rounds per iteration). We then extend it to the general case of L ą 1 and show that the updates converge at a sublinear rate in that case. [L " 1 case] Suppose Assumptions 1-5 hold and the step-size α k t satisfies the line-search condition (5). Also, let 0 ă δ ă 1, 0 ă , 1 ă 1{2 be fixed constants and let Γ " max 1ďiďn }∇f i p.q}. Moreover, assume that the sample size for each worker satisfies s ě 4B κ 2 log 2dK δ , where the samples are chosen without replacement. Then, with the LocalNewton updates, tw t u tě0 , from Algorithm 1 and L " 1, we obtain 1. If s Á Γ 2 2 1 G 2 logpd{δq for G " min k }g k pw t q}, we get with probability at least 1´6Kδ, f pw t`1 q´f pw˚q ď ρ 1 pf pw t q´f pw˚qq.
2. We obtain, with probability at least 1´6Kδ, Here ρ i " p1´2κC i q, for i " t1, 2u, C 1 " p1´ qψ Proof. The proof is presented in Appendix B. Here, we provide a sketch of the proof.
1. Due to the uniform sampling guarantee from Lemma 4.1, the strong-convexity and smoothness of the global function f p¨q implies that the local function at the k-th worker, f k p¨q, also satisfy similar properties. Using this, we can lower bound f pw t q´f pw t`1 q in terms of 1 K ř K k"1 f k pw k t q´f k pw k t`1 q. 2. Apply Lemma 4.2 (that is, the result for standard Newton step) which says f k pw k t qf k pw k t`1 q ě ψ||g k t || 2 @ k P rKs. 3. Using uniform sketching argument, local gradients g k pw t q are close to global gradient gpw t q.
Some remarks regarding the convergence guarantee in Theorem 4.3 are in order.
Remark 1. The above theorem implies that for L " 1, the convergence rate of LocalNewton is linear with high probability. Choosing δ " 1{polypKq, we obtain the high probability as 1´1{polypKq.
Remark 2. We have two different settings in the above theorem. The first setting implies that provided the local gradients tg k pw t qu K k"1 are large enough, and the amount of local data s is reasonably large, then the convergence is purely linear and does not suffer an error floor. This will typically happen in the earlier iterations of LocalNewton. Note that the gradients vanish as we get closer to the optimum, which is why the setting will eventually be violated. If this happens, we move to the next setting. Remark 3. The second setting implies that, if the gradient condition and the restriction of s are violated, although the convergence rate of LocalNewton is still linear, the algorithm incurs an error floor. However, in this setting, the error floor is Op1{ ? sq, and hence it is quite small for sufficiently large sample-size, s, at each worker.
To understand the linear convergence rate of LocalNewton, we consider the following example. Assume all the workers initialize atw 0 and run LocalNewton with L " 1 for T iterations and the first setting is true (that is, }g k pw t q} ě G for all k P rKs and t P rT s). Then, from Theorem 4.3, to reach within ξ of the optimal function value (that is, f pw T q´f pw˚q ď ξ), the number of iterations T is upper bounded by . (Note the increase in sample size s by a factor of T in the logp¨q due to a union bound). The fully synchronized second order method GIANT [22] also has similar linear quadratic convergence but it assumes that the gradients are synchronized in every iteration. We remove this assumption by tracking how far the iterate deviates when the gradients are computed locally, thereby cutting the communication costs in half while still showing linear convergence (within some error floor in the most general case).
We now prove convergence guarantees for the case when L ą 1 in this algorithm.
Proof. The proof is presented in Appendix C.
Remark 4. The theorem shows that LocalNewton with high probability produces a descent direction, provided that the error floor is sufficiently small, i.e. for sufficiently large s (since η is proportional to 1{ ? s). Observe that the convergence rate here is no longer linear. In other words, we are trading-off the rate of convergence for local iterations (L ą 1).

Remark 5.
Choosing δ " 1{polypK, Lq, we get that the theorem holds with probability at least 1´1{polypK, Lq. Note that this is not restrictive since the dependence on δ is logarithmic.
While the theoretical guarantees for L ą 1 in Theorem 4.4 are not as strong as those for L " 1 in Theorem 4.3 (linear versus sublinear convergence), empirically we observe a fast rate of convergence even when L ą 1 (see Section 5 and Appendix E for empirical results). Nevertheless, to the best of our knowledge, Theorem 4.4 is the first to show a descent guarantee for a distributed second-order method without synchronizing at every iteration. Obtaining a better rate of convergence for general L, with or without error floor, is an interesting and relevant future research direction.

Empirical Evaluation
In this section, we present an empirical evaluation of our approach when solving a large-scale logistic regression problem. We ran our experiments on AWS Lambda workers using the PyWren [19] framework. AWS Lambda is a serverless computing platform which uses a high-latency cloud storage (AWS S3) to exchange data with the workers. The master is a serverful AWS EC2 machine of type m4.4xlarge which co-ordinates with the serverless workers and holds the central model during the entire training run. We ran experiments on the real-world datasets described in Table 1 (obtained from LIBSVM [25] We compare the following distributed optimization schemes for the above datasets: 1. Local SGD [24]: The workers communicate their models once every epoch, where training on one epoch implies applying SGD (with mini-batch size one) over one pass of the dataset stored locally at the worker. The best step-size was obtained through hyperparameter tuning (Table 2).

BFGS [26]
: BFGS is a popular quasi-Newton method that estimates an approximate Hessian from the gradient information from previous iterations. The step-size was obtained using backtracking line-search. The best step-size was obtained through hyperparameter tuning (Table 2).
3. GIANT [22]: A state-of-the-art distributed second order algorithm proposed in [22].  Table 1 on AWS Lambda. Both in terms of training loss and testing accuracy, Adaptive LocalNewton converges to the optimal value at least 50% faster than existing schemes.

Adaptive
LocalNewton: For all the considered datasets, Adaptive LocalNewton gradually reduces L if the loss function stops decreasing, starting from L " 3 in the first round of communication. In general, during the later stages of optimization, it switches to GIANT owing to its convergence to the optimal solution whenw t is sufficiently close to w˚. The step-size was obtained using backtracking line-search locally at each worker as described in Algorithm 1.
We also implemented the distributed second-order optimization scheme from [39] with moderate hyperparameter tuning, and observed that its performance is either comparable or worse than the baseline GIANT [22]. Hence, for clarity, we omit those results from our plots.
For all the experiments presented in this paper, we fixed the number of workers, K, to be 100. Hence, the number of samples per worker, s " n{100, for all datasets. The regularization parameter was chosen to be γ " 1{n. Note that there are several other  schemes-such as AGD [50], DANE [35] and SVRG [51]-that have been proposed in the literature for communication-efficient optimization. However, most of these schemes have been shown to be outperformed by one of Local SGD, BFGS or GIANT, and hence, we do not perform the comparison again. In Fig. 3, we plot the training loss and testing accuracy for w8a, covtype 7 , EPSILON, a9a and ijcnn1 datasets. For all the datasets considered, Adaptive LocalNewton significantly outperforms its competitors in terms of time required to reach the same training loss (or testing accuracy) on AWS Lambda. Furthermore, since the number of workers, K, is fixed and serverless platform charges are proportional to the total CPU hours, end-to-end training time is directly proportional to the costs charged by AWS for training. This is assuming that each worker roughly takes the same amount of time per iteration.
In Fig. 4, we highlight the fact that runtime savings on AWS Lambda are a direct consequence of significantly fewer rounds of communication. Specifically, to reach the same training loss, we plot the training times and communication rounds as bar plots for three datasets, and we note that savings in communication rounds results in commensurate savings on end-to-end runtimes on AWS Lambda. In Fig. 5 in Appendix E, we provide detailed plots for training losses and testing accuracies with respect to communication rounds for all the five datasets.  Step-sizes obtained using tuning for Local SGD and BFGS for several datasets Hyperparameter details: In Table 2, we provide the step-sizes for local SGD and BFGS that were obtained through hyperparameter tuning, where s " n{K, n is the number of training examples in the dataset and K " 100.

Conclusion
The practicality of second-order optimization methods has been questioned since naive ways to implement them require large compute and power storage to work with the Hessian. However, in the last few decades, trends such as Moore's law have made computation faster and memory cheaper, while improvements in communication costs have been at best marginal. These trends, combined with a flurry of efficient but approximate algorithms [15,44,45,52], have revived interest in second-order methods. In this paper, we identify and concretize the role that second-order methods-combined with local optimization algorithms-can play in reducing the communication costs during distributed training, in particular in serverless environments. Since second-order information has recently been used to develop state-of-theart methods for deep neural networks with extremely large model sizes [10,11,47,48], we expect that methods such as ours will play a significant role in motivating and designing next-generation communication-efficient algorithms for fast distributed training of machine learning models.

A Auxiliary Lemmas and their Proofs
Here, we prove the auxiliary lemmas that are used in the main proofs of the paper. (For completeness, we restate the lemma statements).
Lemma A.1. Let f p¨q satisfy assumptions 1-4 and 0 ă ď 1{2 and δ ă 1 be fixed constants. Then, if s ě 4B κ 2 log 2d δ , the local Hessian at the k-th worker satisfies for all w P R d and k P rKs with probability (w.p.) at least 1´δ.
Proof. At the k-th worker which samples S k observations from rns, the following is true by Matrix Chernoff (see Theorem 2.2 in Tropp (2011)) Ppλ Now, using the inequality logp1´ q ď´ ? 1´ for 0 ď ă 1, we get Further, utilizing the fact that ?

B Proof of Theorem 4.3
The proofs for theorems in this paper use the auxiliary lemmas in Appendix A.
Proof. The proof of the theorem is based on the following two high probability lower bounds: Case 1: where C " α ‹ βp1´ q 2M p1` q is a constant, and where C 1 is a constant (ą 0) and η " p1`b2 logp 1 δ qq b 1 s Γ. We will prove the above result shortly, but let us complete the proof of the theorem assuming that Eq. (18) and Eq. (19) are true.
Case 1 (using Eq. (18)) Invoking the κ strong convexity of the the function f we have wherew˚is the unique global minimizer of the function f . Combining the last lower bound with equation (18) we obtain f pw t`1 q´f pw t q ď p1´2κCqpf pw t q´f pw˚qq, with probability 1´δ. Also note that where the last inequality uses the definition of α ‹ from Eq. (6). The completes the proof of Theorem 3.2.
Case 2 (using Eq. (19)) Using the same steps as before, and using the condition of Eq.
It remains to prove the claim (18) and (19).

D Concentration Inequalities: With and without Error Floor
Consider a vector v P R d . We have defined the following: gpw t q " 1 n ř i g i pw t q and g k pw t q " 1 s ř iPS g i pw t q, where g i denotes the local gradient in worker machine i, and S is the random set consisting data points for machine k. Let us do the calculation in two settings:

D.1 With error floor
Here we have the error floor. Note that having an error floor is not restrictive, if we go for the adaptive variation of the algorithm, where we run GIANT for the final iterations. Since GIANT has no error floor, the final accuracy won't be affected by the error floor obtained in the first few steps of the algorithm (check if this is true).
Lemma D.1 (McDiarmid's Inequality). Let X " X 1 , . . . , X m be m independent random variables taking values from some set A, and assume that f : A m Ñ R satisfies the following condition (bounded differences ): The property described in the following is useful for uniform row sampling matrix.
We now apply the above in distributed gradient estimation. For the k-th worker machine, we have with probability 1´δ, which implies }g k pw t q´gpw t q} ď p1`c2 logp 1 δ qq with probability at least 1´δ provided }g i pw t q} ď Γ for all i P rms Writing, η " p1`b2 logp 1 δ qq b 1 s L, we succinctly write |xv, g k pw t q´gpw t qy| ď }v}}g k pw t q´gpw t q} ď η}v} with probability at least 1´δ, where η " Op1{ ? sq is small.

D.2 Without error floor
In this section, we analyze the same quantity using vector Bernstein inequality. Intuitively, we show that unless gpw t q is too small, we can overcome the error floor shown in the previous calculation. In particular, we assume that }g k pw t q} ě G.
The idea here is to use the vector Bernstein inequality. Using the notation of Appendix D.1, g k pw t q " 1 n BSS J 1, where S is appropriately defined sampling matrix. Also gpw t q " 1 n B1. For the k-th machine, g k pw t q " 1 s ÿ iPS g i pw t q, and so, g k pw t q´gpw t q " 1 s ÿ iPS pg i pw t q´gpw t qq, with |S| " s. We also have }g i pw t q´gpw t q} ď Γ`Γ " 2Γ, and E}g i pw t q´gpw t q} 2 ď 4Γ 2 . Using vector Bernstein inequality with t " 1 }g k }, we obtain P´}g k pw t q´gpw t q} ě 1 }g k pw t q}¯ď d expp´s we have, |xv, g k pw t q´gpw t qy| ď }v}}g k pw t q´gpw t q} ď 1 }v}}g k } with probability at least 1´δ.
E Plots for convergence w.r.t. communication rounds In our main paper, we skipped the plots for convergence behavior w.r.t. communication rounds due to space constraints. In Figure 5, we show the convergence of adaptive LocalNewton, GIANT, Local SGD and BFGS with communication rounds for all the five datasets considered in this paper. Again, LocalNewton significantly outperforms existing schemes by reducing the communication rounds by at least 60% to reach the same training loss.