Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper extend Langevin Monte Carlo into federated learning setting with non-i.i.d. data and partial participation. Authors tried to develop convergence guarantee for this algorithm under assumption that the target distribution is strongly log-concave. According to their results, the convergence of their algorithm depends on data heterogeneity, learning rate, gradient noise and correlation between Gaussian vectors among clients. A differential privacy guarantee is also provided.
strength_and_weaknesses: **Strength**:

Some claims in this paper appear to be new, including the convergence of FA-LD with correlated Gaussian noise and partial participation.

**Main Weakness**:

The soundness of the theoretical analysis is questionable.

Authors define the auxiliary continuous-time processes
$$
\mathrm{d} \bar{\theta}_t=-\nabla f\left(\bar{\theta}_t\right) \mathrm{d} t+\sqrt{2 \tau} \mathrm{d} \bar{W}_t
$$
and authors claim that "continuous-time algorithm is known to converge to the stationary distribution $\pi(\theta) \propto e^{-\frac{f(\theta)}{\tau}}$".

When the term $\nabla f\left(\bar{\theta}_t\right)$ means the gradient of function $f$ at point $\bar{\theta}_t$, I agree the above SDE converge to the Gibbs distribution.

However, authors interpret that term as 
$
\nabla f\left(\bar{\theta}_t\right)=\sum\_{c=1}^N p_c \nabla f^c\left(\bar{\theta}_t^c\right)
$.

The first problem is that, author left out the dynamics for $\bar{\theta}_t^c$ on each client, so the above SDE is not well-defined.
In Section D.1, authors use $\bar{\theta}\_s^c=-\int\_{k \eta}^s \nabla f^c\left(\bar{\theta}\_t^c\right) d t+\sqrt{2 \tau / p_c} \int\_{k \eta}^s \mathrm{~d} \bar{W}\_t$, and claim this equation is a consequence of eq. (20) (which is the SDE above for $\bar{\theta}_t$). But that is not true. Eq. (20) only defines dynamics for $\bar{\theta}_t$ but not for $\bar{\theta}_t^c$.

The second problem is that, even if we append the missing definition, the convergence claim is still wrong.
Let's choose following SDE for $\bar{\theta}_t^c$ (which matches the integral authors used in Section D.1):
$$
\mathrm{d} \bar{\theta}_t^c=-\nabla f^c\left(\bar{\theta}_t^c\right) \mathrm{d} t+\sqrt{2 \tau/p_c} \mathrm{d} \bar{W}_t
$$
It is clear that the distribution of $\bar{\theta}_t^c$ converge to $\pi^c(\theta) \propto e^{-\frac{p_c f^c(\theta)}{\tau}}$.

$\bar{\theta}_t$ is weighted average of $\bar{\theta}_t^c$, thus the distribution of $\bar{\theta}_t$ will converge to some kind of mixture of $\pi^c$, but not $\pi(\theta) \propto e^{-\frac{f(\theta)}{\tau}}$.

In summary, the auxiliary continuous-time processes defined in this paper doesn't converge to desired distribution $\pi$, and all convergence theorems w.r.t. $\pi$ are wrong.

**Other questions**:

The assumption G.1 is clearly in conflict with assumption 4.2, thus Theorem 4.7 and Theorem 5.7 cannot hold at same time, or more specifically, we can guarantee either convergence or privacy, but not both. Is there any possible mitigation to that dilemma?

Lemma 4.4 is called "informal version of Lemma B.1". Which part of its statement is informal?
clarity,_quality,_novelty_and_reproducibility: The writing is clear and the contribution of the paper is presented with clarity.
summary_of_the_review: My main concern is the soundness of the theoretical analysis.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies non-asymptotic convergence of federated averaging Langevin dynamics in 2-Wasserstein distance, where the target is log strongly concave. The authors consider stochastic gradient, constant and varying learning rates, privacy-accuracy trade-off, partial device participation. They also discuss differential privacy guarantees. 
strength_and_weaknesses: This is a solid theory paper, and the analysis seems to be rigorous. 

However, just in my opinion, I feel that the authors should highlight a bit more about their technical contributions. For example, under the log-strongly-concave setup for overdamped Langevin, the method to obtain convergence is well known, see e.g. Arnak S Dalalyan and Avetik Karagulyan (2019) "User-friendly Guarantees for the Langevin Monte Carlo with Inaccurate Gradient." The authors perhaps should comment on what is the technical difficulty under the federated averaging setting and how they overcome it. Right now, the impression I have is that even though the authors discusses many model setups, for non federated averaging case, they are known in the literature, so the current paper is just a collection of many results, where the only novelty is the presence of the federated averaging. 

Also, the authors mentioned that The frequently used bounded gradient assumption of $\ell_{2}$ norm in FedAvg optimization is not required. It would be nice if the authors can elaborate more on this point and why they can remove this assumption. Also, if they can remove this assumption for Langevin dynamics for sampling, does that mean their techniques can be used to remove this assumption for optimization as well?

Moreover, I am just wondering whether the non-asymptotic convergence is sharp in the current paper. For example, there have been many works in recent years, and one of them is Li et al. (2021) "Sqrt(d) Dimension Dependence of Langevin Monte Carlo", where they used mean-square analysis to obtain better dependence on the dimension d. I am wondering whether that is possible in the federated averaging setting. At least, the authors should make some comments on whether the convergence rates they obtained are optimal or not depending on the model parameters. For example, if you reduce your results to the special case for standard SGLD, are your results sharp according to the literature? This will help the readers understand how good the results are presented in the current paper. 

I am also wondering what is the technical difficulty if you consider non-convex $f$, as in Raginsky et al. (2017). It is possible that non-convex setting is very challenging for the federated averaging setting, but that can also help the readers appreciate the log-strongly-concave assumption made in the paper and make it more clear about the technical challenge in the federated averaging setting. 

clarity,_quality,_novelty_and_reproducibility: Overall, the paper is well written and the presentations are clear. I have some minor suggestions.

(1) on page 2, when you introduced local updates, "then conduct $K\geq 1$ local steps", please make it more clear whether you take $k=0,1,\ldots,K-1$ or not? That is, what is the relation between $k$ and $K$?

(2) In section B.1., it is a bit unusual to use $\gamma^2$ to denote a measure.

(3) In the paragraph about Bukholder-Davis-Gundy inequality in section F, is it true that $\phi=\psi$? Please provide a reference. It seems to me that you are simply stating a very special case of Bukholder-Davis-Gundy inequality which is a direct result of Doob's martingale inequality and Ito's isometry. 
summary_of_the_review: The paper is a theory paper that provides non-asymptotic convergence results for federated averaging Langevin dynamics. It would be better if the authors can make the technical contributions more clear and also comment about the quality of their non-asymptotic convergence results as I mentioned previously.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies a federated version of stochastic gradient Langevin dynamics (SGLD) that the authors dub FA-LD. Motivated by the shortcoming of existing federated optimization research which do not allow for uncertainty quantification, they consider a Bayesian version of the federated optimization problem where one wishes to sample from a posterior, and the negative log density of the posterior is distributed across multiple devices. They study the analog of federated averaging in this setting, where each device does a few steps of SGLD locally before the weight vectors are re-aggregated across devices. Their main findings are convergence bounds in $W_2$ for the law of the iterates, including for fixed learning rate, varying learning rate, correlated noise, and partial device participation. The authors also provide a result giving some differential privacy guarantees for their algorithm, as well as some empirical exploration of their method, including comparisons to vanilla SGLD.
strength_and_weaknesses: Strengths:

- This work provides rigorous theoretical guarantees for a federated sampling algorithm using SGLD.

- The theoretical guarantees are extensive: they include fixed and varying learning rate, correlated and un-correlated noise, and full and partial device participation.

- It includes a result addressing differential privacy of their algorithm

- The authors mention that they do not require $\ell_2$ bounds on the gradients as in the federated averaging optimization framework. I am not familiar enough with the federated averaging literature, nor their proof, to judge if this is significant or not

Weaknesses:

- Their algorithm and setting are not novel, having been already considered in the work Al-Shevidat et al 2020 (the authors address this in their paper; I am by no means saying they missed this reference)

- Their upper bounds (except for the upper-bound for varying learning rate) involve a term that does not go to zero as iterations go to infinity, apparently due to the independent SGLD steps

- The paper is written in a confusing fashion, it is difficult to understand what the definitions of the continuous time dynamics are. Also there is significant repetition between the appendix and main text, with the appendix basically being an extended version of the main text. The related work is in the appendix.

- While there are many results, it is not clear which is most important, what the key difficulties in establishing those results are, and none explain why FA-LD might outperform SGLD (the bounds as-is suggest that with more independent SGLD steps the algorithm performs worse)

- The experiments are not in a setting where the data is non-i.i.d. (in this context meaning the devices see fundamentally different portions of the data distribution). In fact, the data is split randomly between devices, undermining the need for federation

- Issues with correctness (added after reading reviewer PJdt's review): I agree that there seem to be major issues with correctness, greatly compounded by confusing definitions of the continuous time dynamics. I interpret them to be using continuous time dynamics where at all times t, the gradients are shared, which seems to be what they are indicating on the footnote on page 4 as well as in section A.1. As in the footnote on page 4, this means that
$$
\bar \theta_t^c = \bar \theta_t
$$ for all $t \in \mathbb{R}$ and $c \in [N]$. It follows, therefore, that
$$
\sum_{c = 1}^n p_c \nabla f^c (\bar \theta^c_t) = \sum_{c = 1}^n p_c \nabla f^c (\bar \theta_t) = \nabla f(\bar \theta_t),
$$ where the last gradient is in the usual sense. Hence the continuous time dynamics do indeed converge to the correct distribution. However, as reviewer PJdt points out, the integral formula for $\bar \theta_t^c$ seems to be using only the local dynamics
 $$
d \bar \theta^c_t = - \nabla f^c(\bar \theta^c_t) + \sqrt{2\tau/p_c} dW_t.
$$ These are obviously at odds with one another and seem to be a major problem with the proof of the discretization error bound in Lemma B.2. That said, the authors also have some continuous time variables $\beta$ which only follow the local gradients defined in subsection A.1, and it may be that the authors mean to prove Lemma B.2 with these alternate variables (which may not resolve their issues). Clarification on this point is seriously needed.


Al-Shedivat, Maruan, et al. "Federated learning via posterior averaging: A new perspective and practical algorithms." arXiv preprint arXiv:2010.05273 (2020).
clarity,_quality,_novelty_and_reproducibility: See strengths and weaknesses above.

Suggestions for improvement:

- The definition of the auxiliary continuous-time process $(\bar \theta_t)_{t \geqslant 0}$ could be made more clear, the usage of "synchronizes" is confusing and I needed to read the footnote to understand its meaning

- In my opinion, the paper would be improved if the discussion of related work was moved to the main text, and some of the variants on your main results be relegated to the appendix

- The sentence "Notably, since the Brownian motion..." on page 5 is confusing but seems like it is talking about novel aspects of their proof. Perhaps this could be expanded?

- More indication and discussion of the main result (which of the theorems is the most important and why?) would greatly help in comprehension. There was no heading that said "main results", nor links in the contributions section to these theorems. And more discussion of the significance of these results would helpful, in my opinion.

- The experiments don't seem to incorporate any use of uncertainty quantification. Perhaps a set of experiments that use the additional information you gain from a Bayesian approach over the vanilla FedAvg approach would be helpful to indicate the importance of your setting.

- Please clarify the nature of the continuous time dynamics.
summary_of_the_review: This work provides novel theoretical guarantees for a federated version of SGLD. While they do give several theoretical bounds, they generally suffer from an additive term that does not go to zero and it is difficult to judge their significance.  Moreover, their experiments are not extensive and don't incorporate a use of uncertainy quantification fitting their motivation of studying a Bayesian setting. Also, there are definitely issues with clarity of presentation and likely issues with correctness. Overall, I think that the work is not suitable for acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper provides rigorous theoretical guarantees for a federated sampling algorithm using using Langevin dynamics. The theoretical results are interesting and novel: they include fixed and varying learning rate, correlated and un-correlated noise, and full and partial device participation. Moreover, the results also consider the (differential) privacy aspects of SGLD. 

The reviews had some major concerns about the proofs of the paper (since the paper is mainly a theoretical paper) as well as the quality of the bounds, and the presentation of the results -- please see the detailed review (and the discussions). While some of the concerns were addressed, some others still remained. In particular, the reviewers are unable to certify the correctness of some of the main results of the paper. I appreciate the authors responses and revisions. However, I recommend that the authors revise the proofs and make sure that everything is clearly explained with proper details. I am confident that, after all the reviewers comments are addressed in a revised version, the paper would be a very interesting contribution to the literature of Federated Learning and Langevin dynamics.  

justification_for_why_not_higher_score: Two of the reviewers are in favor of rejecting the paper. 
justification_for_why_not_lower_score: -
Decision: Reject