Zeroth-Order Riemannian Adaptive Regularized Proximal Quasi-Newton Optimization Method

Recently, the adaptive regularized proximal quasi-Newton (ARPQN) method has demonstrated a strong performance in solving composite optimization problems over the Stiefel manifold. However, its reliance on first-order information limits its applicability to scenarios where gradient and Hessian evaluations are unavailable or costly. In this paper, we propose a zeroth-order adaptive regularized proximal quasi-Newton method (ZO-ARPQN) for black-box composite optimization over Riemannian manifolds, particularly the Stiefel and symmetric positive definite (SPD) manifolds. The proposed method estimates the Riemannian gradient and curvature information through randomized one-point finite-difference approximations and adaptively updates a regularized quasi-Newton matrix to capture the local manifold geometry. Theoretically, we established global convergence and complex analyses under mild assumptions. More importantly, by incorporating curvature-aware regularization and random perturbations in the proximal quasi-Newton framework, we proved that ZO-ARPQN can escape strict saddle points with a high probability. This guarantees convergence to a stationary point, even in the absence of explicit gradients. Extensive numerical experiments were conducted on manifold-constrained problems, including sparse PCA and robot stiffness tuning. These demonstrated that ZO-ARPQN shows a competitive convergence behavior compared with other state-of-the-art Riemannian optimization methods, while requiring only function evaluations.