{'fraction_non_alphanumeric': 0.04448981028474887, 'fraction_numerical': 0.014501425504206118, 'mean_word_length': 4.285953488372093, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
FLECS: A Federated Learning Second-Order Framework via Compression and Sketching

Inspired by the recent work FedNL (Safaryan et al, FedNL: Making Newton-Type Methods Applicable to Federated Learning), we propose a new communication efficient second-order framework for Federated learning, namely FLECS. The proposed method reduces the high-memory requirements of FedNL by the usage of an L-SR1 type update for the Hessian approximation which is stored on the central server. A low dimensional `sketch' of the Hessian is all that is needed by each device to generate an update, so that memory costs as well as number of Hessian-vector products for the agent are low. Biased and unbiased compressions are utilized to make communication costs also low. Convergence guarantees for FLECS are provided in both the strongly convex, and nonconvex cases, and local linear convergence is also established under strong convexity. Numerical experiments confirm the practical benefits of this new FLECS algorithm.


Introduction
This paper presents a novel second-order method for Federated Learning called FLECS. In this setup, multiple agents/devices/workers collaborate to solve a machine learning problem by communicating over a central node (server). It is assumed that the central node is a large and powerful machine, but the agents/devices are much smaller (for example, a cellphone, or laptop). Moreover, raw data is stored locally on each worker and cannot be exchanged or transferred. The finite sum minimization, or Federated Learning, problem can be formalized in the following way: works that focus on maintaining client data privacy [16]. Beyond first-order methods, second-order methods have also been developed for Federated Learning. Some of these algorithms [42,15,12,5,1] utilize statistical similarity (the homogeneous data setting), which, roughly speaking, means that the local functions f i are similar, and they approximate the overall empirical risk function F well. FedNL [36] for the second-order method for Federated Learning in the case of heterogeneous data. While FedNL makes a valuable step toward the applicability of second-order methods to Federated Learning, this framework seems to be impractical for large-scaled problems, since d × d Hessian approximations are stored locally on workers and transferred to the server via compressed matrix communications. (This violates the assumption in the current work, that the individual workers have small memory.) The goal here is to build upon the work in [36] and develop a new second order framework for Federated Learning that is based upon more realistic assumptions about the available computational architecture. That is, we assume that individual workers are devices with relatively low memory availability and computational capacity (e.g. mobile phones), but they can connect to a large and powerful central machine. The typical situation, that downloading is much faster than uploading, is also assumed. 1 We introduce the FLECS second-order framework for strongly convex and non-convex optimization, which places no additional memory on workers and reduces the number Hessian-vector products per node. Therefore, our algorithm can be viewed as the lightweight FedNL, since it provides similar theoretical guarantees and has almost the same global. FLECS uses sketching [38] and matrix compression for efficient communication and allows for several Hessian learning techniques (including truncated LSR1 update) and two iterate updates, namely Truncated inverse Hessian approximation and FedSONIA, inspired by [30] and [22].

Contributions
We propose FLECS: a Federated LEarning Second-Order Framework via Compression and Sketching with the following properties.
• No additional storage on workers. In large-scale machine learning problems, it is impossible to store the d × d-dimensional Hessian approximations. For a dataset with d = 50, 000 features, the local Hessian approximation requires more than 10 GB of memory. For FLECS, the Hessian approximations are stored on the server, so memory requirements for the individual workers remain low. • Efficient communication via sketching and compression. To reduce the cost of communication, we use a sketching technique. This allows the exchange of d × m matrices instead of d × d, where m d is the user defined memory size, which could be set as m = 1. Moreover, we exploit compression to make the algorithm even more communication-efficient. This strategy heavily improves the one in [36], since we decrease the dimension of the transferred matrices d/m times. Moreover, sketching reduces the number of Hessian-vector products from d to m.
• Heterogeneous data setting. Our framework is flexible and does not assume that data on the workers is independent and identically distributed. • Hessian Learning via Quasi-Newton updates. Motivated by quasi-Newton methods, sketching techniques and inverse Hessian truncation, we propose the Truncated L-SR1 update and Direct update for our Hessian approximations. • Theoretical Analysis. Convergence guarantees in both the strongly convex, and nonconvex cases, are provided, as well as a local linear rate of convergence under strong convexity independent of problem conditioning. • Competitive Numerical Experiments. Our numerical experiments highlight the practical benefits of our proposed framework.
Organization. The remainder of the paper is organized as follows. Related works are described in Section 2. Section 3 presents the proposed framework, including all algorithmic details. In Section 4, we establish theoretical convergence guarantees (all proofs can be found in the appendix). Numerical experiments are provided in Section 5 (additional experiments are provided in the appendix), and concluding remarks and potential future research directions are given in Section 6.

Related Work
Second-order methods are well established in the optimization literature. Such methods employ the Hessian (or an approximation to it) and thereby important (possibly approximate and/or partial) curvature information is available for utilization. The benefits include 'better' search directions, and faster rates of convergence that may be independent of the condition number, although the algorithms often have higher memory and computational requirements than first order methods. To balance the trade off between improved convergence rates versus increased costs, approaches that involve modifying or approximating the Hessian have been proposed, and several of these are discussed now.
Arguably, some of the most popular algorithms that use approximations to the Hessian are quasi-Newton methods. They employ information from the iterates to build an approximation to the Hessian that improves in accuracy as the algorithm progresses. Among these are algorithms that use BFGS, SR1, and DFP updates [17,29,13], which are now considered to be classics in optimization due to their effectiveness and practicality, and also because, under certain conditions, theoretical results related to the accuracy of the Hessian approximations are available. This motivates the current work, which incorporates quasi-Newton type updates to learn a good approximation to the Hessian. Of particular interest is the SR1 update, which does not guarantee positive definiteness of the Hessian approximation [13]. Previously, this was considered to be a disadvantage, but in the case of nonconvex optimization, it would appear to be advantageous. L-SR1, a limited memory variant of SR1, belongs to the class of limited memory quasi-Newton algorithms [25,4]. These methods store only the last m gradient differences Y k = [y k−m+1 , . . . , y k ] and iterate differences S k = [s k−m+1 , . . . , s k ], where m is the memory size, y k = ∇F (w k ) − ∇F (w k−1 ) and s k = w k − w k−1 . The compact form of the L-SR1 update is [6] where are strictly lower and upper triangular, and B 0 is the initial approximation. The work [3] proposed the use of a sampled S k , rather than one based upon the previous m iterate differences. The idea is, given the current iterate w k , simply sample m random directions, and use the differences with w k as the columns of s k (forming Y k appropriately). An S k with this form can be viewed as sketching matrix [38], and the Newton Sketch algorithm in [31], shows that even randomly projected or a sub-sampled Hessian provides enough curvature information for fast convergence. The Nonconvex Newton method of [30] is a different approach, which is an adaptation of Newton's method for nonconvex problems. At each iteration, the singular value decomposition of the Hessian is computed, small eigenvalues (in absolute value) are truncated, and then a positive definite modification of the Hessian is constructed. This is then used to create Newton-type direction. SONIA [22] bridges the gap between first-order and second-order methods, combining the ideas of quasi-Newton algorithms, sketching [31] and truncation [30]. It constructs the search directions using curvature information in one subspace and gradient information in the orthogonal complement. Second-order methods for Federated Learning, can generally be divided in two groups, based upon whether a homogeneous or heterogeneous data setting is assumed. Algorithms in the first group rely on the concept of statistical similarity, which, in practice, means that each local function f i is a 'good' approximation of the global objective function F . (More formally, ∇ 2 F − ∇ 2 f i ≤ β for some β > 0.) Usually, in this case, methods utilize the part of the data stored on the server and use it to approximate the full Hessian [42,15,12,5,1]. No such statistical similarity (i.i.d.) assumption is made in the heterogeneous setting, which is perhaps more realistic (e.g., it may be impossible/impractical to have local data (on a mobile phone say), that approximates the data on the server well). The main work in this setting is FedNL [36]. The authors proposed a way to learn Hessian approximations and then take an approximate Newtontype step. However, the main drawback is that the Hessian approximations are stored locally and communications performed via compressed d × d matrices. For large-scale optimization problems, it is impossible to store the d × d matrix locally, because of memory limitations. Extensions of FedNL can be found in [21], [32]. The approach proposed here combines ideas from quasi-Newton methods, sketching, and Hessian learning, and develops a second-order Federated Learning framework with efficient communications and without an additional memory burden on workers. All Hessian approximations are stored on the server, not the workers. Communications are based on a user-defined memory hyperparameter m and utilize compression to reduce communication. Sketching allows to transfer d × m matrices and reduce the number of Hessian-vector products on the worker. The proposed framework allows for two Hessian learning techniques and two iterate update rules. The Truncated Inverse Hessian approximation is based on the idea of truncating eigenvalues (as in [30]) of Hessian approximate, while FedSONIA is based upon SONIA [22] and reduces the iteration complexity of the step from O(d 3 ) to O(nmd 2 ).

FLECS
Inspired by the works [22,36], we propose a general framework for second-order methods for federated learning problems (1) that allows for different forms for the iterates and different Hessian approximations/updates. One of main goals of this framework is to create fast communicationefficient second-order methods that do not place additional memory requirements on the workers. To make broadcasting between the server and nodes cheap we employ sketching and compression. Throughout the paper, S k ∈ R d×m denotes a sketching matrix, where m is the memory size (m d). Any operator that compresses a matrix is denoted by C : R d×m → R d×m , e.g. random dithering, Rank-R, Top-K, Rand-K (description of compressors can be found in Appendix C). The Hessian approximation of the i-th worker at iteration k is denoted by B i k , and is stored on the central node. Our framework can be described in three steps (further details follow in later subsections): 1. Worker step. Each worker receives the current iterate w k , and their local Hessian approximation multiplied by a sketching matrix, i.e., the product B i k S k ∈ R d×n . The matrix is sent directly (i.e., no compression), since, typically, downloading is faster than uploading. Each worker then computes their local Hessian-sketch product Y i k := ∇ 2 f i (w k )S k and sends back the compressed Hessian approximation update. The server receives C i k , M i k := S T k (∇ 2 f i (w k ))S k , and ∇f i (w k ) from all i = 1, . . . , n workers. Using this information, as well as the current (local) Hessian approximation B i k , the new approximation B i k+1 is formed. Our framework allows B i k+1 to be computed by a (1) Truncated L-SR1 update, or (2) Direct update. 3. Iterate update. The server forms the matrices There are several options for computing the search direction p k , including (1) a truncated inverse Hessian approximation step, or (2) via a SONIA step for Federated Learning (FedSONIA). The process then repeats from Step 1.

Initialization
The algorithm is initialized with a user defined memory size m d, and n matrices B i 0 ∈ R d×d are stored on the central node, each representing an approximation to the local Hessian for the ith worker. Various additional parameters are initialized depending on the selected update rule (to be described later). At iteration k > 0 of FLECS, m directions {s 1 , . . . , s m } are randomly sampled at . . , n, ω > 0truncation constant. 1: On the server: 2: for i = 1, . . . , n do 3: compute B i k+1 via (7). 6: end for all nodes (including the server) and combined together, forming the columns of a sketching matrix S k ∈ R d×m . Note that S k is the same for all machines and the main node; this is guaranteed by setting the random seed to be equal to the iteration number k during sampling.

Worker Step
Each of the workers receives B i k S k , and the iterate w k , from the server. On each node we compute The quantities in (4) are used to construct the Hessian approximation on the main node. Since M i k is an m × m, it can be sent directly without compression. So too can the vector ∇f i (w k ). For the matrix Y i k we use the compression operator C. In order to make the variance of this compression low, we use an error-feedback technique and send C i

Hessian Approximation update
The server receives (4) from each worker i = 1, . . . , n. Firstly, we restore an approximation to Y i k as Then, we apply one of the following options to update the Hessian approximation.
Hessian update option 1. Truncated L-SR1 update (Algorithm 1). In this case we compute the approximate Hessian of the i-th worker using the L-SR1 update: To ensure numerically stability of the update (6), truncation is employed. At first, we take the spectral decomposition of the small (m × m) matrix is a diagonal matrix containing the eigenvalues, and U i k is an orthogonal matrix containing the corresponding eigenvectors. Next, we compute the inverse (L i k ) −1 , and truncate small values. In particular, define (l i k ) −1 j := (L i k ) −1 jj , and set all elements such that |(l i k ) −1 j | ≤ ω to be 0, where ω > 0 is a user defined parameter that must be initialized. The truncated matrix is denoted by Hessian update option 2. Direct update (Algorithm 2). Setting B 0 = 0 in (6) gives which we refer to as the Direct update. Then, we utilize the following learning technique where 0 < β k ≤ 1 is the learning rate. Thus, for the Direct update, the new Hessian approximation is a convex combination of the previous update and the matrix in (8). Note, that for both Option 1 and Option 2, the Hessian approximation B i k+1 is symmetric, since Algorithm 2 Direct update.
select learning rate β k 5:

Iterate update
Note that, at the start of the iterate update step, all the Hessian approximations B i k+1 , and all variables from (4), are available on the main node. Then, the server forms . Now the goal is to compute a search direction p k , of the general form: for some matrix A k . Two specific options for A k are described now.
Search direction option 1. Truncated inverse Hessian approximation (Algorithm 3). Here, A k is taken to be the truncated inverse Hessian approximation |B k+1 | Ω ω −1 . Consider the following.
Definition 1 was proposed in [30] and was used to provide a convergence guarantee for their Nonconvex Newton method (to a local minimum). Firstly, an eigen-decomposition of B k is computed, but with every eigenvalue replaced by its absolute value. Secondly, a thresholding step is applied, so that any eigenvalue (in absolute value) that is smaller (resp. greater) than a user defined threshold ω (resp. Ω) is replaced by ω (resp. Ω). This truncation is crucial for several reasons. Firstly, it ensures B k is well-defined, which leads to stable updates. Secondly, it ensures that after truncation, the resulting matrix will be full-rank and positive definite. Therefore, it guarantees that the following search direction is a decent direction Search direction option 2. FedSONIA (Algorithm 4). FedSONIA is a modification of SONIA [22] that is adapted to the Federated Learning setting. The key idea of SONIA is to utilize curvature information in one subspace and perform a gradient step in orthogonal complement. The intuition is that, by incorporating some curvature information the resulting search direction should be 'better' than a pure gradient direction, but the user has control over the dimension of each subspace, and therefore they have control over the cost of obtaining the curvature information. Truncation (Definition 1) and modified SR1 update (eq. (6)) ensure that the Hessian-approximation is full-rank, positive and well defined, which is crucial to avoid checking condition on the curvature pairs Y T k S k ( Y T k S k for
FedSONIA). To construct the approximation of the Hessian we use (8). Note, that SONIA does not need the Hessian approximation B k itself to commit a step. Instead, it utilizes only Hessian-matrix product Y k and sketching matrix S k .
Following the strategy in [22], apply an economy QR factorization of Y k = Q k R k , so that Q k ∈ R d×m has orthonormal columns and R k ∈ R m×m is upper triangular. Thus, where the columns of V k ∈ R m×m form an orthonormal basis (of eigenvectors), and Λ k ∈ R m×m is a diagonal matrix containing the corresponding eigenvalues. Therefore, has orthonormal columns since Q k has orthonormal columns and V k is an orthogonal matrix. Then, we apply Definition 1 to form the truncated approximation Next, we perform subspace decomposition on the current gradient direction: where Putting this all together, the FedSONIA search direction (similar to [22]) is: One has control over the cost of the curvature information in (14) via the memory size m. Note that this will also affect the communication complexity. Finally, a new search direction p k is computed, which depends on the chosen update strategy (Algorithm 3 or 4) and to compute the new iterate w k+1 via (3). Recall that for both these strategies the resulting search direction p k has the form (10), where A k = (|B k+1 | Ω ω ) −1 for the Truncated inverse Hessian approximation (11), and (14). The process then restarts (from Section 3.2). Our framework is summarized in Algorithm 5.

2:
On i-th machine: 3: sample S k ∈ R d×m ; 4: collect H i k S k , w k from the server; 5: compute to the server.

7:
On the server: 8: sample S k ; 9: collect C i k , M i k , i = 1 . . . n from workers; 10: compute Y i k = C i k + H i k S k ; 11: compute B i k+1 via Algorithm 1 or select learning rate β k and compute B i k+1 via Algorithm 2; 12: form ∇F (w k ), Y k , M k , B k+1 as average over workers of ∇f i (w k ), Y i k , M i k , B i k+1 , i = 1, . . . , n; 13: compute search direction p k via Algorithm 3 or 4; 14: select stepsize α k and set w k+1 = w k + α k p k ; 15: sample S k+1 ∈ R d×m ; 16: send w k , B k+1 S k+1 to all workers. 17: end for

FLECS: Convergence Theory
In this section, convergence theory for our FLECS framework is presented. We provide global convergence results in both the strongly convex, and nonconvex cases. A local convergence result is also presented, which shows local linear convergence of the iterates under strong convexity. We define w 0 to be the initial point, w = arg min w∈R d F (w) and F = F (w ). Assumption 1. The function F (w) is twice continuously differentiable for all w ∈ R d .
We begin by listing the preliminary lemma. Lemma 1. Let Assumption 1 hold. Let A k be defined as in (10) depending on the choice of iterates update. Then, for any k ≥ 0 there exist constants 0 < µ 1 ≤ µ 2 such that µ 1 I A k µ 2 I.
We introduce assumptions and theoretical results for the strongly convex case. Assumption 2. There exist positive constants µ and L such that µI ∇ 2 F (w) LI, ∀w ∈ R d .
The following theorem establishes global linear convergence of FLECS under strong convexity. Theorem 1. Let Assumptions 1 and 2 hold. Then for iterates {w k } generated by Algorithm 5 with We are now ready to present a convergence guarantee which shows local linear convergence for FLECS under strong convexity. Note that, while Theorem 1 shows that FLECS converges linearly under strong convexity, the rate depends on parameters related to the Hessian approximations. The following local rate is independent of problem conditioning.

Theorem 2. Let Assumptions 1 and 2 hold, and w
Then for iterates {w k } generated by Algorithm 5 with Truncated inverse Hessian approximation step (Algorithm 3) with parameters We introduce the assumptions for nonconvex case. Assumption 3. The function F is bounded below by a scalarF . Assumption 4. The gradients of F are L-Lipschitz continuous for all w ∈ R n .
The following result shows that FLECS is convergent when problem (1)

Numerical Experiments
We present numerical experiments for FLECS on a regularized logistic regression problem: are data points on i-th device. We use three datasets from the LIBSVM library [7]: a9a (123 features), gisette-scale (5000 features) and real-sim (20958 features). We use Top-K with k = 4d and random dithering [2] applied to each matrix column with s = 128 levels and ∞-norm as a matrix compressors. The performance of FLECS is compared with FedNL. In our experiments we set regularization parameter µ = 10 −5 , the memory size to m = 16 and use B i k = 0 as the initial Hessian approximation for FLECS and FedNL for random dithering and B i k = ∇f i (w 0 ) for Top-K. Truncation parameters were set to ω = 10 −3 , Ω = 10 8 , and for the FedSONIA update we set ρ = 1 Ω and α = 1. For FLECS we use a Truncated L-SR1 Update (Algorithm 1) and a Direct update (Algorithm 2) with learning rate β = 1 as the Hessian learning techniques. For FedNL we use the same β.
The following three rules were used to compute the search direction p k : (1) a Truncated Inverse Hessian Approximation (Algorithm 3), (2) FedSONIA (Algorithm 4) with ρ k = 1 Ω , and (3) a regularized update where B k+1 = B k + 1 n n i=1 C i k I, where C i k are defined in (4). The last update is motivated by [36]. Note, that in the case of FLECS this update does not guarantee positive definiteness of Hessian approximation B k if m < d, but it can still perform well if m is large enough. For FedNL after random dithering the matrix B k+1 might not be symmetric, so we use 1 2 (B k+1 + B T k+1 ) as Hessian approximation. In this case, we compare algorithms on the number of bits sent to the server per iteration. For Top-K compression, the communication complexity is roughly the same, so we estimate the performance based on the number of Hessian-vector products. For the iterates update (3) we set the step-size α = 1 for all algorithms and datasets except FedSONIA on gisette and real-sim, where we set α = 0.1, as it gives the best performance. Further details specifying algorithm parameters and implementation, as well as additional numerical experiments, can be found in Appendix B.

Conclusion
This work presents a new second order framework for Federated Learning problems. The framework employs sketching and compression to ensure communication costs are low, and Hessian approximations are stored on the central server so that memory requirements for the workers is low. Due to the inclusion of partial approximate second order information, the algorithm enjoys favourable convergence guarantees, and numerical experiments show the practical benefits of our approach.

A Proofs
A.1 Assumptions Assumption 1. The function F is twice continuously differentiable.
Assumption 2. There exist positive constants µ and L such that µI ∇ 2 F (w) LI, ∀w ∈ R d . Assumption 3. The function F is bounded below by a scalarF . Proof. Truncated L-SR1 update. In this case A k = (|B k+1 | Ω ω ) −1 . By spectral decomposition
A.3 Proof of Theorem 1 Theorem 1. Let Assumptions 1, and 2 hold. Then for iterates {w k } generated by Algorithm 5 with where the last inequality is due to the choice of the step-size. By Assumtion 2, we have 2µ(F (w) − F ) ≤ ∇F (w) 2 . Therefore, Recursive application of the above inequality yields the desired result.

by definition of Frobenius norm and the fact that matrices
Theorem 2. Let Assumptions 1 and 2 hold, and w 0 −w * ≤ µ 2 2 , 1 Then for iterates {w k } generated by Algorithm 5 with Truncated inverse Hessian approximation step (Algorithm 3) with parameters α k = α = 1, 0 ≤ ω ≤ µ, Ω ≥ L we have Therefore, by assumptions of the theorem A.5 Proof of Theorem 3 Theorem 3. Let Assumptions1, 3, 4 hold and w 0 be the starting point. Then after T > 0 iterations of Algorithm 5 with 0 < α k = α ≤ µ1 Proof. By (15) Summing both sides of the above inequality from k = 0 to T − 1, we obtain Therefore, we have Dividing (16) by T we conclude

B.1 Top-K Compressor
In this experiment we used Top-K compression with k = 4d on a9a dataset with regularization parameter µ = 10 −5 . We compare FedNL [36] and FLECS in the number of hessian-vector products, since compression cost is roughly the same. For FLECS we set memory size m = 16 and step-size α = 1. For both algorithms we set B i 0 = ∇F (w 0 ) and Hessian approximation rate β = 1. In this experiment we omit initialization cost (computation of the full Hessian at starting point) for both algorithms. In order to compare our framework with DIANA and ADIANA we use random dithering with number of levels s = √ d and p = ∞. For FLECS we set hyperparametes as: m = 1, β = 1, α = 1 and initialize Hessian approximations with 0.
For DIANA and ADIANA we used theoretical parameters L = 1/4 and strong convexity constant µ = 10 −5 . For these methods we used an original code provided by authors [27,43].

B.3 Top-K vs Random Dithering
In this subsection we want to compare Top-K compressor with random dithering for FLECS. We set hyperparametes as: m = 16, β = 1, α = 1 and initialize Hessian approximations with ∇ 2 f (w 0 ). We use Top-K with k = 4d and random dithering with s = 128 and p = ∞, so communication cost per iteration is roughly the same. In this experiment we omit initialization cost (computation of the full Hessian at starting point) for both algorithms.

B.4 Dependence on the Memory Size
Here we compare different memory sizes for FLECS on a9a dataset. We use random dithering with parameters s = 128 and p = ∞. Hyperparametes set as β = 1, α = 1 and initialize Hessian approximations initialized with 0.   Figure 5: Comparison of objective function F (w k ) and the squared norm of gradient ∇F (w k ) 2 for different memory sizes.

C Compressors
FLECS allows several different compression operators. In this section we give definitions and provide examples of possible compressors for our framework.

Definition 2.
A random operator C : R d×m → R d×m satisfying for all X ∈ R d×m is a unbiased compressor operator.
Random dithering for vectors (ω-quantization) [2], applied to each column of the matrix, is an example of unbiased compressors that we used in our experiments.

C.2 Biased compressors.
Definition 3. A random operator C : R d×m → R d×m satisfying for all X ∈ R d×m is a contractive compressor operator.
In our experiments we use Top-K as a contractive compressor.