Anchored randomized subspace Newton method with local superlinear convergence

Randomized subspace projection techniques offer a scalable approach to Newton-type methods by restricting updates to low-dimensional randomized subspaces. However, unlike classical Newton-type methods, they generally fail to achieve superlinear convergence near a solution. In fact, when the subspace is constructed purely at random, such fast local rates are provably unattainable, even under local strong convexity. We show that this limitation can be overcome by a minimal modification of the subspace construction. Specifically, we augment the randomized subspace with a single anchor direction computed via a randomized Kaczmarz-type procedure. This simple addition improves the alignment of the subspace with local curvature. Under local-strongly-convex assumptions, we establish superlinear convergence for randomized subspace variants of quadratic and cubic regularized Newton methods. Our results demonstrate that fast local convergence is recoverable without abandoning the subspace framework. Numerical experiments further show that the proposed method often achieves improved performance despite the additional cost of computing the anchor.