FedNL: Making Newton-Type Methods Applicable to Federated Learning

Mher SafaryanRustem IslamovXun QianPeter Richtárik

article2022ICML95 citations

Proposes FedNL, a family of communication-efficient second-order optimization methods for federated learning that uses contractive Hessian compression and privacy-preserving local updates to achieve condition-number-independent local convergence.

Listen

Training machine learning models across decentralized, private datasets—known as federated learning—is severely hindered by network communication bottlenecks. While second-order optimization techniques like Newton's method converge in far fewer steps than standard first-order gradient methods, transmitting full second-order curvature matrices (Hessians) over the network is prohibitively expensive. Prior attempts to compress this curvature information required sharing raw user data with a central coordinator, failed to accommodate heterogeneous datasets, and applied only to a narrow class of mathematical models.

The article introduces and evaluates a family of algorithms called Federated Newton Learn (FedNL). The primary objective is to demonstrate that second-order optimization can be made communication-efficient, privacy-preserving, and mathematically robust for general federated learning problems.

The authors develop a framework where client devices locally estimate curvature changes and transmit heavily compressed matrix updates back to a central server. They rigorously derive convergence rates across both unbiased and contractive compression schemes (such as Top-K and Rank-R) and validate their theoretical findings using extensive numerical simulations on benchmark classification datasets (e.g., LibSVM datasets including a1a, a9a, w7a, w8a, and phishing) across varying network sizes and data distributions.

The evaluation yields several key findings in order of importance. First, FedNL achieves fast local convergence rates that are completely independent of the problem's condition number, training dataset size, and compression variance, allowing each iteration to cut optimization error by half locally. Second, communication cost per round is drastically reduced to match standard gradient methods while outperforming leading first-order algorithms (such as ADIANA and DIANA) and distributed Newton baselines (such as DINGO) by multiple orders of magnitude in transmitted bits. Third, the framework seamlessly supports aggressive contractive compressors (like Rank-1) without requiring divergence-correcting error feedback mechanisms. Fourth, FedNL successfully extends to practical deployment constraints, demonstrating high efficiency under partial device participation (FedNL-PP), backtracking line search globalization (FedNL-LS), and bidirectional communication compression (FedNL-BC).

These findings demonstrate that federated systems can achieve the fast convergence of second-order optimization without incurring massive network overhead or compromising client data privacy. By eliminating the dependence on condition numbers and data volume, FedNL mitigates training risks on highly ill-conditioned and heterogeneous real-world networks, enabling substantial reductions in bandwidth costs and operational time.

Decision-makers should consider adopting FedNL-based optimization—particularly FedNL with line search and Rank-1 compression—for distributed systems with high communication latency. Where client availability varies, implementing the partial participation variant (FedNL-PP) provides a robust path forward. Prior to full-scale deployment, teams should conduct pilot benchmarks to assess server-side matrix inversion overhead relative to available hardware.

Confidence in these findings is supported by complete mathematical proofs and consistent numerical validation. However, decision-makers should note that the current analysis is limited to convex and strongly convex problems, and it assumes exact computation of local gradients and Hessians rather than stochastic mini-batches, leaving non-convex deep neural networks for future investigation.

Institut polytechnique de Paris King Abdullah University of Science and Technology Moscow Institute of Physics and Technology communication condition numbers data points FedNL framework Newton-type methods federated learning

Safaryan et al (2022).pdf

Paper: SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, Sai Praneeth Karimireddy et al. (2019). Introduces control-variate techniques for mitigating client drift in federated optimization, providing crucial foundational mechanics for communication-efficient distributed training.
Paper: Federated Learning: Strategies for Improving Communication Efficiency, Jakub Konečný et al. (2016). Establishes foundational structured and sketched compression strategies for uplink communication in federated learning that directly inform compressed federated optimization algorithms.
Paper: QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding, Dan Alistarh et al. (2016). Provides the mathematical groundwork for quantized and compressed gradient methods that underpin communication-efficient distributed optimization frameworks.
Paper: Federated Optimization in Heterogeneous Networks, Tian Li et al. (2018). Formulates the canonical proximal regularized framework for federated optimization under statistical and systems heterogeneity.
Paper: Communication-Efficient Learning of Deep Networks from Decentralized Data, H. B. McMahan et al. (2016). Introduces the standard Federated Averaging framework and decentralized training paradigm that advanced federated second-order methods build upon and optimize.
Paper: Optimizing Neural Networks with Kronecker-factored Approximate Curvature, James Martens et al. (2015). Demonstrates practical second-order curvature approximation and structured matrix factorization, motivating tractable Hessian-based updates in large-scale learning.

No sufficiently relevant recommendations were found.

Cover for FedNL: Making Newton-Type Methods Applicable to Federated Learning

Abstract

Inspired by recent work of Islamov et al (2021), we propose a family of Federated Newton Learn (FedNL) methods, which we believe is a marked step in the direction of making second-order methods applicable to FL. In contrast to the aforementioned work, FedNL employs a different Hessian learning technique which i) enhances privacy as it does not rely on the training data to be revealed to the coordinating server, ii) makes it applicable beyond generalized linear models, and iii) provably works with general contractive compression operators for compressing the local Hessians, such as Top-K or Rank-R, which are vastly superior in practice. Notably, we do not need to rely on error feedback for our methods to work with contractive compressors. Moreover, we develop FedNL-PP, FedNL-CR and FedNL-LS, which are variants of FedNL that support partial participation, and globalization via cubic regularization and line search, respectively, and FedNL-BC, which is a variant that can further benefit from bidirectional compression of gradients and models, i.e., smart uplink gradient and smart downlink model compression. We prove local convergence rates that are independent of the condition number, the number of training data points, and compression variance. Our communication efficient Hessian learning technique provably learns the Hessian at the optimum. Finally, we perform a variety of numerical experiments that show that our FedNL methods have state-of-the-art communication complexity when compared to key baselines.

Topics

communication condition numbers data points federated learning linear models local convergence numerical experiments regularization uplink privacy preserving

Keywords

FedNL framework Newton-type methods federated learning contractive Hessian compression second-order methods efficient Hessian learning gradient compression adaptive learning rates global convergence guarantees

1. Introduction
1.1. First-order methods for FL
1.2. Towards second-order methods for FL
1.3. Desiderata for second-order methods applicable to FL
2. Contributions
2.1. The Newton Learn framework of Islamov et al. (2021)
2.2. Issues with the Newton Learn framework
2.3. Our FedNL framework
3. The Vanilla Federated Newton Learn
3.1. New Hessian learning technique
3.2. Compressing matrices
3.3. Two options for updating the global model
3.4. Local convergence theory
3.5. FedNL and the 'Newton Triangle'
4. Extensions to FedNL
4.1. Partial Participation
4.2. Globalization via Line Search
4.3. Globalization via Cubic Regularization
4.4. Bidirectional Compression
5. Experiments
5.1. Parameter setting
5.2. Local convergence
5.3. Global convergence
5.4. Comparison with NL1
References
A. Theoretical Comparisons with Related Works
B. Extra Experiments
B.1. Data sets
B.2. Parameters setting
B.3. Compression operators
B.3.1. RANDOM DITHERING FOR VECTORS
B.3.2. RANKR COMPRESSION OPERATOR FOR MATRICES
B.3.3. TOPK COMPRESSION OPERATOR FOR MATRICES
B.3.4. RANDK COMPRESSION OPERATOR FOR MATRICES
B.4. Projection onto the cone of positive definite matrices
B.5. The effect of compression
B.6. Comparison of Options 1 and 2
B.7. Comparison of different compression operators
B.8. Comparison of different update rules for Hessians
B.9. Bidirectional compression
B.10. The performance of FedNL-PP
B.11. Comparison with NL1
B.12. Local comparison
B.13. Global comparison
B.14. Effect of statistical heterogeneity
C. Proofs of Results from Section 3
C.1. Auxiliary lemmas
C.2. Proof of Theorem 3.6
C.3. Proof of Lemma 3.7
C.4. Proof of Lemma 3.8
D. Extension: Partial Participation ( FedNL-PP )
D.1. Hessian corrected local gradients g k i
D.2. Importance of compression errors l k i
D.3. Local convergence theory
D.4. Proof of Theorem D.1
D.5. Proof of Lemma D.2
D.6. Proof of Lemma D.3
E. Extension: Globalization via Line Search ( FedNL-LS )
E.1. Line search procedure
E.2. Local convergence theory
E.3. Proof of Theorem E.1
E.4. Proof of Lemma E.2
F. Extension: Globalization via Cubic Regularization ( FedNL-CR )
F.1. Cubic regularization
F.2. Solving the subproblem
F.3. Importance of compression errors l k i
F.4. Global and local convergence theory
F.5. Proof of Theorem F.1
F.6. Proof of Lemma F.2
G. Extension: Bidirectional Compression ( FedNL-BC )
G.1. Model learning technique
G.2. Hessian corrected local gradients
G.3. Local convergence theory
G.4. Proof of Theorem G.4
G.5. Proof of Lemma G.5
G.6. Proof of Lemma G.6
H. Local Quadratic Rate of NEWTON-STAR for General Finite-Sum Problems
I. FedNL and the Newton 'Triangle'
J. Limitations
K. Table of Frequently Used Notation

Knowls

Knowl 1 — FedNL Algorithm for Distributed Second-Order Optimization
algorithm
The Federated Newton Learn (FedNL) algorithm minimizes a distributed empirical risk function $f(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)$ over $x \in \mathbb{R}^d$ across $n$ clients coordinated by a central server. In each round, clients compute their local gradient and local Hessian, compress the difference between the true local Hessian and their current local Hessian estimate using an operator $C_i^k$ , and send the compressed update alongside the gradient and scalar compression error to the server.
Input: Initial iterate $x^0 \in \mathbb{R}^d$ , local Hessian estimates $H_1^0, \dots, H_n^0 \in \mathbb{R}^{d \times d}$ , global Hessian estimate $H^0 = \frac{1}{n} \sum_{i=1}^n H_i^0$ , Hessian learning rate $\alpha \ge 0$ , compression operators $\{C_1^k, \dots, C_n^k\}$
for communication round $k = 0, 1, 2, \dots$ do
    for each client $i = 1, \dots, n$ in parallel do
        Receive $x^k$ from the server
        Compute local gradient $\nabla f_i(x^k)$ and local Hessian $\nabla^2 f_i(x^k)$
        Compute compressed Hessian update $S_i^k = C_i^k(\nabla^2 f_i(x^k) - H_i^k)$
        Compute local Hessian compression error $l_i^k = \|H_i^k - \nabla^2 f_i(x^k)\|_F$
        Send $\nabla f_i(x^k)$ , $S_i^k$ , and $l_i^k$ to the server
        Update local Hessian estimate $H_i^{k+1} = H_i^k + \alpha S_i^k$
    end for
    on server do
        Receive $\nabla f_i(x^k)$ , $S_i^k$ , and $l_i^k$ from all clients $i \in \{1, \dots, n\}$
        Compute $\nabla f(x^k) = \frac{1}{n}\sum_{i=1}^n \nabla f_i(x^k)$
        Compute $S^k = \frac{1}{n}\sum_{i=1}^n S_i^k$
        Compute $l^k = \frac{1}{n}\sum_{i=1}^n l_i^k$
        Update global Hessian estimate $H^{k+1} = H^k + \alpha S^k$
        Option 1: Update model using projected Hessian $x^{k+1} = x^k - [H^k]_\mu^{-1} \nabla f(x^k)$
        Option 2: Update model using error-shifted Hessian $x^{k+1} = x^k - [H^k + l^k I]^{-1} \nabla f(x^k)$
    end on server
end for
Option 1 requires knowledge of the strong convexity parameter $\mu > 0$ and projects $H^k$ onto $\{M \in \mathbb{R}^{d \times d} : M^\top = M, M \succeq \mu I\}$ via $[H^k]_\mu = [H^k - \mu I]_0 + \mu I$ , where $[X]_0 = \sum_{j=1}^d \max\{\lambda_j, 0\} u_j u_j^\top$ is computed via eigenvalue decomposition $X = \sum_{j=1}^d \lambda_j u_j u_j^\top$ . Option 2 does not require $\mu$ and ensures positive definiteness by shifting $H^k$ with the average Frobenius norm error $l^k I$ .
Knowl 2 — Local Convergence Theory of FedNL
theoretical result
Let the average loss $f(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)$ be $\mu$ -strongly convex, and let each local loss $f_i$ have Lipschitz continuous Hessians with constants $L_*$ , $L_F$ , and $L_\infty$ with respect to the spectral, Frobenius, and maximum element norms: $\|\nabla^2 f_i(x) - \nabla^2 f_i(y)\| \le L_* \|x - y\|$ , $\|\nabla^2 f_i(x) - \nabla^2 f_i(y)\|_F \le L_F \|x - y\|$ , and $\max_{j,l} |(\nabla^2 f_i(x) - \nabla^2 f_i(y))_{jl}| \le L_\infty \|x - y\|$ for all $x, y \in \mathbb{R}^d$ .

Define constants $(A, B)$ based on the compression operator class:

$(A, B) := \begin{cases} (\alpha^2, \alpha) & \text{if } C_i^k \in \mathbb{C}(\delta) \text{ and } \alpha = 1 - \sqrt{1-\delta} \\ (\delta/4, 6/\delta - 7/2) & \text{if } C_i^k \in \mathbb{C}(\delta) \text{ and } \alpha = 1 \\ (\alpha, \alpha) & \text{if } C_i^k \in \mathbb{B}(\omega) \text{ and } 0 < \alpha \le \frac{1}{\omega+1} \end{cases}$

and $(C, D) := (2, L_*^2)$ for Option 1, or $(C, D) := (8, (L_* + 2L_F)^2)$ for Option 2. Define the Lyapunov function $\Phi^k := \mathcal{H}^k + 6BL_F^2 \|x^k - x^*\|^2$ , where $\mathcal{H}^k := \frac{1}{n}\sum_{i=1}^n \|H_i^k - \nabla^2 f_i(x^*)\|_F^2$ and $x^*$ is the unique minimizer of $f$ .

If $\|x^0 - x^*\| \le \frac{\mu}{\sqrt{2D}}$ and $\mathcal{H}^k \le \frac{\mu^2}{4C}$ for all $k \ge 0$ , FedNL achieves:
1. Deterministic linear convergence for iterates:
$\|x^k - x^*\|^2 \le \frac{1}{2^k} \|x^0 - x^*\|^2$
1. Linear convergence of the Lyapunov function:
$\mathbb{E}[\Phi^k] \le \left(1 - \min\left\{A, \frac{1}{3}\right\}\right)^k \Phi^0$
1. Local superlinear rate of iterate convergence:
$\mathbb{E}\left[\frac{\|x^{k+1} - x^*\|^2}{\|x^k - x^*\|^2}\right] \le \left(1 - \min\left\{A, \frac{1}{3}\right\}\right)^k \left(C + \frac{D}{12BL_F^2}\right) \frac{\Phi^0}{\mu^2}$

Under contractive compression $C_i^k \in \mathbb{C}(\delta)$ , the condition $\mathcal{H}^k \le \frac{\mu^2}{4C}$ holds for all $k \ge 0$ provided $\|x^0 - x^*\| \le \min\left\{\frac{\mu}{2L_F}\sqrt{\frac{A}{BC}}, \frac{\mu}{\sqrt{2D}}\right\}$ and $\|H_i^0 - \nabla^2 f_i(x^*)\|_F \le \frac{\mu}{2\sqrt{C}}$ . Under unbiased compression $C_i^k \in \mathbb{B}(\omega)$ with convex combination entries, the condition holds if $\|x^0 - x^*\| \le \frac{\mu}{\sqrt{D + 4Cd^2 L_\infty^2}}$ .
Knowl 3 — FedNL-PP Algorithm for Partial Participation
algorithm
FedNL-PP extends FedNL to settings where only a random subset $S^k \subset \{1, \dots, n\}$ of $\tau$ clients participates at each round. To account for client inactivity, each device $i$ maintains a local copy $w_i^k$ representing the global model from the most recent iteration in which client $i$ was active, and computes a Hessian-corrected local gradient $g_i^k = (H_i^k + l_i^k I)w_i^k - \nabla f_i(w_i^k)$ .
Input: Hessian learning rate $\alpha > 0$ , compression operators $\{C_1^k, \dots, C_n^k\}$ , number of participating devices $\tau \in \{1, \dots, n\}$
Initialization: For all $i \in \{1, \dots, n\}$ : $w_i^0 = x^0 \in \mathbb{R}^d$ , $H_i^0 \in \mathbb{R}^{d \times d}$ , $l_i^0 = \|H_i^0 - \nabla^2 f_i(w_i^0)\|_F$ , $g_i^0 = (H_i^0 + l_i^0 I)w_i^0 - \nabla f_i(w_i^0)$
Server initial state: $H^0 = \frac{1}{n} \sum_{i=1}^n H_i^0$ , $l^0 = \frac{1}{n} \sum_{i=1}^n l_i^0$ , $g^0 = \frac{1}{n} \sum_{i=1}^n g_i^0$
for communication round $k = 0, 1, 2, \dots$ do
    on server do
        Update global model $x^{k+1} = [H^k + l^k I]^{-1} g^k$
        Sample subset $S^k \subseteq \{1, \dots, n\}$ of cardinality $\tau$ uniformly at random
        Send $x^{k+1}$ to devices $i \in S^k$
    end on server
    for each device $i = 1, \dots, n$ in parallel do
        if $i \in S^k$ then
             $w_i^{k+1} = x^{k+1}$
             $H_i^{k+1} = H_i^k + \alpha C_i^k(\nabla^2 f_i(w_i^{k+1}) - H_i^k)$
             $l_i^{k+1} = \|H_i^{k+1} - \nabla^2 f_i(w_i^{k+1})\|_F$
             $g_i^{k+1} = (H_i^{k+1} + l_i^{k+1} I)w_i^{k+1} - \nabla f_i(w_i^{k+1})$
            Send $C_i^k(\nabla^2 f_i(w_i^{k+1}) - H_i^k)$ , $l_i^{k+1} - l_i^k$ , and $g_i^{k+1} - g_i^k$ to server
        else
             $w_i^{k+1} = w_i^k, H_i^{k+1} = H_i^k, l_i^{k+1} = l_i^k, g_i^{k+1} = g_i^k$
        end if
    end for
    on server do
        Receive updates from participating devices $i \in S^k$
         $g^{k+1} = g^k + \frac{1}{n} \sum_{i \in S^k} (g_i^{k+1} - g_i^k)$
         $H^{k+1} = H^k + \frac{\alpha}{n} \sum_{i \in S^k} C_i^k(\nabla^2 f_i(w_i^{k+1}) - H_i^k)$
         $l^{k+1} = l^k + \frac{1}{n} \sum_{i \in S^k} (l_i^{k+1} - l_i^k)$
    end on server
end for
Knowl 4 — Local Linear Convergence of FedNL-PP under Partial Participation
theoretical result
Let Assumption 3.1 hold (with Hessian Lipschitz constants $L_*$ , $L_F$ , $L_\infty$ ) and assume each local loss function $f_i$ is $\mu$ -convex on $\mathbb{R}^d$ . Define the average stale model error $W^k := \frac{1}{n}\sum_{i=1}^n \|w_i^k - x^*\|^2$ , the average Hessian error $\mathcal{H}^k := \frac{1}{n}\sum_{i=1}^n \|H_i^k - \nabla^2 f_i(x^*)\|_F^2$ , and the Lyapunov function $\Psi^k := \mathcal{H}^k + B L_F^2 W^k$ .

Suppose the initialization satisfies $\|x^0 - x^*\|^2 \le \frac{\mu^2}{4(L_* + 2L_F)^2}$ and $\mathcal{H}^k \le \frac{\mu^2}{64}$ for all $k \ge 0$ . Then FedNL-PP with $\tau$ active clients per round converges linearly according to:

$\|x^{k+1} - x^*\|^2 \le W^k, \quad \mathbb{E}[W^k] \le \left(1 - \frac{3\tau}{4n}\right)^k W^0$

$\mathbb{E}[\Psi^k] \le \left(1 - \frac{\tau}{n} \min\left\{A, \frac{1}{2}\right\}\right)^k \Psi^0$

$\mathbb{E}\left[\frac{\|x^{k+1} - x^*\|^2}{W^k}\right] \le \left(1 - \min\left\{A, \frac{1}{2}\right\}\right)^k \left(\frac{(L_* + 2L_F)^2}{2BL_F^2} + 8\right) \frac{\Psi^0}{\mu^2}$

where $(A, B)$ are the compressor parameters defined in (5). Under contractive compressors $C_i^k \in \mathbb{C}(\delta)$ , the condition $\mathcal{H}^k \le \frac{\mu^2}{64}$ is guaranteed for all $k \ge 0$ if $\|x^0 - x^*\|^2 \le \min\left\{\frac{A\mu^2}{16BL_F^2}, \frac{\mu^2}{4(L_* + 2L_F)^2}\right\}$ and $\|H_i^0 - \nabla^2 f_i(x^*)\|_F^2 \le \frac{\mu^2}{64}$ .
Knowl 5 — FedNL-LS Algorithm for Line Search Globalization
algorithm
FedNL-LS equips the FedNL framework with a backtracking line search procedure on the empirical loss function to achieve global convergence. The search direction is fixed as $d^k = - [H^k]_\mu^{-1} \nabla f(x^k)$ , and the server determines the smallest step integer $s \ge 0$ providing sufficient decrease in $f$ .
Input: Hessian learning rate $\alpha \ge 0$ , compression operators $\{C_1^k, \dots, C_n^k\}$ , line search parameters $c \in (0, 1/2]$ and $\gamma \in (0, 1)$
Initialization: $x^0 \in \mathbb{R}^d$ , $H_1^0, \dots, H_n^0 \in \mathbb{R}^{d \times d}$ , $H^0 = \frac{1}{n}\sum_{i=1}^n H_i^0$
for communication round $k = 0, 1, 2, \dots$ do
    for each client $i = 1, \dots, n$ in parallel do
        Receive $x^k$ from server
        Compute local function value $f_i(x^k)$ , gradient $\nabla f_i(x^k)$ , and Hessian $\nabla^2 f_i(x^k)$
        Send $f_i(x^k)$ , $\nabla f_i(x^k)$ , and $S_i^k = C_i^k(\nabla^2 f_i(x^k) - H_i^k)$ to the server
        Update local Hessian estimate $H_i^{k+1} = H_i^k + \alpha S_i^k$
    end for
    on server do
        Receive $f_i(x^k)$ , $\nabla f_i(x^k)$ , and $S_i^k$ from all clients
        Compute $f(x^k) = \frac{1}{n}\sum_{i=1}^n f_i(x^k)$ and $\nabla f(x^k) = \frac{1}{n}\sum_{i=1}^n \nabla f_i(x^k)$
        Compute $S^k = \frac{1}{n}\sum_{i=1}^n S_i^k$
        Compute search direction $d^k = - [H^k]_\mu^{-1} \nabla f(x^k)$
        Find the smallest integer $s \ge 0$ such that $f(x^k + \gamma^s d^k) \le f(x^k) + c \gamma^s \langle \nabla f(x^k), d^k \rangle$
        Update global model $x^{k+1} = x^k + \gamma^s d^k$
        Update global Hessian estimate $H^{k+1} = H^k + \alpha S^k$
    end on server
end for
Knowl 6 — Global Linear Convergence of FedNL-LS
theoretical result
Let $f(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)$ be $L$ -smooth and $\mu$ -strongly convex on $\mathbb{R}^d$ . Assume that $\tilde{L} := \sup_{k \ge 0} \|H^k\|$ is finite. Then the FedNL-LS algorithm with line search parameters $c = \gamma = 1/2$ converges globally linearly with the rate:

$f(x^{k+1}) - f(x^*) \le \left(1 - \frac{\mu}{L} \min\left\{\frac{\mu}{\tilde{L}}, 1\right\}\right)^k (f(x^0) - f(x^*))$

For level set radius $R := \sup\{\|x - x^*\| : f(x) \le f(x^0)\}$ , the uniform upper bound $\tilde{L}$ is bounded by:
- $\tilde{L} \le \|\nabla^2 f(x^*)\| + \|H_i^0 - \nabla^2 f_i(x^*)\|_F + \sqrt{\frac{B}{A}} L_F R$ when $C_i^k \in \mathbb{C}(\delta)$ with $\alpha = 1 - \sqrt{1-\delta}$ or $\alpha = 1$ .
- $\tilde{L} \le d L_\infty R + \|\nabla^2 f(x^*)\|$ when $C_i^k \in \mathbb{B}(\omega)$ with $\alpha \le \frac{1}{\omega+1}$ and convex combination entry updates.
Knowl 7 — FedNL-CR Algorithm for Cubic Regularization Globalization
algorithm
FedNL-CR achieves global convergence by minimizing a cubic regularized model of the loss function at each iteration using the shifted global Hessian $H^k + l^k I$ .
Input: Hessian learning rate $\alpha \ge 0$ , compression operators $\{C_1^k, \dots, C_n^k\}$ , Lipschitz constant of the Hessian $L_* \ge 0$
Initialization: $x^0 \in \mathbb{R}^d$ , $H_1^0, \dots, H_n^0 \in \mathbb{R}^{d \times d}$ , $H^0 = \frac{1}{n}\sum_{i=1}^n H_i^0$
for communication round $k = 0, 1, 2, \dots$ do
    for each client $i = 1, \dots, n$ in parallel do
        Receive $x^k$ from the server
        Compute local gradient $\nabla f_i(x^k)$ and local Hessian $\nabla^2 f_i(x^k)$
        Compute $S_i^k = C_i^k(\nabla^2 f_i(x^k) - H_i^k)$ and $l_i^k = \|H_i^k - \nabla^2 f_i(x^k)\|_F$
        Send $\nabla f_i(x^k)$ , $S_i^k$ , and $l_i^k$ to the server
        Update local Hessian estimate $H_i^{k+1} = H_i^k + \alpha S_i^k$
    end for
    on server do
        Receive $\nabla f_i(x^k)$ , $S_i^k$ , and $l_i^k$ from all clients
        Compute $\nabla f(x^k) = \frac{1}{n}\sum_{i=1}^n \nabla f_i(x^k)$
        Compute $S^k = \frac{1}{n}\sum_{i=1}^n S_i^k$ and $l^k = \frac{1}{n}\sum_{i=1}^n l_i^k$
        Solve subproblem $h^k = \arg\min_{h \in \mathbb{R}^d} \left\{ \langle \nabla f(x^k), h \rangle + \frac{1}{2} \langle (H^k + l^k I)h, h \rangle + \frac{L_*}{6} \|h\|^3 \right\}$
        Update global model $x^{k+1} = x^k + h^k$
        Update global Hessian estimate $H^{k+1} = H^k + \alpha S^k$
    end on server
end for
Knowl 8 — Global and Local Convergence Theory of FedNL-CR
theoretical result
Let Assumption 3.1 hold, and assume $l := \sup_{k \ge 0} l^k$ is finite, where $R := \sup\{\|x - x^*\| : f(x) \le f(x^0)\}$ .
1. Global convex rate ( $\mu = 0$ ): For general convex functions, FedNL-CR converges globally at a sublinear rate:
$f(x^k) - f(x^*) \le \frac{9l R^2}{k} + \frac{9L_* R^3}{k^2} + \frac{3(f(x^0) - f(x^*))}{k^3}$
1. Global strongly convex rate ( $\mu > 0$ ): An $\varepsilon$ -suboptimal solution $f(x^k) - f(x^*) \le \varepsilon$ is reached within:
$\mathcal{O}\left(\left(\frac{l}{\mu} + \sqrt{\frac{L_* R}{\mu}} + 1\right) \log\frac{f(x^0) - f(x^*)}{\varepsilon}\right) \text{ iterations}$
1. Local fast rates: If $\|x^0 - x^*\|^2 \le \frac{\mu^2}{20(L_*^2 + 8L_F^2)}$ and $\mathcal{H}^k \le \frac{\mu^2}{160}$ for all $k \ge 0$ , FedNL-CR recovers the local linear and superlinear rates of FedNL.
The supremum $l$ is bounded by $l \le \sqrt{\mathcal{H}^0} + \left(1 + \sqrt{\frac{B}{A}}\right) L_F R$ for contractive compressors $C_i^k \in \mathbb{C}(\delta)$ , and by $l \le (d L_\infty + L_F)R$ for unbiased compressors $C_i^k \in \mathbb{B}(\omega)$ .
Knowl 9 — FedNL-BC Algorithm for Bidirectional Compression
algorithm
FedNL-BC enables simultaneous compression of uplink gradients (using Bernoulli trial sampling with probability $p \in (0, 1]$ ), uplink Hessians (using compressors $C_i^k$ ), and downlink model updates (using server compression operator $C_M^k$ ). Clients use a Hessian-corrected gradient $g_i^k = H_i^k(z^k - w^k) + \nabla f_i(w^k)$ when gradients are not computed.
Input: Hessian learning rate $\alpha \ge 0$ , model learning rate $\eta \ge 0$ , gradient sending probability $p \in (0, 1]$ , compression operators $\{C_1^k, \dots, C_n^k\}$ and $C_M^k$
Initialization: $x^0 = w^0 = z^0 \in \mathbb{R}^d$ , $H_1^0, \dots, H_n^0 \in \mathbb{R}^{d \times d}$ , $H^0 = \frac{1}{n}\sum_{i=1}^n H_i^0$ , $\xi^0 = 1$
for communication round $k = 0, 1, 2, \dots$ do
    for each device $i = 1, \dots, n$ in parallel do
        Receive $\xi^k$ from server
        if $\xi^k == 1$ then
            Compute local gradient $\nabla f_i(z^k)$ and send to server
             $g_i^k = \nabla f_i(z^k)$ , $w^{k+1} = z^k$
        else
             $g_i^k = H_i^k(z^k - w^k) + \nabla f_i(w^k)$ , $w^{k+1} = w^k$
        end if
        Compute local Hessian $\nabla^2 f_i(z^k)$
        Send $S_i^k = C_i^k(\nabla^2 f_i(z^k) - H_i^k)$ and $l_i^k = \|\nabla^2 f_i(z^k) - H_i^k\|_F$ to server
        Update local Hessian estimate $H_i^{k+1} = H_i^k + \alpha S_i^k$
    end for
    on server do
        Receive $g_i^k$ , $S_i^k$ , and $l_i^k$ from all devices
         $g^k = \frac{1}{n}\sum_{i=1}^n g_i^k, S^k = \frac{1}{n}\sum_{i=1}^n S_i^k, l^k = \frac{1}{n}\sum_{i=1}^n l_i^k$
        Option 1: $x^{k+1} = z^k - [H^k]_\mu^{-1} g^k$
        Option 2: $x^{k+1} = z^k - [H^k + l^k I]^{-1} g^k$
        Update global Hessian estimate $H^{k+1} = H^k + \alpha S^k$
        Compute compressed model update $s^k = C_M^k(x^{k+1} - z^k)$ and send to all devices
        Update learned global model $z^{k+1} = z^k + \eta s^k$
        Sample $\xi^{k+1} \sim \text{Bernoulli}(p)$ and broadcast to all devices
    end on server
    for each device $i = 1, \dots, n$ in parallel do
        Receive $s^k$ from server and update local copy $z^{k+1} = z^k + \eta s^k$
    end for
end for
Knowl 10 — Local Linear Convergence of FedNL-BC
theoretical result
Let Assumption 3.1 hold. Let $C_M^k$ and $\eta$ have parameters $(A_M, B_M)$ defined by:

$(A_M, B_M) := \begin{cases} (\eta^2, \eta) & \text{if } C_M^k \in \mathbb{C}(\delta_M) \text{ and } \eta = 1 - \sqrt{1-\delta_M} \\ (\delta_M/4, 6/\delta_M - 7/2) & \text{if } C_M^k \in \mathbb{C}(\delta_M) \text{ and } \delta_M = 1 \\ (\eta, \eta) & \text{if } C_M^k \in \mathbb{B}(\omega_M) \text{ and } 0 < \eta \le \frac{1}{\omega_M+1} \end{cases}$

Let $(C_M, D_M) := (24, 8L_F^2 + 9/4L_*^2)$ for Option 1, and $(C_M, D_M) := (32, 16L_F^2 + 9/4L_*^2)$ for Option 2. Define $E_3 := 16L_F^2 + 8L_*^2$ , $\mathcal{H}^k := \frac{1}{n}\sum_{i=1}^n \|H_i^k - \nabla^2 f_i(x^*)\|_F^2$ , and the Lyapunov function $\Phi^k := \|z^k - x^*\|^2 + \frac{A_M}{3p}\|w^k - x^*\|^2$ .

If $\mathcal{H}^k \le \frac{A_M}{B_M}\frac{\mu^2}{9C_M}$ and $\|z^k - x^*\|^2 \le \frac{A_M}{B_M}\frac{\mu^2}{9E_3}$ for all $k \ge 0$ , FedNL-BC achieves the local linear convergence rate:

$\mathbb{E}[\Phi^k] \le \left(1 - \min\left\{\frac{A_M}{3}, \frac{p}{2}\right\}\right)^k \Phi^0$

For contractive compressors, this neighborhood condition holds for all $k \ge 0$ provided $\mathcal{H}^0 \le \frac{A_M}{B_M}\frac{\mu^2}{9C_M}$ and $\|z^0 - x^*\| \le \min\left\{\frac{A_M}{B_M}\frac{\mu^2}{9E_3}, \frac{A}{BL_F^2}\frac{A_M}{B_M}\frac{\mu^2}{9C_M}\right\}$ .
Knowl 11 — Newton Zero Method and the Newton Triangle
model/method
Newton Zero (N0) is a simplified second-order method obtained as a special case of FedNL by setting $C_i^k \equiv 0$ , $\alpha = 0$ , and initializing $H_i^0 = \nabla^2 f_i(x^0)$ for all $i \in \{1, \dots, n\}$ . The resulting master iteration rule is:

$x^{k+1} = x^k - [\nabla^2 f(x^0)]^{-1} \nabla f(x^k), \quad k \ge 0$

N0 requires sending the full Hessian matrix only once at iteration $k=0$ , and thereafter communicates only standard $\mathcal{O}(d)$ gradient vectors per round. It attains a condition-number-independent local linear rate:

$\|x^k - x^*\|^2 \le \frac{1}{2^k} \|x^0 - x^*\|^2$

N0, classical Newton (N), and Newton Star (NS: $x^{k+1} = x^k - [\nabla^2 f(x^*)]^{-1}\nabla f(x^k)$ ) form the vertices of the 'Newton Triangle' over three optimization desiderata:
1. $\mathcal{O}(d)$ communication cost per communication round
2. Practical implementability (does not require unobservable optimal quantities)
3. Local quadratic convergence rate
Each vertex method satisfies exactly two properties: classical Newton satisfies (2+3), Newton Star satisfies (1+3), and Newton Zero satisfies (1+2). FedNL interpolates among all three vertices by learning $\nabla^2 f(x^*)$ adaptively with $\mathcal{O}(d)$ communication.
Knowl 12 — Contractive and Unbiased Matrix Compression Operators
definition
Compression operators applied to $d \times d$ matrix Hessian shifts $\nabla^2 f_i(x^k) - H_i^k$ are categorized into two classes:
1. Unbiased Compressors $\mathbb{B}(\omega)$ : (Possibly randomized) mappings $C : \mathbb{R}^{d \times d} \to \mathbb{R}^{d \times d}$ with variance parameter $\omega \ge 0$ satisfying: $\mathbb{E}[C(M)] = M, \quad \mathbb{E}[\|C(M) - M\|_F^2] \le \omega \|M\|_F^2, \quad \forall M \in \mathbb{R}^{d \times d}$ Example: Matrix Rand- $K$ selects a uniform random subset $S_K$ of $K$ matrix entries and scales them by $d^2/K$ , yielding $\omega = d^2/K - 1$ .
2. Deterministic Contractive Compressors $\mathbb{C}(\delta)$ : Operators $C : \mathbb{R}^{d \times d} \to \mathbb{R}^{d \times d}$ with contraction parameter $\delta \in [0, 1]$ satisfying: $\|C(M)\|_F \le \|M\|_F, \quad \|C(M) - M\|_F^2 \le (1 - \delta) \|M\|_F^2, \quad \forall M \in \mathbb{R}^{d \times d}$ Examples:
- Rank- $R$ Compressor: Keeps the top $R$ singular components $C(X) = \sum_{j=1}^R \sigma_j u_j v_j^\top$ from SVD $X = \sum_{j=1}^d \sigma_j u_j v_j^\top$ , giving $\delta = R/d$ . For symmetric $X$ , $u_j = v_j$ and symmetry is preserved.
- Matrix Top- $K$ : Retains the $K$ largest entries of $X$ in magnitude, giving $\delta = K/d^2$ .
Unlike first-order methods that require error feedback mechanisms to prevent biased contractive compressors from diverging, the FedNL framework works provably with general contractive compressors without error feedback.

Knowl 13 — Theoretical Communication Complexity Comparison

data/table

The table compares the theoretical communication complexity (number of communication rounds $\times$ communication cost per round) required to reach $\varepsilon$ -accuracy across first- and second-order distributed optimization methods. $\kappa = L/\mu$ denotes the condition number, $d$ the model dimension, and $n$ the number of clients.

Method	# Communication Rounds	Comm. Cost / Round	Communication Complexity
Gradient Descent	$\mathcal{O}(\kappa \log \frac{1}{\varepsilon})$	$\mathcal{O}(d)$	$\mathcal{O}(d\kappa \log \frac{1}{\varepsilon})$
ADIANA	$\mathcal{O}\left(\left(d + \sqrt{\kappa} + \sqrt{\frac{d}{n}} + \sqrt[4]{\frac{d}{n}d\kappa}\right)\log \frac{1}{\varepsilon}\right)$	$\mathcal{O}(1)$	$\mathcal{O}\left(\left(d + \sqrt{\kappa} + \sqrt{\frac{d}{n}} + \sqrt[4]{\frac{d}{n}d\kappa}\right)\log \frac{1}{\varepsilon}\right)$
Newton	$\mathcal{O}(\log\log \frac{1}{\varepsilon})$	$\mathcal{O}(d^2)$	$\mathcal{O}(d^2 \log\log \frac{1}{\varepsilon})$
NL	$\mathcal{O}\left(\sqrt{\text{\#data}} \sqrt{\log \frac{1}{\varepsilon}}\right)$	$\mathcal{O}(d)$	$\mathcal{O}\left(d \sqrt{\text{\#data}} \sqrt{\log \frac{1}{\varepsilon}}\right)$
FedNL (linear rate)	$\mathcal{O}(\log \frac{1}{\varepsilon})$	$\mathcal{O}(d)$	$\mathcal{O}(d \log \frac{1}{\varepsilon})$
FedNL (superlinear rate)	$\mathcal{O}\left(\sqrt{d}\sqrt{\log \frac{1}{\varepsilon}}\right)$	$\mathcal{O}(d)$	$\mathcal{O}\left(d\sqrt{d}\sqrt{\log \frac{1}{\varepsilon}}\right)$

FedNL achieves lower communication complexity than classical Newton whenever $d > \frac{\log(1/\varepsilon)}{(\log\log(1/\varepsilon))^2}$ (e.g., $d > 10$ for $\varepsilon = 10^{-10}$ ). FedNL outperforms Gradient Descent when $\kappa > \frac{\sqrt{d}}{\sqrt{\log(1/\varepsilon)}}$ , and outperforms ADIANA when $\kappa > d^3$ or when $\varepsilon$ is sufficiently small due to the $\sqrt{\log(1/\varepsilon)}$ dependence.

Knowl 14 — Empirical Communication Efficiency and Robustness to Data Heterogeneity
empirical result
FedNL and its variants were evaluated on $\ell_2$ -regularized logistic regression ( $f_i(x) = \frac{1}{m}\sum_{j=1}^m \log(1 + \exp(-b_{ij} a_{ij}^\top x)) + \frac{\lambda}{2}\|x\|^2$ ) on LibSVM benchmarks (a1a, a9a, w7a, w8a, phishing, madelon) and synthetic datasets with $\lambda \in \{10^{-3}, 10^{-4}\}$ :
1. Local and Global Performance: FedNL and N0 outperform first-order methods (GD, GD with line search, DIANA with random dithering $s=\sqrt{d}$ , ADIANA with random dithering $s=\sqrt{d}$ , Shifted Local GD) and the distributed second-order baseline DINGO by multiple orders of magnitude in communicated bits per node to reach $f(x^k) - f(x^*) \le 10^{-15}$ , even when accounting for the full Hessian communication at initialization.
2. Globalization Comparison: FedNL-LS (backtracking line search) demonstrates substantially better communication efficiency than FedNL-CR (cubic regularization) and DINGO when initialized far from the optimum.
3. Matrix Compressors: Among Hessian compression operators, Rank- $R$ with $R=1$ yields superior communication efficiency compared to Top- $K$ ( $K=d$ ), PowerSGD ( $R=1$ ), and NL1 with Rand- $K$ ( $K=1$ ).
4. Partial Participation: FedNL-PP significantly outperforms Artemis across various active device fractions $\tau \in \{0.2n, 0.4n, 0.8n\}$ .
5. Robustness to Heterogeneity: On synthetic datasets with increasing statistical data heterogeneity (from IID to Synthetic $(\alpha, \beta)$ with $\alpha=\beta=1$ ), the performance gap between FedNL and first-order baselines as well as DINGO widens dramatically, demonstrating high robustness to non-IID data distributions.
Knowl 15 — Limitations of the FedNL Framework
limitation
The authors identify four principal limitations of the FedNL methods and theoretical analyses:
1. Convexity Restriction: Theoretical guarantees are established only for general convex (sublinear rate for FedNL-CR) and strongly convex objectives. Non-convex loss landscapes are not covered.
2. Deterministic Oracles: The convergence analysis assumes exact local gradient and exact local Hessian evaluations across participating clients; stochastic gradient or stochastic Hessian oracles are not analyzed.
3. Disjoint Algorithmic Extensions: Individual extensions (compressed communication, partial participation, line search globalization, cubic regularization globalization, bidirectional compression) are formulated and analyzed as separate algorithms rather than unified under a single master algorithm.
4. Rudimentary Privacy: The privacy protection mechanism prevents direct transmission of raw training data points to the server, but does not provide formal differential privacy guarantees.

Coverage note — None was omitted; all primary contributions—including the base FedNL algorithm, the four extensions (FedNL-PP, FedNL-LS, FedNL-CR, FedNL-BC), the Newton Zero method, matrix compression definitions, convergence proofs/theorems, complexity comparisons, empirical evaluations, and limitations—are fully covered. Proof derivations and intermediate auxiliary lemmas were omitted as required by the knowl extraction guidelines.

References

1.Alimisis, F., Davies, P., and Alistarh, D. Communication-efficient distributed optimization with quantized preconditioners. In International Conference on Machine Learning (ICML), 2021.
2.Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD: Communication-efficient SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709–1720, 2017.
3.Beck, A. Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB. Society for Industrial and Applied Mathematics, USA, 2014. ISBN 1611973643.
4.Beznosikov, A., Horváth, S., Richtárik, P., and Safaryan, M. On biased compression for distributed learning. arXiv preprint arXiv:2002.12410, 2020.
5.Chang, C.-C. and Lin, C.-J. LibSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST), 2(3):1–27, 2011.
6.Chen, W., Horváth, S., and Richtárik, P. Optimal client sampling for federated learning. arXiv preprint arXiv:2010.13723, 2020.
7.Crane, R. and Roosta, F. Dingo: Distributed newton-type method for gradient-norm optimization. In Advances in Neural Information Processing Systems, volume 32, pp. 9498–9508, 2019.
8.Gorbunov, E., Hanzely, F., and Richtárik, P. A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In The 23rd International Conference on Artificial Intelligence and Statistics, 2020a.
9.Gorbunov, E., Kovalev, D., Makarenko, D., and Richtárik, P. Linearly converging error compensated SGD. In 34th Conference on Neural Information Processing Systems (NeurIPS 2020), 2020b.
10.Gorbunov, E., Burlachenko, K., Li, Z., and Richtárik, P. MARINA: Faster non-convex distributed learning with compression. arXiv preprint arXiv:2102.07845, 2021a.
11.Gorbunov, E., Hanzely, F., and Richtárik, P. Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021b.
12.Gower, R. M., Loizou, N., Qian, X., Sailanbayev, A., Shulgin, E., and Richtárik, P. SGD: General analysis and improved rates. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5200–5209, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
13.Horváth, S., Kovalev, D., Mishchenko, K., Stich, S., and Richtárik, P. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:1904.05115, 2019.
14.Islamov, R., Qian, X., and Richtárik, P. Distributed second order methods with fast rates and compressed communication. arXiv preprint arXiv:2102.07158, 2021.
15.Kairouz et al, P. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977, 2019.
16.Karimireddy, S. P., Rebjock, Q., Stich, S., and Jaggi, M. Error feedback fixes SignSGD and other gradient compression schemes. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. 3252–3261, 2019.
17.Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. In International Conference on Machine Learning (ICML), 2020.
18.Khaled, A., Mishchenko, K., and Richtárik, P. Tighter theory for local SGD on identical and heterogeneous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.
19.Khirirat, S., Feyzmahdavian, H. R., and Johansson, M. Distributed learning with compressed gradients. arXiv preprint arXiv:1806.06573, 2018.
20.Konečný, J., McMahan, H. B., Ramage, D., and Richtárik, P. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02527, 2016a.
21.Konečný, J., McMahan, H. B., Yu, F., Richtárik, P., Suresh, A. T., and Bacon, D. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016b.
22.Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. Federated optimization in heterogeneous networks. arXiv preprint arXiv:1812.06127, 2018.
23.Li, T., Sahu, A. K., Talwalkar, A., and Smith, V. Federated learning: challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50–60, 2020a. doi: 10.1109/MSP.2020.2975749.
24.Li, Z., Kovalev, D., Qian, X., and Richtárik, P. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, 2020b.
25.Liu, X., Li, Y., Tang, J., and Yan, M. A double residual compression algorithm for efficient distributed learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
26.Malitsky, Y. and Mishchenko, K. Adaptive gradient descent without descent. In International Conference on Machine Learning (ICML), 2019.
27.McMahan, H. B., Moore, E., Ramage, D., Hampson, S., and Agüera y Arcas, B. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
28.Mishchenko, K., Gorbunov, E., Takáč, M., and Richtárik, P. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09269, 2019.
29.Mishchenko, K., Khaled, A., and Richtárik, P. Proximal and federated random reshuffling. arXiv preprint arXiv:2102.06704, 2021a.
30.Mishchenko, K., Wang, B., Kovalev, D., and Richtárik, P. IntSGD: Floatless compression of stochastic gradients. arXiv preprint arXiv:2102.08374, 2021b.
31.Philippenko, C. and Dieuleveut, A. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006.14591, 2021.
32.Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečný, J., Kumar, S., and McMahan, H. B. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
33.Reddi, S. J., Konečný, J., Richtárik, P., Póczos, B., and Smola, A. J. AIDE: Fast and communication efficient distributed optimization. CoRR, abs/1608.06879, 2016.
34.Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
35.Shamir, O., Srebro, N., and Zhang, T. Communication-effcient distributed optimization using an approximate newton-type method. In Proceedings of the 31th International Conference on Machine Learning, volume 32, pp. 1000–1008, 2014.
36.Stich, S. U. Local SGD converges fast and communicates little. In International Conference on Learning Representations (ICLR), 2020.
37.Stich, S. U., Cordonnier, J.-B., and Jaggi, M. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
38.Vogels, T., Karimireddy, S. P., and Jaggi, M. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
39.Wang, S., abd Peng Xu, F. R., and Mahoney, M. W. GIANT: Globally improved approximate Newton method for distributed optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
40.Xie, C., Koyejo, O., Gupta, I., and Lin, H. Local AdaAlter: Communication-efficient stochastic gradient descent with adaptive learning rates. arXiv preprint arXiv:1911.09030, 2019.
41.Zhang, J., You, K., and Baş̧ar, T. Achieving globally superlinear convergence for distributed optimization with adaptive newton method. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 2329–2334, 2020. doi: 10.1109/CDC42340.2020.9304321.
42.Zhang, Y. and Lin, X. Disco: Distributed optimization for self-concordant empirical loss. In Bach, F. and Blei, D. (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 362–370, Lille, France, 07–09 Jul 2015. PMLR.

Citation

MLA

Safaryan, M., et al. “FedNL: Making Newton-Type Methods Applicable to Federated Learning”. International Conference on Machine Learning, vol. 162, 2022, pp. 18959–9010, https://proceedings.mlr.press/v162/safaryan22a.html.

APA

Safaryan, M., Islamov, R., Qian, X., & Richtarik, P. (2022). FedNL: Making Newton-Type Methods Applicable to Federated Learning. International Conference on Machine Learning, 162, 18959–19010. https://proceedings.mlr.press/v162/safaryan22a.html

Chicago

Safaryan, M., R. Islamov, X. Qian, and P. Richtarik. 2022. “FedNL: Making Newton-Type Methods Applicable to Federated Learning”. International Conference on Machine Learning 162: 18959–19010. https://proceedings.mlr.press/v162/safaryan22a.html.

Harvard

Safaryan, M. et al. (2022) “FedNL: Making Newton-Type Methods Applicable to Federated Learning”, International Conference on Machine Learning. PMLR, pp. 18959–19010. Available at: https://proceedings.mlr.press/v162/safaryan22a.html.

Vancouver

1. Safaryan M, Islamov R, Qian X, Richtarik P (2022) FedNL: Making Newton-Type Methods Applicable to Federated Learning. In: International Conference on Machine Learning. PMLR, pp 18959–19010

BibTeX

@InProceedings{pmlr-v162-safaryan22a,
  title = 	 {{F}ed{NL}: Making {N}ewton-Type Methods Applicable to Federated Learning},
  author =       {Safaryan, Mher and Islamov, Rustem and Qian, Xun and Richtarik, Peter},
  booktitle = 	 {Proceedings of the 39th International Conference on Machine Learning},
  pages = 	 {18959--19010},
  year = 	 {2022},
  editor = 	 {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan},
  volume = 	 {162},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {17--23 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v162/safaryan22a/safaryan22a.pdf},
  url = 	 {https://proceedings.mlr.press/v162/safaryan22a.html},
  abstract = 	 {Inspired by recent work of Islamov et al (2021), we propose a family of Federated Newton Learn (\algname{FedNL}) methods, which we believe is a marked step in the direction of making second-order methods applicable to FL. In contrast to the aforementioned work, \algname{FedNL} employs a different Hessian learning technique which i) enhances privacy as it does not rely on the training data to be revealed to the coordinating server, ii) makes it applicable beyond generalized linear models, and iii) provably works with general contractive compression operators for compressing the local Hessians, such as Top-$K$ or Rank-$R$, which are vastly superior in practice. Notably, we do not need to rely on error feedback for our methods to work with contractive compressors. Moreover, we develop \algname{FedNL-PP}, \algname{FedNL-CR} and \algname{FedNL-LS}, which are variants of \algname{FedNL} that support partial participation, and globalization via cubic regularization and line search, respectively, and \algname{FedNL-BC}, which is a variant that can further benefit from bidirectional compression of gradients and models, i.e., smart uplink gradient and smart downlink model compression. We prove local convergence rates that are independent of the condition number, the number of training data points, and compression variance. Our communication efficient Hessian learning technique provably learns the Hessian at the optimum. Finally, we perform a variety of numerical experiments that show that our \algname{FedNL} methods have state-of-the-art communication complexity when compared to key baselines.}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

FedNL: Making Newton-Type Methods Applicable to Federated Learning

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — FedNL Algorithm for Distributed Second-Order Optimization

Knowl 2 — Local Convergence Theory of FedNL

Knowl 3 — FedNL-PP Algorithm for Partial Participation

Knowl 4 — Local Linear Convergence of FedNL-PP under Partial Participation

Knowl 5 — FedNL-LS Algorithm for Line Search Globalization

Knowl 6 — Global Linear Convergence of FedNL-LS

Knowl 7 — FedNL-CR Algorithm for Cubic Regularization Globalization

Knowl 8 — Global and Local Convergence Theory of FedNL-CR

Knowl 9 — FedNL-BC Algorithm for Bidirectional Compression

Knowl 10 — Local Linear Convergence of FedNL-BC

Knowl 11 — Newton Zero Method and the Newton Triangle

Knowl 12 — Contractive and Unbiased Matrix Compression Operators

Knowl 13 — Theoretical Communication Complexity Comparison

Knowl 14 — Empirical Communication Efficiency and Robustness to Data Heterogeneity

Knowl 15 — Limitations of the FedNL Framework

References

Citation

BibTeX

Access the Paper