REVIEW 2 major objections 4 minor 40 references
Differentially Private Federated Clustering with Random Rebalancing
T0 review · 2 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read RR-Cluster proposes random rebalancing to guarantee a minimum number of client updates per cluster, reducing the effective noise needed for client-level differential privacy in federated clustering while keeping the same privacy budget.
desk verdict Random rebalancing is a genuinely useful trick for private federated clustering, but the privacy proof as written understates ε because one client's removal can change two cluster sums; the fix looks mechanical, not fatal. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The rebalancing step is the mechanism: in each round, compare each cluster's assigned update count to B, uniformly sample surplus updates from large clusters, and reassign them to small clusters until every cluster has at least B updates. This turns cluster size from an uncontrolled random quantity into a guaranteed lower bound, so the Gaussian noise added after averaging has effective scale roughly (2Cθ)σθ over B updates; larger B trades a smaller noise term for larger assignment bias τ. The convergence proof uses Lemma 4.8's misassignment probability τ, which bounds three error sources: loss-based cluster-selection error, identifier privatization noise, and resampling error.
What would settle it
Compute the exact L2 sensitivity of the vector of all k cluster sums when adding or removing one client in the rebalancing branch, using the noise scale as implemented (which depends on the rebalanced cluster size), and compare the resulting per-round RDP with ε1+ε2. If the two changed clusters make the observed per-round RDP exceed ε1+ε2, the reported privacy guarantee is not met. This calculation can be done directly on the FashionMNIST setup with B > 0.
Extended reading notes
Core claim
RR-Cluster's central claim is that uncontrolled cluster cardinality is the main reason vanilla DP federated clustering needs excessive noise; enforcing a minimum cluster size B by data-independent random rebalancing reduces the noise variance while introducing only bounded clustering bias. Formally, each round the server privatizes cluster identifiers, identifies large clusters (with size at least B) and small ones, samples updates from large clusters uniformly at random to top up small clusters to exactly B, clips updates, adds Gaussian noise with scale involving 2Cθ after averaging, and updates the k cluster models. The paper claims this output satisfies client-level (ε,δ)-DP under Rényi d
Load-bearing premise
The proof assumes the k cluster models are separate privacy mechanisms on disjoint client sets, so adding or removing one client changes at most one cluster's released average with sensitivity at most 2Cθ; when random rebalancing moves an update between two clusters, that premise is strained because two released averages change together with data-dependent noise variance.
Editorial extensions
If this is right
- At any fixed DP budget (ε,δ), RR-Cluster attains higher cluster-model accuracy than privatizing the same base algorithm directly, with the largest gains for imbalanced clusters and small ε.
- The method is communication-preserving: no extra client-server messages are needed beyond what the base clustering algorithm already sends.
- The rebalancing floor B also prevents model collapse in non-private training, keeping all k cluster models updated even when a base algorithm would abandon some clusters.
- Choosing B close to qM/k maximizes noise reduction but increases assignment bias; the paper's convergence bound implies an optimal intermediate B exists.
- Because rebalancing choices are data-independent uniform sampling after private assignments, the advertised per-round RDP accounting remains ε1+ε2 under the paper's parallel-cluster assumption.
Reading between the lines
- A natural extension the authors do not explore is a per-round B schedule: start small to learn initial assignments, then increase B as cluster models separate, reducing noise later without the early bias.
- The bias/variance decomposition suggests a testable practitioner rule: measure cluster separation via distances between cluster models and set B larger when separation is high; the paper evaluates discrete B values but does not propose such a rule.
- The same random-rebalancing idea could apply to other multi-model or group-aggregation settings, such as personalized federated learning or secure aggregation, wherever group size is uncontrolled and privacy noise scales inversely with group size.
- A strict privacy accounting for the rebalancing branch remains an open check: when one client addition/removal changes two cluster averages and the noise variance is data-dependent, the per-round RDP should be computed on the joint vector of all k cluster outputs rather than per cluster; the paper does not perform that calculation.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes RR-Cluster, a plug-in technique for differentially private federated clustering. The idea is to randomly rebalance client updates across clusters so that every cluster receives at least B updates per round, which reduces the effective DP noise after model averaging. The authors give an RDP-based privacy analysis (Theorem 4.2), convergence bounds for the IFCA instantiation (Theorem 4.10), and experiments on FashionMNIST, EMNIST, Shakespeare, CIFAR10, and CIFAR100 showing improved privacy/utility tradeoffs over DP-FedAvg, DP-IFCA, DP-FeSEM, and DP-FedCAM.
Significance. If the privacy analysis were correct, the paper would make a useful and practical contribution: the rebalancing step is simple, algorithm-agnostic, and communication-free, and the empirical gains are substantial. The convergence analysis explicitly models the bias/variance tradeoff induced by B, which is a strength. However, the entire contribution rests on the claimed client-level DP guarantee. The proof of that guarantee has a load-bearing gap, and the reported ε values are therefore not supported as written.
major comments (2)
- [Appendix A.2, Proposition 4.1, Theorem 4.2] The sensitivity analysis treats each cluster's sum separately and concludes that the overall sensitivity is at most 2Cθ. This is not a bound on the L2 sensitivity of the joint vector of k cluster sums. In Case 2, removing one client from cluster 1 and moving an update Δθ′ from cluster 2 into cluster 1 changes cluster 1's sum by Δθ′−Δθ_A and cluster 2's sum by −Δθ′. With Δθ′=−Δθ_A and both norms equal to Cθ, the joint change has L2 norm sqrt(5)Cθ, not 2Cθ. Since the Gaussian noise per coordinate is calibrated to 2Cθ, the claimed (α,ε2)-RDP bound for the k-model output does not follow. Theorem 4.2 and all experimental ε values inherit this gap.
- [Algorithm 1 line 11; Eq. (22), Appendix B.2] The released object is the normalized average Δθtilde_j = (sum_j + Gaussian_noise)/|S_j|, not the noisy sum. The quantity |S_j| is data-dependent: it is determined by private cluster identifiers and by the random rebalancing step. The proof bounds only the sensitivity of the sum, with fixed noise variance, and never accounts for the division by a data-dependent cluster size. Dividing a DP output by a data-dependent random variable is not automatically privacy-preserving unless the divisor is included in the mechanism's analysis or shown to be independent of the data. A correct proof must analyze the joint mechanism that outputs both the partition and the normalized averaged models, or condition on the final partition as a private output and bound conditional sensitivity.
minor comments (4)
- [Section 3.2, Algorithm 1 line 10] The clipping formula uses ∥s∥ in the denominator; it should be ∥Δθ_i∥ or an explicitly defined norm of the model update.
- [Section 4.1] The text refers to 'the randomized mechanism M in Theorem 4.1'; the referenced result is Proposition 4.1, not a theorem.
- [Abstract and Section 3.2] Typos: 'RR-Clsuter' in the abstract and 'rabanlancing' in Section 3.2.
- [Assumption 4.7 and Appendix A.3] Minor typos: 'stocastic' should be 'stochastic'; 'experiemtns' should be 'experiments'.
Circularity Check
No significant circularity: the privacy/utility and convergence claims follow from the stated mechanism and external DP composition theorems; the main risk is a proof gap in sensitivity analysis, not circular reasoning.
full rationale
RR-Cluster's central benefit is derived directly from Algorithm 1/2: lines 8-11 enforce |S_j| >= B before aggregation, so the per-cluster update uses the added sum noise divided by |S_j| >= B. This is a structural averaging argument, not a fitted quantity renamed as a prediction. The privacy accounting (Proposition 4.1, Theorem 4.2, Appendix A.3) applies the standard Gaussian mechanism and RDP composition/sub-sampling theorems of Mironov and Wang et al.; these are external, parameter-free results with stated sensitivities. The convergence analysis (Lemma 4.8, Theorem 4.10) is derived from Assumptions 4.3-4.9; no parameter is fitted to data and then reported as a prediction. B is an algorithm input, and its bias/variance effect is analyzed rather than defined into the result. The only same-author citations are to benchmarks/background (LEAF [5], Motley [35], one-shot clustering [9]) and are not load-bearing; there is no imported uniqueness theorem and no ansatz smuggled through a same-author citation. The one serious issue is Appendix A.2 Case 2: when removing one client triggers rebalancing, two cluster sums change simultaneously, and the written bound of 2Cθ on the overall sensitivity may understate the joint sensitivity (the vector of changes can have squared norm (2Cθ)^2 + Cθ^2). That is a correctness/proof gap affecting Theorem 4.2, but it is not a circularity—the claimed bound is not equivalent to its input by construction—so it does not change the circularity score.
Assumptions & free parameters
free parameters (5)
- B =
grid search {4, 8, 12}
- Cθ =
grid search in np.logspace(-1,-3,5)
- Cs =
0.1
- σs =
not reported
- σθ =
derived from ε2
assumptions (6)
- domain assumption F_j are λ-strongly convex and L-smooth (Assumption 4.3)
- domain assumption Bounded loss and gradient variance (Assumptions 4.4, 4.5)
- domain assumption Bounded variance of cluster sizes µ² (Assumption 4.6)
- domain assumption Bounded gradient norm G with Cθ > G (Assumption 4.7)
- domain assumption Initial models close to cluster optima and cluster separation large (Assumption 4.9)
- ad hoc to paper Per-cluster Gaussian mechanisms can be composed in parallel with a single-cluster sensitivity change and fixed output variance (Appendix A.2, Proposition 4.1)
Cite this review
Pith. "Pith review of Differentially Private Federated Clustering with Random Rebalancing." pith.science (2026). https://pith.science/paper/JIILCX34
@misc{pith2026250806183,
author = {Pith},
title = {Pith review of: Differentially Private Federated Clustering with Random Rebalancing},
year = {2026},
howpublished = {\url{https://pith.science/paper/JIILCX34}},
note = {Machine review of arXiv:2508.06183}
}
read the original abstract
Federated clustering aims to group similar clients into clusters and produce one model for each cluster. Such a personalization approach typically improves model performance compared with training a single model to serve all clients, but can be more vulnerable to privacy leakage. Directly applying client-level differentially private (DP) mechanisms to federated clustering could degrade the utilities significantly. We identify that such deficiencies are mainly due to the difficulties of averaging privacy noise within each cluster (following standard privacy mechanisms), as the number of clients assigned to the same clusters is uncontrolled. To this end, we propose a simple and effective technique, named RR-Cluster, that can be viewed as a light-weight add-on to many federated clustering algorithms. RR-Cluster achieves reduced privacy noise via randomly rebalancing cluster assignments, guaranteeing a minimum number of clients assigned to each cluster. We analyze the tradeoffs between decreased privacy noise variance and potentially increased bias from incorrect assignments and provide convergence bounds for RR-Clsuter. Empirically, we demonstrate the RR-Cluster plugged into strong federated clustering algorithms results in significantly improved privacy/utility tradeoffs across both synthetic and real-world datasets.
Figures
Reference graph
Works this paper leans on
-
[1]
Tensorflow federated: Machine learning on decentralized data. URL https://www. tensorflow.org/federated
-
[2]
Federated learning with personalization layers
Manoj Ghuhan Arivazhagan, Vinay Aggarwal, Aaditya Kumar Singh, and Sunav Choudhary. Federated learning with personalization layers. arXiv preprint arXiv:1912.00818, 2019
arXiv 1912
-
[3]
Dcfl: Dynamic clustered federated learning under differential privacy settings
Andrea Augello, Giulio Falzone, and Giuseppe Lo Re. Dcfl: Dynamic clustered federated learning under differential privacy settings. In PerCom Workshops, 2023
work page 2023
-
[4]
Dif- ferentially private clustering in high-dimensional euclidean spaces
Maria-Florina Balcan, Travis Dick, Yingyu Liang, Wenlong Mou, and Hongyang Zhang. Dif- ferentially private clustering in high-dimensional euclidean spaces. In International Conference on Machine Learning, pages 322–331. PMLR, 2017
work page 2017
-
[5]
Leaf: A benchmark for federated settings
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Koneˇcn`y, H Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:1812.01097, 2018
arXiv 2018
-
[6]
Locally private k-means in one round
Alisa Chang, Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. Locally private k-means in one round. In International conference on machine learning, pages 1441–1451. PMLR, 2021
work page 2021
-
[7]
Emnist: Extending mnist to handwritten letters
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In IJCNN, 2017. 10
work page 2017
-
[8]
Scalable differentially private clustering via hierarchically separated trees
Vincent Cohen-Addad, Alessandro Epasto, Silvio Lattanzi, Vahab Mirrokni, Andres Munoz Medina, David Saulpic, Chris Schwiegelshohn, and Sergei Vassilvitskii. Scalable differentially private clustering via hierarchically separated trees. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 221–230, 2022
work page 2022
Show all 40 references
-
[9]
Heterogeneity for the win: One-shot federated clustering
Don Kurian Dennis, Tian Li, and Virginia Smith. Heterogeneity for the win: One-shot federated clustering. In International Conference on Machine Learning, pages 2611–2620. PMLR, 2021
2021
-
[10]
Calibrating noise to sensitivity in private data analysis
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265–284. Springer, 2006
2006
-
[11]
An efficient framework for clustered federated learning
Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. In NeurIPS, 2020
2020
-
[12]
Clustered federated learning with adaptive local differential privacy on heterogeneous iot data
Zaobo He, Lintao Wang, and Zhipeng Cai. Clustered federated learning with adaptive local differential privacy on heterogeneous iot data. IEEE IoTJ, 2023
2023
-
[13]
Optimal differentially private algorithms for k-means clustering
Zhiyi Huang and Jinyan Liu. Optimal differentially private algorithms for k-means clustering. In PODS, 2018
2018
-
[14]
Advances and open problems in federated learning
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and trends® in machine learning, 14(...
2021
-
[15]
Clustered federated learning via gradient- based partitioning
Heasung Kim, Hyeji Kim, and Gustavo De Veciana. Clustered federated learning via gradient- based partitioning. In ICML, 2024
2024
-
[16]
Learning multiple layers of features from tiny images
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009
2009
-
[17]
Federated learning: Chal- lenges, methods, and future directions
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE SPM, 2020
2020
-
[18]
Private adaptive optimization with side information
Tian Li, Manzil Zaheer, Sashank Reddi, and Virginia Smith. Private adaptive optimization with side information. In ICML, pages 13086–13105, 2022
2022
-
[19]
On the convergence of fedavg on non-iid data
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In ICLR, 2020
2020
-
[20]
Differentially private federated clustering over non-iid data
Yiwei Li, Shuai Wang, Chong-Yung Chi, and Tony QS Quek. Differentially private federated clustering over non-iid data. IEEE IoTJ, 2023
2023
-
[21]
On privacy and personalization in cross-silo federated learning
Ken Liu, Shengyuan Hu, Steven Z Wu, and Virginia Smith. On privacy and personalization in cross-silo federated learning. Advances in neural information processing systems, 35:5925–5940, 2022
2022
-
[22]
Multi-center federated learning: clients clustering for better personalization
Guodong Long, Ming Xie, Tao Shen, Tianyi Zhou, Xianzhi Wang, and Jing Jiang. Multi-center federated learning: clients clustering for better personalization. WWW, 2023
2023
-
[23]
Privacy- preserving clustering federated learning for non-iid data
Guixun Luo, Naiyue Chen, Jiahuan He, Bingwei Jin, Zhiyuan Zhang, and Yidong Li. Privacy- preserving clustering federated learning for non-iid data. FGCS, 2024
2024
-
[24]
Structured federated learning through clustered additive modeling
Jie Ma, Tianyi Zhou, Guodong Long, Jing Jiang, and Chengqi Zhang. Structured federated learning through clustered additive modeling. NeurIPS, 2023
2023
-
[25]
Differentially private clustered federated learning
Saber Malekmohammadi, Afaf Taik, and Golnoosh Farnadi. Differentially private clustered federated learning. arXiv preprint arXiv:2405.19272, 2025
2025 arXiv
-
[26]
Communication-efficient learning of deep networks from decentralized data
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In AISTATS, 2017. 11
2017
-
[27]
Communication-efficient learning of deep networks from decentralized data
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficient learning of deep networks from decentralized data. In AISTATS, 2017
2017
-
[28]
Learning differentially private recurrent language models
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In ICLR, 2018
2018
-
[29]
Rényi differential privacy
Ilya Mironov. Rényi differential privacy. In CSF. IEEE, 2017
2017
-
[30]
Clustering algorithms for the centralized and local models
Kobbi Nissim and Uri Stemmer. Clustering algorithms for the centralized and local models. In Algorithmic Learning Theory, 2018
2018
-
[31]
The complete works of William Shakespeare
William Shakespeare. The complete works of William Shakespeare. Race Point Publishing, 2014
2014
-
[32]
Make landscape flatter in differentially private federated learning
Yifan Shi, Yingqi Liu, Kang Wei, Li Shen, Xueqian Wang, and Dacheng Tao. Make landscape flatter in differentially private federated learning. In CVPR, pages 24552–24562, 2023
2023
-
[33]
Locally private k-means clustering
Uri Stemmer. Locally private k-means clustering. JMLR, 2021
2021
-
[34]
Subsampled rényi differential privacy and analytical moments accountant
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In AISTATS, pages 1226–1235. PMLR, 2019
2019
-
[35]
Motley: Benchmarking heterogeneity and personalization in federated learning
Shanshan Wu, Tian Li, Zachary Charles, Yu Xiao, Ziyu Liu, Zheng Xu, and Virginia Smith. Motley: Benchmarking heterogeneity and personalization in federated learning. arXiv preprint arXiv:2206.09262, 2022
2022 arXiv
-
[36]
Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms
Han Xiao, Kashif Rasul, and Roland V ollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017. 12 A Privacy Analysis A.1 RDP to DP Conversion We restate existing RDP-to-DP conversion theorem, as follows. ...
2017 arXiv
-
[37]
+ λ 2 ∥θj − θ∗ 1∥2 ≥ F 1(θ∗
-
[38]
+ λ∆2 2 ( 1 2 + β)2 (12) and F 1(θ1) ≤ F 1(θ∗
-
[39]
+ L 2 ∥θ1 − θ∗ 1∥2 ≤ F 1(θ∗
-
[40]
Balanced Clusters
+ λ∆2 2 ( 1 2 − β)2. (13) Thus we have that F 1(θj) − F 1(θ1) 2 ≥ λ∆2 2 ( 1 2 + β)2 − λ∆2 2 ( 1 2 − β)2 = βλ∆2 2 . (14) 15 According to the Chebyshev’s inequality and the bounded variance assumption, we obtain Pr(Fi(θ1) > t) ≤ 4η2 β2λ2∆4 and similarly, Pr(Fi(θj) ≤ t) ≤ 4η2 β2λ...
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.