A Parameter-Free Zeroth-Order Method with Covariance Matrix Adaptation and Effective Dimension

arXiv:2609.38561v1 Announce Type: cross Abstract: Zeroth-order optimization methods are essential for solving black-box problems where gradient information is unavailable or expensive to compute. This paper presents POEM-CMA, a novel parameter-free stochastic zeroth-order algorithm that extends the recent POEM method by integrating covariance matrix alignment and the notion of effective dimension. In contrast to traditional zeroth-order approaches that rely on isotropic random directions, POEM-CMA performs anisotropic sampling by constructing a covariance matrix from gradient estimates. This enables the algorithm to focus sampling efforts on the most informative directions. We introduce the use of the empirical effective dimension d^* = frac{operatorname{tr}(hat{Sigma})}{lambda_{max}(hat{Sigma})}, which reflects the intrinsic dimensionality of the problem and replaces the ambient dimension in both sampling and complexity analysis. We prove that POEM-CMA achieves a near-optimal convergence rate, requiring only ilde{O}left(frac{d^* kappa(hat{Sigma}) L^2 D_{X}^2}{arepsilon^2}right) stochastic zeroth-order oracle queries. The method remains fully parameter-free and demonstrates significant improvements over the original POEM in problems with low-rank structure where d^* ll d. Numerical experiments on hinge-loss binary classification tasks using LibSVM datasets confirm the practical superiority of the proposed approach.

Related

• Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning
• ZO-Act: Efficient Zeroth-Order Fine-Tuning via One-Shot Activation-Informed Low-Rank Subspaces
• ConMeZO: Adaptive Descent-Direction Sampling for Gradient-Free Finetuning of Large Language Models
• MpSub: A Momentum p-Dimensional Subspace Trust-Region Method for Derivative-Free Fine-Tuning of Large Language Models

Source: arXiv cs.LG | 2026-10-01