PaperlayerView exact revision on arXiv

Source-linked AI summary

Federated Asymptotics: a model to compare federated learning algorithms

Gary Cheng, Karan Chadha, John Duchi

arXiv:2108.07313v3cs.LGcs.DCmath.OCstat.ML

TL;DR

The paper addresses how to compare personalized and non-personalized federated learning methods when each client has its own loss but limited local data. It develops a high-dimensional asymptotic multi-criterion framework based on linear regression and evaluates its predictions on four federated datasets. The theory and experiments indicate that fine-tuned FedAvg can match more complex personalization methods and outperform FedAvg without personalization in the studied setting.

  • Problem

    Existing federated methods lack precise performance comparisons for client-specific objectives, especially beyond convergence analyses.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes collaborate-then-personalize algorithms through a high-dimensional asymptotic linear regression model and evaluates asymptotic client test risk.

    Source: §1 · p. 2, §3.1 · p. 4

  • Results

    Fine-tuned FedAvg matches the asymptotic risk of more intricate meta-learning and proximal approaches, while experiments on EMNIST, CIFAR-100, Shakespeare, and Stack Overflow corroborate the theoretical predictions.

    Source: §1 · pp. 2, 8, §4.2 · p. 9

  • Takeaways & Limitations

    The framework provides a way to compare actual federated-learning losses and suggests that simple personalization may achieve the benefits of more complex methods in the studied model.

    Source: §1 · pp. 2, 9

    The conclusions are established in a stylized linear model, and pFedMe could not be run on Stack Overflow because its runs took significantly longer.

    Source: §8.2.2 · p. 40

Abstract

from arXiv · show

We propose an asymptotic framework to analyze the performance of (personalized) federated learning algorithms. In this new framework, we formulate federated learning as a multi-criterion objective, where the goal is to minimize each client's loss using information from all of the clients. We analyze a linear regression model where, for a given client, we may theoretically compare the performance of various algorithms in the high-dimensional asymptotic limit. This asymptotic multi-criterion approach naturally models the high-dimensional, many-device nature of federated learning. These tools make fairly precise predictions about the benefits of personalization and information sharing in federated scenarios -- at least in our (stylized) model -- including that Federated Averaging with simple client fine-tuning achieves the same asymptotic risk as the more intricate meta-learning and proximal-regularized approaches and outperforming Federated Averaging without personalization. We evaluate these predictions on federated versions of the EMNIST, CIFAR-100, Shakespeare, and Stack Overflow datasets, where the experiments corroborate the theoretical predictions, suggesting such frameworks may provide a useful guide to practical algorithmic development.

1 Introduction

Federated learning must balance client-specific risks against the data efficiency of shared models, yet existing personalization methods lack precise performance comparisons. This paper develops a high-dimensional asymptotic framework to compare such algorithms and tests its predictions empirically.

Motivation

  • The multi-criterion objective targets each client’s risk, but solving it locally is data-limited, motivating tractable shared or personalized alternatives.Federated learning typically replaces direct minimization of every client risk with objectives such as weighted average loss.Source: §1 · p. 1
  • Zero personalization benefits from plentiful pooled data and simpler engineering, but non-identical client distributions motivate methods targeting client-specific performance.The paper frames this as a trade-off between shared-data efficiency and personalization.Source: §1 · p. 2

Related Work

  • Existing personalization methods often assume client optima are close and emphasize convergence, leaving the performance of their attained solutions insufficiently characterized.This gap motivates direct asymptotic risk comparisons rather than convergence-rate analyses alone.Source: §1 · pp. 2–3

Contributions

  • The paper introduces a stylized high-dimensional linear regression model for characterizing collaborate-then-personalize algorithms in the asymptotic limit.The framework is intended to compare actual client performance across federated procedures.Source: §1 · p. 2
  • The framework evaluates asymptotic test loss for fine-tuned FedAvg, meta-learning, and proximal-regularized personalization methods.Fine-tuned FedAvg learns an average global model and then updates it using local data.Source: §1 · p. 2
  • Theory predicts that simple fine-tuning can match more sophisticated methods and identifies conditions favoring collaboration or personalization; experiments on four federated datasets are consistent with these predictions.The datasets are EMNIST, CIFAR-100, Shakespeare, and Stack Overflow.Source: §1 · p. 2

2 The Linear Model

The paper models each client as an overparameterized linear regression problem with related parameters and evaluates per-client prediction risk in a high-dimensional, many-device asymptotic regime. Client heterogeneity is represented through parameter variation and feature covariances, while shared structure enables information transfer.

Model

  • Each client has an overparameterized linear regression problem with a client-specific parameter, local observations, centered features, and finite-variance noise.The local sample size is smaller than but comparable to the model dimension.Source: §2 · p. 3
  • Clients share a parameter center while differing through label-shift radii and covariate-shift feature covariances.These differences model client heterogeneity while preserving statistically related tasks.Source: §2 · p. 3

Information Sharing

  • Data from other clients is useful because it provides information about the possible location of a target client’s parameter, under independence assumptions across features, parameters, and noise.This formalizes the role of collaboration in the model.Source: §2 · p. 3

Risk

  • The target is each client’s population squared prediction loss on an independent test sample, evaluated conditionally on the training data.The analysis emphasizes per-client performance rather than only aggregate loss.Source: §2 · p. 3

Asymptotics

  • The asymptotic regime sends the number of clients, dimension, and local sample sizes to infinity while keeping dimension-to-sample ratios fixed.This captures the high-dimensional and many-device structure of federated learning.Source: §2 · p. 4

Assumptions

  • Individual devices remain overparameterized, with γ_j > 1, and the analysis controls the data covariance eigenspectrum and sufficient moments.These assumptions support convergence of covariance estimates and spectral limits.Source: §2 · p. 4

3 Locally fine-tuning a global solution

This section analyzes federated algorithms that personalize a globally learned solution through local fine-tuning, deriving asymptotic risks and comparing them with non-personalized and non-collaborative baselines.

3.1 Fine-tuned Federted Averaging (FTFA)

  • FTFA first learns a weighted global model from all clients, then independently fine-tunes each client model using local empirical risk.This parallel local phase is essentially no more expensive than Federated Averaging.Source: §3.1 · pp. 4–5
  • The analysis characterizes FTFA’s asymptotic prediction bias, variance, and test loss under high-dimensional assumptions, including closed forms for identity covariance.The client sample size is smaller than but comparable to the model dimension.Source: §3.1 · p. 5

3.2 Ridge-tuned FedAvg (RTFA)

  • Ridge-tuned FedAvg with an optimal hyperparameter has lower test loss than FTFA and mitigates FTFA’s weaknesses.The ridge solution approaches the minimum ℓ2-norm interpolant as regularization tends to zero.Source: §3.2 · p. 6, §3.3 · p. 7

3.3 Comparison to Naive Estimators

  • The gap between collaborative and non-collaborative solutions is governed by differences between client-specific radii, including in the ridge-based comparison.A first-order expansion establishes the ridge-based relationship when the relevant radii are near one another.Source: §3.3 · p. 7
  • FTFA outperforms FedAvg and the zero-collaboration estimator, showing benefits from combining global information with local personalization.The comparison is made against both zero personalization and zero collaboration baselines.Source: §3.3 · pp. 6–7
  • RTFA with appropriate regularization outperforms the zero-personalization estimator and the ridgeless zero-collaboration estimator.The ridge-based procedure is analyzed through asymptotic test-loss expressions under the same theorem conditions.Source: §3.2 · p. 6, §3.3 · p. 7

4 Meta learning and Proximal Regularized Algorithms

This section evaluates meta-learning and proximal-regularized federated procedures using the paper’s asymptotic framework. It argues that these more sophisticated approaches perform no better than the fine-tuning methods in this framework.

4 Meta learning and Proximal Regularized Algorithms

  • Meta-learning and proximal-regularized approaches perform no better asymptotically than FTFA and RTFA.The section develops predictive and statistical analyses beyond the convergence-rate results previously available for these methods.Source: §4 · p. 7

4.1 Model-Agnostic Meta-Learning

  • MAML-FL adapts Model-Agnostic Meta-Learning to federated learning through a two-step procedure evaluated at one-step-updated parameters.Its variants either ignore the Hessian term or approximate it with finite differences.Source: §4.1 · pp. 7–8
  • The MAML-FL variants were previously shown to converge to stationary points for general non-convex smooth functions, but their predictive performance had not been characterized.This paper analyzes their performance within the high-dimensional asymptotic framework.Source: §4 · p. 7, §4.1 · p. 8

1. Server and clients coordinate to (approximately) solve

The paper analyzes federated personalization by characterizing asymptotic test risk for meta-learning and proximal-regularized procedures in a high-dimensional linear model. The analyses indicate that simpler fine-tuning procedures can match more intricate approaches under stated conditions.

1. Server and clients coordinate to (approximately) solve

  • MAML-FL combines a server-coordinated global model with client-side empirical-risk optimization initialized at that global model.The asymptotic analysis represents the client step as a minimum-norm interpolant after local optimization converges.Source: §1 · p. 8
  • MAML-FL has the same asymptotic test risk as FTFA, while its objective and gradient computation can make optimization more challenging and expensive.The analyzed procedure assumes converged local first-order optimization and requires conditions controlling client covariance behavior.Source: §1 · pp. 8–9

4.2 Proximal-Regularized Approach

  • The proximal method jointly uses global and local parameters, with a penalty encouraging local models to remain close to one another.In the linear model, the resulting global and local estimators can be analyzed through asymptotic prediction bias and variance.Source: §4.2 · p. 9
  • The reported empirical visuals summarize best-average-worst intervals across train-validation splits or random seeds for EMNIST, CIFAR-100, Shakespeare, and Stack Overflow.The supplied captions identify variability summaries and personalization-gain figures, but do not state numerical winners.Source: §4.2 · p. 10, Figure 1 · p. 10, Figure 3 · p. 10
  • The proximal-regularized approach has asymptotic test loss identical to locally ridge-regularized RTFA.This comparison is made in the linear model under appropriately chosen hyperparameters and the stated asymptotic assumptions.Source: §4.2 · pp. 9–10

5 Experiments

The experiments evaluate federated algorithms on semi-synthetic classification tasks using pre-trained neural-network top layers. Across datasets, personalization methods generally outperform zero-communication and zero-personalization baselines, while simpler fine-tuning performs similarly to more complex approaches.

Scope

  • The statistical model is stylized and does not fully represent practical federated learning settings.Source: §5 · p. 10

Experimental setting

  • The experiments use 400 communication rounds, evaluate test accuracy every 50 rounds, and tune methods across seeds and training-validation splits.Source: §5 · pp. 10–11
  • The semi-synthetic setup refits the top layer of a pre-trained network, preserving convex distributed models and avoiding the degradation reported for full deep-model federated training.The authors also use held-out data to pre-train a preliminary Stack Overflow network.Source: §5 · p. 11

Results

  • FTFA, RTFA, and MAML-FL have similar test accuracy, with nearly identical performance on Stack Overflow and EMNIST.These larger datasets are consistent with the paper’s theoretical predictions.Source: §5 · p. 11
  • Zero-communication and zero-personalization methods perform worse than FTFA, RTFA, and MAML-FL in all figures.Source: §5 · p. 11
  • pFedMe performs worse than FTFA, RTFA, and MAML-FL in Figures 1 to 3.Source: §5 · p. 11

Personalization steps

  • The global model is worst, and test accuracy improves monotonically with more personalization steps for FTFA and MAML-FL.Because personalization steps are cheaper than centralized training, the results suggest locally training clients toward convergence.Source: §5 · p. 11

6 Proofs

The proofs establish asymptotic risk expressions for federated linear-regression estimators by combining high-dimensional random-matrix results with bias-variance decompositions. They introduce notation and lemmas needed to control covariance, moment, and error terms.

6.1 Additional Notation

  • The analysis defines client and pooled design matrices, response vectors, empirical covariance matrices, and asymptotic norm notation.Source: §6.1 · p. 14

6.2 Useful Lemmas

  • The proof toolkit bounds random-design and covariance terms using Rademacher inequalities, moment assumptions, operator norms, and matrix perturbation results.Source: §6.2 · pp. 14–16

6.3 Some useful definitions from previous work

  • The risk formulas are expressed through the covariance spectrum and the true regression parameter’s coordinates in the covariance eigenbasis.The analysis uses empirical spectral distributions and related reweighted distributions from prior high-dimensional regression work.Source: §6.3 · pp. 16–17

6.4 Proof of Theorem 1

  • For Theorem 1, the proof solves the federated estimator, decomposes risk into bias and variance, and applies high-dimensional regression limits to each term.Source: §6.4 · pp. 17–18, Bias · pp. 18, 20

Bias:

6.5 Proof of Theorem 2

Theorem 2 is proved by analyzing the global and personalized estimators through asymptotic bias and variance. The argument controls approximation errors probabilistically and applies high-dimensional regression limits to the remaining terms.

6.5 Proof of Theorem 2

  • The proof starts from closed-form global and personalized estimators and decomposes their risks into bias and variance.Source: §6.5 · p. 22

Bias Proof Outline

  • The bias proof shows that error events vanish asymptotically and bounds the resulting estimator perturbation under the stated covariance and norm conditions.Source: §6.5 · p. 22, Bias Proof Outline · p. 23
  • High-dimensional regression results provide the limiting bias expression, with the identity-covariance specialization obtained from a prior corollary.Source: Bias Proof Outline · p. 23

Variance:

  • The variance proof separates three terms, bounds the first two using Schatten-norm inequalities and covariance operator bounds, and evaluates the final term using a high-dimensional limit.Source: Variance · p. 24
  • The limiting variance term is characterized through empirical and weighted empirical spectral distributions, with an identity-covariance specialization from prior work.Source: Variance · p. 25

6.6 Proof of Theorem 3

Theorem 3 follows the same asymptotic strategy: solve the estimator, decompose risk, control high-probability error events, and evaluate bias and variance limits. The proof relies on moment bounds and high-dimensional spectral results.

6.6 Proof of Theorem 3

  • Theorem 3 begins from a closed-form estimator and decomposes its risk into asymptotic bias and variance components.Source: §6.6 · p. 25

Step 2

  • The proof controls approximation events whose probabilities vanish as dimension grows, using operator-norm bounds and the earlier moment lemmas.Source: §6.6 · pp. 25–26, Step 2 · p. 27
  • Several bias steps reuse the argument from Theorem 1, reducing the remaining proof to analogous high-dimensional bounds.Source: §6.6 · p. 26, Step 2 · p. 27

Variance:

  • The variance analysis separates projection-related terms and bounds them with Schatten-norm inequalities, moment assumptions, and concentration arguments.Source: Variance · pp. 21, 27, 28

(iii)

  • The final variance component is evaluated using a high-dimensional regression theorem and empirical spectral distributions, with an identity-covariance specialization.Source: (iii) · p. 29

6.7 Proof of Theorem 4

The proof establishes Theorem 4 by decomposing personalized risk into asymptotic bias and variance, then controlling each term under spectral and high-dimensional assumptions.

6.7 Proof of Theorem 4

  • The proof splits risk into bias and variance and analyzes their asymptotic behavior separately.The variance analysis treats terms (i), (ii), and (iii) independently.Source: §6.7 · p. 29, Variance · p. 33

Step 1

  • The proof shows the probabilities of the key bad events C_t and A_t converge to zero as d tends to infinity.These event bounds provide the high-probability control needed for the asymptotic calculations.Source: §6.7 · p. 30, Step 1 · pp. 31–32
  • Step 1 controls matrix and covariance terms using spectral support, eigenvalue bounds, concentration events, and auxiliary lemmas.The proof uses assumptions that covariance spectra lie in [a, b] and that sample covariance maximum eigenvalues are sufficiently controlled.Source: Step 1 · pp. 31–32
  • The bias calculation applies high-dimensional random-matrix limits, including Theorem 6 of [HMRT19] and Corollary 5 of [HMRT19].The limit is expressed through empirical and weighted empirical spectral distributions, with an identity-covariance specialization.Source: Step 1 · p. 33

Variance

  • The variance calculation bounds all three component terms with high probability before applying Theorem 3 of [HMRT19] and Theorem 1 of [HMRT19].The identity-covariance case receives an explicit specialization for the variance term.Source: Variance · p. 34

6.8 Proof of Corollary 3.1

The proof derives Corollary 3.1 by relating estimator bias and variance to the preceding theorem and then shows that optimally tuned RTFA has lower risk than FedAvg.

6.8 Proof of Corollary 3.1

  • The corollary bounds ρ_i below using the relationship between the estimator’s bias and the client-specific parameter deviation.The proof establishes ρ_i ≥ r_i before evaluating the corresponding bias term.Source: §6.8 · p. 35
  • The relevant bias converges in probability to r_i^2, while an associated variance contribution converges to zero.These conclusions reuse the bias and variance arguments from Theorem 1 with Π_i treated as the identity.Source: §6.8 · p. 35
  • The remaining estimator results follow directly from Theorem 1 and Corollary 5 of [HMRT19].The proof explicitly invokes Theorem 1 for one estimator and Corollary 5 for another.Source: §6.8 · p. 35

6.9 Proof that RTFA has lower risk than FedAvg

  • Optimally tuned RTFA has lower risk than FedAvg by comparing their asymptotic expressions and completing the square.The comparison uses (1 − 1/γ)^2 ≤ (1 + 1/γ)^2 for γ ≥ 1.Source: §6.9 · p. 35

7 Algorithm implementations

This section specifies the exact experimental algorithms, including FTFA, RTFA, and MAML-FL variants, and describes how federated training is followed by client personalization where applicable.

Algorithm implementations

  • The implementation section provides the exact algorithms used in the experiments.It introduces the algorithm descriptions for the tested federated methods and their personalization procedures.Source: §7 · p. 36
  • FTFA and RTFA begin from a FedAvg model and run additional client-specific stochastic gradient steps for personalization.RTFA is presented as a separate algorithm alongside FTFA, with personalization iterations controlled by P.Source: §7 · pp. 36–37
  • MAML-FL uses sampled clients, local stochastic-gradient updates, server aggregation, and a final personalization phase.The implementation description covers both the algorithm setup and the client-side personalization stage.Source: §7 · p. 37

8 Experimental Details

The experiments use federated versions of four datasets, pretrained representations, federated last-layer logistic regression, tuned algorithm configurations, and supplementary plots examining robustness and personalization gains.

8.1 Dataset Details

  • The experiments cover Shakespeare, CIFAR-100, EMNIST, and Stack Overflow with client-level train, validation, and test splits.Shakespeare retains 669 clients after filtering, while Stack Overflow uses a 300-client sample because of scalability constraints.Source: §8.1 · pp. 37–38

8.2.1 Pretrained Model

  • Pretrained non-federated neural networks provide penultimate-layer representations that are used as inputs to the federated experiments.The pretrained models are trained and tuned using train and validation data before representations are stored.Source: §8.2.1 · p. 39, §8.2.2 · p. 39

8.2.2 Federated Last Layer Training

  • The federated stage applies multi-class logistic regression with fixed global and local iteration settings across algorithms.Global iterations R are 400, local iterations K are 20, sampled users D are 20, and batch size B is 32; personalization epochs P are 10 for FTFA, RTFA, and both MAML-FL variants.Source: §8.2.2 · p. 39
  • pFedMe receives less extensive tuning, cannot be run on Stack Overflow, and takes approximately 20x the compute time of FTFA, RTFA, and MAML-FL-FO.These constraints limit direct experimental comparability for pFedMe.Source: §8.2.2 · p. 40

8.3 Additional Results

  • The additional-results plots strengthen the main experimental claims and include best-average-worst intervals and personalization-gain visualizations.The supplementary figures cover CIFAR-100, EMNIST, Shakespeare, and personalization effects for FO-MAML-FL, HF-MAML-FL, and FTFA.Source: §8.3 · p. 41, Figure 7 · p. 41, Figure 8 · p. 41
Loading 2108.07313v3…