Private and Personalized Frequency Estimation in a Federated Setting

Amrith Setlur, Vitaly Feldman, Kunal Talwar

Introduction

Motivated by the challenge of next-word prediction on mobile keyboards, this paper introduces a novel federated learning algorithm for private and personalized frequency estimation. By grouping users into latent clusters based on their vocabularies and utilizing Good-Turing estimators, the proposed method significantly outperforms standard global models (like FedAvg) while maintaining strict user-level differential privacy.

The Challenge: Heterogeneity and Privacy

Imagine your smartphone trying to predict the next word you will type. To do this effectively, the device needs to understand the frequency of words in your specific vocabulary. However, this presents two massive challenges:

  1. Statistical Heterogeneity: Everyone types differently. A single, global language model cannot capture the niche slang, names, or jargon an individual uses. Yet, a single phone rarely generates enough text data to train a highly accurate model entirely from scratch.
  2. Privacy: Typing data is incredibly sensitive. Sending raw text or exact word counts to a central server poses a massive privacy risk.

Existing Personalized Federated Learning (PFL) methods typically try to solve this by training a single global model across all users, which is then fine-tuned locally on the device. However, this ignores the reality that user populations usually consist of distinct subpopulations (e.g., Spanish speakers, programmers, teenagers). Furthermore, existing clustering-based federated methods rely heavily on gradient descent, which can be noisy, slow to converge, and highly "expensive" in terms of privacy budget when dealing with simple frequency histograms.

Proposed Methods

The authors propose an iterative, non-gradient-based clustering algorithm tailored specifically for distribution estimation using KL divergence.

Core clustering algorithms including UserOutput, NonPrivateCenter, and HistogramCluster.

The approach relies on several key technical innovations:

  • Good-Turing Estimators over Empirical Averages: Instead of users calculating simple empirical averages of their words (which perform poorly for small datasets with large vocabularies), users compute local Good-Turing estimates. This classic statistical technique better accounts for unseen words and prevents the model's error from scaling poorly with the vocabulary size.
  • Federated Lloyd's Algorithm: The server maintains $K$ cluster centers. Users privately assign themselves to the cluster that best matches their local Good-Turing estimate. The cluster centers are then updated by averaging the estimates of the users within them.
  • Joint Differential Privacy (JDP): The algorithm protects user data using adaptive clipping, secure aggregation, and Gaussian/Laplace noise addition. JDP ensures that the model sent to a specific user is differentially private with respect to the data of all other users.
  • Private Data-Dependent Initialization: Clustering algorithms are notoriously sensitive to their starting points. The authors introduce a private initialization scheme using the exponential mechanism to pick high-quality starting centers, drastically reducing the number of communication rounds needed.
  • Handling Size-Heterogeneity: Real-world users have vastly different amounts of data. The authors use a two-stage approach: first clustering "data-rich" users to establish stable centers, and then assigning "data-poor" users to these centers to avoid blowing up the sensitivity of the privacy mechanisms.

Key Insights

  • Latent clusters are real and useful: Real-world user distributions aren't just random noise around a single global mean; they form concentrated subpopulations. Identifying these clusters and personalizing from a cluster center yields much better results than personalizing from a single global model.
  • Good-Turing is a superpower in Federated Learning: When local datasets are small and the vocabulary is large (high dimensions), empirical counts fail miserably. Averaging local Good-Turing estimates drastically reduces the sub-optimality gap.
  • Initialization saves privacy budget: In private iterative algorithms, every round of communication burns privacy budget. By using their smart, private initialization scheme, the authors reduced the required clustering iterations from 200 down to 20. This allows them to add far less noise per step, vastly improving the utility-privacy tradeoff.
  • Gradient-free is better for histograms: Gradient-based clustering baselines (like IFCA) incur high privacy overheads per iteration and suffer from poor convergence. Directly averaging distributions is much more efficient for this specific problem.

Empirical Results

The authors evaluated their methods on three standard federated learning text datasets adapted for frequency estimation: Reddit (10k token vocabulary), StackOverflow (32k token vocabulary), and Amazon Reviews (32k token vocabulary).

Test Negative Log Likelihood comparison across Reddit, StackOverflow, and Amazon Reviews datasets.
  • Non-Private Setting: The proposed method reduced the test Negative Log-Likelihood (NLL) sub-optimality gap by 25% to 45% compared to baselines like FedAvg, MAML, and IFCA.
  • Private Setting: The gains are even more pronounced under strict privacy constraints, showing up to a 50% reduction in the NLL gap compared to private baselines.
  • Size-Heterogeneous Setting: When users have varying amounts of data, the proposed two-stage method improved over the clustering baseline IFCA by over 30%.

Limitations and Future Work

The authors acknowledge that their private initialization scheme is difficult to execute in a purely distributed federated setting without a small, centrally collected proxy dataset to seed the initial clusters. Furthermore, this paper focuses strictly on estimating marginal token distributions (overall word frequencies).

True language modeling requires conditional next-token distributions (e.g., predicting the next word given the previous three). Extending this clustering and Good-Turing-based approach to conditional next-token distributions represents a highly promising direction for building better, more private federated language models in the future.

Summary updated

Abstract

Motivated by the problem of next word prediction on user devices we introduce and study the problem of personalized frequency histogram estimation in a federated setting. In this problem, over some domain, each user observes a number of samples from a distribution which is specific to that user. The goal is to compute for all users a personalized estimate of the user's distribution with error measured in KL divergence. We focus on addressing two central challenges: statistical heterogeneity and protection of user privacy. Our approach to the problem relies on discovering and exploiting similar subpopulations of users which are often present and latent in real-world data, while minimizing user privacy leakage at the same time. We first present a non-private clustering-based algorithm for the problem, and give a provably joint differentially private version of it with a private data-dependent initialization scheme. Next, we propose a simple data model which is based on a mixture of Dirichlet distributions, to formally motivate our non-private algorithm and demonstrate some properties of its components. Finally, we provide an extensive empirical evaluation of our private and non-private algorithms under varying levels of statistical and size heterogeneity on the Reddit, StackOverflow, and Amazon Reviews datasets. Our results demonstrate significant improvements over standard and clustering-based baselines, and in particular, they show that it is possible to improve over direct personalization of a single global model.
BibTeX
@inproceedings{setlur2024private,
  author = {Amrith Setlur and Vitaly Feldman and Kunal Talwar},
  title = {{Private and Personalized Frequency Estimation in a Federated Setting}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=0nzKznCjFG},
}
Figure