Home / Curated / Algorithms / FedPD (Federated Primal-Dual Optimization with Adaptivity to Non-IID Data)

FedPD (Federated Primal-Dual Optimization with Adaptivity to Non-IID Data)

Algorithms AIMech:FedPdFederatedPrimalDualOptimizationWithAdaptivityToNonIidData DRAFT

Aliases: FedPD, Federated Primal-Dual Optimization, FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data

A primal-dual federated optimization framework (Zhang et al. 2021, Algorithm 1) for smooth possibly non-convex consensus problems min_{x_0, {x_i}} sum_{i=1}^N w_i f_i(x_i) subject to x_i = x_0 that minimizes the separable client augmented Lagrangian L_i(x_i, x_0^r, lambda_i^r) = f_i(x_i) + <lambda_i^r, x_i - x_0^r> + (1 / (2 eta)) ||x_i - x_0^r||^2 via Q local gradient or stochastic-gradient steps (Oracle I or II), and then with probability 1 - p communicates with the server to aggregate x_0^{r+1} = sum_{i=1}^N w_i (x_i^{r+1} + eta lambda_i^r) and update dual variables lambda_i^{r+1} = lambda_i^r + (1 / eta)(x_i^{r+1} - x_0^{r+1}), or with probability p in [0, 1) skips global communication by setting x_0^{r+1} = x_0^r and lambda_i^{r+1} = lambda_i^r.

Identity Notes & Concept Scope Distinct from FedDyn (AIMech:FedDynFederatedLearningBasedOnDynamicRegularization, which analyzes convex/strongly convex objectives under partial client participation with a server state vector h^t), from FedSplit (AIMech:FedSplitOperatorSplittingForFastFederatedOptimization, which applies Peaceman-Rachford reflection splitting to convex monotone inclusions without randomized communication skipping p), and from Computation-Then-Aggregation (CTA) primal methods such as FedAvg and FedProx, which diverge on unconstrained non-convex objectives with Q > 1 local steps unless inter-client gradient dissimilarity is bounded (Claim 2.2).

Claims & Grounded Evidence

4 Claims

Mechanism #r411-cta-lower-bound-and-fedavg-divergence-under-unbounded-non-iid-gradients

Claim 2.1 (Theorem 2) establishes an Omega(1 / epsilon) communication-round lower bound for any Computation-Then-Aggregation (CTA) algorithm on L-smooth non-convex objectives, and Claim 2.2 (with Claim D.2) proves that FedAvg with Q > 1 local steps diverges on the 1D L-smooth pair f_1(x) = (1/2) x^2, f_2(x) = -(1/2) x^2 without bounded-gradient or bounded-dissimilarity assumptions because the per-round update amplification matrix (1/2) D^{Q-1} 1 1^T D has spectral radius ((1 + eta)^Q + (1 - eta)^Q) / 2 > 1.

supports Source: FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data · Locator: Section 2 Fundamental Limits of Federated Learning (Definition 2.1, Claims 2.1-2.2) & Appendices C-D

Mechanism #r411-optimal-nonconvex-rate-and-non-iid-adaptive-communication-skipping

Theorem 1 proves that for any penalty step size 0 < eta < (sqrt(5) - 1) / (4 L), FedPD with p = 0 converges to an epsilon-stationary and consensus solution in T = O(1 / epsilon) rounds without any data homogeneity or bounded-gradient assumption, while under delta-non-IID gradient dissimilarity ||nabla f_i(x) - nabla f(x)|| <= delta (Assumption A5), choosing communication-skip probability p such that p / (1 - p)^2 = O(epsilon / delta^2) reduces total communication rounds to C = T (1 - p) while preserving O(1 / epsilon) computation complexity.

supports Source: FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data · Locator: Section 4 Convergence Analysis (Theorem 1, Table 1) & Appendix F

Limitation #r411-full-client-participation-and-dual-variable-storage-limitation

Standard FedPD requires clients to maintain persistent local primal-dual iterates (x_i^r, lambda_i^r) across communication rounds and assumes all N clients participate whenever the global aggregation event (Bernoulli(1 - p)) triggers.

supports Source: FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data · Locator: Section 3 (Algorithm 1, Eq. 9) & Section 4 (Theorem 1)

Application #r411-non-iid-mnist-and-federated-speech-command-recognition-application

Applied to non-IID MNIST convolutional classification and Google Speech Commands recognition across distributed clients, outperforming FedAvg, FedProx, and SCAFFOLD in accuracy versus communication rounds.

supports Source: FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data · Locator: Section 6 Numerical Results (Figures 2-6)

⚠️ Curated Limitations & Negative Results

Requires persistent client dual variables lambda_i^r across communication rounds.
Standard convergence analysis assumes full client participation during global aggregation steps.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	broad_match	FedPD is a primal-dual augmented Lagrangian optimization method for Federated Learning.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r411-primary-pdf`	FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, Yang Liu	primary paper full_text	ID: https://doi.org/10.1109/TSP.2021.3115952 sha256:dd2aad49d384…
`r411-arxiv-abs`	FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data (arXiv abstract) Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, Yang Liu	primary paper abstract_only	ID: https://arxiv.org/abs/2005.11418 sha256:472389ec9373…
`r411-metadata-cr`	FedPD: A Federated Learning Framework With Adaptivity to Non-IID Data (Crossref metadata) Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, Yang Liu	primary paper abstract_only	ID: https://doi.org/10.1109/TSP.2021.3115952 sha256:f8fb44bf0e96…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T08:14:00Z

Updated: 2026-10-19T08:14:00Z

Source File: data/curated/FedPdFederatedPrimalDualOptimizationWithAdaptivityToNonIidData.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories