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 paper studies convergence of a previously proposed algorithm called FedProx. FedProx has been fairly popular in the FL community but its analysis is pointed out to depend on unrealistic assumptions, namely, on bounded local gradient dissimilarity assumption. In this work, the authors propose an analysis that doesn't need this assumption. Moreover, they also study convergence of FedProx when the objective is non-smooth. Finally, they propose a variant of FedProx called FedMSPP, which uses proximal-point update in its inner loop. They prove convergence of FedMSPP and provide some numerical results for this method in the Appendix.

# After rebuttal
I decided to increase the score from 3 to 6 since the technical issue has been fixed (I also increased "Soundness" rating from 1 to 3). I still think that a more interesting story could be presented, with at least some result saying why FedProx would be a good method.
strengths_and_weaknesses: ## Strengths
1. The idea to study FedProx without bounded dissimilarity makes perfect sense to me. The method is quite popular in FL, where bounded dissimilarity is not always a reasonable assumption since clients data can be very heterogeneous.
2. The obtained complexities look good compared to that of other methods (see Table 1). The theory covers partial participation and shows improvement in terms of client batch size in case of smooth functions. 
3. The work is well-written and the main contributions and ideas are stated clearly.

## Weaknesses
1. I do not understand one step in the proof of Lemma 5 (see "Questions" section of my review). This seems to be of fundamental importance, so if my question is not addressed, I would vote for rejection of the paper. On the other hand, if I miss something, I will be willing to drastically change the assigned score.
2. As far as I can see, there is no improvement from performing more than a single local step. This is a common issue with FL methods, but it is still disappointing.
questions: ### Main questions
1. The proof of Lemma 5 seems to use $L$-smoothness of $Q_{\mathrm{erm}}^{(m)}$ (when the gradient norm is upper bounded by functional gap). However, $Q_{\mathrm{erm}}^{(m)}(w; w_{t-1})=R_{\mathrm{erm}}^{(m)}(w) + \frac{1}{2\eta_t}\Vert w-w_{t-1}\Vert^2$ seems to be ($L+\frac{1}{\eta_t}$)-smooth. For small $\eta_t$, this seems to make a big difference. As far as I can see, this may change the result of Lemma 5 to have a constant error, in which case the theory might break down.
2. Could the authors comment on why FedProx would be better than simply computing a single gradient $\nabla R_{\mathrm{erm}}^{(\xi)}(w)$ on each client $\xi\in I_t$? At least in the smooth case, it seems to me that there is no benefit from computing the prox. I think it makes sense to at least mention this in the "Limitations" section.
3. The proof of Lemma 4 is problematic. First of all, you take expectation with respect to sampling $I_t$, but then you write that
$\mathbb{E}\left[\frac{1}{|I_t|}\sum_{\xi\in I_t}d_t^{(\xi)} \right] = \frac{1}{|I_t|}\sum_{\xi\in I_t}\mathbb{E}\left[d_t^{(\xi)} \right].$
The problem here is that $I_t$ is stochastic so you cannot put it outisde expectation. The claim itself is correct, so this is just a minor comment.  
You also say that "By uniform without-replacement sampling strategy", but then you rely "the independence among the indices in $I_t$". The issue here is that sampling without replacement does not give independent indices. This can be easily fixed, for instance, see Lemma 1 in "Random Reshuffling: Simple Analysis with Vast Improvements" for the derivation of variance. Alternatively, you can just assume uniform sampling (which would probably make less sense since we talk about client sampling).

### Typos:  
Page 2: partial participants (participation) of devices  
Page 5, Table 1: functions. The involved of quantities (should be no "of")  
Page 9: At nutshell (in a nutshell)  
Page 9: weak convex (weakly convex)  
Page 16, line 561: (Proof) of Theorem 1. "Proof" is also missing on page 18, line 592; page 23, line 657; page 25, line 682.
limitations: The limitations were discussed well. I would be also interested in seeing a discussion on the utility of computing prox instead of computing gradients.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors study FedProx with an improved convergence analysis without the unrealistic assumption of local gradient dissimilarity. Instead, they introduce a novel local dissimilarity invariant convergence theory for FedProx. FedProx for nonsmooth optimization and its minibatch stochastic extension are also studied with convergence guarantees and complexity bounds. 

strengths_and_weaknesses: Strengths: 
- This work gets rid of the usual yet unrealistic assumption of local gradient dissimilarity in the original analysis of FedProx
- Both *smooth and nonconvex* and *nonsmooth and weakly convex* cases are studied with convergence rates 
- Minibatch stochastic extension of FedProx is also studied with convergence guarantees, which also enjoys linear speedup in terms of minibatch size and partial participation ratio 

Weaknesses: 
- Experimental results could be preliminary 
questions: - Typos: 
	- Line 244: independent to → independent of
limitations: The authors have adequately addressed the limitations of their work.
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 studies the FedProx algorithm for nonconvex optimization. FedProx is a distributed version of the stochastic proximal point method that has found many applications in practice, and which generally seems to perform well in practice. FedProx was introduced and analyzed in [1], but the convergence rate given in [1] depends on a highly non-standard assumption, the strong growth condition, which this paper terms the (B, 0)-LGD assumption. The aim of this paper is to study the convergence of FedProx without this assumption; instead using the more-common assumption that each objective is Lipschitz. The authors give a convergence rate for smooth objectives (Theorem 1) that does not depend on the (B, 0)-LGD assumption, and a similar rate for non-smooth but weakly convex problems (Theorem 2)-- in addition, they develop minibatch variants of the algorithm and give convergence rates for it in Theorem 3 (smooth) and Theorem 4 (non-smooth).

[1] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, Virginia Smith. Federated Optimization in Heterogeneous Networks, mlsys.org (2020).

strengths_and_weaknesses: Main points:
- The convergence rate given by Theorem 1 is a welcome improvement upon the prior convergence result given in [1], as it does not require the (B, 0) condition and thus can be used in more general circumstances. On the other hand, this is quite limited by the alternative assumption used: the requirement that each function is Lipschitz itself is a control on the gradient dissimilarity, and does not allow the rate to show improvement with lower function dissimilarity.
- The rate for non-smooth objectives given in Theorem 2 is also novel and interesting in its own right, as it adds to the arsenal of algorithms that are analyzed in the setting of nonconvex but weakly convex objectives. While the authors state that it is the first convergence rate for FL algorithms, the rate given by [2] for SGD can be easily applied to federated learning, by seeing the sampling of stochastic gradients as sampling clients.
- The minibatch variants of the method are a nice addition, even though Theorem 4 does not show that minibatching results in any improvement for the algorithm under non-smoothness.
- None of the rates is asymptotically better than ordinary distributed SGD. This is quite puzzling, as FedProx requires a much stronger computational oracle and seems to perform well in practice. However, this could be inherent to the algorithm, rather than a product of a bad analysis. Without a lower bound for FedProx, we can not tell.
- The novelty of the proof for non-smooth problems is quite limited, especially since the proof shows no benefit from minibatching-- it follows the same outline as in [2].

I believe that this paper improves over the existing analysis and is a good addition to the literature, despite the rate itself not being very good compared to the baseline SGD. While it relaxes the (B, 0) condition required in [1], it also adds the Lipschitz condition that is more restrictive compared to prior work. So while this paper has some good, it is also more restrictive in other parts.

[1] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, Virginia Smith. Federated Optimization in Heterogeneous Networks, mlsys.org (2020).
[2] Damek Davis, Dmitriy Drusvyatskiy Stochastic Model-Based Minimization of Weakly Convex Functions, arXiv:1803.06523 (2018).

questions: - Can your analysis be extended to use bounded variance, rather than the assumption that each function is Lipschitz?

limitations: See the previous sections for limitations. Potential negative societal impacts are not applicable here.
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 is theoretical paper and it aims to study the convergence analysis of FedProx. The difference in this paper compared to existing works is that it does not assume the constraints on local dissimilarity, smoothness and the size of minibach. The novelty is to use algorithm stability theory to perform the analysis. In addition, the authors also provide a FedMSPP algorithm that is a minibatch stochastic extension of FedProx and perform its convergence analysis. 
strengths_and_weaknesses: Strengths: 

1. The authors claim that their theory is the first time local dissimilarity and smoothness are not necessary to guarantee the convergence of FedProx with reasonbale rates. 

2. The authors propose FedMSPP algorithm and perform its convergence analysis. 

Weaknesses:

1. The main novelty of this paper is a new analysis method without assuming local dissimilarity and smoothness. However, the authors failed to clearly explain the details of this novelty. 

2. The obtained convergence rates can be loose. For example, in Theorem 2, the convergence rate is not a function of I, which seems not make sense. In Theorem 4, the convergence rate is not a function of I and d, which also seems not make sense. 
questions: 1. In Theorem 1, is the result obtained by assuming 1 data sample point used per iteration? 

2. What is the real novelty in terms of analysis, please indicate the key step that is different from the approach used in the literature?

3. In Theorems 1 and 2,, what is the reason to use t* instead of averaging all the terms? 


limitations: The convergence rate can be loose. First, it can be worse than what was given in the literature. The authors used a few times that the obtained convergence rate is comparable with those in the literature. It is unclear this is because of the mathematical tools used in this paper or this is the result of relaxing the assumption on the local dissimilarity and/or smoothness. Second, as mentioned before, Theorems 2 and 4 can be very loose since it is not a function of I and/or d (the authors also mentioned this in the end of the paper). If the results are too loose, the contribution of this paper may be weakened.
review_title: null

Meta-review: metareview: The reviewers generally agreed that the work makes a contribution towards weakening the assumptions when analyzing the well-known FedProx method. However, I strongly agree with one of the reviewers' comment that it is not satisfactory to justify an assumption (here, it is the bounded gradient) just by stating that it is common in the literature. It would be desirable, e.g., to give application scenarios that satisfy the assumption and explain the limitations/implications of the assumption. Please consider addressing this in your revision.
confidence: Certain
Decision: Accept