PaperlayerView exact revision on arXiv

Source-linked AI summary

Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization

Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, H. Vincent Poor

arXiv:2007.07481v1cs.LGcs.DCstat.ML

TL;DR

Heterogeneous local progress can make federated optimization converge to a stationary point of a mismatched objective. The paper develops a general framework for analyzing this bias and proposes FedNova, whose normalized averaging ensures consistency while preserving fast convergence and improving test accuracy over FedAvg in a non-IID CIFAR-10 setting.

  • Problem

    Existing federated optimization analyses largely assume equal local-step counts, leaving objective inconsistency under heterogeneous client progress insufficiently understood.

  • Method

    The paper develops a framework covering heterogeneous updates, non-IID data, and varied local solvers, then proposes FedNova to normalize local model updates during aggregation.

  • Results

    FedNova ensures objective consistency while preserving fast error convergence and generally achieves 6-9% higher test accuracy than FedAvg on non-IID CIFAR-10.

  • Takeaways & Limitations

    FedNova supports aggregation of heterogeneous local progress and allows faster clients to perform more local updates within a communication round.

  • Takeaways & Limitations

    The framework treats local-step counts as arbitrary scalars, while client sampling and some extensions require specific sampling assumptions and remain future directions.

Abstract

from arXiv · show

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.

1 Introduction

Federated learning aggregates multiple local updates from heterogeneous clients, but unequal local progress can bias the global model toward an inconsistent objective. The paper develops a general analysis and proposes FedNova to normalize updates while retaining efficient progress.

  • Setting: Federated learning clients perform multiple local updates before their models are aggregated into a global model.Clients have limited communication and computation capabilities, motivating local computation between communication rounds.
  • Heterogeneity: Local update counts vary because clients differ in dataset sizes and computation speeds.With E local epochs and mini-batch size B, client i performs τi = ⌊Eni/B⌋ local iterations.
  • Objective inconsistency: When local steps differ, standard model averaging can converge to a stationary point of an inconsistent objective rather than the true global objective.The resulting objective may be arbitrarily different from the original objective, depending on local-step counts and local objectives.
  • Motivation: Waiting for all clients to complete a common number of updates preserves consistency but can substantially increase training time.FedProx, VRLSGD, and SCAFFOLD reduce inconsistency only partially or introduce slower convergence, extra communication, or memory requirements.
  • Analysis framework: The paper presents a general framework covering heterogeneous local updates, non-IID data, and diverse local solvers, including FedAvg and FedProx.The framework analyzes solution bias and convergence behavior under heterogeneous client progress.
  • FedNova: FedNova normalizes local model updates before aggregation to ensure objective consistency while preserving fast error convergence.It can aggregate heterogeneous local progress and allow faster clients to perform more updates, helping overcome stragglers.

2 System Model and Prior Work

The paper formulates federated optimization around clients with heterogeneous data, availability, computation, and local solvers. It situates FedAvg and FedProx as existing approaches whose analyses do not fully address heterogeneous local progress.

  • System model: Clients jointly optimize a global objective formed from local objectives weighted by relative dataset sizes.Each local objective averages the client’s loss over its local dataset.
  • System model: Each participating client independently runs τi local solver iterations from the current global model during a communication round.The local solver may be SGD or another optimization method.
  • Heterogeneity: The number of local iterations can vary across clients and rounds because of dataset size, computation speed, availability, or fixed wall-clock windows.The framework treats τi as an arbitrary scalar that may change over rounds.
  • FedAvg: FedAvg aggregates locally trained client models at the central server after each communication round.Its local progress is represented by cumulative changes generated during client updates.
  • Prior work: Prior convergence analyses generally assume identical local-step counts and client optimizers across clients.This limits their direct treatment of heterogeneous local progress.
  • FedProx: FedProx adds a tunable proximal term that pulls local models toward the current global model.A larger proximal coefficient mitigates but does not eliminate objective inconsistency, while slowing convergence.
  • Generalized methods: FedNova’s normalization is compatible with local momentum, proximal updates, variable learning rates, and other accumulated-gradient solvers.The generalized update rule normalizes by the ℓ1 norm of the local accumulation weights.

3 A Case Study to Demonstrate the Objective Inconsistency Problem

A quadratic case study shows that heterogeneous local steps can make FedAvg converge far from the true global optimum. Simulations compare this behavior across fixed and random heterogeneity and show stronger performance from FedNova in heterogeneous settings.

  • Quadratic case study: The quadratic case study uses local objectives Fi(x) = 1/2∥x − ei∥2, whose minima are the client-specific vectors ei.The global objective is constructed from these local quadratic objectives.
  • FedAvg behavior: FedAvg can converge to a point arbitrarily far from the true global optimum.The convergence problem arises when clients perform different numbers of local steps.
  • Simulation design: In simulations with 30 clients, FedNova matches FedAvg when every client performs 30 local steps and is compared with FedProx and VRLSGD under heterogeneous steps.The heterogeneous settings use fixed or time-varying local steps in the range [1, 96] with mean 30.
  • Simulation results: FedNova significantly outperforms the other methods when local-step counts are heterogeneous.The comparison includes fixed heterogeneous steps and IID, time-varying local steps.
  • Objective inconsistency: FedAvg converges to the optimum of a surrogate objective rather than the objective it is intended to optimize.The gap depends on the relative local-step counts and local objectives.
  • Other methods: FedProx slightly improves FedAvg’s optimality gap but converges more slowly, while VRLSGD can diverge under random local steps.These observations motivate analysis and algorithms designed specifically for heterogeneous local progress.

4 New Theoretical Framework For Heterogeneous Federated Optimization

The framework represents heterogeneous federated updates through normalized local gradients, aggregation weights, and an effective number of steps. Its convergence analysis shows that algorithms generally optimize a surrogate objective whose weighting can differ from the true global objective, creating bias and slowdown.

  • The framework covers heterogeneous local-update counts, non-IID data, and diverse local solvers, including GD, SGD, proximal gradients, gradient tracking, adaptive learning rates, and momentum.
  • Generalized update rule: Each client’s normalized gradient is formed by weighting its local stochastic gradients with a non-negative accumulation vector and dividing by its ℓ1 norm.
  • Generalized update rule: Aggregation weights determine the surrogate objective eF(x) = Σ_i w_iF_i(x), whereas the true objective uses the data proportions p_i.
  • Generalized update rule: The effective steps parameter τ_eff controls the magnitude of the global update and can be chosen independently of the average number of local steps to manage slowdown.
  • Convergence analysis: Theorem 1 establishes convergence to a stationary point of the surrogate objective, while Theorem 2 identifies a non-vanishing error term caused by the mismatch between p and w.
  • Special cases: FedAvg is recovered when clients use equal local SGD accumulation, while FedProx trades reduced objective inconsistency against increased slowdown as α grows.

5 FedNova: Proposed Federated Normalized Averaging Algorithm

FedNova removes objective inconsistency by aggregating normalized local updates with data-proportional weights. The resulting method accommodates varying local progress, local solvers, server optimizers, and client sampling while retaining convergence guarantees.

  • FedNova design: Setting w_i = p_i eliminates the objective-inconsistency term in the convergence bound and motivates FedNova.
  • FedNova design: FedNova averages normalized stochastic gradients rather than cumulative local parameter changes, then rescales the resulting update through the effective-step parameter.
  • FedNova design: The aggregation adjustment eliminates inconsistency in the solution and gives better convergence than previous methods.
  • Flexibility: FedNova permits varied local solvers, including decayed learning rates, proximal updates, and local momentum, while allowing τ_eff to be selected separately from the local solver.
  • Convergence analysis: Theorem 3 guarantees convergence to a stationary point of F(x) with arbitrarily varying local-update counts and gradient-accumulation methods.
  • Client sampling: With client sampling, FedNova retains a convergence rate expressed in terms of the number of selected clients q and communication rounds T.

6 Experimental Results

Experiments on synthetic and non-IID CIFAR-10 data show that FedNova consistently improves convergence and accuracy across heterogeneous client-update settings and local solvers.

  • Synthetic Dataset Simulations: FedNova converges significantly faster than FedAvg and achieves the best performance across three synthetic-data settings.The settings vary client participation and local epochs, including random time-varying epochs.
  • Non-IID CIFAR-10 Experiments: 6-9% higher test accuracy than FedAvg is achieved on non-IID CIFAR-10 with SGD or momentum-based client optimizers.The comparison uses 100 communication rounds.
  • Non-IID CIFAR-10 Experiments: About 10% higher test accuracy than FedProx is achieved by FedNova-Prox on non-IID CIFAR-10.FedNova-Prox corrects aggregation weights while retaining FedProx's proximal client updates.
  • Non-IID CIFAR-10 Experiments: FedNova preserves test accuracy when combined with SCAFFOLD and supports combinations of local momentum and variance reduction.The combined local-momentum and variance-reduction method achieves the highest test accuracy among the evaluated local solvers.
  • Effectiveness of Local Momentum: 3-7% higher test accuracy than vanilla SGD is generally achieved by using momentum SGD as the local solver.With Ei(t) ∼U(2, 5), hybrid momentum reaches 81.15 ± 0.38%, compared with 77.49 ± 0.25% for server momentum alone.

7 Concluding Remarks

The paper develops a theoretical framework for heterogeneous local progress, showing that FedAvg can optimize a mismatched objective, and validates FedNova's effectiveness theoretically and empirically.

  • Concluding Remarks: FedAvg can converge to stationary points of a mismatched objective that may be arbitrarily different from the true objective.The mismatch arises in the presence of heterogeneous client work within a communication round.
  • Concluding Remarks: FedNova's framework analyzes heterogeneous local steps and local solvers, including GD, SGD, proximal updates, momentum, and adaptive learning rates.The framework is intended to explain how heterogeneous local progress affects convergence rate and final-solution bias.
  • Concluding Remarks: FedNova with proximal updates achieves higher accuracy and faster convergence than the original FedProx.The comparison is reported for the non-IID CIFAR-10 experiments.
  • Concluding Remarks: 6-9% higher test accuracy than FedAvg is generally achieved by FedNova on non-IID CIFAR-10.The paper states that FedNova's effectiveness is validated both theoretically and empirically.

A Proof of Lemma 1: Objective Inconsistency in Quadratic Model

The lemma analyzes FedProx in a strongly convex quadratic setting to determine whether heterogeneous local updates converge to the intended global minimum.

  • Formulation: Each local objective is assumed to be strongly convex and represented using an invertible matrix and an arbitrary vector.The local minimizer is expressed using the matrix inverse and vector parameters.
  • Formulation: The global objective is defined as a weighted average of the local functions, and the proof studies convergence to its global minimum.The analysis asks whether existing federated optimization algorithms reach this minimum.
  • Local Update Rule: FedProx performs local updates with learning rate η, proximal parameter µ, and τi local steps before producing each client model.Setting µ = 0 reduces FedProx to FedAvg.
  • Local Update Rule: Ki(η, µ) captures the effect of the local update dynamics after τi steps in the quadratic model.It is defined through the matrix power of the local update operator and the inverse of Hi + µI.
  • Server Aggregation: The server averages all participating local models according to sample size before updating the central model.The derivation then examines the resulting central-model update over communication rounds.
  • Concrete Example in Lemma 1: With uniform weights, identity Hessian matrices, and µ = 0, the client-specific coefficient becomes Ki = 1 −(1 −η)^τi.For sufficiently small learning rates, the proof further simplifies the resulting expression using L’Hospital's rule.

B Detailed Derivations for Various Local Solvers

The derivations characterize how different local solvers accumulate stochastic gradients, providing the coefficients and normalization quantities used by the general aggregation rule.

  • General Local-Solver Representation: The local change at client i is represented through a non-negative accumulation vector ai over the round's stochastic gradients.The vector ai determines how gradients are locally accumulated.
  • General Local-Solver Representation: The local-model update rule is repeatedly expanded to express the accumulated gradient contributions across local iterations.These expansions produce solver-specific coefficients for the generalized update.
  • Proximal Updates: For proximal updates, ai = [(1 −α)^τi−1, (1 −α)^τi−2, . . . , (1 −α), 1] with α = ηµ.The coefficients encode the weighting induced by the proximal local-update rule.
  • Local Momentum: Local momentum SGD expands the momentum buffer to derive the coefficient assigned to each stochastic gradient.The derivation uses local momentum factor ρ and client momentum buffer ui.
  • Local Momentum: For local momentum, ai = [1 −ρ^τi, 1 −ρ^τi−1, . . . , 1 −ρ]/(1 −ρ), and its ℓ1 norm supplies the normalization quantity.The coefficient vector and its norm determine how momentum updates are normalized.

C Proof of Theorem 1: Convergence of Surrogate Objective

The proof develops bounds for heterogeneous local updates by introducing normalized gradient quantities, controlling stochastic and smoothness terms, and imposing learning-rate conditions for convergence.

  • Proof setup: The proof defines normalized stochastic and deterministic gradients to represent client updates with arbitrary nonnegative weighting coefficients.These quantities support analysis when clients perform different numbers of local updates.
  • Stochastic terms: Worker independence makes cross-worker stochastic-gradient terms vanish in expectation.The proof explicitly uses zero conditional means and independence across workers.
  • Bounding the recursion: Lipschitz smoothness, norm inequalities, Jensen’s inequality, and auxiliary lemmas bound the descent and model-drift terms.The proof repeatedly decomposes the error into terms and bounds each using these assumptions and inequalities.
  • Step-size conditions: The resulting recursion is simplified by defining D = 4η2L2 maxi{∥ai∥1(∥ai∥1 − ai,−1)} and requiring D < 1.A stronger displayed constraint further restricts D relative to β2.
  • Conclusion: Averaging across workers and communication rounds yields the final convergence result under the stated local-learning-rate constraints.The proof concludes after applying the assumptions and averaging the derived bounds.

D Proof of Theorem 2: Including Bias in the Error Bound

This section quantifies the gap between the true and surrogate objectives, establishes that heterogeneous FedAvg can retain non-vanishing bias, and analyzes how FedNova restores objective consistency.

  • Bias bound: Lemma 3 bounds the difference between gradients of the true objective F(x) and surrogate objective eF(x).The bound connects objective mismatch to the local-objective dissimilarity quantified by κ2.
  • Lower bound: A constructed strongly convex example shows that heterogeneous FedAvg need not converge to the global optimum, even as the learning rate approaches zero.The resulting gradient norm can remain nonzero, demonstrating that the error term is not merely an artifact of the analysis.
  • Lower bound: For two quadratic clients, FedAvg induces surrogate weights w1 = τ1/(τ1 + τ2) and w2 = τ2/(τ1 + τ2), tying objective bias to heterogeneous local steps.The construction relates the mismatch to the local-update counts and objective dissimilarity.
  • FedAvg: With equal client dataset sizes, FedAvg converges to a surrogate objective, while equal local steps recover previous convergence results and τi = 1 recovers synchronous SGD.The corresponding synchronous rate is 1/(mT).
  • FedProx: FedProx still converges to a surrogate objective because its aggregation weights differ from dataset-size weights, and its convergence rate matches FedAvg.A nonzero proximal parameter can improve the error bound by a constant, but does not remove objective inconsistency.
  • FedNova: FedNova sets aggregated weights equal to dataset proportions, making its surrogate objective identical to the original global objective.The consistency result extends to random client sampling with replacement according to probabilities pi = ni/n.

I More Experiments Details

Experiments compare FedAvg and FedNova on non-IID CIFAR10 under fixed and time-varying local epochs, and examine momentum, proximal correction, and aggregation-weight choices.

  • Experimental setup: Experiments use 16 TitanX-equipped machines as clients, PyTorch implementations, and three random seeds per experiment.The CIFAR10 setup uses mini-batch size 32, while the synthetic dataset uses mini-batch size 20.
  • Training curves on non-IID CIFAR10: FedNova requires about half as many communication rounds as FedAvg to reach the same test accuracy on non-IID CIFAR10.The reported training curves show FedNova outperforming FedAvg by a large margin.
  • Training curves on non-IID CIFAR10: Figure 7 varies local epochs between a fixed Ei = 2 setting and random time-varying Ei(t) ∼U(2, 5), with local momentum marked separately.The curves isolate aggregation-weight differences between FedAvg and FedNova.
  • Momentum and proximal variants: Figure 8 compares server, client, and hybrid momentum schemes in FedNova and contrasts FedNova-prox with vanilla FedProx.The caption identifies hybrid momentum as combining server and client momentum.
  • Proximal variants: FedNova-prox achieves around 10% higher accuracy than FedProx after correcting the aggregated weights.Using i=1 piτi instead of the default value improves FedProx accuracy by 5% before the further correction.
Loading 2007.07481v1…