Finite-Time Hessian Sketching Below the Effective-Dimension Threshold

Distributed Hessian sketching gives each worker only a small sketched matrix. Averaging the workers' Newton directions reduces random error, but not the bias that all small sketches share. Positive-shift debiasing requires the sketch size $m$ to exceed the effective dimension $d_1(\lambda )$; we study memory-capped workers with smaller $m$. Below a stricter fold threshold $d_2(\lambda )$, no stable sketched inverse, with a positive or a negative shift, recovers the mean Newton direction once the gradient has components on two distinct Hessian eigenvalues, and adding workers cannot remove this error. We introduce $\text{finite-time Hessian sketching}$ (FT): each worker runs a negatively shifted gradient flow on its sketched quadratic and stops it at a finite time, which keeps the worker operator positive semidefinite even when the shifted sketched Hessian is indefinite. For proportional Gaussian sketches of a Hessian with a few large eigenvalues over a tail of high effective rank, under weak regularization, let $\zeta$ be the ratio of the sketched-tail spread to the smallest large eigenvalue. When the large eigenvalues and the gradient's weights on them stay in fixed proportion, every stable shifted inverse keeps a mean-direction error of at least order ${\zeta }^2$, whereas FT with explicit parameters reaches $O({\zeta }^4{\log }^2(1/\zeta ))$ under conditions on the tail spread. Averaging $q$ workers of a fixed policy reduces the remaining variance at rate $1/q$, which gives contraction bounds on quadratics without $m>d_1(\lambda )$. Experiments confirm the predicted response matching and worker crossover and show fewer outer iterations on synthetic and real-data problems with small local sketches.