Zeroth-order method adapts sampling to problem structure automatically
A Parameter-Free Zeroth-Order Method with Covariance Matrix Adaptation and Effective Dimension
Machine Learning
Summary
Some problems are hard to solve because you can't directly measure how good an answer is, making usual methods that need gradients useless. The paper introduces POEM-CMA, a way to explore solutions by focusing on the most important directions automatically, without needing to set parameters. This approach uses a matrix to understand the problem's key features, making it faster and more efficient on problems that have simpler underlying structures. Tests on classification tasks show it works better than previous methods.
What this means in practice
- •For machine learning engineers: Optimize models and hyperparameters without gradients by focusing search on informative directions in complex problems automatically.
- •For operations research teams: Solve black-box optimization problems with underlying low-rank structure efficiently by reducing the search complexity via adaptive sampling.
Authors
Alexander Sholokhov, Alexander Rogozin
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Σ)}{λ_{\max}(\hatΣ)}$, 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^* κ(\hatΣ) 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.