Projected Hessian Direction Estimation by Comparisons under Holder Smoothness

We study the estimation of Hessian-vector directions $\nabla^2 f(x)y/\nr{\nabla^2 f(x)y}$ from a comparison oracle, the primitive underlying the comparison-based stationary-point method of \citet{wang2026finding}, when the Hessian is only $\beta$-H\"older continuous. We first observe that the three-direction construction of that work, which combines the normalized gradients at $x$ and $x\pm ry$, is exact for quadratic objectives but not consistent in general: as $r\to0$ its output converges to an explicit direction that differs from the target whenever the even part of the gradient remainder has a component along $P\nabla^2 f(x)y$, where $P=I-\hg\hg^{\top}$, and under a $\beta$-H\"older Hessian with $\beta<1$ it can converge to $\pm\nabla f(x)/\nr{\nabla f(x)}$. The gradient-parallel component of $\nabla^2 f(x)y$ is encoded only in the difference of two $O(r)$ angles. We then show that the gradient-orthogonal component is recoverable: the normalized difference of the two gradient directions at $x\pm ry$ estimates $P\nabla^2 f(x)y/\nr{P\nabla^2 f(x)y}$ with error $O(L_\beta r^\beta)+O(\xi\nr{\nabla f(x)}/r)$, which gives a probing radius of order $\delta^{1/\beta}$. The normalized-Hessian recovery of \citet{wang2026finding} then carries over to $\nabla^2 f(x)-(\hg^{\top}\nabla^2 f(x)\hg)\hg\hg^{\top}$, and we discuss the consequences for comparison-based second-order optimization.