Federated Learning Based on Dynamic Regularization

Durmus Alp Emre Acar; Yue Zhao; Ramon Matas Navarro; Matthew Mattina; Paul N. Whatmough; Venkatesh Saligrama

Source-linked AI summary

Federated Learning Based on Dynamic Regularization

Durmus Alp Emre Acar, Yue Zhao, Ramon Matas Navarro, Matthew Mattina, Paul N. Whatmough, Venkatesh Saligrama

arXiv:2111.04263v2Nov 8, 2021cs.LGcs.DC

TL;DR

Federated learning faces a communication bottleneck and a mismatch between local-device and global empirical-loss solutions. FedDyn uses dynamically updated device regularizers, enabling exact local minimization while aligning limiting device solutions with the global objective. Analytical and empirical results report efficient training across convex and non-convex settings, with robustness to heterogeneity, partial participation, large device populations, and unbalanced data.

Problem
Communication is costly in federated learning, while minimizing local device losses is inconsistent with minimizing the global empirical loss.
Method
FedDyn dynamically updates each participating device’s regularized objective so exact local minimization is asymptotically consistent with stationary points of the global empirical loss.
Results
FedDyn achieves convergence in convex and non-convex settings and significant communication savings across heterogeneous, partially participating, massively distributed, and unbalanced FL scenarios.
Takeaways & Limitations
The method supports communication-efficient federated training by trading increased device computation for reduced transmission while remaining robust across the evaluated FL conditions.
Takeaways & Limitations
The convergence rate for averaged empirical loss assumes moderate data imbalance; significant imbalance requires accounting for variance in data amounts per device.

Abstract

from arXiv · show

We propose a novel federated learning method for distributively training neural network models, where the server orchestrates cooperation between a subset of randomly chosen devices in each round. We view Federated Learning problem primarily from a communication perspective and allow more device level computations to save transmission costs. We point out a fundamental dilemma, in that the minima of the local-device level empirical loss are inconsistent with those of the global empirical loss. Different from recent prior works, that either attempt inexact minimization or utilize devices for parallelizing gradient computation, we propose a dynamic regularizer for each device at each round, so that in the limit the global and device solutions are aligned. We demonstrate both through empirical results on real and synthetic data as well as analytical results that our scheme leads to efficient training, in both convex and non-convex settings, while being fully agnostic to device heterogeneity and robust to large number of devices, partial participation and unbalanced data.

1 INTRODUCTION

Federated learning prioritizes communication efficiency, but local empirical-loss minimization can conflict with the global objective. FedDyn addresses this mismatch with dynamically regularized device objectives and reports convergence and communication benefits across diverse FL settings.

Motivation: Communication is a central FL constraint because bandwidth-limited devices incur high transmission and reception energy costs.The paper frames communication rounds and transmitted bits as fundamental evaluation criteria, while allowing more device computation.
A Fundamental Dilemma: Local empirical-loss minima can be inconsistent with minima of the global empirical loss, especially under heterogeneous device data.Prior methods address this through inexact local optimization or stabilized server updates.
Dynamic Regularization: FedDyn dynamically modifies each device objective with linear and quadratic penalties so limiting device solutions align with stationary points of the global empirical loss.The method shifts optimization burden toward devices to reduce communication.
Theory: FedDyn provides convergence guarantees in convex and non-convex settings, including sharp communication-round bounds for target accuracy.The introduction reports rates for non-convex smooth functions and convex settings with m devices and P active devices per round, though some formulas are incomplete in the supplied passage.
Experiments: Experiments on visual and language datasets show faster convergence and substantial communication savings versus competing approaches across participation, distribution, heterogeneity, and balance conditions.The evaluated datasets include MNIST, EMNIST, CIFAR-10, CIFAR-100, and Shakespeare.
Related Work: Related methods either rely on local SGD, require extra transmitted device variables, assume full participation, or use compression that is complementary to FedDyn.FedAvg can degrade in non-IID settings, while several distributed optimization methods do not directly support partial participation.

2 METHOD

FedDyn dynamically regularizes each participating device’s local empirical-risk objective so that consensus points align with stationary points of the global loss. Its analysis covers convex and non-convex settings, partial participation, and communication-efficient comparisons with prior methods.

FedDyn Method: FedDyn has each active device minimize its local empirical loss plus a dynamically updated penalty based on its local and received server models.The server samples active devices and transmits its current model each round; updated device models are returned to the server.
Intuitive Justification: Device stationary points generally conflict with global stationary points under heterogeneous data, making consensus and local-loss minimization incompatible.At a global stationary point, individual device gradients can remain non-zero when device distributions differ.
Key Property of Algorithm 1: If local device models converge to a common point, FedDyn’s key property ensures that this consensus point is a stationary point of the global risk.The server-state argument yields a vanishing aggregate of device gradients at the limiting consensus point.
Convergence Analysis: Theorem 1 provides convergence rates for strongly convex, convex, and non-convex local losses when a constant number of devices is sampled uniformly each round.For convex smooth functions, the expected global loss converges at a stated O rate; for non-convex smooth functions, average active-device models converge in expectation to a stationary point at a stated O rate.
Convergence Analysis: The convergence guarantees are conventionally stated for device-averaged empirical loss and require adjustment for significant data imbalance that scales with device data size.The bounds are taken in expectation over random active-device choices, and their problem-dependent constants depend partly on initialization.
Comparison with Prior Methods: FedDyn communicates fewer bits than SCAFFOLD because SCAFFOLD transmits both a model and gradient, while FedDyn uses a dynamically modified local risk.The paper attributes FedDyn’s improved theoretical and practical rate in rounds to this algorithmic difference, while noting that the extra term in FedDyn is a surrogate for an unavailable gradient.

3 EXPERIMENTS

Experiments evaluate FedDyn against competing methods on synthetic and real benchmark datasets across partial participation, device scale, heterogeneous distributions, and unbalanced data. FedDyn consistently reduces communication, with especially large gains in massively distributed settings.

Experimental Setup: FedDyn is evaluated on MNIST, EMNIST-L, CIFAR-10, CIFAR-100, Shakespeare, and synthetic data under four federated-learning scenarios.The scenarios vary device participation, device count, data heterogeneity, and local-data balance.
Experimental Setup: FedDyn, SCAFFOLD, FedAvg, and FedProx are compared using transmitted models required to reach target accuracy, rather than communication rounds alone.This metric accounts for SCAFFOLD transmitting both the current model and an associated gradient per round.
Moderate vs. Large Number of Devices: 4.8× and 2.9× gains over SCAFFOLD are reported for CIFAR-10 IID settings in massive and moderate device regimes, respectively.SCAFFOLD does not reach 80% within 2000 rounds in the massive setting, so the actual massive-setting saving exceeds 4.8×.
Full vs. Partial Participation Levels: 2.9× to 9.4×, 4.0× to 12.8×, and 4.2× to 7.9× communication gains are reported for CIFAR-10 as participation increases across device-distribution settings.The experiments report similar performance increases for full participation on most datasets.
Balanced vs. Unbalanced Data: 4.3× gains over SCAFFOLD are reported for achieving target accuracy with unbalanced data using 100 devices and 10% participation.The reported gains increase with the target accuracy.
IID vs. non-IID Device Distribution: Communication savings increase from 2.9×, 4.0× to 4.2× as CIFAR-10 device distributions become more non-IID under 10% participation.The paper reports the same qualitative pattern for MNIST, EMNIST-L, Shakespeare, and CIFAR-10 unbalanced settings, but not a significant difference for full participation.
Summary: FedDyn consistently achieves substantial communication savings across the evaluated federated-learning regimes, with large gains in massively distributed data settings.The comparison uses the chosen model architectures; higher-capacity models can achieve higher dataset performance.

4 CONCLUSION

FedDyn uses dynamic regularization and exact minimization to align participating-device optima with the global empirical loss. The method is reported to train efficiently across convex and non-convex settings and varied federated conditions.

FedDyn dynamically updates each participating device’s regularizer so its regularized-loss optimum conforms with the global empirical loss.
The method combines empirical and analytical evidence for efficient training in convex and non-convex settings.
FedDyn is reported to have convergence rate O(T) and a linear rate in strongly convex settings.
The scheme is described as agnostic to device heterogeneity and robust to large device populations, partial participation, and unbalanced data.

A.1.1 SYNTHETIC DATA

The synthetic dataset models device heterogeneity through device-specific optima, feature distributions, and data quantities. Experiments compare FedDyn with competing federated methods and report communication savings across the tested settings.

Dataset: Synthetic labels are generated from device-specific optimal parameters for a five-class classification task with 30-dimensional features.
Dataset: Device-specific parameters, feature means, and sample counts generate three distinct heterogeneity types controlled by γ1, γ2, and γ3.
Dataset: Experiments isolate each heterogeneity type by disabling the other two and also include combined heterogeneous settings.
Models and settings: FedDyn, SCAFFOLD, FedAvg, and FedProx are evaluated with multiclass logistic classification and cross-entropy loss.
Results: 1.1× to 7.6× communication savings are reported for FedDyn relative to one round of FedAvg across the tested settings with 10% participation.

A.2 REAL DATA

Real-data experiments evaluate federated methods across image and language datasets, IID and non-IID splits, participation levels, device scales, and balanced or unbalanced data. FedDyn is reported to outperform baselines across these settings, including a higher-capacity CIFAR-10 model and varying α values.

Datasets: Experiments use MNIST, EMNIST-L, CIFAR-10, CIFAR-100, and Shakespeare for image classification and next-character prediction.
Data partitioning: IID splits randomly assign training data to devices, while non-IID splits use Dirichlet-distributed class priors.
Data partitioning: Unbalanced data are generated with lognormal device sample counts, producing standard deviations of 0 for balanced CIFAR-10 and 0.3 for unbalanced CIFAR-10.
Model capacity: FedDyn still outperforms baselines with a ResNet18 model using group normalization on CIFAR-10 under 10% participation.
Hyperparameter sensitivity: The best test performance in the CIFAR-10 α-sensitivity experiment occurs at α = 10^-1, although all tested configurations converge.

A.4 COMPARISON TO A FULL PARTICIPATION METHOD

The section compares FedDyn with FedSplit, a method originally formulated for full device participation, and describes adaptations for partial participation. FedDyn is reported to outperform FedSplit in CIFAR-10 experiments, while broader figures and tables cover participation, heterogeneity, and communication settings.

Comparison to a Full Participation Method: FedSplit was introduced for non-IID data but assumes full device participation, whereas the target FL setting includes partial participation.The section identifies partial participation as critical because not all devices can be expected to participate in every round.
Comparison to a Full Participation Method: The partial-participation adaptations freeze inactive devices’ models and intermediate states during a round.The server model can average all device models or only the currently active devices, producing FedSplit All and FedSplit Act.
Comparison to a Full Participation Method: FedDyn performs better than FedSplit in CIFAR-10 experiments under both 100% and 10% participation.FedSplit All substantially underperforms FedSplit Act when the server averages all device models rather than only active devices.
Comparison to a Full Participation Method: Communication comparisons report transmitted parameters relative to one FedAvg round across 10% and 1% participation regimes and a convex synthetic problem.The tables account for SCAFFOLD transmitting both the current model and its associated gradient per round.

B.1 CONVEX ANALYSIS

The convex analysis develops auxiliary bounds for Algorithm 1 and combines them to establish Theorem 2. The proof tracks model distance, gradient approximation, and local-model variation under smoothness and convexity assumptions.

Theorem 2 states a convergence result for convex, L-smooth device losses.
The analysis introduces Ct and ϵt to track gradient approximation and local-model changes, respectively.Both quantities are described as vanishing when the models converge to θ∗.
The proof uses smoothness, Jensen’s inequality, conditional expectations, and telescoping to derive the convergence statement.
Lemma 1 controls the squared distance to θ∗ by expanding the update difference and bounding the resulting terms.The proof uses additional lemmas to handle (γt − γt−1) and ∥γt − γt−1∥2 terms.
Lemmas 2–5 provide bounds for Algorithm 1, including the excess ϵt term required by Lemma 3.The bounds are combined with scaled versions of Lemmas 4 and 5 to prove Lemma 1.

B.2 STRONGLY CONVEX ANALYSIS

The strongly convex analysis extends the convex proof by modifying the smoothness-related bound and reusing the auxiliary lemmas. It then establishes Theorem 3 under strong convexity and smoothness assumptions.

Theorem 3 states a convergence result for μ-strongly convex, L-smooth device losses.The theorem defines γt as a weighted average and θ∗ as the minimizer of the global objective.
Lemma 8 supplies the principal strongly convex bound used to derive Theorem 3.Its proof expands ∥γt − θ∗∥2, applies Eq. 11 and Lemma 9, and rearranges the resulting inequality.
The proof generalizes the convex analysis to strongly convex functions by changing Eq. 6.Because strongly convex functions are convex, Lemmas 2–5 can be reused after this modification.
The final argument scales auxiliary lemmas by coefficients whose positivity follows from the stated condition on α, then sums the resulting inequalities.
Lemma 9 provides an additional bound for Algorithm 1 using Jensen’s inequality and conditional expectation over device participation.

B.3 NONCONVEX ANALYSIS

The nonconvex analysis establishes convergence guarantees for FedDyn and develops a one-gradient-step variant with matching asymptotic rates. The analysis also tracks local-model approximation errors and supports communication-efficient device updates.

FedDyn provides convergence results for nonconvex smooth local losses toward a stationary point.
The analysis tracks auxiliary quantities whose values approach zero when local models approximate the active-device average at convergence.The passage states that C_t and ε_t become 0 upon convergence.
FedDynOneGD performs one gradient-descent update per active device instead of fully minimizing the local objective.This reduces device optimization effort while retaining the dynamic-regularization framework.
FedDynOneGD has the same asymptotic convergence-rate guarantees as FedDyn.
The FedDynOneGD convergence theorem assumes a constant number of devices selected uniformly at random in each round and a suitably chosen α > 0.

C.2.1 STRONGLY CONVEX ANALYSIS

The strongly convex analysis proves linear convergence for FedDyn under smoothness and strong-convexity assumptions. The proof combines auxiliary lemmas, telescoping bounds, and a condition on the regularization parameter.

The proof uses auxiliary lemmas to bound model-disagreement and excess-error terms before summing them into telescoping expressions.
The convergence proof relies on the local losses being convex and L-smooth in the relevant strongly convex setting.
The analysis imposes a lower-bound condition on α so the coefficients used to combine the lemmas remain positive.
For strongly convex and smooth local losses, a weighted average of active-device averages converges in expectation at a linear rate.

C.2.3 NONCONVEX ANALYSIS

The nonconvex analysis extends the strongly convex proof strategy by refining auxiliary bounds for smooth functions. It establishes an expected convergence rate for active-device models and compares the analysis with prior work.

For nonconvex and smooth local losses, the average of active-device models converges in expectation to a stationary point.
The proof refines earlier auxiliary lemmas and combines scaled bounds to obtain telescoping terms.
The nonconvex analysis assumes a sufficiently large α so that the coefficients in the combined inequalities are positive.
The paper reports that Karimireddy et al. (2019) obtained a convex convergence analysis matching FedDyn’s rate, while raising an empirical-verification issue for a SCAFFOLD nonconvex lemma.