Private and Personalized Frequency Estimation in a Federated Setting

Thank you for the feedback. To address concerns, we add new experiments with different values of $\varepsilon$, number of local points $m$, and plots showing the sparsity of the estimated cluster centers in practice. We also point to our ablations on $K$ in our paper, and clarify concerns with Thm. 5.1, 5.2. We thank you for the relevant citations, and we will use the 1 extra page in the final version to incorporate the new experiments, clarifications, and citations. Please let us know if your concerns are addressed, and if so, we would be grateful if you might raise your score.

Different values of $\varepsilon$ and local data points $m$

We show performance evaluations under varying values of $m$, and fixed privacy budget of $\varepsilon=15$ (Fig 3 in PDF), and varying $\varepsilon$ for the values of $m$ in our paper (Fig 2 in PDF). We note that while the performance of each method drops with reducing $\epsilon$ and $m$, our algorithm has better privacy-utility tradeoffs and is more sample efficient. We also note that these privacy parameters are for a relatively small dataset (10k to 50k users). If the population size was, say, 10x larger, the privacy parameters would be 10x smaller for the same kind of results. In practical FL settings, we would often expect the population sizes to be much larger and thus the epsilons to be proportionately smaller.

Choice of number of clusters $K$

In Fig. 3a (Sec 6) and Fig. 5 (App B) we show how the choice of $K$ (number of clusters) affects the final performance of our algorithm. As expected, the performance improves as $K$ roughly matches the natural heterogeneity/clusters present in the data distribution. In practice, we can use hold out to validate $K$. See our global response for more discussion on this.

Privacy accounting via RDP

We do not use composition results for approximate DP. All our composition results rely on zero concentrated DP (zCDP) (Bun and Steinke [16]) for privacy accounting of user-level DP. We then convert the zCDP guarantees to approximate DP in Thm. 5.2. Note that zCDP is a stricter notion of privacy than RDP since it requires Renyi divergence of multiple orders to be simultaneously bounded. Further, it enjoys the same benefits as RDP for composition, since zCDP’s sequential composition is also asymptotically tight for repeated applications of the Gaussian mechanism [16].

[New Experiment] Sparsity of $P_c[v]$ in practice

In practice, the estimated cluster centers are sparse, as we see on Reddit and StackOverflow, where about 10% of the tokens carry 90% of the probability mass (Fig 4 in 1-page PDF). The assumption we make in Thm. 5.1 on P_c[v] being lower bounded by a constant is needed solely for the theoretical convergence guarantees for clustering. This is needed in theory because KL divergence does not obey triangle inequality, but $l_2^2$ distance does, and for KL between estimated to be roughly tracked by $l_2^2$, we need $P_c[v] = \Omega(1)$.

Dependence on $d$ in the KL separation condition in Thm. 5.1

There is a typo in the condition on the minimum cluster separation $\Delta$. The correct condition is $\Delta = \Omega(k^2 + \frac{k^3 d}{n})$, as derived in the proof of Thm. 5.1 in App. D.1 (below L831). We apologize for this typo and will correct it in the final version. Note that the number of clients $n$ appears in the separation condition on $\Delta$, and the convergence is determined by the condition number. Thus, the condition on KL divergence only scales as $poly(k)$ when $n=\Theta(d)$. For the datasets we use, the number of users is sufficiently large ($d/n < 2$ for all).

$\log(1/\delta)$ term in Thm. 5.2

Yes, for the privacy guarantee to be meaningful $\delta$ needs to be $o(1/n)$. But, note that the guarantee in Thm. 5.2 is $\sqrt{\log(1/\delta)}$, which for the datasets of our size (around $10^5$), translates to $\approx \sqrt{5}$.

To elaborate more on the term, the result in Thm. 5.2 is obtained by first composing the privacy mechanisms in each clustering iteration with zero-concentrated DP (zCDP) and then converting the zCDP guarantees into approx. DP using Lemma 3.6 in Bun & Steinke [16]. The $\log (1/\delta)$ term is an artifact of this conversion. On the other hand, if we were to instead compute approx. DP guarantees (instead of zCDP) at each clustering iteration and then use the advanced composition theorem to compose them, we would still end with a $\sqrt{\log(1/\delta)}$ term from the composition. So, this term is unavoidable either way.

L256 Without any assumptions on the relationship … the best one can do is locally estimate

Consider the following worst-case setting where there is no mutual information between the training datapoints sampled by any pair of users. Let each user’s true token distribution $Q_u$ be supported over subsets of tokens that are disjoint for any pair of users. Further, for any user $u$ and token $v$ with $Q_u[v]>0$, the value of $Q_u[v]>0$ is independent of the token distribution of other users. In such a case, no estimator can improve the average estimation error through collaboration/sharing of data. The optimal estimator is purely local. We will add this example to the paper.

Missing citations

Thanks for pointing out these references, we will cite & discuss them. We believe our contributions go beyond these: for e.g., while [2, 3, 4] look at private histogram estimation, they concern with algorithms that estimate a single global quantity (e.g., mean histogram) whereas ours deals with the nuances of privatizing personalization algorithms that estimate a separate distribution for each user, and learn multiple global centers. Further, [1, 4] conduct their analysis in the $l_2$ metric, whereas we look into the more appropriate KL distance for distribution estimation. KL is harder to analyze and develop algorithms for, given that it does not even obey the triangle inequality.

Thank you for the feedback and a positive assessment of our work. To address your concerns, we present new ablations of our algorithms under different values of per-client training data points $m$, local only training baselines, highlight existing ablations in our paper on the number of clusters, and address the point of analyzing a simpler setting. We will add the new results and discussion on the above points in the extra page we get for the final version. Please let us know if your concerns are addressed, and if so, we would be grateful if you might raise your score.

[New experiment] Lack of comparison to local only training and other personalized estimation methods.

In Fig 5 (1 page PDF), we find that the local only training performance where the clients never collaborate is worse than our approach (for a privacy budget of $\epsilon=15$), even as we increase the number of local data points $m$. Further, comparing this result to Fig 2 (1 page PDF), we find this trend to hold even under a very low privacy budget of $\varepsilon=2$.

The main results are rather in simpler settings, the analysis mostly builds on top of previous work.

While our analysis technique adapts results on clustering and Good-Turing estimation to our setting, its main goal is to serve as a guide that formally validates our algorithmic choices, for e.g. the local finetuning algorithm (in Eq. 2), or using the average of local Good-Turing estimates for estimating the cluster center, as opposed to the typical average of empirical estimates that is used in the K-means algorithm (see our comparison in Thm. 4.3). In the FL and privacy literature, it is also common for algorithms to be analyzed under such models of data heterogeneity (e.g., Cummings et al. [22], Cheng et al. [20]) that mimic real world distributions.

[New experiment] From the current experiments, performance dependence on variables such as number of clusters, clients, data samples per clients, heterogeneity etc. is not clear.

Number of clusters: In Fig. 3a (Sec 6) and Fig. 5 (App B) we show how the choice of $K$ (number of clusters) affects the final performance of our algorithm. As expected, the performance improves as $K$ roughly matches the natural heterogeneity/clusters present in the data distribution. In practice, we can cross-validate to find $K$ and use $K=10$ (close to the optimal choice for all datasets), for all our runs.

Number of clients and privacy budget:In the attached PDF, we show performance evaluations under varying values of $m$ and fixed privacy budget of $\epsilon=15$ (Fig 3), and varying $\epsilon$ for the values of $m$ in our paper (Fig 2). We note that while the performance of each method drops with reducing $\epsilon$ and $m$, our algorithm has better privacy-utility tradeoffs and is more sample efficient

Heterogeneity: Given that the natural datasets we consider already have varying levels of heterogeneity (see discussion in global response on a different choice of $K$ being optimal on each dataset) and allow us to investigate the key phenomenons, we see no compelling reason to empirically study synthetic data. We are also not aware of a sufficiently faithful model of data for our problem (and even for our own data model there are many parameters, for which it is unclear how to choose synthetic values). At the same time we welcome and will certainly consider specific suggestions about synthetic data experiments that would make our work more informative.

Thank you for the feedback! To address concerns we provide an algorithm’s box for the end-to-end algorithm, clarify that assumptions in Sec 4 are only for theoretical motivation, and results in Sec 6 are on real datasets where they needn't hold. We clarify our DP definition is not relaxed at all, in fact it is more stringent than RDP and the final guarantees in Thm. 5.2 are for the approx DP definition. We will use the 1 extra page in the final to incorporate them. Please let us know if your concerns are addressed, and if so, we would be grateful if you might raise your score.

Final alg in Sec 5

In the 1 page PDF (Fig 1), we show an algorithm box for the end-to-end algorithm that uses Alg 5 for private initialization of cluster centers, and Alg 3 for clustering, where the re-centering step uses Alg 4. Each user finetunes their corresponding cluster center using Eq. 2.

Assumptions in stylized model and concentration of user histograms

• In Sec 4, to guide algorithm design we introduce a model where the user distributions are distributed as a mixture of Dirichlets. This model has two latent variables: cluster memberships and cluster centers. For simplicity, we analyze estimators under increasing levels of knowledge in this model: cluster center known -> cluster center unknown but cluster membership known -> both cluster center and membership unknown.
• The simpler analysis in a clean model leads us to three key findings (end of Sec 4) using which we propose the clustering algorithm (Alg. 3), with the recentering step using Good-Turing estimates (Eq. 4), and finetuning given by Eq. 2.
• In Sec 6, we evaluate our proposed algorithm in the most general setting, where cluster centers/memberships are unknown. Here, we also do not assume anything about the distribution of $Q_u$’s.
• Regarding the well-concentrated assumption: We only need that w.h.p., for all users $u$ in cluster $c$, and any token $v$, $|P_c[v] - Q_u[v]| = O(1)$. This is naturally satisfied by our Dirichlet assumption since the $\alpha$ parameter of Dirichlet allows us to analyze our setting with varying degrees of cluster-level concentration where $|P_c[v] - Q_u[v]| = O(1/\sqrt{\alpha})$.

Novelty

The novelty of our Algorithm lies beyond the proposed K-means style clustering method. Following is a set of novel contributions we make, where the final four claims are verified empirically in Sec 6 and defined, analyzed formally in Sec 5.:

• Introduce the personalized and private frequency estimation problem in KL divergence.
• Contrary to popular beliefs (Cheng et al. [20], Wu et al. [76]) in the FL community, we show that there exists practical FL problems where finetuning a single global model (FedAvg+FT) is not sufficient for personalization.
• Specifically to improve clustering error in terms of KL divergence (as opposed to squared loss in k-means) we motivate and propose a Good-Turing based center estimator (Sec 4).
• Propose a private version of the clustering algorithm with approximate differential privacy guarantees (Thm. 5.2).
• Propose a novel data-dependent and yet private initialization for clustering (Alg. 5), which is crucial to improve clustering performance (Fig. 3b). Prior works on private-clustering (e.g., Chang et al.: Locally private k-means) do not analyze expectation maximization (EM) algorithms given their dependence on initialization which is harder to privatize (most initializers for EM directly output a set of points from the dataset (Arthur et al. [5])).
• Propose a practical 2-stage algorithm for the size-heterogeneous setting (Section 5). Naive algorithms in this setting typically hurt the privacy-utility trade off since hiding the participation of data-rich users now becomes very hard when other users have less data. We show that our proposed algorithm is able to improve estimation error from including both data-poor and data-rich users in the collaboration, without hurting the privacy utility trade off (Fig 4).

Our final guarantees are in terms of approx DP and Def 3.2 is stricter than RDP

Our final guarantees in Thm 5.2 are in terms of user-level $(\varepsilon, \delta)$-DP which is equivalent to JDP in our setting. We only use the $\rho$-cJDP (stricter than RDP) in Def 3.2 for easier and tighter composition (than approx. DP), and provide final guarantees in terms of user-level approx. DP.

In billboard model, JDP=user-level DP: Note that our setting is akin to the billboard model (Hsu et al. [41]) where any $(\varepsilon, \delta)$ user-level DP (Dwork [25]) algorithm is also $(\varepsilon, \delta)$-JDP. Similarly, if the algorithm satisfies user-level $\rho$-zCDP (Bun et al. [16]) then, it is also ρ-zCJDP (Def 3.2).

Final guarantees are for user-level DP: We use zCDP for composition at the user-level, and then use Lemma 3.6 from [16] to convert zCDP to approx. DP in Thm. 5.2.

Why use zCDP?: Yes, zDP bounds the $\alpha$ Renyi divergence between the mechanism outputs on neighboring datasets by $\rho\alpha$. Thus, zCDP is a stricter notion than Renyi DP (RDP) since zCDP requires Renyi divergence of multiple orders to be simultaneously bounded. Further, zCDP enjoys the same benefits as RDP for composition, since zCDP’s sequential composition is also asymptotically tight for repeated applications of the Gaussian mechanism [16].

[New Experiment] Evaluating performance at different privacy budgets

In Fig 2 (1 page PDF) we evaluate our algorithm and other baselines under different privacy budgets. Each algorithm needs to satisfy ($\varepsilon, \delta$)-JDP (which is ($\varepsilon, \delta$) user-level DP). On the x-axis we vary $\varepsilon$ and fix the same $\delta$ reported in the paper. We find that our approach continues to outperform baselines. While the clustering baseline IFCA and MAML suffer from severe performance degradation under low privacy budgets, our approach observes a much better privacy-utility trade off.

Thank you for the feedback and a positive assessment of our work. To address concerns, we refer to plots in the paper that ablate $K$, clarify guarantees in Thm. 5.2 are in terms of the typical $(\varepsilon, \delta)$ approx. DP, and discuss the choice of the stricter user-level DP definition. We also explain the motivation to study next-word prediction, and the choice of the stylized model: mixture of Dirichlets. Thank you for pointing us to typos, we will correct them, add discussion on the above points and a conclusion section in the extra page we get for the final. Please let us know if your concerns are addressed, and if so, we would be grateful if you might raise your score.

Choosing the number of clusters K

In Fig 3a, 5 in our paper, we plot the test NLL when varying the number of clusters $K$ parameter for our clustering Alg 3. Please see the global response for more discussion on this.

Converting cJDP to user-level DP

Our final guarantees in Thm 5.2 are in terms of user-level $(\varepsilon, \delta)$-DP which is equivalent to JDP in our setting. We only use the $\rho$-cJDP (stricter than RDP) in Def 3.2 for easier and tighter composition (than approx. DP), and convert them to user-level approx. DP finally.

Our setting is akin to the billboard model (Hsu et al. [41]) where any $(\varepsilon, \delta)$ user-level DP (Dwork [25]) algorithm is also $(\varepsilon, \delta)$-JDP. Similarly, if the algorithm satisfies user-level $\rho$-zCDP (Bun and Steinke [16]) then, it is also ρ-zCJDP (Def 3.2). Thus, we first use zero-concentrated DP (zCDP) for privacy accounting and composition, and then use Lemma 3.6 from [16] to convert the zCDP guarantees to approx. DP in Thm. 5.2.

User vs. record level DP

We defined our problem in Sec. 3 with the goal of achieving personalized predictions for each user’s frequency counts, while satisfying user-level privacy. As you correctly point out, this is indeed stricter than item-level privacy, but it is also a common choice for privacy guarantees in cross-user federated learning (e.g., Cummings et al. [22], Levy et al. [52], Wang et al. [71]). In cross-user FL, e.g. learning to predict the next word on users’ mobile devices, it is natural to protect the participation of every user; as a user may type many different words that are correlated, hiding a single word may not be sufficient privacy protection. Indeed if we had the weaker item level DP protection with $\varepsilon = 2$ (say), the overall user-level privacy loss for a user that contributed $m=200$ words would theoretically be $\varepsilon \cdot m = 400$. Even if 10 of the words are correlated with sensitive information (e.g. related to their medical diagnosis), the $\varepsilon$ parameter increases by that factor. Our user-level guarantee ensures that even if the user were to change all 400 words they contributed, the models will not be significantly different.

Using the mixture of Dirichlets model for our analysis in Sec 4

In Sec. 4, we introduce the mixture of Dirichlets model with the goal of guiding algorithm design when the underlying population is heterogeneous, yet is structured. While each user has a different token distribution it is likely that there exists clusters of ``similar’’ users. This model motivates a setup where adapting a single global model for each user would be less effective than identifying clusters, learning a single model for the cluster and then adapting the cluster-level model for the user. We also observe this empirically in our experiments in Sec 6, where FedAvg+FT performs worse than our approach.

Note that the specific choice of Dirichlet for analysis is only so that we can easily derive the optimal Bayes estimator (Thm 4.2), which gives us our finetuning algorithm in Eq 2. For all other theoretical results in Sec. 4, 5 we only need each user’s true distribution to be concentrated along the cluster center, i.e., w.h.p., for all users $u$ in cluster $c$, and any token $v$, $|P_c[v] - Q_u[v]| = O(1)$. The $\alpha$ parameter of Dirichlet further allows us to analyze our setting with varying degrees of cluster-level concentration, since under the Dirichlet assumption $|P_c[v] - Q_u[v]| = O(1/\sqrt{\alpha})$.

Why focus only on the next-word prediction problem in the FL setting? Extending to other datasets and losses.

Large language models are next-token prediction models that can be used to solve tasks in natural language like math reasoning, coding etc. In FL, the performance of these next-token prediction models can be improved fairly across users when they are personalized (Hard et al. [38], Salemi et al. [66]). At the same time, since each user has few data points for purely local learning, global collaboration is needed to bias the local learning algorithm. Thus, we study frequency estimation (estimating the marginal distribution) as a first step towards private and personalized language models. We highlight how measuring the error in KL divergence and reducing privacy-utility trade offs requires algorithmic innovations (e.g., clustering with Good-Turing, data-dependent private initialization) that are specific to our problem and much required.

We provide an extended analysis on three real-world datasets with varying levels of statistical heterogeneity, each of which are a popular choice for analyzing next-token predictors in FL (Wu et al. [76]). Please let us know if there is a specific dataset that is characteristically different from these, and we would be happy to include experiments on it.

As we mention in Sec 1, we focus on error measured in KL as is common in language modeling (Hoffmann et al. [40]), and is equivalent to minimizing the negative log-likelihood of the sample. Distribution estimation in KL distance is also studied more generally (Drukh et al. [24], Acharya et al. [2]). We believe that extending KL to other losses is an interesting direction of future work, as opposed to a weakness.

Dear reviewers,

Apologies for bothering you! Since we are getting close to the end of the discussion period, we would be grateful and would sincerely appreciate if you could respond to our rebuttal, leaving us enough time to address any remaining questions.

Thanks, Authors