Follow up on symmetric gradient noise assumption
We would like to provide more references to justify that our assumption follows from the non-DP deep learning literature (hence it is actually less constrained). Most theoretical papers that analyze the standard SGD assumes that the mini-batch gradient follows
$$\frac{1}{B}\sum_i g_i\sim \frac{\partial \hat L}{\partial w}+\xi(w)$$
where $\frac{\partial \hat L}{\partial w}$ is the oracle gradient with respect to the generalization loss, and $\xi$ is the random gradient noise with $\mathbb{E}[\xi]=0, \mathbb{E}[\xi\xi^\top]=\Sigma(w)/B$. That is, the per-sample gradient (by setting $B=1) follows
$$g_i\sim \frac{\partial \hat L}{\partial w}+\xi(w)$$
Next, the noise structure $\Sigma$ is proportional to the oracle Hessian matrix $H$, which is symmetric:
- [2*,3*,4*] below assume $\Sigma(w)=\sigma^2 H(w)$ for some constant $\sigma$
- [5*,6*] below assume $\Sigma(w)=2L(w) H(w)$ for loss $L$
- [46, 63, 12, 70] in our submission assume $\Sigma$ is the covariance matrix of some Gaussian.
**In all these cases, the gradient noise is symmetric**, which is verified in practice as well (happy to add reference for this as well). We hope this is helpful and would appreciate it if the reviewer could increase the score.
[2*] Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in
stochastic gradient descent: Its behavior of escaping from sharp minima and regularization
effects. In International Conference on Machine Learning
[3*] Stanisław Jastrz˛ebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua
Bengio, and Amos Storkey. Three factors influencing minima in SGD. arXiv preprint
arXiv:1711.04623, 2017. 3
[4*] Zhiyuan Li, Tianhao Wang, and Sanjeev Arora. What happens after SGD reaches zero loss? –a
mathematical framework. In International Conference on Learning Representations, 2022. 3
[5*] Liu Ziyin, Kangqiao Liu, Takashi Mori, and Masahito Ueda. Strength of minibatch noise in
SGD. In International Conference on Learning Representations, 2022. 3
[6*] Takashi Mori, Liu Ziyin, Kangqiao Liu, and Masahito Ueda. Logarithmic landscape and
power-law escape rate of SGD. arXiv preprint arXiv:2105.09557, 2021. 1, 3, 8