Home / Curated / Algorithms / FedPA (Federated Posterior Averaging via Local MCMC and Shrinkage Covariance)

FedPA (Federated Posterior Averaging via Local MCMC and Shrinkage Covariance)

Algorithms AIMech:FedPaFederatedPosteriorAveragingViaLocalMcmcAndShrinkageCovariance DRAFT

Aliases: FedPA, Federated Posterior Averaging, Federated Learning via Posterior Averaging

A Bayesian posterior-inference federated learning algorithm (Al-Shedivat et al. 2021, Algorithms 1-2) that decomposes the global posterior under a uniform prior into a product of local client posteriors P(theta | D) propto prod_{i=1}^N P(theta | D_i), approximates each client posterior with a Gaussian N(mu_hat_i, Sigma_hat_i) whose mean and Ledoit-Wolf shrinkage covariance Sigma_hat_ell = rho_ell I + (1 - rho_ell) S_hat_ell (rho_ell = 1 / (1 + (ell - 1) rho)) are estimated from ell local stochastic-gradient MCMC (Iterate-Averaged SGD) samples, and transmits only the preconditioned vector update Delta_hat_i = Sigma_hat_i^{-1} (theta^{t-1} - mu_hat_i) computed online in O(ell^2 d) time and O(ell d) memory via rank-1 Sherman-Morrison dynamic programming.

Identity Notes & Concept Scope Distinct from FedAvg and FedOpt (AIMech:FedOptAdaptiveServerOptimizationFedAdagradFedYogiFedAdam), which correspond to the biased identity-covariance special case Sigma_hat_i = I (rho = 0) and converge to the arithmetic mean of local modes rather than the global posterior mode (sum_i q_i Sigma_i^{-1})^{-1} (sum_i q_i Sigma_i^{-1} mu_i) when client posteriors have heterogeneous anisotropic curvatures, and from FedMA (AIMech:FedMaFederatedMatchedAveragingViaLayerWiseBayesianNonparametricMatching, which uses a Beta-Bernoulli Process for layer-wise neuron permutation matching rather than local MCMC sampling and shrinkage covariance preconditioning).

Claims & Grounded Evidence

4 Claims

Mechanism #r412-gaussian-posterior-product-quadratic-objective-and-fedavg-identity-covariance-bias

Propositions 1 and 2 show that under local Laplace/Gaussian posterior approximations N(mu_i, Sigma_i), the global posterior mode mu = (sum_{i=1}^N q_i Sigma_i^{-1})^{-1} (sum_{i=1}^N q_i Sigma_i^{-1} mu_i) minimizes the global quadratic objective Q(theta) = (1/2) theta^T (sum_i q_i Sigma_i^{-1}) theta - (sum_i q_i Sigma_i^{-1} mu_i)^T theta whose stochastic client gradient is Delta_i = Sigma_i^{-1}(theta - mu_i), revealing that FedAvg implicitly sets Sigma_i = I and therefore converges to a biased fixed point whenever client precision matrices Sigma_i^{-1} are heterogeneous and anisotropic.

supports Source: Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms · Locator: Section 3.2-3.3 (Propositions 1 and 2, Eqs. 3-6, Figure 1)

Mechanism #r412-sherman-morrison-dynamic-programming-for-matrix-free-shrinkage-covariance-inversion

Theorem 3 and Appendix C (Algorithm 2) prove that using the Ledoit-Wolf shrinkage covariance estimator Sigma_hat_ell = rho_ell I + (1 - rho_ell) S_hat_ell with rho_ell = 1 / (1 + (ell - 1) rho) over ell local MCMC epoch means x_1,...,x_ell, the unnormalized matrix tilde_Sigma_t = I + rho (t - 1) S_hat_t satisfies the rank-1 recurrence tilde_Sigma_t = tilde_Sigma_{t-1} + gamma_t u_t u_t^T with u_t = x_t - bar_x_{t-1} and gamma_t = rho (t - 1) / t, enabling exact computation of Delta_hat_ell = Sigma_hat_ell^{-1}(x_0 - bar_x_ell) in O(ell^2 d) time and O(ell d) memory without ever instantiating or communicating a d x d matrix.

supports Source: Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms · Locator: Section 4.2 Efficient Local Posterior Covariance Estimation (Theorem 3, Eq. 8) & Appendix C (Algorithm 2)

Limitation #r412-burn-in-epochs-and-local-sample-storage-limitation

FedPA requires an initial burn-in phase of communication rounds before activating posterior covariance preconditioning so that local SG-MCMC chains mix near a local mode, and each client must store ell >= 2 d-dimensional epoch-mean vectors during local training to form rank-1 covariance updates.

supports Source: Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms · Locator: Section 4.1-4.3 (Table 1, Algorithm 1) & Section 5

Application #r412-federated-emnist-cifar100-stackoverflow-and-reddit-benchmarks-application

Evaluated on federated EMNIST-62, CIFAR-100, StackOverflow tag prediction and next-word prediction, and Reddit language modeling, improving convergence speed and final test accuracy over FedAvg and adaptive FedOpt baselines.

supports Source: Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms · Locator: Section 5 Experiments (Tables 2-3, Figures 2-4)

⚠️ Curated Limitations & Negative Results

Requires burn-in communication rounds before activating covariance preconditioning.
Clients must store ell >= 2 epoch-mean sample vectors during each local round.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	broad_match	FedPA is a Bayesian posterior-averaging algorithm for Federated Learning.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r412-primary-pdf`	Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms Maruan Al-Shedivat, Jennifer Gillenwater, Eric P. Xing, Afshin Rostamizadeh	primary paper full_text	ID: https://openreview.net/forum?id=GFsU8a0sGB sha256:aa28ea4d73cf…
`r412-arxiv-abs`	Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms (arXiv abstract) Maruan Al-Shedivat, Jennifer Gillenwater, Eric P. Xing, Afshin Rostamizadeh	primary paper abstract_only	ID: https://arxiv.org/abs/2010.05273 sha256:aee73b9afd8e…
`r412-metadata-cr`	Federated Learning via Posterior Averaging: A New Perspective and Practical Algorithms (Crossref metadata) Maruan Al-Shedivat, Jennifer Gillenwater, Eric P. Xing, Afshin Rostamizadeh	primary paper abstract_only	ID: https://openreview.net/forum?id=GFsU8a0sGB sha256:8f7c4f3ba9dd…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

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

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

Source File: data/curated/FedPaFederatedPosteriorAveragingViaLocalMcmcAndShrinkageCovariance.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