Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization

Jianyu WangQinghua LiuHao LiangGauri JoshiH. Poor

article2020NeurIPS2,165 citations

Establishes a theoretical framework to analyze objective inconsistency in heterogeneous federated learning and proposes FedNova, a normalized averaging method that corrects solution bias caused by unequal client updates without sacrificing convergence speed.

Listen

Federated learning is an increasingly important approach for training artificial intelligence models across distributed edge devices—such as smartphones and internet-of-things sensors—without requiring users to centralize their private data. In real-world deployments, these edge devices exhibit severe heterogeneity: local dataset sizes vary widely, computation speeds differ, and network conditions fluctuate unpredictably. As a result, faster devices perform significantly more local training steps than slower ones before sending updates to the central server. Standard federated aggregation algorithms, such as Federated Averaging (FedAvg), implicitly over-weight devices that perform more local work, causing the global model to drift toward a distorted surrogate goal rather than the true global objective.

The article set out to theoretically analyze the bias and convergence slowdown caused by this "objective inconsistency" in heterogeneous settings and to develop a principled averaging framework that eliminates solution bias while preserving fast convergence.

The authors conducted both rigorous mathematical analysis and empirical simulations across non-identical distributed datasets. They formulated a unified theoretical framework encompassing common federated algorithms and various local solvers, including standard stochastic gradient descent, proximal updates, momentum, and variable learning rates. To validate the findings, the researchers tested a new aggregation algorithm, FedNova, on synthetic benchmarks and a complex image classification task using a partitioned CIFAR-10 dataset distributed across a 16-machine cluster, comparing performance against baseline methods across multiple random seeds.

The investigation produced four key findings. First, standard federated methods exhibit a persistent, non-vanishing error floor when local updates vary across devices, converging to an incorrect objective function regardless of how small the learning rate is or how long the model trains. Second, prior corrective methods like FedProx reduce this bias only by introducing significant training slowdowns, requiring a restrictive trade-off between consistency and training time. Third, the authors' proposed method, FedNova, completely eliminates objective inconsistency by normalizing client updates before server-side aggregation, which dynamically rescales local progress without forcing fast nodes to wait for slower stragglers. Fourth, in empirical evaluations on non-identical image classification tasks, FedNova improved final test accuracy by 6 to 9 percentage points over standard FedAvg across various local solvers and achieved up to a 10 percentage point improvement over FedProx while requiring roughly half the communication rounds to reach target performance.

These findings have direct operational and economic implications for large-scale distributed computing systems. By removing the need to synchronize devices to a fixed, conservative number of updates, FedNova substantially mitigates the "straggler problem" where fast machines sit idle waiting for slow ones. Organizations can cut bandwidth usage and cloud communication costs approximately in half while deploying more accurate models. The methodology also seamlessly integrates with complementary system enhancements, such as server momentum and variance-reduction techniques, allowing existing federated infrastructure to be upgraded without fundamental architectural redesigns.

Decision-makers and engineering teams should adopt normalized gradient aggregation in federated training pipelines where client hardware or dataset sizes are uneven. Practitioners should also leverage hybrid local and server momentum, which demonstrated the highest overall accuracy in benchmarks. Prior to enterprise-wide rollout, engineering teams should conduct pilot deployments to tune server-side scaling parameters under specific network topologies and verify performance with specialized client sampling strategies.

Confidence in these findings is high due to the alignment between theoretical convergence proofs and empirical results on standard distributed learning benchmarks. However, leaders should note several boundary conditions: the mathematical guarantees assume smooth objective functions and unbiased gradient estimates, and the empirical evaluations focused on controlled 16-client and 30-client networks. Further testing is advised when applying the framework to fully decentralized gossip-based architectures or extremely sparse mobile networks.

Carnegie Mellon University Princeton University communication optimization optimization problems Local Eff Objective

arXiv: 2007.07481 JYWa/FedNova

Paper: SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, Sai Praneeth Karimireddy et al. (2019). SCAFFOLD directly motivates the source paper by introducing control variates to eliminate client drift, a core limitation that FedNova builds upon with a normalized averaging framework.
Paper: Federated Optimization in Heterogeneous Networks, Tian Li et al. (2018). FedProx provides essential baseline formulations for heterogeneous federated optimization, establishing the proximal regularization approach that the source paper analyzes and generalizes.
Paper: On the Convergence of FedAvg on Non-IID Data, Xiang Li et al. (2019). This paper establishes foundational convergence bounds for FedAvg under non-IID data, providing the precise analytical baseline that the source paper uses to quantify objective inconsistency.

No sufficiently relevant recommendations were found.

Cover for Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization

Abstract

In federated optimization, heterogeneity in the clients' local datasets and computation speeds results in large variations in the number of local updates performed by each client in each communication round. Naive weighted aggregation of such models causes objective inconsistency, that is, the global model converges to a stationary point of a mismatched objective function which can be arbitrarily different from the true objective. This paper provides a general framework to analyze the convergence of federated heterogeneous optimization algorithms. It subsumes previously proposed methods such as FedAvg and FedProx and provides the first principled understanding of the solution bias and the convergence slowdown due to objective inconsistency. Using insights from this analysis, we propose FedNova, a normalized averaging method that eliminates objective inconsistency while preserving fast error convergence.

Topics

communication optimization optimization problems rate of convergence

Keywords

Local Eff Objective Clients Federated SGD FedAvg Learning Client Optimization

1 Introduction
2 System Model and Prior Work
3 A Case Study to Demonstrate the Objective Inconsistency Problem
4 New Theoretical Framework For Heterogeneous Federated Optimization
4.1 A Generalized Update Rule for Heterogeneous Federated Optimization
4.2 Convergence Analysis for Smooth Non-Convex Functions
5 FedNova: Proposed Federated Normalized Averaging Algorithm
6 Experimental Results
7 Concluding Remarks
8 Acknowledgements
References
A Proof of : Objective Inconsistency in Quadratic Model
B Detailed Derivations for Various Local Solvers
B.1 SGD with Proximal Updates
B.2 SGD with Local Momentum
C Proof of : Convergence of Surrogate Objective
C.1 Preliminaries
C.2 Bounding First term in
C.3 Bounding Second term in
C.4 Intermediate Result
C.5 Bounding the Difference Between Server Gradient and Normalized Gradient
C.6 Final Results
C.7 Constraint on Local Learning Rate
C.8 Further Optimizing the Bound
D Proof of : Including Bias in the Error Bound
D.1 Constructing a Lower Bound
E Special Cases of
E.1 FedAvg
E.2 FedProx
F Proof of
G Extension: Incorporating Client Sampling
H Pseudo-code of FedNova
I More Experiments Details

Knowls

Knowl 1 — Federated Normalized Averaging Framework
algorithm
Federated Normalized Averaging (FedNova) eliminates objective inconsistency in heterogeneous federated optimization by aggregating normalized client updates rather than unscaled cumulative parameter changes.

Let $m$ be the total number of clients, $p_i = n_i / n$ be the relative data size of client $i$ , $\eta$ be the client learning rate, $T$ be the total number of communication rounds, and $S_t \subseteq \{1, \dots, m\}$ be the subset of clients sampled in round $t$ .
Input: Client learning rate $\eta$ , total rounds $T$ , sampling set $S_t$
for $t = 0, 1, \dots, T - 1$ do
    Server randomly samples client subset $S_t$
    Server broadcasts current global model $x^{(t,0)}$ to selected clients $i \in S_t$
    for each client $i \in S_t$ in parallel do
        Client runs local solver for $\tau_i^{(t)}$ steps to obtain local model $x^{(t,\tau_i^{(t)})}_i$
        Client computes local accumulation norm $\|a_i^{(t)}\|_1$
        Client computes normalized local gradient $d_i^{(t)} = \frac{x^{(t,0)} - x^{(t,\tau_i^{(t)})}_i}{\eta \|a_i^{(t)}\|_1}$
        Client sends $\|a_i^{(t)}\|_1$ and $d_i^{(t)}$ to the server
    end for
    Server sets effective step size $\tau_{\text{eff}}^{(t)} = \frac{\sum_{i \in S_t} p_i \|a_i^{(t)}\|_1}{\sum_{i \in S_t} p_i}$
    Server updates global model: $x^{(t+1,0)} = x^{(t,0)} - \tau_{\text{eff}}^{(t)} \frac{\sum_{i \in S_t} \eta p_i d_i^{(t)}}{\sum_{i \in S_t} p_i}$
end for
When client optimizers are vanilla stochastic gradient descent (SGD), $a_i^{(t)} = [1, \dots, 1]^\top$ and $\|a_i^{(t)}\|_1 = \tau_i^{(t)}$ , so $d_i^{(t)}$ is the arithmetic mean of stochastic gradients computed by client $i$ during round $t$ . The server update becomes $x^{(t+1,0)} - x^{(t,0)} = (\sum_{i=1}^m p_i \tau_i^{(t)}) \sum_{i=1}^m p_i \Delta_i^{(t)} / \tau_i^{(t)}$ , rescaling each cumulative update $\Delta_i^{(t)} = x_i^{(t,\tau_i^{(t)})} - x^{(t,0)}$ by $(\sum_{j=1}^m p_j \tau_j^{(t)}) / \tau_i^{(t)}$ .
Knowl 2 — Generalized Update Formulation for Heterogeneous Federated Optimization
model/method
Heterogeneous federated learning algorithms that perform local gradient steps with linear accumulation can be unified under a single generalized server update rule:

$x^{(t+1,0)} - x^{(t,0)} = -\tau_{\text{eff}} \sum_{i=1}^m w_i \cdot \eta d_i^{(t)}$

which optimizes the surrogate objective:

$\tilde{F}(x) = \sum_{i=1}^m w_i F_i(x)$

rather than the target global objective $F(x) = \sum_{i=1}^m p_i F_i(x)$ , where $p_i = n_i / n$ is the dataset weight of client $i$ .

The formulation decomposes the update into three core components:
1. Normalized gradient $d_i^{(t)}$ : Defined as $d_i^{(t)} = G_i^{(t)} a_i / \|a_i\|_1$ , where $G_i^{(t)} = [g_i(x_i^{(t,0)}), g_i(x_i^{(t,1)}), \dots, g_i(x_i^{(t,\tau_i-1)})] \in \mathbb{R}^{d \times \tau_i}$ stacks the mini-batch stochastic gradients in round $t$ , and $a_i \in \mathbb{R}^{\tau_i}$ is a non-negative vector defining the local gradient accumulation method.
2. Aggregation weights $w_i$ : The implicit normalized weight of client $i$ , satisfying $\sum_{i=1}^m w_i = 1$ . In standard aggregation rules: $w_i = \frac{p_i \|a_i\|_1}{\sum_{j=1}^m p_j \|a_j\|_1}$
3. Effective local steps $\tau_{\text{eff}}$ : A scalar determining the step length along the aggregated direction. In standard unnormalized aggregation: $\tau_{\text{eff}} = \sum_{i=1}^m p_i \|a_i\|_1$
Whenever clients have heterogeneous accumulation norms $\|a_i\|_1$ (caused by unequal local iterations $\tau_i$ , non-uniform learning rates, or momentum schedules), the implicit weights $w_i \neq p_i$ , resulting in objective inconsistency.
Knowl 3 — Convergence Bound and Inconsistency Bias for the True Objective
theoretical result
Under Lipschitz smoothness ( $L$ ), unbiased stochastic gradients with bounded variance ( $\sigma^2$ ), and bounded client dissimilarity ( $\beta^2 \ge 1, \kappa^2 \ge 0$ ), executing any federated algorithm characterized by weights $w = [w_1, \dots, w_m]$ and effective step size $\tau_{\text{eff}}$ yields the following bound on the minimal gradient norm of the true objective $F(x) = \sum_{i=1}^m p_i F_i(x)$ :

$\min_{t \in [T]} \|\nabla F(x^{(t,0)})\|^2 \le 2 \left[ \chi^2_{p \parallel w} (\beta^2 - 1) + 1 \right] \epsilon_{\text{opt}} + 2 \chi^2_{p \parallel w} \kappa^2$

where $\chi^2_{p \parallel w} = \sum_{i=1}^m \frac{(p_i - w_i)^2}{w_i}$ is the chi-square divergence between the target data distribution weights $p = [p_1, \dots, p_m]$ and the implicit aggregation weights $w = [w_1, \dots, w_m]$ , and $\epsilon_{\text{opt}}$ is the vanishing optimization error on the surrogate objective $\tilde{F}(x) = \sum_{i=1}^m w_i F_i(x)$ after $T$ communication rounds.

Lower Bound on Bias: For strongly convex local functions with bounded dissimilarity $\kappa^2$ , FedAvg with heterogeneous local steps satisfies:

$\lim_{T \to \infty} \mathbb{E} \|\nabla F(x^{(T,0)})\|^2 = \Omega(\chi^2_{p \parallel w} \kappa^2)$

proving that the non-vanishing error floor $2 \chi^2_{p \parallel w} \kappa^2$ caused by objective inconsistency cannot be eliminated by decreasing the learning rate $\eta$ or increasing rounds $T$ unless $\chi^2_{p \parallel w} = 0$ (i.e., $w = p$ as in FedNova) or $\kappa^2 = 0$ (identical local objectives).
Knowl 4 — Convergence Guarantee of Generalized Federated Optimization to Surrogate Stationary Points
theoretical result
Under Lipschitz smoothness ( $L$ ), bounded stochastic gradient variance ( $\sigma^2$ ), and bounded dissimilarity ( $\beta^2, \kappa^2$ ), if the total communication rounds $T$ is fixed, the generalized federated optimization algorithm with update $x^{(t+1,0)} - x^{(t,0)} = -\tau_{\text{eff}} \sum_{i=1}^m w_i \eta d_i^{(t)}$ and client step size $\eta = \sqrt{\frac{m}{\bar{\tau} T}}$ (where $\bar{\tau} = \frac{1}{m} \sum_{i=1}^m \tau_i$ ) converges to a stationary point of $\tilde{F}(x) = \sum_{i=1}^m w_i F_i(x)$ satisfying:

$\min_{t \in [T]} \mathbb{E}\|\nabla \tilde{F}(x^{(t,0)})\|^2 \le \mathcal{O}\left( \frac{\bar{\tau} / \tau_{\text{eff}}}{\sqrt{m \bar{\tau} T}} \right) + \mathcal{O}\left( \frac{A \sigma^2}{\sqrt{m \bar{\tau} T}} \right) + \mathcal{O}\left( \frac{m B \sigma^2}{\bar{\tau} T} \right) + \mathcal{O}\left( \frac{m C \kappa^2}{\bar{\tau} T} \right)$

where $\mathcal{O}$ hides problem constants including $L$ , and the solver-dependent parameters are defined as:

$A = m \tau_{\text{eff}} \sum_{i=1}^m w_i^2 \frac{\|a_i\|_2^2}{\|a_i\|_1^2}, \quad B = \sum_{i=1}^m w_i (\|a_i\|_2^2 - a_{i,-1}^2), \quad C = \max_{i \in [m]} \left\{ \|a_i\|_1 (\|a_i\|_1 - a_{i,-1}) \right\}$

with $a_{i,-1}$ denoting the final element of vector $a_i$ .

The step size $\eta$ must satisfy the stability condition:

$\eta L \le \frac{1}{2} \min \left\{ \frac{1}{\max_i \|a_i\|_1 \sqrt{2\beta^2 + 1}}, \frac{1}{\tau_{\text{eff}}} \right\}$
Knowl 5 — Convergence of FedNova to True Objective Stationary Points
theoretical result
In FedNova, setting aggregation weights $w_i = p_i$ yields $\chi^2_{p \parallel w} = 0$ , ensuring convergence to a stationary point of the true objective $F(x) = \sum_{i=1}^m p_i F_i(x)$ .

Let each client $i$ perform an arbitrary, time-varying number of local updates $\tau_i(t)$ with accumulation vector $a_i(t)$ at round $t \in [T]$ . Define the round-average local steps as $\tilde{\tau} = \frac{1}{T} \sum_{t=0}^{T-1} \bar{\tau}(t)$ where $\bar{\tau}(t) = \frac{1}{m} \sum_{i=1}^m \tau_i(t)$ , and choose $\eta = \sqrt{\frac{m}{\tilde{\tau} T}}$ .
1. Full Participation: FedNova converges to a stationary point of $F(x)$ at rate: $\min_{t \in [T]} \mathbb{E}\|\nabla F(x^{(t,0)})\|^2 \le \mathcal{O}\left( \frac{\tilde{\tau} / \tilde{\tau}_{\text{eff}}}{\sqrt{m \tilde{\tau} T}} \right) + \mathcal{O}\left( \frac{\tilde{A} \sigma^2}{\sqrt{m \tilde{\tau} T}} \right) + \mathcal{O}\left( \frac{m \tilde{B} \sigma^2}{\tilde{\tau} T} \right) + \mathcal{O}\left( \frac{m \tilde{C} \kappa^2}{\tilde{\tau} T} \right) = \mathcal{O}\left( \frac{1}{\sqrt{m \tilde{\tau} T}} \right)$ where $\tilde{A}, \tilde{B}, \tilde{C}, \tilde{\tau}_{\text{eff}}$ are the round-averaged values of $A(t), B(t), C(t), \tau_{\text{eff}}^{(t)}$ . When $T$ is large, the convergence achieves linear speedup with respect to the number of clients $m$ .
2. Client Sampling: If $q \le m$ clients are sampled with replacement in each round with probability $p_i = n_i / n$ , setting $\eta = \sqrt{\frac{q}{\tilde{\tau} T}}$ gives: $\min_{t \in [T]} \mathbb{E}\|\nabla F(x^{(t,0)})\|^2 \le \mathcal{O}\left( \frac{\tilde{\tau} / \tilde{\tau}_{\text{eff}}}{\sqrt{q \tilde{\tau} T}} \right) + \mathcal{O}\left( \frac{\tilde{\tau}_{\text{eff}} / \tilde{\tau}}{\sqrt{q \tilde{\tau} T}} \right) + \mathcal{O}\left( \frac{q(\tilde{B} + \tilde{C})}{\tilde{\tau} T} \right) = \mathcal{O}\left( \frac{1}{\sqrt{q \tilde{\tau} T}} \right)$
Knowl 6 — Objective Inconsistency of FedAvg on Quadratic Objectives
theoretical result
Consider $m$ clients where each client $i$ has a strongly convex local quadratic objective $F_i(x) = \frac{1}{2}\|x - e_i\|^2$ with minimum $x_i^* = e_i \in \mathbb{R}^d$ . The global objective is $F(x) = \frac{1}{m} \sum_{i=1}^m F_i(x) = \frac{1}{2m} \sum_{i=1}^m \|x - e_i\|^2$ , which has unique global minimum $x^* = \frac{1}{m} \sum_{i=1}^m e_i$ .

If client $i$ performs $\tau_i$ local gradient descent steps per round with deterministic gradients and full participation, then for sufficiently small local learning rate $\eta$ , FedAvg converges to:

$\tilde{x}_{\text{FedAvg}}^* = \lim_{\eta \to 0} \lim_{T \to \infty} x^{(T,0)} = \frac{\sum_{i=1}^m \tau_i e_i}{\sum_{i=1}^m \tau_i}$

This limit strictly minimizes the surrogate objective $\tilde{F}(x) = \frac{\sum_{i=1}^m \tau_i F_i(x)}{\sum_{i=1}^m \tau_i}$ . When the local iterations $\tau_i$ are heterogeneous across clients, $\tilde{x}_{\text{FedAvg}}^* \neq x^*$ , creating an asymptotic error gap that does not vanish even with an infinite number of communication rounds and arbitrarily small learning rates.
Knowl 7 — Gradient Accumulation Vectors and Norms for Client Solvers
definition
For a client performing $\tau_i$ local steps whose cumulative model parameter update is $\Delta_i^{(t)} = x_i^{(t,\tau_i)} - x^{(t,0)} = -\eta G_i^{(t)} a_i$ , the accumulation vector $a_i \in \mathbb{R}^{\tau_i}$ and its $\ell_1$ -norm $\|a_i\|_1$ for common local optimizers are:
1. Vanilla SGD (FedAvg): $a_i = [1, 1, \dots, 1]^\top, \quad \|a_i\|_1 = \tau_i$
2. Proximal SGD (FedProx) with proximal penalty parameter $\mu \ge 0$ and $\alpha = \eta \mu$ : $a_i = \left[ (1 - \alpha)^{\tau_i-1}, (1 - \alpha)^{\tau_i-2}, \dots, (1 - \alpha), 1 \right]^\top, \quad \|a_i\|_1 = \frac{1 - (1 - \alpha)^{\tau_i}}{\alpha}$
3. Decayed Local Learning Rate SGD with decay factor $\gamma_i \ge 0$ : $a_i = \left[ 1, \gamma_i, \dots, \gamma_i^{\tau_i-1} \right]^\top, \quad \|a_i\|_1 = \frac{1 - \gamma_i^{\tau_i}}{1 - \gamma_i}$
4. Momentum SGD with momentum coefficient $\rho \in [0, 1)$ (local buffer reset to 0 at the start of each round): $a_i = \frac{1}{1 - \rho} \left[ 1 - \rho^{\tau_i}, 1 - \rho^{\tau_i-1}, \dots, 1 - \rho \right]^\top, \quad \|a_i\|_1 = \frac{1}{1 - \rho} \left( \tau_i - \frac{\rho(1 - \rho^{\tau_i})}{1 - \rho} \right)$
Knowl 8 — Objective Consistency versus Convergence Slowdown Trade-off in FedProx
theoretical result
In FedProx with proximal parameter $\mu \ge 0$ (where $\alpha = \eta \mu$ ), the implicit aggregation parameters under the generalized framework are:

$\tau_{\text{eff}} = \frac{1}{\alpha} \sum_{i=1}^m p_i \left[ 1 - (1 - \alpha)^{\tau_i} \right], \quad w_i = \frac{p_i \left[ 1 - (1 - \alpha)^{\tau_i} \right]}{\sum_{j=1}^m p_j \left[ 1 - (1 - \alpha)^{\tau_j} \right]}$

This reveals a fundamental tension controlled by $\alpha$ :
- Mitigating Inconsistency: Increasing $\alpha$ forces $w_i \to p_i$ , which reduces the chi-square divergence $\chi^2_{p \parallel w}$ and shrinks the non-vanishing error floor $2 \chi^2_{p \parallel w} \kappa^2$ .
- Convergence Slowdown: Increasing $\alpha$ decreases $\tau_{\text{eff}}$ towards $1$ . When $\alpha \to 1$ , $\tau_{\text{eff}} = 1$ , making the slowdown factor $\bar{\tau} / \tau_{\text{eff}} = \bar{\tau}$ , which slows convergence by a factor of $\bar{\tau}$ compared to FedAvg (where $\alpha = 0, \tau_{\text{eff}} = \bar{\tau}$ ).
Optimal Choice of $\alpha$ : When $p_i = 1/m$ and $\tau_i \gg 1$ , the choice $\alpha = \mathcal{O}\left( \frac{m^{1/2}}{\bar{\tau}^{1/2} T^{1/6}} \right)$ balances the error terms, yielding a surrogate convergence rate of $\mathcal{O}\left( \frac{1}{\sqrt{m \bar{\tau} T}} + \frac{1}{T^{2/3}} \right)$ .
Knowl 9 — FedNova with Client-Side Momentum and Cross-Client Variance Reduction
algorithm
FedNova can be seamlessly combined with client-side momentum SGD and cross-client variance reduction (SCAFFOLD/VRLSGD style tracking).

Let $\eta$ be the client learning rate, $\rho$ be the momentum factor, and $p_i = n_i / n$ . For client $i$ with $\tau_i$ local iterations, the scalar accumulation norm is:

$a_i = \frac{\tau_i - \rho(1 - \rho^{\tau_i})/(1 - \rho)}{1 - \rho}$
Input: Client learning rate $\eta$ , momentum factor $\rho$
for $t = 0, 1, \dots, T - 1$ at client $i$ in parallel do
    Initialize client momentum buffer $u_i^{(t,0)} = 0$
    Receive global model $x^{(t,0)} = x^{(t-1,0)} - (\sum_{j=1}^m p_j a_j) \eta \sum_{j=1}^m p_j d_j^{(t-1)}$ from server
    Receive average normalized direction $\sum_{j=1}^m p_j d_j^{(t-1)}$ from server
    Compute gradient correction term $c_i^{(t)} = -d_i^{(t-1)} + \sum_{j=1}^m p_j d_j^{(t-1)}$
    for $k = 0, 1, \dots, \tau_i - 1$ do
        Compute corrected stochastic gradient $\tilde{g}_i(x_i^{(t,k)}) = g_i(x_i^{(t,k)}) + c_i^{(t)}$
        Update momentum buffer $u_i^{(t,k)} = \rho u_i^{(t,k-1)} + \tilde{g}_i(x_i^{(t,k)})$
        Update local model $x_i^{(t,k+1)} = x_i^{(t,k)} - \eta u_i^{(t,k)}$
    end for
    Compute normalized gradient $d_i^{(t)} = \frac{x^{(t,0)} - x_i^{(t,\tau_i)}}{\eta a_i}$
    Send $p_i a_i$ and $p_i d_i^{(t)}$ to server
end for
Knowl 10 — Standard Smoothness, Variance, and Dissimilarity Assumptions
assumption
The convergence analysis for federated optimization under heterogeneous local progress is established under the following standard assumptions:
1. Smoothness (Assumption 1): Each local objective $F_i(x)$ is $L$ -Lipschitz smooth: $\|\nabla F_i(x) - \nabla F_i(y)\| \le L \|x - y\|, \quad \forall x, y \in \mathbb{R}^d, \forall i \in \{1, \dots, m\}$
2. Unbiased Stochastic Gradient with Bounded Variance (Assumption 2): The stochastic mini-batch gradient $g_i(x|\xi)$ satisfies: $\mathbb{E}_\xi [g_i(x|\xi)] = \nabla F_i(x), \quad \mathbb{E}_\xi \|g_i(x|\xi) - \nabla F_i(x)\|^2 \le \sigma^2, \quad \forall i \in \{1, \dots, m\}, \sigma^2 \ge 0$
3. Bounded Dissimilarity (Assumption 3): For any non-negative weights $\{w_i\}_{i=1}^m$ with $\sum_{i=1}^m w_i = 1$ , there exist constants $\beta^2 \ge 1$ and $\kappa^2 \ge 0$ such that: $\sum_{i=1}^m w_i \|\nabla F_i(x)\|^2 \le \beta^2 \left\| \sum_{i=1}^m w_i \nabla F_i(x) \right\|^2 + \kappa^2, \quad \forall x \in \mathbb{R}^d$ If all local objectives are identical, $\beta^2 = 1$ and $\kappa^2 = 0$ .

Knowl 11 — Test Accuracy of FedAvg and FedNova across Client Solvers on Non-IID CIFAR-10

data/table

Evaluation of FedNova against FedAvg on a VGG-11 model trained on CIFAR-10 partitioned across 16 clients using a Dirichlet distribution $\text{Dir}_{16}(0.1)$ for 100 communication rounds. Results report top-1 test accuracy (mean $\pm$ standard deviation across 3 seeds) for both fixed local epochs ( $E_i = 2$ , yielding $16 \le \tau_i \le 408$ ) and uniform random time-varying epochs ( $E_i^{(t)} \sim \mathcal{U}(2, 5)$ , yielding $16 \le \tau_i^{(t)} \le 1020$ ).

Local Epochs	Client Optimizer	Test Accuracy (%)
		FedAvg	FedNova
$E_i = 2$	Vanilla SGD	$60.68 \pm 1.05$	$66.31 \pm 0.86$
( $16 \le \tau_i \le 408$ )	Momentum SGD	$65.26 \pm 2.42$	$73.32 \pm 0.29$
	Proximal SGD (FedProx)	$60.44 \pm 1.21$	$69.92 \pm 0.34$
$E_i^{(t)} \sim \mathcal{U}(2, 5)$	Vanilla SGD	$64.22 \pm 1.06$	$73.22 \pm 0.32$
( $16 \le \tau_i^{(t)} \le 1020$ )	Momentum SGD	$70.44 \pm 2.99$	$77.07 \pm 0.12$
	Proximal SGD (FedProx)	$63.74 \pm 1.44$	$73.41 \pm 0.45$
	Variance Reduction (VR)	$74.72 \pm 0.34$	$74.72 \pm 0.19$
	Momentum + VR	Not Defined	$79.19 \pm 0.17$

Normalizing updates via FedNova consistently improves test accuracy by 6% to 10% over FedAvg across all client optimizers. Combining client-side momentum with variance reduction within FedNova achieves the highest overall accuracy of 79.19% (further improved to 81.15% $\pm$ 0.38% when combined with server momentum).

Coverage note — None was omitted; all key theoretical bounds, optimization models, algorithms (FedNova and its momentum/VR variant), case study results, and empirical tables were fully preserved.

References

1.H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, et al. Communication-efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
2.Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977, 2019.
3.Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492, 2016.
4.Jakub Konečnỳ, Brendan McMahan, and Daniel Ramage. Federated optimization: Distributed optimization beyond the datacenter. arXiv preprint arXiv:1511.03575, 2015.
5.Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao, Ying-Chang Liang, Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEE Communications Surveys & Tutorials, 2020.
6.Mu Li, David G Andersen, Jun Woo Park, Alexander J Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J Shekita, and Bor-Yiing Su. Scaling distributed machine learning with the parameter server. In OSDI, volume 14, pages 583–598, 2014.
7.Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication-computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953–976, 2018.
8.Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-efficient SGD algorithms. arXiv preprint arXiv:1808.07576, 2018.
9.Sebastian U Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations (ICLR), 2019.
10.Fan Zhou and Guojing Cong. On the convergence properties of a k-step averaging stochastic gradient descent algorithm for nonconvex optimization. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 3219–3227, 2018.
11.Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693–5700, 2019.
12.Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-IID data. In International Conference on Learning Representations, 2020.
13.Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in federated learning. arXiv preprint arXiv:1910.14425, 2019.
14.Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding up distributed SGD for non-convex optimization. In International Conference on Machine Learning, pages 2545–2554, 2019.
15.Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pages 11080–11092, 2019.
16.A Khaled, K Mishchenko, and P Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020.
17.Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv:1909.05350, 2019.
18.Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE Journal on Selected Areas in Communications, 37(6):1205–1221, 2019.
19.Jianyu Wang and Gauri Joshi. Adaptive communication strategies to achieve the best error-runtime trade-off in local-update SGD. arXiv preprint arXiv:1810.08313, 2018.
20.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, 2020.
21.Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local SGD with lower communication complexity. arXiv preprint arXiv:1912.12844, 2019.
22.Blake Woodworth, Kumar Kshitij Patel, Sebastian U Stich, Zhen Dai, Brian Bullins, H Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In International Conference on Machine Learning, 2020.
23.Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized SGD with changing topology and local updates. In International Conference on Machine Learning, 2020.
24.Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In International Conference on Machine Learning, 2019.
25.Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. SlowMo: Improving communication-efficient distributed SGD with slow momentum. In International Conference on Learning Representations, 2020.
26.Zhouyuan Huo, Qian Yang, Bin Gu, Lawrence Carin Huang, et al. Faster on-device training using new federated momentum algorithm. arXiv preprint arXiv:2002.02090, 2020.
27.Fan Zhou and Guojing Cong. A distributed hierarchical SGD algorithm with sparse global reduction. arXiv preprint arXiv:1903.05133, 2019.
28.Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu. FedPD: A federated learning framework with optimal rates and adaptivity to non-IID data. arXiv preprint arXiv:2005.11418, 2020.
29.Reese Pathak and Martin J Wainwright. FedSplit: An algorithmic framework for fast federated optimization. arXiv preprint arXiv:2005.05238, 2020.
30.Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. First analysis of local GD on heterogeneous data. arXiv preprint arXiv:1909.04715, 2019.
31.Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro. Graph oracle models, lower bounds, and gaps for parallel stochastic optimization. In Advances in neural information processing systems, pages 8496–8506, 2018.
32.Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-IID data. arXiv preprint arXiv:1806.00582, 2018.
33.Cong Xie, Oluwasanmi Koyejo, Indranil Gupta, and Haibin Lin. Local AdaAlter: Communication-efficient stochastic gradient descent with adaptive learning rates. arXiv preprint arXiv:1911.09030, 2019.
34.Tao Lin, Sebastian U Stich, and Martin Jaggi. Don’t use large mini-batches, use local SGD. In International Conference on Learning Representations (ICLR), 2020.
35.Grigory Malinovsky, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local SGD to local fixed point methods for federated learning. arXiv preprint arXiv:2004.01442, 2020.
36.Jianyu Wang, Hao Liang, and Gauri Joshi. Overlap local-SGD: An algorithmic approach to hide communication delays in distributed SGD. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8871–8875. IEEE, 2020.
37.Aymeric Dieuleveut and Kumar Kshitij Patel. Communication trade-offs for local-SGD with large step size. In Advances in Neural Information Processing Systems, pages 13579–13590, 2019.
38.Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Conference on Machine Learning and Systems, 2020.
39.Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy. Feddane: A federated newton-type method. In 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pages 1227–1231. IEEE, 2019.
40.Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečnỳ, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
41.Cong Xie, Sanmi Koyejo, and Indranil Gupta. Asynchronous federated optimization. arXiv preprint arXiv:1903.03934, 2019.
42.Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06335, 2019.
43.Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization. arXiv preprint arXiv:1909.13014, 2019.
44.Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-SGD: Distributed SGD with quantization, sparsification and local computations. In Advances in Neural Information Processing Systems, pages 14668–14679, 2019.
45.Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication-efficient learning via atomic sparsification. In Advances in Neural Information Processing Systems, pages 9850–9861, 2018.
46.Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek. Robust and communication-efficient federated learning from non-IID data. IEEE transactions on neural networks and learning systems, 2019.
47.Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. arXiv preprint arXiv:2002.11364, 2020.
48.Feijie Wu, Shiqi He, Yutong Yang, Haozhao Wang, Zhihao Qu, and Song Guo. On the convergence of quantized parallel restarted sgd for serverless learning. arXiv preprint arXiv:2004.09125, 2020.
49.Tian Li, Maziar Sanjabi, and Virginia Smith. Fair resource allocation in federated learning. arXiv preprint arXiv:1905.10497, 2019.
50.Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. arXiv preprint arXiv:1902.00146, 2019.
51.Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018.
52.Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. MATCHA: Speeding up decentralized SGD via matching decomposition sampling. arXiv preprint arXiv:1905.09435, 2019.
53.Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
54.Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
55.Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. In International Conference on Learning Representations (ICLR), 2020.

Citation

MLA

Wang, J., et al. “Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization”. arXiv, 2020, http://arxiv.org/abs/2007.07481v1.

APA

Wang, J., Liu, Q., Liang, H., Joshi, G., & Poor, H. V. (2020). Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization. arXiv. http://arxiv.org/abs/2007.07481v1

Chicago

Wang, J., Q. Liu, H. Liang, G. Joshi, and H. V. Poor. 2020. “Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization”. arXiv. http://arxiv.org/abs/2007.07481v1.

Harvard

Wang, J. et al. (2020) “Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2007.07481v1.

Vancouver

1. Wang J, Liu Q, Liang H, Joshi G, Poor HV (2020) Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization. arXiv

BibTeX

@article{wang2020tackling,
  title = {Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization},
  author = {Wang, Jianyu and Liu, Qinghua and Liang, Hao and Joshi, Gauri and Poor, H. Vincent},
  year = {2020},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2007.07481v1},
  eprint = {2007.07481}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

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

Open PDF

License: Authors

Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Federated Normalized Averaging Framework

Knowl 2 — Generalized Update Formulation for Heterogeneous Federated Optimization

Knowl 3 — Convergence Bound and Inconsistency Bias for the True Objective

Knowl 4 — Convergence Guarantee of Generalized Federated Optimization to Surrogate Stationary Points

Knowl 5 — Convergence of FedNova to True Objective Stationary Points

Knowl 6 — Objective Inconsistency of FedAvg on Quadratic Objectives

Knowl 7 — Gradient Accumulation Vectors and Norms for Client Solvers

Knowl 8 — Objective Consistency versus Convergence Slowdown Trade-off in FedProx