arXiv：cs.LG· Alexander Sholokhov, Alexander Rogozin·· 3 小时前
POEM-ES：基于椭球采样的无参数零阶优化算法
Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling
AI 导读
研究者提出 POEM-ES，一种无参数随机零阶优化算法，通过子空间预条件与椭球随机采样扩展了 POEM 方法，用固定 SPSD 预条件器引导各向异性采样。该方法引入经验有效维度 d* = tr(Σ̂)，在低秩结构假设下实现降维收敛率，仅需 Õ((r²κ(Σ̂)+d*)L²D_X²/ε²) 次零阶 oracle 查询，在 LibSVM 数据集的 hinge-loss 二分类任务上优于原 POEM。
正文
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 $\hat{\Sigma}$ that encodes the underlying low-dimensional geometry. Under a standard structural spectral normalization where $\lambda_{\max}(\hat{\Sigma}) = 1$, we introduce the use of the empirical effective dimension $d^* = \operatorname{tr}(\hat{\Sigma})$, 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 $\tilde{\mathcal{O}}\left( \frac{\left( r^2 \kappa(\hat{\Sigma}) + d^* \right) 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.
| Subjects: | Optimization and Control (math.OC); Machine Learning (cs.LG) |
| Cite as: | arXiv:2609.38561 [math.OC] |
| (or arXiv:2609.38561v2 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2609.38561 arXiv-issued DOI via DataCite |
Submission history
From: Alexander Sholokhov [view email]
[v1]
Tue, 29 Sep 2026 21:22:43 UTC (137 KB)
[v2]
Thu, 8 Oct 2026 14:17:42 UTC (120 KB)
来源：arXiv：cs.LG · arxiv.org