Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper claims to give a general DP framework for decentralized data. The authors claim that the algorithm retains all the desirable properties that we have in non-private setting: generalization or stability and finite sample performance. 
strength_and_weaknesses: The main idea in this paper seems to be to use the private version of stochastic D-KM algorithm. The paper analyzes its sensitivity and from there uses truncated generalized Gaussian mechanism for privacy. The paper claims privacy proof for truncated generalized Gaussian mechanism as well. I believe this can be casted as one of the novel contribution of the paper, too. 
clarity,_quality,_novelty_and_reproducibility: I believe the privacy proof for truncated generalized Gaussian is a novel contribution. For the rest of the contribution, it seems to me as more like following the familiar route of privatizing a known non-private algorithm.
summary_of_the_review: I was unable to read the proofs of the main claim, so I cannot make a judgement of their correctness. For now, I would rely that the authors have done their paper in writing the correct proof. 

I have one central question. Ganesh and Zhao proved that generalized Gaussian is DP for all b \leq \log(k), where k is the number of queries (in their paper). The current submission makes similar statement but only for b=2. How is the proof different or anyhow technically novel considering the paper by Ganesh and Zhao (2020) and adapting their proof for truncated Gaussian just like Geng et al. did for truncated Laplacian? Am I missing something here? The authors have not cited Ganesh and Zhao, so I am wondering if the authors are aware of the paper. 

Second, the authors claim that they present their result for equal sample size for the ease of presentation. Is it just for the ease of presentation or is it the case that the analysis only goes through when sample sizes are equal. I would imagine that if the sample size comes from a very skewed distribution, then we should not be able to say anything meaningful about the generalization error. 

Why do we call the mean parameter vector a consensus vector? Is it common in this literature?

What is $\lambda$? I am guessing it is the rate of the convergence to the stationary distribution.

What is the notation $\| \ell \|_\infty$?

Theorem 5: What is $C_{KL}$ and is other $\widetilde X(i)$ defined similarly to $\widetilde X(1)$? Theorem statement should be precise and complete on their own. 

The notation $\mathbb P$ is overloaded. 

Disclaimer: I am trying to read the proof. I hope to be able to engage with the authors much more during the discussion phase. My current scores are for placeholder. 




[1] Ganesh and Zhao. https://arxiv.org/abs/2010.01457
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper develops a new differentially private (DP) framework to tackle the problem of decentralised consensus learning. This framework is based on the stochastic Decentralised Krasnosel'skii-Mann (D-KM) iteration (its privatised version referred to as "DP-KM" in this paper). It provides both theoretical and empirical results for their approach.
strength_and_weaknesses: Strength:
1. A new private framework is provided to deal with this problem that utilises generalised versions of distributions, like Laplace and Gaussian. There is mathematical rigour in this paper, which I appreciate.

Weaknesses:
1. One major complaint I have is about the writing quality of this paper. It pretty much makes it impossible for me to evaluate its significance and quality. I'll describe more in the next section.
2. I don't completely understand the objective or the motivation of this paper, to be honest. What assumptions are being made/removed about the loss functions, and why is this framework stronger and more general-purpose than in the prior work we have seen so far? What is it trying to improve on -- what is the prior work here? What are the baseline (trivial or non-trivial) approaches I could compare this work with? This point does tie in with the previous point I made here.
3. Theoretical comparisons with some prior work could have given more context.
clarity,_quality,_novelty_and_reproducibility: I have a number of issues with the writing/clarity of this paper.
1. The major one -- the graphs are impossible to read and interpret because of the font and the size. How am I supposed to see anything here? Am I supposed to zoom in and squint to see what is going on in there by looking at blurred images and text? This will sound harsh, but I really am not willing to do that because I feel that it is the responsibility of the authors to convince the reviewer about the quality of their work. The text in Section 6 is not enough for me to be able to justify what you obtained in those plots either. Where is the discussion on your experimental results? I would recommend by starting off by improving this section to be able to actually convey what you achieved through this algorithmic framework.
2. More context of this high-level problem of decentralised consensus learning would be more useful to differentiate with other versions of distributed learning. As a reader, I would want to understand your contributions in terms of the problem being solved first. Yes, there is a section on the problem statement, but it's not really sufficient to distinguish from the other well-known versions of the problems under the same umbrella.
3. How are the assumptions you make about the loss function (or anything else) different from those in the prior work? My understanding was that this work was also supposed to weaken those, and obtain more a general framework.
4. Around Definition 2, it might be helpful to provide more context on this D-KM algorithm. The concepts and the ideas seem to be coming out of thin air right now. For example, what is the high-level idea of the bigger algorithm that uses this iterate? What algorithmic techniques are relevant for this particular design?
5. Also, is improving on the communication complexity one of the main highlights of this approach? The end of page 4 vaguely has a comment of this nature. If so, then how does it compare with that of the relevant prior work?
6. In Theorem 1, why just bound the expected sensitivity? How does this translate to a bound on the worst-case sensitivity? More context here would help! Also, the second summation should have $K$, instead of $k$.
7. The results and the settings are stated in very confusing ways, for example, in Theorem 5. I think the authors could do a better job of providing more context behind what the results are about and what they actually say. It's pretty hard to interpret the results the way they are right now.
8. The previous point brings me to my next complaint that the organisation and the flow of this paper are a bit confusing and haphazard. Sure, the order of the sections makes complete sense, but the ordering within them didn't feel as friendly. For example, the $\Delta_K$ sensitivity in Section 4 is defined, but its theorem is about its expected value, and then there is a table below about that for different graph topologies. What is the context here? Why do these graph topologies matter in particular? How are these three things connected? This was just one example. This may sound a bit vague, but the flow seems a bit jittery right now, in general, and maybe another iteration of revising it maybe helpful for future.
9. Some additional results about these generalised distributions (Laplace and Gaussian) could be more meaningful. For example, the privacy guarantees in terms of the extra parameters, or some tail-bounds. They don't add much value here in terms of clarity otherwise because I don't really know how they are useful for your DP framework.
10. Some theoretical comparisons with prior work could be useful.

In terms of the quality and the novelty, I don't really have much to say. I'm not very convinced about either of those because this paper wasn't really friendly to read or interpret.
summary_of_the_review: I don't think I got enough information from this paper to be able to provide a convincing argument in favour of accepting it. I hope my suggestions/comments on the writing help the authors.

Update: I appreciate and respect the authors' willingness to make all the suggested edits to improve the readability. However, I see that a *very significant* portion of the paper had to be rewritten in order to introduce more clarity, so I am hesitant to change my score. The readability has improved a lot, but I think the authors might benefit from spending some more time on the presentation of the paper, and providing a more convincing argument about the problem and the technical challenges and novelty.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a general DP decentralized learning framework based on stochastic Decentralized Krasnosel’skiˇı–Mann (D-KM) iteration, which can represent the common first-order algorithms, like SGD, SPGD, and ADMM. Also, based on previous truncated Laplace mechanism, they proposed a truncated generalized Gaussian mechanism. 
strength_and_weaknesses: Strength:
1. Achieving privacy in decentralized learning is interesting and important.
2. The paper gives general framework based on D-KM iteration. 
3. Proposed a truncated generalized Gaussian mechanism with higher utility. 

Weakness:
1. Lots of decentralized learning with DP works are not considered.  Please check the corresponding works in 
Li, Zhize, Haoyu Zhao, Boyue Li, and Yuejie Chi. "SoteriaFL: A unified framework for private federated learning with communication compression." arXiv preprint arXiv:2206.09888 (2022).
2. Please provide the experiments comparisons with previous works. For example, In Figure 4, please compare the proposed methods with previous DP-ADMM algorithms to show the effectiveness.  The same things for Figure 2 and 3. 
3. The motivation for proposing truncated generalized Gaussian mechanism is not clear. Instead of the advantage of $l_2$ sensitivity, what is the advantage of truncated generalized Gaussian when compared with Laplace noise? Also, here is a work also proposed truncated Gaussian mechanism. [1] Cesar, Mark, and Ryan Rogers. "Bounding, concentrating, and truncating: Unifying privacy loss composition for data analytics." In Algorithmic Learning Theory, pp. 421-457. PMLR, 2021.
4. Please also provide the generalization and optimization error bound with previous DP-SGD, DP-SPGD and DP-ADMM. 
5. Please provide more experiments over large datasets and neural networks models. 
clarity,_quality,_novelty_and_reproducibility: The novelty of this paper is limited, which directly adds noise to the stochastic Decentralized Krasnosel’skiˇı–Mann (D-KM) iteration. 
summary_of_the_review: Based on the weaknesses in previous part, the paper needs more concrete comparisons with previous works from theoretical and experiments and insights.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper provides a differential private learning framework for consensus learning over networks. Some theoretical results are established for the proposed algorithms. Several numerical studies are demonstrated.
strength_and_weaknesses: Strength:
The targeted problem is interesting. This paper is easy to follow.

Weakness:
1. Differential private decentralized learning has been widely studied. The work aims to provide a general framework by simply combining SGD and SPGD algorithms. The contribution seems to be incremental.
2. In terms of the theoretical study, can the authors provide a detailed analysis of optimization error with differential private mechanisms? What are the convergence rates of the algorithms with SGD, and SPGD, respectively? 
3. We would expect a more comprehensive experimental study. For example, the current experiments only focus on least square regressions with/without l1 regularized term. Can the proposed algorithm apply to classification problems such as logistic regression? What is the effect of the proposed algorithms under different privacy levels (epsilon, delta)? 
4. Also, the proposed algorithm involves some parameters. The authors should provide a sensitive study on these parameters.
5. The text in the figures is too small.
6. How about the support recovery of the regularized least square regression with an l1 penalty with a noise-adding mechanism? It seems that the noise-adding ruins the spare structure easily. Can the authors provide an analysis of the noise-adding mechanism on structure recovery in addition to generalization error?
7. In Theorem 5, what is the sequence {a_m}? It makes delta^{\prime} different.
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is well organized but the presentation has minor details that could be improved.

Quality: The paper has minor technical flaws. For example, the proof of a theorem has some fixable errors or the experimental evaluation is weak. 

Novelty: The paper contributes some new ideas or represents incremental advances.
summary_of_the_review: This paper provides a differential private learning framework for decentralized learning. However, the contribution seems to be incremental.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes a framework for differentially private (DP) learning for decentralized data based on stochastic Decentralized Krasnosel'skii-Mann iterative method. The central claim is that the proposed algorithm retains the performance guarantees in the non-private setting. 

This work aims at developing algorithms for decentralized learning with provable privacy guarantees, which is an important research problem. The privacy guarantee is based on a truncated version of the generalized Gaussian mechanism. The mechanism is a tweaked version of an existing method.

The work appears to be mostly incremental compared to prior work and has limited conceptual and algorithmic novelty. The privacy analysis is largely similar to those in prior works (e.g., [Geng et al. 2018], [Ganesh & Zhao 2021], and [Cesar & Rogers 2021]) as pointed out by two reviewers. The authors claim that the analysis is different but the differences they claim appear to be simple tweaks. Also, the improvement in the guarantee on the added noise is not very significant. 

Moreover, there are major concerns about the presentation and writing quality, which make the reader unable to follow the claims and assess their significance. This seems to apply to the formal statements, proofs, and also the experimental results. 

The paper could also benefit from a more detailed discussion of related work on decentralized learning/optimization with DP including earlier works on locally DP learning. 
justification_for_why_not_higher_score: The work is incremental with limited algorithmic novelty.
Decision: Reject