Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity

1. In the discussion around Lemma 1 and Corollary I, it is mentioned that the asymptotic convergence mainly depends on $\hat{\sigma}_p^2$. From the expression of $\mathbb{E}[\hat{\sigma}_p^2]$ in Lemma 1, one can compute that $\frac{d \text{ } \mathbb{E}[\hat{\sigma}_p^2]}{d p} = (1-2p)(\zeta^2 + \delta^2) - (\sigma^2 - \tilde{\sigma}^2)$. Now, for non-iid situations when $\zeta^2 \gg (\sigma^2 - \tilde{\sigma}^2)$, $\mathbb{E}[\hat{\sigma}_p^2]$ is an increasing function of $p$ around $p=0$ (no synthetic data). So, the convergence should get worse according to this result with small values of $p$ or a little bit of synthetic data.

In fact, I think the value of $p$, say $p^{\ast}$, such that $\mathbb{E}[\hat{\sigma}_{p^{\ast}}^2] < {\sigma}^2$ is going to be large (this can easily be calculated because it is quadratic in $p^{\ast}$).

Can the authors address this?

2. I don't understand the second-last sentence on page 4 "When $\sigma^2=0$, or in general...". Can you quantify "super-linearly"? Also, where is $\sqrt{L_p}$ coming up in the bound of Corollary I? Overall this statement doesn't make too much sense to me.

3. The paper talks about privacy of the local data but there are no formal privacy guarantees given with the proposed method. Moreover, training a generator on each client is also expensive.

1. It is already known that reshuffling data locally reduces the variance (see e.g. [1]). Why is it any harder to study this problem across clients?
2. This is the main dealbreaker: sending synthetic images still breaks privacy. Even on massive datasets, generator models routinely reproduce training data (see [2, 3]). The data on any client in an ordinary federated learning problem is several orders of magnitude smaller than ImageNet or other large training sets, it is virtually guaranteed that a synthetic generator trained on local data would simply regurgitate client data.

My opinion is that the paper's results are not very theoretically surprising, and its practicality is nil because of privacy considerations. For this reason, I recommend rejection.

[1] Mishchenko, Khaled and Richtárik. Proximal and Federated Random Reshuffling, ICML 2022. [2] Tinsley, Czajka, and Flynn. "This face does not exist... but it might be yours! identity leakage in generative models." IEEE/CVF Winter Conference on Applications of Computer Vision. 2021. [3] Carlini N, Hayes J, Nasr M, Jagielski M, Sehwag V, Tramer F, Balle B, Ippolito D, Wallace E. Extracting training data from diffusion models. In32nd USENIX Security Symposium (USENIX Security 23) 2023 (pp. 5253-5270).

1. This paper does not address important privacy concerns of transmitting synthetic samples generated on clients.

2. To evaluate the paper by leaving privacy concerns out of the scope, there are a few aspects I would like to obtain more insights:

   i. if not for privacy concerns, would FL still add value on top on synthetic data training obtained via stronger generative models fine-tuned on clients?  For example, by using state-of-art diffusion model for image, or Large language model for NLP problems.
   

   ii. I would like to see an ablation on the synthetic data generator used. Different generator quality should theoretically correspond to different $\delta$ in Assumption 4. Hence I would like to see how $\delta$ influence the quality backed by experiments. This will also enhance the practicality and shed some insight on the tightness of Corollary 1.

-The theoretical results although insightful, appear to be straightforward derivations applied to known convergence bounds (Koloskova et al., 2020; Woodworth et al., 2020; Khaled et al., 2020). Furthermore, the idea of data reshuffling in FL is well known and as a result the theoretical contribution and the novelty of this work is somewhat marginal.

-A major concern lies on the metric of accuracy that is used in this work. Specifically, in the proposed method the clients obtain an augmented dataset which could potentially be very different from their initial data. As a result, achieving high accuracy on these augmented datasets is a potentially substantially easier task which however is misaligned with the true objectives of the clients. The authors need to further discuss and clarify this issue. Specifically, in the experiments presented it is my understanding that the size of the initial dataset for client $i$, is equal in size to the synthetic datasets that is assigned to the same client $n_i = \tilde{n}$. If indeed this is the case the resulting accuracy could be a misleading metric of success.

-This method relies on clients being able to produce synthetic data of good quality. In many FL settings however clients often have access to very few samples which could significantly hinder the effectiveness/soundness of the proposed method.

-In the comparison with other synthetic-data based approached it would be beneficial to include convergence plot instead of just providing a final accuracy table. Further, the parameters for DENSE should be chosen optimally to provide a fair comparison.

-The comment on page 9 in section "Practical implication" claiming that "Additionally, the client has the option of checking the synthetic images and only sharing the less sensitive synthetic images to alleviate the information leakage." seems unreasonable. It is hard to imagine clients choosing manually images that diminish the information leakage out of a big number of synthetically produced data.

-Minor issues

• Page 3, end of paragraph 1: "fail achieve" --> "fail to achieve".
• Page 4, paragraph 3: "it might infeasible" -->"it might be infeasible"