Fast Convergence to Second-Order Stationary Point through Random Subspace Optimization

We propose the Random Subspace Homogenized Trust Region (RSHTR) method, which efficiently solves high-dimensional non-convex optimization problems by identifying descent directions within randomly selected subspaces. RSHTR provides the strongest theoretical guarantees among random subspace algorithms for non-convex optimization, achieving an ε-approximate first-order stationary point in O(ε-3/2) iterations and converging locally at a linear rate. Furthermore, under rank-deficient conditions, RSHTR satisfies ε-approximate second-order necessary condition in O(ε-3/2) iterations and exhibits a local quadratic convergence.