Source-linked AI summary
Three Approaches for Personalization with Applications to Federated Learning
Yishay Mansour, Mehryar Mohri, Jae Ro, Ananda Theertha Suresh
TL;DR
The paper addresses how to learn useful models for clients whose data distributions differ, rather than relying only on one global model. It develops three model-agnostic personalization approaches—user clustering, data interpolation, and model interpolation—with learning-theoretic guarantees and efficient algorithms. Empirically, the approaches are demonstrated on synthetic and EMNIST data, while data interpolation has non-trivial communication and data-security costs.
Problem
The paper studies how to train a personalized model for each client when client data are non-i.i.d. and a single global model may not be optimal.
Method
It analyzes user clustering, data interpolation, and model interpolation using learning-theoretic guarantees and efficient, model-agnostic algorithms.
Results
The proposed approaches are empirically useful on synthetic and EMNIST datasets, and clustering improves accuracy by at least 4.3% over FEDAVG and AGNOSTIC models.
Takeaways & Limitations
Personalization offers multiple intermediate strategies between local and global models for learning across clients in federated-learning settings.
Takeaways & Limitations
Data interpolation has non-trivial communication and data-security costs, although the paper describes ways to reduce communication overhead and address security.
Abstract
from arXiv · showhide
The standard objective in machine learning is to train a single model for all users. However, in many learning scenarios, such as cloud computing and federated learning, it is possible to learn a personalized model per user. In this work, we present a systematic learning-theoretic study of personalization. We propose and analyze three approaches: user clustering, data interpolation, and model interpolation. For all three approaches, we provide learning-theoretic guarantees and efficient algorithms for which we also demonstrate the performance empirically. All of our algorithms are model-agnostic and work for any hypothesis class.
1. Introduction
The paper motivates personalized models for settings where client data are highly non-i.i.d. and a single global model may not serve most users well. It studies personalization for clients with infrastructure such as federated learning.
- Virtual keyboard models must predict words for individual users, but a single model trained on all users would make the same prediction for everyone.
- Non-i.i.d. client data make training one global model for all clients potentially suboptimal.
- Personalization trains a model for each client using that client’s dataset together with datasets from other clients.
- Federated learning supports personalization because it provides infrastructure for deploying personalized models to individual clients.
- The paper provides a learning-theoretic framework, generalization guarantees, and computationally efficient personalization algorithms that account for federated-learning computation and communication bottlenecks.
2. Preliminaries
The preliminaries contrast global, local, and personalized models, then establish distributional and statistical tools for analyzing when each approach generalizes well. Local models match client distributions but may lack data, while global models have more data but can suffer distribution mismatch.
- Global models generalize from large datasets but may perform poorly for clients whose distributions differ from the global training distribution.
- Local models match clients’ inference distributions but may generalize poorly because each client has scarce data.
- Personalized models are intermediate between local and global models, combining their intended distribution-matching and generalization properties.
- The framework represents client predictors as hypotheses h:X →∆Y, where each input maps to a probability distribution over output classes.
- A local model’s generalization bound depends on Rademacher complexity and sample size, and can become vacuous when user samples number in the hundreds but hypothesis pseudo-dimension is in the millions.
- Label discrepancy is task-aware: when all hypotheses have equal loss under two distributions, it is zero and models trained on either distribution generalize to the other.
- Global-model performance depends on distribution discrepancy, client sample count, and total sample count, while sample-proportional weighting can disadvantage clients with fewer data.
3. Our contributions
The paper proposes three scalable personalization strategies: clustering users, interpolating data, and interpolating models. It supplies generalization bounds and communication-efficient algorithms, while identifying data interpolation’s communication and security costs.
- Personalization can use an intermediate model between local and global models, with scalable algorithms designed for low communication bottlenecks in federated learning.
- User clustering trains separate models for groups of users.
- Data interpolation trains a model on a combination of local and global data.
- Model interpolation combines separately trained local and global models.
- All three approaches have generalization bounds, efficient algorithms, small communication bottlenecks, and qualitative privacy benefits similar to global-model training.
- Model interpolation has the same communication cost and security as single-model training, whereas clustering costs q times as much communication when q clusters are used.
4. User clustering
User clustering trains models for groups of clients, incorporating the learning task to improve clustering and balancing generalization against distribution matching. The resulting bounds depend on average sample statistics and apply to clustering algorithms generally.
- User clustering: Clustering users and training one model per group provides an intermediate approach between purely local and global models.This creates a trade-off between generalization and distribution mismatch.
- Hypothesis-based clustering: Hypothesis-based clustering incorporates the target learning task to obtain better clusters than divergence-based clustering.The paper motivates this by noting that divergence-based clustering may group facial images by background rather than gender.
- Hypothesis-based clustering: The clustering objective partitions users into q clusters and finds the best hypothesis for each cluster, weighting clients by their importance.In practice, the method replaces true client risks with empirical risks and can use either sample-based or equal client weights.
- Generalization bounds: The generalization bound holds for any clustering algorithm and compares true and empirical cluster-based losses across hypotheses.The analysis explicitly states that the bound is not restricted to the proposed clustering procedure.
- Generalization bounds: Good generalization requires average samples per user to exceed log q and average samples per cluster to exceed the hypothesis-class pseudo-dimension.The bound depends on average statistics rather than the minimum number of samples per client.
- Generalization bounds: For q = 1 the method becomes global, while q = p becomes local; increasing q reduces discrepancy but weakens generalization.Choosing q therefore provides a smooth trade-off between generalization and distribution matching.
5. Data interpolation
Data interpolation combines a client’s limited labeled data with auxiliary global or clustered data, using a tunable mixture to personalize models efficiently. DAPPER provides convergence guarantees under strong convexity while reducing communication and computation, although communication and privacy remain practical concerns.
- Motivation: Data interpolation treats global or clustered data as source data and each client’s labeled data as a target distribution.The client minimizes loss on concatenated source and personal data, connecting personalization to domain adaptation with labeled target data.
- DAPPER: DAPPER trains a central model, gives each client a subsample of size r ⋅ mk from the auxiliary distribution, and optimizes the weighted loss.Its communication is r ⋅ mk and its computation is at most (r + 1) ⋅ mk per client.
- Method: The interpolation objective minimizes λL̂Dk(h) + (1 − λ)L̂C′(h), with λ selected by cross-validation or generalization bounds.C may be the uniform distribution or a distribution obtained through clustering.
- Guarantees: Under strong convexity, DAPPER achieves the desired generalization accuracy with additional data equal to a constant multiple of mk, independent of λ and m.The guarantee is established for strongly convex functions, with smoothness and bounded-diameter assumptions in the theorem setup.
- Limitations: The original mixture algorithm has communication cost O(m), while DAPPER reduces transfer and computation but may remain vulnerable to privacy issues.The paper proposes privacy alternatives in Appendix D.3.
6. Model interpolation
Model interpolation combines a central or cluster model with a client-specific local model and learns interpolation weights. The paper gives pseudo-dimension-based generalization analysis and proposes joint optimization because separately training the two models is not always optimal.
- Motivation: Model interpolation addresses cases where the final inference model does not belong to the single hypothesis class H used by earlier approaches.A central model can come from Hc and a local model from Hl before interpolation.
- Method: For client k, the interpolated model is (1 − λk)hc + λkhl,k, with client-specific weights optimized using empirical local losses.The formal objective uses a central or cluster model hc and local models hl,k for all clients.
- Guarantees: The generalization analysis applies when the loss is L-Lipschitz and the central and local models belong to hypothesis classes Hc and Hℓ.The resulting bound is expressed through the pseudo-dimensions of the central and local classes.
- Guarantees: For good generalization, the total sample size should greatly exceed dc and the average samples per client should greatly exceed dl.The bound depends on average samples rather than the minimum number of samples per client.
- MAPPER: Separately training central and local models and then choosing interpolation coefficients may be suboptimal, so the paper proposes joint optimization under the name MAPPER.MAPPER denotes the model interpolation algorithms developed in this section.
7. Experiments
Experiments on synthetic and federated EMNIST data show that the best personalization approach depends on client sample size, while clustering and interpolation improve over global models.
- Synthetic dataset: HYPCLUSTER performs best when the number of samples per user is very small, whereas MAPPER performs best when it is large.
- Synthetic dataset: Test loss decreases as the number of clusters increases to the synthetic data’s four natural clusters, then remains constant.
- EMNIST dataset: On EMNIST, HYPCLUSTER with two clusters significantly outperforms FEDAVG and AGNOSTIC models.
- EMNIST dataset: At least 4.3% accuracy improvement separates HYPCLUSTER from the FEDAVG and AGNOSTIC baselines.
- EMNIST dataset: DAPPER and MAPPER improve accuracy by another 1% over HYPCLUSTER, but their improvement over FINETUNE is not statistically significant.The EMNIST experiments had standard deviations of about 0.1%.
8. Conclusion
The paper concludes with a systematic theory and empirical study of personalization, covering clustering, data interpolation, and model interpolation with efficient algorithms and guarantees.
- The paper studies three personalization approaches: user clustering, data interpolation, and model interpolation.
- All three approaches receive learning-theoretic guarantees and computationally efficient algorithms.
- The proposed approaches are empirically demonstrated on synthetic and EMNIST datasets.
- A motivating example shows that globally trained models can incur constant loss on both clients despite client-specific classifiers achieving zero error.
C.3. Proof of Theorem 1
The proof establishes a generalization guarantee for every client clustering by combining concentration, a union bound over cluster assignments, and standard complexity bounds.
- The proof considers a mapping f from clients to q clusters and first establishes the theorem for one side.
- McDiarmid’s inequality bounds the effect of changing one sample for a fixed clustering.
- A union bound over the q^p possible client-to-cluster mappings makes the guarantee hold simultaneously for all clusterings.
- Sub-additivity of the maximum decomposes the bound across clusters, whose sample counts and distributions enter the analysis.
- The final result combines these inequalities with standard Rademacher-complexity guarantees and normalization by the total sample count.
D.1. Proof of Theorem 4
The DAPPER proof analyzes stochastic gradient descent on a mixture of client and centralized data, yielding an efficient procedure with reduced data transfer but a privacy caveat.
- DAPPER simulates stochastic optimization on a mixture objective by sampling client data with probability λ and centralized data with probability 1−λ.
- The analysis selects T = r m_k SGD steps after sampling r·m_k centralized-data points for each client.
- The proof invokes standard stochastic-gradient-descent guarantees and strong convexity when the centralized hypothesis is optimal.
- The resulting bound contains the term min(2Gλ/[μ(1−λ)], R).
- Practical considerations: DAPPER reduces data transfer and computation but may be vulnerable to privacy issues in federated-learning applications.Suggested alternatives include sufficient statistics, generative models, and proxy public data.
E.2. MAPPER algorithms
The section shows that independently learned local and global models can be sub-optimal, motivating MAPPER’s joint optimization of local models, interpolation weights, and a global model.
- MAPPER algorithm: The algorithm initializes a global model, repeatedly selects a client, searches interpolation weights from a cover of [0,1], and performs local and global minimization steps.After optimization, it reruns the local procedure for each client to obtain final local models and interpolation weights.
- Motivation: Independent training can incur at least a constant loss more than the optimal jointly learned solution in a constructed example.With one example per domain, even clients estimate local models while odd clients jointly estimate the global model.
- Joint optimization: The optimization is rewritten into a joint problem rather than learning local and global models independently.This reformulation motivates the MAPPER algorithm.
- MAPPER algorithm: MAPPER alternates between finding each selected client’s best local model and interpolation weight and updating the global model.For fixed λ, the objective is convex in both the local and global models, but minimizing over λ removes convexity.
F.1. Synthetic dataset
The experiments define client data using shared, cluster, and individual components, then compare personalization algorithms under a common federated-learning setup and tuned hyperparameters.
- Synthetic dataset: Each client distribution combines a uniform component shared across clients, a cluster component shared within clusters, and an individual component specific to that client.The cluster assignment is represented through Pk%4, while the individual component uses Pk%(d−4).
- Experimental setup: The federated experiments use 20 clients per round for 1000 communication rounds, with common batch size, server learning rate, and server momentum settings.The remaining hyperparameters are swept and selected using the evaluation dataset.
- Experimental setup: EMNIST clients are divided into the CENSUS and HIGH SCHOOL writer sources as two distinct domains.The source distinction was identified because the original client ordering produced substantially different seen and unseen performance.
- Baselines and hyperparameters: HYPCLUSTER uses two clusters because larger cluster counts mapped essentially all clients to two clusters.FINETUNE starts from the best baseline global model, while DAPPER fine-tunes using global and client data.
- Baselines and hyperparameters: MAPPER uses the same architecture for local and global models and initializes the local model from the global parameters at each optimization step.Its listed client configuration uses one epoch and a client step size of 0.03.