When Does Symmetry Reduce Effective Rank in Zeroth-Order Optimization?

Fine-tuning large neural networks is often limited by the substantial memory overhead of backpropagation. To address this bottleneck, memory-efficient zeroth-order optimization (MeZO) enables fine-tuning using only function evaluations, but classical zeroth-order optimization (ZO) query-complexity bounds typically scale with the ambient parameter dimension. Recent theory suggests that ZO efficiency can instead depend on the effective rank, a spectral measure of how curvature is distributed across parameter directions. In this work, we show that, for smooth objectives with appropriate symmetries, the effective rank of the Hessian is bounded by the codimension of the symmetry orbit together with an explicit correction term that quantifies nonstationarity. Our bound is tight, with equality achieved by an explicit family of smooth invariant objectives. At stationary points, it recovers the exact Hessian null directions induced by symmetry. Lastly, we establish finite-sample convergence of ZO-SGD under mild conditions and obtain dimension-independent function-query bounds without assuming a dominate low-effective-rank Hessian matrix. In experiments, empirical evidences are provided to illustrate the theoretical mechanism and the connection between effective rank and ZO optimization.