# Parameter-Free Zeroth-Order Optimization with Ellipsoidal Sampling

arXiv: https://arxiv.org/abs/2609.38561 · HTML: https://mlsanity.com/paper/2609.38561/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 25 references that are in the map.
- First posted on arXiv 29 Sep 2026.

## Builds on (most cited first, 20 of 20)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Delving into Transferable Adversarial Examples and Black-box Attacks](https://mlsanity.com/paper/1611.02770/) (2016)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning](https://mlsanity.com/paper/2006.06224/) (2020)
- [Prior Convictions: Black-Box Adversarial Attacks with Bandits and Priors](https://mlsanity.com/paper/1807.07978/) (2018)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Learning-Rate-Free Learning by D-Adaptation](https://mlsanity.com/paper/2301.07733/) (2023)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Simple random search provides a competitive approach to reinforcement learning](https://mlsanity.com/paper/1803.07055/) (2018)
- [Making SGD Parameter-Free](https://mlsanity.com/paper/2205.02160/) (2022)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points](https://mlsanity.com/paper/1809.06474/) (2018)
- [Faster Gradient-Free Algorithms for Nonsmooth Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2301.06428/) (2023)
- [Tuning-Free Stochastic Optimization](https://mlsanity.com/paper/2402.07793/) (2024)
- [An Optimal Structured Zeroth-order Algorithm for Non-smooth Optimization](https://mlsanity.com/paper/2305.16024/) (2023)
- [The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problems](https://mlsanity.com/paper/2201.12289/) (2022)
- [A Parameter-Free and Near-Optimal Zeroth-Order Algorithm for Stochastic Convex Optimization](https://mlsanity.com/paper/2502.05600/) (2025)

## Abstract (arXiv)

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 hatSigma that encodes the underlying low-dimensional geometry. Under a standard structural spectral normalization where λmax(hatSigma) = 1, we introduce the use of the empirical effective dimension d^* = operatornametr(hatSigma), 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 tildeOleft( fracleft( r2 kappa(hatSigma) + d^* right) L2 DX2varepsilon2 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.