Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposed two shuffling based stochastic optimization methods, ProxRR and FedRR. ProxRR is the proximal version of SGD with shuffling, and they prove that ProxRR achieves better convergence rate than vanilla proximal SGD on strongly convex function, similar to its counterpart SGD with shuffling. Another advantage of this paper is that their convergence results do not need bounded gradient assumption, which was needed in the several prior shuffling SGD papers. In FedRR algorithm, each client uses SGD without replacement to optimize the local model, instead of vanilla SGD employed in local SGD. They also have analysis of FedRR for convex and nonconvex functions under both homogeneous and heterogeneous settings, and the convergence rates are faster than local SGD. The experiments also show the faster convergence of shuffling based algorithms.

main_review: As far as I know, this paper is the first to analyze the convergence of proximal SGD without replacement, and it is also the first to introduce shuffling ideas into federated optimization. The theoretical analysis is sound to me. The experiments also support their theory. The paper is well-written and both experimental and theoretical results are clearly presented. This paper introduces shuffled local updates in local SGD, which is a well-known idea to speedup SGD in the traditional optimization community. As the authors showed in the paper, this idea does improve the convergence rate of vanilla local SGD, and the experiments also support that. 
limitations_and_societal_impact: 1. For ProxRR, I am curious about the comparison with the literature of shuffling SGD. Particularly, [1] gives a lower bound $O(n/T^2)$, so can we choose the learning rate carefully such that we can match with this lower bound? 

2.  It is a decent algorithm and it does provably improve local SGD. My minor concern is that FedRR is a simple combination of local SGD and SGD without replacement. It would be great if we can apply the shuffling idea on client level as well, e.g., for model averaging stage, server does not randomly sample a subset of clients to do the average, instead it shuffles the clients and selects subsets without replacement. It makes the algorithm look more tailored for federated learning. 

[1] Rajput, Shashank, Anant Gupta, and Dimitris Papailiopoulos. "Closing the convergence gap of SGD without replacement." International Conference on Machine Learning. PMLR, 2020.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the authors propose two new algorithms for finite sum minimization: Proximal Random Reshuffling (ProxRR) and Federated Random Reshuffling (FedRR). ProxRR is used to solve composite functions, while FedRR is a special case of ProxRR as used in the context of federated optimization. They provide convergence rates under various convexity assumptions, and they also show convergence to small gradient norm (in expectation) for smooth non-convex objectives.
main_review: In extending random reshuffling methods to composite optimization, the authors observe the importance of only applying the proximal operator once every epoch of random reshuffling, rather than at the end of each step. Thus, their algorithm only evaluates the proximal operator a single time during each pass of the data. They go on to show that their results apply to the setting of Shuffle-Once, which was also considered (alongside random reshuffling) in Mishchenko et al. (2020). The authors also provide promising experiments in the federated setting. 

That said, the results of this paper, particularly in handling the random reshuffling difficulties, are somewhat of an incremental extension when compared to Mishchenko et al. (2020). It would be recommended that the authors better elaborate in what ways their results go beyond simply combining Mishchenko et al. (2020) with the standard prox analysis.


==== Minor comments ====

The authors should refer to, and compare with, the method FedAc [1].

Line 263: The equation is overlapping the text.

The authors note there is no tuning for the ProxRR vs SGD experiments (though tuning here would be *strongly* recommended), but what about for the federated optimization experiments? Please elaborate.


[1] Honglin Yuan, and Tengyu Ma. "Federated Accelerated Stochastic Gradient Descent." In NeurIPS. 2020.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper first proposes a proximal variant of the gradient method with shuffling strategy for a class of composite finite-sum minimization problems, and then specifies it for an optimization problem in federated learning (FL). In fact, the proposed algorithm performs n gradient descent updates per epoch and then applies the proximal operator at the end of each epoch. Both single shuffling and randomized reshuffling strategies can be used. The authors analyze the convergence rates of this algorithm under the strong convexity of the losses and the strong convexity of the regularizer. Next, they apply the proposed algorithm to FL, with and without regularizer. This variant is similar to FedAvg, but it replaces SGD by a shuffling gradient scheme for local updates. They establish the convergence of this variant for both the strongly convex case (where the regularizer is strongly convex) and the non-convex case in both heterogeneity and homogeneity settings, respectively. Numerical experiments are conducted to illustrate the algorithm and compare it with two existing methods: local SGD and SCAFFOLD. 
main_review: Originality: The first part of this paper extends the results in [Mishchenko et al, 2020] to the composite setting. The convergence results are very similar to those in this work. The use of proximal operator at the end of each epoch makes sense since the convergence guarantee will be in epoch, and it is independent of the shuffling strategy. This is perhaps one of the main contributions. Algorithm 3 is very similar to FedAvg by replacing a classical SGD update with a shuffling gradient scheme. In this algorithm, I do not see where the proximal operator of R comes in. I believe that it should be placed after line 8. Overall, the originality of this paper is moderate. Except for adding a new proximal step, the results are very similar to [Mishchenko et al, 2020]. In fact, [Mishchenko et al, 2020] essentially extends and improves [Nguyen et al 2020] to randomized reshuffling variants.

Quality/clarity: The paper is well written and well-motivated in general. The extension to composite form is nontrivial as they have discussed. However, I have a feeling that the analysis for the strongly convex case is not much different from [Mishchenko et al, 2020]. Therefore, the quality of the paper is moderate. 
 
Significance: Overall, the paper has considerable contributions in terms of new algorithms, especially Algorithm 1, and the theoretical results associated with both Algorithms 1 and 3. But as mentioned above, due to the similarity of this paper and [Mishchenko et al, 2020], its significance is weak. 

Below are some additional comments:

-- The authors only consider the strongly convex case for Algorithm 1, but not the convex and nonconvex cases. Why are the two latter cases not considered? Is the latter case a special case of Theorem 5?

-- In Theorem 2, how can one estimate or upper bound sigma_rad to form a learning rate? In Theorem 1, its upper bound depends on x*? I believe that this is for theoretical guarantee, but it seems to be very small since it depends on both sigma_rad and epsilon (a desired accuracy). Could you please comment on this aspect?

-- Is there any difference in terms of convergence if either the regularizer is strongly convex or at least one loss is strongly convex?

-- Is Theorem 4 a special case of Theorem 3?

-- In terms of analysis, what is the essential difference between [Mishchenko et al, 2020] and this paper when a regularizer is added?
Without a regularizer, does this analysis reduce to [Mishchenko et al, 2020] or other previous works?

-- The proof of Lemma 7 is unclear to me, making me unable to verify Algorithm 3. Could you please add more details to clarify its proof?

-- In Supp. Doc. the authors present the convergence for diminishing learning rates, when t > t_0 ~=T/2. Can you use diminishing learning rate from t=1? If so, then how does the convergence rate in Theorem 9 change?

limitations_and_societal_impact: Not discussed. 

--- I would suggest the authors to compare also single shuffling (like incremental) and randomized reshuffling in Supp. Doc.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a proximal extension of random reshuffling algorithm, namely ProxRR for finite-sum composite optimization. ProxRR requires only one proximal steps per round, which reduces the complexities incurred by costly proximal operators. This paper also studies a federated version of ProxRR, namely FedRR, and proved theoretical advantages over Local SGD.
main_review: I would like to express my appreciation for your submission to NeurIPS 2021. The paper is overall well-written and I enjoyed reading it. My concerns are as follows.

1. The ProxRR presented in this paper applies only one proximal step per epoch. This reduces the number of calls to proximal operators, but at the same time incurs additional complexities (say, in eq (6)). It is hard to calibrate the significance of ProxRR bound (6) with [1] or Proximal SGD (7) since there are two factors mixed in --- reshuffling and reduced proximal calls. Have you considered doing ablation study to separate these two factors? For example, how does “ProxRR with proximal at every step” work? Will it eliminate the additional term in (6)?

2. This work compares  FedRR with other smooth federated optimization algorithm such as FedAvg and SCAFFOLD. How does FedRR compare with other federated composite algorithms such as [2] (theoretically or empirically)? For example, for experiments presented in Fig. 2, how does FedRR compare with FedDualAvg [2] if $\lambda_1 \neq 0$?

[1] Random Reshufﬂing: Simple Analysis with Vast Improvements, NeurIPS 2020.
[2] Federated Composite Optimization, ICML 2021.

limitations_and_societal_impact: See main review for limitations.
review_title: null

Meta-review: After all reviews, responses, and discussions, there is general agreement that the paper is clear and well motivated on its own, but that its main contributions in relation to previous work appear limited as currently presented. The concerns about improvements on prior work took several forms, with the most common being that the extension above Mishchenko et al. (2020) seemed incremental. The discussion clarified a few finer details about this, but in the end did not address the basic concerns of multiple expert reviewers, even considering the nonconvex analysis.

There was discussion on a minor point between Reviewer Gcuo and the authors about tuning step-sizes in experiments. I understand that step-sizes from analysis are used on purpose in order to simulate the theory. Although tuning these would be a different experiment, it could be a related interesting one. Regardless, I did not read this as the main point of that review and would not consider it a serious issue affecting the overall recommendation. It is clear that this paper focuses on theory.
Decision: Reject