Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling

Alexander Sholokhov, Alexander Rogozin

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 $\hatΣ$ that encodes the underlying low-dimensional geometry. Under a standard structural spectral normalization where $λ_{\max}(\hatΣ) = 1$, we introduce the use of the empirical effective dimension $d^* = \operatorname{tr}(\hatΣ)$, 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…