Projected Hessian Direction Estimation by Comparisons under Holder Smoothness
Liyao Chang
Abstract
We study what a comparison oracle reveals about the Hessian of a smooth nonconvex function $f$, the question behind the comparison-based stationary-point method of \citet{wang2026finding}, when the Hessian is $\beta$-H\"older continuous. We first observe that their three-direction construction for the direction of $\nabla^2 f(x)y$, built from the normalized gradients at $x$ and $x\pm ry$, is exact for quadratic objectives but not consistent in general, and we compute its limit as $r\to0$. Comparisons are invariant under monotone reparametrizations of $f$, which preserve the gradient direction $\hg$ and the scaled projected Hessian $\Hg/\nr{\nabla f(x)}$, $\Hg=\nabla^2 f(x)-(\hg^{\top}\nabla^2 f(x)\hg)\hg\hg^{\top}$, but not the curvature along the gradient. We show that the difference of the gradient directions at $x\pm ry$ estimates $P\nabla^2 f(x)y/\nr{\nabla f(x)}$, $P=I-\hg\hg^{\top}$, with error $O(L_\beta r^\beta/\nr{\nabla f(x)})+O(r^2)+O(\xi/r)$ and with no lower bound on the signal, so that $\Hg/\nr{\nabla f(x)}$ is obtained from $\widetilde O(n^2)$ comparisons. With a comparison-based line search along the gradient and a trust-region step, this gives a method that visits an $\eps$-stationary point using $\widetilde O(n^2\eps^{-(2+\beta)/(1+\beta)})$ comparisons; for $\beta=1$ this is the rate $n^2\eps^{-3/2}$ of \citet{wang2026finding}.
Chat is not available.
Successful Page Load