As a parallel approach to subsampling, Newton sketch has also been broadly investigated. [1]} proposed a generic Newton sketch method that approximates the Hessian via Johnson–Lindenstrauss (JL) transform (e.g., Hadamard transform), and the gradient is exact. Furthermore, [2]}, [3]}, [4]}, [5]} proposed different Newton sketch methods with debiased or unbiased Hessian inverse approximation. [6]} relied on a novel sketching technique called Leverage Score Sparsified (LESS) embeddings [7]} to construct a sparse sketch matrix; and studied the trade-off between the computational cost of \({\hat{}}_t\)  in (REF ) and the convergence rate of the algorithm. Similar to subsampled Newton methods, the aforementioned literature established local linear-quadratic (or linear) recursion for \(\Vert _t-{^\star }\Vert \)  in high probability. A recent work in [8]} adaptively increased the sketch size to let the linear coefficient be proportional to the iteration error, which leads to a quadratic convergence while the computational cost is also larger than typical methods. We refer to [9]} for a brief review of subsampled and sketched Newton, and their connections and empirical comparisons with first-order methods.
