Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work proposes K-SAM as an alternative to SAM to improve algorithmic efficiency. The basic idea is to reduce the number of training samples used to approximate the stochastic gradients in both inner and outer optimization steps based on their loss values. This idea is originally proposed in Ordered-SGD, a biased stochastic optimization method. The authors argue that the proposed methodology can reduce the amount of computations by choosing K well without losing much on the generalization effect by the original SAM.

strength_and_weaknesses: Strength
* clarity; the main idea of the paper is described straightforward so K-SAM is read easily.

Weakness
* very limited novelty; this work naively applies the idea of Ordered-SGD to SAM, not more really.
* overclaiming based on shallow analysis; Figure 1 is clearly showing that the gradient estimate based on less number of samples gets more and more dissimilar to full mini-batch gradient, but the authors drive discussion into a direction where this result unfairly gives grounds for their proposed idea. This is an obvious trade-off between approximation accuracy and computational efficiency. 
* lack of theoretical grounds; the authors borrow some explanations from Ordered-SGD on the convergence analysis, but without any extension on mini-max as in the SAM setting.
* insufficient empirical evidence; the experiments do not show any significant improvements on both performance or efficiency, except for the expected trade-off.

clarity,_quality,_novelty_and_reproducibility: * This work directly applies the idea of Ordered-SGD or biased stochastic optimization in the context of sharpness aware minimization.
* There is no concern on reproducibility.

summary_of_the_review: Unfortunately this work does not provide non-trivial addition to algorithmic extension to the original SAM or empirical/theoretical evidence to support the realization of the proposed idea.

(after rebuttal) It is my regret that my concerns are not effectively addressed by the authors. I'm still not convinced that the paper is ready for publication.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors study the effectiveness of an iterative stochastic minimization algorithm for SAM (sharpness aware minimization): at each iteration the batch is further reduced in size using a Top-K rule based on the value of the loss. The goal of this choice is to reduce the computational expense, taking the cost closer to vanilla SGD while hopefully retaining the benefits of full-batch SAM. Extensive experiments show that the approach is feasible and it is possible to keep almost the same performance of SAM while reducing the computation time to a similar level to that of SGD.
strength_and_weaknesses: The main weakness of this work is that it lacks novelty and originality. The idea of choosing the top-k elements of the batch with highest loss is natural and has been explored before. In particular the work of Kawaguchi and Lu 2020 present the idea in its most generic form and the presented algorithm is almost a simple application of the generic method in the context of SAM. The only difference being that because SAM is a two-step process, one has to choose a subset of the batch both for the ascent step and the descent step. I wouldn't be surprised if there were even older references before 2020 exploring the exact same idea of Top-k elements in a batch. Authors should be more transparent about the fact that their algorithm is a special case of that presented in Kawaguchi and Lu 2020, applied to SAM (perhaps with some minor modifications).

Another weakness is that the authors overstate the computational cost of SAM compared to SGD. It is known that SAM has double the cost of vanilla SGD, but traditionally a constant factor (of 2 in this case) is not necessarily a reason to worry or discard a method as "too slow". This is reserved for methods whose complexity increases beyond constants. For example SGD which needs constant time to compute an update, vs GD which has linear complexity in the size of the data. In the third paragraph of the introduction statements like "the additional cost may make SAM too expensive for widespread adoption" are simply an exaggeration and should be rewritten.

Even though I started stating the weaknesses, I had a positive impression of the work, mainly due to the extensive experimental evaluation. In my view, the strengths of the paper are twofold:
1. The problem is relevant and significant to some extent: it is great to halve the time required to achieve the benefits of SAM
2. The extensive experimental results are convincing and confirm that it is indeed possible to apply Top-K in the context of SAM without a noticeable degradation of the results. The experiments presented cover many different settings like (a) different architectures (b) different and relevant baselines (c) different tasks like supervised learning with images and NLP tasks (d) different hyperparameter settings and (e) different computational infrastructure (single node vs distributed training). Overall I find the authors did a great job in this regard.
clarity,_quality,_novelty_and_reproducibility: 1. Clarity: The paper is well written and I found it easy to read and understand except for two items: (a) the second paragraph in the introduction is huge (contains too many unrelated observations) and should be split at least in two to facilitate reading and (b) the notation used in the definition of the batch subsets in section 3 was really confusing and it took me awhile to decipher what the authors mean with the $\{1. 2\}$ notation: they actually use it to define the two sets $M_{K_1}$ and $M_{K_2}$ in a single line. I think it would be better to simply use a notation like $M_{K_j} = \{ \ldots \}$, $j=1, 2$.

2. quality: I find the writing and mostly the experimental section of really high quality. As I mentioned above the experiments shine in this work and are extensive and convincing, supporting the main claims.

3. Novelty/Originality: As I mentioned above, this is the main weakness of the paper as it is a straightforward application of simple ideas that have already been presented in a more generic framework in the work of Kawaguchi and Lu 2020 and possibly many works before that.

4. Reproducibility: the authors provide the code to reproduce the experiments. However, I did not test the code.
summary_of_the_review: The authors present an application of Ordered SGD (Kawaguchi and Lu 2020) in the context of SAM, showing through extensive and convincing experimental evidence that it allows almost a halving of the training time, while retaining almost the same accuracy numbers from the vanilla SAM method. I don't see a strong reason to reject the paper. The lack of technical novelty might be compensated by the experimental evaluation. It might be useful for practitioners in need of halving the cost of performing SAM.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes to sample two subsets from each batch (choosing examples with the largest loss) to perform the SAM algorithm. The authors justify their method by showing the cosine similarity between the gradients obtained before and after the subsample process. Empirical results on CIFAR-10/100, ImageNet, and BERT finetuning show the effectiveness of the proposes method.
strength_and_weaknesses: ### Strengths
- Motivation of this paper is clear as SAM usually doubles the computational cost of SGD.

### Weaknesses
- How do you obtain the K1 and K2 example specifically? Do you just randomly choose from the K1+K2 examples that have the largest loss? Will their order affect the result? The authors should elaborate more on the algorithm.
- To me, it's surprising to see in Table 1 that just using top-K examples in SGD bring little performance drop. One possible reason is that the   batch size 128 used here is pretty small. Can the authors also provide analysis with a larger batch size.
- The reported training time shows that K-SAM can achieve speedup compared to SGD, while on ImageNet it's much slower. Can the authors provide metrics like FLOPs, which is not impacted by the hardware.
- It could be better if the authors can analyze whether we can save more compute in the ascent or the descent steps? Probably you can control the training time but vary the ratio of K1/K2. I assume that the ascent step can be performed with fewer example thus more savings.
- For the BERT finetuning result, the authors should include the variance as it's know to be pretty high.
- There are some other efficient SAM approaches that the authors can consider to compare with. For example, only performing SAM every k step[1], etc.

Liu et al. "Towards Efficient and Scalable Sharpness-Aware Minimization." CVPR 2022.
clarity,_quality,_novelty_and_reproducibility: ### Clarity
The writing is generally good. But it's not clear to me how to obtain the K1 and K2 example. Additionally, there are too many similar tables in the paper, the authors should consider merging / reorganizing them. 

### Novelty
The idea is simple and straightforward, and selecting the top-K hardest examples has a long history.

### Reproducibility
Code is provided so I assume that the reproducibility is good.
summary_of_the_review: This paper has limited novelty, and I've got some questions for the authors (refer to the weaknesses part). Empirical results is not strong enough to overcome the drawbacks. So I vote for rejection for now.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper investigates the application of the "top-k trick" known from SGD, where only the $k$ examples with the highest loss values are used in backward pass, to the sharpness-aware minimization (SAM) method. It shows via extensive experiments that this can reduce the computational cost of SAM to the level of vanilla SGD while maintaining the generalization-boosting effects of SAM.
strength_and_weaknesses: ### Strengths

1) The paper takes a highly relevant technique, SAM, and improves its computational efficiency. In my opinion that is commendable work with a direct positive impact on practitioners.

2) The paper is well-written. It does a good job of positioning itself in the context of existing work and summarizing the work it builds upon. Overall, the claims are scoped and phrased adequately.

3) The experimental comparison is well done. The selected benchmark problems offer a good amount of variety. The most relevant ablation/sensitivity studies (random examples instead of top-$k$, effect of $K_1$ and $K_2$) are included.


### Weaknesses

1) The paper is of limited originality. It combines the known optimization method SAM with the known (from vanilla SGD) speed-up method of selecting the examples with the top-k losses. Personally, I am fine with such a rather incremental paper, but it requires excellent execution.

2) My main criticism is that I sorely miss one baseline to compare against in the experiments: top-$K$-SGD (e.g. with $K=K_1+K_2$). The paper evaluates methods with regards to their trade-off between generalization and computational cost. For SAM, it uses the "top-$k$ trick", for SGD it does not. In my view, that is an incomplete picture. Assuming that top-$K$-SGD can maintain the generalization performance of SGD for reasonable values of $K$ it would naturally be the fastest method. This would make the claim of providing "significant generalization boosts over [...] SGD at little to no additional costs" rather vacuous. (Importantly, I don't think that would reduce the value of the paper. It is still worthwhile investigating the application of the top-k trick to SAM. But I _do_ think that this baseline is needed to give the full picture.)

3) The proposed methods computes the ranking based on the losses computed for the _ascent_ step and then uses that ranking for both the ascent and the descent step. In my view, the most straight-forward way of transferring the top-k trick from vanilla SGD to SAM would be to select the top-k examples _separately_ for the ascent step and the descent step. Since these loss values would be obtained at $w$ and $w+\varepsilon_\ast$, respectively, this could lead to slightly different results. Using the ranking from the ascent step might be a totally adequate strategy, but I think the first option should be mentioned/discussed in the paper and it would be nice to see an ablation study on that.


### Update after Rebuttal

Thank you for your response. I see now that Table 8 in the appendix contains numbers for top-K-SGD on ImageNet. (However, that is a _single_ experiment.) If we compare top-K-SGD with K-SAM such that $K=K_1 + K_2$ for (roughly) equal computational cost, the test performance achieved by the two methods is actually quite close. In any case, I think this is an absolutely crucial baseline to include for all experiments and contrast the results for K-SAM with. Therefore, unfortunately this doesn't resolve my concern outlined in the original review and I will keep my recommendation as is.
clarity,_quality,_novelty_and_reproducibility: ### Clarity

As stated above, the paper is well-written and adequately positioned in the context of related work. The proposed algorithm is described in full detail.

### Quality

The experimental comparison is very generally very well done, but I think one very important baseline is missing (see weakness 2).

### Originality

This is a rather incremental paper, applying the top-k trick, known to work on SGD, to SAM.
summary_of_the_review: This is a well-written paper providing a small but significant improvement to a relevant technique such as SAM and demonstrates that improvement in extensive experiments. In terms of originality and scientific value, this is certainly a very incremental paper. That, together with the missing baseline of top-$K$-SGD (weakness 2), puts this paper below the bar for a top conference such as ICLR.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper studies a timely and practically relevant research problem: how to reduce the computational cost of SAM algorithm, which has received a lot of attention recently due to its improved generalization performance. The paper proposes a simple and efficient approach for doing this. It builds on Ordered-SGD approach which selects a subset of K samples with the largest loss value. The authors have observed that such selection criterion can also be applied in the context of SAM (for both descent and ascent steps). This enables SAM to be used on larger scale problems with little performance degradation (although the authors have observed and hypothesize that the level of degradation might be sensitive to the number of classes).

The main concerns raised by reviewers were around novelty and lack of satisfactory baseline comparison. I do not personally believe that a combination of existing components (in this case SAM and Ordered-SGD), which was never tried before, is necessarily a weakness, as long as it comes with strong theoretical and/or empirical justification. The paper is in the empirical category, but reviewers feel that the empirical results in the paper need comparison with a greater set of baselines along the efficiency dimension of SAM. For example, Reviewer Y4Jo suggests including variance for language model results (due to the high variance of performance in these tasks) to ensure the reported numbers are not from a lucky run. In addition, Reviewer Y4Jo and T2UG request additional baselines to be compared against. Specifically, T2UG suggests top-K-SGD with K-SAM such that K=K1+K2 as an absolutely crucial baseline to include for all experiments and contrast the results for K-SAM, and Y4Jo suggests comparing against the work by Liu et al. "Towards Efficient and Scalable Sharpness-Aware Minimization." CVPR 2022.

All in all, I find this work very interesting with a great potential of having practical impact. However, with the current state of the paper and the current reviews, unfortunately the submission cannot be accepted. Yet, I truly do encourage the authors to strengthen their story by considering a broader set of baselines and resubmit their paper.
justification_for_why_not_higher_score: The overall ratings are on the reject side and mainly based on the valid criticism that the submission in its current state misses some crucial baselines to compare with.
Decision: Reject