Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the federated learning problem. In this model, local clients are allowed to jointly train a model without sharing user data, and the central goal is to design communication efficient algorithms. The author gives a federated averaging Langevin algorithm and provide theoretical guarantees for strongly log-concave distributions. These results provide guidance on the choice of learning rates and local updates to minimize communication cost. The authors also consider applying correlated noises and using only partial device updates, which are more applicable in practice.
main_review: The authors propose the federated averaging Langevin algorithm (FA-LD) for posterior inference. The authors present non-trivial non-asymptotic convergence analysis for FA-LD for distributions with strongly smooth and strongly convex Hamiltonian and with bounded variance of noise in the stochastic gradient. The assumption of bounded gradient in l2 norm is not required in contrast to the previous work FedAvg as well as many others in literature. The analysis of FA-LD indicates the number of global steps and the choice of the learning rate. More importantly, it shows that the number of local steps should be set roughly as the order of square root of the condition number. The authors further obtain non-trivial results in the cases of varying learning rates in each step, privacy-accuracy tradeoff via correlated Gaussian noises, and computation model with partial device participation. 

The highlights of this paper are novel theoretical analysis of the FA-LD algorithm. It demonstrates how the injected noise, the data heterogeneity, and the stochastic-gradient noise affect the convergence. It would be nice if the authors could also provide some lower bound or worst case analysis for the FA-LD algorithm, to show that the current convergence guarantees are tight or close to tight. For example, how does FA-LD behave for Gaussian posteriors? Is the convergence rate in the main theorem asymptotically optimal for Gaussian?

Detailed comments:
Page 3, right before Section 4: “\tilde{f} is a unbiased estimate of f” 
Shouldn’t it be “\grad \tilde{f} is an unbiased estimate of \grad f”? 

summary_of_the_review: Overall, I think this is a nice paper with strong theoretical results. It provides insights to the theoretical study of standard sampling algorithms in federated learning. The paper is also well-written.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors:

1.  propose a federated learning version of Langevin diffusion sampling. 

2. develop theoretical guarantees for FA-LD for strongly log-concave distributions with non-i.i.d data and study how the injected noise and the stochastic gradient noise, the heterogeneity of data, and the varying learning rates affect the convergence.

3. analyze the partial participation setting. 
main_review: Strength:

1. The idea of sampling using Langevin diffusion in the federated learning setting is new. 

Weakness:

 Since this is a theoretical paper I am basing my decision on its theoretical contribution.

1. Novelty in the proof of LD is incremental.  Only part of the proof which is different from the traditional proof of LD is the divergence term. But showing that this term is small (Lemma B.3) follows very simply from typical strongly convex optimization techniques. All the results corresponding to partial participation and varying rates follow almost directly  from the proof of the main theorem and does not have much theoretical novelty.

2. I liked the idea of allowing for correlated noise but I could not find the proof of theorem B.8 (theorem 5.9) in the paper. So it's difficult to gauge the difficulty of this part or even the correctness of this result. If I have missed the proof, and the authors could point me towards it, that would be great. 
 
summary_of_the_review: The paper lacks theoretical novelty but I liked the idea of introducing LD in federated setting. I may change my decision after discussion with other reviewers.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes Federated Averaging Langevin Dynamic algorithm (FA-LD). The theoretical guarantees for the proposed algorithm are developed and their relationships with noise type, heterogeneity, and learning rate are studied. 
main_review: The paper has shown extensive theoretical analysis for the proposed FA-LD method, such as convergence for independent noise and varying learning rates, with or without full device participation. However, given the existing theoretical analysis for SGLD based on 2-Wasserstein distance and theoretical analysis for FedAvg with or without full device participation, the results are straightforward. Could the authors show the difficulty of the theoretical analysis in this paper?

Empirical studies are missing in the current version. The experiment section should be added to the paper to validate the theoretical findings and investigate the performance of FA-LD. Particularly, the reviewer would like to see the performance of FA-LD in terms of different local updates, learning rates, participating devices, etc, and its comparison with other distributed LD methods. 

 Typo:
section 3.2, "a energy function"
summary_of_the_review: The paper has given extensive theoretical convergence analysis for FA-LD algorithm via 2-Wasserstein. However, empirical studies to verify theoretical findings are missing in the main paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a federated averaging Langevin algorithm (FA-LD) and analyzes its convergence under non-iid and partical participation settings.
main_review: The main contribution is the theoretical guarantees for a federated averaging Langevin algorithm for strongly log-concave distributions with non-i.i.d data. 

The proof sketch is well written and clear. It seems that the proof is sound.
However, most of the analysis technique can be founded in lituerature, the proof technique is thus standard.

I think the writing has room to improve, but overall it is clear and easy to follow.

I have the following concerns:
1. In Section 3.1, I think it is better to stress the $\beta_k$ is an auxiliary sequence. Besides, how $\beta_k^c$ involves the Local Updates step in one iterate of the FedAvg algorithm seems to be incorrect. I think it should add $\theta_k c = \beta_k^c$ for $2 \le k \le K$.
2. Algorithm 1 is easy to understand since it is an approximation of FedAvg. However, Algorithm 2 is not so intuitive. The author didn’t explain why we should add an additional \textbf{shared} noise $\dot{\xi}_{k}$ and make the final noise correlated with the original noise $\xi_{k}^{c}$ in Algorithm 2. How does such a shared noise ensure privacy and what kind of definition of privacy is used ? The last paragraph of Section 4 is quite vague and amphibolous. To substantiate the point, I think more argument and discussion should be added.
3. The current presentation of main result is troublesome. The author could first introduce the main result and then provide a proof sketch. After all, not everyone is interested in the proof technique. What’s more, the analysis for algorithm 2 is deferred to Section 5.3.3, but its introduction is Section 4. I think it is somewhat too late and not helpful for readers to grasp the algorithm. 
4. The first paragraph of Section 5.2 seem to have a type. $\nabla f\left(\bar{\theta}_{t}\right)$ should be defined as $\sum_{c=1}^{N} p_{c} \nabla f^{c}\left(\bar{\theta}_{t}\right)$.
5. Though this paper is theoretical, the author could still provide some numerical experiments to show the convergence of FA-LD. Those experiments can further validate the theorems, for example, the trade-off of $K$ and the effect of sampling methods. After all, FA-LD is different from FedAvg. I don’t know whether the convergence of FA-LD has been empirically studied before.
summary_of_the_review: The delcaimed contribution include FA-LD and its theoretical guarantees.
However, the analysis technique is commonly used in litureature, while no empirical expeirments to illustrate the effectiveness of FA-LD.
Besides, there are some presentation issues and ambiguity on motivation.
I don't think this paper is ready for publication.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies federated learning algorithms, where a collection of computing nodes seek to collectively optimize a global objective through parallelized updates executed at a server. Different from prior works which execute local-only stochastic gradient updates on non-convex losses, here a stochastic gradient Langevin update is developed, which additionally incorporates randomized Gaussian perturbations. Convergence theory is presented for the proposed scheme, which establishes point-wise  convergence in mean, as well as convergence in distribution according to the Wasserstein metric. Variations of the noise generating process which introduce heterogeneity and privacy preservation are also proposed and analyzed.

main_review: 
Assuming strong convexity (Assumption 5.2) seems completely ridiculous in this setting. One of the major motivations for considering stochastic gradient Langevin dynamics is to improve the performance of non-convex stochastic optimization algorithms so as to escape spurious stationarity points and arrive at global extrema. In fact, this can be rigorously shown to tend towards the distribution of global extrema without convexity with non-asymptotic rate given in Raginsky et al 2017

There are no numerical experiments that demonstrate the utility of the approach. How restrictive is it to consider log-concave distributions? This should preclude most neural network training in practice, which is the primary emphasis of federated learning, as compared with more classical methodologies based upon consensus/multi-agent optimization.

Is there a practical phenomenon where standard federated learning or its variants that use Lagrange multipliers such as FedDyan and SCAFFOLD get stuck, whereas this version with randomized perturbations does not? I feel that this scenario is exactly in non-convex settings, which is excluded from consideration in this work.

It is difficult to make sense of what are the specific technical innovations in the analysis here, and how they are a departure from earlier results. 
summary_of_the_review: 
This work is mainly of theoretical interest, as it considers randomized perturbations in a federated averaging setting. However, its technical scope precludes the most useful instances of it in practice, and it is missing experiments. Therefore, it seems of limited usefulness in my view.
review_title: null

Meta-review: This paper proposes a federated averaging Langevin dynamics (FA-LD) for numerical mean prediction with uncertainty quantification under the setting of federated learning. Convergence analysis for the proposed method under the smoothness and strong-convex assumptions is also provided, and the results are summarized in Theorems 5.7-5.10, each of which bounds the Wasserstein-2 distance $W_2(\mu_k,\pi)$ between the model distribution $\mu_k$ and the target distribution $\pi$ under different settings.

This paper received 5 reviews in total, with scores 6, 5, 3, 5, and 3. Some reviewers evaluated positively the novelty of the idea of using the Langevin dynamics in the federated setting, which I would also like to acknowledge. Upon reading the paper by myself, however, I find that the mathematical formulations are in some places not correct. What I think problematic is the third equation in equation (3): The right-hand side is a function of $N$ variables $\\\{\theta_k^c\\\}$, and they undergo different local updates at different clients when $k\not\equiv 0\mod K$ (i.e., the synchronization does not take place). Also $\nabla\tilde{f}^c$ is in general a nonlinear function of its argument. Therefore, the right-hand side cannot be written in general as a function of a single variable $\theta_k$ which is defined as $\theta_k=\sum_{c=1}^Np_c\theta_k^c$, making this equation incorrect. This problem would affect various parts of the arguments to follow in this paper, such as the first two equations in equation (16) on page 14, the two inline equations just after equation (16), equation (18), the second equality in the inline equation in page 15, line 1, and the third line in equation (25) on page 18, to mention a few. Thus I have to question the validity of the theoretical development in this paper.

Another point I would like to mention is that I did not understand the definition of Schemes I and II in Section 5.4. It is not stated at all that $\mathcal{S}_k$ is a random quantity here. Furthermore, the conditions "with/without replacement" are not described at all.  Still another point to mention is that I did not understand the claim in page 7, lines 30-31. Does it mean: If one knows the number $T_\epsilon$ of steps to achieve the precision $\epsilon$, then one should set the number $K$ of local steps per synchronization should be set of the order of $\sqrt{T_\epsilon}$. But $T_\epsilon$ depends on $K$, so that it would be unnatural to assume that one knows $T_\epsilon$ irrespective of $K$ in the first place.

Because of these, I would judge that this paper is not yet ready for presentation in its current form. I would therefore not be able to recommend acceptance of this paper.

Minor points:
- Citation style: The authors use throughout the paper what are called the *narrative citations* even though there are occasions where what are called the *parenthetical citations* (the author name and publication date are both enclosed in parentheses) should be used.
- page 3, line 7: is (the -> an) unbiased stochastic gradient; There are several unbiased estimators for the gradient, and what is mentioned here is only one instance of them.
- page 3, lines 23-24: The aggregation should take place not on each client but on the central server.
- page 3, line 36: a(n) energy function; a(n) unbiased estimate
- page 5, lines 17-20: The contents of Assumptions 5.1 and 5.2 are not assumptions but definitions.
- page 6, line 2: to obtain (the -> a)  lower bound
- page 6, line 18: $\mathcal{D}^2$ is undefined.
- page 8, line 39: (a -> the) probability $p_c$ if it is meant to be the one defined in page 3, line 8. Otherwise, use of the same symbol to represent different quantities should be avoided.
- page 14, line 25: mod ($E$ -> $K$) =0
- page 15, line 30: $H_\rho^2$ -> $H_\rho$
Decision: Reject