Thank you for your questions and we will clarify your concerns!
First and foremost, we sincerely appreciate your effort in raising new questions for further exploration. We will address each of your concerns in detail below, and we hope our responses will earn your understanding and approval.
(Also we want to kindly remind you that this work primarily focuses on experimental contributions. As a result, we conduct lots of experiment result to show the performance of our method and do not extensively delve into theoretical analyses.)
**Question:convergence of HiZOO cannot outperform vanilla SGD due to the trace term, fails to justify the necessity of inverse Hessian estimator.**
**Answer:**
Thank you for your insightful comment on the convergence properties of HiZOO. As indicated in the theoretical analysis of MeZO[1] (HiZOO is an improvement based on MeZO), the loss decrease for MeZO can be expressed as:
$\mathbb{E}[L(\theta_{t+1}) | \theta_t] - L(\theta_t) \leq \frac{1}{\gamma} \left[-\eta_{SGD} \|\nabla L(\theta_t)\|^2 + \frac{1}{2} \eta_{SGD}^2 \ell \cdot \mathbb{E}[\|\nabla L(\theta; \mathcal{B})\|^2] \right],$
where $\gamma^{-1} = O(n/r)$, $n$ denotes the number of queries per iteration, and $r$ is the effective rank of the Hessian. For MeZO/HiZOO, $n = 1$, which implies that its convergence rate depends solely on $r$, the effective rank of the Hessian, rather than $d$, the parameter dimension, as in traditional SGD.
In traditional zeroth-order SGD, the efficiency is scaled by $d$, as the loss decrease is proportional to $1/d$ due to the dimensionality of the parameter space. However, since $r$ is much smaller than $d$, the factor $1/r$ in MeZO and HiZOO results in a faster loss decrease compared to $1/d$ in SGD. A detailed analysis of this can be found in the convergence analysis section of MeZO.
This distinction is significant because, as shown in Adahessian[3], Sophia[4], Shampoo[5], employing curvature information (Hessian approximations) enables algorithms to converge faster than first-order methods like SGD, especially in high-dimensional optimization problems. Specifically, the effective rank $r$ is typically much smaller than the parameter dimension $d$, owing to the low-rank property of the Hessian matrix observed in many practical machine learning scenarios.
Moreover, HiZOO improves upon MeZO by introducing second-order information through preconditioning methods that estimate the diagonal of the Hessian.
**Question:HiZOO can truly be considered a Hessian-informed method or Fisher-informed method?**
**Answer: HiZOO is definitely a Hessian-informed method.**
Thank you for raising this insightful question. Regarding the convergence properties of HiZOO, we would like to emphasize that our method indeed estimates the inverse Hessian matrix, as demonstrated in the theoretical analysis of MiNES[2]. Specifically, Lemma 11 in MiNES establishes that the sequence $\Sigma_k^{-1}$, generated by their algorithm, satisfies:
$\|\Sigma_k^{-1} - \Pi_{\mathcal{S}} (\nabla^2 f(\mu^*))\|^2 \leq \frac{C}{k},$
where $\nabla^2 f(\mu^*)$ is the Hessian matrix of the loss function $f$ at the optimal point $\mu^*$. The projection $\Pi_{\mathcal{S}}$ removes the extreme eigenvalues (both maximum and minimum) of the original Hessian matrix $\nabla^2 f(\mu^*)$, effectively regularizing it within a spectral range defined by $\mathcal{S}$. When $\mathcal{S}$ is chosen to be sufficiently large, $\Pi_{\mathcal{S}} (\nabla^2 f(\mu^*))$ becomes equivalent to $\nabla^2 f(\mu^*)$ itself, as the projection no longer affects the spectral properties of the Hessian. This result clearly demonstrates that $\Sigma_k^{-1}$ approximates $\nabla^2 f(\mu^*)$ as $k \to \infty$, at a convergence rate of $O\left(\frac{\log k}{k}\right)$.
While the MiNES paper also discusses the Fisher matrix $F_\mu$ in the context of natural gradient descent, it is important to note that this section is unrelated to our analysis. HiZOO focuses solely on the inverse covariance matrix $\Sigma_k^{-1}$, which approximates the Hessian matrix and does not involve the Fisher matrix. The distinction is particularly evident in the update rules for $\Sigma_k$, which are derived based on Hessian-specific properties rather than Fisher information.
[1]Malladi, Sadhika, et al. "Fine-tuning language models with just forward passes." Advances in Neural Information Processing Systems 36 (2023): 53038-53075.
[2]Ye, Haishan and Tong Zhang. “Mirror Natural Evolution Strategies.” ArXiv abs/1910.11490 (2019): n. pag.
[3]Yao, Z., Gholami, A., Shen, S., Keutzer, K., & Mahoney, M.W. (2020). ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning. ArXiv, abs/2006.00719.
[4]Liu, H., Li, Z., Hall, D.L., Liang, P., & Ma, T. (2023). Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training. ArXiv, abs/2305.14342.
[5]Anil, R., Gupta, V., Koren, T., Regan, K., and Singer, Y. Scalable second order optimization for deep
learning. arXiv preprint arXiv:2002.09018, 2020.