Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling
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-ES, a novel parameter-free stochastic zeroth-order algorithm that extends the recent POEM method by integrating subspace preconditioning with ellipsoidal randomized sampling. In contrast to traditional zeroth-order approaches that rely on isotropic random directions, POEM-ES performs anisotropic sampling guided by a fixed structural symmetric positive semi-definite (SPSD) preconditioner Σ̂ that encodes the underlying low-dimensional geometry. Under a standard structural spectral normalization where λmax(Σ̂) = 1, we introduce the use of the empirical effective dimension d* = tr(Σ̂), which reflects the intrinsic dimensionality of the problem and guides both the sampling and randomized smoothing parameter schedules. In practice, such a preconditioner can be effectively obtained via pilot sampling, historical trajectories, or domain-specific expert knowledge. We prove that POEM-ES achieves a dimension-reduced convergence rate under low-rank structural assumptions, requiring only 𝒪̃( (( r2 κ(Σ̂) + d* ) L2 D𝒳2)/ε2 ) 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* ≪ d. Numerical experiments on hinge-loss binary classification tasks using LibSVM datasets confirm the practical superiority of the proposed approach.
Related
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
- Stochastic Lie-Bracket Approximations for Zeroth-Order Optimization on Manifolds
- Training with ML-labeled Data via Stochastic First- and Zeroth-Order Optimization
- ZO-COSMO: Index-Free One-Hop Mixing for Decentralized Zeroth-Order Optimization
BibTeX
@misc{sholokhov2026parameterfree,
title = {{Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling}},
author = {Alexander Sholokhov and Alexander Rogozin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.38561},
eprint = {2609.38561},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38561},
}
RIS
TY - UNPB
TI - Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling
AU - Alexander Sholokhov
AU - Alexander Rogozin
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2609.38561
UR - https://arxiv.org/abs/2609.38561
AB - Zeroth-order optimization methods are essential for solving black-box problems where gradient information is unavailable or expensive to compute. This paper presents POEM-ES, a novel parameter-free stochastic zeroth-order algorithm that extends the recent POEM method by integrating subspace preconditioning with ellipsoidal randomized sampling. In contrast to traditional zeroth-order approaches that rely on isotropic random directions, POEM-ES performs anisotropic sampling guided by a fixed structural symmetric positive semi-definite (SPSD) preconditioner Σ̂ that encodes the underlying low-dimensional geometry. Under a standard structural spectral normalization where λ_max(Σ̂) = 1, we introduce the use of the empirical effective dimension d^* = tr(Σ̂), which reflects the intrinsic dimensionality of the problem and guides both the sampling and randomized smoothing parameter schedules. In practice, such a preconditioner can be effectively obtained via pilot sampling, historical trajectories, or domain-specific expert knowledge. We prove that POEM-ES achieves a dimension-reduced convergence rate under low-rank structural assumptions, requiring only 𝒪̃( (( r^2 κ(Σ̂) + d^* ) L^2 D_𝒳^2)/ε^2 ) 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^* ≪ d. Numerical experiments on hinge-loss binary classification tasks using LibSVM datasets confirm the practical superiority of the proposed approach.
ER -