analiza aiqbench
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.
Text integral sub licența deschisă a publicației · 270 cuvinte
Subiecte conexe
Inference for Newton Methods with Accelerated Sketch-and-Project via Random Scaling
arXiv · 14 sept. 2026
Lattice-Based Cryptography Explained
Quantum Zeitgeist · 15 aug. 2026
Challenge: Hand coding weights for efficient sequence memorisation
AI Alignment Forum · 23 iul. 2026
Iteratively Tuning hipBLASLt TensileLite Kernels: A Smaller Search, a Faster Kernel
AMD · 9 sept. 2026