aiqbench analysis
POEM-CMA advances black-box optimization by leveraging covariance matrix adaptation to focus sampling on intrinsic problem dimensions rather than relying on isotropic noise. This parameter-free approach achieves near-optimal convergence rates for low-rank structures, offering a more efficient alternative for scenarios where gradient information is unavailable or costly. The method demonstrates practical superiority in binary classification tasks, addressing a critical bottleneck in hyperparameter tuning and reinforcement learning without requiring manual parameter adjustment.
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 $\tilde{\mathcal{O}}\left(\frac{d^* \kappa(\hat{\Sigma}) L^2 D_{\mathcal{X}}^2}{\varepsilon^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.
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 $\tilde{\mathcal{O}}\left(\frac{d^* \kappa(\hat{\Sigma}) L^2 D_{\mathcal{X}}^2}{\varepsilon^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.
Optimization and Control (math.OC); Machine Learning (cs.LG)
arXiv:2609.38561 [math.OC]
(or arXiv:2609.38561v1 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2609.38561 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 270 words
Related coverage
Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
arXiv · Sep 14, 2026
Lattice-Based Cryptography Explained
Quantum Zeitgeist · Aug 15, 2026
Challenge: Hand coding weights for efficient sequence memorisation
AI Alignment Forum · Jul 23, 2026
Iteratively Tuning hipBLASLt TensileLite Kernels: A Smaller Search, a Faster Kernel
AMD · Sep 9, 2026