Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes two variants of stochastic gradient algorithms without replacement. For smooth functions satisfying the PŁ condition, the authors showed that the proposed shuffling-based variants converge faster than their with-replacement counterparts (for the case with large number of epochs). Moreover, the authors showed that their provided convergence analysis is tight for the case with not large number of epochs. 
main_review: The majority of the manuscript is well-written and easy to understand. This paper is solely theoretical with promising guarantees. The authors showed that if $K \geq c_2\kappa$ where $c_2>0$ and $\kappa = \dfrac{L}{\mu}$, then their convergence rates are faster that the with-replacement counterpart. However, for the ill-conditioned case, the number of epochs (theoretically) will be huge to satisfy the mentioned assumptions. 

It would be ideal if the authors could also provide some numerical results to demonstrate how well their proposed methods performs in practice.


summary_of_the_review: This paper provides some promising theoretical results for the variants of stochastic gradient algorithms without replacement.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work analyzes the convergence rate of local and mini-batch Random Reshuffling. For \mu-PL and smooth objectives, It provides high probability upper bounds, and matching expected lower bounds, and a special variant of the random reshuffling that outperforms the previous tight bounds with \sqrt{M} speed up in some regimes. 

main_review: Strength. 1. The analyzed problems have significant importance in practice and lack a thorough theoretical understanding yet. 2. The technical contribution for analyzing gradient sampling with dependence is original, the technique for bounding gradient noise in local RR is involved and interesting. 3. The provided bounds are tight in some sense and variants with better performance (linear speedup) are analyzed. 4. The lower bound for mini batch RR in small-epoch regime is informative in that it concludes the weakness of mini batch RR for K \lesssim \kappa.

Some other points. 1. There exists a gap of \kappa^2 between upper bounds and lower bounds, which can be important given that \kappa itself is relevant in the considered regime. It may help to explain more on parameter dependence when claiming tightness. 2. The lower bounds and upper bounds are in different notions of convergence, it may help understanding if there are some explanations there. 3. In theorem 3, it might be useful to explain on the connections among c_1, c_2 and \kappa, does it affect the regime K \ge c_2 \kappa, if c_2 has dependence on \kappa given that c_1 has dependence on \kappa. 4. In theorem 4, it also assumes that K \ge MB/N, does it has influence on the followed discussions on the choice of B. It seems to me the cutoff between parameter regimes is not very clear, could you explain more on it, like, similarly, does c_4 has relationship with \kappa? 5. Although this is a theory paper, giving some experiments to validate the analysis especially for the discussions on different regimes would be appreciated. 

summary_of_the_review: I think this is a good paper with solid theoretical analysis and contribution, the analyzed problem is of great importance and needs more thorough understanding like this work.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies two popular algorithms: local SGD and minibatch SGD using the data shuffling technique, which means sampling without replacement. Authors provide analysis under PL condition and show that in some cases these methods with shuffling outperform classical local SGD and minibatch SGD. Additionally, this paper provides lower bounds for minibatch RR and local RR in homogeneous and heterogeneous settings. At the end of the paper, a new technique of using synchronized permutations is proposed. In an almost homogeneous setting, this approach can improve rates.
main_review: The paper presents a deep theoretical study of popular-in-practice methods that utilize shuffling of the data points. This paper has a good structure, all sections are well-written and fully described. All assumptions and statements of theorems are clear and understandable. 

However, assumption 2 is questionable:

Assumption 2 (Intra-machine deviation). There exists $\nu \geq 0$ such that for all $m \in[M]$ and $i \in[N]$,
$$
\left\|\nabla f_{i}^{m}(\boldsymbol{x})-\nabla F^{m}(\boldsymbol{x})\right\| \leq \nu, \text { for all } \boldsymbol{x} \in \mathbb{R}^{d}
$$ 

Does this assumption hold in practice? Is it not too strict to have a uniform bound for this difference? 

The theory is clear and it is easy to follow the proofs. The theoretical part is solid and the importance and novelty of obtained results are significant. Upper and lower bounds explain methods' behaviors in detail. These results should be interesting for the optimization community and the machine learning community in general. However, it might be useful to have a table with a comparison with rates of other methods for Federated Learning. Also, it is interesting to compare these results with results from https://arxiv.org/pdf/2102.06704.pdf. In this paper, local methods with shuffling are also considered. 

This paper does not have any experimental results. I understand that this work is theoretical, but simple and small experiments on toy models are desirable. It can be useful for readers to have graphical illustrations of methods' behavior. 

The synchronized shuffling method is not clearly described. The notation $\sigma_{k}^{m}(i):=\sigma\left(\left(i+\frac{N}{M} \pi(m)\right) \bmod N\right)$ is quite confusing. Can you explain why you shift the permutation that way?  Despite the main idea of this approach being understandable, some technical details are not easy to get. It might be useful to add some clarifications in this part. 




summary_of_the_review: This paper introduces a deep and wide theoretical study of permutation-based variants of local SGD and minibatch SGD. Authors provide upper bounds, as well as lower bounds, which makes the contribution solid. The novelty and tightness of results are significant, so the paper should be accepted. My grade is "accept, good paper".
review_title: null

Meta-review: This paper analyzes local SGD under the random reshuffling data selection setting. As is the case for standard random reshuffling, better rates are shown for local SGD when random reshuffling is used. This would already be a nice contribution to a line of work on random shuffling methods—but the paper goes beyond that by showing a matching lower bound and designing a (theoretically) better variant algorithm. The reviewers were all in agreement that this paper should be accepted (as a result not much further discussion happened after the original reviews), and I agree with this consensus. The modification seems to improve the paper, although I did not look through it in detail.
Decision: Accept (Oral)