Projection-robust zeroth-order optimization on manifolds under heavy-tailed oracle noise
TL;DR
This work proposes PRISM-ZO, a projection-robust framework that samples low-dimensional random tangent subspaces and combines symmetric finite differences with median-of-means or Huber aggregation and establishes the unbiasedness of the correctly rescaled projected direction in expectation over the random subspace.
Abstract
Zeroth-order optimization on Riemannian manifolds is relevant when objectives are available only through function evaluations, but conventional tangent estimators can be unstable under non-Gaussian oracle errors. We propose PRISM-ZO, a projection-robust framework that samples low-dimensional random tangent subspaces and combines symmetric finite differences with median-of-means or Huber aggregation. We establish the unbiasedness of the correctly rescaled projected direction in expectation over the random subspace, quantify its conditional projection error, prove an explicit expected bound for convergence to an approximate first-order stationary point under a stated estimator-error model, and give a verifiable condition for detecting projected negative curvature. In sparse PCA experiments with 10 random seeds, PRISM-ZO variants are compared with full-dimensional zeroth-order and first-order power baselines under Gaussian, Student-t and Cauchy perturbations; the results report means, standard deviations and 95% confidence intervals and identify both beneficial and failure regimes. The hard-thresholded sparse update is treated as an empirical proxy rather than a smooth retraction.