Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This is an information theoretical paper that considers distributed machine learning problems. New upper bounds on the generalization error of distributed learning algorithms are derived and applied to distributed support vector machines. In particular, a very surprising result is that the generalization error of the distributed SVM decays faster than that of the centralized SVM with a factor of O(log(K)/sqrt(K)), where K is the number of groups the whole data set is distributed.

======================

After studying the authors' response, I am happy to see that the background on rate-distortion theory is added, and the typos I found are taken care of. For these updates, I am happy to raise my score to 6.
strengths_and_weaknesses: Strengths:
* solid theoretical analysis
* the results on distributed SVM are very surprising

Weaknesses:
* one of the key tools used throughout the paper, the function RD, is not defined clearly enough (see comments below in the "Questions" section), rendering the whole paper very difficult to follow.
* From bounds on the generalization error of some machine learning algorithm, readers could expect to quickly find out how the generalization error converges to zero (or not), as the training sample size tends to infinity, or while other variables are changing. However, in this paper, such reading is not easy. For example, in Theorem 2, the right-hand side of the bound contains Rp(delta, epsilon), which is defined in a highly complex way such that even telling whether this quantity would be O(1) is extremely difficult. Theorems 3 and 4 are similar.
* I am not sure if the claimed results are well supported.
questions: * Line 93, please clarify: is the output of Algorithm A random? That is, given exactly the same set of data and run A twice, would it be possible that A generates different output hypotheses (e.g., for the purpose of differential privacy etc.)? If not, how should we understand the conditional distribution P_{W|S} since it would then be a degenerated trivial distribution? If yes, would the author(s) provide more details on how the infimum between lines 116 and 117 is defined? Also, what is then the motivation of using a random algorithm in this paper?
* There seems to be one reference item missing in Line 147. Also, I think that the author(s) should declare that the distance d(w;w'|s) is not a distance in the mathematical sense since it lacks symmetry: d(w;w'|s) != d(w';w|s).
* Line 93, I guess that $\mathcal{W}\in\mathbb{R}^d$ should be $\mathcal{W}\subset\mathbb{R}^d$.
* Line 117: what is $\hat{\mathcal{W}}$?
* How is a Markov kernel defined?
* Line 138, is epsilon fixed or random?
* The assumption in Line 190 (sigma-subGaussian) is very difficult for me to follow. Is there any example of this (example that the assumption holds true, and also an example that the assumption is not true)?
* It seems that the function "gen(s,w)" not only depends on s and w, but also on the loss function, the distribution mu, and the sample size n. In particular, we see that in lines 117--118, the function "gen" depends on a new loss function $\hat{\ell}$ where it is emphasized that this may be different from $\ell$. Would it be possible that all the dependent elements be listed explicitly in different places where the function "gen" is used?
* Some long sentences need to be divided into shorter ones. For example the 4-line long sentence in Lines 107-110, the sentence in Lines 211-215, among others.
* In the definition of RD(Q,epsilon) between lines 116 and 117, what is the relation between $S$ and Q? What is the definition of $\hat{\mathcal{W}}$? How is Q deciding $\hat{W}$? What is the expectation taken with respect to? In particular, if the expectation is taken with respect to all the randomness, by definition E[gen(S,W)]=0, which is trivial. What is the role $W$ plays in the infimum? (See also my comments in the "Strengths And Weaknesses" section.)
* Equation (9), should [K] be [m]?
* how is the claim "the generalization error of the distributed setting decays faster than that of the centralized one with a factor of O(log(K)/sqrt(K))" supported by, e.g., Theorem 5?
limitations: There is no negative societal impact observed. The limitations focus on that we doubt if all the claimed results are well supported.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper examines the generalization error of distributed learning using rate-distortion theory and compares the theoretical results with existing information-theoretical generalization bounds. For implication, the theory justifies the advantage of distributed learning by showing that the generalization error of the DSVM decreases with the client number K and is smaller than that of the counterpart centralized learning algorithm.
strengths_and_weaknesses: **Strengths**
- The writing of the paper is good. The advantage of the technical approach adopted in this paper (i.e., the rate-distortion theory) is well discussed.
- As mentioned in the paper, previous results do not explicitly consider the structure of the distributed learning problem. The generalization bound derived in this paper is explicitly tailored for the considered distributed setting rather than a direct extension of the previous rate-distortion theoretic generalization bounds.
- The theory implies exciting and novel results: The generalization error of DSVM decreases with the client number K and is smaller than that of the counterpart centralized learning algorithm.

No major concerns. 
Minor issue
- Line 264-265 seem to be missing something.
questions: - What if the sub-Gaussian assumption is removed?
	- Some work [1] shows that the parameters' distribution is heavy-tailed in multiple settings.
- What is the advantage of rate-distortion bounds over other generalization bounds (e.g., bounds via algorithmic stability or PAC-Bayes theory), especially in the distributed setting? 
- How tight are the upper bounds derived in the paper? How big is $R_p$ in theorem 2 and theorem 3? Would $R_p$ be prohibitively large for deep complex models? 
- In real-world settings, a fundamental challenge is that data may not be i.i.d.  across the workers. However, the generalization theory of distributed learning algorithms is mainly based on the assumption that the data is i.i.d. over clients. Can the results in this paper be extended to **non-i.i.d.** settings?

Reference

[1] Gurbuzbalaban, M., Simsekli, U. &amp; Zhu, L.. (2021). The Heavy-Tail Phenomenon in SGD. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research.


limitations: No negative societal impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper uses tools from rate-distortion theory to establish new generalization error upper bounds for distributed learning algorithms. The bounds depend on the compressibility of each client’s algorithm while keeping other clients’ algorithms un-compressed and leveraging the fact that small changes in each local model change the aggregated model by a factor of only $1/K$, where $K$ is the number of independent clients. The bounds are then applied to the distributed support vector machines (SVM), suggesting that the generalization error of the distributed setting decays faster than that of the centralized one with a factor of $O(\sqrt{\log(K)/K})$.
strengths_and_weaknesses: This paper studies the generalization error of distributed learning algorithms using a novel tool of rate-distortion theoretic generalization bound developed by [SGRS22], which is sufficiently original. However, it is a bit unsatisfying to me that the results in this paper only tell us that the generalization error of a distributed algorithm is better than its centralized counterparts, but no more discussion on the computational and communication costs, and population risk. To my understanding, these aspects are the main reason to adopt distributed learning algorithms in practice instead of improving the generalization error.

The organization of the paper can be improved. I feel that some crucial contents are provided only in the Appendix, e.g., empirical validation, results of SGLD, and comparison with related prior art results. The proof details provided in Section 5 are not very informative (basically follows from [SGRS22] and [GKL 20]) and can be replaced by the additional results in Appendix.

questions: My biggest concern in the paper is comparing the generalization error between distributed and centralized settings. It is stated after Theorem 5 that in expectation bound for $K$ clients, each having $n$ data samples is smaller than that of the counterpart centralized learning algorithm that has $nK$ input data samples by a factor of order $O(\sqrt{\log(K)/K})$. However, [BDP22, Theorem 4] states that the improvement is of order $O(1/\sqrt{K})$, which is even better. Furthermore, it is shown in Appendix B.3.2 that the upper bounds of [BDP22, Theorems 4 & 5] can be recovered as special cases and are subsumed by Theorem 4 in this paper. Thus, I believe that more explanation on the comparisons is needed.

Minor comments:   
1.	In the abstract, it is said that “the generalization error of the distributed setting decays faster than that of the centralized one with a factor of $O(\log K/\sqrt{K})$.” I believe that it should be $O(\sqrt{\log(K)/K})$ as stated in Theorem 5.   
2.	There is a missing reference in Remark 1 on Line 147.

---------------------
Post rebuttal:
Thanks for the clarification about the comparison with [BDP22, Theorem 4]. I did not notice the difference in the assumptions. It is a good paper, and I would like to maintain my original rating.



limitations: I think the authors addressed the limitations and potential negative societal impact of their work.
review_title: null

Meta-review: metareview: The paper investigates generalization error bounds of distributed learning algorithms via rate-distortion theory, and compares the theoretical results with existing information-theoretical generalization bounds. An interesting implication of the authors' theory is the advantage of distributed learning with multiple clients as opposed to a centralized algorithm. This applies, in particular, to distributed SVM and distributed SGD, under some variance regimes. The paper strengthens the literature in several respects by removing or relaxing assumptions. 
All in all, an interesting piece of work that has improved during the discussion period. The authors are committed to re-organized their submission according to what they proposed during the discussion.


confidence: Certain
Decision: Accept