Thank you for reading our rebuttal and for the follow-up comments.
**SNPE v.s. Newton in the regime $n = O(d)$.**
Thank you for the suggestion. We will include the additional plots for the regime where $n = O(d)$ in the appendix of our revision.
---
**The iteration complexity of $\log(\epsilon^{-1})/\log\log(\epsilon^{-1})$.**
Thank you for the question. Due to space constraints, we did not include the proof in the rebuttal. However, we will provide a proof sketch below.
Note that for $t \geq \mathcal{U}\_3 = \tilde{O}(\Upsilon^2 + \kappa)$, we have $\\|x_{t+1}-x^\*\\| = \tilde{O}(\frac{\Upsilon}{\sqrt{t}}) \\|x_{t}-x^\*\\|$ by Theorem 2. By unrolling the inequality, this implies that $$\\|x_{t+1}-x^\*\\| \leq \\|x_{\mathcal{U}\_3}-x^\*\\| \tilde{O}\left(\prod_{s = \mathcal{U}\_3}^t \frac{\Upsilon}{\sqrt{s}}\right) \leq \\|x_0 - x^\*\\| \tilde{O}\left(\prod_{s = \mathcal{U}\_3}^t \frac{\Upsilon}{\sqrt{s}}\right).$$ Further, for $t \geq 2\mathcal{U}\_3$, we can upper bound $\frac{\Upsilon}{\sqrt{s}}$ as follows:
- $\frac{\Upsilon}{\sqrt{s}} \leq \frac{\Upsilon}{\sqrt{\mathcal{U}\_3}} \leq 1$ for any $s \in [\mathcal{U}\_3, t/2]$,
- $\frac{\Upsilon}{\sqrt{s}} \leq \frac{\Upsilon}{\sqrt{t/2}}$ for any $s \in [t/2,t]$.
Thus, we have $$\prod_{s = \mathcal{U}\_3}^t \frac{\Upsilon}{\sqrt{s}} \leq \prod_{s = t/2}^t \frac{\Upsilon}{\sqrt{s}} \leq \left(\frac{\Upsilon}{\sqrt{t/2}}\right)^{\frac{t}{2}}.$$
To derive a complexity bound, we upper bound the required number of iterations $t$ such that $ \left(\frac{\Upsilon}{\sqrt{t/2}}\right)^{\frac{t}{2}} = \epsilon$. Taking the logarithm of both sides and with some algebraic manipulation, we obtain $$\frac{t}{2\Upsilon^2} \log \frac{t}{2\Upsilon^2} = \frac{2}{\Upsilon^2} \log \frac{1}{\epsilon}.$$ Using the [Lambert W function](https://en.wikipedia.org/wiki/Lambert_W_function), the solution can be expressed as $ \log \frac{t}{2\Upsilon^2} = W(\frac{2}{\Upsilon^2} \log \frac{1}{\epsilon}) \Rightarrow t = 2\Upsilon^2 e^{ W(\frac{2}{\Upsilon^2} \log \frac{1}{\epsilon})}$. Finally, by applying the bound $e^{W(x)} \leq \frac{2x+1}{1 + \log (x+1)}$ for any $x \geq 0$, we conclude that $t = O\left(\frac{\log(\epsilon^{-1})}{\log(\log(\epsilon^{-1}))}\right)$. Note that in the above derivation, we ignore the additional logarithmic factor $\log (t)$ in our superlinear convergence rate. However, a more careful analysis will show that it does not affect the final complexity bound. We also refer the reviewer to a similar derivation in Appendix D.2 of Jiang et al. (2023), where the authors provide the same complexity bound for a similar convergence rate of $(1+ O(\sqrt{t}))^{-t}$.
R. Jiang, Q. Jin, and A. Mokhtari. "Online learning guided curvature approximation: A quasi-Newton method with global non-asymptotic superlinear convergence." COLT 2023.