Sketching has also been used to construct low-rank Hessian approximations through the Sketch-and-Project framework, originally developed by [1]} for solving linear systems, and extended to general convex optimization by [2]}, [3]}, [4]} among others. The convergence properties of this family of methods have been thoroughly studied: they are known to achieve linear convergence in expectation, with the rate controlled by a so-called stochastic condition number, which is defined as the smallest eigenvalue of the expectation of the low-rank projection matrix defined by the sketch [1]}. While the per-iteration cost of stochastic Newton methods based on Sketch-and-Project is generally lower than that of the aforementioned Newton sketch methods, their convergence rates are more sensitive to the spectral properties of the Hessian [6]}, [7]}. Also, the obtained Hessian estimates are generally biased, so they are not amenable to averaging.
