Improving Convergence Guarantees of Random Subspace Second-order Algorithm for Nonconvex Optimization

In recent years, random subspace methods have been actively studied for large-dimensional nonconvex problems. Recent subspace methods have improved theoretical guarantees such as iteration complexity and local convergence rate while reducing computational costs by deriving descent directions in randomly selected low-dimensional subspaces. This paper proposes the Random Subspace Homogenized Trust Region (RSHTR) method with the best theoretical guarantees among random subspace algorithms for nonconvex optimization. RSHTR achieves an ε-approximate first-order stationary point in O(ε -3/2 ) iterations, converging locally at a linear rate. Furthermore, under rank-deficient conditions, RSHTR satisfies ε-approximate second-order necessary conditions in O(ε -3/2 ) iterations and exhibits a local quadratic convergence. Experiments on real-world datasets verify the benefits of RSHTR.