REVIEW 4 major objections 6 minor 46 references
Natural Evolutionary Search meets Probabilistic Numerics
T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Bayesian quadrature gives natural evolution strategies a closed-form gradient, making them beat BO and piBO in the paper's tests.
desk verdict A real closed-form BQ-NES derivation, but the empirical claims need a controlled CMA-ES baseline and a misspecification check. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is Bayesian quadrature in the information-geometric optimisation (IGO) formulation: NES is recast as natural gradient descent on $g(\theta)=\mathbb{E}_{x\sim\nu_\theta}[f(x)]$ over distribution parameters, and a GP surrogate for $f$ turns the integrand into a probabilistic object. The workhorse identity is that products of Gaussian densities integrate in closed form: with $k(x,x')=\theta\mathcal{N}(x;x',\Lambda)$ and $\nu_\theta=\mathcal{N}(\mu,\Sigma)$, all Bayesian-quadrature quantities $t$, $T$, and $R$ in Proposition 1 become analytic, yielding the expected natural gradient $\mathbf{d}_t=\mathbb{E}[\nabla_\theta g(\theta_t)]$ used in Algorithm 1. A second mechanism is the variance-reduction acquisition function restricted to a Mahalanobis ball, which decides where to query next while the local GP keeps the model stationary.
What would settle it
Run the paper's own comparison protocol (Prob-CMAES versus CMAES, 15 seeds, regret versus evaluations) on a deliberately non-stationary objective such as a narrow parabolic valley surrounded by a flat plateau, with the GP kernel lengthscale fixed to the prior; if the probabilistic variant's regret is not consistently lower, the local-stationarity premise collapses.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that the distribution of the natural gradient $\nabla_\theta g(\theta)$, where $g(\theta)=\mathbb{E}_{x\sim\nu_\theta}[f(x)]$, is itself Gaussian-process-distributed when $f$ is modelled as a GP, and that for a Gaussian search distribution $\nu_\theta=\mathcal{N}(\mu,\Sigma)$ paired with an RBF kernel, every integral in its mean and covariance is closed-form (Proposition 1, Corollary 1). That makes it possible to write explicit natural-gradient updates for probabilistic versions of rank-$\mu$ CMA-ES, XNES, and SNES (Propositions 2--4), to replace passive sampling with active queries chosen by Bayesian-quadrature variance reduction, and to restrict the GP to a local Mahalanobis region to combat non-stationarity. The paper then claims these ProbNES algorithms consistently dominate their non-probabilistic NES counterparts plus BO and $\pi$BO across eight benchmark functions, nine UCI-derived optimisation tasks, latent-space optimisation with pretrained generators, hyperparameter tuning, and two locomotion tasks.
Load-bearing premise
The load-bearing premise is that the objective is locally stationary on the region defined by the current search distribution, so a GP with a fixed RBF kernel can estimate the integral and its gradient without bias.
Editorial extensions
If this is right
- Classical NES variants with a Gaussian search distribution can replace Monte Carlo gradient noise with closed-form Bayesian-quadrature gradients, removing a main source of sample inefficiency.
- Prior-aware and data-informed optimisation gets a local, exploitative alternative to global Bayesian optimisation that does not require hand-modifying the acquisition function.
- ProbNES reports a probabilistic gradient, so downstream decisions can use uncertainty in the search direction rather than a single point estimate.
- The claimed wins span synthetic functions, data-driven objectives, latent-space generation, hyperparameter tuning, and control, indicating the mechanism is not specific to one objective type.
- Ablations suggest active acquisition and local GP conditioning are both necessary; dropping either degrades performance.
Reading between the lines
- The paper does not quantify how ProbNES behaves as the search covariance widens; a plausible extrapolation is that it interpolates between classical NES and global BO, so its advantage should shrink in very flat, high-dimensional landscapes.
- A natural testable extension is calibrating the Bayesian-quadrature gradient covariance against empirical Monte Carlo noise; if the GP is misspecified, the closed-form uncertainty may be overconfident.
- The same closed-form integrals could support mixture-of-Gaussian or generative search distributions whenever the Fisher matrix is estimated numerically, which the conclusion hints at but does not demonstrate.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes ProbNES, a family of algorithms that replace the Monte Carlo natural-gradient estimate in Natural Evolution Strategies with a Bayesian Quadrature (BQ) estimate based on a Gaussian process surrogate, and that actively select query points to reduce the BQ variance. For Gaussian search distributions with an RBF kernel, the paper derives closed-form BQ formulas for the integral and its gradient (Proposition 1 and Corollary 1) and gives natural-gradient updates for probabilistic versions of rank-mu CMA-ES, XNES, and SNES (Propositions 2-4). The authors evaluate ProbNES on synthetic test functions, UCI regression problems, latent-space optimization, hyperparameter tuning, and locomotion tasks, and claim consistent improvements over the corresponding classical NES algorithms as well as over BO and piBO.
Significance. If the empirical claims hold, the paper makes a useful contribution: it provides a principled way to combine prior-aware NES with probabilistic numerics, yielding closed-form updates and an active sampling rule. The algebraic derivations in Appendices B-D are detailed and internally coherent, and the paper ships a reference implementation. The main significance is conditional on the empirical evaluation being fair and the local-stationarity modeling assumption being robust, since the stated superiority over existing methods rests on the experiments.
major comments (4)
- [Section 4.2 vs Section 5.1, Fig. 2] The Prob-CMAES variant is derived as a rank-mu-only natural-gradient update (Proposition 2), but the baseline labelled 'CMAES' is the full CMA-ES of Hansen (2016), which includes cumulative step-size adaptation and a rank-one update path. The comparison is therefore uncontrolled: any gain of Prob-CMAES over CMAES could be due to dropping these CMA-ES mechanisms rather than to the Bayesian quadrature gradient. Please add a rank-mu-only CMA-ES baseline (or implement a full probabilistic CMA-ES with step-size adaptation) and report it in Figures 2-5 before claiming consistent improvement over CMA-ES.
- [Section 4.3 and Proposition 1 / Algorithm 1, Line 9] The probabilistic gradient estimate E[grad_theta g(theta) | D] is a posterior-mean integral under the GP, and it is biased if the GP posterior mean is not a faithful model of the objective over the support of the search distribution. The paper addresses this only through the local-stationarity premise in Section 4.3, stating that by restricting the domain to a sufficiently small region defined by nu_theta(x), 'this area can be approximately viewed as stationary,' but it provides no misspecification analysis or diagnostic. If the true objective's curvature varies within the Mahalanobis ellipsoid, or if the RBF lengthscale is poorly estimated from the small active set, the BQ gradient can be systematically biased, and the active-query rule inherits the same bias. Please add a misspecification experiment (e.g., a function with spatially varying lengthscale or a deliberately miscalibrated GP) and either demonstrate robustness or narrow the general claim in the abstract to locally stationary objectives.
- [Section 5.3, Fig. 4(a)-(b)] The paper itself states for the CIFAR10 experiments that 'the task seems not complex enough ... which can be the result of overestimating class probabilities in the pretrained classifier.' With random search at essentially the same level, these two runs do not discriminate among methods and cannot be counted as evidence for the claim that ProbNES outperforms baselines on latent-space optimization. Please remove or replace these tasks with a more discriminative setup, or explicitly exclude them from the performance claims.
- [Section 5, Figures 2-5] The claim of 'consistently outperforms' is not backed by an aggregate comparison: the paper reports 95% confidence bands for individual tasks but no average ranks, win counts, or paired tests across the eight test functions, nine UCI tasks, latent-space tasks, HPO, and locomotion runs. Given that several curves overlap within confidence bands at comparable budgets, an aggregate statistic is needed to support the wording 'consistently outperforms.' This is not a theoretical flaw, but it is load-bearing for the abstract's general claim.
minor comments (6)
- [Eq. (6)] For minimization with x* a global minimizer, f(x*) - f(xt) is non-positive, so the displayed max is the least negative gap rather than a regret; please fix the sign or define the regret via the absolute value / best observed value, and clarify how the negative 'Log Regret' values in the plots are computed.
- [Section 5.3 vs Figure 4] The text says the MNIST labels are 'two and five,' while the Figure 4 captions read 'MNIST 4' and 'MNIST 5'; please align the labels.
- [Algorithm 1, Line 5 and Section 4.3] Please specify the batch acquisition procedure used to select the N active points (e.g., sequential greedy with hallucinated observations versus independent maximization of the acquisition function).
- [Section G, 'Influence of Batch Size'] The paragraph duplicates the text from the 'Influence of Mahalanobis Parameter' paragraph and refers to Figure 8 instead of Figure 9; please revise.
- [Throughout] Please use a single consistent notation for piBO (the paper alternates between 'piBO' and 'piBO') and for the ProbNES algorithm variants in the figure legends.
- [Section 5.2] Calling this setup 'semi-supervised' is misleading because no unlabeled data are used at optimization time; the task is better described as data-informed or prior-informed optimization.
Circularity Check
No significant circularity; the BQ natural-gradient updates are derived from stated GP/BQ assumptions rather than fitted to benchmark outcomes.
full rationale
ProbNES's derivation chain is self-contained. Proposition 1 is a direct application of Gaussian-process conditioning and Bayesian quadrature: E[∇θg(θ)|D] is defined as the posterior-mean integral, and the closed-form Gaussian integrals in Corollary 1 follow from standard multivariate-normal identities (product of normal densities, integration of two normal densities). The parameter updates in Propositions 2-4 are obtained by natural-gradient descent on that BQ estimate, with the GP hyperparameters fitted by marginal likelihood; no parameter is fitted to the benchmark objective values and then reported as a prediction. The benchmark tasks are used only for evaluation, not for selecting constants in the derivation. The local-stationarity assumption in Section 4.3 is a modeling premise with potential misspecification risk, but it is not circular: the gradient estimate is not defined in terms of the algorithm's own output. Self-citations (e.g., Briol et al. 2019, Hennig et al. 2022, Adachi et al. 2022) appear in background and for standard closed-form BQ identities, but the load-bearing formulas are elementary and independently verifiable, so no self-citation chain is forced. Overall, the central claim remains an empirical assertion supported by external benchmarks, not a tautology.
Assumptions & free parameters
free parameters (5)
- GP kernel hyperparameters (lengthscale, output scale, noise) =
not reported per experiment
- Natural-gradient learning rate eta =
not reported
- Batch size N and initial dataset size N0 =
ablation uses 3, 5, 10, 20
- Mahalanobis threshold alpha =
99.73% (chi-squared critical value)
- Initial search distribution nu_theta0 =
e.g., N(-1,I), N(0,I), N(0,3I)
assumptions (5)
- domain assumption The objective function f is a sample from a GP with a stationary RBF kernel.
- domain assumption The objective is approximately stationary on the local region defined by the search distribution.
- standard math Natural gradient descent in the Fisher metric on the space of search distributions is a valid way to optimize the expected objective (IGO framework).
- standard math The Fisher information matrix for the (mu, vech(Sigma)) parameterisation is block diagonal with F^{-1} = diag(Sigma, 2 Sigma x Sigma).
- domain assumption The posterior mean integral E(g(theta)) = integral m_post d nu_theta is a sufficient proxy for the true expectation when computing natural gradients.
Cite this review
Pith. "Pith review of Natural Evolutionary Search meets Probabilistic Numerics." pith.science (2026). https://pith.science/paper/SO7DM57G
@misc{pith2026250707288,
author = {Pith},
title = {Pith review of: Natural Evolutionary Search meets Probabilistic Numerics},
year = {2026},
howpublished = {\url{https://pith.science/paper/SO7DM57G}},
note = {Machine review of arXiv:2507.07288}
}
abstract
Zeroth-order local optimisation algorithms are essential for solving real-valued black-box optimisation problems. Among these, Natural Evolution Strategies (NES) represent a prominent class, particularly well-suited for scenarios where prior distributions are available. By optimising the objective function in the space of search distributions, NES algorithms naturally integrate prior knowledge during initialisation, making them effective in settings such as semi-supervised learning and user-prior belief frameworks. However, due to their reliance on random sampling and Monte Carlo estimates, NES algorithms can suffer from limited sample efficiency. In this paper, we introduce a novel class of algorithms, termed Probabilistic Natural Evolutionary Strategy Algorithms (ProbNES), which enhance the NES framework with Bayesian quadrature. We show that ProbNES algorithms consistently outperforms their non-probabilistic counterparts as well as global sample efficient methods such as Bayesian Optimisation (BO) or $\pi$BO across a wide range of tasks, including benchmark test functions, data-driven optimisation tasks, user-informed hyperparameter tuning tasks and locomotion tasks.
Figures
Figures from the paper (8 more)
Reference graph
Works this paper leans on
- [1]
- [2]
-
[3]
Y. Akimoto, Y. Nagata, I. Ono, and S. Kobayashi. Bidirectional relation between CMA evolution strategies and natural evolution strategies. In Parallel Problem Solving from Nature, PPSN XI: 11th International Conference, Krak \'o w, Poland, September 11-15, 2010, Proceedings, Part I 11 , pages 154--163. Springer, 2010
work page 2010
-
[4]
J. Bergstra and Y. Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13 0 (2), 2012
work page 2012
-
[5]
J. Bergstra, R. Bardenet, Y. Bengio, and B. K \'e gl. Algorithms for hyper-parameter optimization. Advances in neural information processing systems (NeurIPS), 24, 2011
work page 2011
- [6]
-
[7]
G. Cornuejols, J. Pe \ n a, and R. T \"u t \"u nc \"u . Optimization methods in finance. Cambridge University Press, 2018
work page 2018
-
[8]
L. Deng. The MNIST database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29 0 (6): 0 141--142, 2012
work page 2012
Show all 46 references
-
[9]
Eriksson, M
D. Eriksson, M. Pearce, J. Gardner, R. D. Turner, and M. Poloczek. Scalable global optimization via local B ayesian optimization. Advances in neural information processing systems (NeurIPS), 32, 2019
2019
-
[10]
R. Garnett. Bayesian optimization. Cambridge University Press, 2023
2023
-
[11]
G \'o mez-Bombarelli, J
R. G \'o mez-Bombarelli, J. N. Wei, D. Duvenaud, J. M. Hern \'a ndez-Lobato, B. S \'a nchez-Lengeling, D. Sheberla, J. Aguilera-Iparraguirre, T. D. Hirzel, R. P. Adams, and A. Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. A...
2018
-
[12]
Grosnit, R
A. Grosnit, R. Tutunov, A. M. Maraval, R.-R. Griffiths, A. I. Cowen-Rivers, L. Yang, L. Zhu, W. Lyu, Z. Chen, J. Wang, et al. High-dimensional B ayesian optimisation with variational autoencoders and deep metric learning. arXiv preprint arXiv:2106.03609, 2021
2021 arXiv
-
[13]
N. Hansen. The CMA evolution strategy: A tutorial. arXiv preprint arXiv:1604.00772, 2016
2016 arXiv
-
[14]
Hansen and A
N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary computation, 9 0 (2): 0 159--195, 2001
2001
-
[15]
Hennig, M
P. Hennig, M. A. Osborne, and H. P. Kersting. Probabilistic Numerics: Computation as Machine Learning. Cambridge University Press, 2022
2022
-
[16]
J. H. Holland. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. MIT press, 1992
1992
-
[17]
Hvarfner, D
C. Hvarfner, D. Stoll, A. Souza, M. Lindauer, F. Hutter, and L. Nardi. BO : Augmenting acquisition functions with user beliefs for B ayesian optimization. In International Conference on Learning Representations (ICLR), 2022
2022
-
[18]
Hvarfner, F
C. Hvarfner, F. Hutter, and L. Nardi. A general framework for user-guided B ayesian optimization. In International Conference on Learning Representations (ICLR), 2024. URL https://openreview.net/forum?id=NjU0jtXcYn
2024
-
[19]
N. Jean, S. M. Xie, and S. Ermon. Semi-supervised deep kernel learning: Regression with unlabeled data by minimizing predictive variance. Advances in Neural Information Processing Systems (NeurIPS), 31, 2018
2018
-
[20]
Jeong and H
T. Jeong and H. Kim. Objective bound conditional G aussian process for B ayesian optimization. In International Conference on Machine Learning (ICML), pages 4819--4828. PMLR, 2021
2021
-
[21]
Kennedy and R
J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of ICNN'95-international conference on neural networks, volume 4, pages 1942--1948. ieee, 1995
1942
-
[22]
M. E. Khan and H. Rue. The B ayesian learning rule. Journal of Machine Learning Research, 24 0 (281): 0 1--46, 2023. URL http://jmlr.org/papers/v24/22-0291.html
2023
-
[23]
D. P. Kingma and M. Welling. Auto-encoding variational B ayes. In International Conference on Learning Representations (ICLR), 2014. URL https://openreview.net/forum?id=33X9fd2-9FyZd
2014
-
[24]
Klein, Z
A. Klein, Z. Dai, F. Hutter, N. Lawrence, and J. Gonzalez. Meta-surrogate benchmarking for hyperparameter optimization. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019
2019
-
[25]
Krizhevsky, V
A. Krizhevsky, V. Nair, and G. Hinton. CIFAR -10 (canadian institute for advanced research), 2024. URL http://www.cs.toronto.edu/ kriz/cifar.html
2024
-
[26]
K. N. Markelle Kelly, Rachel Longjohn. The uci machine learning repository, 2024. URL https://archive.ics.uci.edu
2024
-
[27]
N. Maus, H. T. Jones, J. S. Moore, M. J. Kusner, J. Bradshaw, and J. R. Gardner. Local latent space B ayesian optimization over structured inputs. Advances in neural information processing systems (NeurIPS), 35: 0 34505--34518, 2022
2022
-
[28]
J. Mockus. On the B ayes methods for seeking the extremal point. IFAC Proceedings Volumes, 8 0 (1, Part 1): 0 428--431, 1975. doi:https://doi.org/10.1016/S1474-6670(17)67769-3
1975 doi
-
[29]
J. A. Nelder and R. Mead. A simplex method for function minimization. The computer journal, 7 0 (4): 0 308--313, 1965
1965
-
[30]
L. Ngo, H. Ha, J. Chan, V. Nguyen, and H. Zhang. High-dimensional B ayesian optimization via covariance matrix adaptation strategy. Transactions on Machine Learning Research (TMLR), 2024. ISSN 2835-8856. URL https://openreview.net/forum?id=eTgxr7gPuU
2024
-
[31]
Nguyen and M
V. Nguyen and M. A. Osborne. Knowing the what but not the where in B ayesian optimization. In International Conference on Machine Learning (ICML), pages 7317--7326. PMLR, 2020
2020
-
[32]
Nomura, S
M. Nomura, S. Watanabe, Y. Akimoto, Y. Ozaki, and M. Onishi. Warm starting CMA-ES for hyperparameter optimization. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 9188--9196, 2021
2021
-
[33]
A. O'Hagan. Bayes-- H ermite quadrature. Journal of Statistical Planning and Inference, 29 0 (3): 0 245--260, 1991. URL https://doi.org/10.1016/0378-3758(91)90002-V
1991 doi
-
[34]
Ollivier, L
Y. Ollivier, L. Arnold, A. Auger, and N. Hansen. Information-geometric optimization algorithms: A unifying picture via invariance principles. Journal of Machine Learning Research (JMLR), 18 0 (1): 0 564--628, 2017
2017
-
[35]
M. A. Osborne, R. Garnett, and S. J. Roberts. Gaussian processes for global optimization. In International Conference on Learning and Intelligent Optimization (LION3), 2009. URL https://ora.ox.ac.uk/objects/uuid:7d2b38d0-43be-4bb4-852c-50001a28ead9/files/sq237ht37z
2009
-
[36]
K. B. Petersen, M. S. Pedersen, et al. The matrix cookbook. Technical University of Denmark, 7 0 (15): 0 510, 2008
2008
-
[37]
C. E. Rasmussen and Z. Ghahramani. Bayesian M onte C arlo. In Advances in Neural Information Processing Systems (NeurIPS), volume 15, pages 505--512, 2002. URL https://proceedings.neurips.cc/paper_files/paper/2002/file/24917db15c4e37e421866448c9ab23d8-Paper.pdf
2002
-
[38]
C. E. Rasmussen, C. K. Williams, et al. Gaussian processes for machine learning, volume 1. Springer, 2006
2006
-
[39]
Snoek, K
J. Snoek, K. Swersky, R. Zemel, and R. Adams. Input warping for B ayesian optimization of non-stationary functions. In E. P. Xing and T. Jebara, editors, International Conference on Machine Learning (ICML), volume 32, pages 1674--1682, 2014
2014
-
[40]
Souza, L
A. Souza, L. Nardi, L. B. Oliveira, K. Olukotun, M. Lindauer, and F. Hutter. Bayesian optimization with a prior for the optimum. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), pages 265--296. Springer, 2021
2021
-
[41]
M. L. Stein. Interpolation of spatial data. Springer Science & Business Media, 1999
1999
-
[42]
Surjanovic and D
S. Surjanovic and D. Bingham. Virtual library of simulation experiments: Test functions and datasets. Retrieved October 11, 2024, from http://www.sfu.ca/ ssurjano, 2024
2024
-
[43]
Todorov, T
E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026--5033. IEEE, 2012
2012
-
[44]
Tripp, E
A. Tripp, E. Daxberger, and J. M. Hern \'a ndez-Lobato. Sample-efficient optimization in the latent space of deep generative models via weighted retraining. Advances in Neural Information Processing Systems (NeurIPS), 33: 0 11259--11272, 2020
2020
-
[45]
Wierstra, T
D. Wierstra, T. Schaul, T. Glasmachers, Y. Sun, J. Peters, and J. Schmidhuber. Natural evolution strategies. Journal of Machine Learning Research (JMLR), 15 0 (1): 0 949--980, 2014
2014
-
[46]
L. Xu, C. Hu, and K. Mei. Semi-supervised regression with manifold: A B ayesian deep kernel learning approach. Neurocomputing, 497: 0 76--85, 2022
2022
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.