On Memorization and Privacy Risks of Sharpness Aware Minimization

W1. The toy example in Section 3.1 is not convincing enough. In this case, it so happens that the atypical samples in red class are overlapping with blue class. What if the atypical samples are away from the blue class? Moreover, the generalization and memorization of SAM can be a result of several intertwined factors (e.g., low rankness [1]), this toy example might be oversimplified such that some of factors are ignored.

W2. The numerical results in Tables 1 and 2 seem to not fully align with the claim on privacy. For example, on CIFAR-10 and CIFAR-100 datasets, SAM itself is helpful for label-only attack. This might suggest that the memorization of SAM can be more complicated.

W3. The subgroup arguments in the introduction should be extended to elaborate more on the label noise experiment in SAM paper (Foret et al 2020). Because the label noise is randomly flipped in their experiments, typical and atypical samples are treated the same. And if SAM remembers the atypical data, does this suggest a dropping test accuracy (w.r.t. SGD) that is against the results in (Foret et al 2020)?

===== References =====

[1] https://arxiv.org/pdf/2305.16292.pdf

1. The paper has an incorrect claim in the contributions section. Namely, they mention they are the "first to empirically explore an explicit link between an optimization algorithm and privacy." This is completely incorrect and completely ignores the work of Differential Privacy. For example, Differentially Private Stochastic Gradient Descent is a well-known work that uses different optimization algorithms to achieve privacy (see "Stochastic gradient descent with differentially private updates"). Please remove this claim.
2. The related works completely miss all of the Differentially Private literature, which is very relevant. This needs to be added.
3. The notation is very difficult to understand and poorly done. I understand this paper borrows the notation from the Feldman paper, but a more detailed notation section is needed.
4. Why is $\mathcal{A}(D') = \mathcal{D} - (x_i, y_i)$, Do you mean set minus, i.e.$D' = \mathcal{D} \setminus \{(x_i, y_i)\}$. Moreover, isn't the output of $\mathcal{A}$ a classifier, not a data set? This line needs revisioning.
5. You should use operatorname for operation names such as $\operatorname{mem}$.
6. The first sentence of section 2.1 is not in format; it should be $f(x; \theta)$.
7. The color choices in Figure 1 are poor. It is difficult to tell apart the different reds and point types.
8. The explanation around equation 3 is confusing. I thought $\mathcal{I}$ is defined for the classes. However, you mention you sort test data points by $\mathcal{I}$. What is the $\mathcal{I}$ of a single datapoint?
9. One of my main questions is whether it seems that, more than anything, test accuracy and single query attack accuracy are highly correlated. The two most convincing points of evidence that SAM is correlated with less privacy are in Table 1. However, is it not just the case up to noise that the model with the higher test accuracy almost always has the highest single-query accuracy? Then, SAM, in this manner, causes an increase in single query attack accuracy because it has higher test accuracy. This seems pretty consistent across all experiments. Moreover, it seems that using SharpReg causes less attack accuracy since it decreases test accuracy. What is the correlation between test accuracy and single query accuracy, and is the effect of SAM on accuracy not caused only by this increase in test accuracy? In my opinion, this needs much more development and is lacking in the paper.
10. Moreover, Figure 3a is used to claim that SAM's improvements come from points that require more memorization. However, Figure 3a could also be interpreted as SAM increasing accuracy on points with lower default accuracy. Is the correlation with the memorization level or the difficulty of the data point itself? Figure 3a does not distinguish between the two, which is critical for your paper.
11. No theoretical analysis or even intuitive explanation is given as to why this effect could happen. This is crucial, in my opinion, since the fundamental explanation of why SAM hurts privacy is missing.
12. Existing papers have analyzed SAM and its connection to privacy already. Namely, the paper "Differentially Private Sharpness-Aware Training" analyzes how flatness can actually boost privacy gains, which is the opposite of the claim in the paper. This paper does not cite that paper and explain the differences in claims at all. Although it is a recent paper, this paper was accepted and presented much before this paper was submitted, so I expect an explanation of why the claims run opposite to each other.
13. The explanation of what SharpReg is needs to come earlier.

• Best results in all tables in the paper could be highlighted for more readability.

• Proposed entropy metric is computationally expensive to compute.

**** Additional Weaknesses ****

• There are some typos in important places as highlighted by other reviewers as well. In the memorization and influence score definition on Page 3, $h(x_i) - y_i$ should actually be $h(x_i) = y_i$ .

• Comparison of SharpReg with other privacy preserving methods is missing, also keeping in mind the influence metric proposed. Do other methods impact specific groups more ?

• The toy example presents an oversimplified picture of a real-world setting and does not help in getting intuition in the general case.

I feel this paper fails to "connect the dots" to tell a compelling story. The experiments suggest that SAM and SWA have higher accuracy on points that experience higher memorization, but, as far as I can tell, we see no clear evidence that the models more strongly memorize these points. Perhaps the algorithms do better on these points for some other reason?

The toy example highlights this shortcoming. We see a data distribution (built from subpopulations) where SAM outperforms vanilla SGD. The paper says that "the gain in generalization could potentially come from those atypical data subgroups." Why include such an example if it is not absolutely clear that the gains come from memorizing atypical data?

The paper also has serious presentation issues that made it difficult to understand and draw conclusions. For this and the above reason, I advocate for rejection.

Key presentation issues include the following.

• The entropy definition (Eq 3) appears to have a serious typo. It seems to depend only on the numbers of points in each class. Because of this, I could not interpret the (central) results relating memorization to accuracy. Related but less important issues include the overloaded index $i$ in Eq 3 and bucket numbering (the caption of Fig 2 says bucket 5 has high memorization, while Fig 3 seems to say the opposite).
• As mentioned above, I did not understand what conclusions to draw from the toy example.
• I sometimes had trouble understanding what conclusions to draw from the results. I think Contributions (Sec 1.1) and Conclusion and Future Work (Sec 6) reflect this issue: the only concrete takeaway I identify in them is that SAM may come with additional privacy risks.

Although it did not factor heavily in my decision, I believe the paper has a flawed discussion around "learning" and "memorization." The paper equates learning with compression (page 1) and talks about a spectrum with "perfect learning on one end and perfect memorization on the other" (page 2). However, recent work (Feldman 2020, who they cite, as well as [1] and [2]) highlights how memorization is compatible with learning. This should not be too surprising: the 1-nearest-neighbor classifier both learns and memorizes. These works go further, showing settings where memorization is actually required for accurate learning. Putting these concepts on opposite ends of a spectrum requires using nonstandard definitions.

[1] Brown, Gavin, et al. "When is memorization of irrelevant training data necessary for high-accuracy learning?." Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing. 2021.

[2] Cheng, Chen, John Duchi, and Rohith Kuditipudi. "Memorize to generalize: on the necessity of interpolation in high dimensional linear regression." Conference on Learning Theory. PMLR, 2022.

I would appreciate the authors clarify what they consider memorization is, and further justify the metrics used (influence score and membership inference attack accuracy). Specifically, is it possible that the conclusion about SAM and SWA have stronger memorization concerns due to inaccurate/inefficient metrics instead of the nature of the method? And also discuss the connection between memorization and privacy if possible. Better generalization leads to privacy risk is indeed counter intuitive, like the authors mentioned.

The proposed method SharpReg has different trade-off in generalization and memorization: worse test accuracy, but better membership inference attack performance. As the author noted, ShaprReg does not seem to be better than the other methods. And I am wondering if the authors have considered methods that can provide theoretical guarantees, such as differential privacy.