Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation
Authors: Rustem Islamov
Xun Qian
Slavomir Hanzely
Mher Safaryan
Peter Richtárik
Venue: Accepted by TMLR ()

Abstract: Despite their high computation and communication costs, Newton-type methods remain an appealing option for distributed training due to their robustness against ill-conditioned convex problems. In this work, we study communication compression and aggregation mechanisms for curvature information in order to reduce these costs while preserving theoretically superior local convergence guarantees. We prove that the recently developed class of three point compressors (3PC) of [Richtarik et al., 2022]  for gradient communication can be generalized to Hessian communication as well. This result opens up a wide variety of communication strategies, such as contractive compression and lazy aggregation, available to our disposal to compress prohibitively costly curvature information. Moreover, we discovered several new 3PC mechanisms, such as adaptive thresholding and Bernoulli aggregation, which require reduced communication and occasional Hessian computations. Furthermore, we extend and analyze our approach to bidirectional communication compression and partial device participation setups to cater to the practical considerations of applications in federated learning. For all our methods, we derive fast  condition-number-independent local linear and/or superlinear convergence rates. Finally, with extensive numerical evaluations on convex optimization problems, we illustrate that our designed schemes achieve state-of-the-art communication complexity compared to several key baselines using second-order information.

Published in Transactions on Machine Learning Research (10/2023)
Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation
Rustem Islamov
rustem. vutemmisslaoov@ippprrs
Institut Polytechnique de Paris Palaiseou, France
Xun Qian
JD Explore Academy
Beijing, China
Slavomír Hanzely
King Abdullah University of Science and Technology Thuaal, Saudi Arabia
Mher Safaryan
King Abdullah University of Science and Technology Thwwal, Saudi Arabia
Peter Richtárik
King Abdullah University of Science and Technology
Thwwal, Saudi Arabia
Reviewed OpenReview: /ttps://openreeee net/ formff id= N11BCKK111
Abstract
Despite their high computation and communication costs, Newton-type methods remain an appealing option for distributed training due their robustness against ill-conditioned convex problems. In this work, we study communication compression and aggregation mechanisms for curvature information in order to reduce these costs while preserving theoretically superior local convergence guarantees. We show that the recently developed class of three point compressors (3PC) of (Richtárik et al. 2022) for gradient communication ion can be generalized to Hessian communication as well. This result opens up wide variety of communication strategics, such as contractive compression and lazy aggregation, available our disposal to compress prohibitively costly curvature information. Moreover, discovered several new 3PC mechanisms, such adaptive thresholding and Bernoulli aggregation, which require extend
reduced communication and occasional Hessian computations. Furthermore, and analyze our approach to bidirectional communication compression and partial device participation setups to cater to the practical considerations of applications in federated learning. For all our mothods, we derive fast condition-number number--ndeeeedden local lincar and/or superlinear convergence rates. Finally, with exlensive numerical evaluations on convex optimization problems, we illustrate that our designed schemes achieve state-of- the-art communication complexity compared to several key basclines using second-order information.
1 Introduction
In this work we consider the distributed optimization problem given by the form of ERM:
min f(x) = = Σ nggd
(1)

---

Published in Transactions on Machine Learning Research (10/2023)
where d is the (potentially large) mumber of parameters of the model E Rd we aim to train, is the (potentially large) number of devices in the distributed system, (x) is the loss/risk associated with the data stored on machine i E [n] := m1, and f(z) is the empirical loss/risk.
In order to jointly train a single machine learning model using all devices' local data, collective effort are necessary from all compute nodes. Informally, each entity should invest some "knowledge" from its local "wisdom" " to create the global "wisdom". The classical approach in distributed training to implement the collective efforts was to literally collect all the raw data devices acquired and then perform the training in one place with traditional methods. However, the mere access to the raw data hinders the clients' data privacy in federated learning applications (Koncčný et al.) 2016b a McMahan et al., 2017). Besides, even if we ignore the privacy aspect, accumulating all devices" data into a single machine is often infeasible due to its increasingly large size (Bekkerman et al. 2011).
Because of these considerations, there has been a scrious stream of works studying distributed training with decentralized data. This paradigm of training brings its own advantages and limitations. Perhaps the major advantage is that each remote device's data can be processed simultaneously using local computational resources. Thus, from another perspective, we are scaling up the traditional single-device training to a distributed training of multiple parallel devices with decentralized data and local computation. However, the cost of scaling the training over multiple devices forces intensive communication between nodes, which is the key bottleneck in distributed systems.
1.1 Related work: from first-order to second-order distributed optimization
Currently, first-order optimization methods are the default options for large-scale distributed training due to their cheap per-iteration costs. Tremendous amount of work has been devoted to extend and analyze gradient-type algorithms to conform to various practical constraints such as efficient communication through
compression mechanisms (Alistarh et al.) 2017 2018b Wen et al.
2017 Wangni et al. 2018 Sahu et al. 2021
Tyurin & Richtárik 2022) and local methods Gorbunov et al. 2021b Stich 2020 Karimireddy et al.
2020
Nadiradze Ize et al.j
2021a Mishchenko et al. 2022), peer-to-peer communication through graphs (Kolos kova
et al. 2019 2020 Kovalev et al.] 2021)) asynchronous communication Feyzmahdavvan & Johansson 2021
Nadiradze et al.
2021b), partial device participation (Yang et al., 2021), Byzantine or adversarial attacks
Karimireddy et al.]
2021
2022). faster convergence through acceleration (Allen AAllnnZhhu 2017 Li al. 2020b
Qian et al. 2021
and variance reduction techniques (Lee et al.] 2017 Mishehenko et al. 2019 Horváth et al.
2019
Cen ct al.
2020
Gorbunov et al. 2021a), data privacy and heterogencity over the nodes Kairouz et al
2019
Li et al.]
2020a
Nevertheless, despite their wide applicability, all first-order methods (including accelerated ones) inevitably suffer from ill-conditioning of the problem. In the past few years, several algorithmic idcas and mechanisms to lackle the above-mentiones constraints have been adapted for second-order optimization. The goal in this direction is to enhance the convergence by increasing the resistance of gradient- methods against ill-conditioning using the knowlodge of curvature information. The basic motivation that the Hessian (local) convergence rate
computation will be useful in optimization is the fast of classic Newton's 's method (Beck) 2014), that is beyond the reach of all first-order methods.
Because of the quadratic dependence of Hessian information (d2 floats per each Hessian matrix) from the dimensionality of the problem, the primary challenge of taming second-order methods was efficient communication between the participating devices. To alleviate prohibitively costly Hessian communication,
many works such as DiSCO (Zhang & Xiao 2015 Zhuang et al., 2015 Lin et al. 2014 Roosta et al. 2019
GIANT (Wang et al., 2018 Shamir et al.) 2014 Reddi et al. 2016) and DINGO (Crane & Roossa 2019
Ghosh et al. 2020b) impart second-order information by condensing it into Hessian-vector products. Inspired from compressed first-order methods, an orthogonal linc of work, including DAN-LA (Zhang ct al.
2020b).
Quantized Newlon (Alimisis et. al. 2021), NewlonLearn (Islamov el al.) 2021 FedNL (Safaryan el al.)
2022 Basis Learn (Qian et al.) 2022) and IOS (Fabbro et al., 2022). applies lossy compression strategies
directly to Hossian matrices reducing the number of encoding bits. Other techniques that have been migratod
from first-order optimization literature are local methods (Gupta et al. 2021). partial device participation
(Safaryan et al. 2022 Qian al. 2022), defenses against Byzantine attacks (Ghosh et al. 2020a The
2

---

Published in Transactions on Machine Learning Research (10/2023)
theoretical comparison of second order methods is presented in Table literature of second-order methods to the Appendix.
I We defer more detailed review of
Table 1: Theoretical comparison of several second order methods (including ours) in strongly convex setup with Lipschitz continuous Hessians. Advantages are written in green, while limitations are colored red.
Method
grad
TipC
Comm. Cost?
Comp, Cost.
Rate
Comments
(Wang, al.
GIANT
No
O(4)
Full Hessian
Local x-depeeneent lincar. Global Olog 4/2), quadraties
Big data regime
dW
Crane Roosta
DINGO
2019:
No
((4)
Hessian-vector
products
Global linear, but no fast, local
Hessian pseudo- inverse
and vector products.
Also requires
DAN
No
O(nd*)
Full Hesslan
Global quadratic rate after O(1)))) iterations.
Zhang et al.
2020b
lim log ma Independent of is Better non-asymptotic complexity over linear rate
l=k=1
Zhang et al.
DAN-LA
2020b
Yes
((nd)
Full Hessian
Asymptotic and implicit global superlinear rate.
Local linear and superlinear independent g. but dependent on #data.
NI. 4
No
O(d)
Full Hessian
reveals local data to server
[slamoo et al.
2021
global linear
(Alimiisi et al
Quantized wton
2021
Yes
O(d))
Full Hessian
Local (fixed)
without global
NL
Local (fixed) linear and super]inear, independent
Supports contractive
Safaryan et al.
2022
No
((d)
Full Hesslan
of x and #dataa
Global linear
Bidirectional compression.
Hessian compression,
Local (fixed) linear and superlineaar, independent
Supports contractive
Qian et al.
BL
2022
No
((d)
Full Hesslan
x and #data Global linear
Ridirectional compression.
Exploits lower intrinsic
compression,
dimensionalii of data.
Fabbro et
109
2022
Yes
((4)
Full Hessian
Periodic
implicit global linear
Only tank-type
Backtracking line search.
SVD
round.
Aggafonov
FLEES
2022
Yes
((4)
Hessian-vector
products
Implicit globa] linear,
but no fast local"
Backtracking line search. SVD in each round.
Periodic
Local (fxed) linear and superlinear, independent of independent of #data.
Ncwton-3PC (this work)
Full Hessian
Suppurts contractive
((4)
and/or Hesslan-vectoo
Hessian compression,
Bidirectional compression.
products
Global rate
LipC grad Lipschitz Continuous gradients.
Comm. Cost = Communication Cost per round. Comp. Cost Computation Cost per round.
Only Generalized Linear Models, e-g. lossy (#: = dy (a, a) A||a||?
Uses Moral Smoothness: [[V' - v2) f(x]l & L|i= vl. Strongly convex local loss functions for all clients.
FLECS has local rate under the condition that all iterates remain within some fixed neighborhood of the optimum.
See Section ! in the Appoudix for globalization strategies.
2 Motivation and Contributions
Handling and taking advantage of the second-order information in distributed setup is rather challenging. As opposed to gradient-type methods, Hessian matrices are both harder to compute and much more expensive to communicate. To avoid directly accessing costly Hessian matrices, methods like DisCO (Zhang Xiao 2015), GIANT (Wang et al. 2018) and DINGO (Crane & Roosta 2019) exploit Hessian-vector products only, which are as cheap to compute as gradients (Pearlmutter) 1994). However, these methods typically suffer from data heterogeneity, need strong assumptions problem structure (e.g., generalized linear models) and/or or do not provide fast local convergence rates.
On the other hand, recent works (Safaryan et. al. 2022 Qian el al. 2022 have shown that, with the access of Hessian matrices, fast local rates can be guaranteed for solving general finite sums (1) under compressed communication and arbitrary heterogencous data. In view of these advantages, in this work we adhere this approach and study communication mechanisms that can further lighten communccation and reduce computation costs. Below, we summarize our key contributions.
3

---

Published in Transactions on Machine Learning Research (10/2023)
2.1 Flexible communication strategies for Newton-type methods
We prove that. the recently developed class of three point compressors (3PC) of Richtárik et al. (2022) for gradient communication can be generalized to Hessian communication as well. In particular, propose a method, which call Newton-3PC (Algorithm 1 extending FedNL (Safaryan et al. 2022 algorithm for arbitrary 3PC mechanism. This result opens up wide variety of communication strategies, such
contractice compression (Stich et al., 2018a Alistarh et al. 2018a Karimiroddy et al., 2019) and lazy
aggregation (Chen et al. 2018 Sun et al. 2019a Ghadikolaei et al. 2021), available to our disposal to compress prohibitielyy costly curvature information. Besides, Newton-3PC (and its local convergence theory)
recovers FedNL (Safaryan al. 2022) (when contractive compressors are used as 3PC) and BL (Qian al,
2022
(when rotation compression used as 3PC) in special cases.
2.2
New compression and aggregation schemes
Morcover, discovered several new 3PC mechanisms, which require reduced communication and occasional Hessian computations. In particular, to reduce communication costs, we design an aduplive thresholding (Example 3.3) that can be seamlessly combined with already adaptive lazy aggregation (Example 3.7 In order to reduce computation costs, we propose Bernoulli aggregation (Example 3.9 mechanism which allows local workers to skip both computation and communication local information (e.g., Hessian and gradient) with some predefined probability. Moreover, sketch-and-prope project operator (Example) 3.5 reduces the computation costs relying on Hessian-vector products.
2.3 Extensions
Furthermore, we provide several extensions to approach to cater to the practical considerations of applications in federated learning. In the main part of the paper, consider only bidirectional communication compression (Newton-3PC-BC) setup, where we additionally apply Bernoulli aggregation for gradients (worker to server direction) and another 3PC mechanism for the global model (server to worker direction). The extension for partial device participation (Newton-3PC-BC-PP) setup and the discussion for globalization are deferred the Appendix.
2.4 Fast local linear/superlinet rates
All our methods are analyzed under the assumption that the global objective strongly convex and local Hessians are Lipschitz continuous. In this sctting, derive fast condition- local linear and/or superlinear convergence rates.
2.5 Extensive experiments and Numerical Study
Finally, with extensive numerical evaluations convex optimization problems, we illustrate that our designed schemes achieve state-of-the-art communication complexity compared to several key baselines using second-order information.
3 Three Point Compressors for Matrices
To properly incorporate second-order information distributed training, we need to design an efficient. strategy synchronize locally evaluated d Hessian matrices. Simply transferring d' entries of the matrix each time it gets computed would put significant burden communication links of the system. Recently, Richtárik al. (2022) proposed new class of gradient communication mechanisms under the name three point compressors (3PC), which unifies contractive compression and lazy aggregation mechanisms into one class. Here we extend the definition of 3PC for matrices under the Frobenius norm || ||p and later apply to matrices involving Hessians.
4

---

Published in Transactions on Machine Learning Research (10/2023)
Definition 3.1 (3PC for Matrices).
We say that (possibly randomized) map + Rdddd
(x) Rdxd
Rdxd
Rdxd
(2)
He
Ye
is a three point compressor (3PC) if there ezist constants 0 < A < and B 2 0 such that
E (ICH, x s (1 A)
Y 2 + X YI
(3)
holds for all matrices H, Y, X E Rdxd
The matrices Y and H can be treated parameters defining the compressor that would be chosen adaptively. Once they fixed, CH,Y Rddd + Raxd is map to compress given matrix X. Let us discuss special cases with some examples.
Example 3.2 (Contractive compressors (Karimireddy et al. 2019 ) The (possibly randomized) map C: Rdxd + Rd is called contractive compressor with contraction parameter a E (0, if the following holds for any matria X E gdxd
E [I|((X) - X s (1 a) x
(4)
Notice that is a special case of (2) when = 0, Y = and A = a, B = 0. Therefore, contractive compressors are already included in the 3PC class. Contractive compressors cover various well known compression schemes such as greedy sparsification, low-rank approximation and (with a suitable scaling factor) arbitrary unbiased compression operator (Beznosikov et al. 2020 There have been several recent works utilizing these compressors for compressing Hessian matrices (Zhang et al.. 2020b Alimisis al.,
2021: Islamov et al. 2021 Safaryan et al. 2022 Qian et al. 2022 Fabbro et al. 2022) Below, we introduce yel her contractive compressor based thresholding idea which shows promising performance in our experiments.
Example 3.3 (Adaptive Thresholding [NEW]). Following Salu et al. 2021/ we design on adaptive thresholding operator with parameter X E (0, 1] defined as follows; for all j, E [d] and E Rdxd
X 0
if 1X X|X|oo otherwise,
[C(X)),
(5)
5 uses adaptive threshold X|||| |o> instead of fixed threshold With this choice, we ensures that at least the Top-1 is transferred. In terms of computation,
In contrast hard lhresholding operator [ahu et al. (2021
thresholding approach is more efficient than Top-K (Stich al. 2018b) as only single pass over the values is already enough instead of partial sorting.
Lemma 3.4. The adoplive thresholding operalor
is contractive with max(1 (1- (dx)² 1/8).
A popular technique to decrease computation cost of Newton-type methods is to rely on Hessian-vector products. We show that so called sketch-and-projee mechanism Gower & Richtárik 2017 is a special case of contractive compressor.
Example 3.5 (Sketch-and-Proooct (Gower & Richtárikk 2017 Let be a sketching matria sampled from a fized distribution over matrices in d (T 2 can but does not need to be fized). We define skelch-and-projeer operator follows
C(X) S(S St
(6)
For more details on skelch-and-projeed operator we refer a reader the Appendix.
Lemma 3.6. The sketch-ond, project operator 6 is a contractive compressor with A (S((SS))S))
where the expectation is taken w.r.t. randomness of the sketching S, and X (M) indicates the smallest positive eigenvalue of a symmetric matrix M.
The next two examples are 3PC schemes which in addition to contractive compressors utilize aggregation mechanisms, which is orthogonal approach to contractive compressors.
5

---

Published in Transactions on Machine Learning Research (10/2023)
Example 3.7 (Compressed Lazy AGgregation (CLAG) Richhááiik et al. 2022 ). Let C: B - Baxd
be contruclive compressor with contraction paromeler E (0, 10 and < 2 0 be Irigger for the aggregation. Then CLAG mechanism is defined as
H +CX H) if | H
c Y
CH.((X)
H
otherwise
In the special case of identity compressor C Id (i.e., a 1), CLAG reduces to lazy aggregation (Chen et al, 2018p. On the other extreme, if the trigger 0 is trivial, CLAG recovers recent variant of error feedback for contractive compressors, i.c., EF21 mechanism (Richtárik et al. 2021
Lemma 3.8 (see Lemnaa 4.3 in (Richtárik et al. 2022) ). CLAG mechanism 7 A (1- + s) and max a1 1/,).(), for any E (0, %(1-)).
is a 3PC compressor with
From the first glance, the structure of CLAG in 7 may not seem communication efficient the the matrix H (appearing in both cases) can potentially by dense. However, as we will see in the next section, CH,Y is used to compress X when there is no need to communicate H. Thus, with CLAG we either send compressed matrix C(X- H) the condition with trigger ( activates or nothing,
Example 3.9 (Compressed Bernoulli AGgregation (CBAG) [NEW]). Let C: Rdxd R be (0, and p E (0, 1] be the probability for the
contractive compressor with contraction parameter aggregation. We then define CBAG mechanism is defined as
H H C(X H) with prob. 1 - p.
with prob. p.
CH,Y(X)
(8)
H
The advantage of CBAG over CLAG is that there is no condition to evaluate and check. This choice of probabilistic switching reduces computation costs with probability 1- p it is useless to compute X. Note that CBAG has two independent sources of randomness: Bernoulli aggregation and possibly random operator C.
Lemma 3.10. CBAG mechanism S is a 3PC compressor with A = (1- (1--pa)(++)) and B = (1-pa)(1+3/o) for any s E (0, r>/(1-pa)).
Lazy aggregation communication mechanisms empirically outperform vanilla GD (Chen et al. 2018 The main idea is to communicate local gradients/ mandients/Hessians Hessians only in the case when a certain conidition holds. For example, in the case of CLAG we update local Hessian estimators only if they are sufficiently far from true local Hessians. Parameter Ç controls how often we want to skip communication. If it is large, then we reuse previous Hessian estimators more often. CLAG can be seen as an adaptive mechanism that dynaimcally updates estimators based on the conditions that change throughout the optimization process. Thus, is difficult to sstimate//pppoxxingee
how frequently skip communications.
In fact, lazy aggregation remains poorly studied field in the lilerature. It has been analysed for gradient-type methods only. However, the theoretical analysis show either explicit convergence guarantees (Sun et al. 2019b Chen et al. 2018), or sublinear rates in the strongly convex regime (Shokri Ghadikolaci et al. 2021 Recently, (Richtárik et al. 2022) have shown that LAG can be properly studied from compression point of view. They derive optimal convergence guarantees suported by emprirical evaluations. The follow-up work (Doikov et al. (023) uses similar idea in one node regime. They compute Hessian deterministically once in a/a iterations. Their thcoretical analysis also show benefits of exploiting rare updates. Nevertheless, the lazy aggregation in the case of second-order methods remains poorly studied. In our work we make a step towards better understanding of lazy aggregation for Newton-type algorithms.
For more examples of 3PC compressors see section g of Richtárik et al. (002 and the Appendix.
4 Newton-3PC: Newton's Method with 3PC
In this section we present our first Newton-type type method, called Newton-3PC, employing communication compression through 3PC compressors discussed in the previous section. The proposed method is extension

---

Published in Transactions on Machine Learning Research (10/2023)
of FedNL (Safaryan et al. 2022 from contractive compressors to arbitrary 3PC compressors. From this perspective, our Newton-3PG (see Algorithm 1 is much more flexible, offering wide variely of communication
strategies beyond contractive compressors.
4.1 General technique for learning the Hessian
The central notion in FedNL is the technique for learning priori unknown Hessian fz""") at the (unique) solution x" in a communication efficient manner. This is achieved by maintaining and iteratively updating local Hessian estimates H of fx(")) for all devices i E [n] and the global Hessian estimate H* Ex= H of (xx") for the central server. We adopt the same idea of Hessian learning and aim to update local estimates in such a way that H v=)=(²) for all i [n], and as consequence, H + v² throughout the training process. However, in contrast to FedNL, update local Hessian estimates via generic 3PC
mechanism, namely
H Cn. (((((t)))))))) (V=
which is particular instantiation of 3PC compressor (X) using previous local Hessian Y (2f((**) and previous estimate H H to compress current local Hessian X (z
Algorithm 1 Newton-3PG (Newton's method with 3PC)
Input: xº E R2d H..... . H E Rdxdd H == E H 10 = - H - [2
on server
Option 1: x = x² [H [
Option 2: zk+1 x² - H + I 'v((x))
4:
Broadcast x*+1 to all nodes
for each device Get x++1 and compute local gradient V 11 and local Hessian V fiattt)
,,...,, in parallel do
8: Apply 3PC and update local Hessian estimator to g++ CHy (((( (V2 (z(+t))))
9: Send [f(*++1),, H to the server
> the latter is sent only if H k+1 has been updated
10: Send p4+11 = | V fi(x +))
b if Option 2 used
11: end for
12: on server
13: H n Em
H
k+1 Σi 11
In the special case, when EF21 scheme CH. f=f,(t)) (V f((*+))) = H + C(V - is employed as 3PC mechanism, we recover the Hessian lcarning techmique of FedNL. Our Newton-3PC method also recovers recently proposed Basis Learn (BL) (Qian et al. 2022) algorithm if we specialize the 3PC mechanism to rotation compression (see Appendix).
4.2 Flexible Hessian communication and computation schemes.
The key novelty Newton-3PC brings is the flexibility of options to handle costly local Hessian matrices both in terms of computation and communication.
Due to the adaptive nature of CLAG mechanism 7 Newton-CLAG method does not send any in information about the local Hessian V (x* if it is sufficienlly close to previous Hessian estimate H namely [ H | < f server reuses local Hcssian estimate H while there is no essential discrepancy between locally computed Hessian V (+1x Once sufficient. change is delected by the device, only the compressed difference f( H communicated since the server knows H By adjusting the trigger Ç, we can control the frequency of Hessian communication in an adaptive manner. Together with adaptive thresholding operator ( as a contractive compressor, CLAG is doubly adaptive communication strategy that makes Newton-Cll CCAGG highly efficient in terms of communication complexity.
fi with some positive trigger Ç 0. In other words, the
7

---

Published in Transactions on Machine Learning Research (10/2023)
Interestingly enough, we can design such 3PC compressors that can reduce computational costs too. To achieve this, we consider CBAG mechanism which replaces the adaptive switching condition of CLAG by probabilistic switching according to Bernoulli random variable. Due to the probabilistic nature of CBAG mechanism, Newton-CBAG method roquires devices to compute local Hessian V fi(((*+)) and communicate compressed difference (( - ) only with probability p E 1.. Otherwise, the whole Hessian computation and communication skipped.
4.3 Options for updating the global model
We adopt the same two update rules for the global model as was design in FedNL. the server knows the strong convexity parameter μ > 0 (see Assumption 4.1), then the global Hessian estimate H projected onto the set {M pdxd; M M, م = M] to get the projected estimate [H*],. Alternatively, all devices additionally compute and send compression errors 14 = | (2fe(>>>]le (extra float from each device in terms of communication complexity) to the server, which then formulates the regularized estimate H + 1 by adding the average error 1
-
2i=1 1 to the global Hessian estimate H
4.4 Local convergence theory
To derive loca_ theoretical guarantees, consider the standard assumption that the global objective is strongly convex and local Hessians are Lipschitz continuous.
Assumption 4.1. The average loss f is j-strongly conver, and all local losses fx( have Lipschitz continuous Hessions with respect to three differrnn matrix norms: spectral, Frobenius and infovily norms, respectively. Formally, we require || V
I L-l|z-vll. IIV V f((vll S Lellz-yl1, max,,1 f(() (V)lll S Loo - yll to hold for all E [n] and x, y E Rd.
Define constants C' and D depending on which option is used for global model update, namely C = D= L if Option 1 is used, and C = 8, D = (I,, +2.)2 if Oplion 2 is used. We prove three local rates for Newton-3PC: for the squared distance to the solution ||=* x= I|?, and for the Lyapunov function
h=: H² + 6(1a+ + 33B) 12.
where H² : - H (>)()))
We present our theoretical results for local convergence with two stages. For the first stage, we derive convergence rates using specific locality conditions for model/Hessian /Hessian estimation error. In the second stage, we prove that these locality conditions are satisfied for different situations.
Theorem 4.2. Let Assumption 4.1 hold. Assume ||x - =x*1l S So and H² S fec for all k 2 0. Then, Newton-3PC 1aann3PCAAlggrttiii (Algorithm 7) with any 3PC mechanism converges with the following rales:
|| - 1=1
- SPS - 112
(9)
E [Tp]]
5 (1 - -p)* ~0, p = min (2, }
Φ0,
(10)
++1
S (11 (c+ (C= 12(1 + 3A 1 112
x+11²
AD
(11)
Clearly, these rates are independent of the condition number of the problem, and the choice of 3PC can control the parameter A. Notice that locality conditions here are upper bounds on the initial model error ||o" - x=|| and the errors HK for all k 2 0. It turns out that the latter condition may not be guaranteed in general since it depends on the structure of the 3PC mechanism. Below, we show these locality conditions under some assumptions on 3PC, covering practically all compelling cases. We highlight that the design
For discussion on global convergence guaranters we refer the Appendix
8

---

Published in Transactions on Machine Learning Research (10/2023)
of Algorithm allows to keep iterates xt and Hessian approximations H in neighbourhood of x' and f²"i(x") that is crucally important do derive local convergence guarantees. Moreover, Newton-3PC provably works with biased compression operators that are typically harder to analyze.
Lemma 4.3 (Deterministic 3PC). Let the 3PC compressor in Newton-3PC be deterministic. Assume the following initial conditions hold: ||~0 2111 c1 == min
V8(143A))L5 V2D and |HH V filx""" S 2v2
Ap
Then 1|=0 x² e1 and H fix )ll S We for all k 2 0.
Lemma 4.4 (CBAG). Consider CBAG mechanism with only source of randomness from Bernoulli aggregation.
Assume | - 111| S e2 == min{ (1-vI-a)u 1 H [ v fa("))l 1 2/C for all k 420. 0.
4vCLe V2D and | (2 S z²c Then || x²1 S e2 and
5 Extension to Bidirectional Compression (Newton-3PC-BCC
In this section, we consider the set where both directions of communication between devices and the central server are bottleneck. For this setup, we propose Newton-3PC-BC (Algorithm 2 which additionally applies Bernoulli aggregation for gradients (worker to server direction) and another 3PC mechanism for the global model (server to worker direction) employed the master.
Overall, the method integrates three independent communication schemes: workers' 3PC (denoted by CW) for local Hessian matrices V (=**t)),, master's 3PC (denoted by ) for the global model 2 and Bernoulli aggregation with probability p E (0, 1] for local gradients f(((2=-1).. Because of these three mechanisms, the method maintains three sequences of model parameters (a* wk ===k2-- Parameters x² and w server's and clients" models respectively while wh is copy of z when local gradients were last computed. Notice that, Bernoulli aggregation for local gradients is special case of CBAG (Example 3.9,, which allows to skip the computation of local gradients with probability (1-p). However, this reduction in gradient computation necessitates algo modification in order to guarantee convergence. Specifically, we design gradient estimator g*+ to be the full gradient [=(=++1) if devices compute local gradients (i.e., < 1). Otherwise, when gradient computation is skipped (i.e., & 0), we estimate the missing gradient using Hessian estimate H and stale gradient f(( namely we set g ||* wx+) f(w
Similar to the previous result, we present convergence rates and guarantees for locality separately. Let Am((A)) Bas (Bw) be parameters of the master's 's (workers') 3PC mechanisms. Define constants Cm = A +
4
1+ 5BM 2 Cw == 4 Aw +1+ 5Bw and Lyapunov function + == 1| - x=112 +Mr ||a - =11 Aar(1-p) I| x x²112.
4p
Theorem 5.1. Let Assumption holds. Assume 1|z-- - x 1|3 S
240 and H² <
Aar
AMga
for all k 2 0. 96CM
Then, Newton-3PC-BC (Algorithm converges with the following linear rate:
B < (1 min App, 1) k σ.-
(12)
Note that the above linear rate for t does not depend on the conditioning of the problem and implies linear rates for all three sequences {a*, w 2²). Next we prove locality conditions used in the theorem for two cases: for non-random 3PC schemes and for schomes that preserve certain convex combination condition. It can be seen easily that random sparsification fits into the second case.
Lemma 5.2 (Deterministic 3PC). Let Assumption 4-1 holds. Let CM and CW be deterministic. | x² 1= < 11 e3 11 min AMH² Aw AMp"
Assume 11 oz 24CM
and HO < AMp² Then 1| x=12
24CM
24Cs
L. 384C CM
96CM
l| 2 < e and H* <
Axgu² 96C for all k 0
Lemma 5.3 (Random sparsification). Let Assumption 4.1 holds. Assume (2*) is convez combination of (I=)), and (H{) is conver combination of ((V F((= ) for all E [n], j. E [d], and k: 2 0. If
|| - 12 s e = min PIZ. ZddCss
AMp? Anga
L.. 42 _ }. then x|a*- =x'1| < de and H² & min Aagu? n
90C 48
for all k 2 0.
9

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm Newton- (Newton's method with 3PC and Bidirectional Compression)
1: Parameters: Workers-side 3PC (cW), Master-side 3PC (CM), gradient probability p E (0, 1]
2: Input: xº w = 2d E R H E Rdddd and H = E H 5 = 1; -1:9² Vf(22)
3: on server
Update the global model to x²+1 = H
5: Apply Master-side 3PC and send model estimate 2 CM Sample gk+1 Bernoulli(p) and send to all i e [n] for each device = l...., in parallel do
(zlet) to all devices i E [n]
24,z
8: Get 2 = ** at (I++1) and gk+1 from the server
if ck+l =1
wh+11 = compute local gradient V.i(z*+1) and send the server
10:
if gk+1 =0
11:
wh+11 = w
12:
Apply Worker's 3PC and update local Hessian estimator to H CW
'HH (2 (H (V2St(btt1))
13:
14: end for
15: on server
vf(zk+1) E Vf((ttt)) H - E H
16:
17: if gb+1 =1
wh+1 zttl, ghttl vf(zht!)
18:
19:
if gh+t1 = 0
#+1 = wht
20:
g g+ [ In w + vf(whtl)
21:
10
10
10
10
10
Ais
20
10
2 10-11
10
10
10
10
10
10
g
10
10
gir
g
10
2'
communicated node
Communicated bits per node
communicated per
communicated node
(8) ala, A = 10
(b) w2a, 10
a9a,
w8a, = 10
1
14
16
30
141
(e) phishing, À = 10-3
(f) ala, X 10
(g) a9a, À 10-3
(h) w2a, À = 10-4
100
PORMIS
(i) phishing, 10 (i) aia, A 10
(k) a9a, A 10 30
(1) w2a, À 10
Figure Comparison of Newton-CBAA with Top-d compressor and probability p = 0.75, Newton-EF21 with Rank-1 compressor, NL1 with Rand-l compressor, and DINGO (first row). The performance of Newton-CBAG with Top-d in terms of communication complexity (second row, in Mbytes) and the number of local Hessian computations (third row).
10

---

Published in Transactions on Machine Learning Research (10/2023)
10
10
10
10 CBL ell
10
10
210 11
10
30""
10""
1015
10"1
10
2.00 11
-0""
'0"7
-0"
10
Cal eihh Naw
-3.9 uia Tap
calo ei 1pp
10-11
20
215
214 207
221
222
22
241
215
communicated bits per node
communicated bits per node
communicated bits per node
communicated bits per node
(a) a9a, À = 10-3
(b) ala, A 1071
(c) w8a, A = 10-3
(d) w2a, A 10-
10
10
-0"1
10"
10
10"1
10
10"
10
30"1
10--
10--
2-1-1
Laator
2/ communicared bits per node
Communictted bits per node
Communicated bit node
comminicated bits per node
(e) a9a, 10
(f) w2a, == 10
(g) w8a, == 10-3
(h) ala, A= 10-
30"1
10
10"
18"
2.10
200
10
10-11
9190
10
10
10
10
10
10 gli
bits per
per
(a) aia
(b) aia
(c) phishing
(d) phishing
0.5, 10
0.1,A 10
0=1.AA=
10
Figure 2: Comparison of Newton-CBAG with thresholding and Top-d compressors and Newton-EF21 with thresholding compressor in terms communication complexity (first row). Comparison of Newton-3PC-BC against FedNL-BC in terms of communication complexity (second row). The performance of Newton-CBAG combined with Top-d compressor and probability p 0.75, EF2t with Rank-1 compressor, DINGO, and Fib-ISO in terms of communication complexity Softmax problem (third row).
6 Experiments
In this part, we study the empirical performance of Newton-3PC comparing its performance against other second-order methods on logistic regression problems of the form
min 2ER4
((x))=
[(x) - E f((x)
+ + 2|101|2
(13)
where [i(x)= m Σド log (1 + exp(- exp(-begaT.at) and {aij, big yE[m) are data points belonging to i-th client. We use datasets from LibSVM library (Chang & Lin 2011). Each dataset was shuffled and split into equal parts. Detailed description of datasets and hyperparameters choice is given in the Appendix.
6.1 Comparison between Newton-3PC and other second-order methods
According to Safaryan et al. (2022) FedNL with Rank-1 compressor outperforms other second-order methods in all cases terms of communication complexity. Thus, we compare Figure 1 (first row) Newton-CBAG (based on Top-d compressor and probability p 0.75), Newton-EF21 with Rank-1, NL1 with Rand-1, DINGO, and Fib-IOS indicating how many bits are transmitted by each client in both uplink and downlink directions. We clearly see that Newton-CBAG is much more communication efficient than NL1, Fib-IOS and DINGO. Besides, it outperforms FedNL in all cases. On top of that, we achieve improvement not only in communication complexity, but also in computational cost with Newton-CBAG, Indeed, when clients do not send compressed Hessian differences to the server there is no need to compute local Hessians. Consequently, computational costs goes down. We decided not to compare Newton- 3PC with first-order methods since FedNL alrcady outperforms them in terms of communication complexity in variety of experiments in (Safaryan al. 2022
11

---

Published in Transactions on Machine Learning Research (10/2023)
6.2 Does Bernoulli aggregation bring any advantage?
Next, investigate the performance of Newton-CBAG based on Top-K. We report the results in healmaps (see Figure I second row) where we vary probability along rows and compression level K along columns. Notice that Newton-CBAG reduces to FedNL when = (left column). We observe that Bernoulli aggregation (BAG) is indeed beneficial since the communication complexity reduces when becomes smaller than 1 (in case of aia data set the improvement is significant). We can conclude that BAG leads better communication complexity of Newton-3PC over FedNL.
On top of that, we claim that Newton-CBAG. is also computationally more efficient than FedNL; see Figure (third row) that indicates the number of Hessian computations. We observe that even if communication complexity in two regimes are close to each other, but computationally better the one with smaller Indeed, in the case when < we do not have to compute local Hessians with probability - that leads to acceleration in terms of computation complexity.
6.3 3PC based on adaptive thresholding
Next we test the performance of Newton-3PC using adaptive thresholding operator (5) We compare Newton-EF21 (oquivalent to FedNL), Newton-CBAG, and Newton-CLAG with adaptive thresholding against Newton-CBAG with Top-d compressor. We fix the probability p 0.5 for CBAG, the trigger < = 2 for CLAG, and thresholding parameter X 0.5, According to the results presented in Figure 2 (first row), adaptive thresholding can be beneficial since it improves the performance of Newton-3PC in some cases. Moreover, it is computationally cheaper than Top-K K as we do not sort entries of a matrix as it is for Top-K.
6.4 Newton-3PC-BC against FedNL-BC
In our next experiment we study bidirectional compression. We compare Newton-3PC-BC against Fed For Newton-3PC-BC we fix CBAG with = 0.75 combined with Top-d compressor applied on Hessians, BAG with p = 0.75 applied on gradients, and 3PCv4 (Richtárik et al. 2022) combined with (Top-K,, Top-K2) compressors on iterates. For FedNL-BC we use Top-d compressor on Hessians and BAG with p = 0.75
on gradients, and Top-K compressor on iterates. We choose different values for K₁ and K2 such that it K1 + K₂ K always hold. Such choice of parameters allows to make the iteration cost of both methods to be equal. Based the results, we argue that the superposition of CBAG and 3PCv4 applied on Hessians and iterates respectively is more communication efficient than the combination of EF21 and EF21
6.5 Performance of Newton-3PC on Softmax problem
Finally, we also consider L2 regularized Softmax problem where all ft's of the form
f1(x) a log
ΣØ exp
a.p2- by
Here a > 0 is a smoothing parameter. One can show that this function has both Lipschitz continuous gradient and Lipschitz continuous Hessian. We perform the same data shift as it was done in (Hanzely et al. 2020 (section 8.2). Note that in this case we do not compare Newton-3PP 3PC against NL1 as this problem does not belong the class of generalized linear models.
We compare Nowton-CBAG combined with Top-d compressor and probability p 0.75, Newton-EF21 with Rank-1 compressor, DINGO (Crane & Roosta, 2019). and Fib-TOS (Fabbro et al. 2022 As we can see in Figure 2 (third row), Newton-CBAG and Newton-EF21 demonstrate almost equivalent performance: in some cases slightly botter the first one (ala datasct), in some cases - the second (phishing dataset). Furthermore, DINGO and Fib-IOS are significantly slower than Newton-3PCG methods terms of communication complexity.
References
Artem Agafonov, Dmitry Kamzolov, Rachael Tappenden, Alexander Gasnikov, and Martin Takáč. Flocs: A federated learning second-order framework via compression and sketching. arXiv preprint: arXiv
12

---

Published in Transactions on Machine Learning Research (10/2023)
2206.02002 2022.
Foivos Alimisis, Peter Davies, and Dan Alistarh. Communication--lliieen. distributed optimization with quantized preconditioners. In International Conference on Machine Learning (ICML), 2021.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Commuiccttion-fffcinn SGD via gradient quantization and encoding. In Advonces in Newral Information Processing Systems, pp. 1709 1709-1720, 2017.
Dan Alistarh, Torsten Hoefter, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In 32nd Conference Neural Information Processing Systems, 2018a.
Dan Alistarh, Torsten Hoeller, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advences in Neural Information Processing Systems, pp. 5977-5987, 2018b.
Zeyuan Allen-Zhu. Katyusha: The first direct accelcration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Compuling, pp. 1200-1205. ACM, 2017.
Amir Beck. Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB. Society for Industrial and Applied Mathematics, USA, 2014. ISBN 1611973643.
Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint Xiw:2000. 1 124 10, 2020.
Shicong Cen, Huishuai Zhang, Yuejie Chi, Wei Chen, and Tic-Yan Liu. Convergence of distributed stochastic variance reduced methods without sampling extra data. IEEE TRANSACTIONS ON SIGNAL PROCESS- ING, volume 68, 2020.
Chih-Chuna Chang and Chih-Jen Lin. LibSVM: a library for support vector machines. ACM Transoctions Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
T. Chen, G. Giannakis, T. Sun, and W. Yin. LAG: Lazily aggregated gradient for communictiion-efficieet distributed learning. Advances in Neural Information Processing Systems, 2018.
Rixon Crane and Fred Roosta. Dingo: Distributed newton-type method for gradient- optimization. In Advances in Neural Information Processing Systems, volume 32, pp. 9508, 2019.
Nikita Doikov, El Mahdi Chayti, and Martin Jaggi. Second-order optimization with lazy hessians. Proceedings of the 40th International Conference on Machine Learning, 2023.
Nicolò Dal Fabbro, Subhrakanti Dey, Michele Rossi, and Luca Schenato. A newton-type algorithm for federated learning based incremental hessian eigenvector sharing. Xix preprint arXiv: 2202.05800 2022.
Hamid Reza. Feyzmahdavian and Mikael Johansson. Asynchronous itcrations in optimization: New sequence results and sharper algorithmic guarantees. arXiv preprint arXiv:2109.0 045202 2021.
H. S. Ghadikolaei, S. Stich, and M. Jaggi. LENA: Communicaiion-elicient distributed learning with self- triggered gradient uploads. International Conferencee on Artificial Intelligence and Statistics, pp. 3943 3951. PMLR, 2021.
Avishek Ghosh, Raj Kumar Maity, and Arya Mazumdar. Distributed Newton Can Communicate Less and Resist Byzantine Workers. Advances in Neural Information Processing Systems, 2020a.
13

---

Published in Transactions on Machine Learning Research (10/2023)
Avishek Ghosh, Raj Kumar Maity, Arya Mazumdar, and Kannan Ramchandran. Communication efficient distributed approximate newton method. In 2020 TEEE International Symposium on Information. Theory (ISIT), pp. 2539 2544, 2020b. doi: 10.100//SSIT44444400000111141111
Avishek Ghosh, Raj Kumar Maity, Arya Mazumdar, and Kannan Ramchandran. Escaping Saddle Points Distributed Newton's Method with Communication Efficiency and Byzantine Resilience. arXiv preprint arXiv:2103.0944 2020c.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non-convex distributed learning with compression. arXiv preprint arXiv:2102.0755 2021a.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021b.
Robert Gower and Peter Richtárik. Stochastic dual ascent for solving lincar systems. arXiv preprint: arXiv:1512.06800 2015.
Robert M. Gower and Peter Richtárik. Randomized quasi-newton updates are linearly convergent matrix inversion algorithms. SIAM Journal on Matriz Analysis and Applications, 38(4):1380 1409, 2017.
Vipul Gupta, Avishek Ghosh, Michal Derezinski, Rajiv Khanma, Kannan Ramchandran, and Michael Mahoney. LocalNewton: Reducing Communication Bottlencek for Distributed Learning. In 37th Conference on Uncerlainly in Artificial Intelligence (UAI 2021), 2021.
Filip Hanzely, Konstantin Mishchenko, and Peter Richtarik. Sega: Variance reduction via gradient sketching.
Tn Advances in Neural Information Processing Systems, 2018.
Filip Hanzely, Nikita Doikov, Peter Richtárik, and Yurii Nesterov. Stochastic subspace cubic newton method. arXiv preprint: arXiv 2002.09526, 2020.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXio preprint (XXi::194.05110 2019.
Rustem Islamov, Xun Qian, and Peter Richtárik. Distributed second order methods with fast rates and compressed communication. International Conference on Machine Learning (ICML), 2021.
Peter Kairouz et al. Advances and open problems federated learning. arXiv preprint arXiv:1912.04p00 2019.
S. P. Karimireddy, Q. Rebjock, S. Stich, and M. Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. 36th International Conference on Mochine Learning (ICML), 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. In International Conference on Machine Learning (ICML), 2020.
Sai Pranceth Karimireddy, Lie Hc, and Martin Jaggi. Learning from History for Byzantine Robust Optimiza- tion. International Conference on Machine Learning (ICML), 2021.
Sai Pranceth Karimireddy, Lie He, and Martin Jaggi. Byzantine Robust Learning on Heterogencous Datasets via Bucketing. International Conference on Learning Representations (ICLR), 2022.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 3478-3487 PMLR, 2019.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. International Conference Learning Representations, 2020.
14

---

Published in Transactions on Machine Learning Research (10/2023)
Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. or preprint or orXi::660000222,, 2016a.
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon, Federated learning: strategics for improving communication efficiency. In NIPS Private Multi- Sulti-Party Machine Learning Workshop, 2016b.
Dmitry Kovalev, Konstanting Mishchenko, and Peter Richtárik. Stochastic Newton and cubic Newton methods with simple local linear-quadratic rales. In NewrIPS Beyond First Order Melhods Workshop, 2019.
Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi, Peter Richtárik, and Sebastian U. Stich. A linearly convergent algorithm for decentralized optimization: sending less bits for free! The 24th International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Jason D. Lee, Qihang Lin, Tengyu Ma, and Tianbao Yang. Distributed Stochastic Variance Reduced Gradient Methods by Sampling Extra Data with Replacement. Journal of Machine Learning Research, vilume 18, pages 1-43, 2017.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60 60, 2020a. doi: 10.1109/MSP:2020) 2975749.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, 2020b.
Chich Yen Lin, Cheng-Has Hao Tsai, Ching pei Lee, and Chih-Jen Lin. Large-scale logistic regression and linear support vector machines using spark. 2014 IEEE International Conference on Big Data (Big Data), pp- 519 528, 2014.
H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communiatiinn-efficee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáë, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.00 09269, 2019.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárík. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! 39th International Conference on Machine Learning (ICML), 2022.
Giorgi Nadiradze, Amirmojtaba Sabour, Peter Davies, Shigang Li, and Dan Alistarh. Asynchronous decentralized SGD with quantized and local updates. 35th Conference Neural Information Processing Systems, 2021a.
Giorgi Nadiradze, Amirmojtaba Sabour, Peter Davies, Shigang Li, and Dan Alistarh. Asynchronous decentralized SGD with quantized and local updates. Advances in Neural Information Processing Systems, 2021b.
Barak A. Pearlmutter. Fast exact multiplication ion by the hessian. Newral Compulation, 1994.
Xun Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed SGD can be accelerated. 35th Conference on Neural Information Processing Systems, 2021.
Xun Qian, Rustem Islamov, Mher Safaryan, and Peter Richtárik. Basis matters: Better communication- efficient second order methods for federated learning. In Proceedings of the 24th International Conference on Artificial Intelligence and Statislics CalalicssAASTEA (AISTATS), 2022.
Sashank Reddi, Jakub Konečný, Peter Richtárik, Barnabás Póczos, and Alexander J. Smola. AIDE: Fast and communication efficient distributed optimization. CoRR, hls/1608.0687) 2016.
15

---

Published in Transactions on Machine Learning Research (10/2023)
Peter Richtárik and Martin Takac. Stochastic reformulations of linear systems: algorithms and convergence theory. Xiv preprint: arXiv:1706.00 700.01008. 108, 2017.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. 35th Conference on Neural Information. Processing Systems, 2021.
Peter Richtárik, Igor Sokolov, Nlas Fatkhullin, Elnur Gasanov, Zhize Li, and Eduard Gorbunov. 3pe: Three point compressors for coummmication-efficeee distributed training and a better theory for lazy aggregation. 39th International Conference on Machine Learning (ICML), 2022.
Fred Roosta, Yang Liu, Peng Xu, and Michael W. Mahoney. Newton-MR: Newton's Method Without Smoothness or Convexily. arXiv preprinl or Xix:1810 0.0000, 2019.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik. FedNL: Making Newton- Type Methods Applicable to Federated Learning. 39th International Conference on Machine Learning (TCML., 2022.
Atal Narayan Sahu, Aritra Dutta, Ahmed M. Abdelmoniem, Trambak Banerjee, Marco Canini, and Panos Kalnis. Rethinking gradient sparsification as total error minimization. 35th Conference on Neural Information Processing Systems, 2021.
Ohad Shamir, Nati Srebro, and Tong Zhang. Commmication--ffiion distributed optimization using an approximate newton-type method. Proceedings of the 31th International Conference on Machine Learning, volume 32, pp. 1000-1008, 2014.
Hossein Shokri Ghadikolaci, Sebastian Stich, and Martin Jaggi. Lena: Commuicctioon-fffieett distributed learning with self-triggered gradient uploads. Proceedings of The 24th, International Conference on Artificial Intelligence and Statistics, 2021.
S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurIPS), 2018a.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations (ICLR), 2020.
Scbastian U Stich, Jean- Baptist Cordonnicr, and Martin Jaggi. Sparsified SGD with memory. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neurul Information Processing Systems 31, pp. 4452 4463. Curran Associates, Inc., 2018b.
J. Sun, T. Chen, G. Giannakis, and Z. Yang. Communcatiinn-ffiiien distributed learning via lazily aggregated quantized gradicnts. Advances in Neural Information Processing Systems, 32:3370-3980, 2019a.
Jun Sun, Tianyi Chen, Georgios Giannakis, and Zaiyue Yang. Communication-eficee distributed learning via lazily aggregated quantized gradients. In Advances in Neural Information Processing Systems, 2019b.
Alexander Tyurin and Peter Richtárik. Distributed nonconvex optimization with communication compression, optimal oracle complexity, and no client synchronization. arXiv preprinl ar Xxx::2202.01200 2022.
Shusen Wang, Fred Roosta abd Peng Xu, and Michael W Mahoncy. GIANT: Globally improved approximate Newton method for distributed optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for commuuication-efiicii distributed optimization. In Advances in Neural Information Processing Systems, pp. 1306-1316, 2018.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Newral Information Processing Systems, pp. 1509-1519, 2017.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning. International Conference Learning Represendations (ICLR), 2021.
16

---

Published in Transactions on Machine Learning Research (10/2023)
Jiaqi Zhang, Keyou You, and Tamer Basar. Distributed adaptive Newton methods with globally superlinear convergence. arXiv preprint or 0ft:2002.07778, 2020a.
Jiaqi Zhang, Keyou You, and Tamer Başar. Achieving globally superlinear convergence for distributed optimization with adaptive newton method. In 2020 59th IEFE Conference Decision and Control doi:
(CDC), pp. 2329-22222 2329-2334, 2020b.
Yuchen Zhhng and Lin Xiao. DISCO: Distributed optimization for self-concordant empirical loss. In Proceedings of the 32nd International Conference on Machine Learning, PMLR, volume 37, pages 362-370, 2015.
Yong Zhuang, Wei-Sheng Chin, Yu-Chin Juan, and Chil-Jen Lin. Distributed newton methods for regularized logistic regression. In Tru Cao, Ee-Peng Lim, Zhi-Hua Zhou, Tu-Bao Ho, David Cheung, and Hiroshi Motoda (ods.), Advances in Knowledge Discovery and Data Mining, pp. 690-703, Cham, 2015. Springer International Publishing. ISBN 978-3-319-18032-.
17

---

Published in Transactions on Machine Learning Research (10/2023)
A
Appendix
B Limitations
Here we discuss key limitations of our work and arcas that are not explored in this paper.
Developed theoretical claims are for strongly convex loss functions. The globalization mechanism with cubic regularization can be anaylized for convex functions as well, but we do not consider non-convex objectives this work.
Our methods are analyzed in the regime when the exact local gradients and exact local Hessians of local loss functions are computed for all participating devices. We do not consider stochastic gradient or stochastic Hessian oracles local loss functions our analyses. However, when we use sketch-and-proyt project operator we rely on Hessian-vector products which does not require full Hessian computations.
C Detailed Literature Review of Second-Order Methods
In this section we provide more detailed literature review of second-order methods. The comparison is made based the most relevant prior works in the literature highlighting main differences over our work. The comparison is performed based on criterias including generality of the considered problem structure, assumptions made on the (local) loss functions, commmication complexity per iteration, theoretical convergence guarantees and other aspects of the method.
GIANT (Wang et al. 2018 and NL [Islamov et al. 2021 are not designed to handle a general finite sum problem. In contrast to our work, they only work with Generalized Linear models.
Communication costs per iteration of DAN [Zhang et al. 2020a) and Quantized Newton AAlimisis eet. al.
2021 are significantly high which make them impractical.
NL [Islamov al., 2021 directly reveals local data in each iteration which breaks privacy preserving guaranlees.
The drawback of GIANT, DINGO is in their convergence rales which depend on the condition number of the problem. In some cases theoretical convergence guarantees are even worse than those of first-order methods. DANE (Shamir et al. 2014) and AIDE (Reddi et al. 2016) suffer from the same problem because those methods are first-order methods.
The first drawback of FLECS (Agafonov et al. 2022) is that SVD decomposition needed in cach step to perform truncation which means that the computation cost of those methods can not be reduced. Besides, there is good local theory for that method; the only convergence guarantee is derived under the assumption that the iterates remain close to the optimum. Next, convergence of FLECS and FLECS-SCE depend on the product of the condition number and truncation parameters. For example, using the same truncation parameters as in their experiments, the convergence guarantees are of the order 102²x, where x is the condition number. Finally, they need backtracking line search or other lcarning tochniques with additional parameters perform one step of the methods.
Fib-IOS (Fabbro et al. 2022 introduces Newton-type method based on SVD decomposition which means that similarly to FLECS the computation cost can not be reduced. Besides, this approach is also restricted to rank-type compression only, and consequently does not support popular compression techniques such as Top-K or Rand-K. On top of that, Fib-IOS always requires backtracking line search technique to find appropriate stepsize.
GIANT and DANE work well only in homogeneous setting while practice the problem could be significantly heterogencous. In our work we do not make any assumptions on heterogeneity of the problem.
18

---

Published in Transactions on Machine Learning Research (10/2023)
While convergence guarantees of FedNL (Safaryan et al. 2022 and Newton-3PG are the same (fast local linear sweear/upprlinear rates independent of the condition number) there are several points that make our work superior: (?) FedNL can be seen as special case of Newton-3PC; (ii) we provide
much wider compression mechanisms going beyond those proposed in (Safaryan et al. 2022): (idi) we propose two ways how to reduce computation costs (lazy aggregation and sketching) Newton-3PC.
D More on Sketch-and-Project Mechanism
Sketch-and-project operator has been widely studied as a technique to solve lincar systems Richtárrik & Takac 2017 Gower Richtárik 2015), an application to first-order methods (Hanzely el. al. 2018). Besides, Gower & Richtárik (2017) showed that various Quasi-Newton updates can be seen as a special case of sketch-and-projeet mechanism. Let now describe it in more details. For this reason, introduce arbitrary twice differentiable function & Rd + R. Our desire is to compute approximation of its Hessian V at point 2. Let Xo be the first approximation of (²)( Then we define a sequence {X&} that approximates V²r(z) better and better as & goes to infinity solving the following optimization problem
X == argminxeR 2 |X X
s.t. sTV'p(z)= S
(14)
where S E Rxx7 is a random matrix drawn in i.i.d. fashion from a fixed distribution D. To solve this problem we define a function vec(A) = -A11..... Ad. A12,... Adz..... Aid..... Aad)_. Morcover, we need to define an extended sketch matrix S of the form
S
0
=
ddd xdr
(15)
S
Using 15 we can reformulate 14 as follows
vec(Xx+1) = argminy - vec (x)) S veo(X) = S (vec(V>((x))
(16)
The latter has an explicit solution Hanzely et al. 2018 of the following form
vec(Xx+1) = vec(Xx) + ((vec(V2 - vec(Xx)),
(17)
where 2: Š)) It casy to show that can be rewritten as follows
Z
0
0
(18)
:
: Z
0
where = S(S S) is a projection matrix onto the range a sketch S. Since is not clear how to compute the process [7 we rewrite it explicitly as
X = X + S(S S) Xx).
The way in which the above formula is written resembles the update from (Safaryan et al. 2022
E Deferred Proofs from Section 3 and New 3PC Compressors
E.1 Proof of Lemma 3.4 Adaptive Thresholding
Basically, we show two upper bounds for the error and combine them to get the expression for a. From the definition 5 we get
|IC(X) X
Σ
X S & S &XPXI
19

---

Published in Transactions on Machine Learning Research (10/2023)
The second inequality is derived from the observation that at least entry, the top one in magnitude, is selected always. Since the top entry is missing in the sum below, we imply that the average without the top one is smaller than the overall average.
de
[I((X) X
Σ
X
X
1
X
de
jud |
1
E.2 Proof of Lemma 3.6; Bebech-aan-PProjeee
Note that since Z is projection matrix, then it is symmetric and satisfics
ZZ = S(STs)'sTS( (DSTS(STS))) S(S =
As a consequence, its eigenvalues are between 0 and 1. Assuming that X is symmetric we derive
E [[
E XX F (ZX,
x) X
E [Tr(X z 2X) E Z X X + |
= EE [(X, XX 2 2 X, + X F
| Tr E X)
S Xmin ZZ) x
Note that we can force X to be symmetric in the same way as it was done in (Qian et al. 2022 by using symmetrization operator [X, = (X++)] which does not change the theory.
E.3 Proof of Lemma 3.10: Compressed Bernoulli AGgregation (CBAG)
As was mentioned CBAG has two independent sources of randomness: Bernoulli aggregation and possible random contractive compression. To show that CBAG is a 3PC mechanism, we consider these randomness one by one and upper bound the error as follows:
E (X)) x
= (1 - p) X| + pE [||C(X H) - -X-H)
s (1 p)] H| p(1 [ H|
= (1 pa)|X 2
S (1 p1) - H) Y + - (1-pa) + 1/41| -
E.4 New 3PC:
Adaptive Top-K
Assume that in framework we restricted by the number of floats can send from clients to the server. For example, each client is able to broadcast do S d2 floats to the server. Besides, we want to use Top-K compression operator with adaptive K, but due to the aforementioned restrictions we should control how K evolves. Let KH, such that
H x H
KH,Y min
&
dd
We introduce the following compression operator
CH.Y(X) = H Top-KH.Y (X H).
(19)
The next lemma shows that the described compressor satisfy (3
Lemma E.I. The compressor Cy H 19 satisfy with
do
= max (1
dg
2d
- 1): ,3
2d
dz
do
20

---

Published in Transactions on Machine Learning Research (10/2023)
Proof. Recall that if C is Top-K compressor, then for all X
E Iddd
K d2
[[C(X) -1 S
1
X
p:
Using this property we get in the case when KY do
[C), X
H + Top- KH,
XX
H) - x
do
H
X p
d2
(1
dg
dg
2d
do
HH
Y
Y
X
2d
d2
do
If KHY
then KHHY S
H d,, x Hil
and we have
[CHY((X) - -
H +
H)
X
KH,Y
IA
H -1
d²
Y H
-
| - H|
H XI | H
3
H Y| + 3 - XI|
Y
H ?
2
Y H +3 - X
where the last inequality we use Young's inequality. Since we always have de (because do S dd), then
A
do
]
2d
E.5
New 3PC: Rotation Compression
Qian et al. (022)) proposed a novel idca to change the basis the space of matrices that allows to apply more aggresive compression mechanism. Following Section 2.3 from (Qian et al. 2022 one show that for Generalized Linear Models local Hessians can be represented Vaf((z)
Azx,()) (x),T" where Q is properly designed basis matrix. This means that Qi is orthogonal matrix. Their idea is based on the fact that A+(z) is potentially sparser matrix than fz), and applying compression on Az(x) could require smaller compression level to obtain the same results than applying compression on dense standard representation (x). We introduce the following compression based on this idea. Let C be an arbitrary contractive compressor with parameter a, and Q be an orthogonal matrix, then our new compressor is defined as follows
( = H QC (Q ( HJQ) Q
(20)
Now we prove that this compressor satisfy
Lemma E.2. The compressor CH.Q 20 based on contractive compressor with parameter E (0, 10
satisfy with A =/2 and B a) (2)))/a).
Proof. From the definition of contractive compressor
E [I((x) x1|] (1-a)) |
21

---

Published in Transactions on Machine Learning Research (10/2023)
Thus, we get
E [CH,((X)-
-x] = E QC (Q Q (x H) H)]{]]
E (X Q QQ _ (x - QH)QQ [1]]
E |X - H)Q) - (x - (
I (1 - a) Q H]
(1 a) X -
< (1 a) + 3) || - HI + (1 (1-a) (1-a)(11 -- 3- || XII
where we use the fact that an orthogonal matrix docsn't change a norm. Let B x(1-a}
a then
E ([ICHx((X)- x s (1 - Y
H
2 F (1 -0-) a))
(2-0) I x p
(21)
F Deferred Proofs from Section (Newton-3PC)
F.1
Auxiliary lemma
Denote by Ex+1l- the conditional expectation given (k + 1)th iterate x.+1, We first develop a lemma to handle the mismatch E& || fx of the estimate H defined via 3PC compressor.
Lemma F.I. Assume that || - x²1
1| ||a I²1 for all k 2 0. Then
}1 1 1 H - V f'f((=)) + (1 3B 17 - x=1
A
Ex+1
H
Proof. Using the defining incquality of 3PC compressor and the assumption of the error in terms of iterates, we expand the approximation error of the estimate H as follows:
Ex+1
H
+++
V fz [[
= Ex+1
[CH, (v ~
< (1 + 3) |ICH|
- - + (1+1/)IVV//(**))) - vi(''>)
< (1 + (1(1 - A) - v'ri(> 11
+ - v'a(2")
< (1 + (1 - H) )
+2B|| 42 f(a*)) - v=(((>)) +1 1/++
< (1+ (1 H V(f((=*))1
22 x" F + +1 1/3 + 2B 1
- x² 1|
< (1 + () H) ( +
(52)) -3B T2 - 11
(B+1
23
where we use Young's inequality for some / >>0 0. By choosing 3 2(1-A) when 0 < A < 1, we get
A
E |
V2 ( 1
A 2
h V2 f1(x"))) ) +
1 + 3B
2 1/0 1
When A= 1, we can choose 8 = 1 and have
Ex41 [|| k+1 v²f((>)) s (3B + 1) 13 1 - 112.
Thus, for all 0 < A < we get the desired bound.
22

---

Published in Transactions on Machine Learning Research (10/2023)
F.2 Proof of Theorem 4.2
The proof follows the same steps for FedNL until the appearance of 3PC compressor. We derive recurrence relation for ||æ - 112 covering both options of updating the global model. If Option 1. is used in FedNL, then
| -0=11
H
v)(a*)]
H (2t - x²) - \)(
p1
2
(I(HH) f²f(2²)) (I 2²) + f['))(x)) - x²) - -Vf(=+) + vf(="))(*)
2
2
(I(CT) (²パ(2')) (1t x² x²)|| + ||[]((+)) - V1(x)) -'/('') - =1))²
11
2
||
v2f(2") }|| 12 x²12 + 1
|| - x x²11'
122
4
2
L
11*
x²1
[ - -V-'((>>'1
1|
xx' 113
112
4
12 11a
2
H - >"f(>")11 /1²
12
12 x²11 113
4
2
11a
x²1' 11?
|H* [(x()) ||
2
1|
x² (12)) 1
2
where we use Hè = 1 in the second inequality, and v2f(x") > μI in the fourth inequality. From the convexity of || Ib, we have
| Σ [ (((()))
H - v3
<
H V'A(==)) Htt
E=
Thus,
2
+ I2
1a 1²112 v 222 1 x0'1 211
||
x:
(22)
2/²2
If Option 2. is used in FedNL, then as H + | I v2 ž μM and vf(x*) 0, we have
1+1 x²11 ||
1 x² IH + | -
[ + |h1 || ( + (x - xx)) - + vf(*')| V((=')
[[H
- (z² - xx)]l -IV[((+))
- -x")l
1
1
L.
<
||H* + 1 - v2 - x11 +
|| - x=1
2/1
1 a
Lx ||,t - 101 112
H + 1 I V' -0 +
n/
24
Lu
H (= x=11+
L 11a0 x=" 112
np
21
From the definition of 1k. we have
N =
=
42 s(<x))>>
| V² + 11 ==11-
23

---

Published in Transactions on Machine Learning Research (10/2023)
Thus,
2 H
n
L. + 2Tr
| x=1
V= -x11
11 -xx =x212
2/1
From Young's inequality, we further have
-0'11 ( -"(("")1>>>>~~==1| 211) 2
k+1
x²
1
n
H
(Te. 2Txx) )
||
x0" x0"1'
112
71
24²²
(L. 2Lp)²
1
x²11
Σ
H fi
||
x0111
112
n
241²
x² x²11274 + (L. 21p) )2
n 1a
| x
(23)
241²
where we use the convexity of ||
|| in the second inequality.
Thus, from 22 and
23
we have the following unified bound for both Option 1 and Option 2
C || - x²1 & fe Il - x²11244 + 2412 lla x²11a.
(24)
Assume || -x012 S
nº 2D and H²
- n² for all k 2 0. Then we show that || - 10
x=1
10² 2D
for all k: 2 0 by
induction. Assume 1| - xz1 1
< _ for all k < K. Then from 24 we have
20
/
ax k+1
x11 1| S $ 110 - x² 1²1 + 4
10 x²1 S
2D
Thus we have || - 1=2
/² 20
and H s toc for h 2 0. Using 24 again, we obtain
1 - 1 x 10
||a 2²11
(25)
Assume |1x00 - xx1 -
n² and H
< / for all h 2 0. Then we show that || fa0--*h
x011 <
4² 20
for all k: 2 0 by
2D
1o
induction. Assume ||a - 11 2|
I n²= for all S K. Then from 24 we have
2n
| K+1 x 111 S 4 ll 121 + 1 1 x²1 S 1
2D
Thus we have 1| - x='l 112 <
2D and H¹ s 10 for 1: 2 0. Using 24 again, we obtain
u²
|| 101 |1 x x=1
(26)
Thus, we derived the first rate of the theorem. Next, we invoke Lomma F.1 to have an upper bound for *
A H* + 2
(1 3B 3 L 18 111
Es Ex[H++1]
1
A
Using the above inequality and
26 for Lyapunov function t we deduce
Eg #111 <
1
A
H* +
1
+
3B
D x0112 +
=2'12+3
{AA A 3B
17 - 2²11
2
A
A
1
1
H +
1
6
+ 3B
17 x=12
2
3
A
{
A 1
1
min
2 2
24

---

Published in Transactions on Machine Learning Research (10/2023)
Hence E& (x*) 1 (1 - min ()) $0. Clearly, we further have B(H{*] S (1 min ()) To and B|Iaa* x* x*1|²] S 6(+3AB]]4 (1 min { A 31)
& to for & 2 Assume s + x² for all k. Then from [24 we have
2 ++ x=1 112
C 1
D 24²
H
1 x²1
rx
x² 1|?
and by taking expectation, we have
| 2²
C
I
B1M11
+
Biil2* - xx
1 - 101
2p²2
(A & (C+
AD
s min
12(1 + 3AB)L3
2
which concludes the proof.
F.3 Proof of Lemma 4.3
We prove this by induction. Assume H
S vi
n² 40
and 1| - x²11 s oî
for A S K. Then we also
have H² S o² for k S K. From 24 we can get
1C
4 || - -x11 1111222 + D
|
x111 <
24² l| - x1
||0t =x111 111 + 1 + xx11
S | k x01 s e
Using Lemma F.1 and the assumptions that we use non-random 3PC compressor, we have
A
1 3AB
H K ff(("))
)1
1
H
L 11 - 212
2
A
A
2
1+ 3AB
A²
1
L
2
40
A
8(1 + 3AB)CL
n
4C'
F.4 Proof of Lemma 4.4
We prove this by induction. Assume || xI S and H - v2S(<**) < fúc for k S K. Then we also
have H² < o² for ls < K. From 24 we can gel
40
C
|| - xx11 101227 + D
kt
1=
24 11 - x²11
12
S |1o - 112 + 1
bllo* x²112 S o7
From the definition
H + +C(
H
with probability p,
H
(27)
H
with probability 1- p.
have two cases for H we need to upper bound individually instead of in expectation. Note that the H fi(x"]l I w/c. For the other case when
case H. H is trivial as H HH+ f(f"">l
25

---

Published in Transactions on Machine Learning Research (10/2023)
H H + C(V H we have
| fi )l
H +
H - A(1"")
[C(V - H - - 1V 22 "²fa(x")) )|1
v1 v1- a 1 + LF |p||= h+
+
x'1l
VI H f2 vI a V2 f((tttt)) V2
fa(z )ll
L -F||=*h1 x"1l
H (i
>||F 2| t+z x'1l
(1-vI- a) μ
V1
+ 2hp
2/C
4VCLF 2/C'
which completes our induction step and the proof.
G Deferred Proofs from Section 5 (Newton-3PC-BC)
G.1 Proof of Theorem 5.1
First we have
||
x²112 = 1| x² [H*), 9 101
[ [a(* -x*) - -
1 [H x²) (g* [
(28)
where we use [)(x*) = 0 in the second equality, and |||||] < 1 in the last inequality.
If gk =1, 1, then
H -g) V
V Vf(2=) -+())))))))(((()))))))))) (2* - =1))?
<2/\v((>*) - Vf(2') - V3)(2') 2¹)1 +2] (++
122
1 - -1
H v2 112
2
12
<
1
-
+
H v² [1 - 1212
2
L2
1 H 1 1 f( /1/ ||= x111
1
x"
+2
2
L2 2
2 n
< 11
1
| v2 f( 1|21=* - -1'1.
(29)
where in the second inequality, we use the Lipschitz continuity of the Hessian of f. and in the last incquality, use the convexity of ||- 11..
26

---

Published in Transactions on Machine Learning Research (10/2023)
If 5h 0, then
x²) (0- - V/(+")|||
H 1e (2 w² + Vf(w*) Vf(x²) [ (= x²)
H I0 (x* w²) + V - V/(x')]
V (w V/(xx' V f²x xx)) + (V2f(x')
H (w) =1)]|²
L2
2 1lo* - =0"11" +011"
+ 2 1( )1 I x²1
2
x011 2 H v2 f1 1| x1
- 1w
(30)
For k 2 1, from the above three inequalities, can obtain
L3P 2p
2p
Eg| [x|| z²112 <
11
x=11
H
V2 f((x())
- x²1
np
(1 - p)
11 - xx" x=1 11+ 2(1 p)
+
H - V2 22 [1 11 - x1
2/12
n112
1=1
p
(L?11 - x21 + 471") 112 - x 11
2n²
(1 1-p)) p)
+
(T.21lu0 1²1 + 17( 11w - x² 11
(31)
2/12
where we denote H = 1
n Σリ H
For k 0, since 20 = w", it is easy to verify that the above equality also holds.
From the update rule of 2 we have
E Ex - x²1 2 (1 (1+ + - (1+ 1
Rx Bx1la=t1 x011
a
1 1
$ (1 + a1 AN)ll** - 2112 + (1 + xx) B1 x1112 +
Ex 1xx x=12
(1++a)) a)(( Am + =)]1== - 11 + (1 +1+ a1+ And (1+ 3
11 x01 112
+ 2(1 + BM - 21
2211+ a)+ + +1+ - Ex Balla - x11
-
for any a > 0, 3 > 0. By choosing a = Av and 3 =
Ay
we arrive at
4
4(1 SAy
Ay
4
5BM
4
5BM
Eg k+1
2²1 <
||
x²112+ +
3+
11a 12²12+
1 +
Ex
B| x²
2
Aar
2
Am
112* -011 +
CM
x²11 112 + CCMEAl1Z -
-x*111
(32)
2
27

---

Published in Transactions on Machine Learning Research (10/2023)
where we denote Cm
4 Ag
+ +1+
5BMr
Then we have
AM
Ex [|ll== - x²112 + 20 -x
11 - -x-11 + - x2112+
[|1++30Mrii 30 11 x²12
2
31
AM
115 - -x"11 3CMP -0'11---1'11---- 47th 11 - =x111
2
2412
30 (1 - p)
(L31le²* - xx111 + 471*) 1 - x2112 + CM - x2111
2p²2
AMnu Assume 11 - 1²1 S 240 and H I
Aup" for k: 2 0. 96C'M
Then from the update rule of wt, we also have
ll x¹1 =1125 S 200
Aar for & 2 O. Therefore, we have
Am
AMp)
+12+ AM p) I10
Es -x" -x011= =x21|=+00m || ++ x² x11 S
+
xx==-1"1²-
-x"11² 1
-xa|p+Carell=* -x-
2
8
8
(33)
From the update rule of w we have
Ex ExllwA-1 - x012 = --p1|=t x²1 + (1 -p)llu - x=' x=1
(34)
Define Øf := 112 2²1 + Cs C - -20114 A
1 2²11².
Then we have
4p
Eg [0]+1]== = Exx11= 8+1 - xz 112 + 200rlll - xx"1|]+ AM - p)
Exll [+1l - 11
4p
1 Aar(1 - p)
Av - -p)
Exll|aht1= - x²112 + 20 200s|lantt1 - -0-1
I1u* - x011
-x11
4
4p
1
AM (1 p)) (1-
AM
2 + AMp)
)
1=*t=0*122 11
AM (1 ( Carllst- 201112
4
8
4
As (1 -p)
AM(11 - p)
Ass (1)))
1100 =211
8
4p
Aas || - 1211
(1-3
3
20Mr 10r0-=1110
=11113
Aas - p)
3p
| x²11
8
4p
min min (2AM, 3p}
Φ/.
By applying the tower property, we have
1 S (1-
min (2AM 3p}
E 1 +
E [.
8
Unrolling the recursion, we can get the result.
G.2 Proof of Lemma 5.2
We prove the results by mathematical induction. Assune the results hold for k K. From the update rule
of w* we know || - 2² S min
AMR Aw } for k & K. If Ex = 1, from 28 and 29 we have 24Cx1
3SICxrC
1 K+1 x²1 <<<
1
L2
K
2²12 -x-11
+ 27t ) 11 - 11a"=
-2112
(35)
1122
2
Am
<
k
x²
112.
24CM
28

---

Published in Transactions on Machine Learning Research (10/2023)
If gk =0, 0,, from || - x012 S min( Aua² Aw
} and (30), we can obtain the above inequality simi-
24CM 3840 L
larly, From the upper bound of ||z* - =2"1l?, we further have || x*1 || S
11 240M 24
min{ Aaru²
Aw Aga
384CsrCw
Then from 32 and the fact that C.V. (a+t1) is deterministic, have
As
|| x x²1 S
1
-x'112 + CMrllE - x²111 + CMrllRR - =x111 1=*-
2
Am
Am
11AM 24C
Aarua Awra
1|= -x011 + Cas
min
24/
24C M L? 384CMs
AMp² AwAM?
$ min {
}. Ms
240 L2,"
For
-
we have
E& -=,1-~=((''" S (1+ H V -F + (1+ ! E& ( - (
$ (1+ - Aw H - |1 + (1 a Ex - viS((++11)1
+ |+ = Eg Ex fi( - {(
s <11 + a) - Aw) H - V> > + (1 + 12
+ ++(1 1+ .) 1. x
v'f((>>) + +1 (1 a))(1 -Aw) (1+) 1 11) 1 11 x011
I (1+ - Aw)(1+ + B) (1++3)||H
[1
3
Bw 1//1= - x111 + 2 + a) Bw +1 + 2) 1 1.711 - -x²113
+ 211 Bw
for any a > 0, B >>> O. By choosing a
Au and 3 = Aw
1(1 - " we arrive at
E, ++ 12 f3>1(("") >1 - (1
Aw 2
+1 H V2 fi(x" >1 + Cw 1= - x x21 + Cw T. - x² 113 (36)
where we denote Cw == Aw
1
+ +
5BM Since CW ((( (2) is disterministic, from 360, we have
Aw
H K++
<
1
H + Cw Lw 1=11=* K - x1 + Cw (2 - 12
2
Aw
AMFR
Aw
1
+ +2C Ii..
2
96CM
384CM L3
Amu²
960M
G.3 Proof of Lemma 5.3
We prove the results by mathematical induction. From the assumption on H we have
n2 72
H
H ('1(21))12
1
Σ
d
max
(axx(((HH))) )3æ (V²
n
il
1=1
<
d8
L2
max || - 112
(37)
0515k
29

---

Published in Transactions on Machine Learning Research (10/2023)
Then from | x²1l 112 č1, we have 7o min
Axyu" ف² 4d }- Assume the results hold for all k s K. If g 1, 95C
from 35
have
|
x= 1
1
L2
||
x
0²11
+ 27 ) || 11=-=x"> x011
112
2
xx
x=11
If tK 0, from I|= x²1 s dē1 and 30), we can obtain the above inequality similarly. From the assumption 2,, have
x=1 1|? dmax 1z) 1 - xr31 |
d max || - x="
0gigk+1
dē1.
At last, using (37 we can get HK+ < min Amp" n² ) which completes the proof. 96CM 4d
H Extension to Bidirectional Compression and Partial Participation
In this section, unify the bidirectional compression and partial participation in Algorithm 3 The algorithm can also be regarded as an extension of BL2 in (Qian et al. 2022 by the three point compressor. Here the symmetrization operator [t) is defined as
A = A+ A
2
for any A Rdxdd The update of the global model at k-th iteration is
x k+l
(H*) + + g
where H 1h, and g are the average of H. 1t, and of respectively. This update is based on the following step in Stochastic Newton method (Kovalev et al. 2019)
n n
x n
V fe(t))w Va(utt)
22 fi(
We use [H]]. I to estimate (( and of to estimate (L Jw! Vi(ww)), where 1 v f2 F is adopted to guarantee the positive definiteness of H + I.. Hence, like BL2 in QQian et al, 2022 we maintain the key relation
9. - + +111 - V.((w().
(38)
Since each node has a local model w we introduce 2 apply the bidirectional compression with the three point compressor and H expected learn ((=() iteratively. For the update of di on the server when ek 0, from (38). is natural let
9,
k+1 of -(H
((H++)
[ + 1
since we have w. k+1 w when t: 0. The convergence results of Newton BPwton-3PC-BC-PP are stated in the following two theorems.
30

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm
(Newton's method with 3PC, BC and Partial Participation)
1: Parameters: Worker's (CW) and Master's (CM) 3PC; probability p (0. 11: 0 <<<<> n
2: Initialization: o. 2, x E Rd; H
E Rdxd,
1 | - (. Ile; of = (H + (TT)
(u());; Moreover: H > - on server
H
Di= 10. go -
xk+11 ([H), + ITT) g²,
choose subset S C [n] such that Pli E St1 s/n for all i [n]
k+1 = =f (x (ctt1) for i S
6:
k+1 = whtl w for i S
2i
Send C.M. S/ (e (ctt1) to the selected devices i E S
9: for each device = =.....,?! in parallel do
10: for participating devices i Sh do
11:
2, k+1 C
C.M
=f (x*+1)
v2 (V2 VV
12:
= H.
1-+1 ||
V fi
13:
14: Sample
ck+1l Bernoulli(p)
15:
if ck+t1 =
16:
w
k+1
Di
k+1 ((H++)) + 1. I Vi((wtt)), send gf D: to server
17:
W w k+l -+1= (( [1 + 1 Tu buttt f
18:
Send H 1/ 12, and ch+1 to the server
19:
20: for non-participating devices i & 5 do
k+1 w/, H H. 18+1 11 91 21: k+1 = 2 w.
A+1 = ot
22: end for
23: on server
if cl+11
24:
25:
w
k-1
2/
k+1 receive 1+1 g
26:
if C
27:
W
w/ 9
k+1
H
H
k+1 ux
+ (1/-1 -1/ )e
28:
g++l
= gh + Σ
Lish
(g:
k+1
g.
29:
H+
E H.
"
k+1
30:
gk+1
1k Liest (1e41 14)
For 0, define Lyapunov function
2TCas
Ass we
= z
11*
x 111 12- +
4p
where [n] is the number of devices participating in each round.
Theorem H.1. Let Assumption 4.1 and & 0. Then we have
Assume
|| x=1 <
36( 36 and H* < 576C for all i E [n]
Aar
Aagu²
E $ < (
T m2A 3p)
40
8n
for k 2 0.
31

---

Published in Transactions on Machine Learning Research (10/2023)
Proof. First, similar to (30) in (Qian et al.
2022
can get
3 4n²
12W*
" Σ
3 122
| x²112 - (Whr)3
H -
+
nu²
3
+ 12W*
3
(W
Ht
(39)
Aμ²
122
2²
where W ; Σ
i= | - 1²2 and z
1
Ei= || - x²1
For i E 8t, we have 2ft11 C.M
mi (xhh-1).
n
Then, similar to [32 we have
11112/+11111 - x²112 - (1 (1- Av ) | 1²1 + Casll* -001= Casllatt- x²11? -x=11
Ex
2
Noticing that Pii E s*1 7/n and 2/ 2/411
z/ for $ s* we further have
Ex 2 k+1 - 2²11 = - 1Ex || k++ - x x²1
E 5*1 + (1 1--
Ex =| k+1 - x111| 1 1 shy
n1
Am
|| 1=1 + TOM || xx112+ + JCM || - x x²11²+ + (1-
| 1)
s
1 -
n
x²1
2
TAM
x² 11 + JCM 1| x² 112 + =CM 1 - -x" ==²1²2
1
||
2n
which implics that
1
Ex
11{22+1]-
Ball=, k+1 - x11
TAM
TOM
=OM
1
|| - x1" +
100e - xx x=1 112
1|
k41
- x11
71
2n
n
n
i=1
TAM
TCM
11 2²1 + TCM M 1 k+1 -x² x²'1
2h +
(40)
2n
Combining 33
and 40
we have
2TC
Es 1x
+
k+1
xx113
11
AM
TC'r 1|at
3rCMr
2 +
x= 101 +
| x²112
2n
n
n
<
TAM
2
+
TCM |1: 12+ 37CM
(312
W*
+ 12Hr
+
3 2
W
2m
4112
112
Assume ||
x=1 <
Aup?
and H <
Auu² 576CM
for all E [n]] and k 2 0.
Then we have
36(12 + 1
3T22
127
3122
2
Am 24CM²
Wk +
112 +
S
4u2
422
which indicates that
2TCM Ex (xt +
TAM
TCM
TAs Wh
|| k-1 - x: x01 5
1
2h +
||00 - 1112
(41)
n
2n
8n
For Wk. similar to (32) in Qian et al. 2022). have
Eg W
= -(1
TP
Wi
+
TP
E E
n
n
32

---

Published in Transactions on Machine Learning Research (10/2023)
Then from the above two inequalities we have
Eg
[
1
TAM
Ex|2
+
2TCM
---1-1111]--
AM
(1- TP)
4n
n
4p
nl
TAM
z
1
TAM
TCw
11 1e--x=11
Am
(1
TP
+
Tp
1
TAm
))
We
4n
4n
n
4p
n2
2n
4n
min
(2A M: 3p}
8n
By applying the tower property, we have
El $ (1- (1-
T min (2AM 3p}
E E((g).
8n
Unrolling the recursion, we can obtain the result.
Define 4 = H. + 16C
|1 k - x²12 2 for 2 O, where Cw := A + +1 5B
Ass
2.
Thcorem H.2. Let Assumption 4-1 holds, ch= 1, S = [n], and CMM
of 2 (x*+1) = xk41 for all i [n] and
k 2 0. Assume || x²112
36( + 44 and H² Aup² for all i [n] and O. Then we have 376CM
AMp
B[ 0/
| ++1 x x²12
(3(3 + (.L))
12 +
E
S S03
1 x0d 112
64Cw 12112
1
for k 2 0, where 02:= (1
min (ain/2Aww.on Ame
Proof. Since g* 1, S* = [m], and CM (x/+1) = x+1 for all i E [n]] and A: 2 O, we have 2/ = w = x* for
all i e [n] and ào 2 O. Then from 41 we have
(1 (1
3AM
Eg 1 6+1
x² 1²1
11 1=*--211 11
(42)
8
For H k+1 fl( similar to
36),
we have
Aw
Eg V2 S
H
-2
Cw T.
1 ++1 x² x²112
Considering 2t = b we further have
Aw
H
H
V2f((>))1 - + Cw 12 - 11
x111
22
Aw
v > + 20 LE - |H
which implics that
[H+ 1 (1-
Aw
E
H + 2Cw 1. 11.
(43)
2
33

---

Published in Transactions on Machine Learning Research (10/2023)
Thus, have
160w 1
Ex 1 Ex (7
E&
1 11 x=1
Am
Aw 2
160w 1.
Ht + 2Ow 1/ -
Ex |1 1 k+ - x=
AM
min (2Aw. AM
4
By applying the tower property, we have E B
11 _ 8, 0.E Unrolling the recursion, we have E[P4] S 05 0..
Then we further have [ s 0f tb and B|ix* - x= 1| 2 S
Av 0 $9.
16C L3
From we can get
3(I? + 4L.))
|1 x² x²113 4²
|| x=11² + 127
1| x x=11
4
Assume x² + xx for all k 2 0. Then have
| | x² 112
3(L + 417)
1 10"=-"" x1111 1271* +1174
||a x²
112
and by taking expectation, arrive at
x x0 112
3(L? + 4L2)
12
B1a²"
x=1
2 x= 12
4122
422
3(L3 + AL7)AM
12
S 8
+ 412
64Cw 1
Next, we explore under what conditions we can guarantee the boundedness of || x²1 and Hta
Theorem H.3. Let Assumplion 4.1 holds.
(i) Let CM and ew be deterministic. Assume ||00 11 S
11Áx min AMp? Aw Aur
24C 36(1/+1L3)CM 2301C Lp
and H <
Asp² Then have || - S 11AM min s6(L) + 44 2301C ) || - 21 S 570CM
Agnu
Aw
240x
minf Aunu 36(L3+113)0
Asn² Aw Asp² } and th < 576CM for all E [n] and k 2 0. 23
(ii) Assume (xt) is a conver combination of ((*")))/ and (H²) jr is a convex combina- tion of
for all E [n], j.l [d]. and 2 If ||20 x²1 Agg" & mint 3P +1gs 3odCm(Li++g 570. T 24 J. then || x11 1
2
Aun"
s dõg and H² <
min Awa²
576CM 24d for all i E [n] and h 2 0.
Proof. The proof is similar to that of Lemmas 5.2 and 5.3 Hence omit it.
Globalization Through Cubic Regularization and Line Search Procedure
So far, we have discussed only the local convergence of our methods. To prove global rates, one must incorporate additional regularization mechanisms.. Otherwise, global convergence cannot be guaranteed. Due
34

---

Published in Transactions on Machine Learning Research (10/2023)
to the smooth transition from contractive compressors to general 3PC mechanism, easily adapt two globalization strategies of FedNL (equivalent to Newton-EF21) to our Newton-3PC algorithm.
The two globalization strategies are cubic regularization and line search procedure. We only present the extension with cubic regularization Newton-3PC-CO (Algorithm 4 analogous to FedNL-CR (Safaryan et al. 2022 Similarly, line search procedure can be combined as was done in FedNL-LS
(Safaryan et al. 2022).
Algorithm Newton-3PC-CR (Newton's method with 3PC and Cubic Regularization)
Input: xº E 12d H H gaxd HJ = Σー H. 1 = - H& fix"))]
master
h* = arg ge (h), where Tx (h)h) == (V[(*),, + ((H 1*1),, + z ||Al|
4: Update global model to x*+1 = xF + h² and send to the nodes
5: for each device i = = 1...., n in parallel do
6: Get z and compute local gradient fz and local Hessian V f((ahtl) Take fi)t(x²)) from memory and update H CH. ( fi 1((x+1))
Send Vf((**+)), H and g+ = | fia to the server
end for
10: on server
11:
Aggregate ff(xtt1)= = E Vf(( H
k+ = E
(K+1 1 EE 4 141
We omit theoretical analysis of these extension as they can be obtained directly from FedNL approach with minor adaptations. In particular, one can get global linear rate for Newton-3PC-CR, global O(+) rate for general convex case and the same fast local rates and 11 Newton-3PC.
J Additional Experiments and Extended Numerical Analysis
In this section we provide extended variety of experiments to analyze the empirical performance of Newton-3PC. We study the efficiency of Newton-3PC in different settings changing 3PC compressor and comparing with other second-order stato-of-the-art algorithms. Tests were carried out on logistic regression problem with L2 regularization
H M(x)) + 3 f((x) =
1 Σ log (1 exp( (xp((bbjafxt))
min ZERd
(44)
where {aij. bij hjemm] are data points at the i-th device. On top of that, we also consider L2 regularized Softmax problem of the form
1 M f(x))
+
m
a a bij
min #ERd
fa(z) log
Σ exp
(45)
where a > 0 is a smoothing paramcter. One can show that this function has both Lipschitz continuous gradient and Lipschitz contimuous Hessian. Let ā.g be initial data points, and fc be defined as
a.fu big )
m
f(x) = log
exp
o
Then data shift is performed as follows
aij = - f.(0), e [m], E [m].
After such shift we may claim that is the optimum since Vf(0) 0. Note that this problem does not belong to the class of generalized linear models.
35

---

Published in Transactions on Machine Learning Research (10/2023)
J.1 Datasets split
We use standard datasets from LibSVM library (Chang & Lin 201 We shuflle and split each dataset into n equal parts representing local data of i-th client. Exact names of datasets and values of n are shown in Table
Table 2: Datasets used in the experiments with the number of worker nodes used in each case.
Data set
workers
total # of data points nm)
# features d
ala
16
1600
123
a9a
80
32560
123
w2a
50
3450
300
w8a
142
49700
300
phishing
100
11000
68
J.2 Choice of parameters
We follow the authors' choice of DINGO CCrane & Roosta 2019: in choosing hyperparameters: 0 = 10
10-6 : 10-4. Besides, DINGO uses a backtracking line scarch that selects the largest stepsize from {1, (1,2-1 , 2-10). The initialization of H for Newton-3PC, FedNL (Safaryan et al. 2022) and its extensions, NL1 Islamov et al. 2021 f=((=))) it not specified directly. For Fib-IOS (Fabbro et al, 2022) we set dx 1. Local Hessians are computed following the partial sumns of Fibonacci number and the parameter
p = A This is stated in the description of the method. The parameters of backtracking line search for Fib-IOS
0.5 and 0.9.
We conduct experiments for two values of regularization parameter À E (10-3,10-1) In the figures plot the relation of the optimality gap f(x*) f(x") and the number of communicated bits per node. In the heatmaps numbers represent the communication complexity per client of Newton-3PC for some specific choice of 3PC compression mechanism (see the description in corresponding section). The optimal value f(x*) is chosen as the function value al the 20-th iterate of standard Newlon's 's method.
In our experiments we use various compressors for the methods. Examples of classic compression mechanisms include Top-K and Rank-R. The paramcters of these compressors parsed in details in Section A.3 of Salaryan et al. (2022); we refer reader to this paper for disaggregaled description of aforementioned compression mechanisms, Besides, we use various 3PC compressors introduced in (Richtárik et al. 2022)
J.3 Behavior of Newton-CLAG based on Top-K and Rank- R compressors
Next, we study how the performance of Newton-CLAG changes when we vary parameters of biased compressor CLAG compression mechanism is based on. In particular, we test Newton-CLAG combined with Top- K and Rank-R R compressors modifying compression level (parameters K and respectively) and trigger parameter Ç. We present the results as heatmaps in Figure 3 indicating the communication complexity in Mbytes for particular choice of pair of parameters ((K, () or (R, <) for CLAG based on Top-K and Rank-R respectively).
First, we can highlight that in special cases Newton-CLAG reduces to FedNL (C = 0, left column) and Newton-LAG (compression is identity, bottom row). Second, we observe slight improvement from using the lazy aggregation.
J.4 Efficiency of Newton-3PCv2 under different compression levels
On the following step we study how Newton-3PCv2 behaves when the parameters of compressors 3PCv2 is based on are changing. In particular, in the first set of experiments we test the performance of Newton-3PGv2 assembled from Top-K, and Rand-K, compressors where K₁ + K2 = Such constraint forced to make the cost of one iteration to be Odd. In the second set of experiments we choose K₁ K₂ K and vary K. The results are presented in Figure
36

---

Published in Transactions on Machine Learning Research (10/2023)
70
27
96
(4)
23
89
90
64
55
68
26
28
29
28
29
45
171
17
98
33
21
320
120
Inggeri
a
phishing, 10
d 68
(b)
ala, À
10
d
123
a9a,
10 3
d
123
45
44
46
21
48
15
93
07
56
bngger
(e) phishing, == 10 9, 68
(I) ala, A 10 d, 123
g a9a, A 10 dd 123
Figure 3: First row: The performance of Newton- based on Top-K K varying values of (C, K) in terms of communication complexity (in Mbytes). Second row: The performance of Cowton-CLAG based on Rank- R varying values of (c, R) in terms of communication complexity (in Mbytes).
10"
10
10
10"
10
10
10
10
10
10
10
10
10
10"1
1900
10
3464 Supii Ruedl
Tour
WINT Tay
217 communicated bits node
git
221
21"
2l1
communicated bits node
communicated bits per node
communicated bits node
(a) phishing, 10
(b) ala, A 10
(c) a9a, 10
(d) w8a, 10-3
10:
101
10
10
10
10-11
10
10
10""
knad
10111
10-1
10-3
10
10
10
10
10
10
Tepts
2 -I:
2 10-12
10-1:
10
dand" 9050 Tedii did
10-11
10
sed Surtu Aowit
11
10"5
10-1
communicated bits
communicated bits
communicated bits node
communicated bits
(e) phishing, A= 10
(f) ala, A= 10
(g) a9a, 10
(h) w8a, À 10
Figure 4: First row: The performance of Newton-3PCv2 where 3PCv2 compression mechanism is based on Top-K₁ and Rand-K, compressors with K₁ + K2 = d in terms of communication complexity. Second row: The performance of Newton-3PCv2 where 3PCv2 compression mechanism is based on Top-K1 and Rand-K2 compressors with K1 = K₂ E (4/s, 4/1, d/2, d} in terms of communication complexity.
For the first set of experiments, one can notice that randomness hurts the convergence since the larger the value of K2, the worse the convergence in terms of communication complexity. In all cases a weaker level observe that the larger K, the better
of randomness is preferable. For the second set of experiments, communication complexity of Newton-3PCv2 except the case of w8a where the results for K = 150 are slightly better than those for K = 300.
J.5 Behavior of Newton-3PCv4 under different compression levels
Now we lest the behavior of Newton-3PCv4 where 3PCv4 is based on a pair (Top-Ki, Top-K2) of compressons. Again, we have to sets of experiments: in the first one we examine the performance of Newton-3PCv4 when K2 + Kg = d; in the sccond one we check the efficiency of Newton-3PCv4 when K, = K₂ = K varying K. In both cases we provide the behavior of Newton-EFF EF21 (equivalent to FedNL) for comparison. All results are presented in Figure 5
37

---

Published in Transactions on Machine Learning Research (10/2023)
10"
10
10
10"1
Tyol
WOA Payik Sigi
10
from Temt
10"1:
Part Togin
(POL
1,10
BPO TacciPaah
lea
10-12
15
211
gur
311
2/4
211
211
commanirated bits per node
communicated bit per node
communicated bits per node
communicated bits per node
(a) phishing, 10-4
(b) ala, 10
(c) a9a, A 10-
(d) w&a, A == 10
10
10
10
10
10
10-5
in
10
vew Tour
10
11--1 1r5t loptiiin
10
proit teportio
10-
arov Tostirlgin
(TL Tea
6721 hetie
(911 Teams
211 communicated bits per node
214
2m
2ir
22r
215
communicated bits per node
cammunicated bits per node
communicated bits per node
(e) phishing, 10
(f) ala, 10
(g) a9a, 10
(h) w8a, A 10
Figure 5: First row: The performance of Newton-3PCv4 where 3PCv4 compression mechanism is based on Top-K and Top-Kr compressors with K1 + K₂ = in terms of communication complexity. Second row: The performance of Newton-3PCv4 where 3PCv4 compression mechanism based on Top-K, and Top-K2 compressors with K1 K2 E {4/s, 4/4, 4/2, d} in terms of communication complexity. Performance of Newton-EF21 with Top-d is given for comparison.
10
10
10
10-15
40-5
10-5:
10-1:
Fand:
42.0
10
5.
2210
10-1
2.. Toom
10
10-12
2
3 24
202
2
211 20
2
2
2 20
communicated bits per node
communicated bits per nade
communicated bits per node
communicated bits per node
(a) phishing, A 10
(b) aia, A = 10-3
(c) a9a, A = 10
(d) vSa, A = 10
Figure The performance of Newton-3PCV 3PCv1 with 3PCv1 basod on Top-d, Newton-EF21 (equivalent FedNL) with Top-d, NL1 with Rand-1, and DINGO in terms of communication complexity.
As we can see, in the first set of experiments does not matter how we distribute between K₃ and K₂ since it does not affect the performance. Regarding the second set of experiments, we can say that some cases less aggressive compression (Ki K2 = d) could be better than Newton-EF21.
J.6 Study of Newton-3PCvl
Next, we investigate the performance of Newton-3PCvl where 3PC compression mechanism based on Top-K. We compare its performance with Newton-EF22 (equivalent to FedNL) with Top-d, NL1 with Rand-1, and DINGO. We observe in Figure that Newton-3PCvl is not efficient method since it fails in all cases.
J.7 Performance of Newton-3PCM.
In this section we investigate the performance of Newton-3PCv5 where 3PC compression mechanism is based on Top-K. We compare its performance with Newton-EF21 (equivalent to FedNL) with Top-d, NL1 with Rand-1, and DINGO. According to the plots presented in Figure 7 we conclude that Newton-3PCv5 not as effective as NL1 and Newton-EF21 but comparable with DINGO. The reason why Newton-3PCv5 not efficient in terms commuiicaiin complexity is that we still need to send true Hessians with some nonzero probability which hurts the communication complexity of this method.
38

---

Published in Transactions on Machine Learning Research (10/2023)
10
10
10-3
10m3
10
10
141 Radi
10
R.A. Bind
10
NLL Rind
1210
10
Norten 3008 Topits
10
10-92
10-13
10-12
24
2
21
2
2
communicated bits per node
communicated bits per node
communicated bits per node
communicated bits per nade
(a) phishing, = 10-4
(b) ala, 10
(c) a9a, 10-
(d) wsa, A 1010
The performance of Newton-3PCv5 with 3PCv5 based on Top-d, Newton-EF21 (equivalent FedNL) with Top-d, NL1 with Rand-1, and DINGO terms of communication complexity.
Figure 7:
10-
10
10
Teei
10
10
RX) Treii
GLNA
Trams
10"5
WOLL
10
3PV Toams
MOL Taooo
10-111
10-11
10-11
MOS Tey
10
2005 leputtn.
gll
gll 2/f 2
"il"
"224"" "1"
10-15
ge
221 3 2
communicated bits node
communicated bits node
communicated bits per node
communicated bits per node
aa) phishing, À 10"4
(b) ala, == 10-3
(c) a9a, A= 10
(d) w8a, 10-3
Figure 8: The performance of Newton-3PC with different choice of 3PC compression mechanism in terms of communication complexity.
J.8 Newton-3PC with different choice of 3PC compression mechanism
Now we investigate how the choice of 3PC compressor influences the communication complexity of Newton-3PC. We test the performance of Newton-3PC with EF21, CLAG, LAG, 3PCv1 (based on Top-K), 3PCv2 (based Top-K₁ and Rand-K2), 3PCv4 (based
Top-K, and Top-K2), and 3PCv5 (based on Top-K). We choose 1/a for Newton 3PCv5 in order to make the communication cost of one iteration to be Odd). The choice of K, K1, and K2 is justified by the same logic.
We clcarly see that Newton-3PG combined with EF21 (Newton-3PC with this 3PC compressor reduces to FedNL), CLAG, 3PCv2, 3PCv4 demonstrates almost identical results in terms of communication complexity. Newton-LAG performs worse than previous methods except the case of phishing dataset. Surprisingly, Newton-3PCvl, where only true Hessian differences compressed, demonstrates the worst performance among all 3PC compression mechanisms. This probably caused by the fact that commuiiattion cost of one iteration of Newton-3PCvl is significantly larger than those of other Newton-3PC methods.
J.9
Analysis of Bidirectional Newton-3PC
J.9.1
EF21 compression mechanism
In this section we analyze how each type of compression (Hessians, iterates, and gradients) affects the performance of Newton-3PC. Tn particular, we choose Newton-EF21 (equivalent. FedNL) and change parameters of each compression mochanism. For Hessians and itcrates we use Top-K₃ and Top-K2 compressors respectively. In Figure g we present the results when vary the parameter K1, K₂ of Top-K compressor and probability p of Bernoulli Aggregation. The results presented heatmaps indicating the number of Mbytes transmitted in uplink and downlink directions by each client.
In the first row in Figure 9 we Lest different combinations of compression parameters for Hessians and iterates keeping the probability p of BAG for gradients to be equal 0.5. In the second row we analyze various combinations of pairs of parameters (K,p) for Hcssians and gradients when the compression on iterates not applied. Finally, the third row corresponds the case when Hessians compression is fixed (we use Top-d), and we vary pairs of parameters (K,p) for iterates and gradients compression.
39

---

Published in Transactions on Machine Learning Research (10/2023)
According to the results in the heatmaps, we conclude that Newton-EF21 benefits from the iterates compression. Indeed, in both cases (when we vary compression level applied on Hessians gradients) the best result is given in the case when we do apply the compression on iterates. This is not the case for gradients (sec sccond row) since the best results are given for high probability p; usually for p - 1 and rarely for = 0.75. Nevertheless, we clearly see that. bidirectional compression is indeed useful in almost all cases.
14
Compriss
compriatio lavel
(al) #2a,
(b1) a9a, A 3
(cl) ala, A
NOU greee
(a2) #2a,
(b2) a9a,
3
(c2) a1a, 10
36
3
12
11
14
15
15
(a3) x2a, A
(b3) a9a, A
(c3) aia, A
Figure 9: First row: The performance of Newton-3PC-BS in terms of communication complexity for different. values of (K1, K2) of Top-K and Top-K2 compressors applied on Hessians and iterates respectively while probability p = 0.75 of BAG applied on gradients is fixod. Second row: The performance of Newton-EF22 in terms of communication complexity for different values of (K1,P) of Top-K, compressor applied Hessians and probability p of BAG applied on gradients while K₂ Third row: The performance of Newton-EF21 in terms of communication complexity for different values of (K2,p) of Top-Ky compressor applied on iterates and probability p of BAG applied on gradients while K1 = d parameter of Top-K, applied on Hessians is fixed.
parameter of Top-K2 applied on iterates is fixed.
J.9.2 3PCv4 compression mechanism
In next set of experiments fix EF21 compression mechanism based Top-d compressor applied Hessians and probability p- = 0.75 of Bernoulli aggregation applied on gradients. Now we use 3PCv4 update rule on iterates based on outer and inner compressors (Top-Ki, Top-K2) varying the values of pairs (K1, K2). We report the results as heatmaps in Figure 10]
We observe that in all cases is better to apply relatively smaller outer and inner compression levels as this leads to better performance in terms of communication complexity. Note that the first row in heatmaps corresponds to Newton-3PC-BB 3PC-BC reduces to FedNL-BC method (Safaryan et al. 2022). We obtain that 3PCv4 compression mechanism applied on itcrates in this setting is more communication efficient than EF21 This implics the fact that Newton-3PC-BC could be more efficient. than FedNL-BC in terms of communication complexity.
when we apply just EF21 update rule on iterates. As consequence, Newton-
J.10 BL1 QQian et al., 2022) with 3PC compressor
As it was stated in Section 4.1 Newton-3PC covers methods introduced in QQian et al. 2022 as a special case. Indeed, in order to run, for example, BL1 method we need to use rotation compression operator 20 The role of orthogonal matrix in the definition plays the basis matrix.
In this section we test the performance of BL1 in terms of communication complexity with different 3PC compressors: EF21, CBAG, CLAG. For CBAG update rule the probability p 0.5, and for CLAG the
40

---

Published in Transactions on Machine Learning Research (10/2023)
14
14
39
76
Cosr
(a) a9a, == 10-3
(b) ala, A 10
(c) phishing, A= 10
(d) ala, A A= 10
Figure 10: The performance of Newton-3PC-BC with EF21 update rule based Top-d compressor applied Hessians, BAG update rule with probability 0.75 applied on gradients, and 3PCv4 update rule based on (Top-K1, Top-K2) compressors applied on iterates for different values of pairs (K1, K2).
trigger <= 2. All aforementioned 3PC compression operators are based on Top-T compressor where the dimension of local data (sce Section 2.3 of (Qian al. 2022 for detailed description).
Observing the results in Figure 11 we notice that there is no improvement of one update rule over another. However, in EF21 is slightly better than other 3PC compressors in a half of the cases, and CBAG insignificantly outperform in other cases. This mcans that oven if the performance of BL1 with EF21 and CBAG are almost idantical, CBAG is still preferable since is computationally less expensive since we do not need compute local Hessians and their representations in new basis.
10
10 10
991
10
10:1.
PP1
10
10
CRSO
10
10
10
10
10
10
10
10-1
10-9
10-01
10
2M
g per
glr
2
2
g
per
per
per
(a) a9a, = 10-3
(b) phishing, A 10
(c) a1a, = 10-3
(d) w2a, 10
Figure 11: The performance of BL1 with EF21, CBAG and CLAG 3PC compression mechanisms in terms of communication complexity.
J.11 Analysis of Newton-3PC-BC-P
J.11.1 3PC's parameters fine-tuning for Newton-3PC-BC-PP
On the following step we study how the choice of parameters of 3PC compression mochanism and the number of active clients influence the performance Newton-3PC-BC-PP.
In the first series of experiments we test Newton-3PC-BC-PP with CBAG compression combined with Top-2d compressor and probability p applied Hessians; EF21 with Top-2d/s compressor applied on iterates; BAG update rule with probability p = 0.75 applied on gradients. We vary aggregation probability p of Hessians and the number of active clients Looking at the numerical results in Figure 12 (first row), we may claim that the more clients are involved in the optimization process in each communication round, the faster the convergence since the best results in each case always belongs the first column. However, we do observe that lazy aggregation rule with probability p < is still beneficial.
In the second row of Figure 12 we investigate Newton-3PC-BC-PP with CBAG compression based on Top-d and probability p 0.75 applied on Hessians; 3PCv5 update rule combined with Top-2d/s and probability p applied on iterates; BAG lazy aggregation rule with probability p 0.75 applied gradients. In this case we modify iterate aggregation probability p and the number of clients participating in the training. We observe that again the fastest convergence is demonstrated when all clients are active, but aggregation parameter of iterates smaller than 1.
Finally, we study the effect of BAG update rule on the communication complexity of Newton-3PC-BCCPP. As in previous cases, Newton-3PC-BC-PP is more efficient when all clients participate in the training process.
41

---

Published in Transactions on Machine Learning Research (10/2023)
Nevertheless, lazy aggregation rule of BAG still brings the benefit to communication complexity of the method.
18
60
13
181
18
144
12
6.6
139
123
(a1) phishing, À
(b1) ala, A 10 8
(cl) w2a, À
144
X1
427
101
131
500
200
(a2) phishing,
(b2) ala, À
(c2) w2a,
327
22:
23
181
114
181
200
eachacles
(a3) phishing, 10-
(b3) aia, 10-3
(c3) w2a,
Figure 12:
The performance of Newton-3PC-BC-PP with various update strategies in terms of communication complexity (in Mbytes).
J.11.2 Comparison of different 3PC update rules
Now we test different combinations of 3PC compression mechanisms applied Hessians and iterates. First, fix probability parameter of BAG update rule applied gradients to p 0.7. The nunber of active clients in all cases n/2. We analyze various combinations of 3PC compressors: CBAG (Top-d and p = 0.7) and 3PCv5 (Top-4/2 and p = 0.7); EF21 (Top-d) and EF21 (Top-4/2); CBAG (Top-d and = 0.7) and EF21 (Top-"/2); EF21 (Top-d) and 3PCv5 (Top-//2 and = 0.7) applied on Hessians and iterates respectively, Numerical results might be found in Figure 13. We can see that in all cases Newton-3PC-BC-PP performs the best with a combination of 3PC compressors that differ from EF21+EF21. This allows conclude that EF21 update rule is not always the most effective since other 3PC compression mechanisms lead to better performance in terms of communication complexity. Nonetheless one notice that it is useless to apply CBAG or LAG compression mechanisms on iterates. Indeed, in the case when we skip communication the iterates remain intact, and the next step is equivalent to previous one. Thus, there is no need to carry out the step again.
10
10
10
10
10
10
10-5
10-5
10-1
10
10-2"
110
10-11
COPSASPOS 1911
10
communicated bits
communicated node
communicated bits node
communicated bits node
(n1) ala, A= 10
(b1) w2a, =
(c1) a9a, 10
(c1) w8a, 10-4
Figure 13: The performance of on Hessians and iterates respectively.
with different combinations of 3PC compressors applied
J.12 Global convergence of Newton-3PP
Now we investigate the performance of globally convergent Newton-3PC-LS an extension of Newton- 3PC based the line search it performs significantly better than Newton-3PC-CR based cubic
42

---

Published in Transactions on Machine Learning Research (10/2023)
regularization. The experiments are done synthetically generated datasets with heterogencity control. A detailed description of how the datasets are created is given in section B.12 of (Salaryan et. al. 2022 Roughly speaking, the generation function has 2 parameters and 3 that control the heterogeneity of local data. We denote datasets created a such way with parameters a and 3 as Synt (a, f). All datasets are generated with dimension d = 100, split between n = 20 clients each which has m 1000 local data points. In all cases the regularization parameter is chosen 10-4
We compare versions of Newton-3PC-LS combined with EF21 (based Rank-1 compressor), CBAG (based Rank-1 compressor with probability 0.8), CLAG (based on Rank-1 compressor and communication trigger Ç = 2), 3PCv2 (based on Top-3d/4 and Rand-4/4 compressors): and 3PCv4 (based on Top-4/2 and Top-d/2 compressors). In this series of experiments the initialization of H is equal to zero matrix. The comparison is performed against ADIANA (Li et al. 2020b) with random dithering (s = vd), Fib-IOS Fabbro et al,
2022 and GIANT (Wang et al. 2018).
The numerical results shown in Figure 14 According to them, observe that Newton-3PC-LS is more resistant to heterogeneity than other methods since they outperform others by several orders in magnitude. Besides, we see that Newton-CBAGan and Newton-EF21-LS are the most efficient among all Newton-3PC-LS methods; in some cases, the difference is considerable.
10
10
10
10
10
10
Unew Whote
10
10
10"5
10"
10
10-3.
4210
10
10-11
10
gi
gli
gur
per
per
per
(a) (0.50.0055
(b) S1nt(1,1)
(c) Synt (1.5,1.5)
(d) Synt(2,2)
Figure 14: The performance of Sowton-3PC-LS with different combinations of 3PC compressors applied Hessians against ADIANA, Fib-IOS, and GIANT.
43


Reviews:
[{"review_id": "LshcmXGXZz", "reviewer": "Reviewer_pEt4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\nWhen viewed as a generalization of FedNL to arbitrary three point compressors, while maintaining convergence guarantees, the core idea seems strong. As well, the idea of randomized updating through Bernoulli aggregation has clear benefits in terms of reducing complexity.\n\n## Weaknesses\nOverall, the paper suffers from a general lack of clarity in exposition and focus on what makes this work novel.\n\n-  One of the main suggested contributions is the extension of three point compressors to Hessian communication in Definition 3.1. However, using the Frobenius norm for matrices is equivalent to using the 2-norm for vectors, so the original definition suffices if the matrix is simply reshaped. Thus the novelty of this purported extension is questionable.\n- Fast local convergence rates are the focus of the theoretical analysis, yet in many cases it seems this would likely not be the dominant cost. Globalization strategies are partially presented in the appendix, but there is limited discussion on the subject in the main text.\n- In Section 4.2 it is stated that \"The key novelty Newton-3PC brings\" is in reducing communication and computational complexity. While the communication complexity depends on the compressor being used, it seems that the computational complexity on any local node is still large as a new Hessian must be computed and stored at every step even if there is no update.\n- Lemma 4.4 appears to have no dependence on the probability of updating the estimate, which begs the question of what happens when $p=0$, i.e. no update is ever sent?\n- In Section 4.4 local convergence rates are provided for three different quantities, yet discussion surrounding these results is lacking.\n- In Section 6.2 and Figure 1 the benefits of Bernoulli aggregation on communcation and computational complexity are discussed, but these results seem somewhat trivial. Infrequent updates necessarily result in a reduction of costs.\n- Unclear algorithm presentation. The following specifically apply to Algorithm 1, but Algorithm 2 has similar issues.\n\t- How are the initial local Hessian estimates computed?\n\t- The option to send the local error seems unnecessarily confusing, perhaps a comment that this step is only necessary if using the second update strategy would suffice.\n\t- Line 9 always sends the local updated local Hessian estimate to the server, but this will always incur a $d^2$ communication cost even if there has been no update\n- Unclear language\n\t- In the discussion of Example 3.3, the idea of Top-K is referenced but not defined. This, and other compressors such as Rank-K are again brought up in Section 6, but never clearly defined.\n\t- The second paragraph of Section 5 introduces three sets of parameters, but where these parameters live and their purpose is not discussed.\n\t- Throughout Section 3 the domain and range are given as $\\mathrm{R}^d$ when it should be $\\mathrm{R}^{d\\times d}$.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper discusses Newton-type convex optimization methods in a distributed setting. Specifically, the authors consider a general approach using three point compressors for communicating Hessian information. A variety of compressors and aggregation schemes are explored, and two new techniques for deciding when to aggregate are proposed. Local linear and superlinear convergence rates are established for this general method depending on the quantity under consideration.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Overall, the paper needs to be thoroughly updated to provide a clearer presentation of the author's work and a more focused  discussion of their specific contributions. Addressing the weaknesses given above provide a starting point for these changes.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZGPaAl8Xrv", "reviewer": "Reviewer_22SC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. The proposed Newton-3PC method is clean. \n\n2. The theory is solid with local linear and/or superlinear convergence rates.\n\nWeaknesses:\n\n1. The improvement of the proposed methods over the SOTA methods is not significant. In the first row of Figure 1, to achieve the same accuracy, the proposed method only saves half communication bits compared with NL1 or DINGO.\n\n2. I am not sure if it is a trival combination of 3PC and Newton method. I suggest the authors to discuss the challenges in the proof of Theorem 4.2, especially something new beyong the proofs in the Newton method and 3PC. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper stuides distributed Newton method with communication compression. Specifically, the three point compressor (3PC) of Richtarik et al. [2022] is combined with the traditional Newton method. Several new 3PC mechanisms, such as adaptive thresholding and Bernoulli aggregation, are discovered in this paper. Fast condition-number-independent local linear and/or superlinear convergence rates are derived for the proposed methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I suggest the authors to discuss the challenges in the proof of Theorem 4.2, especially something new beyong the proofs in the Newton method and 3PC.\n\n2. I suggest the authors to compare with the uncompressed distributed Newton method in the first row of Figure 1, which communicates the full Hessian matrix. Then, the readers will know how many bits are saved after compression.\n\n3. In Table 1, the communication cost is O(d). However, the proposed methods need to send the compressed Hessian matrix to the server. Is this because the compresser only sets the top-d elements non-zero in the d*d matrix?", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jfS983vyMt", "reviewer": "Reviewer_tB6q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThe empirical results are promising and adequate. The presented algorithms and theory and clear to read and understand. I have not gone through all the proofs in the \n\nQuestions/weaknesses:\nThe paper rehashes known techniques, so novelty is limited but that is not what tmlr is about. \n\nI would suggest add more information about aggregation mechanisms and what that implies, since it is an equal part of the CLAG mechanisms.\n\n Some of the “lemmas” such as 3.6 and 3.4 are trivial and could be written as sentences to save place, if needed. \n\nGenerally the convergence rates are known where the shrinkage factor (e.g. \\rho in Theorem 4.2) depends on the condition number. Even if there is no compression, should the convergence rate not “fall back”to what is known about strongly convex functions? It would be nice if the authors can provide some intuition on why this does not happen, and why the presented rates turn out to be free of the condition number. \n\nThe locality conditions mentioned in Lemmas 4.3 and 4.4 are required to hold for \\mathcal{H^k} for Theorem 4.2, and not really required for || x^k – x^*||^2, no ? why is the latter also mentioned in the lemmas, when it can be skipped and it is not useful ? \n\nThis is not really related to the paper itself or its contributions, but are the authors aware of approximate compression techniques that does not required full instantiation/calculation of the local hessians? The use of sketch and project operator is unclear, and it is also not clear how to hunt for \"good\" compression operators, since the analysis itself assumes this is known already.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes the use of 3pc compressors for a few federated learning settings. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the strenghts/weaknesses section.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers agreed there were interesting ideas, and that the paper was by-and-large well-executed; the paper is also a good length, which may help its impact. In terms of clarity, the high-level ideas were clear, but even after the rebuttal and revision, reviewer pEt4 still felt the details of the presentation could be cleaned up to make the paper more clear.  If the authors wish to make any minor changes related to clarity before submitting the camera-ready version, that is fine with me [also for the camera-ready version, if the authors have github code that they did not include a link to before since it would de-anonymize the paper, they may choose to add it back in].
Decision: Accept (poster)