PaperlayerView exact revision on arXiv

Source-linked AI summary

Agnostic Federated Learning

Mehryar Mohri, Gary Sivek, Ananda Theertha Suresh

arXiv:1902.00146v1cs.LGstat.ML

TL;DR

Federated learning commonly trains against an unspecified aggregate target and can produce client- or group-biased models. The paper proposes agnostic federated learning, analyzes and optimizes its worst-case mixture-distribution objective, and reports practical benefits across datasets.

  • Problem

    Federated learning minimizes loss under an unspecified target distribution and may yield models biased or unfair toward some clients or protected groups.

  • Method

    Agnostic federated learning optimizes the centralized model for any mixture of client distributions, with theoretical guarantees, a fairness formulation, and a stochastic optimization algorithm.

  • Results

    The authors report significant practical benefits across several datasets, including about 74.5% performance for AFL versus about 71.2% for standard federated learning on any target distribution in Fashion MNIST.

  • Takeaways & Limitations

    The framework provides a fairness-oriented federated objective that limits the maximum loss across protected classes without reducing other classes unless it affects the most-sensitive category.

  • Takeaways & Limitations

    When the number of domains is large, the models may generalize poorly; clustering clients into sufficiently sampled, homogeneous domains is suggested instead.

Abstract

from arXiv · show

A key learning scenario in large-scale applications is that of federated learning, where a centralized model is trained based on data originating from a large number of clients. We argue that, with the existing training and inference, federated models can be biased towards different clients. Instead, we propose a new framework of agnostic federated learning, where the centralized model is optimized for any target distribution formed by a mixture of the client distributions. We further show that this framework naturally yields a notion of fairness. We present data-dependent Rademacher complexity guarantees for learning with this objective, which guide the definition of an algorithm for agnostic federated learning. We also give a fast stochastic optimization algorithm for solving the corresponding optimization problem, for which we prove convergence bounds, assuming a convex loss function and hypothesis set. We further empirically demonstrate the benefits of our approach in several datasets. Beyond federated learning, our framework and algorithm can be of interest to other learning scenarios such as cloud computing, domain adaptation, drifting, and other contexts where the training and test distributions do not coincide.

1. Motivation

Federated learning commonly trains a centralized model from client data, but the usual objective may not match the deployment distribution or address fairness. Agnostic federated learning instead optimizes over mixtures of client distributions and supports theoretical, algorithmic, and empirical analysis.

  • Learning scenario: Federated learning trains a centralized model from data distributed across many clients with potentially unreliable or slow connections.Clients may include mobile phones, other mobile devices, or sensors.
  • Mismatch in objectives: Standard federated learning implicitly minimizes loss under a uniform client-derived distribution, although the deployment target may differ from it.Client participation and sample sizes can vary with connectivity, charging, and other factors.
  • Proposed framework: Agnostic federated learning optimizes the centralized model for any target distribution formed by a mixture of client distributions.The framework replaces optimization for one specific distribution with an agnostic, more risk-averse objective.
  • Theoretical benefit: For some target mixtures, uniform-distribution minimization has cross-entropy loss worse by a constant additive term than AFL, even with infinite samples.This establishes a theoretical separation between the standard and agnostic objectives.
  • Fairness and broader scope: AFL naturally yields good-intent fairness by treating protected categories similarly, while extending to cloud learning, domain adaptation, and drifting settings.The paper also develops data-dependent Rademacher guarantees, a regularized algorithm, and a stochastic optimization method with convergence analysis.

2. Related work

Related work connects federated learning to distributed optimization, fairness, domain adaptation, and multiple-source adaptation. The paper distinguishes AFL by using labeled data from each domain and optimizing a predictor in a global hypothesis set.

  • Domain adaptation: AFL relates to transfer learning and domain adaptation, where source and target distributions differ, including single-source and multiple-source settings.The related literature includes unsupervised and lightly supervised adaptation methods.
  • Multiple-source adaptation: Multiple-source adaptation seeks predictors with guarantees for mixtures of source domains but assumes access only to domain predictors, not labeled training data.Those methods define each domain through its distribution and combine source-domain predictors.
  • Distinction from prior work: AFL differs by assuming labeled data from each domain and selecting the best predictor from a global hypothesis set that may include distribution-weighted combinations.This contrasts with prior methods restricted to a specific hypothesis set of combinations of domain predictors.
  • Local minimax comparison: AFL also differs from local minimax robustness work because it uses samples from multiple unknown distributions rather than one source distribution.The comparison concerns both the sampling setting and the family of distributions optimized over.

3. Learning scenario

The paper formulates agnostic federated learning around unknown mixtures of client distributions rather than the standard uniform distribution. It connects this objective to worst-case performance across protected categories and good-intent fairness.

  • 3.2. Comparison with federated learning: Standard federated learning uses the uniform distribution over the union of client samples, but this choice can be disadvantageous when the target distribution is unspecified.The paper states that the uniform predictor can have higher agnostic loss than the optimal AFL predictor by a constant even with infinitely many samples.
  • 3.1. Agnostic federated learning: AFL models the target distribution as an unknown mixture of client distributions and seeks a hypothesis favorable for every mixture in a specified set.The accessible empirical objective uses mixtures of the clients’ empirical distributions.
  • 3.1. Agnostic federated learning: The domains used in AFL need not coincide with individual clients; clustering may be preferable when the client population is very large.When p is small or Λ is restrictive, performance may be poor on certain domains, while regularization is proposed to mitigate large-p effects.
  • 3.2. Comparison with federated learning: For cross-entropy loss, the paper constructs distributions and hypothesis classes showing that uniform optimization can be strictly worse than agnostic optimization.The construction uses two classes and client distributions concentrated on a single input.
  • 3.3. Good-intent fairness in learning: In good-intent fairness, each protected category defines a conditional client distribution, and AFL minimizes the maximum loss over those categories.With Λ consisting of Dirac measures, the objective avoids overfitting to one protected category at the cost of others.
  • 3.3. Good-intent fairness in learning: The framework treats protected categories similarly and can highlight bias in the training procedure without degrading other categories unless the most-sensitive category’s loss changes.The paper distinguishes training-data bias from bias introduced by the training procedure.

4. Learning bounds

The paper derives data-dependent generalization guarantees for agnostic federated learning using weighted Rademacher complexity, mixture covers, and a skewness parameter. These bounds characterize how domain sample sizes and the allowed mixture set affect generalization.

  • 4.1. Generalization guarantees: The learning guarantees are expressed through weighted Rademacher complexity, the skewness parameter s(Λ∥m), and an ϵ-cover of the mixture set Λ.The bounds apply to losses generated by a hypothesis family across multiple domain samples.
  • 4.1. Generalization guarantees: Theorem 2 gives a high-probability agnostic-loss bound for bounded losses over samples drawn independently from the domain distributions.The result is stated for any δ > 0 and sample-size vector m.
  • 4.1. Generalization guarantees: The proof extends standard Rademacher-complexity arguments using concentration, an ϵ-cover of Λ, and a maximization over mixture weights.McDiarmid’s inequality controls sample changes before the argument extends from the finite cover to all λ in Λ.
  • 4.2. Complexity bounds: The skewness parameter also appears in a lower bound on the generalization bound, according to a result the paper says will be included in its final version.This is presented as an additional characterization of the parameter’s role.
  • 4.2. Complexity bounds: For losses taking values in {−1,+1}, weighted Rademacher complexity is bounded using the VC-dimension of the loss family and the skewness of Λ.Lemma 3 supplies the corresponding complexity bound.
  • 4.2. Complexity bounds: When Λ contains only the average distribution with λ_k = m_k/m, the skewness equals one and the guarantees coincide with standard supervised-learning bounds.The paper notes that large p with Λ = ∆p can produce large skewness and weaker guarantees when per-domain sample sizes are small.

5. Algorithm

The paper defines an AFL algorithm by combining empirical agnostic loss with complexity and skewness regularization, then solves the resulting minmax problem using projected stochastic updates. Under convexity and stated boundedness and variance assumptions, STOCHASTIC-AFL has convergence and time-complexity guarantees, while stochastic-gradient choices trade variance against computation.

  • AFL objective: The AFL algorithm minimizes empirical agnostic loss together with hypothesis-complexity and mixture-weight skewness regularization.The regularized objective uses a norm on the hypothesis and a chi-squared constraint or penalty on mixture weights.
  • Optimization formulation: The optimization is a convex minmax problem when the loss is convex and the hypothesis set is convex.Nature maximizes over mixture weights while the learner minimizes over predictor parameters.
  • Optimization algorithm: STOCHASTIC-AFL computes unbiased stochastic gradients, projects predictor and mixture-weight updates onto their feasible sets, and returns averaged predictor weights.The algorithm repeats these updates for T steps; regularization contributes an additional derivative to the mixture-weight update when included.
  • Stochastic gradients: PERDOMAIN and WEIGHTED stochastic gradients are both analyzed for unbiasedness, variance, and time complexity.The paper also gives an optimistic stochastic variant, but its convergence analysis is not covered.
  • Guarantees: The convergence theorem assumes compact parameter sets, bounded gradients, bounded stochastic-gradient variance, and specified costs for gradient computation and projection.The resulting STOCHASTIC-AFL time complexity is O((Uλ + Uw + Up + d + k)T).
  • Stochastic gradients: When k is small, PERDOMAIN is preferable because its roughly k-times higher time complexity can outweigh its apparent variance advantage.This comparison assumes the stated setting RΛ ≤1 and that the dominant cost is U.

6. Experiments

Experiments compare agnostic federated learning with uniform and domain-specific training across three datasets, showing benefits for worst-domain and overall performance. The approach also performs well with non-convex models and stochastic-gradient variants despite convex-theory assumptions.

  • Experimental setup: Experiments on three datasets compare the domain-agnostic model with uniform-distribution and individual-domain models.The experiments use PERDOMAIN stochastic gradients and set Λ = ∆p.
  • Optimization settings: The experiments show good performance with non-convex functions and variants such as momentum and Adagrad, although convergence guarantees assume convex loss and hypothesis sets.The empirical study therefore extends beyond the stated optimization-theory conditions.
  • Language modeling: For the language-model dataset, the domain-agnostic model minimizing L_DΛ has the best perplexity on the worst domain.Table 3 reports test perplexity across domains as a function of training loss.
  • Adult: On Adult, AFL reaches at least about 71.5% on any target distribution Dλ, compared with about 69.6% for the standard federated model on DΛ.The agnostic model is less biased and performs better on DΛ, although its uniform average across domains is slightly lower.
  • Fashion MNIST: On Fashion MNIST, AFL improves shirt-specific and overall accuracy while improving the loss of the worst domain.The shirt class is the hardest to distinguish, and its improvement exceeds the degradation on the other classes.

7. Extensions

The extensions discuss how to define domains, incorporate prior knowledge over target mixtures, and combine agnostic models with personalization. They also identify domain selection as a key factor affecting generalization.

  • Domain definitions: When there are many clients and Λ = ∆p, using each client as a domain may yield poor generalization.The paper suggests clustering clients by distributional similarity so each domain is sufficiently sampled and relatively homogeneous.
  • Domain definitions: Domains can be chosen by expertise, native language, or application, and agnostic training is intended to keep user experience favorable across applications.The keyboard example uses chat, social, and web-input applications as possible domains.
  • Prior knowledge: A prior distribution pΛ(λ) can assign larger weights to more likely domains instead of treating all domains equally.The modified objective retains suitable generalization guarantees; with a log-concave prior, the objective remains convex in h and concave in λ.
  • Scope: Agnostic federated learning is framed as learning a model that performs well on all domains.This summarizes the stated scope of the framework.
  • Personalization: The resulting centralized model can be combined with a client-side personalized model using an appropriate mixture weight αk.This extension is proposed for better client-specific models.

8. Conclusion

The paper introduces agnostic federated learning with theoretical analysis, an analysis-guided algorithm, and a stochastic optimization method for large-scale problems. Experiments suggest that the solution can provide significant practical benefits.

  • The paper introduces a new agnostic federated learning framework and presents a detailed theoretical analysis.
  • It provides an algorithm guided by the analysis and a stochastic optimization solution designed for large-scale problems.
  • Experimental results suggest that the proposed solution can lead to significant benefits in practice.

Appendix A. Alternative learning guarantees

The appendix compares alternative learning guarantees with prior multiple-source adaptation bounds. The paper states that its guarantee can be stronger up to logarithmic factors, while the relative strength depends on sample and mixture parameters.

  • AFL bounds apply to any subset Λ of the simplex, unlike prior bounds stated for a single mixture weight λ.
  • In a two-domain example, prior bounds are proportional to a constant and become uninformative, while the AFL guarantee is proportional to 1/√m.
  • For Λ ⊂ ∆p, the paper gives an alternative learning guarantee based on domain-specific Rademacher complexity.
  • Theorem 10 holds with probability at least 1 − δ over sampled domains and simultaneously for all h ∈ H and λ ∈ Λ.
  • The proof uses known Rademacher complexity bounds and a union bound, and is omitted.
  • Up to logarithmic factors in the second term, Theorem 2 is stronger than Theorem 10, but which bound is stronger generally depends on m and λ.The appendix notes that Λε may be large and exponential in p.
Loading 1902.00146v1…