# Mirror Natural Evolution Strategies

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 1 Aug 2023.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Black-box Adversarial Attacks with Limited Queries and Information](https://mlsanity.com/paper/1804.08598/) (2018)
- [The CMA Evolution Strategy: A Tutorial](https://mlsanity.com/paper/1604.00772/) (2016)
- [HopSkipJumpAttack: A Query-Efficient Decision-Based Attack](https://mlsanity.com/paper/1904.02144/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Efficient Decision-based Black-box Adversarial Attacks on Face Recognition](https://mlsanity.com/paper/1904.04433/) (2019)
- [AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks](https://mlsanity.com/paper/1805.11770/) (2018)
- [Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents](https://mlsanity.com/paper/1712.06560/) (2017)
- [CMA-ES for Hyperparameter Optimization of Deep Neural Networks](https://mlsanity.com/paper/1604.07269/) (2016)
- [Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack](https://mlsanity.com/paper/1812.11377/) (2018)
- [A note on concentration inequality for vector-valued martingales with weak exponential-type tails](https://mlsanity.com/paper/1809.02495/) (2018)

## Abstract (arXiv)

The zeroth-order optimization has been widely used in machine learning applications. However, the theoretical study of the zeroth-order optimization focus on the algorithms which approximate (first-order) gradients using (zeroth-order) function value difference at a random direction. The theory of algorithms which approximate the gradient and Hessian information by zeroth-order queries is much less studied. In this paper, we focus on the theory of zeroth-order optimization which utilizes both the first-order and second-order information approximated by the zeroth-order queries. We first propose a novel reparameterized objective function with parameters (μ, Sigma). This reparameterized objective function achieves its optimum at the minimizer and the Hessian inverse of the original objective function respectively, but with small perturbations. Accordingly, we propose a new algorithm to minimize our proposed reparameterized objective, which we call textttMiNES (mirror descent natural evolution strategy). We show that the estimated covariance matrix of textttMiNES converges to the inverse of Hessian matrix of the objective function with a convergence rate widetildeO(1/k), where k is the iteration number and widetildeO(·) hides the constant and log terms. We also provide the explicit convergence rate of textttMiNES and how the covariance matrix promotes the convergence rate.