Neural Collapse meets Differential Privacy: Curious behaviors of NoisySGD with Near-Perfect Representation Learning

It appears that our main contribution may have been overlooked by the reviewer. We would like to highlight it once more and also address the reviewer's question as follows.

$\mathbf{Comments:}$ $M_k, k = 1,\cdots, K$ form an ETF frame, orm an ETF frame, which separate categories very well, the zero initialization makes $f_0(M_k) = 0$ , which is very weird.

$\mathbf{Response:}$ We would like to clarify that $0$ initialization is ubiquitous in training SGD or DP-SGD and we are not sure which part is weird. Even though, $f_0(M_k) = 0$ for all $k$, the training process will push the parameter to fit the the separate categories after iterations.

$\mathbf{Comments:}$ The one-step NoisyGD seems not useful at all.

$\mathbf{Response:}$ For perfect collapse, the fact that 1-iteration, full-batch GD suffices, and the fact that it is free of hyperparameters (any learning rate, any class imbalance, any dimension, any meaningful loss function) come at a surprise in a sense that — even such a much weaker and non-adaptive algorithm works.

In more realistic, imperfect collapse scenarios, our theory can be extended to multiple iterations. However, it is obvious that dimension dependency can not be mitigated using multi-iterations. Therefore, it is not clear why one-iteration NoisyGD would be deemed without merit.

$\mathbf{Comments:}$ I am not sure your results are for NoisySGD or NoisyGD. In introduction section, your statements are all about NoisySGD, but the other parts for NoisyGD. Moreover, there is no definition about NoisySGD at all in the whole paper.

$\mathbf{Response:}$ Our theoretical framework specifically addresses NoisyGD. In our experimental analysis, however, we assess the performance of both NoisyGD and NoisySGD. We appreciate the reviewer highlighting the omission of NoisySGD's definition, and we have now included it in Section 2.2.

$\mathbf{Comments:}$ The proofs are very simple.

$\mathbf {Response:}$ We agree that our analysis is simple, but in light of Point 1,2,3 in the official rebuttal above, we believe the simplicity of the analysis is a feature rather than a bug! After all, we believe the reviewer agree that our results are interesting and new.
To reiterate, we would like to highlight once more the contributions and novel findings of our study. Isn’t it better to have a simpler proof of a fundamental result than a highly technical (and harder to verify) proof?

1. It appears that our crucial observation--- that DP fine-tuning is non-robust to perturbations---was not acknowledged by the reviewer, a point we emphasized in Sections 3.2 and 3.3. The “Approximate Neural Collapse” case shows that the remarkable property is quite fragile if we train with standard DP-GD or DP-SGD. This actually led to various actionable algorithmic modifications to these private learning methods that make these methods substantially more robust — in theory and in practice!

2. In the perfect neural collapse case, our analysis also works perfectly for DP-SGD and it works for multiple iterations. As we stated above, many interesting facts come at a surprise in a sense that — even such a much weaker and non-adaptive algorithm works.

3. Existing analysis of DP-GD and DP-SGD focuses on suboptimality in the surrogate losses. The sample complexity is polynomial $d/\gamma$ or $d/ \sqrt{\gamma}$ (in the strongly convex case) to achieve $(1-\gamma)$-accuracy. We actually directly studied the ``0-1" loss! And we showed that the sample complexity is $\log(1/\gamma)$. This is an exponential improvement and shows an exponential benefit of strong representation learning.

$\mathbf{Questions:}$ How about $f_W(x) = Wx + b$?

$\mathbf {Response:}$ In the case of perfect collapse, incorporating an offset term $b$ is unnecessary. For binary classification problem with $\alpha$-class imbalance, straightforward computation reveals that the output of NoisyGD is given by $(n e_1,(1 - 2\alpha)) + \mathcal{N}(0,\sigma^2 I)$ where the $1 - 2\alpha$ component arises from the offset $b$ and the direction associated with $b$ is simply Gaussian noise. This noise could potentially detract from performance.

For a non-perfect collapse scenario, a similar computation indicates that an offset $b$ does not eliminate the perturbation. Consequently, the outcome retains its dimension-dependence.

Thank you for your valuable comments. It appears there may have been some misunderstandings in the review, potentially due to our failure to emphasize certain aspects within our original manuscript. We would like to address these points in the following response

$\mathbf{Weakness 1:}$ Typos: In theorem 2, is it $\gamma$ accuracy or $1 - \gamma$ accuracy?

$\mathbf{Response:}$ Thank you for pointing it out. It is $1 - \gamma$ accuracy and we have corrected it.

$\mathbf{Weakness 2:}$ All of the proofs only analyze one-step ... might not be very useful. & $\mathbf{Weakness 4:}$ The proof is simple and the technical contribution is limited.

$\mathbf{Response:}$ We have emphasized our main contributions in the official comments in details and we would like to emphasize them again here shortly.

1. In addition to examining the ideal scenario of perfect neural collapse, our research also explores the concept of approximate collapse, which is more prevalent in practical situations. Our results suggest that the extraordinary dimension-independent properties observed during perfect neural collapse is inherently fragile. This non-robustness is also evident in our empirical studies for both NoisyGD and NoisySGD using real datasets!

2. We wish to clarify for the reviewer that the example where the $G$ is near zero, as mentioned by the reviewer, does not align with our theory. In fact, in the proof, we choose $G$ to be the sensitivity of the gradient, and our theory is valid only when $G\geq 1$ for perfect collapse, or when $G \geq \sqrt{1 + \beta^2 p}$ for imperfect collapse. It is worth noting that even if we clip the data point with a small $G$, this does not alter our results. In fact, in the case where $K=2$, as detailed in the proof of Theorem 3 (similar results hold for the more general case, Theorem 2, and the imperfect case in Section 3.2 and Section 3.3) in Appendix A.2, $n/2$ is scaled to $Gn/2$ if $G<1$, and a smaller $G$ does not imply a smaller mis-classification error.

3. Existing analysis of DP-GD and DP-SGD focuses on suboptimality in the surrogate losses. The sample complexity is polynomial $d/\gamma$ or $d/ \sqrt{\gamma}$ (in the strongly convex case) to achieve $(1-\gamma)$-accuracy. We actually directly studied the ``0-1" loss! And we showed that the sample complexity is $\log(1/\gamma)$. This is an exponential improvement and shows an exponential benefit of strong representation learning.

4. We agree that our analysis is simple, but in light of those points in this response and the official comments above, we believe the simplicity of the analysis is a feature rather than a bug! After all, we believe the reviewer agree that our results are interesting and new. Isn’t it better to have a simpler proof of a fundamental result than a highly technical (and harder to verify) proof?

$\mathbf{Weakness 3:}$ The proposed tricks are not demonstrated empirically on real datasets.

$\mathbf{Response:}$ We wish to clarify for the reviewer that our investigation includes empirical evidence of the non-robustness of DP-finetuning to perturbations using real datasets. Specifically, our Figure 2(b), which uses a real dataset, demonstrates that SGD without DP is robust to increasing dimensions. Conversely, the accuracy of DP-SGD decreases significantly with rising dimensions.

Additionally, the phenomenon of neural collapse is a widely observed phenomenon in deep learning, as evidenced by various references cited in our paper, including the study available at https://www.pnas.org/doi/10.1073/pnas.2103091118. Related to transfer learning, a notable reference is a recent paper presented at NeurIPS, which provides evidence of neural collapse during the fine-tuning process (https://openreview.net/pdf?id=xQOHOpe1Fv).

$\mathbf{Questions:}$ Is there any ... to be accounted.

$\mathbf{Response:}$ DP-PCA has been widely adopted in DP-SGD to enhance empirical performance, as evident in ``Deep Learning with Differential Privacy" (https://arxiv.org/abs/1607.00133). We provide a perspective from neural collapse theory to explain the efficacy of PCA. Due to the time constraints of the rebuttal period, we have not conducted experiments using DP-PCA at this stage.

The reviewer is correct that DP-PCA requires a privacy-utility trade-off. However, the impact of the privacy budget on PCA's accuracy is not the focus of our paper. It's important to note that the recent theory on DP-PCA, such as the one described in ``https://arxiv.org/abs/2205.13709", cannot be directly applied to our setting since their accuracy is measured by the angle between eigenvectors. In contrast, our investigation into the 0-1 loss highlights the importance of the infinity norm between eigenvectors. Therefore, it would be interesting to establish theoretical guarantees for DP-PCA under the infinity norm.

We are grateful for your valuable feedback. In particular, Question 4 has provided us with insightful perspectives. We would like to offer the following response in return.

$\mathbf{Weakness:}$ It may be difficult for some readers to understand... I would recommend giving a high level explanation of neural collapse in the introduction to help readers.

$\mathbf{Response:}$ Thank you for these comments. We have added a high-level explanation of the neural collapse and the $K$-simplex equiangular tight frame (ETF) to the manuscript in the introduction. Neural collapse is the phenomenon where features corresponding to different classes are separable enough. An illustrative example for the case where $K=2$ is as follows: an ETF $M$ can be represented as $M = [-m_1, m_1]$ for some vector $m_1 \in \mathbb{R}^{p}$, where the features corresponding to the label $y=1$ are $m_1$, and the features corresponding to the label $y=-1$ are $-m_1$.

$\mathbf{Question 1:}$ Introduction, paragraph 1, last line: do you mean "no-privacy utility tradeoff".

$\mathbf{Response:}$ Thank you for pointing out this typo. We have corrected it.

$\mathbf{Question 2:}$ Bottom of page 7, Sigma is missing a backslash.

$\mathbf{Response:}$ Corrected.

$\mathbf{Question 3:}$ The dimension independence of Theorem 5 requires $\beta_0$ to scale with $p$, but the non-robustness results in 3.2 and 3.3 would also become dimension independent if $\beta$ chosen to vary with $p$ in a similar way. Because of this, it's not clear what we are gaining from dimension reduction in section 4.2.

$\mathbf{Response:}$ As detailed in Section 4.3, for PCA we have established that $\beta_0 \leq \frac{1}{\sqrt{m}}$ with high probability where $m$ represents the sample size used in PCA, effectively scaling $p$ to $p/\sqrt{m}.$ Our theoretical framework, at this stage, does not encompass DP-PCA, which is actually implemented in DP-SGD. Should DP-PCA be taken into account, $\beta_{0}$ would be influenced by the privacy budget. While our current paper does not concentrate on this aspect, understanding the convergence of the eigenvector in DP-PCA, particularly in terms of the infinity norm, necessitates a separate and thorough analysis.

$\mathbf {Question 4:}$ It's not clear to me how this analysis of neural collapse applies to full fine tuning ... these results might shed light on the dynamics of intermediate layers.

$\mathbf{Response:}$ Thank you for drawing attention to this intriguing topic. Our empirical findings suggest that, except in the final layer, neural collapse is typically not observed—even in settings without Differential Privacy. This is also corroborated by another paper "Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training" (https://arxiv.org/pdf/2101.12699.pdf), which explains that, from a mathematical standpoint, an Equiangular Tight Frame (ETF) is the optimal solution for Empirical Risk Minimization (ERM) when considering the features of the last layer.

Recent research, such as "The Tunnel Effect: Building Data Representations in Deep Neural Networks" by Masarczyk et al., presented at NeurIPS 2023, has made some novel observations. These include the discovery that the last few layers of deep neural networks exhibit low-rank structures, and their performance is resemblance to that of linear models. Within this context, neural collapse in the final layer can be seen as a special case of these low-rank structures, which are also present in transfer learning scenarios.

Given these developments, it would be a valuable line of inquiry for our future research to examine whether fine-tuning the last few layers with NoisySGD could reveal low-rank structures, like neural collapse --- or perhaps a partially neural collapse influenced by the noise. Due to time limitations, we will defer this investigation to subsequent studies.