Balancing Gradient and Hessian Queries in Non-Convex Optimization

Thank you for your positive feedback and detailed comments!

Regarding your question on the efficiency of the proposed methods in practice, while this aspect is not the primary focus of our work, we agree that it is an interesting question. We hope our results open the door for such exploration. As a possible direction, we note that our algorithm only requires matrix-vector product access to $\hat{H}^{-1}$, which could admit more efficient implementations.

Regarding your question on the condition $H \preceq L_1 I$, thank you for catching this minor issue: It should instead be $H \preceq 2L_1 I$. The corrected inequality is guaranteed by the gradient Lipschitzness of $f$ and the condition that $\delta\leq L_1$.

Thank you for your positive feedback and detailed comments!

Regarding your question on the computational complexity of our algorithm, while this aspect is not the primary focus of our work, we agree that it is an interesting question. Although certain components of our algorithm, such as the eigen-decomposition step, may appear more involved than those in the classical Newton method, we note that these operations can also be implemented in $O(d^{\omega})$ time in the worst case, where $\omega$ denotes the matrix multiplication exponent [1]. This matches the cost of solving the linear system and the per-iteration cost of Newton method.

Based on this, the overall computational complexity of our algorithm under the parameter setting of Corollary 1 is $\tilde{O}(d^{7/3}/\epsilon^{3/2})$. For comparison, the restarted AGD algorithm [2] requires $O(d/\epsilon^{7/4})$ time, while the Newton method requires $O(d^2/\epsilon^{3/2})$. Thus, our algorithm improves upon the first order method when $\epsilon=O(d^{-16/3})$, and exceeds the complexity of the Newton method by only a factor of $d^{1/3}$. We may add more discussion on this in our final version.

We appreciate your thoughtful comments on the presentation of the paper. In terms of the accessibility of the paper, this is something we care about greatly and would like to improve if we can. In the submission, in Section 1.1, we included a detailed comparison with prior work along with a table that conceptualizes our contributions, in Section 2 we provided an overview of our approach, and we provided a concluding section that summarizes our algorithms and main insights. Nevertheless, we do recognize that the paper discusses trade-offs across multiple oracle models and four parameters, which inherently leads to technical complexity. If there are specific parts of the paper that you believe could benefit from clearer presentation or if you have ideas for helping the paper’s accessibility, we would be eager to hear them.

In particular, for your question on the intuition regarding the faster rate we obtained, the key insight behind the improved rate lies in Algorithm 1, which is a variant of accelerated gradient descent (AGD) in the Hessian norm. In classical AGD, the step size is chosen to be as large as possible while still respecting the smoothness condition. However, if we have access to local second-order curvature information, it becomes possible to take larger steps along directions with small curvature, thereby accelerating convergence. Algorithm 1 formalizes this intuition. If you have further questions about other aspects of our work, we would be happy to address them as well.

[1]. James Demmel Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik 2007.

[2]. Huan Li and Zhouchen Lin. Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(epsilon^(-7/4)) Complexity. ICML 2023

Thank you for your positive feedback and detailed comments!

Regarding your comment on the practicality of our algorithm, particularly the large constants and logarithmic dependencies in the query complexity, we want to kindly note that our focus in this paper was on worst-case theoretical query complexity and showing how our improved query complexities are obtainable. We agree it is an interesting direction for future work to improve these dependencies and the practicality of our method. We hope our results open the door for such exploration.

Regarding your question on the approximate Hessian oracle and its implementation, we would like to kindly clarify that each column of the approximate Hessian can be obtained using two queries to a gradient oracle via finite differences (even if the gradients are only computed approximately). As a result, the overall implementation cost is $2d$ gradient queries. This cost is implicitly reflected in the trade-off presented in Corollary 1. We will include a more detailed discussion of this point in the final version.

Regarding your question on whether the $\tilde{O}(d^{1/3})$ dependence is tight, we agree that this is an excellent question. To the best of our knowledge, there is no known matching lower bound. This term arises from the trade-off between gradient queries and Hessian queries in Theorem 1. Specifically, we require $n_H \cdot d$ gradient queries to construct the $n_H$ approximate Hessians, and $O(n_H^{-1/2}\epsilon^{-9/4})$ gradient queries to perform the AGD steps in the approximate Hessian norm. Balancing these two terms yields a total query complexity of $O(d^{1/3}\epsilon^{-3/2})$ when choosing $n_H = \Theta(d^{-2/3} \epsilon^{-3/2})$. Thus, the $\tilde{O}(d^{1/3})$ term reflects a limitation of our current analysis rather than a fundamental limitation. We will expand on this discussion around Lines 274–277 in the final version.

Regarding your question regarding lower bounds for the new trade-off regimes, we would like to kindly note that dimension-dependent lower bounds for critical point computation are not completely understood. To the best of our knowledge, existing dimension dependent lower bounds are limited to the low-dimensional setting and do not assume Hessian Lipschitzness of the function. Moreover, establishing tight lower bounds in our setting would require improving the current $\Omega(\epsilon^{-12/7})$ lower bound for gradient computations for a function with Lipschitz gradient and Hessian, which has remained open for several years. For this reason, we view the development of tight lower bounds in our regime as an independent and interesting open problem. We will include a more detailed discussion of lower bounds in the low-dimensional and Hessian-only settings in the final version.

Regarding your question on inexact Hessian approximations. While our current algorithm is presented under the assumption that the Hessian approximation is obtained deterministically, the framework naturally extends to settings where the approximation is computed via non-deterministic means, including stochastic oracles. A straightforward approach in the stochastic setting is to compute a mini-batch average of stochastic Hessians whenever a Hessian estimate is needed, ensuring that the approximation error is bounded by $\tilde{\delta}$, as defined in Equation (8). This would introduce terms such as $\sigma / \tilde{\delta}$ in the complexity. We view it as an interesting open problem to explore whether improved bounds can be obtained in this setting using more advanced techniques.

Regarding your question regarding the practicality and computational complexity of spectral computations, while this aspect is not the primary focus of our work, we agree that it is an interesting question and thank you for asking. Although certain components of our algorithm, such as the eigendecomposition step, may appear more involved than those in the classical Newton method, we note that these operations can also be implemented in $O(d^{\omega})$ time in the worst case, where $\omega$ denotes the matrix multiplication exponent [1]. This matches the worst-case cost of solving a dense linear system and the worst-case per-iteration cost of Newton method. We agree with you that it is an interesting open question to develop an algorithm with the same theoretical guarantee and is more practical to implement. Notably, our algorithm only requires matrix-vector product access to $\hat{H}^{-1}$, which suggests potential for more efficient implementations. While directly applying Krylov subspace methods in our setting may be nontrivial, we hope our results open the door to practical variants of our approach and worth further exploration.

[1]. James Demmel, Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik 2007.

Thank you for your positive feedback and detailed comments!

Regarding your question regarding the computational complexity of our algorithm, while this aspect is not the primary focus of our work, we agree that it is an interesting question and thank you for asking. Although certain components of our algorithm, such as the eigendecomposition step, may appear more involved than those in the classical Newton method, we note that these operations can also be implemented in $O(d^{\omega})$ time in the worst case, where $\omega$ denotes the matrix multiplication exponent [1]. This matches the worst-case cost of solving a dense linear system and the worst-case per-iteration cost of Newton method.

Regarding your question on the origin of the logarithmic terms in the approximate Hessian estimate, we first note the following intuition: our rescaled Hessian AGD framework is stable under constant-factor perturbations in the eigenvalues of $H$. That is, changing an eigenvalue $\lambda$ to $2\lambda$ or $\lambda/2$ does not affect the asymptotic convergence. To formalize this, our analysis partitions the eigenspace of $H$ into $O(\log(L_1/\delta))$ groups based on eigenvalue magnitude, as detailed in Appendix C. Within each group, eigenvalues are either $\delta$-close to zero or differ by at most a constant factor. This grouping is the source of the logarithmic term.

As for how this appears in the algorithm, our analysis requires that the spectrum of the normalized matrix $\hat{H}^{-1/2} H \hat{H}^{-1/2}$ closely approximates that of $H$. In particular, the relative ordering and grouping of eigenvalues must be preserved—eigenvalues that belong to the same group in $H$ must remain in the same group after normalization. The explicit truncation steps based on this logarithmic grouping ensure that this spectral structure is maintained. We agree with you that finding a simpler construction of $\hat{H}$ that suffices is a wonderful question for future research.

Regarding your question on the asymptotic $d$-dependence in the bound of Corollary 1, we thank you for pointing it out and will correct it in the final version.

[1]. James Demmel Ioana Dumitriu, and Olga Holtz. Fast linear algebra is stable. Numerische Mathematik 2007.